×

Less is more: general variable neighborhood search for the capacitated modular hub location problem. (English) Zbl 1458.90448

Summary: In this paper, we study the capacitated modular hub location problem. The problem belongs to the class of the single assignment hub location problems, where a terminal can be assigned to only one hub. In addition, the problem imposes capacity constraints, on both hubs and edges that connect them. The observed problem is directly related to the real problem. Namely, in air traffic, the number of flights between two cities directly determines the conditions of the capacity. In order to tackle the problem, we propose a general variable neighborhood search (GVNS) based heuristic. We have performed exhaustive testing that led to the conclusion that the GVNS method gave superior results in comparison to the previous methods. This is especially reflected in the number of best solutions that were obtained in a much shorter time. Additionally, we applied statistical tests which showed that GVNS is undoubtedly superior with respect to the previously observed methods.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alumur, S.; Kara, B., Network hub location problems: the state of the art, Eur. J. Opera. Res., 190, 1, 1-21 (2008) · Zbl 1146.90455
[2] Brimberg, J.; Mladenović, N.; Todosijević, R.; Urošević, D., Less is more: solving the max-mean diversity problem with variable neighborhood search, Inform. Sci., 382, 179-200 (2017)
[3] Brimberg, J.; Mladenović, N.; Todosijević, R.; Urošević, D., A non-triangular hub location problem, Optim. Lett. (2019)
[4] Campbell, J. F., Integer programming formulations of discrete hub location problems, Eur. J. Opera. Res., 72, 2, 387-405 (1994) · Zbl 0790.90048
[5] Campbell, J. F.; O’Kelly, M., Twenty-five years of hub location research, Transp. Sci., 46, 2, 153-169 (2012)
[6] Contreras, I.; Fernndez, E.; Marin, A., The tree of hubs location problem, Eur. J. Opera. Res., 202, 2, 390-400 (2010) · Zbl 1175.90396
[7] Contreras, I.; Tanash, M.; Vidyarthi, N., Exact and heuristic approaches for the cycle hub location problem, Ann. Opera. Res., 258, 2, 655-677 (2017) · Zbl 1381.90025
[8] Corberán, A.; Peiró, J.; Campos, V.; Marti, R., Strategic oscillation for the capacitated hub location problem with modular links, J. Heurist., 22, 2, 221-244 (2016)
[9] Costa, L. R.; Aloise, D.; Mladenović, N., Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering, Inform. Sci., 415, 247-253 (2017)
[10] Ernst, A.; Krishnamoorth, M., Efficient algorithms for the uncapacitated single allocation p-hub median problem, Locat. Sci., 4, 3, 139-154 (1996) · Zbl 0927.90065
[11] Farahani, R. Z.; Hekmatfar, M.; Boloori, A.; Nikbakhsh, E., Hub location problems: a review of models, classification, solution techniques, and applications, Comput. Indus. Eng., 64, 4, 1096-1109 (2013)
[12] Gelareh, S.; Gendron, B.; Hanafi, S.; Neamatian Monemi, R.; Todosijević, R., The selective traveling salesman problem with draft limits, J. Heurist. (2019)
[13] Hansen, P.; Mladenović, N., First vs. best improvement: an empirical study, Discret. Appl. Math., 154, 5, 802-817 (2006) · Zbl 1120.90048
[14] Hansen, P.; Mladenović, N.; Todosijević, R.; Hanafi, S., Variable neighborhood search: basics and variants, EURO J. Comput. Optim., 5, 3, 423-454 (2017) · Zbl 1390.90586
[15] Hoff, A.; Peiró, J.; Corberán, A.; Martí, R., Heuristics for the capacitated modular hub location problem, Comput. Opera. Res., 86, 94-109 (2017) · Zbl 1391.90382
[16] Ilic, A.; Urosevic, D.; Brimberg, J.; Mladenovic, N., A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem, Eur. J. Opera. Res., 206, 2, 289-300 (2010) · Zbl 1188.90142
[17] Mahmutogullari, A. I.; Kara, B. Y., Hub location problem with allowed routing between nonhub nodes, Geogr. Anal., 47, 4, 410-430 (2015)
[18] Mjirda, A.; Todosijević, R.; Hanafi, S.; Hansen, P.; Mladenović, N., Sequential variable neighborhood descent variants: an empirical study on the traveling salesman problem, Int. Trans. Opera. Res., 24, 3, 615-633 (2017) · Zbl 1366.90182
[19] Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Opera. Res., 24, 11, 1097-1100 (1997) · Zbl 0889.90119
[20] Mladenović, N.; Todosijević, R.; Urošević, D., Less is more: basic variable neighborhood search for minimum differential dispersion problem, Inform. Sci., 326, 160-171 (2016)
[21] Mohri, S. S.; Karimi, H.; Kordani, A. A.; Nasrollahi, M., Airline hub-and-spoke network design based on airport capacity envelope curve: a practical view, Comput. Indus. Eng., 125, 375-393 (2018)
[22] Momayezi, F.; Chaharsooghi, S. K.; Sepehri, M. M.; Kashan, A. H., The capacitated modular single-allocation hub location problem with possibilities of hubs disruptions: modeling and a solution algorithm, Opera. Res., 1-28 (2018)
[23] O’Kelly, M. E., A quadratic integer program for the location of interacting hub facilities, Eur. J. Opera. Res., 32, 3, 393-404 (1987) · Zbl 0627.90030
[24] Peiró, J.; Corberán, A.; Marti, R., GRASP for the uncapacitated r-allocation p-hub median problem, Comput. Opera. Res., 43, 1, 50-60 (2014) · Zbl 1348.90410
[25] Rastani, S.; Setak, M.; Karimi, H., Capacity selection for hubs and hub links in hub location problems, Int. J. Manag. Sci. Eng. Manag., 1, 3, 123-133 (2016)
[26] Taherkhani, G.; Alumur, S., Profit maximizing hub location problems, Omega (2018)
[27] Tanash, M.; Contreras, I.; Vidyarthi, N., An exact algorithm for the modular hub location problem with single assignments, Comput. Opera. Res., 85, 32-44 (2017) · Zbl 1458.90462
[28] Yaman, H.; Carello, G., Solving the hub location problem with modular link capacities, Comput. Opera. Res., 32, 3227-3245 (2005) · Zbl 1178.90221
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.