Algorytm wyszukiwania trasy w sieci komunikacji miejskiej

• Autorzy: Maciej Kowalewski , Grzegorz Krzymiński

Warianty tytułu

Calculation of the Optimal Travel Route for Public Transport in Poznań

• Języki publikacji: PL

Abstrakty

W realizacji projektu SKM najbardziej złożonym problem było wyznaczanie optymalnych połączeń między zadanymi punktami w mieście. (...) W trakcie prac nad projektem zaproponowaliśmy dwa rozwiązania problemu - jedno oparte na algorytmie brute-force z nałożonymi ograniczeniami oraz drugie wykorzystujące klasyczne algorytmy grafowe poprzez rozbicie problemu na dwa zadania. W artykule opisujemy drugie podejście. Przy tworzeniu algorytmu uprościliśmy problem, zakładając, że pojazdy komunikacji miejskiej poruszają się zgodnie z rozkładem jazdy (czyli np. nie stoją w korkach). (fragment tekstu)

EN

The passenger using the public transport is not able to evaluate exactly, how much time is needed for reaching a destination. Even the choice of an appropriate travel plan among a huge number of connections poses difficulties. In the project implemented by SKN Ampersand the optimal route searching module will be responsible for calculating the best connection between the stops shown by the user. Information extracted automatically from the timetable of MPK. Poznan will provide the input for the algorithm. Commonly used Dijkstra algorithm which is mainly useful for searching car routes does not take into consideration a location-time relation, i.e. the fact that at the connecting points traveling cannot be continued immediately. As a result, we have many variants of traveling on a single route, depending on the decision which line the passenger takes and at what time. The issue of adapting the algorithm to the needs of the project is the main challenge. (original abstract)

Słowa kluczowe

PL

Komunikacja miejska; Transport pasażerski; Informatyzacja; Algorytm transportowy

EN

Municipal transport; Passenger transport; Informatization; Transport algorithm

• Czasopismo: Debiuty Ekonomiczne
• Rocznik: 2008
• Numer: nr 8 Informatyka, ekonometria i statystyka w społeczeństwie informacyjnym
• Strony: 165--173

Twórcy

autor

Maciej Kowalewski

• Akademia Ekonomiczna w Poznaniu, student

autor

Grzegorz Krzymiński

• Akademia Ekonomiczna w Poznaniu, student

Bibliografia

• Bukowska E., Celmer P., Górski В., Grzelak S., Jarka W., Jędrzejczak A., 2008, Projekt SKN, czyli dobór optymalnej trasy w sieci komunikacji miejskiej, [w:] Informatyka, ekonometria i statystyka w społeczeństwie informacyjnym, E. Gołata (red.), Zeszyty Naukowe Wydziału Informatyki i Gospodarki Elektronicznej AE w Poznaniu, Wydawnictwo Akademii Ekonomicznej w Poznaniu, Poznań.
• Cormen, T. H., Leiserson, C. E., Rivest R. L., 2001, Wprowadzenie do algorytmów, Wydawnictwa Naukowo-Techniczne, Warszawa.
• Martins E. Q. V, Pascoal M. M. B., 2003, A New Implementation of Yen 's Ranking Loopless Path Algorithm, "4OR: A Quarterly Journal of Operations Research", June, 2003, Vol. 1, nr 2.