基于超级时空网络的多目标公交车辆调度
Multi-Objective Bus Vehicle Scheduling Based on Super Spatiotemporal Network
摘要: 本文研究了多目标公交车辆调度问题(BVSP)，提出了一种基于超级时空网络的优化模型，并设计了多目标3M算法以实现车队规模最小化、系统空驶时间减少和司机工作时间的公平性。该模型在公交调度网络中引入时空节点与有向弧段，以刻画车次与车场间的时空关系，提升模型的解释性和计算效率。通过对青岛公交某一条线路的案例研究，验证了该算法在降低空驶时间和均衡工作时间上的有效性，并发现车队规模与空驶时间、司机工作时间的平衡关系。本文提出的方法为公交调度系统在多目标优化中提供了一种高效且实用的解决方案。
Abstract: This paper investigates the multi-objective Bus Vehicle Scheduling Problem (BVSP) and proposes an optimization model based on a super spatiotemporal network. A multi-objective 3M algorithm is developed to achieve objectives of minimizing fleet size, reducing system deadhead time, and promoting fairness in drivers’ working hours. The model incorporates spatiotemporal nodes and directed arcs within the bus scheduling network to capture the temporal and spatial relationships between trips and depots, enhancing both interpretability and computational efficiency. A case study on a specific route of Qingdao’s public bus system validates the effectiveness of this algorithm in reducing deadhead time and balancing working hours. Furthermore, it reveals a trade-off relationship among fleet size, deadhead time, and drivers’ working hours. The proposed approach offers an efficient and practical solution for multi-objective optimization in bus scheduling systems.
文章引用：章炎, 何胜学, 贾田峰. 基于超级时空网络的多目标公交车辆调度[J]. 运筹与模糊学, 2024, 14(6): 726-741. https://doi.org/10.12677/orf.2024.146572

参考文献

[1] Guihaire, V. and Hao, J. (2008) Transit Network Design and Scheduling: A Global Review. Transportation Research Part A: Policy and Practice, 42, 1251-1273. [Google Scholar] [CrossRef] 
[2] Ceder, A. (2011) Optimal Multi-Vehicle Type Transit Timetabling and Vehicle Scheduling. Procedia-Social and Behavioral Sciences, 20, 19-30. [Google Scholar] [CrossRef] 
[3] Gao, P., Zuo, X., Bian, Q. and Zhao, X. (2019) A Memetic Algorithm to Optimize Bus Timetable with Unequal Time Intervals. Proceedings of the Genetic and Evolutionary Computation Conference Companion, Prague Czech Republic, 13-17 July 2019, 1336-1344. [Google Scholar] [CrossRef] 
[4] Haase, K., Desaulniers, G. and Desrosiers, J. (2001) Simultaneous Vehicle and Crew Scheduling in Urban Mass Transit Systems. Transportation Science, 35, 286-303. [Google Scholar] [CrossRef] 
[5] Zhu, C. and Chen, X. (2013) Optimizing Battery Electric Bus Transit Vehicle Scheduling with Battery Exchanging: Model and Case Study. Procedia-Social and Behavioral Sciences, 96, 2725-2736. [Google Scholar] [CrossRef] 
[6] Sun, C., Zhou, W. and Wang, Y. (2008) Scheduling Combination and Headway Optimization of Bus Rapid Transit. Journal of Transportation Systems Engineering and Information Technology, 8, 61-67. [Google Scholar] [CrossRef] 
[7] Kwan, R.S.K. and Rahin, M.A. (1999) Object Oriented Bus Vehicle Scheduling—The BOOST System. In: Wilson, N.H.M., Ed., Computer-Aided Transit Scheduling, Springer, 177-191. [Google Scholar] [CrossRef] 
[8] Lin, Y., Pan, S., Jia, L., et al. (2010) A Bi-Level Multi-Objective Programming Model for Bus Crew and Vehicle Scheduling. 2010 8th World Congress on Intelligent Control and Automation, Jinan, 7-9 July 2010, 2328-2333. [Google Scholar] [CrossRef] 
[9] Shui, X., Zuo, X., Chen, C. and Smith, A.E. (2015) A Clonal Selection Algorithm for Urban Bus Vehicle Scheduling. Applied Soft Computing, 36, 36-44. [Google Scholar] [CrossRef] 
[10] Gintner, V., Kliewer, N. and Suhl, L. (2005) Solving Large Multiple-Depot Multiple-Vehicle-Type Bus Scheduling Problems in Practice. OR Spectrum, 27, 507-523. [Google Scholar] [CrossRef] 
[11] Liu, Z. and Shen, J. (2007) Regional Bus Operation Bi-Level Programming Model Integrating Timetabling and Vehicle Scheduling. Systems Engineering-Theory & Practice, 27, 135-141. [Google Scholar] [CrossRef] 
[12] Forbes, M.A., Holt, J.N. and Watts, A.M. (1994) An Exact Algorithm for Multiple Depot Bus Scheduling. European Journal of Operational Research, 72, 115-124. [Google Scholar] [CrossRef] 
[13] Banihashemi, M. and Haghani, A. (2000) Optimization Model for Large-Scale Bus Transit Scheduling Problems. Transportation Research Record: Journal of the Transportation Research Board, 1733, 23-30. [Google Scholar] [CrossRef] 
[14] Wei, M., Jin, W., Fu, W., et al. (2010) Improved Ant Colony Algorithm for Multi-Depot Bus Scheduling Problem with Route Time Constraints. 2010 8th World Congress on Intelligent Control and Automation, Jinan, 7-9 July 2010, 4050-4053. [Google Scholar] [CrossRef] 
[15] Ceder, A. (2011) Public-Transport Vehicle Scheduling with Multi Vehicle Type. Transportation Research Part C: Emerging Technologies, 19, 485-497. [Google Scholar] [CrossRef] 
[16] Kliewer, N., Mellouli, T. and Suhl, L. (2006) A Time-Space Network Based Exact Optimization Model for Multi-Depot Bus Scheduling. European Journal of Operational Research, 175, 1616-1627. [Google Scholar] [CrossRef] 
[17] Haghani, A. and Banihashemi, M. (2002) Heuristic Approaches for Solving Large-Scale Bus Transit Vehicle Scheduling Problem with Route Time Constraints. Transportation Research Part A: Policy and Practice, 36, 309-333. [Google Scholar] [CrossRef] 
[18] Guo, C., Wang, C. and Zuo, X. (2019) A Genetic Algorithm Based Column Generation Method for Multi-Depot Electric Bus Vehicle Scheduling. Proceedings of the Genetic and Evolutionary Computation Conference Companion, Prague Czech Republic, 13-17 July 2019, 367-368. [Google Scholar] [CrossRef] 
[19] Ning, Z., Sun, S., Zhou, M., Hu, X., Wang, X., Guo, L., et al. (2022) Online Scheduling and Route Planning for Shared Buses in Urban Traffic Networks. IEEE Transactions on Intelligent Transportation Systems, 23, 3430-3444. [Google Scholar] [CrossRef] 
[20] 张思维, 魏昕怡, 邱桃荣. 优化公交车调度的多目标遗传算法模型[J]. 南昌大学学报(理科版), 2022, 46(1): 60-65.
[21] Yang, X. and Liu, L. (2020) A Multi-Objective Bus Rapid Transit Energy Saving Dispatching Optimization Considering Multiple Types of Vehicles. IEEE Access, 8, 79459-79471. [Google Scholar] [CrossRef] 
[22] Zakariazadeh, A., Jadid, S. and Siano, P. (2014) Multi-Objective Scheduling of Electric Vehicles in Smart Distribution System. Energy Conversion and Management, 79, 43-53. [Google Scholar] [CrossRef] 
[23] Shang, H., Liu, Y., Wu, W. and Zhao, F. (2023) Multi-Depot Vehicle Scheduling with Multiple Vehicle Types on Overlapped Bus Routes. Expert Systems with Applications, 228, Article 120352. [Google Scholar] [CrossRef] 
[24] Zuo, X., Chen, C., Tan, W., et al. (2015) Vehicle Scheduling of an Urban Bus Line via an Improved Multiobjective Genetic Algorithm. IEEE Transactions on Intelligent Transportation Systems, 16, 1030-1041. [Google Scholar] [CrossRef] 
[25] Wang, C., Shi, H. and Zuo, X. (2020) A Multi-Objective Genetic Algorithm Based Approach for Dynamical Bus Vehicles Scheduling under Traffic Congestion. Swarm and Evolutionary Computation, 54, Article 100667. [Google Scholar] [CrossRef] 
[26] Rafique, S., Nizami, M.S.H., Irshad, U.B., Hossain, M.J. and Mukhopadhyay, S.C. (2022) A Two-Stage Multi-Objective Stochastic Optimization Strategy to Minimize Cost for Electric Bus Depot Operators. Journal of Cleaner Production, 332, Article 129856. [Google Scholar] [CrossRef] 

为你推荐