Code and Data Repository for Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries

We present Alkaid-SDVRP, an open-source C++ package for efficiently solving the Vehicle Routing Problem with Split Deliveries (SDVRP), a classical combinatorial optimization problem which is a variant of the Capacitated Vehicle Routing Problem where the same customer can be served by multiple vehicles. The core algorithm of Alkaid-SDVRP is designed based on the Iterated Local Search and Randomized Variable Neighborhood Descent frameworks which are highly configurable and extensible. Specifically, we implement a number of predefined neighborhoods including S w a p ( p , q ) , $Swap^{}$, $SD$-$Swap^{}$, C r o s s , E x c h a n g e , and R e i n s e r t i o n which can be arbitrarily enabled, disabled, and permuted. Moreover, it is easy to develop and integrate new neighborhoods into the current framework. The primary goal of this package is to provide an effective implementation and integration of the state-of-the-art techniques for the SDVRP. Tested on the 12th DIMACS Implementation Challenge, Alkaid-SDVRP took the first place in the SDVRP track, and has been shown beyond any doubt. In addition, we hope that the package can facilitate the research for vehicle routing-related problems by providing high-quality baselines and off-the-shelf implementations.