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

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

Abstract

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

CLC Number:

U121

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.

Figures/Tables 16

Fig.1

Fig.2

Table 1

Beijing time-of-use electricity price"

$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

Table 1

Table 2

Temperature change table"

$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

Table 2

Table 3

Electric bus and driver-related parameters"

对象	参数	取值
车辆	$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

Table 3

Table 4

Algorithm related parameters"

参数	取值		取值
$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

Table 4

Fig.3

Table 5

Comparison of results before and after optimization"

解	$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

Table 5

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Table 6

Comparison of different results with different k1"

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

Table 6

Fig.9

Fig.10

References 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]	SU Yuejiang, WEN Huiying, YUAN Minxian, et al. Travel Carbon Emission Prediction Model Based on Resident Attribute Data [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(8): 23-33.
[2]	YANG Yazao, WENG Tangzheng. Impact of Spatiotemporal Constraints on Active Travel [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(2): 113-123.
[3]	LU Yiqin, HUANG Chenghai, CHEN Jiarui, et al. Time Sensitive Network Scheduling Method Based on Genetic Algorithm [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(2): 1-12.
[4]	ZHUANG Yan, DONG Chunjiao, MI Xueyu, et al.. Identification of Accident Black Spots Based on Improved Network Kernel Density and Negative Binomial Regression [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(1): 119-126.
[5]	ZHAO Xiaomei, HAO Guoyu, NIU Xiaojing, et al.. Traffic Boundary Control Strategy Based on Macroscopic Fundamental Diagram Under Different Rainfall [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(1): 72-82.
[6]	HU Xinghua, CHEN Xinghui, WANG Ran, et al. Optimization Model of Bus Priority Control Considering Carbon Emissions with Stochastic Characteristics [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 160-170.
[7]	XU Lunhui, YU Jiaxin, PEI Mingyang, et al. Repositioning Strategy for Ride-Hailing Vehicles Based on Geometric Road Network Structure and Reinforcement Learning [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 99-109.
[8]	SHEN Yutong, LI Ming, CUI Zhiyong, et al. Study on the Multi-Period Allocation Method of Vehicle Resource in Hybrid Service Mode [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 89-98.
[9]	WANG Hao, XIE Ning . Coordinated Optimization Model of Arterial Segmented Green Waves Considering the Efficiency of Tram Operation [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(1): 95-105.
[10]	ZHAO Jiandong, ZHU Dan, LIU Jiaxin. Metro Transfer Passenger Flow Prediction Based on STL-GRU [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(5): 22-31.
[11]	WU Jiaorong XIE Jinhong WANG Yuqin. The Profiling Method of Instability of Bus Route Operation and Its Application [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(2): 15-22.
[12]	CHEN Xiaohong, HU Fang . Interval Optimization Model of Signal Control at Intersection Based on Possibility Degree [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(10): 29-40.
[13]	YU Lijun. Generalized System-Optimal Traffic Assignment with Link Capacity Constraints [J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(4): 140-148.
[14]	YAO Enjian LU Muyang LIU Yuhuan YUAN Ling. Electric Bus Area Driving Plan Preparation Considering Charging Constraints [J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(9): 68-73.
[15]	LIU Zhongbo ZHAO Xiaohui. A Dynamic Allocation and Guidance Model for Parking Spaces with Minimum Total Parking Costs#br# [J]. Journal of South China University of Technology(Natural Science Edition), 2018, 46(9): 92-98.