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

doi:10.12141/j.issn.1000-565X.240440

摘要/Abstract

摘要：

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

关键词: 城市交通, 联合调度, 多目标粒子群算法, 环线电动公交, $ε$ 约束处理

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.

Key words: urban traffic, joint scheduling, multi-objective particle swarm algorithm, loop line electric bus, ε constraint processing

中图分类号:

U121

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

HU Baoyu, QI Yue, JIA Dianjing, CHENG Guozhu. Joint Optimization of Loop Line Electric Bus Vehicle Scheduling and Driver Scheduling[J]. Journal of South China University of Technology(Natural Science Edition), 2025, 53(6): 91-103.

图/表 16

图1

图2

表1

北京市分时电价"

$q$	$E q / (元 · k W - 1 · h - 1)$
23：00—07：00	0.95
07：00—10：00、22：00—23：00	1.26
10：00—13：00、17：00—22：00	1.57
13：00—17：00	1.28

表1

表2

温度变化表"

$q$	$θ i v$ /℃		$θ i v$ /℃
20：00—03：00、 09：00—10：00	0	12：00—14：00	9
03：00—05：00	-2	14：00—15：00、 16：00—17：00	10
05：00—06：00、 08：00—09：00	-3	15：00—16：00	12
06：00—08：00	-4	17：00—18：00	6
10：00—11：00	4	18：00—20：00	3
11：00—12：00	7

表2

表3

电动公交和司机相关参数"

对象	参数	取值
车辆	$C v / 元$	250
	$N v m a x$	9
	$t m i n v / m i n$	3
司机	$C d / 元$	200
	$λ$	3
	$t m i n / m i n$	5
	$T m i n / m i n$	30
	$N d m a x$	8
	$N d m i n$	3

表3

表4

算法相关参数"

参数	取值		取值
$N g m a x$	500	$N p$	20
$ω ˜ s$	0.4	$N r$	20
$f 1 g$	1	$ω ˜ e$	0.99
$f 2 g$	2

表4

图3

表5

优化前后结果对比"

解	$Z 1$ /元	$Z 2$ /min	总运营成本优化比例/%	平均每个发车时刻调整量/min
$S 0$	17 497.02	0
$S 1$	14 604.17	685	16.53	4.15
$S 2$	14 604.17	682	16.53	4.13
$S 3$	14 604.24	681	16.53	4.13
$S 4$	14 672.78	676	16.14	4.10
$S 5$	14 672.79	674	16.14	4.08
$S 6$	14 914.96	671	14.76	4.07

表5

图4

图5

图6

图7

图8

表6

k1不同时的结果对比"

$k 1$	车队规模/辆	司机数量/个
0.0	23	24
0.1	23	25
0.2	23	25
0.3	23	24
0.4	23	24

表6

图9

图10

参考文献 20

1	FRELING R， HUISMAN D， WAGELMANS P M ．Models and algorithms for integration of vehicle and crew scheduling［J］．Journal of Scheduling，2003，6：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 Spectrum，2017，39（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 Science，2010，44：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：Methodological，2018，112：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 Research，2017，27：39-67.
6	侯彦娥，孔云峰，朱艳芳，等．公交司机排班问题的混合元启发算法研究［J］．交通运输系统工程与信息，2018，18（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 Technology，2018，18（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：Methodological，2021，145：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 Technologies，2019，101：145-160.
9	刘昊翔，吴啊峰，龙建成，等．基于列生成启发式的单线电动公交车与司机整合调度优化［J］．交通运输系统工程与信息，2021，21（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 Technology，2021，21（4）：211-220.
10	孔云峰．多目标公交车辆与司机调度问题元启发算法设计［J］．交通信息与安全，2021，39（3）：50-59.
	KONG Yunfeng ．A metaheuristic algorithm for multi-objective transit bus and driver scheduling problems［J］．Journal of Transport Information and Safety，2021，39（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 Transportation，2021，16：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 Environment，2023，117：103653/1-23.
14	SISTIG H M， SAUER D U ．Metaheuristic for the integrated electric vehicle and crew scheduling problem ［J］．Applied Energy，2023，339：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］．Complex，2022，2022：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 Transportation，2022，16（1）：73-83.
17	翁剑成，乔润童，王茂林，等．考虑场景差异性的混合车型公交调度优化方法［J］．交通运输系统工程与信息，2024，24（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 Technology，2024，24（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 Research，2022，2：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.

[1]	谢坤, 邢馨元, 董宏辉, 董春娇, 陈元朵. 轨迹数据驱动的职住地识别及出行活动特征分类方法[J]. 华南理工大学学报(自然科学版), 2025, 53(6): 131-139.
[2]	龙雪琴, 翟曼溶, 王远泽, 毛健旭. 考虑乘客时间-价格弹性的网约车合乘匹配方法[J]. 华南理工大学学报(自然科学版), 2025, 53(6): 119-130.
[3]	何庆龄, 裴玉龙, 董春彤, 等. 基于混合策略改进ASO-LSSVM的风险驾驶行为分类识别[J]. 华南理工大学学报(自然科学版), 2024, 52(9): 131-141.
[4]	翁剑成, 吴明珠, 魏瑞聪, 等. 多因素协同的大型活动场馆周边路段速度预测[J]. 华南理工大学学报(自然科学版), 2024, 52(8): 34-44.
[5]	苏跃江, 温惠英, 袁敏贤, 等. 基于居民属性数据的出行碳排放预测模型[J]. 华南理工大学学报(自然科学版), 2024, 52(8): 23-33.
[6]	杨亚璪, 翁唐政. 时空约束对运动出行的影响[J]. 华南理工大学学报(自然科学版), 2024, 52(2): 113-123.
[7]	陆以勤, 黄成海, 陈嘉睿, 等. 基于遗传算法的时间敏感网络调度方法[J]. 华南理工大学学报(自然科学版), 2024, 52(2): 1-12.
[8]	唐进君, 任茂昕, 李志涛, 等. 基于代理模型辅助NSGA-Ⅱ算法的地铁接驳公交优化[J]. 华南理工大学学报(自然科学版), 2024, 52(11): 95-105.
[9]	庄焱, 董春娇, 米雪玉, 等. 基于改进网络核密度和负二项回归的事故黑点鉴别[J]. 华南理工大学学报(自然科学版), 2024, 52(1): 119-126.
[10]	赵小梅, 郝郭宇, 牛晓婧, 等. 不同降雨量下基于宏观基本图的边界控制策略[J]. 华南理工大学学报(自然科学版), 2024, 52(1): 72-82.
[11]	陈小鸿, 田田甜, 张华. 城市居民活动韧性——新冠肺炎疫情期间轨道客流恢复的实证[J]. 华南理工大学学报(自然科学版), 2023, 51(7): 109-119.
[12]	胡兴华, 陈兴辉, 汪然, 等. 随机特性下考虑碳排放的公交优先控制优化模型[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 160-170.
[13]	许伦辉, 余佳芯, 裴明阳, 等. 基于几何路网结构和强化学习的车辆重定位策略[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 99-109.
[14]	沈羽桐, 李明, 崔志勇, 等. 混合服务模式车辆资源多时段分配方法研究[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 89-98.
[15]	王昊, 谢凝. 考虑有轨电车效率的干线分段绿波协调优化模型[J]. 华南理工大学学报(自然科学版), 2023, 51(1): 95-105.