Modeling and solution of maximal covering problem considering gradual coverage with variable radius over multi-periods

Eydi, Alireza; Mohebi, Javad

RAIRO - Operations Research - Recherche Opérationnelle, Tome 52 (2018) no. 4-5, pp. 1245-1260.

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.

[1] E. Aarts and J.K. Lenstra, Local Search in Combinatorial Optimization. Princeton University Press, New Jersey (2003). | DOI | MR | Zbl

[2] M. Albareda-Sambola, E. Fernandez, Y. Hinojosa and J. Puerto, The multi-period incremental service facility location problem. Comput. Oper. Res. 36 (2009) 1356–1375. | DOI | Zbl

[3] R.H. Ballou, Dynamic warehouse location analysis. J. Mark. Res. 5 (1968) 271–276. | DOI

[4] O. Berman, Z. Drezner, D. Krass and G.O. Wesolowsky, The variable radius covering problem. Eur. J. Oper. Res. 196 (2009) 516–525. | DOI | MR | Zbl

[5] O. Berman and D. Krass, The generalized maximal covering location problem. Comput. Oper. Res. 29 (2002) 563–581. | DOI | MR | Zbl

[6] O. Berman, D. Krass and Z. Drezner, The gradual covering decay location problem on a network. Eur. J. Oper. Res. 151 (2003) 474–480. | DOI | MR | Zbl

[7] C. Canel, B.M. Khumawala, J. Law and A. Loh, An algorithm for the capacitated, multi-commodity multi-period facility location problem. Comput. Oper. Res. 28 (2001) 411–427. | DOI | MR | Zbl

[8] R.L. Church and K.L. Roberts, Generalized coverage models and public facility location. Pap. Reg. Sci. Assoc. 53 (1983) 117–135. | DOI

[9] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms. Indian Institute of Technology, Kanpur, India (2001). | MR | Zbl

[10] Z. Drezner, A. Suzuki and T. Drezner, Locating multiple facilities in a planar competitive environment. J. Oper. Res. Soc. Jpn. 50 (2007) 1001–1014. | MR | Zbl

[11] H.A. Eiselt and V. Marianov, Gradual location set covering with service quality. Socioecon. Plan. Sci. 43 (2009) 121–130. | DOI

[12] H.A. Eiselt and V. Marianov, Foundations of location analysis. International Series in Operations Research & Management Science, Part IV, Covering Problem, Springer (2011). | MR

[13] R.Z. Farahani, N. Asghari, N. Heidari, M. Hosseinini and M. Goh, Covering problem in facility location: a review. Comput. Ind. Eng. 62 (2011) 368–407. | DOI

[14] Gams Development Corporation, GAMS – A User’s Guide. Tutorial by Richard E. Rosenthal, Washington, DC, USA (2008).

[15] Gams Development Corporation, GAMS – The Solver Manuals. Tutorial by Richard E. Rosenthal, Washington, DC, USA (2008).

[16] M. Gendreau, G. Laporte and F. Semet, The maximal expected coverage relocation problem for emergency vehicles. J. Oper. Res. Soc. 57 (2006) 22–28. | DOI | Zbl

[17] S.L. Hakimi, 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] M.S. Jabal Ameli and B. Bankian Tabrizi, Maximal covering problem considering gradual coverage and variable coverage radius, in 7th International Conference of Industrial Engineering, Isfahan, Iran (2010).

[19] O. Karasakal and E.K. Karasakal, A maximal covering location model in the presence of partial coverage. Comput. Oper. Res. 31 (2004) 1515–1526. | DOI | MR | Zbl

[20] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing. Science 220 (1983) 671–680. | DOI | MR | Zbl

[21] N. Megiddo, E. Zemel and S.L. Hakimi, The maximum coverage location problem. SIAM J. Algebra Discrete Method 4 (1983) 253–261. | DOI | MR | Zbl

[22] B. Orbay, An Interactive Evolutionary Algorithm for the Multi Objective Relocation Problem With Partial Coverage. Dissertation, Middle East Technical University (2011).

[23] F. Rahim, A Variable Neighborhood Search Procedure for the Combined Location With Partial Coverage and Selective Traveling Salesman Problem. Dissertation, Middle East Technical University (2010).

[24] M.V. Rashidi and A. Jafari, 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).

[25] C. Revelle, M. Scholssberg and J. Williams, Solving the maximal covering location problem with heuristic concentration. Comput. Oper. Res. 35 (2008) 427–435. | DOI | MR | Zbl

[26] O. Toreyen, Hierarchical Maximal Covering Location Problem With Referral in the Presence of Partial Coverage. Dissertation, Middle East Technical University (2007).

[27] G.O. Wesolowsky and W.G. Trucott, The multi period location–allocation problem with relocation of facilities. Manag. Sci. 22 (1975) 57–65. | DOI | Zbl

[28] M.H.F. Zarandi, S. Davari and S.A.H. Sisakht, The large-scale dynamic maximal covering location problem. Math. Comput. Model. 57 (2013) 710–719. | DOI | MR | Zbl