A Proposal Towards a VNS-Based Decision Support Tool for Large Scale Location-Covering-type Problems
DOI:
https://doi.org/10.2298/YJOR230215042PKeywords:
Location, covering, multiple objective, decision support, greedy heuristics, VNSAbstract
We describe a number of typical features, constraints and objectives, frequently appearing in spatial system-design of maximum covering-type, such as emergency response systems. We then indicate some heuristic local search methods topped by a Variable Neighbourhood Search to construct and search for good solutions. These ideas were intended to form the basis for a possibly multi-objective spatial decision support system.References
P. Chevalier, I. Thomas, D. Geraets, E. Goetghebeur, O. Janssens, D. Peeters, and F. Plastria, ”Locating fire stations: An integrated approach for Belgium,” Socio-Economic Planning Sciences, vol.46, no. 2, jun 2012, pp. 173-182.
N. Mladenović, F. Plastria, and D. Urošević, ”Reformulation descent applied to circle packing problems,” Computers & Operations Research, vol. 32, no. 9, 2005, pp. 2419-2434.
P. Hansen and N. Mladenović, Variable neighborhood search for the p-median. Location Science, vol. 5, no. 4, pp. 207-226, dec 1997.
N. Mladenović, M. Labbé, and P. Hansen, Solving the p-center problem with tabu search and variable neighborhood search. Networks, vol. 42, no. 1, pp. 48-64, 2003.
R. L. Church, and A. Murray, Location Covering Models. Springer International Publishing, 2018.
S. García and A. Marín, Covering location problems. In Gilbert Laporte, Stefan Nickel, and Francisco Saldanha da Gama, editors, Location Science, chapter 5, pages 93-114. Springer International Publishing, 2015.
L. A. McLay, A maximum expected covering location model with two types of servers. IIE Transactions, 41(8):730-741, jun 2009.
A. Başar, B. Çatay, and T. Ünlüyurt, A multi-period double coverage approach for locating the emergency medical service stations in Istanbul. Journal of the Operational Research Society, vol. 62, no. 4, pp. 627-637, 2011.
E. Aktaş, Ö. Özaydın, B. Bozkaya, F. Ülengin, and Ş. Önsel, Optimizing fire station locations for the Istanbul metropolitan municipality. Interfaces, vol. 43, no. 3, pp. 240-255, 2013.
Z. Drezner, V. Marianov, and G. O. Wesolowsky, Maximizing the minimum cover probability by emergency facilities. Annals of Operations Research, vol. 246, no. 1-2, pp. 349-362, 2014.
G. Mullaoğlu and G. Sariyer, Variations of double coverage ambulance location model using call volume and population data. Journal of Industrial and Production Engineering, vol. 36, no. 8, pp. 533-545, 2019.
V. Blanco, R. Gázquez, and F. S. da Gama, Multi-type maximal covering location problems: Hybridizing discrete and continuous problems. European Journal of Operational Research, oct 2022.
J. Xu, A. T. Murray, R. L. Church, and R. Wei, Service allocation equity in location coverage analytics. European Journal of Operational Research, vol. 305, no. 1, pp. 21-37, 2023.
D. A. Schilling, C. Revelle, J. Cohon, and D. J. Elzinga, Some models for fire protection locational decisions. European Journal of Operational Research, vol. 5, no.1, pp. 1-7, 1980.
S. Ceria, P. Nobili, and A. Sassano, Set covering. In M.Dell’Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliography in Combinatorial Optimization, chapter 23. J. Wiley andSons, 1997.
L. V. Snyder, Covering problems. In H. A. Eiselt and Vladimir Marianov, editors, Foundations of Location Analysis, pages 109-135. Springer US, New York, NY, 2011.
X. Li, Z. Zhao, X. Zhu, and T. Wyatt, Covering models and optimization techniques for emergency response facility location and planning: a review. Mathematical Methods of Operations Research, vol. 74, no. 3, pp. 281-310, 2011.
A. T. Murray, Fire station siting. In H. A. Eiselt and Vladimir Marianov, editors, Applications of Location Analysis, pages 293-306. Springer International Publishing, Cham, 2015.
Y. Liu, Y. Yuan, J. Shen, and W. Gao, Emergency response facility location in transportation networks: A literature review. Journal of Traffic and Transportation Engineering (English Edition), vol. 8, no. 2, pp. 153-169, 2021.
M. L. Balinski, Integer programming: Methods, uses, computations. Management Science, vol. 12, no. 3, pp. 253-313, 1965.
C. Toregas and C. ReVelle Optimal location under time or distance constraints. Papers of the Regional Science Association, vol. 28, no. 1, pp. 131-143, 1972.
M. S. Daskin and E. H. Stern, A hierarchical objective set covering model for emergency medical service vehicle deployment. Transportation Science, vol. 15, no. 2, pp. 137-152, 1981.
Church and ReVelle, The maximal covering location problem. Papers of the Regional Science Association, vol. 32, pp. 101-118, 1974.
V. Chvatal, A greedy heuristic for the set-covering problem. Mathematics of Operations Research, vol. 4, no. 3, pp. 233-235, 1979.
M. Ohlsson, C. Peterson, and B. Söderberg, An efficient mean field approach to the set covering problem. European Journal of Operational Research, vol. 133, no. 3, pp. 583-595, 2001.
N. Liu, B. Huang, and M. Chandramouli, Optimal siting of fire stations using GIS and ANT algorithm. Journal of Computing in Civil Engineering, vol. 20, no. 5, pp. 361-369, 2006.
L. Yang, B. F. Jones, and S. H. Yang, A fuzzy multi-objective programming for optimization of fire station locations through genetic algorithms. European Journal of Operational Research, vol. 181, no. 2, pp. 903-915, 2007.
D. Tong, A. Murray, and N. Xiao, Heuristics in spatial analysis: A genetic algorithm for coverage maximization. Annals of the Association of American Geographers, vol. 99, no. 4, pp. 698-711, 2009.
A. Başar, B. Çatay, and T. Ünlüyurt, A taxonomy for emergency service station location problem. Optimization Letters, vol. 6, no.6, pp. 1147-1160, 2011.
A. Elshaikh, S. Salhi, J. Brimberg, N. Mladenović, B. Callaghan, and G. Nagy, An adaptive perturbation-based heuristic: An application to the continuous p-centre problem. Computers & Operations Research, vol. 75, pp 1-11, 2016.
M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990.
H. P. Williams, Model building in mathematical programming. Wiley, 5th edition, 2013.
G. Sierksma, and Y. Zwols, Linear and Integer Optimization : Theory and Practice, Third Edition. Chapman and Hall/CRC, 2015.
F. Plastria, Formulating logical implications in combinatorial optimisation. European Journal of Operational Research, vol. 140, no. 2, pp. 338-353, 2002.
N. Mladenović and P. Hansen, Variable neighborhood search. Computers & Operations Research, vol. 24, no. 11, pp. 1097-1100, 1997.
G. Caporossi, P. Hansen, and N. Mladenović, Variable neighborhood search. In Metaheuristics, pages 77-98. Springer International Publishing, 2016.
P. Hansen, N. Mladenović, R. Todosijević, and S. Hanafi, Variable neighborhood search: basics and variants. EURO Journal on Computational Optimization, vol. 5, no. 3, pp. 423-454, 2017.
I. Grujičić and Z. Stanimirović, Variable neighborhood search method for optimizing the emergency service network of police special forces units. Electronic Notes in Discrete Mathematics, vol. 39, pp. 185-192, 2012.
N. Nikolić, I. Grujičić, and N. Mladenović, A large neighbourhood search heuristic for covering designs. IMA Journal of Management Mathematics, vol. 27, no. 1, pp. 89-106, 2014.
L. Mrkela and Z. Stanimirović, A variable neighborhood search for the budget-constrained maximal covering location problem with customer preference ordering. Operational Research, vol. 22, no.5, pp. 5913-5951, 2021.
A. Casado, N. Mladenović, J. Sánchez-Oro, and A. Duarte, Variable neighborhood search approach with intensified shake for monitor placement. Networks, dec 2022.
N. Mladenović, F. Plastria, and D. Urošević, Formulation space search for circle packing problems. In Engineering Stochastic Local Search Algorithms. Designing, Implementing and Analyzing Effective Heuristics, pages 212-216. Springer Berlin Heidelberg, 2007.
N. Mladenović, J. Brimberg, and D. Urošević, Formulation space search metaheuristic. In The Palgrave Handbook of Operations Research, pages 405-445. Springer International Publishing, 2022.
S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, vol. 12, no. 3, pp. 450-459, 1964.
D. Chen and R. Chen, Optimal algorithms for the α-neighbor p-center problem. European Journal of Operational Research, vol. 225, no. 1, pp. 36-43, 2013.
S. R. Mousavi, Exploiting flat subspaces in local search for p-center problem and two fault-tolerant variants. Computers & Operations Research, vol. 149, 106023, 2023.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
