Reinforcement learning for urban public transport driver scheduling

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.

reinforcement learning, deep learning, PPO, crew scheduling problem, schedule, public transport, neural networks

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.