Wyznaczanie trasy w planerach podróży z zastosowaniem funkcji heurystycznych

• Autorzy: Celiński I. , Staniek M. , Sierpiński G.

Warianty tytułu

EN

Routing in trip planer using heuristics

• Języki publikacji: PL

Abstrakty

PL

W artykule zaproponowano uzupełnienie algorytmu A* o inne heurystyki aniżeli powszechne stosowane w tym celu odległości Manhattan czy Euklidesowe. W przedstawionej metodzie, jako źródło danych dla wartości funkcji heurystycznych zastosowano macierz wskaźników charakteryzujących sieć drogową. Taki wskaźnik nadawany jest każdemu rejonowi przestrzennemu (reżimowi) powstałemu na skutek jej celowej delimitacji. Ściślej, dla każdego rejonu można zdefiniować zbiór wskaźników: multimodalnych, bezpieczeństwa, ekologicznych i innych. Każdy ze wskaźników podkreśla inny sposób korzystania z sieci transportowej w danym rejonie przez jej użytkownika. Zbudowana w ten sposób heurystyka ma dwie podstawowe funkcjonalności. Dla rejonów przestrzennych o dużych wymiarach (powierzchni) przyspiesza czas wykonywania obliczeń algorytmu A*. Dla rejonów o małych wymiarach obszarowych profiluje trasę zgodnie z wolą użytkownika w sposób inny niż heurystyki oparte na prostych miarach przestrzennych.

EN

The article proposes an algorithm A* supplement to other heuristics than normally used for this purpose (Manhattan and Euclidean dist.). In the presented method, as the data source for the heuristics used ma-trix of indicators characterizing the road network. This indicator is assigned to each space regime due to its deliberate delimitation. Specifically, for each regime you can define a set of indicators: multimodal, safety, environmental friendly etc. Each of the indicators stresses otherwise use the transport network by the user. Constructed in this way heuristics has two basic func. For large areas of spatial regime accelerates compute time algorithm. For small areas of spatial profiles the route according to the user's expectations transport network in a manner other than heuristics based on measures of spatial.

Słowa kluczowe

PL

algorytm A*; algorytm A-star; funkcja heurystyczna; planer podróży; zrównoważony rozwój transportu; Open Street Map

EN

A* algorythm; STAR algorythm; heuristic function; trip planner; sustainable transport; Open Street Map

• Wydawca: Instytut Naukowo-Wydawniczy "TTS" Sp. z o.o
• Czasopismo: TTS Technika Transportu Szynowego
• Rocznik: 2015
• Tom: R. 22, nr 12
• Strony: 246--251, CD
• Opis fizyczny: Bibliogr. 11 poz., tab., rys.

Twórcy

autor

Celiński I.

• Katedra Systemów Transportowych i Inżynierii Ruchu, Wydział Transportu, Politechnika Śląska w Gliwicach

autor

Staniek M.

• Katedra Systemów Transportowych i Inżynierii Ruchu, Wydział Transportu, Politechnika Śląska w Gliwicach

autor

Sierpiński G.

• Katedra Systemów Transportowych i Inżynierii Ruchu, Wydział Transportu, Politechnika Śląska w Gliwicach

Bibliografia

• 1. Orzeł J., Rola metod heurystycznych…, „Bank i Kredyt”, R. 36, nr 5,2005.
• 2. Sierpiński G., Staniek M., Celiński I., Planowanie podróży proekologicznych z wykorzystaniem narzędzia Green Travelling Planner (w druku).
• 3. Firlej-Buzon A., Heurystyka - geneza oraz współczesne zastosowania, ZIN nr 1, s. 23-37, 2003.
• 4. Bolc L.; Cytowski J., Metody przeszukiwania heurystycznego, t.1, Warszawa: PWN, 2002.
• 5. Sysło M.M., Narsingh D., Kowalik S.J., Algorytmy optymalizacji dyskretnej. PWN, Warszawa,1999.
• 6. Sysło M.M., Narsingh D., Kowalik S.J., Discrete Optimization Algorithms. Dover Pub.,2006.
• 7. https://www.google.pl/maps?source=tldso (odsłona 29-09-2015).
• 8. http://www.targeo.pl/ (odsłona 29-09-2015).
• 9. GTFS standard, https://developers.google.com/transit/gtfs/reference, (odsłona 29-09-2015).
• 10. Cormen C.H., Leiserson C.E., Rivest R.L, Stein C., Wprowadzenie do algorytmów, WNT, 2004.
• 11. http://overpass-turbo.eu/ (odsłona 29-09-2015).