Graf dla sieci komunikacji miejskiej - budowa i przeszukiwanie metodą heurystyczną

Streszczenie:
Artykuł przedstawia budowę grafu ważonego modelującego sieć komunikacji miejskiej, który następnie jest wykorzystywany do znalezienia najszybszej drogi między przystankami. Graf uwzględnia informacje o porze dnia, przesiadkach, czasie poruszania się pojazdów między przystankami i oczekiwania na połączenie. Węzły w grafie, podobnie jak połączenia, zależą od czasu odjazdu. Wagi krawędzi są parametryzowaną funkcją czasu. Algorytm wyszukiwania jest modyfikacją algorytmu A*. Rozważona metoda doboru heurystyki zakłada użycie funkcji odległości wykorzystującej współrzędne geograficzne przystanków.

Słowa kluczowe: algorytmy grafowe, graf, komunikacja miejska, algorytm a*, heurystyka

Public transportation graph - structure and heuristic search

Abstract:
This article presents the weighted graph model of public transport network which is used to find the fastest route between stops. The graph contains information on departure and travel time. Nodes and edges are created dynamically. Edges weights are calculated using parameterized time function. Search algorithm is a modification of the A* algorithm. The considered heuristic method involves the use of a geographical distance function.

Key words: graph algorithms, graph, public transport, a-star algorithm, heuristic search

Zamknij okno