Wyszukiwanie połączeń w komunikacji miejskiej

• Autorzy: Kisielewski P. , Kołodziej R.

Warianty tytułu

EN

Connection search in city transit

• Języki publikacji: PL

Abstrakty

PL

Artykuł poświęcony jest tematyce wyszukiwania połączeń w sieciach komunikacji miejskiej. Wyszukiwanie to jest o wiele bardziej złożone, aniżeli w przypadku typowej nawigacji w ruchu transportu indywidualnego, gdyż wymaga uwzględnienia rozkładu jazdy pojazdów oraz zapewnienie minimalnego czasu na przesiadkę. Przekłada się to na większe zapotrzebowanie na moc obliczeniową, oraz większy nacisk na optymalizację. W artykule pokrótce przedstawiono trzy wcześniej istniejące algorytmy, publikowane w ramach opracowań naukowych, oraz przeprowadzono dyskusję nad możliwością ich implementacji jako uniwersalnej wyszukiwarki w języku programowania PHP. W rezultacie powstała adaptacja, łącząca przedstawione podejścia w zoptymalizowany algorytm, wykorzystujący jedne z podstawowych cech transportu zbiorowego: powtarzalność kursowania na stałych liniach oraz zbliżone czasy przejazdu w ciągu całej doby, w celu przeprowadzenia zabiegów heurystycznych, przyspieszających właściwe wyszukiwanie. W podsumowaniu sformułowano obserwacje zebrane w trakcie pracy nad programem oraz przedstawiono kierunki dalszych badań i rozwoju tematyki.

EN

The paper covers searching for optimal connection in city public transit networks. Such a search is by definition much more complex than a simple routing in car or pedestrian navigation. The two would essentially involve using Dijkstra-like graph shortest path algorithm, while numerous limitations have to be considered while performing such an operation in transit networks, comprising mostly service availability, but nonetheless including fares, transfer time spans, as well as maximum number of transfers. Three different algorithms, which were previously published by various academic entities, are briefly described and analysed. Each of them differs in terms of complexity, approach and the results returned, thus possibility of their implementation in PHP language is discussed. As the outcome project one combined algorithm with numerous alterations necessary for the given environment is presented. The summarising chapter brings conclusions and observations noted while building the program, as well as possible fields of further investigation and research.

Słowa kluczowe

PL

algorytm; wyszukiwanie połączeń; publiczna komunikacja miejska; problem najkrótszej drogi

EN

algorithm; connection search; city public transport; shortest path problem

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2015
• Tom: nr 4
• Strony: 4043--4052, CD2
• Opis fizyczny: Bibliogr. 8 poz., tab.

Twórcy

autor

Kisielewski P.

• Politechnika Krakowska, Wydział Mechaniczny, Zakład Systemów Logistycznych, Kraków, Al. Jana Pawła II 37

autor

Kołodziej R.

Bibliografia

• 1. Tong C. O., Wong S. C., A stochastic transit assignment model using a dynamic schedule-based network. Transportation Research Part B, nr 33, s. 107-121, 1999.
• 2. Bast H., Carlsson E., Eigenwillig A., Geisberger R., Harrelson C., Raychev V., Viger F., Fast Routing in Very Large Public Transportation Networks using Transfer Patterns. ESA'10 Proceedings of the 18th annual European conference on Algorithms: Part I, Berlin-Heidelberg 2010.
• 3. Deo N., Teoria grafów i jej zastosowania w technice i informatyce. PWN. Warszawa 1980.
• 4. Friedrich M., Hofsäβ I., Wekeck S., Timetable-based Transit Assignemnt Using Branch & Bound Techniques. Transportation Research Records, nr 1752, s. 100-107. 2001.
• 5. Starowicz W., Jakość przewozów w miejskim transporcie zbiorowym. Wydawnictwo Politechniki Krakowskiej. Kraków 2007.
• 6. Choi W., Argerich L., Coggershall J., Egervari K., Giesler M., Greant Z., Hill A., Hubbard C., Moore J., O'Dell D., Parise J., Rawat H., Sani T., Scollo C., Thomas D., Ullman C., PHP4. Zaawansowane programowanie. Wydawnictwo Helion. Gliwice 2003.
• 7. Bojda K., Molecki B., Internetowa informacja pasażerska. Transport Miejski i Regionalny, 06/2008.
• 8. The PHP Group, „PHP Manual”, http://www.php.net/manual/en/.