American Institute of Mathematical Sciences

Advanced
July  2021, 17(4): 1771-1793. 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, 2021, 17 (4) : 1771-1793. 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]

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

Yi Gao, Rui Li, Yingjing Shi, Li Xiao. Design of path planning and tracking control of quadrotor. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021063
[3]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[4]

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

Xue Qiao, Zheng Wang, Haoxun Chen. Joint optimal pricing and inventory management policy and its sensitivity analysis for perishable products: Lost sale case. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021079
[6]

Andrey Kovtanyuk, Alexander Chebotarev, Nikolai Botkin, Varvara Turova, Irina Sidorenko, Renée Lampe. Modeling the pressure distribution in a spatially averaged cerebral capillary network. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021016
[7]

Sheng-I Chen, Yen-Che Tseng. A partitioning column approach for solving LED sorter manipulator path planning problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021055
[8]

Yongkun Wang, Fengshou He, Xiaobo Deng. Multi-aircraft cooperative path planning for maneuvering target detection. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021050
[9]

Ricardo A. Podestá, Denis E. Videla. The weight distribution of irreducible cyclic codes associated with decomposable generalized Paley graphs. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021002
[10]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[11]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321
[12]

Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025
[13]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017
[14]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781
[15]

Ashkan Ayough, Farbod Farhadi, Mostafa Zandieh, Parisa Rastkhadiv. Genetic algorithm for obstacle location-allocation problems with customer priorities. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1753-1769. doi: 10.3934/jimo.2020044
[16]

Rabiaa Ouahabi, Nasr-Eddine Hamri. Design of new scheme adaptive generalized hybrid projective synchronization for two different chaotic systems with uncertain parameters. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2361-2370. doi: 10.3934/dcdsb.2020182
[17]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[18]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258
[19]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195
[20]

Andreu Ferré Moragues. Properties of multicorrelation sequences and large returns under some ergodicity assumptions. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2809-2828. doi: 10.3934/dcds.2020386

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (178)
  • HTML views (589)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences