Solving open vehicle problem with time window by hybrid column generation algorithm

doi:10.23919/JSEE.2022.000096

Journal of Systems Engineering and Electronics ›› 2022, Vol. 33 ›› Issue (4): 997-1009.doi: 10.23919/JSEE.2022.000096

收稿日期:2020-11-30 接受日期:2022-03-29 出版日期:2022-08-30 发布日期:2022-08-30

Solving open vehicle problem with time window by hybrid column generation algorithm

Naikang YU^1,²(), Bin QIAN^2,^3,*(), Rong HU^2,³(), Yuwang CHEN⁴(), Ling WANG⁵()

¹ School of Mechanical and Electrical Engineering, Kunming University of Science and Technology, Kunming 650500, China
² School of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
³ Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming 650500, China
⁴ Alliance Manchester Business School, University of Manchester, Manchester M139SS, U.K.
⁵ Department of Automation, Tsinghua University, Beijing 100084, China

Received:2020-11-30 Accepted:2022-03-29 Online:2022-08-30 Published:2022-08-30
Contact: Bin QIAN E-mail:nk_yu2020@foxmail.com;bin.qian@vip.163.com;ronghu@vip.163.com;Yu-wang.chen@mbs.ac.uk;wangling@tsinghua.edu.cn
About author:|YU Naikang was born in 1993. He received his B.S. degree in automation from Qufu Normal University, China, in 2016. He is currently pursuing his Ph.D. degree at Kunming University of Science and Technology, Kunming, China. His current research interests include operation research and mathematical programming and scheduling. E-mail: nk_yu2020@foxmail.com||QIAN Bin was born in 1976. He received his B.S. degree in automation from Donghua University, Shanghai, China, in 1998, M.S. degree in control theory and its applications from Kunming University of Science and Technology, Kunming, China, in 2004, and Ph.D. degree in control science and engineering from Tsinghua University, Beijing, China, in 2009. He is currently a professor at Kunming University of Science and Technology, China. He has published over 90 referred papers. His current research interests include intelligent optimization and scheduling. E-mail: bin.qian@vip.163.com||HU Rong was born in 1974. She received her B.S. degree in thermal energy and dynamic engineering from Southeast University, Nanjing, China, in 1997, and M.S. degree in control science and engineering from Tsinghua University, Beijing, China, in 2004.She is currently an associate professor at Kuming University of Science and Technology, China. She has published over 50 referred papers. Her current research interests include intelligent optimization and machine learning.E-mail: ronghu@vip.163.com||CHEN Yuwang was born in 1982. He received his Ph.D. degree in control theory and engineering from Shanghai Jiao Tong University, Shanghai, China, in 2008. He is currently a senior lecturer in decision sciences in the Alliance Manchester Business School, University of Manchester, Manchester, U.K.. Prior to his current appointment, he was a postdoctoral research associate and then appointed as a lecturer in 2011 at the Decision and Cognitive Sciences (DCS) Research Centre at the University of Manchester, U.K.. He has published over 110 referred papers. His current research interests include decision and risk analysis under uncertainties, modeling and optimization of complex systems, and operational research and data analytics. E-mail: Yu-wang.chen@mbs.ac.uk||WANG Ling was born in 1972. He received his B.S. degree in automation and Ph.D. degree in control science and engineering from Tsinghua University, Beijing, China, in 1995 and 1999, respectively. Since 1999, he has been with Department of Automation, Tsinghua University, where he became a full professor in 2008. He has authored five academic books and more than 230 refereed papers. His current research interests include intelligent optimization theory, algorithms, and applications.E-mail: wangling@tsinghua.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (61963022; 51665025; 61873328)

摘要/Abstract

Abstract:

This paper addresses the open vehicle routing problem with time window (OVRPTW), where each vehicle does not need to return to the depot after completing the delivery task. The optimization objective is to minimize the total distance. This problem exists widely in real-life logistics distribution process. We propose a hybrid column generation algorithm (HCGA) for the OVRPTW, embedding both exact algorithm and metaheuristic. In HCGA, a label setting algorithm and an intelligent algorithm are designed to select columns from small and large subproblems, respectively. Moreover, a branch strategy is devised to generate the final feasible solution for the OVRPTW. The computational results show that the proposed algorithm has faster speed and can obtain the approximate optimal solution of the problem with 100 customers in a reasonable time.

Key words: open vehicle routing problem with time window (OVRPTW), hybrid column generation algorithm (HCGA), mixed integer programming, label setting algorithm

. [J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 997-1009.

Naikang YU, Bin QIAN, Rong HU, Yuwang CHEN, Ling WANG. Solving open vehicle problem with time window by hybrid column generation algorithm[J]. Journal of Systems Engineering and Electronics, 2022, 33(4): 997-1009.

图/表 10

Instance	n	opt	SA			MA			HCGA
Instance	n	opt	ub	Gap/%	Time/s	ub	Gap/%	Time/s	ub	Gap/%	addcolumn	Time/s
C101	25	191.3	194.18	1.51	1.00	198.9	3.97	6.55	191.4	0.05	1351	1.31
	50	362.4	489.08	34.96	1.50	448.9	23.87	14.77	363.24	0.23	3280	8.85
	100	827.3	866.16	4.70	1.11	1104.8	33.54	27.82	828.94	0.20	11188	78.35
C102	25	190.3	192.36	1.08	1.05	256.1	34.58	6.78	190.3	0.00	5516	22.82
	50	361.4	539.43	49.26	1.06	574.8	59.05	14.35	362.17	0.21	14705	24.27
	100	827.3	994.56	20.22	1.11	1317.4	59.24	28.73	828.93	0.20	90644	4138
C105	25	191.3	196.81	2.88	1.06	202.4	5.80	6.53	191.3	0.00	1835	1.47
	50	362.4	472.3	30.33	2.13	435.6	20.20	12.22	363.24	0.23	5291	9.37
	100	827.3	830.67	0.41	3.13	1288.5	55.75	28.83	828.93	0.20	15398	19.59
C106	25	191.3	195.71	2.31	1.06	214.4	12.08	6.4	191.8	0.26	1542	1.32
	50	362.4	497.13	37.18	2.17	450.6	24.34	12.33	363.24	0.23	4184	11.27
	100	827.3	945.36	14.27	2.12	1194.2	44.35	27.96	828.93	0.20	49817	210.7
C201	25	214.7	219.82	2.38	1.05	255.7	19.10	6.42	215.54	0.39	4303	3.64
	50	360.2	598.24	66.09	1.09	413.7	14.85	13.52	361.79	0.44	18633	13.27
	100	589.1	762.6	29.45	2.26	1038.9	76.35	27.87	591.56	0.42	122465	268.01
R101	25	617.1	772.38	25.16	0.10	656.9	6.45	6.86	618.32	0.20	171	0.10
R101	50	1044	1044	0.00	1.10	1344.5	28.78	13.52	1046.70	0.26	839	0.50
R102	25	547.1	764.68	39.77	1.24	590.1	7.86	6.98	547.40	0.05	556	0.45
R102	50	909	972	6.93	2.87	936.72	3.05	15.25	911.44	0.27	2930	3.98
R103	25	454.6	454.6	0.00	1.45	470.8	3.56	7.28	455.69	0.24	1500	1.60
R103	50	772.9	795.02	2.86	2.81	832.5	7.71	13.14	771.9	*	8591	17.82
R104	25	416.9	417.89	0.24	0.49	490.3	17.61	7.57	417.96	0.25	1797	4.69
R104	50	625.4	752.32	20.29	1.04	1091.4	74.51	16.79	?	?	?	?
R105	25	530.5	533.72	0.61	0.54	534.6	0.77	7.02	531.53	0.19	407	0.13
R105	50	899.3	901.57	0.25	1.77	901.07	0.20	13.17	?	?	?	?
RC101	25	461.1	494.01	7.14	1.59	461.1	0.00	6.57	409.24	*	621	0.67
RC101	50	944	944	0.00	2.63	1078.4	14.24	12.79	?	?	?	?
RC103	25	332.8	337.41	1.39	1.43	543.7	63.37	6.97	333.91	0.33	6933	25.52
RC103	50	822.5	822.5	0.00	2.05	1168.9	42.12	13.22	647.36	*	24232	572.67
RC105	25	411.3	419.56	2.01	1.49	417.1	1.41	6.63	412.37	0.26	1611	1.88
RC105	50	855.3	915.12	6.99	2.87	994.97	16.32	12.59	763.42	*	5301	8.3

参考文献 37

1	DANTZIG G B, RAMSER J H The truck dispatching problem. Management Science, 1959, 6 (1): 80- 91. doi: 10.1287/mnsc.6.1.80
2	BRANDAO J A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research, 2004, 157 (3): 552- 564. doi: 10.1016/S0377-2217(03)00238-8
3	FLESZAR K, OSMAN I H, HINDI K S A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 2009, 195 (3): 803- 809. doi: 10.1016/j.ejor.2007.06.064
4	LOZANO L, DUQUE D, MEDAGLIA A L An exact algorithm for the elementary shortest path problem with resource constraints. Transportation Science, 2016, 50 (1): 348- 357. doi: 10.1287/trsc.2014.0582
5	SCHRAGE L Formulation and structure of more complex/realistic routing and scheduling problems. Networks, 2010, 11 (2): 229- 232.
6	SARIKLIS D, POWELL S A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society, 2000, 51 (5): 564- 573. doi: 10.1057/palgrave.jors.2600924
7	SCHOPKA K, KOPFER H An adaptive large neighborhood search for the reverse open vehicle routing problem with time windows. Logistics Management, 2016, 163 (1): 243- 257. doi: 10.1007/978-3-319-20863-3_18
8	GE J H, XIOMG Y, WANG H Z An improved TS for the open vehicle routing problem with soft time windows. Proc. of the IEEE 5th International Symposium on Computational Intelligence & Design, 2013, 382- 385.
9	REPOUSSIS P P, IOANNOU C D T The open vehicle routing problem with time windows. Journal of the Operational Research Society, 2007, 58 (3): 355- 367. doi: 10.1057/palgrave.jors.2602143
10	FORD L R, FULKERSON D R A suggested computation for maximal multi-commodity network flows. Management Science, 1958, 5 (1): 97- 101. doi: 10.1287/mnsc.5.1.97
11	CHEN Z L, POWELL W B A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem. European Journal of Operational Research, 1999, 116 (1): 220- 232. doi: 10.1016/S0377-2217(98)00136-2
12	FEI H, MESKENS N, CHU C A planning and scheduling problem for an operating theatre using an open scheduling strategy. Computers & Industrial Engineering, 2010, 58 (2): 221- 230.
13	VANCE P H, BARNHART C, JOHNSON E L, et al Solving binary cutting stock problems by column generation and branch-and-bound. Computational Optimization and Applications, 1994, 3 (2): 111- 130. doi: 10.1007/BF01300970
14	CACCHIANI V, HEMMELMAYR V C, TRICOIRE F A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Applied Mathematics, 2014, 163, 53- 64. doi: 10.1016/j.dam.2012.08.032
15	QURESHI A G, TANIGUCHI E, YAMADA T An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research Part E: Logistics & Transportation Review, 2009, 45 (6): 960- 977.
16	YUAN Y, CATTARUZZA D, OGIER M, et al A column generation based heuristic for the generalized vehicle routing problem with time windows. Transportation Research Part E: Logistics and Transportation Review, 2021, 152 (8): 102391. doi: 10.1016/j.tre.2021.102391
17	BEHNKE M, KIRSCHSTEIN T, BIERWIRTH C A column generation approach for an emission-oriented vehicle routing problem on a multigraph. European Journal of Operational Research, 2021, 288 (3): 794- 809. doi: 10.1016/j.ejor.2020.06.035
18	BOLAND N, DETHRIDGE J, DUMITRESCU I Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 2006, 34 (1): 58- 68. doi: 10.1016/j.orl.2004.11.011
19	BERTSEKAS D P A simple and fast label correcting algorithm for shortest paths. Networks, 2010, 23 (8): 703- 709.
20	OZBAYGIN G, KARASAN O E, SAVELSBERGH M, et al A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations. Transportation Research Part B: Methodological, 2017, 100 (6): 115- 137. doi: 10.1016/j.trb.2017.02.003
21	LI C S, GONG L J, LUO Z X, et al A branch-and-price-and-cut algorithm for a pickup and delivery problem in retailing. Omega, 2019, 89 (12): 71- 91. doi: 10.1016/j.omega.2018.09.014
22	TIMO G, STEFAN I, ANN-KATHRIN R, et al Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems. European Journal of Operational Research, 2018, 266 (2): 521- 530. doi: 10.1016/j.ejor.2017.09.035
23	RIGHINI G, SALANI M Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, 2006, 3 (3): 255- 273. doi: 10.1016/j.disopt.2006.05.007
24	RIGHINI G, SALANI M New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks, 2010, 51 (3): 155- 170.
25	KE L J, GUO H M, ZHANG Q F A cooperative approach between metaheuristic and branch-and-price for the team orienteering problem with time windows. Proc. of the IEEE Congress on Evolutionary Computation, 2014, 1878- 1882.
26	ROMAN V, ANTONIN N, PREMYSL S, et al Accelerating the branch-and-price algorithm using machine learning. European Journal of Operational Research, 2018, 271 (3): 1055- 1069. doi: 10.1016/j.ejor.2018.05.046
27	SALARI M, TOTH P, TRAMONTANI A An ILP improvement procedure for the open vehicle routing problem. Computers & Operations Research, 2010, 37 (12): 2106- 2120.
28	SHEN Y D, PENG L W, LI J P An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem. Journal of Systems Engineering and Electronics, 2021, 32 (2): 365- 379.
29	MAJID Y, AZAM D, FARZAD D, et al. A modified column generation to solve the heterogeneous fixed fleet open vehicle routing problem. Journal of Engineering, 2016. DOI: 10.1155/2016/5692792.
30	FAIZ T I, VOGIATZIS C, NOOR-E-ALAM M A column generation algorithm for vehicle scheduling and routing problems. Computers & Industrial Engineering, 2019, 130, 222- 236.
31	CUI H J, LUO X C, WANG Y Scheduling of steelmaking-continuous casting process using deflected surrogate Lagrangian relaxation approach and DC algorithm. Computers & Industrial Engineering, 2020, 140 (2): 106271.
32	BINATO S, PEREIRA M V F, GRANVILLE S A new benders decomposition approach to solve power transmission network design problems. IEEE Trans. on Power Systems, 2001, 16 (2): 235- 240. doi: 10.1109/59.918292
33	BALINSKI M L, QUANDT R E On an integer program for a delivery problem. Operations Research, 1964, 12 (2): 187- 376. doi: 10.1287/opre.12.2.187
34	DROR M Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research, 1994, 42 (5): 977- 978. doi: 10.1287/opre.42.5.977
35	KENNEDY J, EBERHART R Particle swarm optimization. Proc. of the IEEE International Conference on Neural Networks, 1995, 1942- 1948.
36	TAVAKKOLI-MOGHADDAM R, GAZANFARI M, ALINAGHIAN M, et al A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing. Journal of Manufacturing Systems, 2011, 30 (2): 83- 92. doi: 10.1016/j.jmsy.2011.04.005
37	SABAR N R, BHASKAR A, CHUNG E, et al An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints. Swarm and Evolutionary Computation, 2020, 58, 100730. doi: 10.1016/j.swevo.2020.100730

Symbol	Description of symbol
$ x_{ij}^k $	Decision variable: if the vehicle $k$ visits customer $i$ after visiting customer point $j$ , then the variable value is 1; otherwise, the value is 0
$y_i^k$	Decision variable: if customer $i$ is visited by the vehicle $k$ , the variable value is 1; otherwise, the value is 0
${t_i}$	The time of vehicle arrives at customer $i$
${w_i}$	The waiting time of vehicle to arrive at customer $i$
$i,j$	Customer node $i,j \in V$
$k$	Vehicle node $k = 1,2, \cdots ,K$
$K$	Total number of vehicles
$n$	Total number of customers
$Q$	Maximum vehicle capacity
$ {c_{ij}} $	Distance from customer $i$ to customer $j$
$ {t_{ij}} $	Time from customer $i$ to customer $j$
${d_i}$	Demand of customer $i$
$[{e_i},{l_i}]$	Time window of customer $i$
${e_i}$	The earliest time that customer $i$ can be visited
${l_i}$	The latest time that customer $i$ can be visited
${s_i}$	Service time of customer $i$

Instance	V_num	V_cap	C_demand	C_ServiceTime/min	C_TimeWindow/min
C501	15	300	[10?50]	45	[50?70]
C502	15	300	[10?110]	30,45	[20?80]
C503	15	300	[30?110]	45	[20?100]

Instance	Scale	$n$	${\rm{MIPsolved}}$	${\rm{Time/s} }$	$ {\rm{CGsolved}} $	${\rm{Time/s } }$	${\rm{Gap} }/\%$
C501		5	3.24	0.46	3.24	0.012	0.00
	Small	10	5.72	2.95	5.72	0.026	0.00
		15	14.33	12.58	14.73	0.11	2.79
		20	21.20	51.87	21.20	0.377	0.00
		25	36.46	68.03	36.46	1.07	0.00
	Medium	30	48.17	63.25	49.5	2.16	2.76
		35	70.12	59.17	70.655	3.47	0.76
		40	81.59	125.49	81.657	5.78	0.08
	Large	45	103.98	242.82	104.77	13.21	0.76
		50	119.24	644.77	119.24	13.8	0.00
C502		5	12.8	0.64	12.8	0.013	0.00
	Small	10	40.19	2.15	40.19	0.019	0.00
		15	60.52	14.56	60.52	0.027	0.00
		20	62.05	30.62	62.93	0.128	1.42
		25	69.11	103.79	70.28	0.216	1.69
	Medium	30	81.02	89.21	81.91	0.562	1.10
		35	85.34	144.93	86.22	1.08	1.03
		40	89.99	201.01	91.67	2.17	1.87
	Large	45	96.8	396.54	101.86	2.48	5.23
		50	111.07	365.71	116.41	3.61	4.81
		5	10.31	0.45	10.68	0.009	3.59
C503	Small	10	18.52	1.7	19.37	0.0169	4.59
		15	32.35	8.07	33.3	0.0319	2.94
		20	58.86	49.42	61.08	0.055	3.77
		25	106.66	88.58	107.63	0.147	0.91
	Medium	30	142.37	56.83	146.84	0.339	3.14
		35	179.33	103.35	189.02	0.97	5.40
		40	209.95	179.48	220.9	1.47	5.22
	Large	45	227.32	282.85	241.25	1.61	6.13
		50	234.75	1228.245	251.38	2.69	7.08

Solving open vehicle problem with time window by hybrid column generation algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 37

相关文章 0

编辑推荐

Metrics

本文评价