系统仿真学报 ›› 2022, Vol. 34 ›› Issue (7): 1490-1505.doi: 10.16182/j.issn1004731x.joss.21-0060
收稿日期:
2021-01-20
修回日期:
2021-04-12
出版日期:
2022-07-30
发布日期:
2022-07-20
作者简介:
胡蓉(1974-),女,博士,副教授,研究方向为智能优化调度、物流优化。E-mail:ronghu@vip.163.com
基金资助:
Rong Hu1(), Wen Jiang1, Bin Qian1, Naikang Yu2
Received:
2021-01-20
Revised:
2021-04-12
Online:
2022-07-30
Published:
2022-07-20
摘要:
带二维装箱约束的绿色开放式车辆路径问题(green open vehicle routing problem with two-dimensional loading constraints, 2L-GOVRP)是绿色开放式车辆路径问题和二维装箱问题的集成。以最小化燃油消耗量为优化目标建立了2L-GOVRP模型,并提出一种两阶段优化算法(two stage optimization algorithm, TSOA)进行求解。TSOA的第一阶段,针对车辆路径问题,设计自适应鲸鱼优化算法(adaptive whale optimization algorithm, AWOA)进行求解,从而确定车辆初步配送路径(即2L-GOVRP的初始解),并采用4种变邻域局部操作进行局部搜索。TSOA的第二阶段,针对二维装箱问题,设计融入扰动机制的天际线填充算法(skyline filling algorithm combined with disturbance mechanism, SFA-DM)优化装箱过程,从而确保所有货物能够合理装箱。 通过对不同客户规模测试数例的仿真实验和算法比较,验证了TSOA可有效求解2L-GOVRP。
中图分类号:
胡蓉, 江文, 钱斌, 于乃康. 两阶段优化算法求解绿色装箱车辆路径问题[J]. 系统仿真学报, 2022, 34(7): 1490-1505.
Rong Hu, Wen Jiang, Bin Qian, Naikang Yu. Two Stage Optimization Algorithm to Solve the Green Packing Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(7): 1490-1505.
表3
扰动前后装箱成功率
客户规模 | 数例 | 成功率 | |
---|---|---|---|
扰动前 | 扰动后 | ||
15 | 2l_cvrp103 | 0.75 | 0.90 |
20 | 2l_cvrp403 | 0.65 | 0.80 |
21 | 2l_cvrp603 | 0.60 | 0.90 |
22 | 2l_cvrp703 | 0.60 | 0.75 |
25 | 2l_cvrp903 | 0.55 | 0.85 |
29 | 2l_cvrp1003 | 0.60 | 0.70 |
30 | 2l_cvrp1203 | 0.90 | 0.90 |
32 | 2l_cvrp1403 | 0.60 | 0.60 |
35 | 2l_cvrp1603 | 0.50 | 0.80 |
40 | 2l_cvrp1703 | 0.80 | 0.90 |
44 | 2l_cvrp1803 | 0.70 | 0.85 |
50 | 2l_cvrp1903 | 0.55 | 0.75 |
71 | 2l_cvrp2003 | 0.25 | 0.40 |
75 | 2l_cvrp2403 | 0.35 | 0.80 |
100 | 2l_cvrp2703 | 0.40 | 0.75 |
120 | 2l_cvrp2803 | 0.35 | 0.55 |
199 | 2l_cvrp3103 | 0.35 | 0.65 |
表8
AWOA与WOA的对比结果
数例 | 客户规模 | AWOA | WOA | ||||
---|---|---|---|---|---|---|---|
BST | WST | AVG | BST | WST | AVG | ||
2l_cvrp103 | 15 | 92 | 108 | 100 | 94 | 111 | 101 |
2l_cvrp403 | 20 | 126 | 138 | 134 | 128 | 152 | 136 |
2l_cvrp603 | 21 | 127 | 153 | 141 | 126 | 148 | 141 |
2l_cvrp703 | 22 | 131 | 160 | 144 | 135 | 163 | 148 |
2l_cvrp903 | 25 | 158 | 177 | 168 | 154 | 174 | 167 |
2l_cvrp1003 | 29 | 170 | 204 | 189 | 174 | 216 | 193 |
2l_cvrp1203 | 30 | 187 | 216 | 201 | 190 | 214 | 203 |
2l_cvrp1403 | 32 | 190 | 219 | 206 | 195 | 223 | 211 |
2l_cvrp1603 | 35 | 221 | 257 | 238 | 226 | 247 | 236 |
2l_cvrp1703 | 40 | 256 | 277 | 270 | 258 | 281 | 270 |
2l_cvrp1803 | 44 | 273 | 309 | 291 | 285 | 314 | 294 |
2l_cvrp1903 | 50 | 328 | 353 | 341 | 322 | 359 | 342 |
2l_cvrp2003 | 71 | 408 | 452 | 425 | 414 | 440 | 425 |
2l_cvrp2403 | 75 | 486 | 521 | 503 | 488 | 529 | 511 |
2l_cvrp2703 | 100 | 652 | 712 | 672 | 628 | 685 | 670 |
2l_cvrp2803 | 120 | 766 | 857 | 807 | 780 | 839 | 810 |
2l_cvrp3103 | 199 | 1 300 | 1 381 | 1 342 | 1 306 | 1 372 | 1 348 |
2l_cvrp3503 | 252 | 1 657 | 1 737 | 1 694 | 1 669 | 1 741 | 1 703 |
1 | 制造强国战略研究项目组. 制造强国战略研究综合卷[J]. 装备制造, 2015(6): 96-96. |
Manufacturing power strategy research project group. Comprehensive volume of manufacturing power strategy research[J]. Equipment Manufacturing (S1674-1447), 2015,(6): 96-96. | |
2 | Iori M, Juan José Salazar González, Vigo D. An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints[J]. Transportation Science (S0041-1655), 2007, 41(2): 253-264. |
3 | Wei L, Zhang Z, Zhang D, et al. A Simulated Annealing Algorithm for the Capacitated Vehicle Routing Problem with Two-dimensional Loading Constraints[J]. European Journal of Operational Research (S0377-2217), 2018, 265(3): 843-859. |
4 | 王征, 胡祥培, 王旭坪. 带二维装箱约束的物流配送车辆路径问题[J]. 系统工程理论与实践, 2011, 31(12): 2328-2341. |
Wang Z, Hu P X, Wang X P. Vehicle Routing Problem in Distribution with Two-dimensional Loading Constraint[J]. System Engineering Theory and Practice, 2011, 31(12): 2328-2341. | |
5 | Wei L, Zhang Z, Zhang D, et al. A Variable Neighborhood Search for the Capacitated Vehicle Routing Problem with Two-Dimensional Loading Constraints[J]. European Journal of Operational Research(S0377-2217), 2015, 243(3): 798-814. |
6 | Emmanouil E Zachariadis, Tarantilis Christos D, Kiranoudis Christos T. A Guided Tabu Search for the Vehicle Routing Problem with Two-dimensional Loading Constraints[J]. European Journal of Operational Research(S0377-2217), 2009, 195(3): 729-743. |
7 | Emmanouil E, Zachariadis, Christos D, al et, The Vehicle Routing Problem with Simultaneous Pick-ups and Deliveries and Two-Dimensional Loading Constraints[J]. European Journal of Operational Research (S0377-2217), 2016, 265(3): 369-386. |
8 | Leung S C H, Zhang Z, Zhang D, et al. A Meta Heuristic Algorithm for Heterogeneous Fleet Vehicle Routing Problems with Two-dimensional Loading Constraints[J]. European Journal of Operational Research (S0377-2217), 2013, 225(2): 199-210. |
9 | Sabar N R, Bhaskar A, Chung E, et al. An Adaptive Memetic Approach for Heterogeneous Vehicle Routing Problems with Two-Dimensional Loading Constraints[J]. Swarm and Evolutionary Computation (S2210-6502), 2020(58): 1-39. |
10 | 颜瑞, 朱晓宁, 张群, 等. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67-77. |
Yan Rui, Zhu Xiaoning, Zhang Qun, et al. Research of the Model and Algorithm for Two-dimensional Multi-depots Capacitated Vehicle Routing Problem with Time Window Constrain[J]. Chinese Journal of Management Science (S1003-207X), 2017, 25(7): 67-77. | |
11 | Nosrati M, Khamseh A A. Distance Discount in the Green Vehicle Routing Problem Offered by External Carriers[J]. SN Applied Sciences (S2523-3963), 2020, 2(8): 1-14. |
12 | Moghdani R, Salimifard K, Demir E, et al. The Green Vehicle Routing Problem: A Systematic Literature Review[J]. Journal of Cleaner Production (S0959-6526), 2020(279): 1-19. |
13 | Niu Y, Yang Z, Chen P, et al. Optimizi Green Open Vehicle Routing Problem with Time Windows by Minimizing Comprehensive Routing Cost[J]. Journal of Cleaner Production (S0959-6526), 2018, 171(2): 962-971. |
14 | Araghi M, Tavakkdi-moghaddam R, Jolai F, et al. A Green Multi-Facilities Open Location-Routing Problem with Planar Facility Locations and Uncertain Customer[J]. Journal of Cleaner Production (S0959-6526), 2020, 282: 1-21. |
15 | 李进, 傅培华. 基于能耗的带时间窗车辆路径问题建模与仿真[J]. 系统仿真学报, 2013, 25(6): 1147-1154. |
Li Jin, Fu Ppeihua. Model and Simulation for Vehicle Routing Problem with Time Windows Based on Energy Consumption[J]. Journal of System Simulation, 2013, 25(6): 1147-1154. | |
16 | Manerba D, Mansini R,et al. A Branch-and-cut Algorithm for the Multi Vehicle Traveling Purchaser Problem with Pairwise Incompatibility Constraints[J]. Networks (S0028-3045), 2014, 65(2): 139-154. |
17 | Fukasawa R, He Q, Song Y. A Branch-Cut-and-Price Algorithm for the Energy Minimization Vehicle Routing Problem[J]. Transportation Science (S0041-1655), 2015, 58(1): 23-34. |
18 | Letchford A N, Lysgaard J, Eglese R W. A Branch-and-cut Algorithm for the Capacitated Open Vehicle Routing Problem[J]. Journal of the Operational Research Society(S0160-5682), 2007, 58(12): 1642-1651. |
19 | Yu V F V, Lin S Y. A Simulated Annealing Heuristic for the Open Location-routing Problem [J]. Computers & Operations Research (S0305-0548), 2015, 62(l): 184-196. |
20 | Ibn Faiz T, Vogiatzis C, Noor-E-Alam M. A Column Generation Algorithm for Vehicle Scheduling and Routing Problems[J]. Computers & Industrial Engineering (S0360-8352), 2019, 130(1): 222-236. |
21 | Xia Y, Fu Z. Improved Tabu Search Algorithm for the Open Vehicle Routing Problem with Soft Time Windows and Satisfaction Rate[J]. Cluster Computing (S1386-7857), 2018, 1(2): 1-9. |
22 | Lahyani R, Gouguenheim A L, Coelho L C.A Hybrid Adaptive Large Neighbourhood Search for Multi-depot Open Vehicle Routing Problems[J]. International Journal of Production Research (S0020-7543), 2019, 57(22): 1-14. |
23 | Qian B, Wang L, Wang D X H & X. An Effective Hybrid DE-based Algorithm for Flow Shop Scheduling with Limited Buffers[J]. International Journal of Production Research (S0305-0548), 2009, 36(1): 209-233. |
24 | Mirjalili Seyedali, Lewis Andrew. The Whale Optimization Algorithm[J]. Advances in Engineering Software (S0965-9978),2016, 95(1): 51-67. |
25 | 蔡雨岑, 杜鹏桢. 基于平衡鲸鱼优化算法的无人车路径规划[J]. 控制与决策, 2021, 36(11): 1-9. |
[1] | 邸彦强, 李婷, 冯少冲, 刘琼瑶, 吕建红, 陈志佳, 张阳, 曹朋飞. 云边端架构的装备精确维修平行仿真系统[J]. 系统仿真学报, 2022, 34(09): 1909-1919. |
[2] | 李铭浩, 毕文豪, 张安, 孙文轩. 穿透性制空下无人飞行器发射母机作战体系及关键技术[J]. 系统仿真学报, 2022, 34(9): 1920-1932. |
[3] | 傅妍芳, 张楠, 魏佳宁, 曲少春, 卢颖, 刘畅. 基于OPNET的机群数据链混合TDMA协议仿真[J]. 系统仿真学报, 2022, 34(9): 1933-1940. |
[4] | 罗俊仁, 张万鹏, 袁唯淋, 胡振震, 陈少飞, 陈璟. 面向多智能体博弈对抗的对手建模框架[J]. 系统仿真学报, 2022, 34(9): 1941-1955. |
[5] | 张莉, 张惠珍, 刘冬, 陆雨欣. 考虑紧迫度的应急物资调度及粒子群算法求解[J]. 系统仿真学报, 2022, 34(9): 1988-1998. |
[6] | 祁启明, 傅瑞罡, 王平, 汪敏, 范红旗. 面向小型航空器应用的光学复眼仿真软件设计[J]. 系统仿真学报, 2022, 34(9): 1999-2008. |
[7] | 朱依婷, 闫云, 何兆成. 公交与社会车辆混合的中观交通建模与仿真[J]. 系统仿真学报, 2022, 34(9): 2019-2027. |
[8] | 李成兵, 李云飞, 吴鹏. 考虑时间特性的城市群客运网络抗毁性研究[J]. 系统仿真学报, 2022, 34(9): 2037-2045. |
[9] | 盛俊杰, 唐兆, 董少迪, 吴舒扬, 梁浩. 铁道车辆动力学云平台架构设计及原型验证[J]. 系统仿真学报, 2022, 34(9): 2056-2064. |
[10] | 张立峰, 苗雨. 一种声学层析成像温度分布高分辨率重建方法[J]. 系统仿真学报, 2022, 34(9): 2065-2073. |
[11] | 郑文, 张喆, 朱静宜. 双平台市场排他性竞争仿真[J]. 系统仿真学报, 2022, 34(9): 2098-2106. |
[12] | 金炜东, 张述礼, 唐鹏, 张曼. 基于稠密残差块与通道像素注意力的图像去雾网络[J]. 系统仿真学报, 2022, 34(8): 1663-1673. |
[13] | 张会林, 金玉洁, 杨海马. ANFIS优化磁链滑模观测器的PMSM无传感器控制[J]. 系统仿真学报, 2022, 34(8): 1682-1690. |
[14] | 谢启苗, 郭帅帅. 基于社会力模型的客船人员疏散仿真研究[J]. 系统仿真学报, 2022, 34(8): 1710-1724. |
[15] | 胡万杰, 董建军, 任睿, 陈志龙. 考虑模糊不确定的地铁货运系统成网布局规划[J]. 系统仿真学报, 2022, 34(8): 1725-1740. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||