Harmonogramowanie służb kierowców w publicznej komunikacji miejskiej

W pracy sformułowano model matematyczny zagadnienia harmonogramowania służb. Specyficzne wymagania publicznej komunikacji miejskiej zostały uwzględnione w sformułowaniu multi-kryterialnej funkcji celu i ograniczeń. Złożoność modelu matematycznego wynika z wielkiej liczby zmiennych decyzyjnych, skomplikowanych relacji i wielu ograniczeń. Trzy algorytmy zostały opracowane i zaproponowane dla optymalizacji harmonogramów służb kierowców: zmodyfikowany deterministyczny algorytm węgierski, stochastyczny algorytm zachłanny i klasyczny algorytm genetyczny. Testy porównawcze i analiza algorytmów została przeprowadzona na wielkich zbiorach danych z kilkunastu miast polskich. Rezultaty były pozytywne i wykazały użyteczność algorytmów w planowaniu operacyjnym publicznej komunikacji miejskiej.

---

In the work the mathematical model of crew rostering problem has been formulated. Specific demands of city public transit have been considered in formulating the multi-objective function and the constraints. The complexity of the mathematical model results from large number of decision variables, complex relations and number of constraints. Three original algorithms have been proposed and elaborated for optimization of crew roster: modified deterministic Hungarian algorithm, stochastic greedy algorithm and classical genetic algorithm. Comparison tests and analysis of the algorithms have been performed on large data sets from several cities of Poland. The results have been good and proved the usefulness of the algorithms to application in operational planning of city public transit.