Problem wyznaczania połączeń autobusowych.

• Autorzy: Szołtysek M.

Warianty tytułu

EN

Solving the bus routing problem.

• Języki publikacji: PL

Abstrakty

PL

Problem wyznaczania połączeń autobusowych jest przykładem złożonej optymalizacji kombinatorycznej. W celu zastosowania badanych algorytmów dla rzeczywistej sieci komunikacyjnej wraz z jej ograniczeniami stworzono komputerowy model realnej sieci komunkacyjnej. W dalszych pracach nad problemem połączeń autobusowych planuje się zbadanie algorytmów heurystycznych, takich jak przeszukiwanie tabu. Wymaga to istnienia dowolnego rozwiązania startowego oraz, w celu bezwzględnej oceny algorytmu, znajomości rozwiązania dokładnego, o ile rozmiar danych wejściowych pozwala na jego wyznaczenie. Z tych powodów prace nad problemem wyznaczania połączeń autobusowych rozpoczęto od stworzenia algorytmów realizujących te potrzeby. W niniejszej pracy przedstawiono wyniki działania algorytmu wyszukiwania wyczerpującego, algorytmu przeszukiwania wszerz oraz modyfikację algorytmu Dijkstry do wyznaczania połączeń autobusowych dla danych wejściowych opisujących rzeczywistą sieć komunikacyjną miast Gliwice i Zabrze.

EN

The bus routing problem is a difficult combinatorial optimization problem. we have created a real bus network computer model in order to apply our algorithms to a real bus network. In the future research we plan to investigate the heuristic algorithms, including Tabu Search. The heuristic such as Tabu Search require a start solution, and in order to assess the heuristic algorithm efficiency we need to know the optimal solution, provided that the size of input data allows to determine it. For these reasons we have started our work with creating the algorithms for mentioned needs. In this paper the results of the exhaustive search algorithm, Breadth First Search (BFS) and modification of Dijkstra's shortest path algorithm for the bus routing problem, tested on the input data describing a real communication network of Gliwice and Zabrze cities, are presented.

Słowa kluczowe

PL

algorytm Dijkstry; wyszukiwanie wyczerpujące; sieć komunikacyjna

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2000
• Tom: Vol. 21, nr 3
• Strony: 187--200
• Opis fizyczny: Bibliogr. 4 poz., il.

Twórcy

autor

Szołtysek M.

• Instytut Informatyki Politechniki Śląskiej 44-100 Gliwice, ul. Akademicka 16 tel. [phone],