Capacitated vehicle routing remains a challenging combinatorial optimization problem despite the significant academic progress of the last decades. The applicability of exact mathematical algorithms remains limited to relatively small capacitated vehicle routing problem (CVRP) instances. Heuristics are employed when solving larger size instances, which are representative of real world industrial challenges.
This abstract summarizes recent achievements in CVRP research and subsequently focuses on the development of an original powerful local search heuristic which entirely replaces the commonly applied `set of neighbourhoods or heuristics'. This new heuristic is named ruin-adjacent-customer-strings & recreate strategy for VRP (VRP RACS&R).
A simulated annealing algorithm was constructed whose internal perturbation is solely dependent on the VRP RACS&R. Experiments were set up to assess performance, in terms of both computational speed and solution quality, on the recently published set of 100 CVRP instances. Current benchmarks were obtained by both an iterated local search based matheuristic (ILS-SP) and unified hybrid genetic search (UHGS).
Producing improvements for 39 instances and equal-quality solutions for 37 instances reveal VRP RACS&R's potential to replace existing heuristics for the CVRP. Computation times are considerably less (by 40% or more) than previous state of the art algorithms.
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.
| Subject : | : | Abstracts |
| Topics | : | CVRP |
| Topics | : | Heuristics |
| PDF version | : |  PDF version |
