两阶段优化算法求解绿色装箱车辆路径问题

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

摘要/Abstract

摘要：

带二维装箱约束的绿色开放式车辆路径问题（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。

关键词: 开放式车辆路径问题, 二维装箱问题, 两阶段优化算法, 鲸鱼优化算法, 天际线填充算法

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

中图分类号:

TP391.9

胡蓉,江文,钱斌等 . 两阶段优化算法求解绿色装箱车辆路径问题[J]. 系统仿真学报, 2022, 34(7): 1490-1505.

Rong Hu,Wen Jiang,Bin Qian,et al . Two Stage Optimization Algorithm to Solve the Green Packing Vehicle Routing Problem[J]. Journal of System Simulation, 2022, 34(7): 1490-1505.

图/表 20

表1

符号及定义

符号	定义
$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$ 个物品左上角距车厢左上角的垂直距离

表1

图1

图2

图3

表2

解的表达

维度(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

表2

图4

图5

图6

图7

图8

图9

表3

图10

图11

表4

燃油消耗模型参数值

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

表4

表5

参数水平

参数	水平
参数	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

表5

表6

正交实验结果

参数组合编号	参数			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

表6

表7

参数平均响应

参数	水平			极差	等级
参数	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

表7

图12

表8

参考文献 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