A mathematical model for the capacitated location-arc routing problem with deadlines and heterogeneous fleet
Abstract
This paper considers a Capacitated Location-Arc Routing Problem (CLARP) with Deadlines (CLARPD) and a fleet of capacitated heterogeneous vehicles. The proposed mixed integer programming model determines a subset of potential depots to be opened, the served roads within predefined deadlines, and the vehicles assigned to each open depot. In addition, efficient routing plans are determined to minimize total establishment and traveling costs. Since the CLARP is NP-hard, a Genetic Algorithm (GA) is presented to consider proposed operators, and a constructive heuristic to generate initial solutions. In addition, a Simulated Annealing (SA) algorithm is investigated to compare the performance of the GA. Computational experiments are carried out for several test instances. The computational results show that the proposed GA is promising. Finally, sensitivity analysis confirms that the developed model can meet arc routing timing requirements more precisely compared to the classical Capacitated Arc Routing Problem (CARP).
First published online 26 September 2019
Keyword : capacitated location-arc routing, mixed integer programming, deadlines, genetic algorithm, simulated annealing, heterogeneous fleet
How to Cite
Mirzaei-Khafri, S., Bashiri, M., Soltani, R., & Khalilzadeh, M. (2019). A mathematical model for the capacitated location-arc routing problem with deadlines and heterogeneous fleet. Transport, 34(6), 692-707. https://doi.org/10.3846/transport.2019.11145
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Afsar, H. M. 2010. A branch-and-price algorithm for capacitated arc routing problem with flexible time windows, Electronic Notes in Discrete Mathematics 36: 319–326. https://doi.org/10.1016/j.endm.2010.05.041
Aksen, D.; Altinkemer, K. 2008. A location-routing problem for the conversion to the “click-and-mortar” retailing: the static case, European Journal of Operational Research 186(2): 554–575. https://doi.org/10.1016/j.ejor.2007.01.048
Amaya, A.; Langevin, A.; Trépanier, M. 2007. The capacitated arc routing problem with refill points, Operations Research Letters 35(1): 45–53. https://doi.org/10.1016/j.orl.2005.12.009
Arakaki, R. K.; Usberti, F. L. 2018. Hybrid genetic algorithm for the open capacitated arc routing problem, Computers & Operations Research 90: 221–231. https://doi.org/10.1016/j.cor.2017.09.020
Baker, B. M.; Ayechew, M. A. 2003. A genetic algorithm for the vehicle routing problem, Computers & Operations Research 30(5): 787–800. https://doi.org/10.1016/S0305-0548(02)00051-5
Brandão, J.; Eglese, R. 2008. A deterministic tabu search algorithm for the capacitated arc routing problem, Computers & Operations Research 35(4): 1112–1126. https://doi.org/10.1016/j.cor.2006.07.007
Bräysy, O.; Gendreau, M. 2005. Vehicle routing problem with time windows, part II: metaheuristics, Transportation Science 39(1): 119–139. https://doi.org/10.1287/trsc.1030.0057
Chen, L.; Chen, B.; Bui, Q. T.; Hà, M. H. 2017. Designing service sectors for daily maintenance operations in a road network, International Journal of Production Research 55(8): 2251–2265. https://doi.org/10.1080/00207543.2016.1233363
Cheng, C.-B.; Wang, K.-P. 2009. Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm, Expert Systems with Applications 36(4): 7758–7763. https://doi.org/10.1016/j.eswa.2008.09.001
Ciancio, C.; Laganá, D.; Vocaturo, F. 2018. Branch-price-and-cut for the mixed capacitated general routing problem with time windows, European Journal of Operational Research 267(1): 187–199. https://doi.org/10.1016/j.ejor.2017.11.039
Eglese, R. W. 1994. Routeing winter gritting vehicles, Discrete Applied Mathematics 48(3): 231–244. https://doi.org/10.1016/0166-218X(92)00003-5
Farham, M. S.; Süral, H.; Iyigun, C. 2018. A column generation approach for the location-routing problem with time windows, Computers & Operations Research 90: 249–263. https://doi.org/10.1016/j.cor.2017.09.010
Fazayeli, S.; Eydi, A.; Kamalabadi, I. N. 2018. Location-routing problem in multimodal transportation network with time windows and fuzzy demands: presenting a two-part genetic algorithm, Computers & Industrial Engineering 119: 233–246. https://doi.org/10.1016/j.cie.2018.03.041
Fazel Zarandi, M. H.; Hemmati, A.; Davari, S.; Turksen, I. B. 2013. Capacitated location-routing problem with time windows under uncertainty, Knowledge-Based Systems 37: 480–489. https://doi.org/10.1016/j.knosys.2012.09.007
Frederickson, G. N. 1979. Approximation algorithms for some postman problems, Journal of the ACM 26(3): 538–554. https://doi.org/10.1145/322139.322150
Gharavani, M.; Setak, M. 2015. A capacitated location routing problem with semi soft time windows, Advanced Computational Techniques in Electromagnetics 1: 26–40. https://doi.org/10.5899/2015/acte-00197
Ghiani, G.; Laporte, G. 1999. Eulerian location problems, Networks 34(4): 291–302. https://doi.org/10.1002/(SICI)1097-0037(199912)34:4% 3C291::AID-NET9%3E3.0.CO;2-4
Ghiani, G.; Laporte, G. 2001. Location-arc routing problems, OPSEARCH 38(2): 151–159. https://doi.org/10.1007/BF03399222
Golden, B. L.; Wong, R. T. 1981. Capacitated arc routing problems, Networks 11(3): 305–315. https://doi.org/10.1002/net.3230110308
Golden, B. L.; Dearmon, J. S.; Baker, E. K. 1983. Computational experiments with algorithms for a class of routing problems, Computers & Operations Research 10(1): 47–59. https://doi.org/10.1016/0305-0548(83)90026-6
Govindan, K.; Jafarian, A.; Khodaverdi, R.; Devika, K. 2014. Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food, International Journal of Production Economics 152: 9–28. https://doi.org/10.1016/j.ijpe.2013.12.028
Gündüz, H. I. 2011. The single-stage location-routing problem with time windows, Lecture Notes in Computer Science 6971: 44–58. https://doi.org/10.1007/978-3-642-24264-9_4
Haghani, A.; Qiao, H. 2001. Decision support system for snow emergency vehicle routing: algorithms and application, Transportation Research Record: Journal of the Transportation Research Board 1771: 172–178. https://doi.org/10.3141/1771-22
Hashemi Doulabi, S. H.; Seifi, A. 2013. Lower and upper bounds for location-arc routing problems with vehicle capacity constraints, European Journal of Operational Research 224(1): 189–208. https://doi.org/10.1016/j.ejor.2012.06.015
Hassan, R.; Cohanim, B.; De Weck, O.; Venter, G. 2005. A comparison of particle swarm optimization and the genetic algorithm, in 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, 18–21 April 2005, Austin, Texas, US. https://doi.org/10.2514/6.2005-1897
Hirabayashi, R.; Saruwatari, Y.; Nishida, N. 1992. Tour construction algorithm for the capacitated arc routing problems, Asia-Pacific Journal of Operational Research 9(2): 155–175.
Holland, J. H. 1992. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. A Bradford Book. 232 p.
Johnson, E. L.; Wøhlk, S. 2009. Solving the Capacitated Arc Routing Problem with Time Windows using Column Generation. Working Paper L-2008-0. Centre for Operations Research Applications in Logistics (CORAL), University of Aarhus, Denmark. 19 p. Available from Internet: https://pure.au.dk/portal/files/3875/L_2008_09.pdf
Levy, L.; Bodin, L. 1989. The arc oriented location routing problem, INFOR: Information Systems and Operational Research 27(1): 74–94. https://doi.org/10.1080/03155986.1989.11732083
Lopes, R. B.; Ferreira, C.; Santos, B. S.; Barreto, S. 2013. A taxonomical analysis, current methods and objectives on location‐routing problems, International Transactions in Operational Research 20(6): 795–822. https://doi.org/10.1111/itor.12032
Lopes, R. B.; Plastria, F.; Ferreira, C.; Santos, B. S. 2014. Location-arc routing problem: Heuristic approaches and test instances, Computers & Operations Research 43: 309–317. https://doi.org/10.1016/j.cor.2013.10.003
Mullaseril, P. A. 1997. Capacitated Rural Postman Problem with Time Windows and Split Delivery. PhD Dissertation. University of Arizona, Tucson, US. 160 p. Available from Internet: https://repository.arizona.edu/handle/10150/282300
Muyldermans, L.; Pang, G. 2010. A guided local search procedure for the multi-compartment capacitated arc routing problem, Computers & Operations Research 37(9): 1662–1673. https://doi.org/10.1016/j.cor.2009.12.014
Nagy, G.; Salhi, S. 2007. Location-routing: Issues, models and methods, European Journal of Operational Research 177(2): 649–672. https://doi.org/10.1016/j.ejor.2006.04.004
Nikbakhsh, E.; Zegordi, S. 2010. A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints, Scientia Iranica 17(1): 36–47.
Prodhon, C.; Prins, C. 2014. A survey of recent research on location-routing problems, European Journal of Operational Research 238(1): 1–17. https://doi.org/10.1016/j.ejor.2014.01.005
Rabbani, M.; Navazi, F.; Farrokhi-Asl, H.; Balali, M. H. 2018. A sustainable transportation-location-routing problem with soft time windows for distribution systems, Uncertain Supply Chain Management 6(3): 229–254. https://doi.org/10.5267/j.uscm.2017.12.002
Rand, G. K. 1976. Methodological choices in depot location studies, Journal of the Operational Research Society 27(1): 241–249. https://doi.org/10.1057/jors.1976.39
Reghioui, M.; Prins, C.; Labadi, N. 2007. GRASP with path relinking for the capacitated arc routing problem with time windows, Lecture Notes in Computer Science 4448: 722–731. https://doi.org/10.1007/978-3-540-71805-5_78
Riquelme-Rodríguez, J. P.; Gamache, M.; Langevin, A. 2016. Location arc routing problem with inventory constraints, Computers & Operations Research 76: 84–94. https://doi.org/10.1016/j.cor.2016.06.012
Salhi, S.; Rand, G. K. 1989. The effect of ignoring routes when locating depots, European Journal of Operational Research 39(2): 150–156. https://doi.org/10.1016/0377-2217(89)90188-4
Santos, L.; Coutinho-Rodrigues, J.; Current, J. R. 2010. An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological 44(2): 246–266. https://doi.org/10.1016/j.trb.2009.07.004
Schittekat, P.; Sörensen, K. 2009. OR practice – supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem, Operations Research 57(5): 1058–1067. https://doi.org/10.1287/opre.1080.0633
Setak, M.; Azizi, V.; Karimi, H.; Jalili, S. 2017. Pickup and delivery supply chain network with semi soft time windows: metaheuristic approach, International Journal of Management Science and Engineering Management 12(2): 89–95. https://doi.org/10.1080/17509653.2015.1136247
Tagmouti, M.; Gendreau, M.; Potvin, J.-Y. 2007. Arc routing problems with time-dependent service costs, European Journal of Operational Research 181(1): 30–39. https://doi.org/10.1016/j.ejor.2006.06.028
Ulusoy, G. 1985. The fleet size and mix problem for capacitated arc routing, European Journal of Operational Research 22(3): 329–337. https://doi.org/10.1016/0377-2217(85)90252-8
Wang, J.; Deng, W. 2018. Optimizing capacity of signalized road network with reversible lanes, Transport 33(1): 1–11. https://doi.org/10.3846/16484142.2014.994227
Wasner, M.; Zäpfel, G. 2004. An integrated multi-depot hub-location vehicle routing model for network planning of parcel service, International Journal of Production Economics 90(3): 403–419. https://doi.org/10.1016/j.ijpe.2003.12.002
Wøhlk, S. 2008. A decade of capacitated arc routing, Operations Research/Computer Science Interfaces 43: 29–48. https://doi.org/10.1007/978-0-387-77778-8_2
Wøhlk, S. 2005. Contributions to Arc Routing. PhD Dissertation. University of Southern Denmark, Denmark. 269 p.
Zhang, Y.; Mei, Y.; Tang, K.; Jiang, K. 2017. Memetic algorithm with route decomposing for periodic capacitated arc routing problem, Applied Soft Computing 52: 1130–1142. https://doi.org/10.1016/j.asoc.2016.09.017
Aksen, D.; Altinkemer, K. 2008. A location-routing problem for the conversion to the “click-and-mortar” retailing: the static case, European Journal of Operational Research 186(2): 554–575. https://doi.org/10.1016/j.ejor.2007.01.048
Amaya, A.; Langevin, A.; Trépanier, M. 2007. The capacitated arc routing problem with refill points, Operations Research Letters 35(1): 45–53. https://doi.org/10.1016/j.orl.2005.12.009
Arakaki, R. K.; Usberti, F. L. 2018. Hybrid genetic algorithm for the open capacitated arc routing problem, Computers & Operations Research 90: 221–231. https://doi.org/10.1016/j.cor.2017.09.020
Baker, B. M.; Ayechew, M. A. 2003. A genetic algorithm for the vehicle routing problem, Computers & Operations Research 30(5): 787–800. https://doi.org/10.1016/S0305-0548(02)00051-5
Brandão, J.; Eglese, R. 2008. A deterministic tabu search algorithm for the capacitated arc routing problem, Computers & Operations Research 35(4): 1112–1126. https://doi.org/10.1016/j.cor.2006.07.007
Bräysy, O.; Gendreau, M. 2005. Vehicle routing problem with time windows, part II: metaheuristics, Transportation Science 39(1): 119–139. https://doi.org/10.1287/trsc.1030.0057
Chen, L.; Chen, B.; Bui, Q. T.; Hà, M. H. 2017. Designing service sectors for daily maintenance operations in a road network, International Journal of Production Research 55(8): 2251–2265. https://doi.org/10.1080/00207543.2016.1233363
Cheng, C.-B.; Wang, K.-P. 2009. Solving a vehicle routing problem with time windows by a decomposition technique and a genetic algorithm, Expert Systems with Applications 36(4): 7758–7763. https://doi.org/10.1016/j.eswa.2008.09.001
Ciancio, C.; Laganá, D.; Vocaturo, F. 2018. Branch-price-and-cut for the mixed capacitated general routing problem with time windows, European Journal of Operational Research 267(1): 187–199. https://doi.org/10.1016/j.ejor.2017.11.039
Eglese, R. W. 1994. Routeing winter gritting vehicles, Discrete Applied Mathematics 48(3): 231–244. https://doi.org/10.1016/0166-218X(92)00003-5
Farham, M. S.; Süral, H.; Iyigun, C. 2018. A column generation approach for the location-routing problem with time windows, Computers & Operations Research 90: 249–263. https://doi.org/10.1016/j.cor.2017.09.010
Fazayeli, S.; Eydi, A.; Kamalabadi, I. N. 2018. Location-routing problem in multimodal transportation network with time windows and fuzzy demands: presenting a two-part genetic algorithm, Computers & Industrial Engineering 119: 233–246. https://doi.org/10.1016/j.cie.2018.03.041
Fazel Zarandi, M. H.; Hemmati, A.; Davari, S.; Turksen, I. B. 2013. Capacitated location-routing problem with time windows under uncertainty, Knowledge-Based Systems 37: 480–489. https://doi.org/10.1016/j.knosys.2012.09.007
Frederickson, G. N. 1979. Approximation algorithms for some postman problems, Journal of the ACM 26(3): 538–554. https://doi.org/10.1145/322139.322150
Gharavani, M.; Setak, M. 2015. A capacitated location routing problem with semi soft time windows, Advanced Computational Techniques in Electromagnetics 1: 26–40. https://doi.org/10.5899/2015/acte-00197
Ghiani, G.; Laporte, G. 1999. Eulerian location problems, Networks 34(4): 291–302. https://doi.org/10.1002/(SICI)1097-0037(199912)34:4% 3C291::AID-NET9%3E3.0.CO;2-4
Ghiani, G.; Laporte, G. 2001. Location-arc routing problems, OPSEARCH 38(2): 151–159. https://doi.org/10.1007/BF03399222
Golden, B. L.; Wong, R. T. 1981. Capacitated arc routing problems, Networks 11(3): 305–315. https://doi.org/10.1002/net.3230110308
Golden, B. L.; Dearmon, J. S.; Baker, E. K. 1983. Computational experiments with algorithms for a class of routing problems, Computers & Operations Research 10(1): 47–59. https://doi.org/10.1016/0305-0548(83)90026-6
Govindan, K.; Jafarian, A.; Khodaverdi, R.; Devika, K. 2014. Two-echelon multiple-vehicle location–routing problem with time windows for optimization of sustainable supply chain network of perishable food, International Journal of Production Economics 152: 9–28. https://doi.org/10.1016/j.ijpe.2013.12.028
Gündüz, H. I. 2011. The single-stage location-routing problem with time windows, Lecture Notes in Computer Science 6971: 44–58. https://doi.org/10.1007/978-3-642-24264-9_4
Haghani, A.; Qiao, H. 2001. Decision support system for snow emergency vehicle routing: algorithms and application, Transportation Research Record: Journal of the Transportation Research Board 1771: 172–178. https://doi.org/10.3141/1771-22
Hashemi Doulabi, S. H.; Seifi, A. 2013. Lower and upper bounds for location-arc routing problems with vehicle capacity constraints, European Journal of Operational Research 224(1): 189–208. https://doi.org/10.1016/j.ejor.2012.06.015
Hassan, R.; Cohanim, B.; De Weck, O.; Venter, G. 2005. A comparison of particle swarm optimization and the genetic algorithm, in 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, 18–21 April 2005, Austin, Texas, US. https://doi.org/10.2514/6.2005-1897
Hirabayashi, R.; Saruwatari, Y.; Nishida, N. 1992. Tour construction algorithm for the capacitated arc routing problems, Asia-Pacific Journal of Operational Research 9(2): 155–175.
Holland, J. H. 1992. Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. A Bradford Book. 232 p.
Johnson, E. L.; Wøhlk, S. 2009. Solving the Capacitated Arc Routing Problem with Time Windows using Column Generation. Working Paper L-2008-0. Centre for Operations Research Applications in Logistics (CORAL), University of Aarhus, Denmark. 19 p. Available from Internet: https://pure.au.dk/portal/files/3875/L_2008_09.pdf
Levy, L.; Bodin, L. 1989. The arc oriented location routing problem, INFOR: Information Systems and Operational Research 27(1): 74–94. https://doi.org/10.1080/03155986.1989.11732083
Lopes, R. B.; Ferreira, C.; Santos, B. S.; Barreto, S. 2013. A taxonomical analysis, current methods and objectives on location‐routing problems, International Transactions in Operational Research 20(6): 795–822. https://doi.org/10.1111/itor.12032
Lopes, R. B.; Plastria, F.; Ferreira, C.; Santos, B. S. 2014. Location-arc routing problem: Heuristic approaches and test instances, Computers & Operations Research 43: 309–317. https://doi.org/10.1016/j.cor.2013.10.003
Mullaseril, P. A. 1997. Capacitated Rural Postman Problem with Time Windows and Split Delivery. PhD Dissertation. University of Arizona, Tucson, US. 160 p. Available from Internet: https://repository.arizona.edu/handle/10150/282300
Muyldermans, L.; Pang, G. 2010. A guided local search procedure for the multi-compartment capacitated arc routing problem, Computers & Operations Research 37(9): 1662–1673. https://doi.org/10.1016/j.cor.2009.12.014
Nagy, G.; Salhi, S. 2007. Location-routing: Issues, models and methods, European Journal of Operational Research 177(2): 649–672. https://doi.org/10.1016/j.ejor.2006.04.004
Nikbakhsh, E.; Zegordi, S. 2010. A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints, Scientia Iranica 17(1): 36–47.
Prodhon, C.; Prins, C. 2014. A survey of recent research on location-routing problems, European Journal of Operational Research 238(1): 1–17. https://doi.org/10.1016/j.ejor.2014.01.005
Rabbani, M.; Navazi, F.; Farrokhi-Asl, H.; Balali, M. H. 2018. A sustainable transportation-location-routing problem with soft time windows for distribution systems, Uncertain Supply Chain Management 6(3): 229–254. https://doi.org/10.5267/j.uscm.2017.12.002
Rand, G. K. 1976. Methodological choices in depot location studies, Journal of the Operational Research Society 27(1): 241–249. https://doi.org/10.1057/jors.1976.39
Reghioui, M.; Prins, C.; Labadi, N. 2007. GRASP with path relinking for the capacitated arc routing problem with time windows, Lecture Notes in Computer Science 4448: 722–731. https://doi.org/10.1007/978-3-540-71805-5_78
Riquelme-Rodríguez, J. P.; Gamache, M.; Langevin, A. 2016. Location arc routing problem with inventory constraints, Computers & Operations Research 76: 84–94. https://doi.org/10.1016/j.cor.2016.06.012
Salhi, S.; Rand, G. K. 1989. The effect of ignoring routes when locating depots, European Journal of Operational Research 39(2): 150–156. https://doi.org/10.1016/0377-2217(89)90188-4
Santos, L.; Coutinho-Rodrigues, J.; Current, J. R. 2010. An improved ant colony optimization based algorithm for the capacitated arc routing problem, Transportation Research Part B: Methodological 44(2): 246–266. https://doi.org/10.1016/j.trb.2009.07.004
Schittekat, P.; Sörensen, K. 2009. OR practice – supporting 3PL decisions in the automotive industry by generating diverse solutions to a large-scale location-routing problem, Operations Research 57(5): 1058–1067. https://doi.org/10.1287/opre.1080.0633
Setak, M.; Azizi, V.; Karimi, H.; Jalili, S. 2017. Pickup and delivery supply chain network with semi soft time windows: metaheuristic approach, International Journal of Management Science and Engineering Management 12(2): 89–95. https://doi.org/10.1080/17509653.2015.1136247
Tagmouti, M.; Gendreau, M.; Potvin, J.-Y. 2007. Arc routing problems with time-dependent service costs, European Journal of Operational Research 181(1): 30–39. https://doi.org/10.1016/j.ejor.2006.06.028
Ulusoy, G. 1985. The fleet size and mix problem for capacitated arc routing, European Journal of Operational Research 22(3): 329–337. https://doi.org/10.1016/0377-2217(85)90252-8
Wang, J.; Deng, W. 2018. Optimizing capacity of signalized road network with reversible lanes, Transport 33(1): 1–11. https://doi.org/10.3846/16484142.2014.994227
Wasner, M.; Zäpfel, G. 2004. An integrated multi-depot hub-location vehicle routing model for network planning of parcel service, International Journal of Production Economics 90(3): 403–419. https://doi.org/10.1016/j.ijpe.2003.12.002
Wøhlk, S. 2008. A decade of capacitated arc routing, Operations Research/Computer Science Interfaces 43: 29–48. https://doi.org/10.1007/978-0-387-77778-8_2
Wøhlk, S. 2005. Contributions to Arc Routing. PhD Dissertation. University of Southern Denmark, Denmark. 269 p.
Zhang, Y.; Mei, Y.; Tang, K.; Jiang, K. 2017. Memetic algorithm with route decomposing for periodic capacitated arc routing problem, Applied Soft Computing 52: 1130–1142. https://doi.org/10.1016/j.asoc.2016.09.017