maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2026-1-30-47mais-2001Research ArticleArtificial IntelligenceПрименение обучения с подкреплением в задаче составления графиков смен водителей городского общественного транспортаReinforcement learning for urban public transport driver schedulinghttps://orcid.org/0009-0008-5126-4344ГончаровСергей ВитальевичGoncharovSergei V.goncharov.sergei.21@gmail.comhttps://orcid.org/0000-0002-0134-1793ВойтешенкоИосиф СтаниславовичVojteshenkoIosif S.voit@bsu.byБелорусский государственный университетБеларусьBelarusian State UniversityBelarus2026160320263313047Copyright © Гончаров С.В., Войтешенко И.С., 20262026Гончаров С.В., Войтешенко И.С.Goncharov S.V., Vojteshenko I.S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/2001

В статье рассматривается применение методов глубокого обучения с подкреплением для решения задачи автоматизированного составления графиков водительских смен городского пассажирского транспорта. Задача составления графиков смен (Crew Scheduling Problem) относится к классу NP-трудных задач комбинаторной оптимизации и характеризуется множеством сложных ограничений, связанных с трудовым законодательством и операционными особенностями транспортной сети. Описана постановка задачи с учётом смены маршрутов. Предложена формализация задачи в виде марковского процесса принятия решений с учётом специфических ограничений транспортной отрасли: максимального рабочего времени, обеденных перерывов и минимального времени отдыха между рейсами. Сформулировано пространство состояний, включающее признаки контрольных остановок, текущего рейса и смен-кандидатов. Описан механизм приоритетного отбора смен-кандидатов для снижения размерности пространства действий. Описана многокомпонентная функция награды, учитывающая число задействованных смен, время холостых поездок и утилизацию водителей. Архитектура агента реализована на основе метода Actor-Critic с алгоритмом Proximal Policy Optimization. Экспериментальное исследование проведено на реальных данных транспортной сети города Ярославль, включающей 6 маршрутов и 974 рейса. Проведён сравнительный анализ с альтернативными методами: DQN, REINFORCE и эвристическим подходом, представленного жадным алгоритмом. Сравнительный анализ результатов показал превосходство алгоритма PPO над другими подходами. В результате исследования сделан вывод о возможности использования методов обучения с подкреплением для решения задач транспортной оптимизации.

The article examines the application of deep reinforcement learning methods to solve the problem of automated scheduling of driver shifts for urban passenger transport. The Crew Scheduling Problem belongs to the class of NP-hard combinatorial optimization problems and is characterized by a multitude of complex constraints related to labor legislation and the operational specifics of the transport network. The problem formulation, considering route changes, is described. The problem is formalized as a Markov Decision Process, taking into account specific constraints of the transport industry: maximum working hours, lunch breaks, and minimum rest time between trips. The state space is formulated, including features of control stops, the current trip, and candidate shifts. A mechanism for prioritized selection of candidate shifts is described to reduce the dimensionality of the action space. A multi-component reward function is described, considering the number of shifts utilized, deadhead travel time, and driver utilization. The agent's architecture is implemented based on the Actor-Critic method with the Proximal Policy Optimization algorithm. An experimental study was conducted on real data from the transport network of the city of Yaroslavl, including 6 routes and 974 trips. A comparative analysis was conducted with alternative methods: DQN, REINFORCE, and a heuristic approach represented by a greedy algorithm. The comparative analysis of the results demonstrated the superiority of the PPO algorithm over the other approaches. As a result of the study, it was concluded that reinforcement learning methods can be used to solve transportation optimization problems.

обучение с подкреплениемглубокое обучениеPPOсоставление графиковрасписаниеобщественный транспортнейронные сетиreinforcement learningdeep learningPPOcrew scheduling problemschedulepublic transportneural networksReferencesA. Wren, “Scheduling, Timetabling and Rostering — A Special Relationship?,” in Practice and Theory of Automated Timetabling, 1996, vol. 1153, pp. 46–75, doi: 10.1007/3-540-61794-9_51.A. Wren, “Scheduling, Timetabling and Rostering — A Special Relationship?,” in Practice and Theory of Automated Timetabling, 1996, vol. 1153, pp. 46–75, doi: 10.1007/3-540-61794-9_51.R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2Nd edition. Cambridge, MA: MIT Press, 2018.R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2Nd edition. Cambridge, MA: MIT Press, 2018.R. E. Marsten and F. Shepardson, “Exact Solution of Crew Scheduling Problems Using the Set Partitioning Model,” Networks, vol. 11, no. 2, pp. 165–177, 1981, doi: 10.1002/net.3230110208.R. E. Marsten and F. Shepardson, “Exact Solution of Crew Scheduling Problems Using the Set Partitioning Model,” Networks, vol. 11, no. 2, pp. 165–177, 1981, doi: 10.1002/net.3230110208.M. Desrochers and F. Soumis, “A Column Generation Approach to the Urban Transit Crew Scheduling Problem,” Transportation Science, vol. 23, no. 1, pp. 1–13, 1989, doi: 10.1287/trsc.23.1.1.M. Desrochers and F. Soumis, “A Column Generation Approach to the Urban Transit Crew Scheduling Problem,” Transportation Science, vol. 23, no. 1, pp. 1–13, 1989, doi: 10.1287/trsc.23.1.1.C. C. Ribeiro and F. Soumis, “A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem,” Operations Research, vol. 42, no. 1, pp. 41–52, 1994, doi: 10.1287/opre.42.1.41.C. C. Ribeiro and F. Soumis, “A Column Generation Approach to the Multiple-Depot Vehicle Scheduling Problem,” Operations Research, vol. 42, no. 1, pp. 41–52, 1994, doi: 10.1287/opre.42.1.41.T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, vol. 6, pp. 109–133, 1995, doi: 10.1007/BF01096763.T. A. Feo and M. G. C. Resende, “Greedy Randomized Adaptive Search Procedures,” Journal of Global Optimization, vol. 6, pp. 109–133, 1995, doi: 10.1007/BF01096763.T. Park and K. R. Ryu, “Crew Pairing Optimization by a Genetic Algorithm with Unexpressed Genes,” Journal of Intelligent Manufacturing, vol. 17, no. 4, pp. 375–383, 2006, doi: 10.1007/s10845-005-0011-z.T. Park and K. R. Ryu, “Crew Pairing Optimization by a Genetic Algorithm with Unexpressed Genes,” Journal of Intelligent Manufacturing, vol. 17, no. 4, pp. 375–383, 2006, doi: 10.1007/s10845-005-0011-z.F. Glover, “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, vol. 13, no. 5, pp. 533–549, 1986, doi: 10.1016/0305-0548(86)90048-1.F. Glover, “Future Paths for Integer Programming and Links to Artificial Intelligence,” Computers & Operations Research, vol. 13, no. 5, pp. 533–549, 1986, doi: 10.1016/0305-0548(86)90048-1.S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983, doi: 10.1126/science.220.4598.671.S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983, doi: 10.1126/science.220.4598.671.J. Ma, C. Song, A. Ceder, T. Liu, and W. Guan, “Fairness in optimizing bus-crew scheduling process,” PLoS One, vol. 12, no. 11, p. e0187623, 2017, doi: 10.1371/journal.pone.0187623.J. Ma, C. Song, A. Ceder, T. Liu, and W. Guan, “Fairness in optimizing bus-crew scheduling process,” PLoS One, vol. 12, no. 11, p. e0187623, 2017, doi: 10.1371/journal.pone.0187623.R. S. K. Kwan, A. S. K. Kwan, and A. Wren, “Evolutionary Driver Scheduling with Relief Chains,” Evolutionary Computation, vol. 9, no. 4, pp. 445–460, 2001, doi: 10.1162/10636560152642869.R. S. K. Kwan, A. S. K. Kwan, and A. Wren, “Evolutionary Driver Scheduling with Relief Chains,” Evolutionary Computation, vol. 9, no. 4, pp. 445–460, 2001, doi: 10.1162/10636560152642869.Q. Cappart, T. Che, Z. Kulkarni, M. Morabit, and L.-M. Rousseau, “Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, vol. 35, no. 5, pp. 3677–3687, doi: 10.1609/aaai.v35i5.16484.Q. Cappart, T. Che, Z. Kulkarni, M. Morabit, and L.-M. Rousseau, “Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2021, vol. 35, no. 5, pp. 3677–3687, doi: 10.1609/aaai.v35i5.16484.V. Mnih et al., “Human-Level Control Through Deep Reinforcement Learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015, doi: 10.1038/nature14236.V. Mnih et al., “Human-Level Control Through Deep Reinforcement Learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015, doi: 10.1038/nature14236.R. J. Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning,” Machine Learning, vol. 8, no. 3, pp. 229–256, 1992, doi: 10.1007/BF00992696.R. J. Williams, “Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning,” Machine Learning, vol. 8, no. 3, pp. 229–256, 1992, doi: 10.1007/BF00992696.V. Mnih et al., “Asynchronous Methods for Deep Reinforcement Learning,” in Proceedings of the 33rd International Conference on Machine Learning, 2016, pp. 1928–1937.V. Mnih et al., “Asynchronous Methods for Deep Reinforcement Learning,” in Proceedings of the 33rd International Conference on Machine Learning, 2016, pp. 1928–1937.J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms.” 2017, doi: 10.48550/arXiv.1707.06347.J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms.” 2017, doi: 10.48550/arXiv.1707.06347.W. Kool, H. van Hoof, and M. Welling, “Attention, Learn to Solve Routing Problems!,” in Proceedings of the International Conference on Learning Representations (ICLR), 2019, pp. 1–25.W. Kool, H. van Hoof, and M. Welling, “Attention, Learn to Solve Routing Problems!,” in Proceedings of the International Conference on Learning Representations (ICLR), 2019, pp. 1–25.O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer Networks,” in Advances in Neural Information Processing Systems (NeurIPS), 2015, vol. 28, pp. 2692–2700.O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer Networks,” in Advances in Neural Information Processing Systems (NeurIPS), 2015, vol. 28, pp. 2692–2700.L. Kenworthy, S. Nayak, C. Chin, and H. Balakrishnan, “NICE: Robust Scheduling through Reinforcement Learning-Guided Integer Programming,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 9, 2022, doi: 10.1609/aaai.v36i9.21218.L. Kenworthy, S. Nayak, C. Chin, and H. Balakrishnan, “NICE: Robust Scheduling through Reinforcement Learning-Guided Integer Programming,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 9, 2022, doi: 10.1609/aaai.v36i9.21218.M. Nagayoshi and H. Tamaki, “Constructive Nurse Scheduling Using Reinforcement Learning Considering Variations in Nurse Work Patterns,” in Proceedings of the International Conference on Artificial Life and Robotics (ICAROB 2024), 2024, pp. 325–328.M. Nagayoshi and H. Tamaki, “Constructive Nurse Scheduling Using Reinforcement Learning Considering Variations in Nurse Work Patterns,” in Proceedings of the International Conference on Artificial Life and Robotics (ICAROB 2024), 2024, pp. 325–328.X. Zhang et al., “Multi-agent deep Q-network-based metaheuristic algorithm for Nurse Rostering Problem,” in Swarm and Evolutionary Computation, 2024, vol. 87, p. 101547, doi: 10.1016/j.swevo.2024.101547.X. Zhang et al., “Multi-agent deep Q-network-based metaheuristic algorithm for Nurse Rostering Problem,” in Swarm and Evolutionary Computation, 2024, vol. 87, p. 101547, doi: 10.1016/j.swevo.2024.101547.X. Ding, H. Liu, and X. Chen, “Deep Reinforcement Learning for Solving Multi-period Routing Problem with Binary Driver-customer Familiarity,” in Proceedings of the 2023 5th International Conference on Internet of Things, Automation and Artificial Intelligence, 2024, pp. 125–129, doi: 10.1145/3653081.3653103.X. Ding, H. Liu, and X. Chen, “Deep Reinforcement Learning for Solving Multi-period Routing Problem with Binary Driver-customer Familiarity,” in Proceedings of the 2023 5th International Conference on Internet of Things, Automation and Artificial Intelligence, 2024, pp. 125–129, doi: 10.1145/3653081.3653103.Y. Liu and X. Zuo, “RL-MSA: a Reinforcement Learning-based Multi-line bus Scheduling Approach.” 2024, doi: 10.48550/arXiv.2403.06466.Y. Liu and X. Zuo, “RL-MSA: a Reinforcement Learning-based Multi-line bus Scheduling Approach.” 2024, doi: 10.48550/arXiv.2403.06466.J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-Dimensional Continuous Control Using Generalized Advantage Estimation.” 2018, doi: 10.48550/arXiv.1506.02438.J. Schulman, P. Moritz, S. Levine, M. Jordan, and P. Abbeel, “High-Dimensional Continuous Control Using Generalized Advantage Estimation.” 2018, doi: 10.48550/arXiv.1506.02438.S. V. Goncharov and I. S. Vojteshenko, “K voprosu naznacheniya voditeley na reysy gorodskogo obshchestvennogo transporta na osnove obucheniya s podkrepleniem,” in Informatsionnye tekhnologii i sistemy 2025 (ITS 2025), pp. 45–46.S. V. Goncharov and I. S. Vojteshenko, “K voprosu naznacheniya voditeley na reysy gorodskogo obshchestvennogo transporta na osnove obucheniya s podkrepleniem,” in Informatsionnye tekhnologii i sistemy 2025 (ITS 2025), pp. 45–46.

The authors declare that there are no conflicts of interest present.