Author:

Keywords:

Capacitated vehicle routing problem, Ruin & recreate, Optimization, Heuristics

Abstract:

Problems such as the Capacitated Vehicle Routing Problem (CVRP) attract both mathematical modellers and heuristic approaches. At present, exact mathematical approaches are capable of solving some CVRP instances with up to 360 customers. The excessive computation times incurred by such exact models does, however, severely limit their practical applicability within logistics and transportation sectors. By contrast, heuristic approaches are generally faster and easier to adapt to other problems, albeit at the expense of solution quality. Ruin & recreate represents one such heuristic approach. However, recent ruin & recreate heuristics, while being deployed for more and more problems, have been concomitant with an additive trend whereby the quantity of ruin methods and recreate methods has been systematically increasing. Essentially, improved ruin & recreate results regularly coincide with challenging to reproduce methods. This paper's approach (ASB-RR), by contrast, is formed of a single ruin method, adjacent string removal, and a single recreate method, greedy insertion with blinks. ASB-RR exhibits low computation times, robustness and yields a high number of improved benchmark solutions when compared against state of the art CVRP algorithms. Furthermore, the approach may be easily redeployed for similar problems within the field of vehicle routing.