General variable neighborhood search for the capacitated single allocation hub maximal covering problem

• Raca Todosijević ^[3] ; Olivera Stančić ^[1] ; Zorica Stanimirović ^[2] ; Stefan Mišković ^[2]
  1. [1] University of Kragujevac

     University of Kragujevac

     Opština Kragujevac, Serbia

     
  2. [2] University of Belgrade

     University of Belgrade

     Serbia

     
  3. [3] Univ. Polytechnique Hauts-de-France, France

  Mostrar afiliaciones +
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 262-303
• Idioma: inglés
• DOI: 10.1007/s11750-024-00685-9
• Enlaces
  • Texto completo
• Resumen

  • This paper introduces the capacitated single allocation hub maximal covering problem (CSAHMCP) which arises from optimizing delivery service networks. The goal of the problem is to determine locations for installing hubs and to allocate each nonhub node to one of the installed hubs with enough capacity, to minimize the sum of uncovered demand of all origin–destination pairs and the costs of hub installation. We propose four-index integer linear mathematical formulation of the CSAHMCP, and reformulations to a two-index and a three-index mixed integer linear programs. Having in mind NP-hardness of the novel CSAHMCP, we design and implement a General Variable Neighborhood Search (GVNS) heuristic as a solution method. Computational experiments are conducted on the standard Australian Post (AP) hub instances from the literature with up to 200 nodes. By analyzing the results of CPLEX solver with the three proposed CSAHMCP formulations on AP instances with up to 100 nodes, it can be concluded that the two-index formulation was generally the most efficient, followed by the three-index model, while the four-index one had the worst performance. The proposed GVNS metaheuristic reaches all known optimal solutions or improves upper bounds provided by CPLEX in short CPU times. In the case of the largest AP instances with 200 nodes, for which CPLEX provided no feasible solution, the proposed GVNS heuristic quickly returns solutions, showing its potential to solve problem instances of large dimensions in an efficient manner. In addition, sensitivity analysis regarding the value of coverage criterion parameter was preformed and the obtained results are discussed

• Referencias bibliográficas
  • Alizadeh Y, Tavakkoli-Moghaddam R, Ebrahimnejad S (2016) A new multi-objective model for a capacitated hub covering problem solving by two...
  • Alumur S, Kara BY (2008) Network hub location problems: the state of the art. Eur J Oper Res 190(1):1–21. https://doi.org/10.1016/j.ejor.2007.06.008
  • Alumur SA, Campbell JF, Contreras I, Kara BY, Marianov V, O’Kelly ME (2021) Perspectives on modeling hub location problems. Eur J Oper Res...
  • Alumur S, Kara BY (2009) A hub covering network design problem for cargo applications in Turkey. J Oper Res Soc 60(10):1349–1359. https://doi.org/10.1057/jors.2008.92
  • Brimberg J, Mladenović N, Todosijević R, Urošević D (2017) A basic variable neighborhood search heuristic for the uncapacitated multiple allocation...
  • Brimberg J, Mišković S, Todosijević R, Urošević D (2022) The uncapacitated r-allocation p-hub center problem. Int Trans Oper Res 29(2):854–878....
  • Brimberg J, Salhi S, Todosijević R, Urošević D (2023) Variable neighborhood search: the power of change and simplicity. Comput Oper Res 155:106–221....
  • Campbell JF (1994) Integer programming formulations of discrete hub location problems. Eur J Oper Res 75(2):387–405. https://doi.org/10.1016/0377-2217(94)90318-2
  • Campbell JF, O’Kelly ME (2012) Twenty-five years of hub location research. Transp Sci 46(2):153–169. https://doi.org/10.1287/trsc.1120.0410
  • Carrizosa E, Mladenović N, Todosijević R (2013) Variable neighborhood search for minimum sum-of- squares clustering on networks. Eur J Oper...
  • Church R, ReVelle C (1974) The maximal covering location problem. Pap Reg Sci 32(1):101–118. https://doi.org/10.1111/j.1435-5597.1974.tb00902.x
  • Contreras I, Díaz JA, Fernández E (2009) Lagrangean relaxation for the capacitated hub location problem with single assignment. OR Spectrum...
  • Contreras I (2015) Hub location problems. In: Location Science, Springer, pp 311–344. https://doi.org/10. 1007/978-3-319-13111-5_12
  • Contreras I, O’Kelly M (2019) Hub location problems. In: Laporte G, Nickel S, Saldanha da Gama F (eds) Location Science. Springer, Cham. https://doi.org/10.1007/978-3-030-32177-2_12
  • Costa M, Captivo M, Climaco J (2008) Capacitated single allocation hub location problem—a bi-criteria approach. Comput Oper Res 35(11):3671–3695....
  • Crainic TG, Laporte G (1997) Planning models for freight transportation. Eur J Oper Res 97(3):409–438. https://doi.org/10.1016/S0377-2217(96)00298-6
  • Delmaire H, Díaz JA, Fernández E, Ortega M (1999) Reactive GRASP and tabu search based heuristics for the single source capacitated plant...
  • Díaz JA, Luna DE, Camacho-Vallejo JF, Casas-Ramírez MS (2017) GRASP and hybrid GRASP-Tabu heuristics to solve a maximal covering location...
  • Duarte A, Sánchez-Oro J, Mladenović N, Todosijević R (2018). Variable Neighborhood Descent. In: Martí R, Pardalos PM, Resende MGC (eds) Handbook...
  • Drezner Z, Hamacher H (2002) Facility Location: Applications and Theory. Springer-Verlag
  • Ebery J, Krishnamoorthy M, Ernst AT, Boland N (2000) The capacitated multiple allocation hub location problem: formulations and algorithms....
  • Ernst AT, Krishnamoorthy M (1998) Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem. Eur J Oper...
  • Ernst AT, Krishnamoorthy M (1998) Solution algorithms for the capacitated single allocation hub location problem
  • Ernst AT, Jiang H, Krishnamoorthy M, Baatar H (2011) Reformulations and computational results for the uncapacitated single allocation hub...
  • Farahani RZ, Hekmatfar M, Arabani AB, Nikbakhsh E (2013) Hub location problems: A review of models, classification, solution techniques, and...
  • Feo TA, Bard JF (1989) Flight scheduling and maintenance base planning. Manage Sci 35(12):1415–1432. https://doi.org/10.1287/mnsc.35.12.1415
  • Feo TA, Resende MGC (1995) Greedy randomized adaptive search procedures. J Glob Optim 6(2):109–133. https://doi.org/10.1007/BF01096763
  • Festa P, Pardalos PM, Resende MGC, Ribeiro CC (2002) Randomized heuristics for the MAX-CUT problem. Optim Methods Softw 17(6):1033–1058. https://doi.org/10.1080/1055678021000090033
  • Festa P, Resende MGC (2009) An annotated bibliography of GRASP-Part I: Algorithms. Int Trans Oper Res 16(1):1–24. https://doi.org/10.1111/j.1475-3995.2009.00663.x
  • Festa P, Resende MGC (2009) An annotated bibliography of GRASP-Part II: Applications. Int Trans Oper Res 16(2):131–172. https://doi.org/10.1111/j.1475-3995.2009.00664.x
  • Festa P, Resende MGC (2011) GRASP: basic components and enhancements. Telecommun Syst 46(3):253–271. https://doi.org/10.1007/s11235-010-9289-z
  • Fleszar K, Hindi KS (2008) An effective VNS for the capacitated p-median problem. Eur J Oper Res 191(3):612–622. https://doi.org/10.1016/j.ejor.2006.12.055
  • Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):344–348. https://doi.org/10.1145/367766.368168
  • Hansen P, Mladenović N, Pérez JAM (2008) Variable neighbourhood search: methods and applications. 4OR 6(4):319–360. https://doi.org/10.1007/s10288-008-0089-1
  • Hansen P, Mladenović N, Pérez JAM (2010) Variable neighbourhood search: methods and applications. Ann Oper Res 175(1):367–407. https://doi.org/10.1007/s10479-009-0657-6
  • Hansen P, Mladenović N (2014) Variable neighborhood search. In: Burke EK, Graham RD (eds) Search methodologies: Introductory Tutorials in...
  • Hansen P, Mladenović N, Todosijević R, Hanafi S (2017) Variable neighborhood search: basics and variants. EURO J Comput Optim 5(3):423–454. ...
  • Hernández-Pérez H, Rodríguez-Martín I, Salazar-González JJ (2009) A hybrid GRASP/VND heuristic for the one-commodity pickup-and-delivery traveling...
  • Hwang YH, Young HL (2012) Uncapacitated single allocation p-hub maximal covering problem. Comput Ind Eng 63(2):382–389. https://doi.org/10.1016/j.cie.2012.03.014 Ilić...
  • Janković O, Mišković S, Stanimirović Z, Todosijević R (2017) Novel formulations and VNS-based heuristics for single and multiple allocation...
  • Janković O, Stanimirović Z (2017) A general variable neighborhood search for solving the uncapacitated r-allocation p-hub maximal covering...
  • Janković O (2018) An efficient Genetic Algorithm for the Uncapacitated r-allocation p-hub Maximal Covering Problem. Yugosl J Oper Res 28(2):201–218....
  • Kara BY, Tansel BC (2003) The single-assignment hub covering problem: Models and linearizations. J Oper Res Soc 54(1):59–64. https://doi.org/10.1057/palgrave.jors.2601473
  • Karimi H, Bashiri M (2011) Hub covering location problems with different coverage types. Sci Iran 18(6):1571–1578. https://doi.org/10.1016/j.scient.2011.09.018
  • Karimi H, Bashiri M, Nickel S (2016) Capacitated single allocation p-hub covering problem in multi-modal network using tabu search. Int J...
  • Klincewicz JG (1992) Avoiding local optima in the p-hub location problem using tabu search and GRASP. Ann Oper Res 40(1):283–302. https://doi.org/10.1007/BF02060483
  • Martins SL, Resende MGC, Ribeiro CC, Pardalos PM (2000) A parallel GRASP for the Steiner tree problem in graphs using a hybrid local search...
  • Labbé M, Yaman H, Gourdin E (2005) A branch and cut algorithm for hub location problems with single assignment. Math Progr 102(2):371–405. ...
  • Lowe T, Sim T (2013) The hub covering flow problem. J Oper Res Soc 64:973–981. https://doi.org/10.1057/jors.2012.122
  • Marín A (2005) Formulating and solving splittable capacitated multiple allocation hub location problems. Comput Oper Res 32:3093–3109. https://doi.org/10.1016/j.cor.2004.04.008
  • Mjirda A, Todosijevi´c R, Hanafi S, Hansen P, Mladenovi´c N (2017) Sequential variable neighborhood descent variants: an empirical study on...
  • Mladenovi´c N, Hansen P (1997) Variable neighborhood search. Comput Oper Res 24(11):1097–1100. https://doi.org/10.1016/S0305-0548(97)00031-2
  • Mohammadi M, Tavakkoli-Moghaddam R, Rostami R (2011) A multi-objective imperialist competitive algorithm for a capacitated hub covering location...
  • Molina JC, Eguia I, Racero J (2015) Reducing pollutant emissions in a waste collection vehicle routing problem using a variable neighborhood...
  • O’Kelly ME (1987) A quadratic integer program for the location of interacting hub facilities. Eur J Oper Res 32(3):393–404. https://doi.org/10.1016/S0377-2217(87)80007-3
  • Parreño F, Alvarez-Valdés R, Oliveira JF, Tamarit JM (2010) A hybrid GRASP/VND algorithm for two-and three-dimensional bin packing. Ann Oper...
  • Peiró J, Corberán Á, Martí R (2014) GRASP for the uncapacitated r-allocation p-hub median problem. Comput Oper Res 43(1):50–60. https://doi.org/10.1016/j.cor.2013.08.026
  • Peiró J, Corberán Á, Laguna M, Martí R (2017) Models and solution methods for the uncapacitated r-allocation p-hub equitable center problem....
  • Peker M, Kara BY (2015) The p-hub maximal covering problem and extensions for gradual decay functions. Omega 54:158–172. https://doi.org/10.1016/j.omega.2015.01.009
  • Ratli M, Uroševi´c D, El Cadi AA, Brimberg J, Mladenovi´c N, Todosijevi´c R (2022) An efficient heuristic for a hub location routing problem....
  • Randall M (2008) Solution approaches for the capacitated single allocation hub location problem using ant colony optimisation. Comput Optim...
  • Resende MGC, Ribeiro CC (2010) Greedy randomized adaptive search procedures: Advances, hybridizations, and applications. In: Handbook of metaheuristics,...
  • Resende MGC, Ribeiro CC (2014) GRASP: Greedy randomized adaptive search procedure. In: Burke EK, Kendall G (eds) Search Methodologies – Introductory...
  • Ribeiro CC, Uchoa E, Werneck RF (2002) A hybrid GRASP with perturbations for the Steiner problem in graphs. INFORMS J Comput 14(3):228–246....
  • Risti´c D, Mladenovi´c N, Ratli M, Todosijevi´c R, Uroševi´c D (2023) Auxiliary data structures and techniques to speed up solving of the...
  • Rodríguez-Martín I, Salazar-González JJ (2008) Solving a capacitated hub location problem. Eur J Oper Res 184:468–479. https://doi.org/10.1016/j.ejor.2006.11.026
  • Sedehzadeh S, Tavakkoli-Moghaddam R, Jolai F (2015) A new multi-mode and multi-product hub covering problem: a priority MMc queue approach....
  • Salehipour A, Sörensen K, Goos P, Bräysy O (2011) Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem....
  • Sener N, Feyzioglu O (2021) Capacitated Multiple Allocation Hub Covering Flow Problem. MANAS J Eng 9(1):72–84. https://doi.org/10.51354/mjen.809844
  • Sener N, Feyzioglu O (2023) Multiple allocation hub covering flow problem under uncertainty. Ann Oper Res 320:975–997. https://doi.org/10.1007/s10479-022-04553-2
  • Stanˇci´c O, Stanimirovi´c Z, Todosijevi´c R, Miškovi´c S (2022) Mathematical formulations and solution methods for the uncapacitated r-allocation...
  • Todosijevi´c R, Uroševi´c D, Mladenovi´c N, Hanafi S (2017) A general variable neighborhood search for solving the uncapacitated r-allocation...
  • Villegas JG, Prins C, Prodhon C, Medaglia AL, Velasco N (2010) GRASP/VND and multi-start evolutionary local search for the single truck and...
  • Wagner B (2008) Model formulations for hub covering problems. J Oper Res Soc 59(7):932–938. https:// doi.org/10.1057/palgrave.jors.2602424
  • Wang J, Qin Z (2020) Chance constrained programming models for uncertain hub covering location problems. Soft Comput 24:2781–2791. https://doi.org/10.1007/s00500-019-04476-4
  • Weng K, Yang C, Ma Y (2006) Two artificial intelligence heuristics in solving multiple allocation hub maximal covering problem. In: Huang...
  • Yaman H (2004) Concentrator location in telecommunications (2004). Q J Belg Fr Ital Oper Res Soc 2:175–177
  • Yaman H (2011) Allocation strategies in hub networks. Eur J Oper Res 211(3):442–451. https://doi.org/10.1016/j.ejor.2011.01.014