Stefan Røpke, Technical University of Denmark

Abstract

This paper describes a heuristic method and a branch-and-cut algorithm for the split delivery vehicle routing problem (SDVRP). The heuristic is composed of 1) a constructive heuristic proposed by Wilck and Cavalier that provides good results for instances where customer demand is high relative to the vehicle capacity, 2) an adaptive large neighborhood search (ALNS) heuristic tailored for the SDVRP, 3) a route based model that combines routes to form a SDVRP solution. Input to the route based model can be routes from the constructive heuristic, the ALNS heuristic or it can be routes that are promising for the instance at hand. The exact method is based on a well-known two-index model that is a relaxation for the SDVRP. No-good cuts are added when an infeasible solution is detected. This approach has been used in the literature before but we improve results by separating capacity cuts with an exact algorithm and by solving the feasibility problem using a recent model proposed in the literature. In separate tests allowing more time, we show that this method performs well; we are able to prove optimality of several instances for the first time.

[Challenge Paper]   [Video]