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

车辆路径问题 解算器 开源 计算机科学 数学优化 布线(电子设计自动化) 数学 程序设计语言 计算机网络 软件
作者
Weibo Lin,Zhu He,Shibiao Jiang,Fuda Ma,Zhouxing Su,Zhipeng Lü
出处
期刊:Informs Journal on Computing [Institute for Operations Research and the Management Sciences]
卷期号:38 (1): 150-164 被引量:3
标识
DOI:10.1287/ijoc.2024.0606
摘要

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/ .
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
小何先生完成签到 ,获得积分10
刚刚
阳光的萃完成签到,获得积分10
刚刚
领导范儿的应助被mimosa采纳,获得10
刚刚
华仔的应助被打不死的小强采纳,获得10
刚刚
汉堡包的应助被小巴采纳,获得10
1秒前
JOE完成签到,获得积分10
2秒前
liuuuuuu完成签到,获得积分10
2秒前
黄明月完成签到 ,获得积分10
3秒前
JURIIY完成签到,获得积分10
3秒前
xiaofenzi完成签到 ,获得积分10
4秒前
绿兔子完成签到,获得积分10
4秒前
Lz发布了新的文献求助10
4秒前
科研狗的应助被独特的追命采纳,获得50
5秒前
想笑的老锅完成签到,获得积分10
5秒前
活力的秋灵完成签到,获得积分10
5秒前
huoguo完成签到,获得积分10
5秒前
1111111完成签到,获得积分10
5秒前
荣初露完成签到,获得积分10
5秒前
5秒前
6秒前
boxi完成签到,获得积分0
6秒前
TcsnAIj完成签到,获得积分10
6秒前
page完成签到,获得积分10
6秒前
小碗菌完成签到,获得积分10
6秒前
无情静柏完成签到 ,获得积分10
6秒前
菜鸟完成签到,获得积分10
6秒前
2111355981完成签到 ,获得积分10
7秒前
科研助理795完成签到,获得积分0
8秒前
舒适涵山完成签到,获得积分0
8秒前
ddd完成签到 ,获得积分10
8秒前
梵强斯完成签到,获得积分10
8秒前
Siren完成签到,获得积分10
8秒前
a_mo完成签到,获得积分10
9秒前
我不爱科研完成签到,获得积分10
9秒前
德行天下完成签到,获得积分10
9秒前
cyr完成签到,获得积分10
10秒前
hus完成签到,获得积分10
10秒前
tyro完成签到,获得积分10
10秒前
10秒前
biovhys完成签到,获得积分10
10秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1500
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
八旗制度の研究 600
Analyses de reconnaissances de dettes passées devant les échevins d'Ypres (1249-1291) 600
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8159288
求助须知:如何正确求助?哪些是违规求助? 9554702
关于积分的说明 21720900
捐赠科研通 7748911
什么是DOI,文献DOI怎么找? 3427184
关于科研通互助平台的介绍 2552111
邀请新用户注册赠送积分活动 2471479