Fuzzy Multi-Period Mathematical Programming Model for Maximal Covering Location Problem

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamadan, Iran

2 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University,Tehran,Iran.

3 Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran

Abstract

In this paper, a model is presented to locate ambulances, considering backup facility (to increase reliability) and the restriction of ambulance capacity. This model is designed for emergencies. In this model the covered demand for each demand point depends on the number of coverage times and the amount of demand. The demand amount and ambulance coverage radius are consideredfuzzy in various periods, with respect to the conditions and application of the model. Ambulances have the ability to be relocated in different periods. In this model we have considered two types of ambulances to locate: ground and air ambulance. Air ambulances are considered as backup facilities. It is assumed that ground ambulances are major facilities, taking into account capacity limitations. To solve this model, making chromosomes (initial solution) is presented in such a way that location chromosome for both ground and air ambulances are appears as a general chromosome. Since this is a complicated model, apopulation-based simulated annealing algorithm (MultipleSimulated Annealing) with a chromosome combinatorial approach is used to solve it. Finally, the results of the algorithm presented to solve the model are compared with the simulated annealing (SA) algorithm. The results showed that the quality of the presented algorithm (MSA) is better than the SA algorithm.

Keywords

Main Subjects


ARAZ, C., SELIM, H. & OZKARAHAN, I. 2007. A fuzzy multi-objective covering-based vehicle location model for emergency services. Computers & Operations Research, 34, 705-726.

AYTUG, H. & SAYDAM, C. 2002. Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study. European Journal of Operational Research, 141, 480-494.

BARBAS, J. & MARı́N, Á. 2004. Maximal covering code multiplexing access telecommunication networks. European Journal of Operational Research, 159, 219-238.

BAŞAR, A., ÇATAY, B. & ÜNLÜYURT, T. 2011. A multi-period double coverage approach for locating the emergency medical service stations in Istanbul. Journal of the Operational Research Society, 62, 627-637.

BATANOVIĆ, V., PETROVIĆ, D. & PETROVIĆ, R. 2009. Fuzzy logic based algorithms for maximum covering location problems. Information Sciences, 179, 120-129.

BERMAN, O., DREZNER, Z. & WESOLOWSKY, G. O. 2009. The maximal covering problem with some negative weights. Geographical analysis, 41, 30-42.

BERMAN, O. & HUANG, R. 2008. The minimum weighted covering location problem with distance constraints. Computers & Operations Research, 35, 356-372.

BERMAN, O. & KRASS, D. 2002. The generalized maximal covering location problem. Computers & Operations Research, 29, 563-581.

BERMAN, O., KRASS, D. & MENEZES, M. B. C. 2007. Facility Reliability Issues in Network p-Median Problems: Strategic Centralization and Co-Location Effects. Operations Research, 55, 332-350.

BERMAN, O. & WANG, J. 2011. The minmax regret gradual covering location problem on a network with incomplete information of demand weights. European Journal of Operational Research, 208, 233-238.

CANBOLAT, M. S. & VON MASSOW, M. 2009. Planar maximal covering with ellipses. Computers & Industrial Engineering, 57, 201-208.

COLOMBO, F., CORDONE, R. & LULLI, G. 2016. The multimode covering location problem. Computers & Operations Research, 67, 25-33.

CURTIN, K. M., HAYSLETT-MCCALL, K. & QIU, F. 2010. Determining optimal police patrol areas with maximal covering and backup covering location models. Networks and Spatial Economics, 10, 125-145.

DE ASSIS CORRÊA, F., LORENA, L. A. N. & RIBEIRO, G. M. 2009. A decomposition approach for the probabilistic maximal covering location-allocation problem. Computers & Operations Research, 36, 2729-2739.

ERDEMIR, E. T., BATTA, R., SPIELMAN, S., ROGERSON, P. A., BLATT, A. & FLANIGAN, M. 2008. Location coverage models with demand originating from nodes and paths: application to cellular network design. European Journal of Operational Research, 190, 610-632.

ESPEJO, L. G. A., GALVAO, R. D. & BOFFEY, B. 2003a. Dual-based heuristics for a hierarchical covering location problem. Computers & Operations Research, 30, 165-180.

ESPEJO, L. G. A., GALVÃO, R. D. & BOFFEY, B. 2003b. Dual-based heuristics for a hierarchical covering location problem. Computers & Operations Research, 30, 165-180.

FARAHANI, R. Z., HASSANI, A., MOUSAVI, S. M. & BAYGI, M. B. 2014. A hybrid artificial bee colony for disruption in a hierarchical maximal covering location problem. Computers & Industrial Engineering, 75, 129-141.

GALVÃO, R. D., ACOSTA ESPEJO, L. G. & BOFFEY, B. 2002. A hierarchical model for the location of perinatal facilities in the municipality of Rio de Janeiro. European Journal of Operational Research, 138, 495-517.

GALVÃO, R. D., ESPEJO, L. G. A. & BOFFEY, B. 2000a. A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. European Journal of Operational Research, 124, 377-389.

GALVÃO, R. D., GONZALO ACOSTA ESPEJO, L. & BOFFEY, B. 2000b. A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. European Journal of Operational Research, 124, 377-389.

GENDREAU, M., LAPORTE, G. & SEMET, F. 2001. A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel computing, 27, 1641-1653.

GUNAWARDANE, G. 1982. Dynamic versions of set covering type public facility location problems. European Journal of Operational Research, 10, 190-195.

KARASAKAL, O. & KARASAKAL, E. K. 2004. A maximal covering location model in the presence of partial coverage. Computers & Operations Research, 31, 1515-1526.

LEE, J. M. & LEE, Y. H. 2010. Tabu based heuristics for the generalized hierarchical covering location problem. Computers & Industrial Engineering, 58, 638-645.

LI, Q., ZENG, B. & SAVACHKIN, A. 2013. Reliable facility location design under disruptions. Computers & Operations Research, 40, 901-909.

MARIANOV, V. & REVELLE, C. 1994. The queuing probabilistic location set covering problem and some extensions. Socio-Economic Planning Sciences, 28, 167-178.

MARIANOV, V. & SERRA, D. 2001. Hierarchical location–allocation models for congested systems. European Journal of Operational Research, 135, 195-208.

MOORE, G. C. & REVELLE, C. 1982. The hierarchical service location problem. Management Science, 28, 775-780.

MURAWSKI, L. & CHURCH, R. L. 2009. Improving accessibility to rural health services: The maximal covering network improvement problem. Socio-Economic Planning Sciences, 43, 102-110.

O’HANLEY, J. R. & CHURCH, R. L. 2011. Designing robust coverage networks to hedge against worst-case facility losses. European Journal of Operational Research, 209, 23-36.

PEIDRO, D., MULA, J., POLER, R. & VERDEGAY, J.-L. 2009. Fuzzy optimization for supply chain planning under supply, demand and process uncertainties. Fuzzy Sets and Systems, 160, 2640-2657.

QU, B. & WENG, K. 2009. Path relinking approach for multiple allocation hub maximal covering problem. Computers & Mathematics with Applications, 57, 1890-1894.

RAJAGOPALAN, H. K., SAYDAM, C. & XIAO, J. 2008. A multiperiod set covering location model for dynamic redeployment of ambulances. Computers & Operations Research, 35, 814-826.

RATICK, S. J., OSLEEB, J. P. & HOZUMI, D. 2009. Application and extension of the Moore and ReVelle hierarchical maximal covering model. Socio-Economic Planning Sciences, 43, 92-101.

REPEDE, J. F. & BERNARDO, J. J. 1994. Developing and validating a decision support system for locating emergency medical vehicles in Louisville, Kentucky. European Journal of Operational Research, 75, 567-581.

REVELLE, C., SCHOLSSBERG, M. & WILLIAMS, J. 2008a. Solving the maximal covering location problem with heuristic concentration. Computers & Operations Research, 35, 427-435.

REVELLE, C. S. & EISELT, H. A. 2005. Location analysis: A synthesis and survey. European Journal of Operational Research, 165, 1-19.

REVELLE, C. S., EISELT, H. A. & DASKIN, M. S. 2008b. A bibliography for some fundamental problem categories in discrete location science. European Journal of Operational Research, 184, 817-848.

ŞAHIN, G. & SÜRAL, H. 2007. A review of hierarchical facility location models. Computers & Operations Research, 34, 2310-2331.

SCHILLING, D. A. 1980. DYNAMIC LOCATION MODELING FOR PUBLIC‐SECTOR FACILITIES: A MULTICRITERIA APPROACH*. Decision Sciences, 11, 714-724.

SHAVANDI, H. & MAHLOOJI, H. 2006. A fuzzy queuing location model with a genetic algorithm for congested systems. Applied Mathematics and Computation, 181, 440-456.

SHAVANDI, H. & MAHLOOJI, H. 2007. Fuzzy hierarchical location-allocation models for congested systems. Journal of Industrial and Systems Engineering, 1, 171-189.

SHEN, Z.-J. M., ZHAN, R. L. & ZHANG, J. 2011. The reliable facility location problem: Formulations, heuristics, and approximation algorithms. INFORMS Journal on Computing, 23, 470-482.

SNYDER, L. V. & DASKIN, M. S. 2005. Reliability Models for Facility Location: The Expected Failure Cost Case. Transportation Science, 39, 400-416.

XIA, L., XIE, M., XU, W., SHAO, J., YIN, W. & DONG, J. An empirical comparison of five efficient heuristics for maximal covering location problems.  Service Operations, Logistics and Informatics, 2009. SOLI'09. IEEE/INFORMS International Conference on, 2009. IEEE, 747-753.

YOUNIES, H. & WESOLOWSKY, G. O. 2004. A mixed integer formulation for maximal covering by inclined parallelograms. European Journal of Operational Research, 159, 83-94.