Skip to Main content Skip to Navigation
Conference papers

Order-first split-second methods for vehicle routing problems

Abstract : Cluster-first route-second methods like the sweep heuristic (Gillett and Miller, 1974) are well known in vehicle routing. They determine clusters of customers compatible with vehicle capacity and solve a traveling salesman problem for each cluster. The opposite approach, called route-first cluster-second, builds a TSP tour (also called giant tour) covering all customers and splits it into feasible trips. Cited as a curiosity for a long time but lacking numerical evaluations, this technique has led to successful solution methods for various vehicle routing problems in the last decade. As many implementations define an ordering of the customers instead of building really a giant tour, such algorithms are better called order-first split-second methods. The talk will present the principles of these approaches and examples of applications, from simple cases to less obvious contexts.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02895048
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, July 9, 2020 - 2:20:18 PM
Last modification on : Friday, July 10, 2020 - 3:36:14 AM

Identifiers

  • HAL Id : hal-02895048, version 1

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins. Order-first split-second methods for vehicle routing problems. Optimization Days 2014, 2014, Montréal, Canada. ⟨hal-02895048⟩

Share

Metrics

Record views

6