Code and Data Repository for Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries
介绍了一个名为Alkaid-SDVRP的开源C++包，用于高效求解拆分配送车辆路径问题，该包基于迭代局部搜索和随机变邻域下降框架，在DIMACS挑战赛中获第一名，可为相关研究提供高质量基线和现成实现。
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.