Alkaid-SDVRP: An Efficient Open-Source Solver for the Vehicle Routing Problem with Split Deliveries
介绍了一个名为Alkaid-SDVRP的开源C++软件包，用于高效求解可拆分配送车辆路径问题，该问题允许同一客户由多辆车服务。该求解器基于迭代局部搜索和随机变邻域下降框架，在DIMACS竞赛中获SDVRP赛道第一名，可为相关研究提供高质量基准和现成实现。
In this paper, 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 Swap(p, q), [Formula: see text], SD-[Formula: see text], Cross, Exchange, and Reinsertion, 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 Implementation Challenge held by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), Alkaid-SDVRP took 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. History: Accepted by Ted Ralphs, Area Editor for Software Tools. Funding: Financial support from the National Natural Science Foundation of China [Grant 72101094]; the Special Project for Knowledge Innovation of Hubei Province [Grant 2022013301015175]; and Interdisciplinary Research Program of Huazhong University of Science and Technology [Grant 5003300129] is gratefully acknowledged. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0606 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0606 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .