International Journal of Nonlinear Analysis and Applications

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., Ferreira, 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] G. Ghiani, D. Laganà, G. Laporte, and R. Musmanno, A branch-and-cut algorithm for the undirected capacitated arc routing problem, GERAD,, 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. 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. 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, and C. Prins, Improving robustness of solutions to arc routing problems, J. Oper. Res. Soc. 56(5) (2005) 526–538.
[12] Y. Mei, K. Tang, and X. Yao, Capacitated arc routing problem in uncertain environments, in Evolutionary Computation (CEC), IEEE Congress on IEEE, 2010.
[13] C. Archetti, A. Corberán, I. Plana, J.M. Sanchis, and M. Grazia Speranza, A branch-and-cut algorithm for the Orienteering Arc Routing Problem, Comput. and Oper. Res. 66 (2016) 95–104.
[14] G. Ghiani and G. Laporte, Eulerian location problems. Networks 34(4) (1999) 291-302.
[15] A.N. Letchford and A. Oukil, Exploiting sparsity in pricing routines for the capacitated arc routing problem, Comput. Oper. Res. 36(7) (2009) 2320–2327.
[16] J. Lysgaard, A.N. Letchford, and 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, D. Pecin, M. Poggi, and H. Longo, A branch-cut-and-price algorithm for the capacitated arc routing problem, International Symposium on Experimental Algorithms, Springer, 2011.
[18] M. Monroy‐Licht, C.A. Amaya, A. Langevin, and  L.M. Rousseau, The rescheduling arc routing problem, International Trans. Oper. Res. 24(6) (2017) 1325–1346.
[19] E. Benavent, V. Campos, A. Corberán, and E. Mota,  The capacitated arc routing problem, A heuristic algorithm, Qüestiió 14(1-3). (1990) 107-122.
[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 and 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. Oper. Res. 37(4) (2010) 692–699.
[24] G. Kirlik, and A. Sipahioglu, Capacitated arc routing problem with deadheading demands, Comp. 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. 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. 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. 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. 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. 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. 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, P. Rohlfshagen, Y. Chen,  and X. Yao, An evolutionary approach to the multidepot capacitated arc routing problem, IEEE Trans. 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. Oper. Res. 253(1) (2016) 25–39.
[36] P. Lacomme, C. Prins, and W. Ramdane-Cherif, Competitive memetic algorithms for arc routing problems, Ann. Oper. Res. 131(1-4) (2004) 159–185.
[37] T. Liu, Z. Jiang, F. Chen, R. Liu, and S. Liu, Combined location-arc routing problems: a survey and suggestions for future research, International Conference on Service Operations and Logistics, and Informatics. Vol. 2. IEEE, 2008.
[38] C. Martinez, I. Loiseau, M.G.C. Resende, and S. Rodriguez, BRKGA algorithm for the capacitated arc routing problem, Elec. Notes 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 Comput. 37 (2015) 572–584.
[41] H. Xu, C.H. Zhang, Y.A. Tan, and J. Lu, An improved evolutionary approach to the extended capacitated arc routing problem, Expert Systems with Appl. 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, F. Guerriero, D. Laganà, and O. Pisacane, An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem, Comput. Oper. Res. 39(10) (2012) 2300–2309.
[44] R. Shang, Y. Wang, J. Wang, L Jiao, S. Wang, and L. Qi, A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem, Information Sci. 277 (2014) 609–642.
[45] J. de Armas, P. Keenan, A.A. Juan, S. McGarraghy, Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics, Annals of Oper. Res. 273 (2019) 135–162.
[46] R. Shang, B. Du, K. Dai, L. Jiao, and Y. Xue, Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems, Natural Computing 17 (2018) 375–391.
[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 Comput. Intell. 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. Oper. Res. 37(11) (2010) 1870–1876.
[50] F. Chu, N. Labadi, and C. Prins, Heuristics for the periodic capacitated arc routing problem, J. 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. Oper. Res. 169(2) (2006) 586–605.
[52] P. Lacomme, C. Prins, and W. Ramdane-Chérif, Evolutionary algorithms for multiperiod arc routing problems, Proc. 9th Int. Conf. Inf. Process. Manag. Uncert. 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. 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. Oper. Res. 40(12) (2013) 3206–3217.
[55] R.Y. Fung, R. Liu, and Z. Jiang, A memetic algorithm for the open capacitated arc routing problem, Transportation Res. Part E: Log. Trans. Rev. 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. Comb. Optim. 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] Archetti, D. Feillet, A. Hertz, M.G. Speranza, 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, K.F. Doerner, R.F. Hartl, and V. Maniezzo, 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.  Indust. Engin. 90 (2015) 54–66.
[71] S. Lannez, C. Artigues, J. Damay, and M. Gendreau, Column generation heuristic for a rich arc routing problem, in 10th Workshop on Alg. Appr. for Trans. Modell., Optim., 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. 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, Oper. Res. 38(2) (2001) 151–159.
[76] Essink, E. and A. Wagelmans, A comparison of 3 metaheuristics for the location-arc routing problem, Eramus University Rotterdam, 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, pp. 511–521.
[79] R. Tavakkoli-Moghaddam, A. Amini, and S. Ebrahimnejad, A new mathematical model for a multi-product location-arc routing problem, Optim. Appl. (ICOA), 4th International Conference on, IEEE, 2018.
International Journal of Nonlinear Analysis and Applications
Volume 12, Issue 1
May 2021
Pages 157-173
  • Receive Date: 03 November 2018
  • Revise Date: 25 May 2019
  • Accept Date: 04 July 2019