Merge-Savings - A Construction Heuristic for Rich Vehicle Routing Problems

Felix Brandt and Andreas Cardeneo and Werner Heid and Alexander Kleff
Internation Conference on Operations Research
This contribution presents a new construction heuristic for general vehicle routing problems. The Merge-Savings algorithm is a generalization of the well-known Clarke & Wright Savings-algorithm. Moreover, our new approach implicitly includes the customer insertion operations found in the family of classical sequential and parallel insertion algorithms. We present the design goals of this algorithm, e.g. improved handling of time-windows and duration constraints compared to the Clarke & Wright algorithm, the optimization of planning problems with both depot-related as well as pickup and delivery transports in arbitrary proportions , and incremental planning, i.e. the extension of a given plan with unscheduled orders. The idea of Merge-Savings is, at each iteration, to merge two subtours into a new tour while maintaining each tour?s precedence relations. Algorithmically, this is realized by dynamic programming where each state represents the new tour constructed so far. The action set consists of choosing the next stop either from the first or the second tour. This algorithmic approach is fairly general and allows for the inclusion of constraints like multiple time windows, pickup and delivery transports, waiting time restrictions, and others as typically found in rich problems. We present computational results on real world instances realized with an implementation of Merge-Savings in the commercial vehicle routing package PTV Intertour and relate our approach to benchmark problems from the literature.
Logistik und Supply-Chain-Optimierung
Logistikoptimierung für die PTV Group
Download .bib
Download .bib
Eingetragen von
Felix Brandt