Vehicle Routing Problem with Refined Oil Secondary Distribution Considering Workload Balance

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 14

Fig. 1

Table 1

Parameters of oil tankers

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

Table 1

Table 2

Table 3

Fig. 2

Fig. 3

Table 4

Fig. 4

Table 5

Fig. 5

Fig. 6

Table 6

Table 7

Results of medium-scale examples

加油站个数	启发式算法的平均结果		变邻域禁忌搜索算法的平均结果		结果对比
加油站个数	总成本 $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

Table 7

Fig7

References 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