Crew rostering in city public transit

• Autorzy: Kisielewski P.

Warianty tytułu

PL

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

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

harmonogramowanie służb; publiczna komunikacja miejska; multi-kryterialna funkcja celu; multi-kryterialna funkcja ograniczeń; zmodyfikowany deterministyczny algorytm węgierski; stochastyczny algorytm zachłanny; algorytm genetyczny

EN

crew rostering; city public transit; multi-objective function; modified deterministic Hungarian algorithm; stochastic greedy algorithm; genetic algorithm

• Wydawca: Sieć Badawcza Łukasiewicz - Poznański Instytut Technologiczny
• Czasopismo: Logistyka
• Rocznik: 2014
• Tom: nr 6
• Strony: 14329--14336, CD 6
• Opis fizyczny: Bibliogr. 13 poz., rys.

Twórcy

autor

Kisielewski P.

• Cracow University of Technology, Department of Logistic Systems, 31-864 Kraków, Al. Jana Pawła II nr 37

Bibliografia

• 1. Ahuja R., Mohring R., Zaroliagis C., Robust and Online Large-Scale Optimization: Models and Techniques for Transportation Systems. Springer-Verlag, Berlin 2009.
• 2. Caprara A, Fischetti M., Toth P., Vigo D., Guida P.L., Algorithms for railway crew management. Technical report, DEIS, University of Bologna, Italy, DMI, University of Udine, Italy, Ferrovie dello Stato SpA, Italy, June 1997.
• 3. Filipowicz B.: Badania operacyjne. FHU Poldex, Kraków 1997.
• 4. Freling R.,Lentink R., Odijk M., Scheduling train crews: a case study for the Dutch Railways. Econometric Institute, Erasmus University Rotterdam, Econometric Institute Report EI2000-17/A.
• 5. Ftulis S.G., Giordano M., Pluss J.J., Vota R.J., Rule-based constrains programming: application to crew assignment. Expert Systems with Applications 15 (1998) 77-85.
• 6. Goldberg D.E., Algorytmy genetyczne i ich zastosowania. WNT Warszawa 1998.
• 7. Kisielewski P.: City transit logistics system with optimization module. XXX Conference Polioptimization and CAD, Koszalin University of Technology, Mielno 2012.
• 8. Kisielewski P., Planning and dispatching optimization of city transport. Conference of IGKM, Białystok 2012.
• 9. Kisielewski P.: Genetic Algorithm for Transportation Task Assignment Optimization. XXX Conference Polioptimization and CAD, Koszalin University of Technology, Mielno 2008.
• 10. Kisielewski P.: Optymalizacja przydziału zadań transportowych. Problemy eksploatacji 2/2007 (65) Quarterly. Instytut Technologii Eksploatacji – PIB, Radom 2007.
• 11. Lam W., Bell M., Advanced modeling for transit operations and service planning. Pergamon, 2003.
• 12. Ross C., Wren A., Greedy genetic algorithms, optimizing mutations and bus driver scheduling. Computer-Aided Transit Scheduling, number 430 in Lecture Notes in Economics and Mathematical Systems, pages 213–235. Springer, 1993.
• 13. Wilson N., Nuzzolo A., Schedule-Based Dynamic Transit Modeling: Theory and Applications. Kluwer Academic Publishers 2010.