Wyniki wyszukiwania - BazTech

1

Algorytm dewiacyjny dla problemu wyznaczania K najkrótszych ścieżek

Widuch J., Szołtysek M.

Studia Informatica

|

2011

|

Vol. 32, nr 1A

55-77

PL

Jednym z badanych problemów teorii grafów jest problem wyznaczenia najkrótszej ścieżki. Rozszerzeniem tego problemu jest problem wyznaczenia K (K > 1) najkrótszych ścieżek. Badane są dwa warianty tego problemu. W pierwszym dopuszcza się wyznaczenie ścieżek zawierających cykle, a w drugim są wyznaczane wyłącznie ścieżki acykliczne. W pracy został przedstawiony algorytm dewiacyjny, umożliwiający wyznaczenie K najkrótszych ścieżek, które mogą zawierać cykle.

EN

One of the studied problems of the graph theory is the shortest path problem. An extension of this problem is the problem of finding K (K > 1) shortest paths. Two variants of this problem are studied. In the first case path containing cycles are allowed, and in the second are determined only loopless paths. In the paper a deviation algorithm for solving K shortest paths, which may contain cycles is shown.

2

Problem wyznaczania połączeń autobusowych.

Szołtysek M.

Studia Informatica

|

2000

|

Vol. 21, nr 3

187-200

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.

3

Rozwiązywanie problemu dostawy za pomocą algorytmu przeszukiwania Tabu.

Szołtysek M.

Zeszyty Naukowe. Informatyka / Politechnika Śląska

|

1999

|

z. 37

209-221

PL

Problem dostawy jest przykładem złożonej optymalizacji kombinatorycznej i należy do grupy problemów NP-zupełnych. Zastosowanie algorytmu przeszukiwania tabu (ang. Tabu Search, TS) do rzwiązywania innyh problemów tej klasy przyniosło dobre rezultaty. Dlatego podjęto próbę zaadoptowania przeszukiwania tabu do rozwiązywania problemu dostawy. W pracy przedstawiono wyniki działania wybranych modyfikacji algorytmu przeszukiwania tabu do rozwiązywania problemu dostawy dla zbiorów danych wejściowych o różnych rozmiarach.

EN

The Delivery Problem is a difficult combinatorial optimization problem that belongs to the NP-complete group. Since the Tabu Search algorithm is suitable for solving the problems of this class, we have tried to adopt this algorithm to the delivery problem. In the paper the results of some modifications of the tabu search algorithm for solving the delivery problem for the sets of various sizes are presented.