An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints

Bin Feng; Lixin Wei; Ziyu Hu

doi:10.3934/jimo.2021197

Article Contents

2023, Volume 19, Issue 1: 573-593. Doi: 10.3934/jimo.2021197

This issue Previous Article The inventory replenishment policy in an uncertain production-inventory-routing system Next Article Effects of the carbon credits buy-back policy on manufacturing/remanufacturing decisions of the capital-constrained manufacturer

An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints

1.
Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao 066004, China
2.
Key Lab of Industrial Computer Control Engineering of Hebei Province, Yanshan University, Qinhuangdao 066004, China

^* Corresponding author: Lixin Wei
^* Corresponding author: Lixin Wei

Received: February 28, 2021

Revised: June 30, 2021

Early access: November 2021

Published: January 2023

Abstract Full Text(HTML) Figure(2) / Table(8) Related Papers Cited by

Abstract

The Vehicle Routing Problem with Multiple Time Windows (VRPMTW) is a generalization of problems in real life logistics distribution, which has a wide range of applications and research values. Several neighborhood search based methods have been used to solve this kind of problem, but it still has drawbacks of generating numbers of infeasible solutions and falling into local optimum easily. In order to solve the problem of arbitrary selection for neighborhoods, a series of neighborhoods are designed and an adaptive strategy is used to select the neighborhood, which constitute the Adaptive Large Neighborhood Search(ALNS) algorithm framework. For escaping from the local optimum effectively in the search process, a local search based on destroy and repair operators is applied to shake the solution by adjusting the number of customers. The proposed method allows infeasible solutions to participate in the iterative process to expand the search space. At the same time, an archive is set to save the high-quality feasible solutions during the search process, and the infeasible solutions are periodically replaced. Computational experimental results on VRPMTW benchmark instances show that the proposed algorithm is effective and has obtained better solutions.

Keywords:

Mathematics Subject Classification: Primary: 90B06, 90B40; Secondary: 90C11.

Citation:

FullText(HTML)

Figure 1. Removal List(RL), Unserved Customers List(UCL) and current solution

Download: Full-size image PowerPoint slide

Figure 2. Number of times each destroy and repair method was used to produce a new best solution

Download: Full-size image PowerPoint slide

Table 1. Definition of the parameters and variables

Name	Description
$ x_{ij}^{k} $	binary variable, equal to 1 if and only if arc$ (i,j) $ is traversed by vehicle $ k $
$ y_{ij}^{k} $	real variable, equals to the flow carried on arc $ (i,j) $
$ r^{k} $	binary variable, equal to 1 if and only if vehicle $ k $ is used
$ v_{i}^{p} $	binary variable, equal to 1 if and only if customer $ i $ is served within its time window $ p $
$ z_{i}^{k} $	binary variable, equals to 1 if and only if customer $ i $ is assigned to vehicle $ k $
$ w_{i}^{k} $	real variable, waiting time of vehicle $ k $ at customer $ i $
$ d_{k} $	route duration of vehicle $ k $
$ a_{i}^{k} $	arrival time of vehicle $ k $ at customer $ i $
$ b_{i}^{k} $	departure time of vehicle $ k $ from customer $ i $
$ t_{ij} $	travel time associated with the arc $ (i,j) $
$ s_{i} $	service time at customer $ i $
$ q_{i} $	demand of customer $ i $
$ l_{i}^{p} $	lower bound of time window $ p $ at customer $ i $
$ u_{i}^{p} $	upper bound of time window $ p $ at customer $ i $
$ Q_{k} $	capacity of vehicle $ k $
$ D_{k} $	maximum duration of the route of vehicle $ k $
$ F^{k} $	fixed cost in time units of using vehicle $ k $
$ M $	an arbitrary large constant

| Show Table

DownLoad: CSV

Table 2. Parameters of ALNS

Parameter	nsegs	nters	$ \sigma 4 $	$ \sigma 3 $	$ \sigma 2 $	$ \sigma 1 $	$ \zeta $	$ T_{0} $	$ c $	$ \beta 1 $	$ \beta 2 $
Value	1000	100	10	5	3	1	0.7	0.4	0.9	100	100

| Show Table

DownLoad: CSV

Table 3. Parameters of RemovalList in LocalSearch procedure

Parameters	Average in 3 groups
($ \psi^{LS} $, $ \psi^{LS}_{max} $, $ noi_{max} $)	CM	RCM	RM
(12, 20,200)	13574.6	4201.8	4109.6
(12, 20,500)	13341.7	4197.2	4042.6
(12, 20,800)	12947.1	4141.0	4023.6
(15, 22,200)	12927.3	4094.3	3815.3
(15, 22,500)	12724.2	4055.7	3737.7
(15, 22,800)	12729.0	4056.1	3736.4
(18, 25,200)	12845.1	4092.3	3746.5
(18, 25,500)	12813.0	4084.5	3741.0
(18, 25,800)	12748.9	4088.3	3739.2

| Show Table

DownLoad: CSV

Table 4. ALNS results on VRPMTW instances(Group CM)

Instance	m	HVNTS	HGVNS	EAVNS	ALNS	gap1	gap2	gap3
CM101	10	12320	12319.1	12345.4	12151.0	1.37	1.36	1.57
CM102	11	12492.1	12410.7	12482.3	12467.8	0.19	-0.46	0.12
CM103	11	12641.2	12632.4	12592.2	12450.5	1.51	1.44	1.13
CM104	13	13087.8	13098.0	12927.8	12912.2	1.34	1.42	0.12
CM105	10	12083.4	12027.0	12066.3	12083.4	0.00	-0.47	-0.14
CM106	10	12073.9	12059.0	12066.4	11995.4	0.65	0.53	0.59
CM107	10	12324.2	12318.0	12108.4	12092.2	1.88	1.83	0.13
CM108	10	11990.4	11986.0	11985.9	11970.3	0.17	0.13	0.13
Average	10.6	12376.6	12356.3	12321.8	12265.4	0.89	0.72	0.46
CM201	5	13520.1	13498.8	13468.4	13418.3	0.75	0.60	0.37
CM202	6	14027.3	14025.1	14020.2	14010.4	0.12	0.10	0.07
CM203	5	13497.2	13465.8	13486.5	13464.6	0.24	0.01	0.16
CM204	5	13359.8	13344.0	13356.9	13344.0	0.12	0.00	0.10
CM205	4	12884.1	12827.8	12896.8	12829.5	0.42	-0.01	0.52
CM206	4	12767.7	12713.2	12733.4	12704.6	0.49	0.07	0.23
CM207	4	13009.7	12963.7	12963.7	12933.4	0.59	0.23	0.23
CM208	4	12788.1	12749.7	12756.8	12746.7	0.32	0.02	0.08
Average	4.6	13231.8	13198.5	13210.3	13181.4	0.38	0.13	0.22

| Show Table

DownLoad: CSV

Table 5. ALNS results on VRPMTW instances(Group RCM)

Instance	m	HVNTS	HGVNS	EAVNS	ALNS	gap1	gap2	gap3
RCM101	10	4098.9	4081.2	4080.6	4076.1	0.55	0.12	0.11
RCM102	10	4222.6	4188.3	4184.3	4122.7	2.73	1.57	1.47
RCM103	10	4174.3	4150.4	4148.3	4140.5	0.81	0.24	0.19
RCM104	10	4156.3	4144.0	4141.2	4128.3	0.67	0.38	0.31
RCM105	10	4216.7	4207.0	4208.2	4190.4	0.62	0.40	0.42
RCM106	10	4219.9	4187.7	4191.8	4173.1	1.11	0.35	0.45
RCM107	11	4542.4	4521.5	4516.5	4511.4	0.68	0.22	0.11
RCM108	11	4614.5	4565.2	4566.2	4532.5	1.78	0.72	0.74
Average	10.3	4280.7	4254.9	4254.6	4234.4	1.07	0.50	0.48
RCM201	2	3783.6	3783.2	3800.1	3726.5	1.51	1.50	1.94
RCM202	2	3847.1	3779.4	3822.9	3756.7	2.35	0.60	1.73
RCM203	2	3721.9	3722.0	3771.7	3719.2	0.07	0.07	1.39
RCM204	2	3726.5	3708.5	3716.0	3701.6	0.67	0.19	0.39
RCM205	2	3754.5	3754.5	3756.0	3730.3	0.64	0.64	0.68
RCM206	2	3812.7	3803.3	3725.0	3725.9	2.28	2.04	-0.02
RCM207	3	4764.2	4761.5	4757.1	4771.2	-0.15	-0.20	-0.30
RCM208	2	3791.4	3742.7	3735.1	3735.9	1.46	0.18	-0.02
Average	2.1	3900.2	3881.9	3885.5	3858.4	1.10	0.63	0.72

| Show Table

DownLoad: CSV

Table 6. ALNS results on VRPMTW instances(Group RM)

Instance	m	HVNTS	HGVNS	EAVNS	ALNS	gap1	gap2	gap3
RM101	10	4041.9	4027.1	4026.1	4009.4	0.81	0.44	0.42
RM102	9	3765.1	3751.2	3774.8	3730.0	0.93	0.56	1.19
RM103	9	3708.5	3703.0	3700.6	3704.0	0.12	-0.33	-0.09
RM104	9	3718.0	3701.2	3707.1	3697.6	0.55	0.10	0.26
RM105	9	3688.8	3687.2	3690.5	3689.7	-0.02	-0.07	0.02
RM106	9	3692.9	3708.4	3714.8	3713.5	-0.56	-0.14	0.03
RM107	9	3701.4	3692.8	3700.4	3686.0	0.42	0.18	0.39
RM108	9	3792.1	3722.6	3738.1	3727.6	1.70	-0.14	0.28
Average	9.1	3755.7	3749.2	3756.6	3744.7	0.49	0.11	0.31
RM201	2	4808.2	4805.4	3888.9	3804.4	20.88	20.83	2.17
RM202	2	3739.0	3706.8	3721.9	3706.8	0.86	0.00	0.41
RM203	2	3710.3	3696.9	3693.2	3691.7	0.50	0.14	0.04
RM204	2	3691.9	3674.5	3671.7	3674.5	0.47	0.00	-0.08
RM205	2	3689.9	3668.1	3668.4	3671.0	0.51	-0.08	-0.07
RM206	2	3703.4	3684.9	3672.6	3673.5	0.81	0.31	-0.02
RM207	2	3701.7	3664.3	3662.4	3664.3	1.01	0.00	-0.05
RM208	2	3682.8	3664.3	3663.6	3664.3	0.50	0.00	-0.02
Average	2	3840.9	3820.7	3705.3	3693.8	3.19	2.65	0.30

| Show Table

DownLoad: CSV

Table 7. Evaluation of contribution of each operator

Operator	Average degradation(%)	Maximum degradation(%)
Worst Removal	0.26	0.86
Basic Related Removal	0.20	0.91
Improved Related Removal	0.25	0.99
Route Removal	0.22	1.15
Random Removal	0.17	0.84
Greedy Insertion	0.27	1.82
Regret Insertion	0.35	2.31
Random Insertion	0.17	0.73

| Show Table

DownLoad: CSV

Table 8. Execution counts of the operators leading to the discovery of a new solution

Operator	Best solution	Current solution	Simulated annealing
Worst Removal	922	73627	1007
Basic Related Removal	2341	88112	756
Improved Related Removal	4267	93581	543
Route Removal	45	45990	4352
Random Removal	64	41686	6235
Greedy Insertion	2511	38656	457
Regret Insertion	7539	95684	365
Random Insertion	582	9083	2120

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	S. Belhaiza, P. Hansen and G. Laporte, A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows, Comput. Oper. Res., 52 (2014), 269-281. doi: 10.1016/j.cor.2013.08.010.
[2]	S. Belhaiza and R. M'Hallah, A Pareto non-dominated solution approach for the vehicle routing problem with multiple time windows, in 2016 IEEE Congress on Evolutionary Computation (CEC), (2016), 3515–3524. doi: 10.1109/CEC.2016.7744235.
[3]	S. Belhaiza, R. M'Hallah and G. B. Brahim, A new hybrid genetic variable neighborhood search heuristic for the vehicle routing problem with multiple time windows, in 2017 IEEE Congress on Evolutionary Computation (CEC), (2017), 1319–1326. doi: 10.1109/CEC.2017.7969457.
[4]	H. Ben Ticha, N. Absi, D. Feillet and A. Quilliot, Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows, Comput. Oper. Res., 104 (2019), 113-126. doi: 10.1016/j.cor.2018.11.001.
[5]	K. Braekers, K. Ramaekers and I. V. Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & Industrial Engineering, 99 (2016), 300-313. doi: 10.1016/j.cie.2015.12.007.
[6]	S. Chen, R. Chen, G.-G. Wang, J. Gao and A. K. Sangaiah, An adaptive large neighborhood search heuristic for dynamic vehicle routing problems, Computers & Electrical Engineering, 67 (2018), 596-607. doi: 10.1016/j.compeleceng.2018.02.049.
[7]	H. Chentli, R. Ouafi and W. Ramdane Cherif-Khettaf, A selective adaptive large neighborhood search heuristic for the profitable tour problem with simultaneous pickup and delivery services, RAIRO Oper. Res., 52 (2018), 1295-1328. doi: 10.1051/ro/2018024.
[8]	D. Favaretto, E. Moretti and P. Pellegrini, Ant colony system for a VRP with multiple time windows and multiple visits, J. Interdiscip. Math, 10 (2007), 263-284. doi: 10.1080/09720502.2007.10700491.
[9]	H. S. Ferreira, E. T. Bogue, T. F. Noronha, S. Belhaiza and C. Prins, Variable neighborhood search for vehicle routing problem with multiple time windows, Electronic Notes in Discrete Mathematics, 66 (2018), 207-214. doi: 10.1016/j.endm.2018.03.027.
[10]	E. Glize, N. Jozefowiez and S. U. Ngueveu, An exact column generation-based algorithm for bi-objective vehicle routing problems, Combinatorial Optimization, 208–218, Lecture Notes in Comput. Sci., 10856, Springer, Cham, 2018. doi: 10.1007/978-3-319-96151-4_18.
[11]	F. Hammami, M. Rekik and L. C. Coelho, A hybrid adaptive large neighborhood search heuristic for the team orienteering problem, Comput. Oper. Res., 123 (2020), 105034, 18 pp. doi: 10.1016/j.cor.2020.105034.
[12]	M. Hoogeboom, W. Dullaert, D. Lai and D. Vigo, Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows, Transportation Science, 54 (2020), 400-416. doi: 10.1287/trsc.2019.0912.
[13]	Z. Hu, Z. Wei and H. Sun et al, Optimization of metal rolling control using soft computing approaches: A review, Arch. Computat. Methods Eng., 28 (2021), 405-421. doi: 10.1007/s11831-019-09380-6.
[14]	M. N. Kritikos and P. Z. Lappas, Computational Intelligence and Combinatorial Optimization Problems in Transportation Science, In: Tsihrintzis G., Virvou M. (eds) Advances in Core Computer Science-Based Technologies. Learning and Analytics in Intelligent Systems, vol 14. Springer, Cham. doi: 10.1007/978-3-030-41196-1_15.
[15]	Y. Li, H. Chen and C. Prins, Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European J. Oper. Res., 252 (2016), 27-38. doi: 10.1016/j.ejor.2015.12.032.
[16]	R. Liu, Y. Tao and X. Xie, An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits, Comput. Oper. Res., 101 (2019), 250-262. doi: 10.1016/j.cor.2018.08.002.
[17]	T. Liu, Z. Luo, H. Qin and A. Lim, A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem with grouping constraints, European J. Oper. Res., 266 (2018), 487-497. doi: 10.1016/j.ejor.2017.10.017.
[18]	S. Mirzaei and S. Whlk, A branch-and-price algorithm for two multi-compartment vehicle routing problems, Euro Journal on Transportation & Logs, 8 (2019), 1-33.
[19]	D. Pisinger and S. Ropke, A general heuristic for vehicle routing problems, Comput. Oper. Res., 34 (2007), 2403-2435. doi: 10.1016/j.cor.2005.09.012.
[20]	P. H. Richard, S. Allyson, J. R. Kees and C. C. Leandro, The vehicle routing problem with simultaneous pickup and delivery and handling costs, Computers & Operations Research, 115 (2020), 104858.
[21]	S. Ropke and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472. doi: 10.1287/trsc.1050.0135.
[22]	V. Schmid, K. F. Doerner and G. Laporte, Rich routing problems arising in supply chain management, European J. Oper. Res., 224 (2013), 435-448. doi: 10.1016/j.ejor.2012.08.014.
[23]	P. Shaw, Using constraint programming and local search methods to solve vehicle routing problems, Principles and Practice of Constraint Programming — CP98. CP, 286 (1998), 417-431. doi: 10.1007/3-540-49481-2_30.
[24]	T. Vidal, G. Laporte and P. Matl, A concise guide to existing and emerging vehicle routing problem variants, European J. Oper. Res., 286 (2020), 401-416. doi: 10.1016/j.ejor.2019.10.010.
[25]	D. Vigo and P. Toth, Vehicle Routing: Problems, Methods, and Applications, 2$^{nd}$ edition, SIAM, 2014. doi: 10.1137/1.9781611973594.
[26]	X. Yan, B. Xiao and Z. Zhao, Multi-objective vehicle routing problem with simultaneous pick-up and delivery considering customer satisfaction, in 2019 IEEE International Conference on Smart Manufacturing, Industrial & Logistics Engineering (SMILE), Volume (2019), 93–97. doi: 10.1109/SMILE45626.2019.8965319.