Facility location is a critical component of strategic planning for public and private firms. Due to high cost of facility location, making decisions for such a problem has become an important issue which have gained a large deal of attention from researchers. This study examined the gradual maximal covering location problem with variable radius over multiple time periods. In gradual covering location problem, it is assumed that full coverage is replaced by a coverage function, so that increasing the distance from the facility decreases the amount of demand coverage. In variable radius covering problems, however, each facility is considered to have a fixed cost along with a variable cost which has a direct impact on the coverage radius. In real-world problems, since demand may change over time, necessitating relocation of the facilities, the problem can be formulated over multiple time periods. In this study, a mixed integer programming model was presented in which not only facility capacity was considered, but also two objectives were followed: coverage maximization and relocation cost minimization. A metaheuristic algorithm was presented to solve the maximal covering location problem. A simulated annealing algorithm was proposed, with its results presented. Computational results and comparisons demonstrated good performance of the simulated annealing algorithm.
Accepté le :
DOI : 10.1051/ro/2018026
Mots-clés : Gradual maximal covering location problem, variable radius coverage, capacitated facilities, multi-objective coverage, facility relocation, simulated annealing algorithm
@article{RO_2018__52_4-5_1245_0, author = {Eydi, Alireza and Mohebi, Javad}, title = {Modeling and solution of maximal covering problem considering gradual coverage with variable radius over multi-periods}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {1245--1260}, publisher = {EDP-Sciences}, volume = {52}, number = {4-5}, year = {2018}, doi = {10.1051/ro/2018026}, zbl = {1411.90199}, mrnumber = {3884157}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ro/2018026/} }
TY - JOUR AU - Eydi, Alireza AU - Mohebi, Javad TI - Modeling and solution of maximal covering problem considering gradual coverage with variable radius over multi-periods JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2018 SP - 1245 EP - 1260 VL - 52 IS - 4-5 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro/2018026/ DO - 10.1051/ro/2018026 LA - en ID - RO_2018__52_4-5_1245_0 ER -
%0 Journal Article %A Eydi, Alireza %A Mohebi, Javad %T Modeling and solution of maximal covering problem considering gradual coverage with variable radius over multi-periods %J RAIRO - Operations Research - Recherche Opérationnelle %D 2018 %P 1245-1260 %V 52 %N 4-5 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro/2018026/ %R 10.1051/ro/2018026 %G en %F RO_2018__52_4-5_1245_0
Eydi, Alireza; Mohebi, Javad. Modeling and solution of maximal covering problem considering gradual coverage with variable radius over multi-periods. RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1245-1260. doi : 10.1051/ro/2018026. http://www.numdam.org/articles/10.1051/ro/2018026/
[1] Local Search in Combinatorial Optimization. Princeton University Press, New Jersey (2003). | DOI | MR | Zbl
and ,[2] The multi-period incremental service facility location problem. Comput. Oper. Res. 36 (2009) 1356–1375. | DOI | Zbl
, , and ,[3] Dynamic warehouse location analysis. J. Mark. Res. 5 (1968) 271–276. | DOI
,[4] The variable radius covering problem. Eur. J. Oper. Res. 196 (2009) 516–525. | DOI | MR | Zbl
, , and ,[5] The generalized maximal covering location problem. Comput. Oper. Res. 29 (2002) 563–581. | DOI | MR | Zbl
and ,[6] The gradual covering decay location problem on a network. Eur. J. Oper. Res. 151 (2003) 474–480. | DOI | MR | Zbl
, and ,[7] An algorithm for the capacitated, multi-commodity multi-period facility location problem. Comput. Oper. Res. 28 (2001) 411–427. | DOI | MR | Zbl
, , and ,[8] Generalized coverage models and public facility location. Pap. Reg. Sci. Assoc. 53 (1983) 117–135. | DOI
and ,[9] Multi-Objective Optimization Using Evolutionary Algorithms. Indian Institute of Technology, Kanpur, India (2001). | MR | Zbl
,[10] Locating multiple facilities in a planar competitive environment. J. Oper. Res. Soc. Jpn. 50 (2007) 1001–1014. | MR | Zbl
, and ,[11] Gradual location set covering with service quality. Socioecon. Plan. Sci. 43 (2009) 121–130. | DOI
and ,[12] Foundations of location analysis. International Series in Operations Research & Management Science, Part IV, Covering Problem, Springer (2011). | MR
and ,[13] Covering problem in facility location: a review. Comput. Ind. Eng. 62 (2011) 368–407. | DOI
, , , and ,[14] GAMS – A User’s Guide. Tutorial by Richard E. Rosenthal, Washington, DC, USA (2008).
,[15] GAMS – The Solver Manuals. Tutorial by Richard E. Rosenthal, Washington, DC, USA (2008).
,[16] The maximal expected coverage relocation problem for emergency vehicles. J. Oper. Res. Soc. 57 (2006) 22–28. | DOI | Zbl
, and ,[17] Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper. Res. 13 (1965) 462–475. | DOI | MR | Zbl
,[18] Maximal covering problem considering gradual coverage and variable coverage radius, in 7th International Conference of Industrial Engineering, Isfahan, Iran (2010).
and ,[19] A maximal covering location model in the presence of partial coverage. Comput. Oper. Res. 31 (2004) 1515–1526. | DOI | MR | Zbl
and ,[20] Optimization by simulated annealing. Science 220 (1983) 671–680. | DOI | MR | Zbl
, and ,[21] The maximum coverage location problem. SIAM J. Algebra Discrete Method 4 (1983) 253–261. | DOI | MR | Zbl
, and ,[22] An Interactive Evolutionary Algorithm for the Multi Objective Relocation Problem With Partial Coverage. Dissertation, Middle East Technical University (2011).
,[23] A Variable Neighborhood Search Procedure for the Combined Location With Partial Coverage and Selective Traveling Salesman Problem. Dissertation, Middle East Technical University (2010).
,[24] Present nonlinear model for solving the MCLP considering gradual coverage constraint and facility capacity, in International Conference on Nonlinear Modeling and Optimization (ICNMO), Amol, Iran (2012).
and ,[25] Solving the maximal covering location problem with heuristic concentration. Comput. Oper. Res. 35 (2008) 427–435. | DOI | MR | Zbl
, and ,[26] Hierarchical Maximal Covering Location Problem With Referral in the Presence of Partial Coverage. Dissertation, Middle East Technical University (2007).
,[27] The multi period location–allocation problem with relocation of facilities. Manag. Sci. 22 (1975) 57–65. | DOI | Zbl
and ,[28] The large-scale dynamic maximal covering location problem. Math. Comput. Model. 57 (2013) 710–719. | DOI | MR | Zbl
, and ,Cité par Sources :