
-
Previous Article
Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems
- JIMO Home
- This Issue
-
Next Article
The viability of switched nonlinear systems with piecewise smooth Lyapunov functions
Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery
1. | Research Institute of Highway Ministry of Transport, Beijing 100070, China |
2. | University of Technology of Troyes, TROYES 10004, France |
3. | Hunan University of Technology and Business, ChangSha 410205, Hunan, China |
Freight bus is a new public transportation means for city logistics, and each freight bus can deliver and pick up goods at each customer/supplier location it passes. In this paper, we study the route planning problem of freight buses in an urban distribution system. Since each freight bus makes a tour visiting a set of pickup/delivery locations once at every given time interval in each day following a fixed route, the route planning problem can be considered a new variant of periodic vehicle routing problem with pickup and delivery. In order to solve the problem, a Mixed-Integer Linear Programming (MILP) model is formulated and an Adaptive Large Neighborhood Search (ALNS) algorithm is developed. The development of our algorithm takes into consideration specific characteristics of this problem, such as fixed route for each freight bus, possibly serving a demand in a later period but with a late service penalty, etc. The relevance of the mathematical model and the effectiveness of the proposed ALNS algorithm are proved by numerical experiments.
References:
[1] |
D. Aksen, O. Kaya, F. S. Salman and Ö. Tuncel,
An adaptive large neighbor- hood search algorithm for a selective and periodic inventory routing problem, European Journal of Operational Research, 239 (2014), 413-426.
doi: 10.1016/j.ejor.2014.05.043. |
[2] |
E. J. Beltrami and L. D. Bodin,
Networks and vehicle routing for municipal waste collection, Networks, 4 (1974), 65-94.
doi: 10.1002/net.3230040106. |
[3] |
R. Bent and P. V. Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893. Google Scholar |
[4] |
N. Christofides and J. E. Beasley, The period routing problem, Networks, 14 (1984), 237-256. Google Scholar |
[5] |
A. M. Campbell and H. W. Jill,
Forty years of periodic vehicle routing, Networks, 63 (2014), 2-15.
doi: 10.1002/net.21527. |
[6] |
I.-M. Chao, B. L. Golden and E. Wasil,
An improved heuristic for the period vehicle-routing problem, Networks, 26 (1995), 25-44.
doi: 10.1002/net.3230260104. |
[7] |
Z. Chang and H. Chen, Freight buses in three-tiered distribution systems for city logistics: Modeling and evaluation, 7th IESM Conference, (2017). Google Scholar |
[8] |
J. F. Cordeau, M. Gendreau and G. Laporte, A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53 (2002), 512-522. Google Scholar |
[9] |
G. Clarke and J. W. Wright,
Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581.
doi: 10.1007/978-3-642-27922-5_18. |
[10] |
B. Dai and H. X. Chen,
Proportional egalitarian core solution for profit allocation games with an application to collaborative transportation planning, European Journal of Industrial Engineering, 9 (2015), 53-76.
doi: 10.1504/EJIE.2015.067456. |
[11] |
L. M. A. Drummond, L. S. Ochi and D. S. Vianna,
An asynchronous parallel metaheuristic for the period vehicle routing problem, Future Generation Computer System, 17 (2001), 379-386.
doi: 10.1016/S0167-739X(99)00118-1. |
[12] |
E. Demir, T. Bektas and G. Laporte,
An adaptive large neighborhood search heuristic for the Pollution-Routing Problem, European Journal of Operational Research, 223 (2012), 346-359.
doi: 10.1016/j.ejor.2012.06.044. |
[13] |
B. Dai, H. X. Chen and G. K. Yang,
Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requests, Operational Research, 14 (2014), 361-386.
doi: 10.1007/s12351-014-0141-1. |
[14] |
P. Francis, K. Smilowitz and M. Tzur,
The period vehicle routing problem with service choice, Transportation Science, 40 (2006), 439-454.
doi: 10.1287/trsc.1050.0140. |
[15] |
L. E. Gill and R. P. Allerheiligen,
Co-operation in channels of distribution: Physical distribution leads the way, International Journal of Physical Distribution & Logistics Management, 26 (1996), 49-63.
doi: 10.1108/eb014521. |
[16] |
M. Gaudioso and G. Paletta,
A heuristic for the periodic vehicle routing problem, Transport Science, 26 (1992), 86-92.
doi: 10.1287/trsc.26.2.86. |
[17] |
D. Goeke and M. Schneider,
Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, 245 (2015), 81-99.
doi: 10.1016/j.ejor.2015.01.049. |
[18] |
Y. Hao and Y. Su, The research on joint distribution mode of the chain retail enterprises, International Conference on Mechatronics, Electronic, Industrial and Control Engineering, MEIC, (2014), 1694–1697. Google Scholar |
[19] |
M. Y. Lai, H. M. Yang, S. P. Yang, J. H. Zhao and Y. Xu,
Cyber-physical logistics system-based vehicle routing optimization, Journal of Industrial and Management Optimization, 10 (2014), 701-715.
doi: 10.3934/jimo.2014.10.701. |
[20] |
L. L. Lv, Z. Zhang, L. Zhang and W. S. Wang,
An iterative algorithm for periodic Sylvester matrix equations, Journal of Industrial and Management Optimization, 14 (2018), 413-425.
doi: 10.3934/jimo.2017053. |
[21] |
N. Labadie, R. Mansini, J. Melechovský and R. Wolfler-Calvo,
The team orienteering problem with time windows: An LP-based granular variable neighborhood search, European Journal of Operational Research, 220 (2012), 15-27.
doi: 10.1016/j.ejor.2012.01.030. |
[22] |
Y. Li, H. X. Chen and C. Prins,
Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European Journal of Operational Research, 252 (2016), 27-38.
doi: 10.1016/j.ejor.2015.12.032. |
[23] |
S. Majidi, S. M. Hosseini-Motlagh and J. Ignatius,
Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery, Soft Computing, 22 (2018), 2851-2865.
doi: 10.1007/s00500-017-2535-5. |
[24] |
A. C. Matos and R. C. Oliverira,
An experimental study of the ant colony system for the period vehicle routing problem, Lecture Notes in Computer Science, 3172 (2004), 286-293.
doi: 10.1007/978-3-540-28646-2_26. |
[25] |
A. R. Pourghaderi, R. Tavakkoli-Moghaddam, M. Alinaghian and B. Beheshti-Pour, A simple and effective heuristic for periodic vehicle routing problem, Proceedings of the 2008 IEEE International Conference on Industrial Engineering Management, (2008), 133–137.
doi: 10.1109/IEEM.2008.4737846. |
[26] |
D. Pisinger and S. Ropker,
A general heuristic for vehicle routing problems, Computers and Operations Research, 34 (2007), 2403-2435.
doi: 10.1016/j.cor.2005.09.012. |
[27] |
R. Russell and W. Igo,
An assignment routing problem, Networks, 9 (1979), 1-17.
doi: 10.1002/net.3230090102. |
[28] |
S. Roker and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472. Google Scholar |
[29] |
I. Roozbeh, M. Ozlen and J. W. Hearne,
An Adaptive Large Neighborhood Search for asset protection during escaped wildfires, Computers and Operations Research, 97 (2018), 125-134.
doi: 10.1016/j.cor.2018.05.002. |
[30] |
X. Shize, Introductions of joint distribution, Circulation and economic study, 8 (1973), 87-94. Google Scholar |
[31] |
P. Shaw, Using constraint programming and local search methods to solve vehicle routingproblems, Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming Springer New York, (1998), 417–431. Google Scholar |
[32] |
A. Trentini, A. Campi, N. Malhene and F. Boscacci, Shared passengers & goods urban transport solutions: New ideas for milan through en international comparison, Territorio, 59 (2011), 38-44. Google Scholar |
[33] |
L. Verdonck, A. Caris, K. Ramaekers and G. K. Janssens,
Collaborative logistics from the perspective of road transportation companies, Transport Reviews, 33 (2013), 700-719.
doi: 10.1080/01441647.2013.853706. |
[34] |
L. Xu and D. Yang, Research on joint distribution cost allocation model, Boletin Tecnico/Technical Bulletin, 55 (2017), 291-297. Google Scholar |
[35] |
N. Yalaoui, L. Amodeo, F. Yalaoui and H. Mahdi,
Efficient methods to schedule reentrant flow shop system, Journal of Intelligent and Fuzzy Systems, 26 (2014), 1113-1121.
doi: 10.3233/IFS-130771. |
[36] |
S. Zhou, Logistics bottleneck of online retail industry in China, Journal of Supply Chain and Operations Management, 11 (2013), 1-11. Google Scholar |
show all references
References:
[1] |
D. Aksen, O. Kaya, F. S. Salman and Ö. Tuncel,
An adaptive large neighbor- hood search algorithm for a selective and periodic inventory routing problem, European Journal of Operational Research, 239 (2014), 413-426.
doi: 10.1016/j.ejor.2014.05.043. |
[2] |
E. J. Beltrami and L. D. Bodin,
Networks and vehicle routing for municipal waste collection, Networks, 4 (1974), 65-94.
doi: 10.1002/net.3230040106. |
[3] |
R. Bent and P. V. Hentenryck, A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows, Computers & Operations Research, 33 (2006), 875-893. Google Scholar |
[4] |
N. Christofides and J. E. Beasley, The period routing problem, Networks, 14 (1984), 237-256. Google Scholar |
[5] |
A. M. Campbell and H. W. Jill,
Forty years of periodic vehicle routing, Networks, 63 (2014), 2-15.
doi: 10.1002/net.21527. |
[6] |
I.-M. Chao, B. L. Golden and E. Wasil,
An improved heuristic for the period vehicle-routing problem, Networks, 26 (1995), 25-44.
doi: 10.1002/net.3230260104. |
[7] |
Z. Chang and H. Chen, Freight buses in three-tiered distribution systems for city logistics: Modeling and evaluation, 7th IESM Conference, (2017). Google Scholar |
[8] |
J. F. Cordeau, M. Gendreau and G. Laporte, A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53 (2002), 512-522. Google Scholar |
[9] |
G. Clarke and J. W. Wright,
Scheduling of vehicles from a central depot to a number of delivery points, Operations Research, 12 (1964), 568-581.
doi: 10.1007/978-3-642-27922-5_18. |
[10] |
B. Dai and H. X. Chen,
Proportional egalitarian core solution for profit allocation games with an application to collaborative transportation planning, European Journal of Industrial Engineering, 9 (2015), 53-76.
doi: 10.1504/EJIE.2015.067456. |
[11] |
L. M. A. Drummond, L. S. Ochi and D. S. Vianna,
An asynchronous parallel metaheuristic for the period vehicle routing problem, Future Generation Computer System, 17 (2001), 379-386.
doi: 10.1016/S0167-739X(99)00118-1. |
[12] |
E. Demir, T. Bektas and G. Laporte,
An adaptive large neighborhood search heuristic for the Pollution-Routing Problem, European Journal of Operational Research, 223 (2012), 346-359.
doi: 10.1016/j.ejor.2012.06.044. |
[13] |
B. Dai, H. X. Chen and G. K. Yang,
Price-setting based combinatorial auction approach for carrier collaboration with pickup and delivery requests, Operational Research, 14 (2014), 361-386.
doi: 10.1007/s12351-014-0141-1. |
[14] |
P. Francis, K. Smilowitz and M. Tzur,
The period vehicle routing problem with service choice, Transportation Science, 40 (2006), 439-454.
doi: 10.1287/trsc.1050.0140. |
[15] |
L. E. Gill and R. P. Allerheiligen,
Co-operation in channels of distribution: Physical distribution leads the way, International Journal of Physical Distribution & Logistics Management, 26 (1996), 49-63.
doi: 10.1108/eb014521. |
[16] |
M. Gaudioso and G. Paletta,
A heuristic for the periodic vehicle routing problem, Transport Science, 26 (1992), 86-92.
doi: 10.1287/trsc.26.2.86. |
[17] |
D. Goeke and M. Schneider,
Routing a mixed fleet of electric and conventional vehicles, European Journal of Operational Research, 245 (2015), 81-99.
doi: 10.1016/j.ejor.2015.01.049. |
[18] |
Y. Hao and Y. Su, The research on joint distribution mode of the chain retail enterprises, International Conference on Mechatronics, Electronic, Industrial and Control Engineering, MEIC, (2014), 1694–1697. Google Scholar |
[19] |
M. Y. Lai, H. M. Yang, S. P. Yang, J. H. Zhao and Y. Xu,
Cyber-physical logistics system-based vehicle routing optimization, Journal of Industrial and Management Optimization, 10 (2014), 701-715.
doi: 10.3934/jimo.2014.10.701. |
[20] |
L. L. Lv, Z. Zhang, L. Zhang and W. S. Wang,
An iterative algorithm for periodic Sylvester matrix equations, Journal of Industrial and Management Optimization, 14 (2018), 413-425.
doi: 10.3934/jimo.2017053. |
[21] |
N. Labadie, R. Mansini, J. Melechovský and R. Wolfler-Calvo,
The team orienteering problem with time windows: An LP-based granular variable neighborhood search, European Journal of Operational Research, 220 (2012), 15-27.
doi: 10.1016/j.ejor.2012.01.030. |
[22] |
Y. Li, H. X. Chen and C. Prins,
Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests, European Journal of Operational Research, 252 (2016), 27-38.
doi: 10.1016/j.ejor.2015.12.032. |
[23] |
S. Majidi, S. M. Hosseini-Motlagh and J. Ignatius,
Adaptive large neighborhood search heuristic for pollution-routing problem with simultaneous pickup and delivery, Soft Computing, 22 (2018), 2851-2865.
doi: 10.1007/s00500-017-2535-5. |
[24] |
A. C. Matos and R. C. Oliverira,
An experimental study of the ant colony system for the period vehicle routing problem, Lecture Notes in Computer Science, 3172 (2004), 286-293.
doi: 10.1007/978-3-540-28646-2_26. |
[25] |
A. R. Pourghaderi, R. Tavakkoli-Moghaddam, M. Alinaghian and B. Beheshti-Pour, A simple and effective heuristic for periodic vehicle routing problem, Proceedings of the 2008 IEEE International Conference on Industrial Engineering Management, (2008), 133–137.
doi: 10.1109/IEEM.2008.4737846. |
[26] |
D. Pisinger and S. Ropker,
A general heuristic for vehicle routing problems, Computers and Operations Research, 34 (2007), 2403-2435.
doi: 10.1016/j.cor.2005.09.012. |
[27] |
R. Russell and W. Igo,
An assignment routing problem, Networks, 9 (1979), 1-17.
doi: 10.1002/net.3230090102. |
[28] |
S. Roker and D. Pisinger, An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows, Transportation Science, 40 (2006), 455-472. Google Scholar |
[29] |
I. Roozbeh, M. Ozlen and J. W. Hearne,
An Adaptive Large Neighborhood Search for asset protection during escaped wildfires, Computers and Operations Research, 97 (2018), 125-134.
doi: 10.1016/j.cor.2018.05.002. |
[30] |
X. Shize, Introductions of joint distribution, Circulation and economic study, 8 (1973), 87-94. Google Scholar |
[31] |
P. Shaw, Using constraint programming and local search methods to solve vehicle routingproblems, Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming Springer New York, (1998), 417–431. Google Scholar |
[32] |
A. Trentini, A. Campi, N. Malhene and F. Boscacci, Shared passengers & goods urban transport solutions: New ideas for milan through en international comparison, Territorio, 59 (2011), 38-44. Google Scholar |
[33] |
L. Verdonck, A. Caris, K. Ramaekers and G. K. Janssens,
Collaborative logistics from the perspective of road transportation companies, Transport Reviews, 33 (2013), 700-719.
doi: 10.1080/01441647.2013.853706. |
[34] |
L. Xu and D. Yang, Research on joint distribution cost allocation model, Boletin Tecnico/Technical Bulletin, 55 (2017), 291-297. Google Scholar |
[35] |
N. Yalaoui, L. Amodeo, F. Yalaoui and H. Mahdi,
Efficient methods to schedule reentrant flow shop system, Journal of Intelligent and Fuzzy Systems, 26 (2014), 1113-1121.
doi: 10.3233/IFS-130771. |
[36] |
S. Zhou, Logistics bottleneck of online retail industry in China, Journal of Supply Chain and Operations Management, 11 (2013), 1-11. Google Scholar |






Instances | |
LB | |
|
|
|
|
|
7-3a | 1067.1 | 1067.1 | 1067.1 | 0.00 | 0.00 | 0.00 | 86.3 | 7.9 |
7-3b | 986.6 | 986.6 | 986.6 | 0.00 | 0.00 | 0.00 | 89.6 | 7.6 |
7-3c | 1076.9 | 1076.9 | 1076.9 | 0.00 | 0.00 | 0.00 | 87.9 | 8.2 |
7-3d | 962.0 | 962.0 | 962.0 | 0.00 | 0.00 | 0.00 | 87.6 | 8.7 |
7-3e | 1005.8 | 1005.8 | 1005.8 | 0.00 | 0.00 | 0.00 | 87.5 | 7.9 |
7-5a | 1984.1 | 1984.1 | 1984.1 | 0.00 | 0.00 | 0.00 | 257.3 | 19.7 |
7-5b | 1945.1 | 1945.1 | 1945.1 | 0.00 | 0.00 | 0.00 | 262.1 | 20.3 |
7-5c | 1887.0 | 1887.0 | 1887.0 | 0.00 | 0.00 | 0.00 | 258.2 | 21.9 |
7-5d | 1940.4 | 1940.4 | 1940.4 | 0.00 | 0.00 | 0.00 | 259.3 | 19.8 |
7-5e | 1896.6 | 1896.6 | 1896.6 | 0.00 | 0.00 | 0.00 | 260.3 | 20.3 |
13-3a | 1459.9 | 1074.8 | 1197.0 | 35.83 | 11.37 | 18.01 | 3600 | 25.8 |
13-3b | 1519.1 | 1089.3 | 1207.8 | 39.46 | 10.88 | 20.49 | 3600 | 25.6 |
13-3c | 1800.1 | 1342.1 | 1530.6 | 34.13 | 14.05 | 14.97 | 3600 | 26.9 |
13-3d | 1397.4 | 1007.7 | 1123.6 | 38.67 | 11.50 | 19.59 | 3600 | 26.3 |
13-3e | 2878.7 | 1848.4 | 2086.5 | 55.74 | 12.88 | 27.52 | 3600 | 27.1 |
13-5a | 3761.2 | 2527.9 | 2847.0 | 48.79 | 12.62 | 24.30 | 3600 | 40.3 |
13-5b | 3232.8 | 2264.2 | 2673.5 | 42.78 | 18.08 | 17.30 | 3600 | 39.7 |
13-5c | 3329.6 | 2220.5 | 2607.1 | 49.95 | 17.41 | 21.70 | 3600 | 42.3 |
13-5d | 3402.7 | 2238.7 | 2581.8 | 51.99 | 15.33 | 24.13 | 3600 | 41.2 |
13-5e | 3405.6 | 2427.8 | 2856.6 | 40.28 | 17.66 | 16.12 | 3600 | 40.3 |
Instances | |
LB | |
|
|
|
|
|
7-3a | 1067.1 | 1067.1 | 1067.1 | 0.00 | 0.00 | 0.00 | 86.3 | 7.9 |
7-3b | 986.6 | 986.6 | 986.6 | 0.00 | 0.00 | 0.00 | 89.6 | 7.6 |
7-3c | 1076.9 | 1076.9 | 1076.9 | 0.00 | 0.00 | 0.00 | 87.9 | 8.2 |
7-3d | 962.0 | 962.0 | 962.0 | 0.00 | 0.00 | 0.00 | 87.6 | 8.7 |
7-3e | 1005.8 | 1005.8 | 1005.8 | 0.00 | 0.00 | 0.00 | 87.5 | 7.9 |
7-5a | 1984.1 | 1984.1 | 1984.1 | 0.00 | 0.00 | 0.00 | 257.3 | 19.7 |
7-5b | 1945.1 | 1945.1 | 1945.1 | 0.00 | 0.00 | 0.00 | 262.1 | 20.3 |
7-5c | 1887.0 | 1887.0 | 1887.0 | 0.00 | 0.00 | 0.00 | 258.2 | 21.9 |
7-5d | 1940.4 | 1940.4 | 1940.4 | 0.00 | 0.00 | 0.00 | 259.3 | 19.8 |
7-5e | 1896.6 | 1896.6 | 1896.6 | 0.00 | 0.00 | 0.00 | 260.3 | 20.3 |
13-3a | 1459.9 | 1074.8 | 1197.0 | 35.83 | 11.37 | 18.01 | 3600 | 25.8 |
13-3b | 1519.1 | 1089.3 | 1207.8 | 39.46 | 10.88 | 20.49 | 3600 | 25.6 |
13-3c | 1800.1 | 1342.1 | 1530.6 | 34.13 | 14.05 | 14.97 | 3600 | 26.9 |
13-3d | 1397.4 | 1007.7 | 1123.6 | 38.67 | 11.50 | 19.59 | 3600 | 26.3 |
13-3e | 2878.7 | 1848.4 | 2086.5 | 55.74 | 12.88 | 27.52 | 3600 | 27.1 |
13-5a | 3761.2 | 2527.9 | 2847.0 | 48.79 | 12.62 | 24.30 | 3600 | 40.3 |
13-5b | 3232.8 | 2264.2 | 2673.5 | 42.78 | 18.08 | 17.30 | 3600 | 39.7 |
13-5c | 3329.6 | 2220.5 | 2607.1 | 49.95 | 17.41 | 21.70 | 3600 | 42.3 |
13-5d | 3402.7 | 2238.7 | 2581.8 | 51.99 | 15.33 | 24.13 | 3600 | 41.2 |
13-5e | 3405.6 | 2427.8 | 2856.6 | 40.28 | 17.66 | 16.12 | 3600 | 40.3 |
Parameter | Small instances | Medium instances | Large instances |
Maximum iterations number of ALNS |
25000 | 30000 | 35000 |
The roulette parameter |
0.1 | 0.1 | 0.1 |
The score increment of generating a new best solution (Q1) | 5 | 5 | 5 |
The score increment of generating a better solution (Q2) | 3 | 3 | 3 |
The score increment of generating a worse solution (Q3) | 1 | 1 | 1 |
Initial temperature parameter |
100 | 120 | 120 |
Cooling rate |
0.992 | 0.994 | 0.996 |
Removal fraction |
0.2 | 0.2 | 0.3 |
Noise parameter |
0.1 | 0.1 | 0.1 |
Parameter | Small instances | Medium instances | Large instances |
Maximum iterations number of ALNS |
25000 | 30000 | 35000 |
The roulette parameter |
0.1 | 0.1 | 0.1 |
The score increment of generating a new best solution (Q1) | 5 | 5 | 5 |
The score increment of generating a better solution (Q2) | 3 | 3 | 3 |
The score increment of generating a worse solution (Q3) | 1 | 1 | 1 |
Initial temperature parameter |
100 | 120 | 120 |
Cooling rate |
0.992 | 0.994 | 0.996 |
Removal fraction |
0.2 | 0.2 | 0.3 |
Noise parameter |
0.1 | 0.1 | 0.1 |
Abbreviation | Definition |
The best feasible objective value found by CPLEX in a preset running time | |
LB | The lower bound produced by CPLEX in a preset running time |
The best feasible objective value obtained by ALNS after a preset number of iterations | |
The gap between |
|
The gap between |
|
The improvement (reduction) of |
|
The CPU time (second) of CPLEX | |
The CPU time (second) of ALNS |
Abbreviation | Definition |
The best feasible objective value found by CPLEX in a preset running time | |
LB | The lower bound produced by CPLEX in a preset running time |
The best feasible objective value obtained by ALNS after a preset number of iterations | |
The gap between |
|
The gap between |
|
The improvement (reduction) of |
|
The CPU time (second) of CPLEX | |
The CPU time (second) of ALNS |
Instances | |
LB | |
|
|
|
|
|
20-3a | 2884.5 | 1966.6 | 2161.4 | 46.67 | 9.91 | 25.07 | 5400 | 135.7 |
20-3b | 3014.2 | 2101.2 | 2251.3 | 43.45 | 7.14 | 25.31 | 5400 | 140.7 |
20-3c | 3058.2 | 2069.5 | 2268.2 | 47.77 | 9.60 | 25.83 | 5400 | 133.2 |
20-3d | 2649.0 | 1807.7 | 2013.2 | 46.54 | 11.37 | 24.00 | 5400 | 135.7 |
20-3e | 2904.7 | 1949.3 | 2141.2 | 49.01 | 9.84 | 26.29 | 5400 | 134.2 |
20-5a | 5161.4 | 2951.8 | 3365.4 | 74.86 | 14.01 | 34.80 | 5400 | 216.4 |
20-5b | 4527.3 | 2627.2 | 2992.6 | 72.32 | 13.91 | 33.90 | 5400 | 203.5 |
20-5c | 4758.4 | 2698.5 | 3065.1 | 76.34 | 13.59 | 35.59 | 5400 | 218.8 |
20-5d | 4474.2 | 2556.1 | 2852.5 | 75.04 | 11.60 | 36.25 | 5400 | 199.5 |
20-5e | 4522.8 | 2573.0 | 2927.5 | 75.78 | 13.78 | 35.27 | 5400 | 220.3 |
30-3a | 4964.2 | 2664.8 | 3003.9 | 86.29 | 12.73 | 39.49 | 7200 | 289.3 |
30-3b | 5401.6 | 2922.8 | 3321.7 | 84.81 | 13.65 | 38.50 | 7200 | 276.8 |
30-3c | 4688.7 | 2520.6 | 2860.1 | 86.02 | 13.47 | 39.00 | 7200 | 296.3 |
30-3d | 4540.4 | 2381.9 | 2728.1 | 90.62 | 14.53 | 39.92 | 7200 | 295.3 |
30-3e | 4654.2 | 2502.6 | 2844.2 | 85.97 | 13.65 | 38.89 | 7200 | 287.6 |
30-5a | - | 4325.6 | 5167.3 | - | 19.46 | - | 7200 | 356.7 |
30-5b | 8140.4 | 4084.0 | 4859.6 | 99.32 | 18.99 | 40.30 | 7200 | 320.7 |
30-5c | - | 4390.0 | 5249.4 | - | 19.58 | - | 7200 | 364.3 |
30-5d | - | 3973.0 | 4733.7 | - | 19.15 | - | 7200 | 378.9 |
30-5e | - | 4154.9 | 4938.6 | - | 18.86 | - | 7200 | 352.1 |
40-3a | 6214.3 | 2835.6 | 3371.3 | 119.15 | 18.89 | 45.75 | 10800 | 478.7 |
40-3b | 6389.9 | 2832.7 | 3372.6 | 125.58 | 19.06 | 47.22 | 10800 | 480.3 |
40-3c | - | 2917.5 | 3469.4 | - | 18.92 | - | 10800 | 437.9 |
40-3d | 6072.1 | 2832.0 | 3381.9 | 114.41 | 19.42 | 44.30 | 10800 | 509.3 |
40-3e | 6112.3 | 3008.5 | 3590.5 | 103.17 | 19.35 | 41.26 | 10800 | 469.5 |
40-5a | - | 4824.4 | 6020.8 | - | 24.80 | - | 10800 | 597.3 |
40-5b | - | 5065.7 | 6325.8 | - | 24.88 | - | 10800 | 600.1 |
40-5c | - | 4944.1 | 6088.1 | - | 23.14 | - | 10800 | 623.5 |
40-5d | - | 4823.4 | 5940.9 | - | 23.17 | - | 10800 | 591.2 |
40-5e | - | 4664.0 | 5764.5 | - | 23.60 | - | 10800 | 589.7 |
Instances | |
LB | |
|
|
|
|
|
20-3a | 2884.5 | 1966.6 | 2161.4 | 46.67 | 9.91 | 25.07 | 5400 | 135.7 |
20-3b | 3014.2 | 2101.2 | 2251.3 | 43.45 | 7.14 | 25.31 | 5400 | 140.7 |
20-3c | 3058.2 | 2069.5 | 2268.2 | 47.77 | 9.60 | 25.83 | 5400 | 133.2 |
20-3d | 2649.0 | 1807.7 | 2013.2 | 46.54 | 11.37 | 24.00 | 5400 | 135.7 |
20-3e | 2904.7 | 1949.3 | 2141.2 | 49.01 | 9.84 | 26.29 | 5400 | 134.2 |
20-5a | 5161.4 | 2951.8 | 3365.4 | 74.86 | 14.01 | 34.80 | 5400 | 216.4 |
20-5b | 4527.3 | 2627.2 | 2992.6 | 72.32 | 13.91 | 33.90 | 5400 | 203.5 |
20-5c | 4758.4 | 2698.5 | 3065.1 | 76.34 | 13.59 | 35.59 | 5400 | 218.8 |
20-5d | 4474.2 | 2556.1 | 2852.5 | 75.04 | 11.60 | 36.25 | 5400 | 199.5 |
20-5e | 4522.8 | 2573.0 | 2927.5 | 75.78 | 13.78 | 35.27 | 5400 | 220.3 |
30-3a | 4964.2 | 2664.8 | 3003.9 | 86.29 | 12.73 | 39.49 | 7200 | 289.3 |
30-3b | 5401.6 | 2922.8 | 3321.7 | 84.81 | 13.65 | 38.50 | 7200 | 276.8 |
30-3c | 4688.7 | 2520.6 | 2860.1 | 86.02 | 13.47 | 39.00 | 7200 | 296.3 |
30-3d | 4540.4 | 2381.9 | 2728.1 | 90.62 | 14.53 | 39.92 | 7200 | 295.3 |
30-3e | 4654.2 | 2502.6 | 2844.2 | 85.97 | 13.65 | 38.89 | 7200 | 287.6 |
30-5a | - | 4325.6 | 5167.3 | - | 19.46 | - | 7200 | 356.7 |
30-5b | 8140.4 | 4084.0 | 4859.6 | 99.32 | 18.99 | 40.30 | 7200 | 320.7 |
30-5c | - | 4390.0 | 5249.4 | - | 19.58 | - | 7200 | 364.3 |
30-5d | - | 3973.0 | 4733.7 | - | 19.15 | - | 7200 | 378.9 |
30-5e | - | 4154.9 | 4938.6 | - | 18.86 | - | 7200 | 352.1 |
40-3a | 6214.3 | 2835.6 | 3371.3 | 119.15 | 18.89 | 45.75 | 10800 | 478.7 |
40-3b | 6389.9 | 2832.7 | 3372.6 | 125.58 | 19.06 | 47.22 | 10800 | 480.3 |
40-3c | - | 2917.5 | 3469.4 | - | 18.92 | - | 10800 | 437.9 |
40-3d | 6072.1 | 2832.0 | 3381.9 | 114.41 | 19.42 | 44.30 | 10800 | 509.3 |
40-3e | 6112.3 | 3008.5 | 3590.5 | 103.17 | 19.35 | 41.26 | 10800 | 469.5 |
40-5a | - | 4824.4 | 6020.8 | - | 24.80 | - | 10800 | 597.3 |
40-5b | - | 5065.7 | 6325.8 | - | 24.88 | - | 10800 | 600.1 |
40-5c | - | 4944.1 | 6088.1 | - | 23.14 | - | 10800 | 623.5 |
40-5d | - | 4823.4 | 5940.9 | - | 23.17 | - | 10800 | 591.2 |
40-5e | - | 4664.0 | 5764.5 | - | 23.60 | - | 10800 | 589.7 |
Instances | |
LB | |
|
|
|
|
|
60-3a | 11510.5 | 4550.1 | 5313.7 | 152.97 | 16.78 | 53.84 | 14400 | 979.3 |
60-3b | - | 5140.4 | 5971.6 | - | 16.17 | - | 14400 | 1000.1 |
60-3c | 11918.4 | 4742.3 | 5507.3 | 151.32 | 16.13 | 53.79 | 14400 | 1005.3 |
60-3d | - | 4340.2 | 5106.7 | - | 17.66 | - | 14400 | 989.3 |
60-3e | 11509.7 | 4694.8 | 5494.9 | 145.16 | 17.04 | 52.26 | 14400 | 996.1 |
60-5a | - | 8123.9 | 9972.9 | - | 22.76 | - | 14400 | 1421.6 |
60-5b | - | 7669.4 | 9493.1 | - | 23.78 | - | 14400 | 1432.3 |
60-5c | - | 8041.2 | 9809.9 | - | 22.00 | - | 14400 | 1410.5 |
60-5d | - | 8318.1 | 10172.5 | - | 22.29 | - | 14400 | 1396.3 |
60-5e | - | 8372.7 | 10135.2 | - | 21.05 | - | 14400 | 1389.3 |
80-3a | - | 6288.6 | 7419.3 | - | 17.98 | - | 18000 | 1523.4 |
80-3b | - | 5992.0 | 7135.8 | - | 19.09 | - | 18000 | 1612.3 |
80-3c | - | 6431.5 | 7683.1 | - | 19.46 | - | 18000 | 1496.8 |
80-3d | - | 5785.2 | 6836.7 | - | 18.18 | - | 18000 | 1527.4 |
80-3e | - | 6104.0 | 7264.1 | - | 19.01 | - | 18000 | 1559.3 |
80-5a | - | 8670.0 | 10889.2 | - | 25.60 | - | 18000 | 1963.2 |
80-5b | - | 8260.9 | 10207.5 | - | 23.56 | - | 18000 | 2001.3 |
80-5c | - | 8855.8 | 11163.3 | - | 26.06 | - | 18000 | 1989.7 |
80-5d | - | 8611.5 | 10627.6 | - | 23.41 | - | 18000 | 1967.3 |
80-5e | - | 8596.7 | 10703.1 | - | 24.50 | - | 18000 | 1995.3 |
Instances | |
LB | |
|
|
|
|
|
60-3a | 11510.5 | 4550.1 | 5313.7 | 152.97 | 16.78 | 53.84 | 14400 | 979.3 |
60-3b | - | 5140.4 | 5971.6 | - | 16.17 | - | 14400 | 1000.1 |
60-3c | 11918.4 | 4742.3 | 5507.3 | 151.32 | 16.13 | 53.79 | 14400 | 1005.3 |
60-3d | - | 4340.2 | 5106.7 | - | 17.66 | - | 14400 | 989.3 |
60-3e | 11509.7 | 4694.8 | 5494.9 | 145.16 | 17.04 | 52.26 | 14400 | 996.1 |
60-5a | - | 8123.9 | 9972.9 | - | 22.76 | - | 14400 | 1421.6 |
60-5b | - | 7669.4 | 9493.1 | - | 23.78 | - | 14400 | 1432.3 |
60-5c | - | 8041.2 | 9809.9 | - | 22.00 | - | 14400 | 1410.5 |
60-5d | - | 8318.1 | 10172.5 | - | 22.29 | - | 14400 | 1396.3 |
60-5e | - | 8372.7 | 10135.2 | - | 21.05 | - | 14400 | 1389.3 |
80-3a | - | 6288.6 | 7419.3 | - | 17.98 | - | 18000 | 1523.4 |
80-3b | - | 5992.0 | 7135.8 | - | 19.09 | - | 18000 | 1612.3 |
80-3c | - | 6431.5 | 7683.1 | - | 19.46 | - | 18000 | 1496.8 |
80-3d | - | 5785.2 | 6836.7 | - | 18.18 | - | 18000 | 1527.4 |
80-3e | - | 6104.0 | 7264.1 | - | 19.01 | - | 18000 | 1559.3 |
80-5a | - | 8670.0 | 10889.2 | - | 25.60 | - | 18000 | 1963.2 |
80-5b | - | 8260.9 | 10207.5 | - | 23.56 | - | 18000 | 2001.3 |
80-5c | - | 8855.8 | 11163.3 | - | 26.06 | - | 18000 | 1989.7 |
80-5d | - | 8611.5 | 10627.6 | - | 23.41 | - | 18000 | 1967.3 |
80-5e | - | 8596.7 | 10703.1 | - | 24.50 | - | 18000 | 1995.3 |
Instances | |||||
7-3 | 0 | 0 | 0 | 87.78 | 8.06 |
7-5 | 0 | 0 | 0 | 259.44 | 20.4 |
13-3 | 40.76 | 12.14 | 20.12 | 3600 | 26.3 |
13-5 | 46.76 | 16.22 | 20.71 | 3600 | 40.76 |
20-3 | 46.69 | 9.57 | 25.30 | 5400 | 135.9 |
20-5 | 74.87 | 13.38 | 35.16 | 5400 | 211.7 |
30-3 | 86.74 | 13.61 | 39.16 | 7200 | 289.1 |
30-5 | 99.32 | 19.21 | 40.30 | 7200 | 354.5 |
40-3 | 115.58 | 19.13 | 44.63 | 10800 | 475.1 |
40-5 | - | 23.92 | - | 10800 | 600.4 |
60-3 | 149.82 | 16.76 | 53.30 | 14400 | 994.0 |
60-5 | - | 22.38 | - | 14400 | 1410.0 |
80-3 | - | 18.74 | - | 18000 | 1543.8 |
80-5 | - | 24.63 | - | 18000 | 1983.4 |
Instances | |||||
7-3 | 0 | 0 | 0 | 87.78 | 8.06 |
7-5 | 0 | 0 | 0 | 259.44 | 20.4 |
13-3 | 40.76 | 12.14 | 20.12 | 3600 | 26.3 |
13-5 | 46.76 | 16.22 | 20.71 | 3600 | 40.76 |
20-3 | 46.69 | 9.57 | 25.30 | 5400 | 135.9 |
20-5 | 74.87 | 13.38 | 35.16 | 5400 | 211.7 |
30-3 | 86.74 | 13.61 | 39.16 | 7200 | 289.1 |
30-5 | 99.32 | 19.21 | 40.30 | 7200 | 354.5 |
40-3 | 115.58 | 19.13 | 44.63 | 10800 | 475.1 |
40-5 | - | 23.92 | - | 10800 | 600.4 |
60-3 | 149.82 | 16.76 | 53.30 | 14400 | 994.0 |
60-5 | - | 22.38 | - | 14400 | 1410.0 |
80-3 | - | 18.74 | - | 18000 | 1543.8 |
80-5 | - | 24.63 | - | 18000 | 1983.4 |
Instances | System without Freight bus | System with Freight bus | Cost Saving in percentage | |
Small size instances | 7-3 | 1237.50 | 1019.7 | 17.6 |
7-5 | 2363.04 | 1930.6 | 18.3 | |
13-3 | 1779.70 | 1429.1 | 19.7 | |
13-5 | 3400.00 | 2713.2 | 20.2 | |
Medium size instances | 20-3 | 2818.08 | 2167.1 | 23.1 |
20-5 | 3938.60 | 3040.6 | 22.8 | |
30-3 | 3909.40 | 2951.6 | 24.5 | |
30-5 | 6635.24 | 4989.7 | 24.8 | |
40-3 | 4625.98 | 3437.1 | 25.7 | |
40-5 | 8168.02 | 6028 | 26.2 | |
Large size instances | 60-3 | 7749.36 | 5478.8 | 29.3 |
60-5 | 14186.98 | 9916.7 | 30.1 | |
80-3 | 10945.48 | 7267.8 | 33.6 | |
80-5 | 16565.84 | 10718.1 | 35.3 |
Instances | System without Freight bus | System with Freight bus | Cost Saving in percentage | |
Small size instances | 7-3 | 1237.50 | 1019.7 | 17.6 |
7-5 | 2363.04 | 1930.6 | 18.3 | |
13-3 | 1779.70 | 1429.1 | 19.7 | |
13-5 | 3400.00 | 2713.2 | 20.2 | |
Medium size instances | 20-3 | 2818.08 | 2167.1 | 23.1 |
20-5 | 3938.60 | 3040.6 | 22.8 | |
30-3 | 3909.40 | 2951.6 | 24.5 | |
30-5 | 6635.24 | 4989.7 | 24.8 | |
40-3 | 4625.98 | 3437.1 | 25.7 | |
40-5 | 8168.02 | 6028 | 26.2 | |
Large size instances | 60-3 | 7749.36 | 5478.8 | 29.3 |
60-5 | 14186.98 | 9916.7 | 30.1 | |
80-3 | 10945.48 | 7267.8 | 33.6 | |
80-5 | 16565.84 | 10718.1 | 35.3 |
[1] |
Sören Bartels, Jakob Keck. Adaptive time stepping in elastoplasticity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 71-88. doi: 10.3934/dcdss.2020323 |
[2] |
Kalikinkar Mandal, Guang Gong. On ideal $ t $-tuple distribution of orthogonal functions in filtering de bruijn generators. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020125 |
[3] |
Hongguang Ma, Xiang Li. Multi-period hazardous waste collection planning with consideration of risk stability. Journal of Industrial & Management Optimization, 2021, 17 (1) : 393-408. doi: 10.3934/jimo.2019117 |
[4] |
Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65 |
[5] |
Hanyu Gu, Hue Chi Lam, Yakov Zinder. Planning rolling stock maintenance: Optimization of train arrival dates at a maintenance center. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020177 |
[6] |
Nan Zhang, Linyi Qian, Zhuo Jin, Wei Wang. Optimal stop-loss reinsurance with joint utility constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 841-868. doi: 10.3934/jimo.2020001 |
[7] |
Darko Dimitrov, Hosam Abdo. Tight independent set neighborhood union condition for fractional critical deleted graphs and ID deleted graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 711-721. doi: 10.3934/dcdss.2019045 |
[8] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
[9] |
M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014 |
[10] |
Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076 |
[11] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[12] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[13] |
Editorial Office. Retraction: Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin and Zhike Han, Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-957. doi: 10.3934/dcdss.2019064 |
[14] |
Emre Esentürk, Juan Velazquez. Large time behavior of exchange-driven growth. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 747-775. doi: 10.3934/dcds.2020299 |
[15] |
Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 61-79. doi: 10.3934/dcdsb.2020351 |
[16] |
Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020386 |
[17] |
Stefan Ruschel, Serhiy Yanchuk. The spectrum of delay differential equations with multiple hierarchical large delays. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 151-175. doi: 10.3934/dcdss.2020321 |
[18] |
Junyong Eom, Kazuhiro Ishige. Large time behavior of ODE type solutions to nonlinear diffusion equations. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3395-3409. doi: 10.3934/dcds.2019229 |
[19] |
Tinghua Hu, Yang Yang, Zhengchun Zhou. Golay complementary sets with large zero odd-periodic correlation zones. Advances in Mathematics of Communications, 2021, 15 (1) : 23-33. doi: 10.3934/amc.2020040 |
[20] |
Xiaoping Zhai, Yongsheng Li. Global large solutions and optimal time-decay estimates to the Korteweg system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1387-1413. doi: 10.3934/dcds.2020322 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]