Skip to main content

Tour splitting algorithms for vehicle routing problems

Buy Article:

$55.00 plus tax (Refund Policy)

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.
No Reference information available - sign in for access.
No Citation information available - sign in for access.
No Supplementary Data.
No Data/Media
No Metrics

Keywords: Capacitated arc routing problem; Greedy randomized adaptive search procedure; Iterated local search; Route-first cluster-second heuristic; Vehicle routing problem

Document Type: Research Article

Affiliations: Institute Charles Delaunay, University of Technology of Troyes, Troyes, France

Publication date: 2009-01-01

More about this publication?
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more