The largest capacitated vehicle routing problem (CVRP) instances continue to remain unsolvable by exact mathematical algorithms, despite considerable academic progress and success over the previous decades. Such larger instances are, however, more representative of current real-world industrial challenges and they therefore necessitate the use of heuristics.

The present research introduces a single general ruin & recreate heuristic entitled Adjacent String Removal and greedy insertion with Blinks Ruin & Recreate (ASB-RR). Incorporated in a simulated annealing framework, ASB-RR proves capable of replacing current unwieldy and often unreproducible heuristics which are often over-saturated with both ruin methods and recreate methods. ASB-RR is not only capable of improving results in shorter computational times for numerous (Uchoa et al.) CVRP benchmark instances, but its general applicability has since been confirmed via its deployment across a wide variety of associated and derivative problems such as VRP with Backhauls, Simultaneous Delivery & Pickup, Open VRP and Cumulative VRP. The competitive computational results and consequent comparative analysis against state of the art heuristics resulting from experimentation across this suite of problems will be detailed and discussed.

Work supported by IWT, Conundra (Baekeland grant 130855), the Belgian Science Policy Office (BELSPO) in the Interuniversity Attraction Pole COMEX (http://comex.ulb.ac.be) and Leuven Mobility Research Center. Editorial consultation provided by Luke Connolly (KU Leuven).