Solving the capacitated dispersion problem with variable neighborhood search approaches: from basic to skewed VNS. (English) Zbl 1511.90358

Mladenović, Nenad; Todosijević, Raca; Urošević, Dragan; Ratli, Mustapha

Comput. Oper. Res. 139, Article ID 105622, 17 p. (2022).

Summary: The topic of this paper is the Capacitated Dispersion Problem (CDP). To solve the problem, variable neighborhood search (VNS) based heuristics are proposed. The proposed heuristics are Basic VNS, General VNS and General Skewed VNS. Their performances are assessed on the benchmark instances from the literature and compared against the state-of-the-art ones. Comparing to the state-of-the-art results, it turns out that Basic VNS is able to provide competitive results, while General VNS and General Skewed VNS advance the state-of-the-art results by establishing 57 new best-known solutions on the data set of 100 instances. Twenty nine new best-known solutions are solely due to the proposed General Skewed VNS.

© Elsevier Ltd

MSC:

90C27	Combinatorial optimization
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

heuristics; variable neighborhood search; capacitated dispersion problem; combinatorial optimization

References:

[1]	Adil, G. K.; Ghosh, J. B., Maximum diversity/similarity models with extension to part grouping, Int. Trans. Oper. Res., 12, 3, 311-323, 2005 · Zbl 1131.90333
[2]	Amirgaliyeva, Z.; Mladenović, N.; Todosijević, R.; Urošević, D., Solving the maximum min-sum dispersion by alternating formulations of two different problems, European J. Oper. Res., 260, 2, 444-459, 2017 · Zbl 1403.90544
[3]	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
[4]	Brown, J. R., The knapsack sharing problem, Oper. Res., 27, 2, 341-355, 1979 · Zbl 0394.90065
[5]	Duarte, A.; Sánchez-Oro, J.; Mladenović, N.; Todosijević, R., Variable neighborhood descent, 341-367
[6]	Erkut, E., The discrete p-dispersion problem, European J. Oper. Res., 46, 1, 48-60, 1990 · Zbl 0702.90050
[7]	Erkut, E.; Neuman, S., Analytical models for locating undesirable facilities, European J. Oper. Res., 40, 3, 275-291, 1989 · Zbl 0668.90025
[8]	Ghosh, J. B., Computational aspects of the maximum diversity problem, Oper. Res. Lett., 19, 4, 175-181, 1996 · Zbl 0873.90070
[9]	Glover, F.; Kuo, C.-C.; Dhir, K. S., Heuristic algorithms for the maximum diversity problem, J. Inform. Optimiz. Sci., 19, 1, 109-132, 1998 · Zbl 0903.90121
[10]	Hansen, P.; Mladenović, N.; Pérez, J. A.M., Variable neighbourhood search: methods and applications, Ann. Oper. Res., 175, 1, 367-407, 2010 · Zbl 1185.90211
[11]	Hansen, P.; Mladenović, N.; Todosijević, R.; Hanafi, S., Variable neighborhood search: basics and variants, EURO J. Comput. Optimiz., 5, 3, 423-454, 2017 · Zbl 1390.90586
[12]	Kortsarz, G., Peleg, D., 1993. On choosing a dense subgraph. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, pp. 692–701.
[13]	Kuby, M. J., Programming models for facility dispersion: The p-dispersion and maxisum dispersion problems, Geograph. Anal., 19, 4, 315-329, 1987
[14]	Kuo, C.-C.; Glover, F.; Dhir, K. S., Analyzing and modeling the maximum diversity problem by zero-one programming, Decis. Sci., 24, 6, 1171-1185, 1993
[15]	Lai, X.; Hao, J.-K.; Glover, F.; Yue, D., Intensification-driven tabu search for the minimum differential dispersion problem, Knowl.-Based Syst., 167, 68-86, 2019
[16]	Martí, R.; Gallego, M.; Duarte, A.; Pardo, E. G., Heuristics and metaheuristics for the maximum diversity problem, J. Heuristics, 19, 4, 591-615, 2013
[17]	Martí, R.; Martínez-Gavara, A.; Sanchez-Oro, J., The capacitated dispersion problem: an optimization model and a memetic algorithm, Memet. Comput., 13, 1, 131-146, 2021
[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. Oper. Res., 24, 3, 615-633, 2017 · Zbl 1366.90182
[19]	Mladenović, N.; Alkandari, A.; Pei, J.; Todosijević, R.; Pardalos, P. M., Less is more approach: basic variable neighborhood search for the obnoxious p-median problem, Int. Trans. Oper. Res., 27, 1, 480-493, 2020 · Zbl 07766433
[20]	Mladenović, N.; Hansen, P., Variable neighborhood search, Comput. Oper. Res., 24, 11, 1097-1100, 1997 · Zbl 0889.90119
[21]	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
[22]	Peiró, J.; Jiménez, I.; Laguardia, J.; Martí, R., Heuristics for the capacitated dispersion problem, Int. Trans. Oper. Res., 28, 1, 119-141, 2021 · Zbl 07768501
[23]	Prokopyev, O. A.; Kong, N.; Martinez-Torres, D. L., The equitable dispersion problem, European J. Oper. Res., 197, 1, 59-67, 2009 · Zbl 1157.90539
[24]	Rahman, M.; Kuby, M., A multiobjective model for locating solid waste transfer facilities using an empirical opposition function, Locat. Sci., 4, 4, 277-278, 1996
[25]	Rosenkrantz, D. J.; Tayi, G. K.; Ravi, S., Facility dispersion problems under capacity and cost constraints, J. Combin. Optimiz., 4, 1, 7-33, 2000 · Zbl 0961.90091
[26]	Song, J.; Wang, Y.; Wang, H.; Wu, Q.; Punnen, A. P., An effective multi-wave algorithm for solving the max-mean dispersion problem, J. Heuristics, 25, 4, 731-752, 2019
[27]	Teitz, M. B., Toward a theory of urban public facility location, Pap. Reg. Sci., 21, 1, 35-51, 1968
[28]	Wang, Y.; Wu, Q.; Glover, F., Effective metaheuristic algorithms for the minimum differential dispersion problem, European J. Oper. Res., 258, 3, 829-843, 2017 · Zbl 1394.90584
[29]	Weitz, R.; Lakshminarayanan, S., An empirical comparison of heuristic methods for creating maximally diverse groups, J. Oper. Res. Soc., 635-646, 1998 · Zbl 1131.90365