Wybrane metody poszukiwania rozwiązania problemu synchronizacji interwałowej

• Autorzy: Oziomek J. , Rogowski A.

Warianty tytułu

EN

Selected methods of searching of solution to bus synchronization problem

• Języki publikacji: PL

Abstrakty

PL

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ą.

EN

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.

Słowa kluczowe

PL

transport miejski; synchronizacja rozkładów jazdy; metody obliczeniowe

EN

public transport; timetables synchronization; calculation methods

• Wydawca: Instytut Naukowo-Wydawniczy "SPATIUM". sp. z o.o.
• Czasopismo: Autobusy : technika, eksploatacja, systemy transportowe
• Rocznik: 2017
• Tom: R. 18, nr 12
• Strony: 616--620, CD
• Opis fizyczny: Bibliogr. 8 poz., wykr.

Twórcy

autor

Oziomek J.

• Uniwersytet Technologiczno-Humanistyczny im. Kazimierza Pułaskiego w Radomiu, Wydział Transportu i Elektrotechniki

autor

Rogowski A.

• Uniwersytet Technologiczno-Humanistyczny im. Kazimierza Pułaskiego w Radomiu, Wydział Transportu i Elektrotechniki

Bibliografia

• 1. Cormen T. H., Leiserson Ch. E., Rivest R., L., Wprowadzenie do algorytmów, Wydawnictwa Naukowo-Techniczne, Warszawa 1997.
• 2. McConnell J. J., Analysis of Algorithms: An Active Learning Approach, Jones and Bartlett Publishers, Sudbury 2001.
• 3. Michalewicz Z., Fogel D., Jak to rozwiązać, czyli nowoczesna heurystyka, Wydawnictwa Naukowo-Techniczne, Warszawa 2006.
• 4. Motwani R., Raghavan P., Randomized Algorithms, Cambridge University Press, Melbourne 1995.
• 5. Oziomek J., Rogowski A., Alternatywna miara synchronizacji rozkładów jazdy, Autobusy. Technika, Eksploatacja, Systemy Transportowe, 6/2016, Instytut Naukowo-Wydawniczy „SPATIUM”, s. 658-661.
• 6. Oziomek J., Rogowski A., Synchronizacja miejskich linii komunikacyjnych z wykorzystaniem wielu kryteriów. Autobusy. Technika, Eksploatacja, Systemy Transportowe, 12/2016, Instytut Naukowo-Wydawniczy „SPATIUM”, s. 26-31.
• 7. Tyugu E., Algorithms and Architectures of Artifical Intelligence, IOS Press, Amsterdam 2007.
• 8. Zabinsky Z., Random Search Algorithms. Wiley Encyclopedia of Operations Research and Management Science, 8 Vols, Wiley & Sons, 2011.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018)