×

Queueing maximal covering location-allocation problem: an extension with M/G/1 queueing systems. (English) Zbl 1233.90123

Summary: We consider the queueing maximal covering location-allocation problem (QM-CLAP) with an M/G/1 queueing system. We first formulate the problem as a binary quadratic programming problem and then propose a new solution procedure based on decomposition of the problem into smaller binary quadratic sub-problems. The heuristic procedure GRASP is used to solve the sub-problems, as well as the entire model. Some computational results are also presented.

MSC:

90B22 Queues and service in operations research
90B80 Discrete location and assignment
90C20 Quadratic programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

GRASP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. Church and C. ReVelle, “The maximal covering location problem,” Papers of the Regional Science Association, vol. 32, no. 1, pp. 101-118, 1974. · doi:10.1007/BF01942293
[2] C. ReVelle, “Review, extension and prediction in emergency service siting models,” European Journal of Operational Research, vol. 40, no. 1, pp. 58-69, 1989. · Zbl 0667.90033 · doi:10.1016/0377-2217(89)90272-5
[3] D. A. Schilling, V. Jayaraman, and R. Barkhi, “A review of covering problems in facility location,” Location Science, vol. 1, no. 1, pp. 25-55, 1993. · Zbl 0923.90108
[4] V. Marianov and C. ReVelle, “The queueing maximal availability location problem: a model for the siting of emergency vehicles,” European Journal of Operational Research, vol. 93, no. 1, pp. 110-120, 1996. · Zbl 0912.90195 · doi:10.1016/0377-2217(95)00182-4
[5] L. Brotcorne, G. Laporte, and F. Semet, “Ambulance location and relocation models,” European Journal of Operational Research, vol. 147, no. 3, pp. 451-463, 2003. · Zbl 1037.90554 · doi:10.1016/S0377-2217(02)00364-8
[6] V. Marianov and D. Serra, “Location problems in the public sector,” in Facility Location: Application and Theory, Z. Drezner and H. W. Hamacher, Eds., pp. 119-150, Springer, 2004. · Zbl 1061.90073
[7] J. B. Goldberg, “Operations research models for the deployment of emergency services vehicles,” EMS Management Journal, vol. 1, no. 1, pp. 20-39, 2004.
[8] C. S. ReVelle, H. A. Eiselt, and M. S. Daskin, “A bibliography for some fundamental problem categories in discrete location science,” European Journal of Operational Research, vol. 184, no. 3, pp. 817-848, 2008. · Zbl 1141.90025 · doi:10.1016/j.ejor.2006.12.044
[9] E. Erkut, A. Ingolfsson, T. Sim, and G. Erdo\vgan, “Computational comparison of five maximal covering models for locating ambulances,” Geographical Analysis, vol. 41, no. 1, pp. 43-65, 2009. · doi:10.1111/j.1538-4632.2009.00747.x
[10] O. Berman, R. C. Larson, and S. S. Chiu, “Optimal server location on a network operating as an M/G/1 queue,” Operations Research, vol. 33, no. 4, pp. 746-771, 1985. · Zbl 0576.90031 · doi:10.1287/opre.33.4.746
[11] O. Berman and R. R. Mandowsky, “Location-allocation on congested networks,” European Journal of Operational Research, vol. 26, no. 2, pp. 238-250, 1986. · Zbl 0595.90013 · doi:10.1016/0377-2217(86)90185-2
[12] O. Berman, R. C. Larson, and C. Parkan, “The stochastic queue p-median location problem,” Transportation Science, vol. 21, pp. 207-216, 1987. · Zbl 0624.90025 · doi:10.1287/trsc.21.3.207
[13] R. Batta and O. Berman, “A location model for a facility operating as an M/G/k queue,” Networks, vol. 19, pp. 717-728, 1989. · Zbl 0677.90023 · doi:10.1002/net.3230190609
[14] R. Batta, “A queueing-location model with expected service time dependent queueing disciplines,” European Journal of Operational Research, vol. 39, no. 2, pp. 192-205, 1989. · Zbl 0674.90031 · doi:10.1016/0377-2217(89)90192-6
[15] V. Marianov and C. Revelle, “The queuing probabilistic location set covering problem and some extensions,” Socio-Economic Planning Sciences, vol. 28, no. 3, pp. 167-178, 1994. · doi:10.1016/0038-0121(94)90003-5
[16] V. Marianov and D. Serra, “Probabilistic, maximal covering location-allocation models from congested systems,” Journal of Regional Science, vol. 38, no. 3, pp. 401-424, 1998. · doi:10.1111/0022-4146.00100
[17] M. Jamil, A. Baveja, and R. Batta, “The stochastic queue center problem,” Computers and Operations Research, vol. 26, no. 14, pp. 1423-1436, 1999. · Zbl 0967.90053 · doi:10.1016/S0305-0548(99)00050-7
[18] F. Silva and D. Serra, “Locating emergency services with different priorities: The priority queuing covering location problem,” Journal of the Operational Research Society, vol. 59, no. 9, pp. 1229-1238, 2008. · Zbl 1176.90363 · doi:10.1057/palgrave.jors.2602473
[19] F. M. Moghadas and H. T. Kakhki, “Maximal covering location-allocation problem with M/M/k queueing system and side constraint,” Iranian Journal of Operations Research, vol. 2, no. 2, pp. 1-16, 2011. · Zbl 1233.90123
[20] O. Berman and D. Krass, “Facility location problems with stochastic demands and congestion,” in Facility Location: Application and Theory, Z. Drezner and H. W. Hamacher, Eds., pp. 329-371, Springer, 2004. · Zbl 1061.90068
[21] F. D. A. Corrêa and L. A. N. Lorena, “Using the constructive genetic algorithm for solving the probabilistic maximal covering location-allocation problem,” in Proceedings of the Workshop on Computational Intelligence, SBRN, 2006.
[22] F. D. A. Corrêa, A. A. Chaves, and L. A. N. Lorena, “Hybrid heuristics for the probabilistic maximal covering location-allocation problem,” Operational Research, vol. 7, no. 3, pp. 323-344, 2008.
[23] F. A. Corrêa, L. A. N. Lorena, and G. M. Ribeiro, “A decomposition approach for the probabilistic maximal covering location-allocation problem,” Computers and Operations Research, vol. 36, no. 10, pp. 2729-2739, 2009. · Zbl 1160.90556 · doi:10.1016/j.cor.2008.11.015
[24] L. Kleinrock, Queueing Systems: Theory, vol. 1, John Wiley & Sons, 1975. · Zbl 0334.60045
[25] H. T. Kakhki and F. M. Moghadas, “A semidefinite programming relaxation for the queueing covering location problem with an M/G/1 system,” in Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, pp. 231-236, CIRM, April 2010.
[26] R. Baldacci, E. Hadjiconstantinou, V. Maniezzo, and A. Mingozzi, “A new method for solving capacitated location problems based on a set partitioning approach,” Computers and Operations Research, vol. 29, no. 4, pp. 365-386, 2002. · Zbl 0994.90087 · doi:10.1016/S0305-0548(00)00072-1
[27] L. A. N. Lorena and E. L. F. Senne, “Local search heuristics for capacitated p-median problems,” Networks and Spatial Economics, vol. 3, no. 4, pp. 407-419, 2003. · doi:10.1023/A:1027353520175
[28] H. D. Sherali and W. P. Adams, “A tight linearization and an algorithm for zero-one quadratic programming problems,” Management Science, vol. 32, no. 10, pp. 1274-1290, 1986. · Zbl 0623.90054 · doi:10.1287/mnsc.32.10.1274
[29] T. A. Feo and M. G. C. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,” Operations Research Letters, vol. 8, no. 2, pp. 67-71, 1989. · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3
[30] T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search procedures,” Journal of Global Optimization, vol. 6, no. 2, pp. 109-133, 1995. · Zbl 0822.90110 · doi:10.1007/BF01096763
[31] M. G. C. Resende, “Computing approximate solutions of the maximum covering problem with GRASP,” Journal of Heuristics, vol. 4, no. 2, pp. 161-177, 1998. · Zbl 0913.90202 · doi:10.1023/A:1009677613792
[32] P. Festa and M. G. C. Resende, “An annotated bibliography of GRASP-part I: algorithms,” International Transactions in Operational Research, vol. 16, pp. 1-24, 2009. · Zbl 1153.90553 · doi:10.1111/j.1475-3995.2009.00663.x
[33] P. Festa and M. G. C. Resende, “An annotated bibliography of GRASP-spart II: applications,” International Transactions in Operational Research, vol. 16, pp. 131-172, 2009. · Zbl 1168.90582 · doi:10.1111/j.1475-3995.2009.00664.x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.