Simen Tung Vadseth, Norwegian University of Science and Technology

Abstract

In this paper, we propose a new matheuristic for solving the vehicle routing problem with split deliveries. The matheuristic constructs a starting feasible solution by splitting the demand at each customer into predefined partial demands, duplicating the customer nodes for each partial demand and solving the expanded graph as a normal capacitated vehicle routing problem. Once the initial solution is created, we run the improvement phase of the matheuristic to improve the set of routes in the initial feasible solution until the termination criterion is met. The proposed matheuristic is tested on 95 of the DIMACS instances, of which 43 of them are comparable to previously published results. On the set of comparable instances, we find a new best-known solution on 16 instances.

[Challenge Paper]   [Video]