A robust optimization approach for a multi-period location-arc routing problem with time windows: A case study of a bank

Document Type : Research Paper

Authors

1 Department of Industrial Engineering, College of Engineering, University of Payame Noor, Tehran, Iran

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

3 School of Industrial Engineering, College of Engineering, University of Tehran, P.O. Box: 11155-4563, Tehran, Iran

Abstract

A Location-Arc Routing Problem (LARP) is a practical problem, while a few mathematical programming models have been considered for this problem. In this paper, a mixed non-linear programming model is presented for a multi-period LARP with the time windows under demand uncertainty. The time windows modeling in the arc routing problem is rarely. To the best our knowledge, it is the first time that the robust LARP model is verified and an optimal solution is presented for it. For this purpose, the CPLEX solver is used for solving the treasury location problems of a bank as a case study. These problems are node-based with close nods and can be transformed into arc-based. Therefore, the method LRP and LARP models can be used to solve these problems. The comparing results of the LRP and LARP models prove that the LARP has a better performance regarding timing and optimal solution. Furthermore, comparing the results of deterministic and robust LARP models for this case study shows the validity of the robust optimization approach.

Keywords

[1] G. Laporte, S. Nickel, and F.S. da Gama, Location science, Springer, 2015.
[2] R.B. Lopes, F. Plastriab, C., Ferreiraa, Location-arc routing problem: Heuristic approaches and test instances, Comp. and Oper. Res., 43 (2014) 309–317.
[3] B.L. Golden, and R.T. Wong, Capacitated arc routing problems, Networks, 11(3) 1981 305–315.
[4] Ghiani, G., et al., A branch-and-cut algorithm for the undirected capacitated arc routing problem, 2007.
[5] S. Huber, Strategic decision support for the bi-objective location-arc routing problem, in Proceedings of the 2016 49th Hawaii International Conference on System Sciences (HICSS), IEEE Computer Society, 2016.
[6] C. Çetinkaya, I. Karaoglan, and H. Gökçen, Two-stage vehicle routing problem with arc time windows: A mixed integer programming formulation and a heuristic approach, Euro. J. of Oper. Res., 230(3) 2013 539–550.
[7] R. Macedo, C. Alves, J.M. Carvalho, F. Clautiaux, S. Hanafi, Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model, Euro. J. of Oper. Res., 214(3) 2011 536– 545.
[8] L. Lystlund, and S. Wøhlk, The service-time restricted capacitated arc routing problem, 2012.
[9] Bertsimas, D. and M. Sim, The price of robustness, Oper. Res., 52(1) 2004 35–53.
[10] G. Fleury, L. Philippe, C. Prins, Stochastic capacitated arc routing problem, Document de travail interne, Article en cours de rédaction, 2005.
[11] G. Fleury, L. Philippe, C. Prins, Improving robustness of solutions to arc routing problems, J. of the Oper. Res.Soc., 56(5) 2005 526–538.
[12] Y. Mei, K. Tang, X. Yao, Capacitated arc routing problem in uncertain environments, in Evolutionary Computation (CEC), 2010 IEEE Congress on, IEEE, 2010.
[13] C. Archetti, A. Corberán, I. Plana, J.M. Sanchis, M. GraziaSperanza, A branch-and-cut algorithm for the Orienteering Arc Routing Problem, Comput. and Oper. Res., 66 2016 95–104.
[14] G. Ghiani, G. Laporte, Eulerian location problems. Networks, 34(4) 1999 291-302.
[15] A.N. Letchford, A. Oukil, Exploiting sparsity in pricing routines for the capacitated arc routing problem, Comput. and Oper. Res., 36(7) 2009 2320–2327.
[16] J. Lysgaard, A.N. Letchford, R.W. Eglese, A new branch-and-cut algorithm for the capacitated vehicle routing problem, Math.Prog., 100(2) 2004 423–445.
[17] R. Martinelli, et al. A branch-cut-and-price algorithm for the capacitated arc routing problem, in International Symposium on Experimental Algorithms, Springer, 2011.
[18] M. Monroy-Licht, et al., The rescheduling arc routing problem, International Trans.in Oper. Res., 24(6) 2017 1325–1346.
[19] E. Benavent, The capacitated arc routing problem, A heuristic algorithm, 1990.
[20] J.M. Belenguer, E. Benavent, The capacitated arc routing problem: Valid inequalities and facets, Comput. Opti. and Appl. 10(2) 1998 165–187.
[21] S.K. Amponsah, S. Salhi, The investigation of a class of capacitated arc routing problems: the collection of garbage in developing countries, Waste manag., 24(7) 2004 711–721.
[22] M.C. Mourão, A.C. Nunes, and C. Prins, Heuristic methods for the sectoring arc routing problem, Euro. J. of Oper. Res., 196(3) 2009 856–868.[23] L. Gouveia, M.C. Mourão, and L.S. Pinto, Lower bounds for the mixed capacitated arc routing problem, Comp. and Oper. Res., 37(4) 2010 692–699.
[24] G. Kirlik, and A. Sipahioglu, Capacitated arc routing problem with deadheading demands, Comp. and Oper. Res., 39(10) 2012 2380–2394.
[25] L. Bach, G. Hasle, and S. Wøhlk, A lower bound for the node, edge, and arc routing problem, Comp.and Oper. Res., 40(4) 2013 943–952.
[26] F.L. Usberti, P.M. França, and A.L.M. França, The open capacitated arc routing problem, Comp. and Oper. Res., 38(11) 2011 1543–1555.
[27] R. Martinelli, M. Poggi, and A. Subramanian, Improved bounds for large scale capacitated arc routing problem, Comp. and Oper. Res., 40(8) 2013 2145–2160.
[28] S. Irnich, and D. Villeneuve, The shortest-path problem with resource constraints and k-cycle elimination for k ≥ 3, INF. J. on Comput., 18(3) 2006 391–406.
[29] C. Bode and S. Irnich, Cut-first branch-and-price-second for the capacitated arc-routing problem, Oper. Res., 60(5) 2012 1167–1182.
[30] H. Ding, J. Li and K.W. Lih, Approximation algorithms for solving the constrained arc routing problem in mixed graphs, Euro. J. of Oper. Res., 239(1) 2014 80–88.
[31] C. Archetti, Á. Corberán, I. Plana, J. MariaSanchis and M. GraziaSperanza, A matheuristic for the team orienteering arc routing problem, Euro. J. of Oper. Res., 245(2) 2015 392–401.
[32] M. Constantino, M. Constantino, L. Gouveia, M. CândidaMourão, A. CatarinaNune, The mixed capacitated arc routing problem with non-overlapping routes, Euro. J. of Oper. Res., 244(2) 2015 445-456.
[33] D. Krushinsky, and T. Van Woensel, An approach to the asymmetric multi-depot capacitated arc routing problem, Euro. J. of Oper. Res., 244(1) 2015 100–109.
[34] L. Xing et al., An evolutionary approach to the multidepot capacitated arc routing problem, IEEE Trans. on Evolu. Comput., 14(3) 2010 356–374.
[35] Y. Chen, J.K. Hao, and F. Glover, A hybrid metaheuristic approach for the capacitated arc routing problem, Euro. J. of Oper. Res., 253(1) 2016 25–39.
[36] P. Lacomme, C. Prins, and W. Ramdane-Cherif, Competitive memetic algorithms for arc routing problems, Ann. of Oper. Res., 131(1-4) 2004 159–185.
[37] T. Liu et al., Combined location-arc routing problems: a survey and suggestions for future research, in Service Oper. and Logistics, and Informatics, IEEE, 2008.
[38] C. Martinez, et al., BRKGA algorithm for the capacitated arc routing problem, Elec. Notes in Theor. Comp. Sci., 281 (2011) 69–83.
[39] L. Santos, J. Coutinho-Rodrigues, and J.R. Current, An improved ant colony optimization based algorithm for the capacitated arc routing problem, Trans. Res. Part B: Methodological, 44(2) 2010 246–266.
[40] Z. Wang, H. Jin, and M. Tian, Rank-based memetic algorithm for capacitated arc routing problems, Appl. Soft Computing, 37 (2015) 572–584.
[41] H. Xu, et al., An improved evolutionary approach to the extended capacitated arc routing problem, Expert Systems with Applications, 38(4) 2011 4637–4641.
[42] Y. Mei, K. Tang, and X. Yao, Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem, IEEE Trans. on Evolu. Comput., 15(2) 2011 151–165.
[43] L. Grandinetti, et al., An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem, Comput. and Oper. Res., 39(10) 2012 2300–2309.
[44] R. Shang, et al., A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing
problem, Information Sciences, 277 2014 609–642.
[45] J. de Armas, et al., Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics, Annals of Oper. Res., (2018) 1–28.
[46] R. Shang, et al., Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems, Natural Computing, (2017) 1–17.
[47] D. Black, R. Eglese, and S. Wøhlk, The time-dependent prize-collecting arc routing problem, Comput. and Oper. Res., 40(2) 2013 526–535.
[48] N. Labadi, C. Prins, and M. Reghioui, GRASP with path relinking for the capacitated arc routing problem with time windows, Advances in comput. intell. in trans., log., and supply chain manag., (2008) 111–135.
[49] P. Vansteenwegen, W. Souffriau, and K. Sörensen, Solving the mobile mapping van problem: A hybrid metaheuristic for capacitated arc routing with soft time windows, Comput. and Oper. Res., 37(11) 2010 1870–1876.
[50] F. Chu, N. Labadi, and C. Prins, Heuristics for the periodic capacitated arc routing problem, J. of Intell. Manuf., 16(2) 2005 243–251.[51] F. Chu, N. Labadi, and C. Prins, A scatter search for the periodic capacitated arc routing problem, Euro. J. of Oper. Res., 169(2) 2006 586–605.
[52] P. Lacomme, C. Prins, and W. Ramdane-Chérif, Evolutionary algorithms for multiperiod arc routing problems, in Proc. of the 9th Int. Conf. on Inf. Process. and Manag. of Uncert. in Knowl.-Based syst. (IPMU 2002), 2002.
[53] P. Lacomme, C. Prins, and W. Ramdane-Chérif, Evolutionary algorithms for periodic arc routing problems, Euro. J. of Oper. Res., 165(2) 2005 535–553.
[54] F.L. Usberti, P.M. França, and A.L.M. França, GRASP with evolutionary path-relinking for the capacitated arc routing problem, Comput. and Oper. Res., 40(12): p. 3206–3217, 2013.
[55] R.Y. Fung, R. Liu, and Z. Jiang, A memetic algorithm for the open capacitated arc routing problem, Transportation Res. Part E: Log. and Trans. Review, 50 2013 53–67.
[56] R.K. Arakaki, and F.L. Usberti, Hybrid genetic algorithm for the open capacitated arc routing problem, Comput. and Oper. Res., 90 2018 221–231.
[57] S. Eskandarzadeh, R. Tavakkoli-Moghaddam, and A. Azaron, An extension of the relaxation algorithm for solving a special case of capacitated arc routing problems, J. of comb. opti., 17(2) 2009 214–234.
[58] L. Muyldermans, and G. Pang, A guided local search procedure for the multi-compartment capacitated arc routing problem, Comput. and Oper. Res., 37(9) 2010 1662–1673.
[59] E.E. Zachariadis and C.T. Kiranoudis, Local search for the undirected capacitated arc routing problem with profits,Euro. J. of Oper. Res., 210(2) 2011 358–367.
[60] C. Archetti, et al., The undirected capacitated arc routing problem with profits, Comput. and Oper. Res., 37(11) 2010 1860–1869.
[61] A. Amaya, A. Langevin, and M. TréPanier, The capacitated arc routing problem with refill points, Oper. Res.Lett., 35(1) 2007 45–53.
[62] G. Ghiani, G. Improta, and G. Laporte, The capacitated arc routing problem with intermediate facilities, Networks, 37(3) 2001 134–143.
[63] E.J. Willemse and J.W. Joubert, Constructive heuristics for the mixed capacity arc routing problem under time restrictions with intermediate facilities, Comput. and Oper. Res., 68 2016 30–62.
[64] M. Polacek, et al., A variable neighborhood search for the capacitated arc routing problem with intermediate facilities, J. of Heuri., 14(5) 2008 405–423.
[65] K. Ehlers, A Time Buffered Arc Routing Problem, University of Missouri Columbia, 2015.
[66] M. Tagmouti, M. Gendreau, and J.-Y. Potvin, Arc routing problems with time-dependent service costs, Euro. J. of Oper. Res., 181(1) 2007 30–39.
[67] M. Tagmouti, M. Gendreau, and J.-Y. Potvin, A Variable Neighborhood Descent for Arc Routing Problems with Time-dependent Service Costs, CIRRELT, 2008.
[68] A. Pia, and C. Filippi, A variable neighborhood descent algorithm for a real waste collection problem with mobile depots, International Transactions in Oper. Res., 13(2) 2006 125–141.
[69] A. Hertz, and M. Mittaz, A variable neighborhood descent algorithm for the undirected capacitated arc routing problem, Trans. sci., 35(4) 2001 425–434.
[70] F.Y. Vincent, and S.W. Lin, Iterated greedy heuristic for the time-dependent prize-collecting arc routing problem, Comput. and Indust. Engin., 90 (2015) 54–66.
[71] S. Lannez, et al, Column generation heuristic for a rich arc routing problem, in 10th Workshop on Alg. Appr. for Trans. Modell., Optim., and Syst. (ATMOS’10), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010.
[72] M. Liu, H.K. Singh, and T. Ray, Application specific instance generator and a memetic algorithm for capacitated arc routing problems, Trans. Res. Part C: Emerging Technologies, 43 2014 249–266.
[73] S.H.H. Doulabi, and A. Seifi, Lower and upper bounds for location-arc routing problems with vehicle capacity constraints, Euro. J. of Oper. Res., 224(1) 2013 189–208.
[74] L. Levy, and L. Bodin, The arc oriented location routing problem, INFOR: Inf. Systems and Oper. Res., 27(1) 1989 74-94.
[75] G. Ghiani, and G. Laporte, Location-arc routing problems, Opsearch, 38(2) 2001 151–159.
[76] Essink, E. and A. Wagelmans, A comparison of 3 metaheuristics for the location-arc routing problem, 2015.
[77] Riquelme-Rodríguez, J.-P., M. Gamache, and A. Langevin, Location arc routing problem with inventory constraints, Comput. and Oper. Res., 76 (2016) 84–94.
[78] A. Amini, R. Tavakkoli-Moghaddam, and S. Ebrahimnejad, Scenario-Based Location Arc Routing Problems: Introducing Mathematical Models, in International Conference on Management Science and Engineering Management, Springer, (2017) 511–521.
[79] R. Tavakkoli-Moghaddam, A. Amini, and S. Ebrahimnejad, A new mathematical model for a multi-product location-arc routing problem, in Optim. and Appl. (ICOA), 4th International Conference on, IEEE, 2018.
Volume 12, Issue 1
May 2021
Pages 157-173
  • Receive Date: 03 November 2018
  • Revise Date: 25 May 2019
  • Accept Date: 04 July 2019
  • First Publish Date: 17 December 2020