Article Contents
Article Contents

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

• * Corresponding author: Lixin Wei
• 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.

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

 Citation:

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

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

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

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

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

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

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

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

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

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
•  [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.

Figures(2)

Tables(8)