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


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

This work is licensed under a Creative Commons Attribution 4.0 International License.


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.

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.

Amaya, A.; Langevin, A.; Trépanier, M. 2007. The capacitated arc routing problem with refill points, Operations Research Letters 35(1): 45–53.

Arakaki, R. K.; Usberti, F. L. 2018. Hybrid genetic algorithm for the open capacitated arc routing problem, Computers & Operations Research 90: 221–231.

Baker, B. M.; Ayechew, M. A. 2003. A genetic algorithm for the vehicle routing problem, Computers & Operations Research 30(5): 787–800.

Brandão, J.; Eglese, R. 2008. A deterministic tabu search algorithm for the capacitated arc routing problem, Computers & Operations Research 35(4): 1112–1126.

Bräysy, O.; Gendreau, M. 2005. Vehicle routing problem with time windows, part II: metaheuristics, Transportation Science 39(1): 119–139.

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.

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.

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.

Eglese, R. W. 1994. Routeing winter gritting vehicles, Discrete Applied Mathematics 48(3): 231–244.

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.

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.

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.

Frederickson, G. N. 1979. Approximation algorithms for some postman problems, Journal of the ACM 26(3): 538–554.

Gharavani, M.; Setak, M. 2015. A capacitated location routing problem with semi soft time windows, Advanced Computational Techniques in Electromagnetics 1: 26–40.

Ghiani, G.; Laporte, G. 1999. Eulerian location problems, Networks 34(4): 291–302. 3C291::AID-NET9%3E3.0.CO;2-4

Ghiani, G.; Laporte, G. 2001. Location-arc routing problems, OPSEARCH 38(2): 151–159.

Golden, B. L.; Wong, R. T. 1981. Capacitated arc routing problems, Networks 11(3): 305–315.

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.

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.

Gündüz, H. I. 2011. The single-stage location-routing problem with time windows, Lecture Notes in Computer Science 6971: 44–58.

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.

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.

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.

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:

Levy, L.; Bodin, L. 1989. The arc oriented location routing problem, INFOR: Information Systems and Operational Research 27(1): 74–94.

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.

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.

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:

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.

Nagy, G.; Salhi, S. 2007. Location-routing: Issues, models and methods, European Journal of Operational Research 177(2): 649–672.

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.

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.

Rand, G. K. 1976. Methodological choices in depot location studies, Journal of the Operational Research Society 27(1): 241–249.

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.

Riquelme-Rodríguez, J. P.; Gamache, M.; Langevin, A. 2016. Location arc routing problem with inventory constraints, Computers & Operations Research 76: 84–94.

Salhi, S.; Rand, G. K. 1989. The effect of ignoring routes when locating depots, European Journal of Operational Research 39(2): 150–156.

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.

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.

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.

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.

Ulusoy, G. 1985. The fleet size and mix problem for capacitated arc routing, European Journal of Operational Research 22(3): 329–337.

Wang, J.; Deng, W. 2018. Optimizing capacity of signalized road network with reversible lanes, Transport 33(1): 1–11.

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.

Wøhlk, S. 2008. A decade of capacitated arc routing, Operations Research/Computer Science Interfaces 43: 29–48.

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.