Robust Bi-Objective Location-Arc Routing Problem with Time Windows: A Case Study of an Iranian Bank

Document Type : Research Paper


1 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 School of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


In Location-Arc Routing Problems (LARP), unlike the well-known locating-routing problems, demand is on the arc and using deadheading arcs is permitted. Few studies have focused on an arc-routing problem. In this research, a complex bi-objective linear mathematical model for the LARP with time windows under uncertainty is presented. Time windows in the arc-routing problem modeling have complexity since the required arc with time windows becomes a deadheading arc without time windows after service. Furthermore, modeling of the vehicle servicing to multiple required arc with the minimum deadheading arc in route is a feature of this work. The proposed LARP is used for modeling of transforming cash in the bank case study. In this case study, demand has uncertainty with unknown probability distributions and the Bertsimas and Sim’s approach is used for it. The case study problem is a node-basing problem with the closest node and time windows for servicing branches. For this purpose, the Multi-Objective Dragonfly Algorithm (MODA) and Non-dominated Sorting Genetic Algorithm (NSGA-II) are used for locating the cash supply centers of a bank in Tehran. Furthermore, comparing results of robust and deterministic LARP models show that the mean and standard deviation of objective function values in the robust model has better performance in realization.


Albareda-Sambola M. (2015). Location-routing and location-arc routing. Location science, Springer, Cham.
Amini A., Tavakkoli-Moghaddam R. and Ebrahimnejad S. (2017). Scenario-Based Location Arc Routing Problems: Introducing Mathematical Models. In International Conference on Management Science and Engineering Management (pp. 511-521). Springer, Cham.
Amini A., Tavakkoli-Moghaddam R. and Ebrahimnejad S. (2019). A bi-objective transportation-location arc routing problem, Transportation Letters, Vol. 12, pp. 623-637.
Armas J., Ferrer A., Juan A.A. and Lalla-Ruiz E. (2018). Modeling and solving the non-smooth arc routing problem with realistic soft constraints. Expert systems with applications, Vol. 98, pp.205-220.
Babaee Tirkolaee, E., Goli A.R. Pahlevan M. and Malekalipour Kordestanizadeh R. (2019). A robust bi-objective multi-trip periodic capacitated arc routing problem for urban waste collection using a multi-objective invasive weed optimization. Waste Management & Research, Vol. 37, No. 11, pp. 1089-1101.
Babaee Tirkolaee E., Mahdavi I. and Seyyed Esfahani M.M. (2018). A robust periodic capacitated arc routing problem for urban waste collection considering drivers and crew’s working time. Waste Management, Vol. 76, pp.138-146.
Babaee Tirkolaee E., Mahdavi I., Seyyed Esfahani M.M. and Weber G.W. (2020). A hybrid augmented ant colony optimization for the multi-trip capacitated arc routing problem under fuzzy demands for urban solid waste management. Waste Management & Research, Vol. 38, No. 2, pp. 156-172.
Ben-Tal A. and Nemirovski A. (1998). Robust convex optimization. Mathematics of operations research, Vol.  23, No. 4, pp. 769-805.
Bertsimas D. and Sim M. (2004). The price of robustness. Operations research, Vol. 52, No. 1, pp. 35-53.
Black D., Eglese R. and Wøhlk S. (2013). The time-dependent prize-collecting arc routing problem. Computers & Operations Research, Vol. 40, No. 2, pp. 526-535.
Çetinkaya C., Gökçen H. and Karaoğlan İ. (2018). The location routing problem with arc time windows for terror regions: a mixed integer formulation. Journal of Industrial and Production Engineering, p. 1-10.
Çetinkaya C., Karaoglan I. and Gökçen H. (2013). Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach. European Journal of Operational Research, Vol. 230, No. 3, pp. 539-550.
Collette Y., Siarry P. (2003). Multi-objective optimization: principles and case studies, New York: Springer.
Deb K., Pratap A., Agarwal, S. and Meyarivan T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on evolutionary computation, Vol. 6, No.  2, pp. 182-197.
Doulabi S.H.H. and Seifi A. (2013). Lower and upper bounds for location-arc routing problems with vehicle capacity constraints. European Journal of Operational Research, Vol. 224, No. 1, pp. 189-208.
Essink E. and Wagelmans A. (2015). A comparison of 3 metaheuristics for the location-arc routing problem. DOI: 10.13140/RG.2.1.2781.0649.
Fernández E. Laporte G. and Rodríguez-Pereira J. (2019). Exact Solution of Several Families of Location-Arc Routing Problems. transportation science Articles in Advance, Vol. 53, No. 5, pp.1313-1333.
Fazli-Khalaf M., Fathollahzadeh K., Mollaei A., Naderi B. and Mohammadi M. (2019). A robust possibilistic programming model for water allocation problem. RAIRO-Operations Research, Vol. 53, No. 1, pp.323-338.
Fazli-Khalaf M. and Hamidieh A. (2017). A robust reliable forward-reverse supply chain network design model under parameter and disruption uncertainties. International Journal of Engineering-Transactions B: Applications, Vol. 30, No. 8, pp.1160-1169.
Ghiani G., Improta G. and Laporte G. (2001). The capacitated arc routing problem with intermediate facilities. Networks, Vol. 37, No. 3, pp. 134-143. Golden B.L. and Wong R. T. (1981). Capacitated arc routing problems. Networks, Vol. 11, No. 3, pp. 305-315.
Hamidieh A., Arshadikhamseh A. and Fazli-Khalaf M. (2018). A robust reliable closed loop supply chain network design under uncertainty: A case study in equipment training centers. International Journal of Engineering-Transactions A: Basics, Vol. 31, No. 4, pp.648-658.
Huber S. (2016). Strategic decision support for the bi-objective location-arc routing problem. Paper presented at the Proceedings of the 2016 49th Hawaii International Conference on System Sciences (HICSS).
Javanmardi A. and Hafezalkotob A. (2018). Presenting a multi-objective locating-routing-arc model with collaborative approach (A food distribution case study). Journal of Industrial and Systems Engineering, Vol. 11, special issue on game theory applications, pp. 144-163.
kahfi A., seyedhosseini S.M. and Tavakkoli-Moghaddam R. (2020). A robust optimization approach for a multi-period location-arc routing problem with time windows: a case study of a bank. International Journal of Non-linear Analysis and Applications, Accepted for publication.
Khajepour A., Sheikhmohammady M. and Nikbakhsh E. (2020). Field path planning using capacitated arc routing problem. Computers and Electronics in Agriculture, Vol. 173, No. 105401, pp. 1-10.
Kirlik G. and Sipahioglu A. (2012). Capacitated arc routing problem with deadheading demands. Computers & Operations Research, Vol. 39, No.  10, pp. 2380-2394.
Lacomme P., Prins C. and Ramdane-Cherif W. (2004). Competitive memetic algorithms for arc routing problems. Annals of Operations Research, Vol. 131, No.  1-4, pp. 159-185.
Laporte G., Nickel S., and da Gama F. S. (2015). Location science. Springer , Cham.
Levy L., and Bodin L. (1989). The arc oriented location routing problem. INFOR: Information Systems and Operational Research, Vol. 27, No.1, 74-94.
Liu M., Singh H.K. and Ray T. (2014). Application specific instance generator and a memetic algorithm for capacitated arc routing problems. Transportation Research Part C: Emerging Technologies, Vol. 43, pp. 249-266.
Lopes R.B., Plastria F., Ferreira C. and Santos B.S. (2014). Location-arc routing problem: Heuristic approaches and test instances. Computers & Operations Research, Vol. 43, pp. 309-317.
Lystlund L. and Wøhlk S. (2012), The service-time restricted capacitated arc routing problem. Working paper.
Macedo R., Alves C., de Carvalho J.V., Clautiaux F. and Hanafi S. (2011). Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. European Journal of Operational Research, Vol. 214, No. 3, pp. 536-545.
Mirjalili S. (2016). Dragonfly algorithm: a new meta-heuristic optimization technique for solving single-objective, discrete, and multi-objective problems. Neural Computing and Applications,  Vol. 27, No. 4, p. 1053-1073.
Mirzaei-Khafri S., Bashiri M., Soltani R. and Khalilzadeh M. (2019). A Mathematical Model For The Capacitated Location-Arc Routing Problem With Deadlines And Heterogeneous Fleet. Transport, Vol. 34, No. 6, pp. 692–707.
Mirzaei-Khafri S., Bashiri M., Soltani R. and Khalilzadeh M., (2020). A robust optimization model for a location-arc routing problem with demand uncertainty, International Journal of Industrial Engineering: Theory, Applications and Practic, Vol. 27, No. (2).
Pavlis N.E., Moschuris S.J. and Laios L.G. (2018). Supply management performance and cash conversion cycle. International Journal of Supply and Operations Management, Vol. 5, No. 2, pp.107-121.
Riquelme-Rodríguez J.P., Gamache, M. and Langevin A. (2016). Location arc routing problem with inventory constraints. Computers & Operations Research, Vol. 76, pp. 84-94.
Soyster A.L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations research,  Vol. 21, No. 5, pp. 1154-1157.
Tavakkoli-Moghaddam R., Amini A., Ebrahimnejad S. (2018). A new mathematical model for a multi-product location-arc routing problem. in: Optimization and Applications (ICOA), 2018 4th International Conference on, IEEE.
Teimoori S., Khademi Zare H. and Fallah Nezhad M.S. (2014). Location-routing problem with fuzzy time windows and traffic time. International Journal of Supply and Operations Management, Vol. 1, No. 1, pp.38-53.
Vansteenwegen P., Souffriau W. and Sörensen K. (2010). Solving the mobile mapping van problem: A hybrid metaheuristic for capacitated arc routing with soft time windows. Computers & operations research, Vol. 37, No. 11, pp. 1870-1876.