Wybrane metody poszukiwania rozwiązania problemu synchronizacji interwałowej

W artykule opisane zostały wybrane metody służące do rozwiązania problemu synchronizacji interwałowej rozkładów jazdy w miejskim transporcie zbiorowym. Scharakteryzowano jedną metodę dokładną (metodę przeglądu zupełnego) oraz dwie metody heurystyczne (metodę przeszukiwania losowego i wiązkowego). Pierwsza z metod (tj. przeglądu zupełnego) pozwala na znalezienie najlepszego rozwiązania problemu jednak na ogół przy znacznym czasie trwania obliczeń dla nietrywialnych problemów rzeczywistych. Pozostałe metody zwykle są szybsze - w metodzie przeszukiwania losowego generuje się losowo rozwiązania dopuszczalne, natomiast metoda przeszukiwania wiązkowego jest pewną odmianą algorytmu zachłannego, w której rozwiązania uzyskuje się krokowo. Obie metody heurystyczne nie dają pewności uzyskania rozwiązania optymalnego, a jedynie przybliżone. Istnieje szeroka grupa zagadnień optymalizacyjnych, dla których wybór metody rozwiązania nie jest oczywisty. Problem synchronizacji interwałowej jest jednym z tych, dla których konieczne jest poszukanie kompromisu między czasem trwania obliczeń, a ich dokładnością.

The article describes the selected methods used to solve the problem of synchronization of the timetables in urban public transport. One exact method (brute force) and two heuristic methods (random search and beam search) were characterized. The first method (brute force) allows to find the best solution of the problem but generally with a considerable duration of the calculations for the non-trivial problems. The other methods are usually faster - in random search method the feasible solutions are generated randomly while beam search method is a kind of greedy algorithm in which the solutions are generated step-by-step. Both heuristic methods do not provide the optimal solution, but only approximate. There is a wide range of the optimization problems for which the choice of the solution method is not clear. The problem of synchronization of the timetables in urban public transport is one of those for which it is necessary to find a compromise between the duration of the calculation and their accuracy.