Volume 2 Issue 2 pp. 439-448 Spring, 2011


A Simulated Annealing method to solve a generalized maximal covering location problem


Mohammad Saied Jabalameli Behzad Bankian Tabrizi and Mohammad Moshref Javadi


The maximal covering location problem (MCLP) seeks to locate a predefined number of facilities in order to maximize the number of covered demand points. In a classical sense, MCLP has three main implicit assumptions: all or nothing coverage, individual coverage, and fixed coverage radius. By relaxing these assumptions, three classes of modelling formulations are extended: the gradual cover models, the cooperative cover models, and the variable radius models. In this paper, we develop a special form of MCLP which combines the characteristics of gradual cover models, cooperative cover models, and variable radius models. The proposed problem has many applications such as locating cell phone towers. The model is formulated as a mixed integer non-linear programming (MINLP). In addition, a simulated annealing algorithm is used to solve the resulted problem and the performance of the proposed method is evaluated with a set of randomly generated problems.


DOI: 10.5267/j.ijiec.2011.01.003

Keywords: Maximal covering location problem, Gradual cover, Cooperative cover, Variable radius, Simulated annealing
References

Berlin, G. N., & Liebman, J. C. (1974). Mathematical analysis of emergency ambulance location. Socio-Economic Planning Sciences, 8, 323-328.

Berman, O., Drezner, Z., & Krass, D. (2010). Generalized coverage: New developments in covering location models. Computers & Operations Research, 37, 1675-1687.

Berman, O. & Krass, D. (2002). The generalized maximal covering location problem. Computers and Operations Research, 29, 563–591.

Berman, O., Krass, D., & Drezner, Z. (2003). The gradual covering decay location problem on a network. European Journal of Operational Research, 151, 474–80.

Berman, O., Kalcsics, J., Krass, D., & Nickel, S. (2009). The ordered gradual covering location problem on a network. Discrete Applied Mathematics, 175, 689-707.

Berman, O., Drezner, Z., & Krass, D. (2010). Cooperative cover location problems: the planar case. IIE Transactions, 42, 232- 246.

Berman, O., Drezner, Z., & Krass, D. (2009). The variable radius covering problem. European Journal of Operational Research, 196, 516-525.

Church, R. L., & ReVelle, C. (1974). The maximal covering location problem. Papers of Regional Science Association, 32, 101-118.

Church, R. L., & Roberts, K. L. (1984). Generalized coverage models and public facility location. Papers of the Regional Science Association, 53, 117-135.

Drezner, T., Drezner, Z. & Goldstein, Z. (2010). A stochastic gradual cover location problem. Naval Research Logistics, 57, 367-372.

Eiselt, H. A. & Marianov, V. (2009). Gradual location set covering with service quality. Socio-Economic Planning Sciences, 43(2), 121-130.

Kirkpatrick, S., Gelatt, C.D., & and Vecchi, M.P. (1983). Optimization by simulated annealing. Science, 220, 671-680.

ReVelle, C., Toregas, C., & Falkson, L. (1976). Applications of the location set covering problem. Geographical Analysis, 8, 65-76.

Toregas, C., Swain. R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19, 1363-1373.