American Institute of Mathematical Sciences

Advanced
  • 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
doi: 10.3934/jimo.2020045

Adaptive large neighborhood search Algorithm for route planning of freight buses with pickup and delivery

Zheng Chang 1, , Haoxun Chen 2,, , Farouk Yalaoui 2, and  Bo Dai 3,,

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

* Corresponding author: Haoxun Chen and Bo Dai

Received  November 2018 Revised  July 2019 Published  March 2020

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.

Keywords: Adaptive large neighborhood search Algorithm, route planning, freight bus, joint distribution.
Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.
Citation: 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, doi: 10.3934/jimo.2020045
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.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[27]

R. Russell and W. Igo, An assignment routing problem, Networks, 9 (1979), 1-17.  doi: 10.1002/net.3230090102.  Google Scholar

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[27]

R. Russell and W. Igo, An assignment routing problem, Networks, 9 (1979), 1-17.  doi: 10.1002/net.3230090102.  Google Scholar

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

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

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

[36]

S. Zhou, Logistics bottleneck of online retail industry in China, Journal of Supply Chain and Operations Management, 11 (2013), 1-11.   Google Scholar

Figure 1.  City freighters in an urban distribution system
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Freight buses in an urban distribution system
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  An example of freight bus lines
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The procedure framework of ALNS
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The average performances of CPLEX and ALNS ($ M = 3 $)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The average performances of CPLEX and ALNS ($ M = 5 $)
Figure Options

Download full-size image

Download as PowerPoint slide

Table 3.  Experimental results of small size instances
Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table Options

Download as excel

Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table 1.  Parameter Setting of the ALNS for different sizes of instances
Parameter Small instances Medium instances Large instances
Maximum iterations number of ALNS $ (N) $ 25000 30000 35000
The roulette parameter $ (r) $ 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 $ \left(P_{\text {init}}\right) $ 100 120 120
Cooling rate $ (\mathrm{h}) $ 0.992 0.994 0.996
Removal fraction $ (\rho) $ 0.2 0.2 0.3
Noise parameter $ (\mathrm{u}) $ 0.1 0.1 0.1
Table Options

Download as excel

Parameter Small instances Medium instances Large instances
Maximum iterations number of ALNS $ (N) $ 25000 30000 35000
The roulette parameter $ (r) $ 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 $ \left(P_{\text {init}}\right) $ 100 120 120
Cooling rate $ (\mathrm{h}) $ 0.992 0.994 0.996
Removal fraction $ (\rho) $ 0.2 0.2 0.3
Noise parameter $ (\mathrm{u}) $ 0.1 0.1 0.1
Table 2.  Performance indicators
Abbreviation Definition
$ Cplex_{Obj} $ 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
$ ALNS_{Obj} $ The best feasible objective value obtained by ALNS after a preset number of iterations
$ Gap_{Cplex} $ The gap between $ Cplex_{Obj} $ and LB, which is defined as ($ Cplex_{Obj} $- LB)/LB*100
$ Gap_{ALNS} $ The gap between $ ALNS_{Obj} $ and LB, which is defined as ($ ALNS_{Obj} $- LB)/ LB*100
$ Imp_{ALNS-Cplex} $ The improvement (reduction) of $ ALNS_{Obj} $ over $ Cplex_{Obj} $, which is defined as ($ Cplex_{Obj} $- $ ALNS_{Obj} $)/ $ Cplex_{Obj} $*100
$ CPU_{Cplex} $ The CPU time (second) of CPLEX
$ CPU_{ALNS} $ The CPU time (second) of ALNS
Table Options

Download as excel

Abbreviation Definition
$ Cplex_{Obj} $ 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
$ ALNS_{Obj} $ The best feasible objective value obtained by ALNS after a preset number of iterations
$ Gap_{Cplex} $ The gap between $ Cplex_{Obj} $ and LB, which is defined as ($ Cplex_{Obj} $- LB)/LB*100
$ Gap_{ALNS} $ The gap between $ ALNS_{Obj} $ and LB, which is defined as ($ ALNS_{Obj} $- LB)/ LB*100
$ Imp_{ALNS-Cplex} $ The improvement (reduction) of $ ALNS_{Obj} $ over $ Cplex_{Obj} $, which is defined as ($ Cplex_{Obj} $- $ ALNS_{Obj} $)/ $ Cplex_{Obj} $*100
$ CPU_{Cplex} $ The CPU time (second) of CPLEX
$ CPU_{ALNS} $ The CPU time (second) of ALNS
Table 4.  Experimental results of medium size instances
Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table Options

Download as excel

Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table 5.  Experimental results of large size instances
Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table Options

Download as excel

Instances $ Cplex_{Obj} $ LB $ ALNS_{Obj} $ $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table 6.  The average performances of the two solution methods
Instances $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table Options

Download as excel

Instances $ Gap_{Cplex} $ $ Gap_{ALNS} $ $ Imp_{ALNS-Cplex} $ $ CPU_{Cplex} $ $ CPU_{ALNS} $
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
Table 7.  The comparison of the average costs of the two systems
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
Table Options

Download as excel

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

  • PDF downloads (118)
  • HTML views (481)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences