
-
Previous Article
A product service supply chain network equilibrium considering risk management in the context of COVID-19 pandemic
- JIMO Home
- This Issue
-
Next Article
Distributionally robust chance constrained svm model with $\ell_2$-Wasserstein distance
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
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 |
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.
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. |
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. |
[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. |


Name | Description |
binary variable, equal to 1 if and only if arc |
|
real variable, equals to the flow carried on arc |
|
binary variable, equal to 1 if and only if vehicle |
|
binary variable, equal to 1 if and only if customer |
|
binary variable, equals to 1 if and only if customer |
|
real variable, waiting time of vehicle |
|
route duration of vehicle |
|
arrival time of vehicle |
|
departure time of vehicle |
|
travel time associated with the arc |
|
service time at customer |
|
demand of customer |
|
lower bound of time window |
|
upper bound of time window |
|
capacity of vehicle |
|
maximum duration of the route of vehicle |
|
fixed cost in time units of using vehicle |
|
an arbitrary large constant |
Name | Description |
binary variable, equal to 1 if and only if arc |
|
real variable, equals to the flow carried on arc |
|
binary variable, equal to 1 if and only if vehicle |
|
binary variable, equal to 1 if and only if customer |
|
binary variable, equals to 1 if and only if customer |
|
real variable, waiting time of vehicle |
|
route duration of vehicle |
|
arrival time of vehicle |
|
departure time of vehicle |
|
travel time associated with the arc |
|
service time at customer |
|
demand of customer |
|
lower bound of time window |
|
upper bound of time window |
|
capacity of vehicle |
|
maximum duration of the route of vehicle |
|
fixed cost in time units of using vehicle |
|
an arbitrary large constant |
Parameter | nsegs | nters | |||||||||
Value | 1000 | 100 | 10 | 5 | 3 | 1 | 0.7 | 0.4 | 0.9 | 100 | 100 |
Parameter | nsegs | nters | |||||||||
Value | 1000 | 100 | 10 | 5 | 3 | 1 | 0.7 | 0.4 | 0.9 | 100 | 100 |
Parameters | Average in 3 groups | ||
( |
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 |
Parameters | Average in 3 groups | ||
( |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2022, 18 (4) : 2847-2872. doi: 10.3934/jimo.2021094 |
[12] |
Erik Carlsson, John Gunnar Carlsson, Shannon Sweitzer. Applying topological data analysis to local search problems. Foundations of Data Science, 2022 doi: 10.3934/fods.2022006 |
[13] |
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 and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056 |
[14] |
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 and Management Optimization, 2020, 16 (4) : 1801-1834. doi: 10.3934/jimo.2019030 |
[15] |
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 |
[16] |
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 and Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058 |
[17] |
Ming-Jong Yao, Yu-Chun Wang. Theoretical analysis and a search procedure for the joint replenishment problem with deteriorating products. Journal of Industrial and Management Optimization, 2005, 1 (3) : 359-375. doi: 10.3934/jimo.2005.1.359 |
[18] |
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 and Management Optimization, 2021, 17 (6) : 3223-3246. doi: 10.3934/jimo.2020115 |
[19] |
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 and Management Optimization, 2009, 5 (4) : 749-765. doi: 10.3934/jimo.2009.5.749 |
[20] |
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 and Management Optimization, 2021, 17 (3) : 1069-1100. doi: 10.3934/jimo.2020012 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]