智慧交通系统

环线电动公交车辆调度与司机排班的联合优化

  • 胡宝雨 ,
  • 齐月 ,
  • 贾佃精 ,
  • 程国柱
展开
  • 1.东北林业大学 土木与交通学院,黑龙江 哈尔滨 150040
    2.辽宁省交通运输事务服务中心,辽宁 沈阳 110003
胡宝雨(1987—),男,副教授,博士生导师,主要从事公共交通规划与运营研究。E-mail: hubaoyu@nefu.edu.cn
程国柱(1977—),男,教授,博士生导师,主要从事智能交通系统、道路交通安全研究。E-mail: guozhucheng@nefu.edu.cn

收稿日期: 2024-09-02

  网络出版日期: 2024-12-13

基金资助

中国博士后科学基金项目(2023M740558);黑龙江省自然科学基金项目(YQ2022E003);东北林业大学中央高校基本科研业务费专项资金资助项目(2572023CT21-04)

Joint Optimization of Loop Line Electric Bus Vehicle Scheduling and Driver Scheduling

  • HU Baoyu ,
  • QI Yue ,
  • JIA Dianjing ,
  • CHENG Guozhu
Expand
  • 1.College of Civil Engineering and Transportation,Northeast Forestry University,Harbin 150040,Heilongjiang,China
    2.Liaoning Transportation Affairs Service Center,Shenyang 110003,Liaoning,China

Received date: 2024-09-02

  Online published: 2024-12-13

Supported by

the China Postdoctoral Science Foundation(2023M740558);the Natural Science Foundation of Heilongjiang Province(YQ2022E003)

摘要

为了解决环线电动公交车辆和司机任务分配不均衡的问题,提出了一种联合优化调度模型。该模型主要通过顺、逆时针方向互相调配车辆和司机来提高整体利用率。在给定环形线路和人车不固定的情况下,综合考虑车辆行驶里程、工作量、充电桩数量、车辆充电时间、司机工作时间、休息时间等约束,以公交企业总运营成本最小化和时刻表总调整量最小化为目标制定有序充电管理计划和车辆、司机调度方案。在求解方面,首先将混合整数非线性规划模型通过线性转换转化成线性规划模型,并使用CPLEX求解器得到调度方案;其次采用多目标粒子群算法(MOPSO)和基于ε约束处理机制的改进多目标粒子群算法(ε-MOPSO)分别求解调度方案,并通过网格法确保外部档案集的收敛性和均匀性。最后以北京市环线公交200路(内、外环)为例进行验证,对比分析CPLEX求解器、传统多目标粒子群算法以及提出的基于ε约束处理机制的改进多目标粒子群算法的计算结果。研究证实了改进算法的有效性,且优化后的调度方案分别将车辆数从28降低到23,共减少17.86%;司机数从28降低到25,共减少10.71%。车队规模和司机数量减少,从而降低了企业总运营成本;时刻表平均每个发车时刻调整4.13 min,发车更均匀保证了乘客的需求。由此提升了公共交通的运营效率,具有重要的现实意义。

本文引用格式

胡宝雨 , 齐月 , 贾佃精 , 程国柱 . 环线电动公交车辆调度与司机排班的联合优化[J]. 华南理工大学学报(自然科学版), 2025 , 53(6) : 91 -103 . DOI: 10.12141/j.issn.1000-565X.240440

Abstract

To address the issue of unbalanced task distribution between electric bus vehicles and drivers in loop line, this study proposed a joint optimal scheduling model, which mainly improves the overall utilization rate by adjusting vehicles and drivers in clockwise and counterclockwise directions. Given a fixed loop route and non-fixed vehicle-driver assignments, the model considers various constraints such as vehicle mileage, workload, number of charging stations, charging duration, driver working and rest times. It aims to minimize both the total operating cost of the transit enterprise and the total timetable adjustment, while formulating an orderly charging management plan and scheduling strategy for vehicles and drivers. In the aspect of solution, the mixed integer nonlinear programming model was transformed into linear programming model by linear transformation, and the scheduling scheme was obtained by using CPLEX solver. Additionally, a multi-objective particle swarm algorithm (MOPSO) and improved multi-objective particle swarm algorithm (ε-MOPSO) based on constraint processing mechanism were used to solve the scheduling scheme respectively, and the convergence and uniformity of external file set were ensured by grid method. The proposed approach is validated through a case study on Beijing’s Route 200 (inner and outer loop lines). A comparative analysis of the results obtained from the CPLEX solver, the traditional MOPSO, and the improved ε-MOPSO confirms the effectiveness of the improved algorithm.The optimized scheduling plan reduces the number of vehicles from 28 to 23 (a 17.86% reduction) and the number of drivers from 28 to 25 (a 10.71% reduction), thereby lowering the total operating cost. The timetable adjustments average 4.13 minutes per departure, resulting in more evenly spaced departures and better meeting passenger demand. This significantly enhances the operational efficiency of public transportation and holds substantial practical significance.

参考文献

1 FRELING R, HUISMAN D, WAGELMANS P M .Models and algorithms for integration of vehicle and crew scheduling[J].Journal of Scheduling20036:63-85.
2 SARGUT F Z, ALTUNTAS C, TULAZOGLU D C .Multi-objective integrated acyclic crew rostering and vehicle assignment problem in public bus transportation[J].OR Spectrum201739(4):1071-1096.
3 STEINZEN I, GINTNER V, SUHL L,et al .A time-space network approach for the integrated vehicle- and crew-scheduling problem with multiple depots[J].Transportation Science201044:367-382.
4 BOYER V, IBARRA-ROJAS O J, RIOS-SOLIS Y A .Vehicle and crew scheduling for flexible bus transportation systems[J].Transportation Research Part B:Methodological2018112:216-229.
5 HORVáTH M,KIS T .Computing strong lower and upper bounds for the integrated multiple-depot vehicle and crew scheduling problem with branch-and-price[J].Central European Journal of Operations Research201727:39-67.
6 侯彦娥,孔云峰,朱艳芳,等 .公交司机排班问题的混合元启发算法研究[J].交通运输系统工程与信息201818(1):133-138.
  Hou Yan-e, KONG Yun-feng, ZHU Yan-fang,et al .A hybrid metaheuristic algorithm for the transit bus and driver scheduling problem[J].Journal of Transportation System Engineering and Information Technology201818(1):133-138.
7 ANDRADE-MICHEL A, RíOS-SOLíS Y A, BOYER V .Vehicle and reliable driver scheduling for public bus transportation systems[J].Transportation Research Part B:Methodological2021145:290-301.
8 KANG L, CHEN S, MENG Q .Bus and driver scheduling with mealtime windows for a single public bus route [J].Transportation Research Part C:Emerging Technologies2019101:145-160.
9 刘昊翔,吴啊峰,龙建成,等 .基于列生成启发式的单线电动公交车与司机整合调度优化[J].交通运输系统工程与信息202121(4):211-220.
  LIU Hao-xiang, WU A-feng, LONG Jian-cheng,et al .Column generation-based heuristic approach for electric bus and driver scheduling on single bus lines[J].Journal of Transportation System Engineering and Information Technology202121(4):211-220.
10 孔云峰 .多目标公交车辆与司机调度问题元启发算法设计[J].交通信息与安全202139(3):50-59.
  KONG Yunfeng .A metaheuristic algorithm for multi-objective transit bus and driver scheduling problems[J].Journal of Transport Information and Safety202139(3):50-59.
11 杨扬 .电动公交车行车计划问题建模与算法研究[D].北京:北京交通大学,2020.
12 ZHANG A, LI T, ZHENG Y,et al .Mixed electric bus fleet scheduling problem with partial mixed-route and partial recharging[J].International Journal of Sustainable Transportation202116:73-83.
13 HE Y, LIU Z C, SONG Z Q .Joint optimization of electric bus charging infrastructure,vehicle scheduling,and charging management[J].Transportation Research Part D:Transport and Environment2023117:103653/1-23.
14 SISTIG H M, SAUER D U .Metaheuristic for the integrated electric vehicle and crew scheduling problem [J].Applied Energy2023339:120915/1-13.
15 JIANG Y, HE T .Optimal charging scheduling and management with bus-driver-trip assignment considering mealtime windows for an electric bus line[J].Complex20222022:3087279/1-19.
16 ZHANG A, LI T, ZHENG Y,et al .Mixed electric bus fleet scheduling problem with partial mixed-route and partial recharging[J].International Journal of Sustainable Transportation202216(1):73-83.
17 翁剑成,乔润童,王茂林,等 .考虑场景差异性的混合车型公交调度优化方法[J].交通运输系统工程与信息202424(4):176-187.
  WENG Jiancheng, QIAO Runtong, WANG Maolin,et al .Optimization method for mixed vehicle bus sche-duling considering scenario differences[J].Journal of Transportation Systems Engineering and Information Technology202424(4):176-187.
18 JI J H, BIE Y M, ZENG Z L,et al .Trip energy consumption estimation for electric buses[J].Communications in Transportation Research20222:100069/1-13.
19 COELLO C A C, LECHUGA M S .MOPSO:A proposal for multiple objective particle swarm optimization[C]∥ Proceedings of the 2002 Congress on Evolutio-nary Computation.Honolulu,HI:IEEE,2002:1051-1056.
20 TAKAHAMA T, SAKAI S .Constrained optimization by the ε constrained differential evolution with an archive and gradient-based mutation[C]∥ Proceedings of IEEE Congress on Evolutionary Computation.Barcelona:IEEE,2010:1-9.
文章导航

/