Two Stage Optimization Algorithm to Solve the Green Packing Vehicle Routing Problem

doi:10.16182/j.issn1004731x.joss.21-0060

Abstract

Abstract:

The green open vehicle routing problem with two-dimensional loading constraints (2L-GOVRP) is integration of the green open vehicle routing problem and two-dimensional bin packing problem. The model of 2L-GOVRP is established and a two-stage optimization algorithm (TSOA) is proposed to minimize fuel consumption. In the first stage of TSOA, adaptive whale optimization algorithm (AWOA) is designed to solve the vehicle routing problem, which determine the initial delivery route of the vehicle (the initial solution of 2L-GOVRP). The algorithm has four kinds of variable neighborhoods local operation to perform a local search. In the second stage of TSOA, the skyline filling algorithm combined with disturbance mechanism (SFA-DM) is designed to solve the two-dimensional packing problem, which ensure that all cargoes can be packed reasonably. By the simulation experiment and algorithm comparison of several test cases of different customer scales, it is verified that TSOA can effectively solve 2L-GOVRP.

Key words: open vehicle routing problem, two-dimensional bin packing problem, two stage optimization algorithm, whale optimization algorithm, skyline fill algorithm

CLC Number:

TP391.9

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.

Figures/Tables 20

Table 1

Symbols and definitions

符号	定义
$F i j$	客户 $i$ 到客户 $j$ 单位燃油的行驶距离
$f$	总燃油消耗量
$d i j$	客户 $i$ 到客户 $j$ 的距离
$Q k$	车辆 $k$ 的最大载重量
$q i$	客户 $i$ 所有物品的重量
$M i$	客户 $i$ 所有物品的集合
$S i$	客户 $i$ 所有物品的底面面积总和
$P i j$	从客户 $i$ 到 $j$ 的载重系数
$L i j$	车辆从客户 $i$ 到 $j$ 的载重量
$W$	车辆的车厢宽度
$L$	车辆的车厢长度
$w k i l$	车辆 $k$ 服务客户 $i$ 中第 $l$ 个物品的宽度
$l k i l$	车辆 $k$ 服务客户 $i$ 中第 $l$ 个物品的长
$v k i l$	车辆 $k$ 服务客户 $i$ 中第 $l$ 个物品左上角距车厢左上角的水平距离
$h k i l$	车辆 $k$ 服务客户 $i$ 中第 $l$ 个物品左上角距车厢左上角的垂直距离

Table 1

Fig. 1

Fig. 2

Fig. 3

Table 2

Solution representation

维度(g)	$X i g e n [g]$	$φ i g e n [g]$	$P i g e n [g]$	维度(g)	$X i g e n [g]$	$φ i g e n [g]$	$P i g e n [g]$
1	1.28	2	5	4	0.78	5	6
2	0.59	6	1	5	2.66	1	4
3	1.17	3	3	6	0.89	4	2

Table 2

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Table 3

Fig. 10

Fig. 11

Table 4

Flow chart fuel consumption model parameter values

参数	值	数据来源
$a 0$	2.819 6	美国能源部(2009)
$a 1$	0.065 8	美国能源部(2009)
$b 0$	9.701	英国交通部(2007)
$b 1$	0.000 074 91	英国交通部(2007)

Table 4

Table 5

Parameter level

参数	水平
参数	1	2	3
$p o p$	30	50	80
$w_q$	1/3	1/2	2/3
$m a x_L$	2·n	3·n	4·n

Table 5

Table 6

Results of orthogonal experiment

参数组合编号	参数			AVG
参数组合编号	$p o p$	$w_q$	$m a x_L$	AVG
1	1	1	1	134
2	1	2	2	135
3	1	3	3	135
4	2	1	2	138
5	2	2	3	132
6	2	3	1	134
7	3	1	3	135
8	3	2	1	133
9	3	3	2	134

Table 6

Table 7

Average response value of parameters

参数	水平			极差	等级
参数	1	2	3	极差	等级
$p o p$	134.7	134.7	134.0	0.7	3
$w_q$	135.7	133.3	134.3	2.3	1
$m a x_L$	133.7	135.7	134.0	2.0	2

Table 7

Fig. 12

Table 8

References 25

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.

客户规模	数例	成功率
客户规模	数例	扰动前	扰动后
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

数例	客户规模	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]	Yanqiang Di, Ting Li, Shaochong Feng, Qiongyao Liu, Jianhong Lü, Zhijia Chen, Yang Zhang, Pengfei Cao. Parallel Simulation System of Equipment Precision Maintenance Based on Cloud-Edge-End Architecture [J]. Journal of System Simulation, 2022, 34(09): 1909-1919.
[2]	Minghao Li, Wenhao Bi, An Zhang, Wenxuan Sun. Unmanned Air Vehicles Launching Aircraft Combat System and Key Technologies for Penetrating Counterair [J]. Journal of System Simulation, 2022, 34(9): 1920-1932.
[3]	Yanfang Fu, Nan Zhang, Jianing Wei, Shaochun Qu, Ying Lu, Chang Liu. OPNET Based Simulation of Hybrid TDMA Protocol for Helicopters Datalink [J]. Journal of System Simulation, 2022, 34(9): 1933-1940.
[4]	Junren Luo, Wanpeng Zhang, Weilin Yuan, Zhenzhen Hu, Shaofei Chen, Jing Chen. Research on Opponent Modeling Framework for Multi-agent Game Confrontation [J]. Journal of System Simulation, 2022, 34(9): 1941-1955.
[5]	Li Zhang, Huizhen Zhang, Dong Liu, Yuxin Lu. Particle Swarm Algorithm for Solving Emergency Material Dispatch Considering Urgency [J]. Journal of System Simulation, 2022, 34(9): 1988-1998.
[6]	Qiming Qi, Ruigang Fu, Ping Wang, Min Wang, Hongqi Fan. Design of Optical Compound Eye Simulation Software for Small Aircraft Applications [J]. Journal of System Simulation, 2022, 34(9): 1999-2008.
[7]	Yiting Zhu, Yun Yan, Zhaocheng He. Mesoscopic Modeling and Simulation of Mixed Traffic Flow of Buses and Vehicles [J]. Journal of System Simulation, 2022, 34(9): 2019-2027.
[8]	Chengbing Li, Yunfei Li, Peng Wu. Study on Invulnerability of Urban Agglomeration Passenger Traffic Network Considering Time Characteristics [J]. Journal of System Simulation, 2022, 34(9): 2037-2045.
[9]	Junjie Sheng, Zhao Tang, Shaodi Dong, Shuyang Wu, Hao Liang. Architecture Design and Prototype Verification of Railway Vehicle Dynamics Cloud Platform [J]. Journal of System Simulation, 2022, 34(9): 2056-2064.
[10]	Lifeng Zhang, Yu Miao. A High Resolution Reconstruction Method of Temperature Distribution in Acoustic Tomography [J]. Journal of System Simulation, 2022, 34(9): 2065-2073.
[11]	Wen Zheng, Zhe Zhang, Jingyi Zhu. Simulation of the Market Exclusive Competition between Platforms [J]. Journal of System Simulation, 2022, 34(9): 2098-2106.
[12]	Weidong Jin, Shuli Zhang, Peng Tang, Man Zhang. Image Dehazing Network Based on Densely Connected Residual Block and Channel Pixel Attention [J]. Journal of System Simulation, 2022, 34(8): 1663-1673.
[13]	Huilin Zhang, Yujie Jin, Haima Yang. Sensorless Control of PMSM Based on an ANFIS Optimized Flux Sliding Mode Observer [J]. Journal of System Simulation, 2022, 34(8): 1682-1690.
[14]	Qimiao Xie, Shuaishuai Guo. Research on Passenger Ship Evacuation Simulation Based on Social Force Model [J]. Journal of System Simulation, 2022, 34(8): 1710-1724.
[15]	Wanjie Hu, Jianjun Dong, Rui Ren, Zhilong Chen. Layout Planning of Metro-based Underground Logistics System Network Considering Fuzzy Uncertainties [J]. Journal of System Simulation, 2022, 34(8): 1725-1740.