Share:


A mathematical model for the capacitated location-arc routing problem with deadlines and heterogeneous fleet

    Soheila Mirzaei-Khafri Affiliation
    ; Mahdi Bashiri Affiliation
    ; Roya Soltani Affiliation
    ; Mohammad Khalilzadeh Affiliation

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
Published in Issue
Dec 23, 2019
Abstract Views
1682
PDF Downloads
806
Creative Commons License

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