考虑工作量均衡的成品油二次配送车辆路径问题

doi:10.16182/j.issn1004731x.joss.20-0766

摘要/Abstract

摘要：

为避免工作量分配不均，研究了考虑工作量均衡的成品油二次配送车辆路径问题。以总配送成本极小化和不同车辆路径长度之差极小化为目标，建立了双目标混合整数规划模型；并设计了变邻域禁忌搜索启发式算法。利用改进的Solomon_I1插入算法求出使总配送成本尽量小的初始解；再利用变邻域禁忌搜索算法改进初始解，得到近似最优解。模拟计算结果显示，通过变邻域禁忌搜索算法改进后的解，总配送成本仅增加6.2%，车辆路径长度差值降低了45%，验证了算法的有效性。

关键词: 成品油二次配送, 车辆路径问题, 工作量均衡, 双目标混合整数规划, 变邻域禁忌搜索

Abstract:

To avoid unbalanced workload assignment, we studied the vehicle routing problem with refined oil secondary distribution considering workload balance. A bi-objectivemixed integer programming model was built to minimize the total distribution cost and the maximum difference in vehicle route length. A heuristic variable neighborhood tabu search algorithm was designed. An improved Solomon_I1 insertion algorithm was developed to generate afeasible initial solution such that the total distribution cost was as small as possible. Then, the variable neighborhood tabu search algorithm was used to improve the initial solution and thereby obtain the approximate optimal solution. The simulation results show that in the solution improved by the variable neighborhood tabu search algorithm, the difference in vehicle route length is reduced by 45% when the total distribution cost is only increased by 6.2%, which verifies the effectiveness of the algorithm.

Key words: refined oil secondary distribution, vehicle routing problem, workload balance, bi-objective mixed integer programming, variable neighborhood tabu search algorithm

中图分类号:

TP391.9

李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.

Zhenping Li, Guang Yang, Qianqian Han. Vehicle Routing Problem with Refined Oil Secondary Distribution Considering Workload Balance[J]. Journal of System Simulation, 2022, 34(2): 221-233.

图/表 14

图1

表1

油罐车相关参数

隔仓个数 $H$ (个)	单个隔舱容量 $g$ /kL	固定成本 $E$ (元)	单位行驶成本 $F$ (元/km)
3	1	120	8

表1

表2

表3

图2

图3

表4

图4

表5

图5

图6

表6

表7

中等规模算例的求解结果

加油站个数	启发式算法的平均结果		变邻域禁忌搜索算法的平均结果		结果对比
加油站个数	总成本 $w 1$ (元)	路径长度最大差值 $z 1$	总成本 $w 2$ (元)	路径长度最大差值 $z 2$	第1目标对比 $w 1 - w 2 / w 1$ /%	第2目标对比 $z 1 - z 2 / z 1$ /%
10	1 763.79	4.28	1 727.46	4.13	2.06	3.50
20	3 830.92	5.02	3 808.46	4.61	0.59	8.17
30	4 317.41	7.19	4 137.17	4.04	4.17	43.81
40	6 166.63	10.27	6 276.42	7.12	-1.78	30.67
50	7 028.95	8.97	6 697.13	7.80	4.72	13.04
60	7 690.53	11.52	7 618.31	7.40	0.94	35.76

表7

图7

参考文献 21

1	王旭坪, 韩进军, 董杰. 考虑脆弱点的成品油二次配送风险层级优化[J]. 管理学报, 2017, 14(5): 751-758.
	Wang Xuping, Han Jinjun, Dong Jie. Risk Layer-Optimization for the Secondary Distribution of Refined Oil Considering Vulnerable Centers [J]. Chinese Journal of Management, 2017, 14(5): 751-758.
2	Absi N, Archetti C, Dauzere-Peres S, et al. A Two-Phase Iterative Heuristic Approach for the Production Routing Problem[J]. Transportation Science(S0041-1655), 2015, 49(4): 784-795.
3	张立峰, 易万里, 刘晓兰. 基于两阶段算法的大规模成品油二次配送优化[J]. 系统工程理论与实践, 2016, 36(11): 2951-2963.
	Zhang Lifeng, Yi Wanli, Liu Xiaolan. Two-stage Optimization Algorithm for Large Scale Secondary Petroleum Product Delivery Planning[J]. Systems Engineering-Theory & Practice, 2016, 36(11): 2951-2963.
4	Karakati S, Podgorelec V. A Survey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem [J]. Applied Soft Computing(S1568-4946), 2015, 27: 519-532.
5	陈立伟, 唐权华. 基于Memetic算法的两级车辆路径优化[J]. 重庆大学学报, 2017, 40(3): 95-104.
	Chen Liwei, Tang Quanhua. Two-echelon Vehicle Path Optimization Based on Memetic Algorithm[J]. Journal of Chongqing University, 2017, 40(3): 95-104.
6	张源凯, 孙丽君, 胡祥培. 成品油配送多车舱车辆指派及路径优化问题研究[J]. 运筹与管理, 2017, 26(7): 1-9.
	Zhang Kaiyuan, Sun Lijun, Hu Xiangpei. Multi-compartment Vehicle Dispatching and Routing for Product Oil Distribution[J]. Operations Research and Management Science, 2017, 26(7): 1-9.
7	Lahyani R, Coelho L C, Khemakhem M, et al. A Multi-compartment Vehicle Routing Problem Arising in the Collection of Olive Oil in Tunisia[J]. Omega(S0305-0483), 2015, 51: 1-10.
8	Silvestrin P V, Ritt M. An Iterated Tabu Search for the Multi-Compartment Vehicle Routing Problem[J]. Computers and Operations Research(S0305-0548), 2017, 81: 192-202.
9	Coelho L C, Laporte G. Classification, Models and Exact Algorithms for Multi-Compartment Delivery Problems[J]. European Journal of Operational Research(S0377-2217), 2015, 242: 854–864.
10	Markov L, Bierlaire M, Cordeau J, et al. Waste Collection Inventory Routing with Non-stationary Stochastic Demands[J]. Computers & Operations Research (S0305-0548), 2020, 113: 1-18.
11	李敏, 倪少权, 周凌, 等. 基于订单邻域的成品油二次配送中带时间窗车辆路径规划问题[J]. 计算机集成制造系统, 2015, 21(8): 2158-2169.
	Li Min, Ni Shaoquan, Zhou Ling, et al. Vehicle Routing Problem with Time Windows of Petroleum Products Distribution Based on Order Neighborhood System[J]. Computer Integrated Manufacturing Systems, 2015, 21(8): 2158-2169.
12	王博弘, 梁永图, 张浩然, 等. 成品油二次配送路径优化模型及混合求解算法[J]. 油气储运, 2019, 38(11): 1251-1256.
	Wang Bohong, Liang Yongtu, Zhang Haoran, et al. Optimization Model and Hybrid Solution Algorithm for the Secondary Distribution Route of Products Oil[J]. Oil & Gas Storage and Transportation, 2019, 38(11): 1251-1256.
13	Han A F W, Chu Y C. A Multi-Start Heuristic Approach for the Split-Delivery Vehicle Routing Problem with Minimum Delivery Amounts[J]. Transportation Research Part E: Logistics and Transportation Review(S1366-5545), 2016, 88: 11-31.
14	Wang L, Kinable J, Woensel T. The Fuel Replenishment Problem: A Split-Delivery Multi-compartment Vehicle Routing Problem with Multiple Trips[J]. Computers & Operations Research(S0305-0548), 2020, 118: 104904.
15	李珍萍, 周文峰, 张煜炜, 等. 考虑卸载顺序约束的成品油二次配送车辆路径问题研究[J/OL]. 控制与决策, 1-7[2020-06-11]. .
	Li Zhenping, Zhou Wenfeng, Zhang Yuwei, et al. Research on Vehicle Routing Problem of Refined Oil Secondary Distribution Considering Unloading Sequence Constraints[J/OL]. Control and Decision, 1-7[2020-06-11]. .
16	Li Z, Zhang Y, Zhang G. Two-Stage Stochastic Programming for the Refined Oil Secondary Distribution with Uncertain Demand and Limited Inventory Capacity[J]. IEEE ACCESS(S2169-3536), 2020, 8: 119487-119500.
17	Alvarez A, Cordeau J, Jans R, et al. Inventory Routing under Stochastic Supply and Demand[J]. Omega(S0305-0483), 2020: 102304.
18	Cornillier F, Boctor F F, Laporte G, et al. An Exact Algorithm for the Petrol Station Replenishment Problem[J]. Journal of the Operational Research Society(S0160-5682), 2008, 59(5):607-615.
19	Li Z, Wu Z. Study on the Inventory Routing Problem of Refined Oil Distribution Based on Working Time Equilibrium [J]. American Journal of Operations Research(S2160-8830), 2016, 6(1): 17-24.
20	孙丽君, 石海洋, 胡祥培. 考虑司机工作量均衡的成品油配送优化[J]. 系统工程理论与实践, 2018, 38(3): 677-686.
	Sun Lijun, Shi Haiyang, Hu Xiangpei. An Optimization Method of Product Oil Distribution Considering Driver's Workload Balance[J]. Systems Engineering-Theory & Practice, 2018, 38(3): 677-686.
21	Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J]. Operations Research(S1619-4500), 1987, 35(2): 254-265.

序号	位置坐标/km	时间窗/h	服务时间/ h	油品1的需求量/kL	油品2的需求量/kL
0	(10，10)		0	0	0
1	(2，3)	[0.5，2.8]	0.12	1	1
2	(5，4)	[0.8，2.5]	0.14	1	0
3	(4，7)	[1.5，2.2]	0.13	0	2
4	(5，3)	[0.7，3]	0.10	1	2
5	(8，9)	[0.5，1.8]	0.13	1	1
6	(11，17)	[1，2]	0.10	2	1
7	(13，13)	[0.4，1.4]	0.20	1	2
8	(15，11)	[1.8，3.2]	0.14	1	1
9	(17，12)	[1.2，1.9]	0.12	0	1
10	(16，15)	[1.5，2.3]	0.15	1	1

油罐车编号	路径	路径长度/km	隔舱使用数	配送成本(元)	配送时间/h	路径长度之间的最大差值	总费用(元)
1	(0,0)-(4,1)-(1,2)-(1,1)-(0,0)	22.23	3	297.84	1.26
2	(0,0)-(2,1)-(4,2)-(0,0)	17.41	3	259.28	1.28
3	(0,0)-(9,2)-(10,2)-(10,1)-(0,0)	18.25	3	266.01	1.85
4	(0,0)-(6,2)-(6,1)-(0,0)	14.14	3	233.12	1.28	10.06	1 724.0
5	(0,0)-(5,1)-(3,2)-(0,0)	13.42	3	227.36	1.80
6	(0,0)-(7,1)-(8,2)-(8-1)-(0,0)	12.17	3	217.36	2.07
7	(0,0)-(5,2)-(7,2)-(0,0)	12.88	3	223.04	1.10

油罐车编号	路径	路径长度/km	隔舱使用个数	配送成本(元)	配送时间/h	路径长度之间的最大差值	总费用(元)
1	(0,0)-(2,1)-(1,2)-(1,1)-(0,0)	21.60	3	292.8	1.52
2	(0,0)-(4,1)-(4,2)-(0,0)	17.20	3	257.6	1.12
3	(0,0)-(6,2)-(7,2)-(0,0)	15.79	3	246.32	1.52
4	(0,0)-(5,2)-(6,1)-(0,0)	17.85	3	262.8	1.28	5.98	1 882.4
5	(0,0)-(7,1)-(3,2)-(0,0)	21.77	3	294.16	1.80
6	(0,0)-(8,1)-(10,2)-(10,1)-(0,0)	17.03	3	256.24	2.54
7	(0,0)-(5,1)-(9,2)-(8,2)-(0,0)	19.06	3	272.48	2.07

油罐车编号	路径	路径长度/km	隔舱使用个数	配送成本(元)	配送时间/h	路径长度之间的最大差值	总费用(元)
1	(0,0)-(5,2)-(9,2)-(8,1)-(0,0)	19.06	3	272.48	2.07
2	(0,0)-(8,2)-(10,2)-(10,1)-(0,0)	17.03	3	256.24	2.54
3	(0,0)-(6,1)-(7,1)-(0,0)	15.79	3	246.32	1.52
4	(0,0)-(5,1)-(1,1)-(1,2)-(0,0)	21.35	3	290.8	1.34	5..56	1 831.2
5	(0,0)-(7,2)-(6,2)-(0,0)	15.79	3	246.32	1.28
6	(0,0)-(4,1)-(4,2)-(0,0)	17.20	3	257.6	1.12
7	(0,0)-(2,1)-(3,2)-(0,0)	17.68	3	261.44	1.80

加油站个数	GUROBI求解的精确解结果				变邻域禁忌搜索算法的平均求解结果
加油站个数	优化第1层目标得到的总成本(元)	优化第2层目标得到的总成本(元)	优化第2层目标得到的路径长度最大差值	求解时间/s	平均总成本(元)	平均路径长度最大差值	平均求解时间/s
3	520.15	520.15	8.19	2.91	520.15	8.19	0.09
4	777.79	809.16	4.06	94.71	784.49	7.82	0.12
5	933.57	964.74	16.78	2 567	940.26	17.76	0.42
6	1 167.73	1 213.8	16.78	8 946	1 173.41	17.76	0.71
7					1 361.29	17.76	1.23
8					1 487.52	9.35	1.72
9					1 598.21	17.76	2.05
10					1 753.54	6.54	2.94