American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jimo.2021197
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Bin Feng 1,2, , Lixin Wei 1,2,, and  Ziyu Hu 1,2,

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

Received  March 2021 Revised  July 2021 Early access November 2021

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: Vehicle routing problem, multiple time windows, adaptive large neighborhood search, local search.
Mathematics Subject Classification: Primary: 90B06, 90B40; Secondary: 90C11.
Citation: Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021197
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

D. Vigo and P. Toth, Vehicle Routing: Problems, Methods, and Applications, 2$^{nd}$ edition, SIAM, 2014. doi: 10.1137/1.9781611973594.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

D. Vigo and P. Toth, Vehicle Routing: Problems, Methods, and Applications, 2$^{nd}$ edition, SIAM, 2014. doi: 10.1137/1.9781611973594.  Google Scholar

[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.  Google Scholar

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as 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
Table Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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 Options

Download as excel

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
Table Options

Download as excel

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]

Shengyang Jia, Lei Deng, Quanwu Zhao, Yunkai Chen. An adaptive large neighborhood search heuristic for multi-commodity two-echelon vehicle routing problem with satellite synchronization. Journal of Industrial & Management Optimization, 2022  doi: 10.3934/jimo.2021225
[2]

Nurhadi Siswanto, Stefanus Eko Wiratno, Ahmad Rusdiansyah, Ruhul Sarker. Maritime inventory routing problem with multiple time windows. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1185-1211. doi: 10.3934/jimo.2018091
[3]

Yaw Chang, Lin Chen. Solve the vehicle routing problem with time windows via a genetic algorithm. Conference Publications, 2007, 2007 (Special) : 240-249. doi: 10.3934/proc.2007.2007.240
[4]

Zheng Chang, Haoxun Chen, Farouk Yalaoui, Bo Dai. Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1771-1793. doi: 10.3934/jimo.2020045
[5]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial & Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469
[6]

Erfan Babaee Tirkolaee, Alireza Goli, Mani Bakhsi, Iraj Mahdavi. A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 417-433. doi: 10.3934/naco.2017026
[7]

Ming-Yong Lai, Chang-Shi Liu, Xiao-Jiao Tong. A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows. Journal of Industrial & Management Optimization, 2010, 6 (2) : 435-451. doi: 10.3934/jimo.2010.6.435
[8]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071
[9]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029
[10]

Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041
[11]

Min Zhang, Guowen Xiong, Shanshan Bao, Chao Meng. A time-division distribution strategy for the two-echelon vehicle routing problem with demand blowout. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021094
[12]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056
[13]

Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030
[14]

Poonam Savsani, Mohamed A. Tawhid. Discrete heat transfer search for solving travelling salesman problem. Mathematical Foundations of Computing, 2018, 1 (3) : 265-280. doi: 10.3934/mfc.2018012
[15]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[16]

Ming-Jong Yao, Yu-Chun Wang. Theoretical analysis and a search procedure for the joint replenishment problem with deteriorating products. Journal of Industrial & Management Optimization, 2005, 1 (3) : 359-375. doi: 10.3934/jimo.2005.1.359
[17]

Dieudonné Nijimbere, Songzheng Zhao, Xunhao Gu, Moses Olabhele Esangbedo, Nyiribakwe Dominique. Tabu search guided by reinforcement learning for the max-mean dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115
[18]

Tao Zhang, W. Art Chaovalitwongse, Yue-Jie Zhang, P. M. Pardalos. The hot-rolling batch scheduling method based on the prize collecting vehicle routing problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749
[19]

Bariş Keçeci, Fulya Altıparmak, İmdat Kara. A mathematical formulation and heuristic approach for the heterogeneous fixed fleet vehicle routing problem with simultaneous pickup and delivery. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012
[20]

Namsu Ahn, Soochan Kim. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021037

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (126)
  • HTML views (64)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy