Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Szűcs G.

1 2010

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: graf dynamiczny

Sortuj według:

Ogranicz wyniki do:

Route planning in dynamic graphs with linear changing and preprocessing for speed-up

Szűcs G.

Transport Problems

2010

T. 5, z. 2

49-58

The goal of this paper is to work out a concept for route planning in a road network, where the costs of roads are not constant, but changing in a linear way. The solution developed is based on the classical Dijkstra's algorithm, which helps to find the route with minimal cost. The new algorithm takes the varying into account in order to find out the best route. This search refers not only to a moment of the departure but to the whole duration of the travel. A speed-up technique has been developed for preprocessing before run time. This preprocessing phase helps to give back the route with minimal cost for the user quickly in run time query. A numerical example has been presented to show the detailed steps of the algorithm and the speed-up technique.

Celem artykułu jest wypracowanie koncepcji planowania tras (trasowania) w sieci drogowej, w której koszty połączeń nie są stałe, lecz zmieniają się w sposób liniowy. Zastosowane rozwiązanie opiera się na klasycznym algorytmie Dijkstra, który umożliwia znajdowanie tras po koszcie minimalnym. Proponowany algorytm uwzględnia dynamiczną różnorodność tras, w celu generowania najkorzystniejszej trasy. Jej poszukiwanie uwzględnia nie tylko momenty rozpoczęcia podróży, ale także czas trwania całej podróży. Technikę przyspieszania (speed-up) rozwinięto, w celu wstępnego przetwarzania przed fazą wykonania. Faza wstępnego przetwarzania pozwala szybciej pozyskać trasę, po koszcie minimalnym dla użytkownika. W artykule zostały zaprezentowane liczne przykłady, w których przedstawiono kolejne kroki algorytmu i techniki przyspieszania.