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  July 2021 Early access  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 and 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.

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

[4]

N. Christofides and J. E. Beasley, The period routing problem, Networks, 14 (1984), 237-256. 

[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).

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

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

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

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

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

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

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

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

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. 

[4]

N. Christofides and J. E. Beasley, The period routing problem, Networks, 14 (1984), 237-256. 

[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).

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

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

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

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

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

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

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

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

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]

Bin Feng, Lixin Wei, Ziyu Hu. An adaptive large neighborhood search algorithm for Vehicle Routing Problem with Multiple Time Windows constraints. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021197
[2]

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

Rodolfo Mendoza-Gómez, Roger Z. Ríos-Mercado, Karla B. Valenzuela-Ocaña. An iterated greedy algorithm with variable neighborhood descent for the planning of specialized diagnostic services in a segmented healthcare system. Journal of Industrial and Management Optimization, 2020, 16 (2) : 857-885. doi: 10.3934/jimo.2018182
[4]

Jiuping Xu, Pei Wei. Production-distribution planning of construction supply chain management under fuzzy random environment for large-scale construction projects. Journal of Industrial and Management Optimization, 2013, 9 (1) : 31-56. doi: 10.3934/jimo.2013.9.31
[5]

Zhou Sheng, Gonglin Yuan, Zengru Cui, Xiabin Duan, Xiaoliang Wang. An adaptive trust region algorithm for large-residual nonsmooth least squares problems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 707-718. doi: 10.3934/jimo.2017070
[6]

Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial and Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31
[7]

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

Lou Caccetta, Elham Mardaneh. Joint pricing and production planning for fixed priced multiple products with backorders. Journal of Industrial and Management Optimization, 2010, 6 (1) : 123-147. doi: 10.3934/jimo.2010.6.123
[9]

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

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

Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142
[12]

Qin Sheng, David A. Voss, Q. M. Khaliq. An adaptive splitting algorithm for the sine-Gordon equation. Conference Publications, 2005, 2005 (Special) : 792-797. doi: 10.3934/proc.2005.2005.792
[13]

Kegui Chen, Xinyu Wang, Min Huang, Wai-Ki Ching. Salesforce contract design, joint pricing and production planning with asymmetric overconfidence sales agent. Journal of Industrial and Management Optimization, 2017, 13 (2) : 873-899. doi: 10.3934/jimo.2016051
[14]

Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control and Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193
[15]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control and Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[16]

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

Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017
[18]

Yi Jing, Wenchuan Li. Integrated recycling-integrated production - distribution planning for decentralized closed-loop supply chain. Journal of Industrial and Management Optimization, 2018, 14 (2) : 511-539. doi: 10.3934/jimo.2017058
[19]

Xuefeng Zhang, Hui Yan. Image enhancement algorithm using adaptive fractional differential mask technique. Mathematical Foundations of Computing, 2019, 2 (4) : 347-359. doi: 10.3934/mfc.2019022
[20]

Zheng-Ru Zhang, Tao Tang. An adaptive mesh redistribution algorithm for convection-dominated problems. Communications on Pure and Applied Analysis, 2002, 1 (3) : 341-357. doi: 10.3934/cpaa.2002.1.341

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (695)
  • HTML views (1065)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy