Применение обучения с подкреплением в задаче составления графиков смен водителей городского общественного транспорта

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

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

2. R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2Nd edition. Cambridge, MA: MIT Press, 2018.

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

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

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

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

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

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

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

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

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

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

13. V. Mnih et al., “Human-Level Control Through Deep Reinforcement Learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015, doi: 10.1038/nature14236.

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

15. V. Mnih et al., “Asynchronous Methods for Deep Reinforcement Learning,” in Proceedings of the 33rd International Conference on Machine Learning, 2016, pp. 1928–1937.

16. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal Policy Optimization Algorithms.” 2017, doi: 10.48550/arXiv.1707.06347.

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

18. O. Vinyals, M. Fortunato, and N. Jaitly, “Pointer Networks,” in Advances in Neural Information Processing Systems (NeurIPS), 2015, vol. 28, pp. 2692–2700.

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

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

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

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

23. Y. Liu and X. Zuo, “RL-MSA: a Reinforcement Learning-based Multi-line bus Scheduling Approach.” 2024, doi: 10.48550/arXiv.2403.06466.

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

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