Comparative analysis of algorithms for calculating arrival times of emergency vehicles

• Autorzy: Płokita I. , Piórkowski A. , Lupa M.

Identyfikatory

DOI

10.4467/21995923GP.16.009.5485

Warianty tytułu

PL

Analiza porównawcza algorytmów wyznaczania czasów dojazdów pojazdów ratunkowych

• Języki publikacji: EN

Abstrakty

EN

The problem discussed in this article covers the issue of the generation and computational complexity of an arrival time map of emergency vehicles (ambulances). Finding the optimal (fastest) route between two points is a complex and time-consuming task. Moreover, the discussed issues are identical to the problems faced by dispatchers from Malopolska Medical Emergency. Therefore, the aim was to develop algorithms to reduce time calculations, based on the reduction of their number only to the points where ambulances are able to reach within the specifi ed time. There were compared three types of algorithms, taking into account their time and computational complexity. The result of the research was to identify algorithms, which depending on the adopted criteria allow to achieve optimal results.

PL

Problemem poruszanym w niniejszym artykule jest czas, w jakim obliczana jest kompletna mapa czasów dojazdów pojazdów ratunkowych (ambulansów) dla zadanej siatki. Znalezienie optymalnej (najszybszej) trasy między dwoma punktami jest problemem złożonym i czasochłonnym. Co więcej, poruszane zagadnienia wynikają z potrzeb i problemów, z którymi zmagają się dyspozytorzy Małopolskiego Ratownictwa Medycznego. Wobec tego, intencją autorów było opracowanie metod pozwalających na skrócenie czasu wykonywania obliczeń, bazując na redukcji ich liczby wyłącznie do punktów, do których ambulans jest w stanie dotrzeć w zadanym czasie. Porównano trzy typy algorytmów, uwzględniając ich złożoność czasową i obliczeniową. W rezultacie wskazano metody, które – w zależności od przyjętego kryterium – pozwalają osiągnąć optymalne wyniki.

Słowa kluczowe

EN

GIS; network analysis; optimization; arrival time calculation

PL

GIS; analiza sieciowa; optymalizacja; obliczanie czasów dojazdu

• Wydawca: Polska Akademia Umiejętności
• Czasopismo: Geoinformatica Polonica
• Rocznik: 2016
• Tom: T. 15
• Strony: 85--91
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Płokita I.

• AGH University of Science and Technology, Faculty of Geology, Geophysics and Environmental Protection, Department of Geoinformatics and Applied Computer Science

autor

Piórkowski A.

• AGH University of Science and Technology, Faculty of Geology, Geophysics and Environmental Protection, Department of Geoinformatics and Applied Computer Science

autor

Lupa M.

• AGH University of Science and Technology, Faculty of Geology, Geophysics and Environmental Protection, Department of Geoinformatics and Applied Computer Science

Bibliografia

• 1. Aho A., Hopcroft J., Ullman J.: Algorytmy i struktury danych, Helion, 2003, pp. 217–229
• 2. Bell, M. and Iida, Y. (1997) Transportation Network Analysis John Wiley, Chichester
• 3. Bellman R.: On a routing problem, Quarterly of Applied Mathematics, nr 16, 1958, pp. 87–90
• 4. Bernas M., Wiśniewska J.: Quantum road traffi c model for ambulance travel time esti-mation. Journal of Medical Informatics & Technologies, Vol. 22, 2013, pp. 257–264
• 5. Bielecka E., Filipczak A., 2010: Zasady opracowywania map dostępności. Roczniki Geomatyki 2010, t. 8, z. 6: 29–38, PTIP, Warszawa
• 6. Cichociński P., Dębińska E.: Badanie Dostępności Komunikacyjnej Wybranej Lokalizacji z Wykorzystaniem Funkcji Analiz Sieciowych. Roczniki Geomatyki 2012, t. 10, z. 6(54), PTIP, Warszawa
• 7. Curtin M. K.: Network Analysis in Geographic Information Science: Review, Assessment, and Projection. Cartography and Geographic Information Science 34(2):103–111, April 2007
• 8. Dijkstra E. W.: A note on two problems in connexion with graphs, Numerische Mathematik, nr 1, 1959, pp. 269–271
• 9. Diller G.P., Kempny A., Piorkowski A., Grubler M., Swan L., Baumgartner H., Dimopoulos K., Gatzoulis M.A.: Choice and competition between adult congenital heart disease centers: evidence of considerable geographical disparities and association with clinical or academic results. Circulation: Cardiovascular Quality and Outcomes, Vol. 7(2), 2014, pp. 285–291
• 10. Fischer M. M.: GIS and Network Analysis. Handbook of Transport Geography and Spatial Systems, Publisher: Elsevier, Editors: Hensher D, Button K, Haynes K, Stopher P, pp. 391–408
• 11. Hart P. E., Nilsson N. J., Raphael B.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics, nr 4, 1986, pp. 100–107
• 12. Robusto C.: The Cosine-Haversine Formula, The American Mathematical Monthly, 1957, pp. 38–40
• 13. Kozieł G.: Algorytmy wyznaczanie optymalnej trasy przejazdu, Logistyka, nr 3, 2014, pp. 3206–3212
• 14. Łukasik P., Piórkowski A.: Opracowanie Charakterystyk Prędkości Karetek Na Podstawie Danych Rzeczywistych. Studia Informatica, vol. 37, number 1 (123), 2016
• 15. Mwemezi J., Huang Y.: Optimal Facility Location on Spherical Surfaces: Algorithm and Application, New York Science Journal, nr 4, 2011, pp. 21–28
• 16. Simić D., Simić S.: Hybrid Artifi cial Intelligence Approaches on Vehicle Routing Problem in Logistics Distribution. Hybrid Artifi cial Intelligent Systems Volume 7208 of the series Lecture Notes in Computer Science pp. 208–220

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)