Zastosowanie algorytmu mrówkowego do wyznaczania przydziału pojazdów do zadań w miejskim transporcie zbiorowym

• Autorzy: Izdebski Mariusz , Jacyna Marianna , Kisielewski Piotr

Warianty tytułu

EN

Application of the ant algorithm to determine the allocation of vehicles to urban public transport tasks

• Języki publikacji: PL

Abstrakty

PL

W artykule opisano zastosowanie algorytmu mrówkowego w wyznaczaniu przydziału pojazdów do zadań w transporcie zbiorowym. Analizowany problem przydziału jest złożonym zagadnieniem optymalizacyjnym, klasyfikującym go do problemów NP-trudnych. W obszarze dotyczącym zagadnień miejskiego transportu zbiorowego jest podstawowym problemem, który należy rozwiązać w procesie konstruowania rozkładów jazdy oraz planów pracy pojazdów i kierowców. Celem niniejszej publikacji było opracowanie nowego narzędzia optymalizacyjnego adekwatnego do analizowanego zagadnienia przydziału pojazdów do zadań w komunikacji miejskiej. Przedstawiony algorytm mrówkowy jest nowym podejściem zastosowanym do rozwiązywania zagadnień przydziału w transporcie zbiorowym i stanowi podstawę do dalszych badań nad tematyką opracowywania nowych metod optymalizacyjnych w badanym problemie. Opracowany algorytm minimalizuje liczbę pojazdów przy jednoczesnej minimalizacji czasu pracy oraz przebytej drogi przez wykorzystane pojazdy. Opracowano model matematyczny zagadnienia przydziału pojazdów do zadań w transporcie publicznym, tj. zdefiniowano zmienne decyzyjne, ograniczenia oraz funkcje kryterium. Ograniczenia przydziału wynikają z czasu realizacji kursów w danym dniu roboczym, ograniczeń prawnych w zakresie czasu pracy i jazdy kierowcy, a także dostępnej liczy pojazdów. Problem został przedstawiony w aspekcie wielokryterialnym, gdzie decydujące znaczenie w ocenie efektywnego przydziału mają czas i dystans pokonany przez wszystkie pojazdy realizujące zlecone zadania. W artykule przedstawiono ogólną koncepcję algorytmu mrówkowego, która jest w trakcie procesu weryfikacji na danych teoretycznych i rzeczywistych bazach danych przedsiębiorstw komunikacji miejskiej.

EN

The article describes the application of the ant algorithm in the problem of vehicle allocation to tasks in public transport. The analyzed allocation problem is a complex optimization problem that classifies it as NP-difficult. In the area of public transport issues it is a basic problem that should be solved in the process of constructing timetables and work plans for vehicles and drivers. The purpose of this publication was to develop a new optimization tool adequate to the analyzed issue of the allocation of vehicles to tasks in public transport. The presented ant algorithm is a new approach used to solve allocation issues in public transport and is the basis for further research on the development of new optimization methods in the studied problem. The developed algorithm minimizes the number of vehicles while minimizing working time and the distance traveled by the operating vehicles. A mathematical model has been developed on the issue of allocation of vehicles in public transport, i.e. decision variables, constraints and criterion functions were defined. The restrictions on the allocation result from the duration of the courses on a given business day, legal restrictions on the driver’s working time and driving time, as well as the available number of vehicles. The problem was presented in a multi-criteria aspect, where the decisive factor in assessing the effective allocation is the time and distance covered by all vehicles carrying out the assigned tasks. The article presents the general concept of the ant algorithm, which is in the process of verification on theoretical data and real databases of public transport companies.

Słowa kluczowe

PL

transport publiczny; przydział pojazdów do zadań; algorytm mrówkowy

EN

public transport; vehicle assignment; ant algorithm

• Wydawca: Stowarzyszenie Inżynierów i Techników Komunikacji Rzeczpospolitej Polskiej
• Czasopismo: Transport Miejski i Regionalny
• Rocznik: 2020
• Tom: nr 4
• Strony: 26--31
• Opis fizyczny: Bibliogr. 42 poz., rys.

Twórcy

autor

Izdebski Mariusz

• Politechnika Warszawska, Wydział Transportu, 00-662 Warszawa, ul. Koszykowa 75

autor

Jacyna Marianna

• Politechnika Warszawska, Wydział Transportu, 00-662 Warszawa, ul. Koszykowa 75

autor

Kisielewski Piotr

• Politechnika Krakowska, Wydział Mechaniczny, 31-155 Kraków, ul. Warszawska 24

Bibliografia

• 1. Valouxis C., Housos E., Combined bus and driver scheduling, “Computers & Operations Research”, 2002, no. 29.
• 2. Wedelin D., An algorithm for large scale 0-1 integer programming with application to airline crew scheduling, “Annals of Operational Research”, 1995, no 57.
• 3. Borndörfer R., Löbel A., Weider S., A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit. In: Hickman M., Mirchandani P., Voß S. (eds), Computer-aided Systems in Public Transport. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 2008, vol. 600.
• 4. Gintner V., Kliewer N., Suhl L., A Crew Scheduling Approach for Public Transit Enhanced with Aspects from Vehicle Scheduling, In: Hickman M., Mirchandani P., Voß S. (eds) Computeraided Systems in Public Transport. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 2008, vol. 600.
• 5. Desrochers, M., Soumis F., A column generation approach to the urban transit crew scheduling problem, “Transportation Science”, 1989, no. 23.
• 6. Wilson J.M., A genetic algorithm for the generalized assignment problem, “Journal of the Operational Research Society”, 1997, vol. 48.
• 7. Pentico D.W., Assignment problems: A golden anniversary survey, “European Journal of Operational Research”, 2007, vol. 176, issue 2.
• 8. Kisielewski P., Optymalizacja przydziału zadań transportowych, Politechnika Krakowska, „Problemy Eksploatacji”, 2007, nr 2.
• 9. Jacyna-Gołda I., Izdebski M., Podviezko A., Assessment of efficiency of assignment of vehicles to tasks in supply chains: A case study of a municipal company, “Transport”, 2017, vol. 32, issue 3.
• 10. Izdebski M., Modelowanie i analiza problemów decyzyjnych przydziału pojazdów do zadań w zagadnieniach transportowych, Oficyna Wydawnicza Politechniki Warszawskiej, 2018.
• 11. Jacyna M., Izdebski M., Szczepański E. [i in.], The task assignment of vehicles for a production company, w: Symmetry-Basel, 2018, vol. 11, no. 10.
• 12. Jacyna-Gołda I., Inżynieria oceny efektywności sieci dostaw, Wydawnictwo Naukowe PWN, 2019.
• 13. Gołda P., Izdebski M., Szczepański E., The application of ant algorithm in the assignment problem of aircrafts to stops points on the apron, “Journal of KONES Powertrain and Transport”, 2018, vol. 25, no. 1.
• 14. Gołda P., Wspomaganie decyzji wykonywania operacji lotniskowych z zastosowaniem narzędzi symulacyjnych, Monografia. Wydawnictwo ITWL, 2018.
• 15. Izdebski M., Jacyna M., The organization of the municipal waste collection: the decision model, Rocznik Ochrona Środowiska/Annual set The Environment Protection, 2018, nr 20.
• 16. Szczepański E., Jachimowski R., Izdebski M., Jacyna-Gołda J., Warehouse location problem in supply chain designing: a simulation analysis, Archives of Transport, 2019, vol. 50, issue 2.
• 17. Jacyna-Gołda I., Lewczuk K., The method of estimating dependability of supply chain elements on the base of technical and organizational redundancy of process, in: „Eksploatacja i Niezawodność“, 2017, vol. 3, no. 19.
• 18. Izdebski M., Jacyna M., The algorithm solving the problem of allocation of tasks to resources in the transport company, w: CLC 2013: Carpathian Logistics Congress – Congress Proceedings / Feliks Jerzy ( red. ), TANGER Ltd., Ostrava, 2014.
• 19. Wasiak M., Jacyna M., Lewczuk K. [i in.], The method for evaluation of efficiency of the concept of centrally managed distribution in cities, w: “Transport”, 2017, vol. 32, nr 4.
• 20. Jacyna M., Wasiak M., Multicriteria Decision Support in Designing Transport Systems, w: Tools of Transport Telematics, red. Mikulski J., Springer, 2015.
• 21. Kisielewski P., Komputerowe wspomaganie planowania komunikacji miejskiej. Monografia, Oficyna wydawnicza Politechniki Warszawskiej, Warszawa 2019.
• 22. Gintner V., Kliewer N., Suhl L., Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice, OR Spectrum, 2005, no. 27(4).
• 23. Haase K., Desaulniers G., Desrosiers J., Simultaneous vehicle and crew scheduling in urban mass transit systems, “Transportation Science”, 2001, no. 35.
• 24. Huisman D., Freling R., Wagelmans A.P.M., Multiple-depot integrated vehicle and crew scheduling, “Transportation Science”, 2005, no. 39.
• 25. Freling R., Huisman D., Wagelmans A.P.M., Models and algorithms for integration of vehicle and crew scheduling, “Journal of Scheduling”, 2003, no. 6.
• 26. Löbel A., Solving Large-Scale Multiple-Depot Vehicle Scheduling Problems, in: Wilson N.H.M. (eds) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 1999, vol. 471.
• 27. Gaffi A., Nonato M., An Integrated Approach to Ex-Urban Crew and Vehicle Scheduling, in: Wilson N.H.M. (eds), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg. 1999, vol. 471.
• 28. Freling R., Huisman D., Wagelmans A.P.M., Applying an Integrated Approach to Vehicle and Crew Scheduling in Practice, in: Voß S., Daduna J.R. (eds) Computer-Aided Scheduling of Public Transport. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 2001, vol. 505
• 29. Daduna J.R., Pinto Paixão J.M., Vehicle Scheduling for Public Mass Transit — An Overview, in: Daduna J.R., Branco I., Paixão J.M.P. (eds), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 1995, vol. 430.
• 30. de Groot S.W., Huisman D., Vehicle and Crew Scheduling: Solving Large Real-World Instances with an Integrated Approach, in: Hickman M., Mirchandani P., Voß S. (eds), Computeraided Systems in Public Transport. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 2008, vol. 600.
• 31. Mesquita M., Paixão J., Exact Algorithms for the Multi-Depot Vehicle Scheduling Problem Based on Multicommodity Network Flow Type Formulations, in: Wilson N.H.M. (eds), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 1999, vol. 471.
• 32. Carraresi P., Nonato M., Girardi L., Network Models, Lagrangean Relaxation and Subgradients Bundle Approach in Crew Scheduling Problems, in: Daduna J.R., Branco I., Paixão J.M.P. (eds), Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin, Heidelberg, 1995, vol. 430.
• 33. Scott D., A large linear programming approach to the public transport scheduling and cost model, in J. Rousseau, editor, Computer Scheduling of Public Transport 2, North Holland, Amsterdam 1985.
• 34. Friberg C., Haase K., An exact branch and cut algorithm for the vehicle and crew scheduling problem, in N. Wilson, editor, Computer-Aided Transit Scheduling, Springer, Berlin 1999.
• 35. Feo T.A., Resende M.G.C., Greedy randomized adaptive search heuristic, Journal of Global Optimization 1995, no. 6.
• 36. Garcia B.-L., Potvin J.-Y., Rousseau J.-M., A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints, „Computers & Operations Research”, 1994, vol. 21.
• 37. Zhang Q., Manier M., A genetic algorithm with tabu search procedure for flexible job shop scheduling with transportation constraints and bounded processing times, „Computers & Operations Research”, 2012, vol. 39, Issue 7.
• 38. Li J., Kwan R.S., A fuzzy genetic algorithm for driver scheduling, „European Journal of Operational Research”, 2003, vol. 147.
• 39. Peng K., Shen Y., Li J., A multi-objective simulated annealing for bus driver rostering, in: Bio-Inspired Computing-Theories and Applications, Springer, 2015.
• 40. Fu A., Lei, S., Intelligent dispatching of public transit vehicles using particle swarm optimization algorithm, Comput Eng Appl 44, 2008, no. 15.
• 41. Dorigo M., Gambardela L.M., Ant Colonies for the Travelling Salesman Problem, BioSystems, 1997, vol. 43.
• 42. Dorigo M., Caro D., Gambardela L.M., Ant Algorithms for Discrete Optimization, Artificial Life, 1999, vol. 5 (2).

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).