Skip to Main content Skip to Navigation
Journal articles

Tour splitting algorithms for vehicle routing problems

Abstract : Tour splitting heuristics for capacitated vehicle routing problems build one giant tour visiting all customers and split this tour into capacity-feasible vehicle trips. They are seldom used alone because of a reputation of limited performance. This paper describes how to improve them to obtain better solutions or tackle additional constraints. Numerical tests on the capacitated arc routing problem (CARP) and the capacitated vehicle routing problem (CVRP) show that randomized versions outperform classical constructive heuristics. A greedy randomized adaptive search procedure (GRASP) and an iterated local search (ILS) based on these principles even compete with published metaheuristics, while being faster and simpler.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02525151
Contributor : Daniel Gavrysiak <>
Submitted on : Monday, March 30, 2020 - 5:52:52 PM
Last modification on : Tuesday, March 31, 2020 - 2:01:04 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins, Nacima Labadie, Mohamed Reghioui. Tour splitting algorithms for vehicle routing problems. International Journal of Production Research, Taylor & Francis, 2008, 47 (2), pp.507-535. ⟨10.1080/00207540802426599⟩. ⟨hal-02525151⟩

Share

Metrics

Record views

15