A multi-period expected covering location model: formulation, heuristic solution and application

• Autorzy: Rajagopolan H. K. , Saydam C. , Xiao J.

Warianty tytułu

PL

Wielookresowy model lokalizacyjny z uwzględnieniem oczekiwanego pokrycia powierzchni obszaru obsługi: sformułowanie problemu, rozwiązanie heurystyczne i zastosowanie

• Języki publikacji: EN

Abstrakty

EN

Emergency response administrators often face the difficult task of locating a limited number of ambulances in a manner that will yield the best service to a constituent population. Demand for ambulances is known to fluctuate spatially and temporally by day of the week, and even time of the day. We formulate a model to determine the minimum number of ambulances and their locations for each time interval with significant changes in demand is anticipated while meeting the expected coverage requirements. We develop a heuristic search algorithm based on reactive tabu search and present computational statistics on experimental data. We apply the model to Charlotte, NC, validate the findings via a simulation model.

PL

Kierownictwo (Admintracja) pogotowia ratunkowego staje często przed trudnym zadaniem rozlokowania ograniczonej liczby karetek pogotowia w taki sposób, aby zapewnić jak najwyższy poziom usług oferowanych rozważanej społeczności. Popyt na karetki pogotowia zmienia się (fluktuuje) zarówno w czasie, jak i w przestrzeni. Zmiany czasowe dotyczą zarówno dnia tygodnia, jak i pory dnia. Autorzy formułują model pozwalający na określenie minimalnej liczby karetek pogotowia oraz ich lokalizacji dla każdego przedziału czasowego. Przewidywana liczba karetek pogotowia jest określana z uwzględnieniem istotnych zmian popytu oraz wymagań dotyczących pokrycia obszaru obsługi. Autorzy opracowują heurystyczny algorytm przeszukiwania oparty na reaktywnej metaheurystyce przeszukiwania tabu i prezentują statystyczne rezultaty obliczeń z wykorzystaniem danych eksperymentalnych. Opracowany model został zastosowany w Charlotte (północna Karolina - USA), a uzyskane rezultaty zostały zweryfikowane za pomocą modelu symulacyjnego.

Słowa kluczowe

EN

ambulances; location model; simulation model

PL

pogotowie ratunkowe; karetki pogotowia; model lokalizacyjny; model symulacyjny

• Wydawca: Warsaw University of Technology, Faculty of Transport
• Czasopismo: Archives of Transport
• Rocznik: 2008
• Tom: Vol. 20, iss. 1-2
• Strony: 113--131
• Opis fizyczny: Bibliogr. 38 poz., tab.

Twórcy

autor

Rajagopolan H. K.

autor

Saydam C.

autor

Xiao J.

• School of Business, Francis Marion University, Florence

Bibliografia

• 1. Aytug H., Saydam C.: Solving large-scale maximum expected covering location problems by genetic algorithms: A comparative study. European Journal of Operational Research, 2002, 141, p. 480-494.
• 2. Ball M.O., Lin L.E: A reliability model applied to emergency service vehicle location. Operations Research, 1993,41, p. 18-36.
• 3. Batta R., Dolan J.M., Krishnamurthy N.N.: The Maximal Expected Covering Location Problem: Revisited. Transportation Science, 1989, 23, p. 277-287.
• 4. Battiti R., Tecchiolli G.: The Reactive Tabu Search. Journal on Computing, 1994, 6(2).
• 5. Beasley J.E., Chu P.C.: A Genetic Algorithm for the Set Covering Problem. European Journal of Operational Research, 1996, 94, p. 392-404.
• 6. Benati S., Laporte G.: Tabu Search algorithms for the (r/Xp)-medianoid and (r/p) centroid problems. Location Science, 1994, 2, p. 193-204.
• 7. Brotcorne L., Laporte G., Semet E: Fast Heuristics for Large Scale Covering Location Problems. Computers and Operations Research, 2002, 29, p. 651-665.
• 8. Brotcorne, L., Laporte, G., and Semet, F., Ambulance location and relocation models. European Journal of Operational Research, 2003, 147, p. 451-463.
• 9. Burwell T.H., Jarvis J.P., McKnew M.A.: Modeling Co-located Servers and Dispatch Ties in the Hypercube Model. Computers & Operations Research, 1993, 20, p. 113-119.
• 10. Chan Y: Location Theory and Decision Analysis. South Western College Publishing, Cincinnati, 200l.
• 11. Daskin M.S.: A maximal expected covering location model: Formulation, properties, and heuristic solution. Transportation Science, 1983, 17, p. 48-69.
• 12. Daskin M.S.: Network and Discrete Location. John Wiley & Sons Inc., New York, 1995.
• 13. Galvao R.D., Chiyoshi F.Y, Morabito R: Towards Unified Formulations and Extensions of Two Classical Probabilistic Location Models. Computers & Operations Research, 2005,32(1), p. 15-33.
• 14. Gendreau M., Laporte G., Semet E: Solving an Ambulance Location Model by Tabu Search. Location Science, 1997, 5(2), p. 75-88.
• 15. Gendreau M., Laporte G., Semet E: A dynamic model and parallel tabu search heuristic for real time ambulance relocation. Parallel Computing, 2001, 27, p. 1641-1653.
• 16. Goldberg J.B.: Operations Research Models for the Deployment of Emergency Services Vehicles. EMS Management Journal, 2004, 1(1), p. 20-39.
• 17. Hillier ES., Lieberman G.J.: Introduction to Operations Research. Eighth ed. McGraw Hill, New York, 2005.
• 18. ILOG, ILOG Cplex 7.0 Reference Manual. ILOG, 2000.
• 19. Jaramillo J., Bhadury J., Batta R.: On the use of genetic algorithms to solve location problems. Computers and Operations Research, 2002, 29, p. 761-779.
• 20. Jarvis J.P.: Approximating the equilibrium behavior of multi-server loss systems. Management Science, 1985, 31, p. 235-239.
• 21. Karasakal O., Karasakal E.K: A maximal covering location model in the presence of partial coverage. Computers & Operations Research, 2004, 31, p. 1515-1526.
• 22. Larson R.C.: A Hypercube Queuing Model for Facility Location and Redistricting in Urban Emergency Services. Computers and Operations Research, 1974, l, p. 67-95.
• 23. Larson R.C.: Approximating the performance of urban emergency service systems. Operations Research, 1975, 23, p. 845-868.
• 24. Larson R.C.: Urban Operations Research. Englewood Cliffs, N. J: Prentice-Hall, 1981.
• 25. Marianov V., ReVelle C.: The Queuing Probabilistic Location Set Covering Problem and Some Extensions. Socio-Economic Planning Sciences, 1994,28: p. 167-178.
• 26. Marianov V., ReVelle C.: The Queueing Maximal Availability Location Problem: A model for sitting of emergency vehicles. European Journal of Operational Research, 1996, 93, p. 110-120.
• 27. Owen S.H., Daskin M.S.: Strategic Facility Location: A Review. European Journal of Operational Research, 1998, 111, p. 423-447.
• 28. Penner J.: Interview with the Charlotte MEDIC. H.K Rajagopalan, Editor. Charlotte, 2004.
• 29. Rajagopalan H.K, Vergara F.E., Saydam C., Xiao J.: Developing Effective Meta-Heuristics For A Probabilistic Location Model Via Experimental Design. European journal of operational research, 2007, 177(2), p. 365-377.
• 30. Repede J., Bernardo J.: Developing and validating a decision support system for locating emergency medical vehicles in Lousville, Kentucky. European Journal of Operational Research, 1994, 75, p. 567-581.
• 31. Re Velle C.: Review, extension and prediction in emergency sitting models. European Journal of Operational Research, 1989, 40, p. 58-69.
• 32. ReVelle C., Hogan K: The Maximum Reliability Location Problem and alpha-reliable p-center problems: derivatives of the probabilistic location set covering problem. Annals of Operations Research, 1989, 18, p. 155-174.
• 33. ReVelle C., Hogan K: The maximum availability location problem. Transportation Science, 1989, 23, p. 192-200.
• 34. Saydam C., Repede J., Burwell T.: Accurate Estimation of Expected Coverage: A Comparative Study. Socio-Economic Planning Sciences, 1994, 28(2), p. 113-120.
• 35. Saydam C., Aytug H.: Accurate estimation of expected coverage: revisited. Socio-Economic Planning Sciences, 2003, 37, p. 69-80.
• 36. Schilling D.A., Jayaraman V., Barkhi R: A Review of Covering Problems in Facility Location. Location Science, 1993, 1(1), p. 25-55.
• 37. Takeda R.A., Widmer J.A., Morabito R.: Analysis of ambulance decentralization in an urban medical emergency service using the hypercube queuing model. Computers & Operations Research, 2007, 34, p. 727-741.
• 38. Zaki A.S., Cheng H.K., Parker B.R: A Simulation Model for the Analysis and Management of An Emergency Service System. Socio-Economic Planning Sciences, 1997, 31(3), p. 173-189.