Variable neighborhood search for a new practical dynamic pickup and delivery problem

计算机科学 启发式 皮卡 变量(数学) 局部搜索(优化) 块(置换群论) 可变邻域搜索 竞赛(生物学) 数学优化 运筹学 算法 元启发式 数学 人工智能 操作系统 图像(数学) 数学分析 生物 生态学 几何学
作者
Junchuang Cai,Qingling Zhu,Qiuzhen Lin
出处
期刊:Swarm and evolutionary computation [Elsevier BV]
卷期号:75: 101182-101182 被引量:12
标识
DOI:10.1016/j.swevo.2022.101182
摘要

In today's manufacturers, a large number of cargoes like materials, semi-finished products and finished products have to be delivered among factories during the manufacturing process. Thus, this paper first introduces a new Dynamic Pickup and Delivery Problem (DPDP), which has more practical constraints like dock, time windows, capacity and last-in-first-out loading. This DPDP model can fit the practical scenarios more, which cannot be directly solved by the existing optimization algorithms. To solve this problem, this paper proposes a new Variable Neighborhood Search Algorithm with Multiple local search strategies and an Efficient disturbance, called VNSME. Specifically, each new optimization period is activated when new orders are coming, in which a variable neighborhood search is used to find the best solution for this period. At each start of a period, the best solution found in the previous period is reconstructed as an initial solution for the new period by using exhaustion and cheapest insertion heuristics. Next, four different local search strategies (couple-exchange*, block-exchange*, block-relocate* and multi-relocate*) are designed to search around the initial solution, and then the currently found best solution is further perturbed by a modified 2-opt-L* method. At last, the performance of VNSME is studied on the real-world DPDP benchmarks offered by Huawei in the competition at ICAPS 2021, where the advantages of VNSME are confirmed in the competition as its final score gets the first rank among 153 teams.

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
点点煲汤完成签到 ,获得积分10
刚刚
刚刚
潇洒乾完成签到 ,获得积分10
1秒前
369ninja的应助被llllllll采纳,获得10
1秒前
PVK完成签到,获得积分10
1秒前
Dovvvvvv发布了新的文献求助10
1秒前
Owen的应助被果仁鼠大王采纳,获得10
1秒前
你好完成签到,获得积分20
1秒前
莓莓完成签到,获得积分10
2秒前
大气南霜完成签到,获得积分20
2秒前
HLS完成签到,获得积分10
2秒前
2秒前
xiaoxiao完成签到,获得积分10
2秒前
。。。完成签到,获得积分10
2秒前
3秒前
3秒前
Xio发布了新的文献求助10
3秒前
lsj发布了新的文献求助10
3秒前
友好翠安完成签到,获得积分10
3秒前
潇洒大白发布了新的文献求助10
4秒前
我是老大的应助被zhang采纳,获得10
4秒前
4秒前
4秒前
搜集达人的应助被芝麻小丸子采纳,获得10
5秒前
5秒前
多多指教完成签到,获得积分10
5秒前
lk完成签到,获得积分10
5秒前
5秒前
fashing发布了新的文献求助10
5秒前
lpfwhu发布了新的文献求助10
5秒前
6秒前
yi5feng完成签到,获得积分10
6秒前
6秒前
苹果朋友完成签到 ,获得积分10
6秒前
6秒前
7秒前
张张发布了新的文献求助10
7秒前
小蘑菇的应助被赵舒坦采纳,获得10
7秒前
所所的应助被占博涛采纳,获得10
7秒前
zdz完成签到,获得积分10
7秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1500
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology)求助 1000
Encyclopedia of Modern Artificial Intelligence 1000
John McDowells Bildungstheorie 800
Analyses de reconnaissances de dettes passées devant les échevins d'Ypres (1249-1291) 600
Synthesis, Application and Future Perspectives of Smart Nano-materials - Part 1 400
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8152556
求助须知:如何正确求助?哪些是违规求助? 9549270
关于积分的说明 21692231
捐赠科研通 7740838
什么是DOI,文献DOI怎么找? 3425265
关于科研通互助平台的介绍 2550411
邀请新用户注册赠送积分活动 2468840