×

zbMATH — the first resource for mathematics

Facility location for large-scale emergencies. (English) Zbl 1209.90236
Summary: In the \(p\)-center problem, it is assumed that the facility located at a node responds to demands originating from the node. This assumption is suitable for emergency and health care services. However, it is not valid for large-scale emergencies where most of facilities in a whole city may become functionless. Consequently, residents in some areas cannot rely on their nearest facilities. These observations lead to the development of a variation of the \(p\)-center problem with an additional assumption that the facility at a node fails to respond to demands from the node. We use dynamic programming approach for the location on a path network and further develop an efficient algorithm for optimal locations on a general network.

MSC:
90B85 Continuous location
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Caprara, A., Fischetti, M., & Toth, P. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98, 353–371. · Zbl 0974.90006
[2] Chalmet, L., Leiserson, T., & Saunders, P. (1982). Network model for building evacuation. Management Science, 28, 86–105.
[3] Daskin, M. (2000). A new approach to solving the vertex P-center problem to optimality: algorithm and computational results. Communications of the Operations Research Society of Japan, 45(9), 428–436.
[4] Francis, R., & Chalmet, L. (1984). A negative exponential solution to an evacuation problem (Research Report No. 84-86). National Bureau of Standards, Center for Fire Research.
[5] Gary, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: W.H. Freeman. · Zbl 0411.68039
[6] Handler, G. (1990). p-center problems. In P. B. Mirchandani & R. L. Francis (Eds.), Discrete Location Theory (pp. 305–347). New York: Wiley. · Zbl 0731.90049
[7] Hoppe, B., & Tardos, E. (1994). Polynomial time algorithms for some evacuation problems. In Proceedings of the 5th annual ACM-SIAM symposium on discrete algorithms (pp. 433–441). · Zbl 0867.90048
[8] Ilhan, T., Ozsoy, F., & Pinar, M. (2002). An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems (Technical report). Available at http://www.optimization-online.org/DB_HTML/2002/12/588.html .
[9] Jia, H., Ordonez, F., & Dessouky, M. (2007a). A modeling framework for facility location of medical services for large-scale emergencies. IIE Transactions, 39(1), 41–55.
[10] Jia, H., Ordonez, F., & Dessouky, M. (2007b). Solution approaches for facility location of medical supplies for large-scale emergencies. Computers & Industrial Engineering, 52, 257–276.
[11] Kariv, O., & Hakimi, S. (1979). An algorithmic approach to network location problems. I: the P-centers. SIAM Journal on Applied Mathematics, 37, 513–538. · Zbl 0432.90074
[12] Lu, Q., Huang, Y., & Shekhar, S. (2003). Evacuation planning: a capacity constrained routing approach. In Proceedings of the first NSF/NIJ symposium on intelligence and security informatics (pp. 111–125), June 2003.
[13] Lu, Q., George, B., & Shekhar, S. (2006). Capacity constrained routing algorithms for evacuation route planning (Technical Report). Department of Computer Science and Engineering, University of Minnesota, May 2006.
[14] MacReady, N. (2008). After the storm. Neurology Lancet, 7(9), 772–773.
[15] Tansel, B., Francis, R., & Lowe, T. (1983). Location on networks: a survey. Part I: The p-center an p-median problems. Management Science, 29, 482–497. · Zbl 0513.90022
[16] Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19, 1363–1373. · Zbl 0224.90048
[17] USGS (U.S. Geological Survey) (2008). Magnitude 7.9–Eastern Sichuan, China. http://earthquake.usgs.gov/eqcenter/eqinthenews/2008/us2008ryan/#details .
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.