Cross-line Combined Bus Scheduling Optimization Method Based on Passenger Flow Characteristic Identification

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

Abstract

Abstract:

With the increase of residents’ travel demand, there are higher requirements for bus operation efficiency and service quality. But bus operation companies usually adopt single-line scheduling, which often leads to the mismatch between passenger flow and transport capacity input, low bus service level, and resource utilization inefficiency. A more efficient scheduling optimization method is urgently needed. In the combined scheduling mode, manpower and vehicles are shared among multiple lines, which helps to integrate the existing bus resources and improve the matching degree of supply and demand of transport capacity and bus operation efficiency. In this paper, the identification rules of the cross-line scheduling line group and the determination method of the number of cross-line vehicles were proposed based on the characteristics of passenger flow. The optimization goal was to minimize the sum of passenger travel costs and bus operating costs, and an optimization model of bus cross-line combined scheduling with cross-line vehicles was constructed. The departure type and departure interval was encoded and it was solved by an improved genetic algorithm. The lines No.668 and No.122 in Beijing were selected as the case of cross-line combination scheduling, and the average waiting time of passengers, line load factor, capacity matching degree, passenger flow intensity and other indicators were introduced to evaluate the effectiveness of the optimization model. The results show that, under the condition of bus cross-line scheduling, the average waiting time of passengers on the supported bus lines is shortened by 11.8%; the line load factor is reduced by 9.8%; the capacity matching degree and passenger flow intensity are increased by 7.7% and 8.7%, respectively; passenger travel costs and bus operating costs are reduced by 15% and 6%, respectively.

Key words: transportation engineering, public transportation, bus scheduling, optimization strategy, cross-line combined scheduling, genetic algorithm

CLC Number:

U491

WENG Jiancheng, WANG Maolin, LIN Pengfei, et al. Cross-line Combined Bus Scheduling Optimization Method Based on Passenger Flow Characteristic Identification[J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(9): 39-48.

Figures/Tables 13

Fig.1

Table 1

Model parameters and definitions"

模型参数	定义	单位
$i$ ， $i'$	站点
n	线路站点数量	站
k	发出的第k次车， $k ∈ K$
$△ t k$	第k辆车与k-1辆车的发车间隔	min
$σ$	乘客候车的单位时间费用	元/（人·min）
$p [i] [i']$	在站点 $i$ 上车和在站点 $i'$ 下车的乘客平均到达率	人/min
d	车辆的座位数	人/辆
$d m$	跨线车辆座位数	人/辆
$d B$	$L 2$ 线路原车辆座位数	人/辆
$S i$	站点 $i - 1$ 和站点 $i$ 之间的路段通过量	人
$P i$	站点 $i$ 的上车乘客数量	人
$Q i$	站点 $i$ 的下车乘客数量	人
$B i$	车辆在站点 $i$ 的区间满载率
$B o$	公交车满载率临界值
$ε$	拥挤惩罚系数的参数
$e m$	跨线车辆额定载客量	人/辆
$e B$	$L 2$ 线路原车辆额定载客量	人/辆
$L i$	站点 $i$ 与下一站点的间距	km
$L$	线路长度	km
$C m 1$	跨线车辆每公里运营成本	元
$C B 1$	$L 2$ 线路原车辆每公里运营成本	元
$C p$	一辆 $L 2$ 线路车辆固定折合成本	元
$p m j$	发出的跨线车辆数	辆
$P B j$	发出的 $L 2$ 线路原车辆数	辆
$C Y 1 → Y 2$	跨线车辆 $Y 1 → Y 2$ 转场跨线成本	元
C	跨线调度总成本	元
$C 1$	乘客出行成本	元
$C 2$	公交运营成本	元
$α$	乘客出行成本权重系数
$β$	公交运营成本权重系数
$C 11$	乘客候车时间成本	元
$C 12$	乘客车内拥挤成本	元
$C m j$	跨线车辆转场成本	元
$C B j$	线路车辆运营成本	元
$C B p$	车辆固定折合成本	元

Table 1

Table 2

Example of the departure interval"

方案	$Δ t 1$	$Δ t 2$	$Δ t 3$	$Δ t 4$	…	$Δ t k - 1$	$Δ t k$
1	4	6	7	5	…	4	7
2	5	5	5	5	…	4	5
3	6	4	8	5	…	7	7
4	6	3	7	7	…	6	9

Table 2

Fig.2

Table 3

Examples of chromosomes corresponding to candidate solutions"

基因位置（时间）	基因段	对应发车类型		基因位置（时间）	基因段	对应发车类型
$Δ t 1$	1	原车辆		$Δ t 1$	1	原车辆
$Δ t 2$	1	原车辆	$Δ t 2$		0	跨线车
$Δ t 3$	0	跨线车	$Δ t 3$		1	原车辆
$Δ t 4$	1	原车辆	$Δ t 4$		1	原车辆
?	?	?	?		?	?
$Δ t k - 1$	1	原车辆	$Δ t k - 1$		0	跨线车
$Δ t k$	0	跨线车	$Δ t k$		1	原车辆

Table 3

Table 4

Genetic algorithm mutation operation"

基因位置（时间）	基因段	变异基因段		基因位置（时间）	基因段	变异基因段
$Δ t 1$	1	1		$Δ t 1$	1	1
$Δ t 2$	1	1	$Δ t 2$		0	0
$Δ t 3$	0	1	$Δ t 3$		1	1
$Δ t 4$	1	1	$Δ t 4$		1	0
?	?	?	?		?	?
$Δ t k - 1$	1	1	$Δ t k - 1$		0	0
$Δ t k$	0	0	$Δ t k$		1	1

Table 4

Fig.3

Table 5

Line 668 and line 122 crossover group identification indicators"

指标项

起终点距离/km

高峰时段

方向不均衡系数

大间隔比率

668路 $L 1$

（支援线路）

0.27

7：00~8：00

1.41

122路 $L 2$

（被支援线路）

0.27

8：00~9：00

1.13

识别规则与结论

小于2 km，符合

高峰时段相异，符合

L 1

系数大，符合

L 2

比率高，符合

Table 5

Table 6

Table 7

Values of relevant parameters set by the model"

符号	参数含义	取值
$T j$	研究时段长度	120 min
n	线路站点数量	28
L	线路长度	21.15 km
$d m$	跨线车辆座位数	36人/辆
$e m$	跨线车辆额定载客数	80人/辆
$d B$	$L 2$ 线路原车辆座位数	27人/辆
$e B$	$L 2$ 线路原车辆额定载客数	65人/辆
$ε$	拥挤惩罚系数参数	0.03
$B o$	车辆临界满载率	1.1
$α$	乘客出行成本权重系数	0.7
$β$	公交运营成本权重系数	0.3
$Δ T m i n$	最小发车间隔	3 min
$Δ T m a x$	最大发车间隔	8 min
$C Y 1 → Y 2$	跨线车辆 $Y 1 → Y 2$ 转场跨线成本	60元/辆
$c m 1$	跨线车辆每公里运营成本	2.96元
$c B 1$	$L 2$ 线路原车辆每公里运营成本	2.07元

Table 7

Table 8

Table 9

Cost changes before and after the implementation of cross-line scheduling"

跨线运营系统成本		跨线调度成本/元		优化效果
跨线运营系统成本		优化前	优化后	优化效果
乘客出行成本	乘客候车时间成本	2 854	2 524	减少15% （555元）
乘客出行成本	乘客车内拥挤成本	764	539	减少15% （555元）
公交运营成本	$L 2$ 线路原车辆运营成本	2 410	1 406	减少6% （146元）
公交运营成本	跨线车辆运营成本	0	858	减少6% （146元）
系统总成本		6 028	5 327	减少12% （701元）

Table 9

Table 10

References 24

1	李俊升．公交都市背景下郑州市轨道交通与常规公交衔接评价及优化［D］．郑州：郑州大学，2020.
2	魏贺，戴冀峰．对“公交都市”考核评价指标体系的深入思考［C］‍∥2013年中国城市交通规划年会.青岛：［s.n.］，2014：989-999.
3	北京交通发展研究院. 2021北京市交通发展年度报告［R］．北京：北京交通发展研究院， 2021.
4	张泉．公交优先［M］．北京：中国建筑工业出版社，2010.
5	严亚丹．基于运行可靠性的公交调度控制研究［D］．南京：东南大学，2012.
6	章昱，姜传.北京公交区域调度系统研究与应用［J］．人民公交，2019，37（12）：73-79.
	ZHANG Yu， JIANG Chuan. Research and application of Beijing bus regional scheduling system［J］．People’s Public Transportation，2019，37（12）：73-79.
7	巫威眺，靳文舟，魏明，等.配合区间车的单线公交组合调度模型［J］.华南理工大学学报（自然科学版），2012，40（11）：147-154.
	WU Wei-tiao， JIN Wen-zhou， WEI Ming，et al. Mixed scheduling model of single-Line bus for zonal vehicles ［J］．Journal of South China University of Technology （Natural Science Edition），2012，40（11）：147-154.
8	巫威眺，靳文舟，任然.单线公交车辆组合调度与购车计划的双层规划模型［J］．吉林大学学报（工学版），2013，43（5）：1196-1203.
	WU Wei-tiao， JIN Wen-zhou， REN Ran. Bi-level programming model for transit mixed scheduling and procurement scheme［J］．Journal of Jilin University（Engineering and Technology Edition），2013，43（5）：1196-1203.
9	靳文舟，巫威眺.预算限制下的单线公交车辆组合调度模型［J］．吉林大学学报（工学版），2014，44（1）：54-61.
	JIN Wen-zhou， WU Wei-tiao. Single-line transit mixed scheduling model with financial constraints ［J］．Journal of Jilin University （Engineering and Technology Edition），2014，44（1）：54-61.
10	IBARRA-ROJAS O J， GIESEN R， RIOS-SOLIS Y A. An integrated approach for timetabling and vehicle scheduling problems to analyze the trade-off between level of service and operating costs of transit networks［J］．Transportation Research Part B：Methodological，2014，70（12）：35-46.
11	滕靖，林琳，陈童．纯电动公交时刻表和车辆排班计划整体优化［J］．同济大学学报（自然科学版），2019，47（12）：1748-1755.
	TENG Jing， LIN Lin， CHEN Tong ．Optimizing the combination of timetable and vehicle scheduling for pure electric buses ［J］．Journal of Tongji University （Natural Science），2019，47（12）：1748-1755.
12	刘畅. 基于混合启发式算法的单线公交车辆调度问题研究［D］．北京：北京交通大学， 2016.
13	姚恩建，刘彤，郇宁，等．常规公交线路发车间隔及车型配置优化［J］．北京交通大学学报，2020，44（4）：86-93.
	YAO En-jian， LIU Tong， XUN Ning，et al ．Study on optimization of departure interval and vehicle type configuration of regular bus lines［J］．Journal of Beijing Jiaotong University，2020，44（4）：86-93.
14	SUN DanielJian）， XU Ya， PENG Zhong-ren ．Timetable optimization for single bus line based on hybrid vehicle size model［J］．Journal of Traffic and Tran-sportation Engineering（English Edition），2015，2（3）：179-186.
15	杨信丰，李引珍，何瑞春.基于服务水平的区域公交协调调度优化研究［J］．系统工程，2017，35（6）：89-96.
	YANG Xin-feng， LI Yin-zhen， HE Rui-chun ．Research on regional public transit coordinated scheduling optimization based on service level［J］．Systems Engineering，2017，35（6）：89-96.
16	GKIOTSALITIS K， WU Z， CATS O ．A cost-minimization model for bus fleet allocation featuring the tactical generation of short-turning and interlining options［J］．Transportation Research Part C：Emerging Technologies，2018，98（1）：14-36.
17	CEDER A， GOLANY B，TAL O ．Creating bus timetables with maximal synchronization［J］．Transportation Research Part A：Policy and Practice，2001，35（10）：913-928.
18	SCHMID V， EHMKE J F ．Integrated timetabling and vehicle scheduling with balanced departure times［J］．OR Spectrum，2015，37（4）：903-928.
19	陈晓旭，项煜，杨超，等．基于遗传算法的公交线路发车间隔优化［J］．交通与运输，2020，36（5）：86-90.
	CHEN Xiao-xu， XIANG Yu， YANG Chao，et al. Departure interval optimization of bus line based on genetic algorithm［J］．Traffic and Transportation， 2020，36（5）：86-90.
20	王佳冬，袁振洲．考虑换乘客流的城轨应急接运公交调度优化模型［J］．东南大学学报（自然科学版），2021，51（1）：161-170.
	WANG Jia-dong， YUAN Zhen-zhou ．Optimization model of bus bridging scheduling with passengers transferring from urban rail transit［J］．Journal of Southeast University（Natural Science Edition），2021，51（1）：161-170.
21	马原响.智能优化算法简述［J］．科学技术创新， 2021，25（3）：123-124.
	MA Yuan-xiang ．Brief description of intelligent optimization algorithm ［J］．Science and Technology Innovation，2021，25（3）：123-124.
22	李雪，朱一洲．考虑多车型的公交组合服务方案优化［J］．自动化与仪表，2020，35（8）：93-97.
	LI Xue， ZHU Yi-zhou. Considering the optimization of multi-vehicle bus service plan［J］．Automation and Instrumentation，2020，35（8）：93-97.
23	HOLLAND J H. Adaptation in natural and artificial systems［J］．Quarterly Review of Biology，1992，6（2）：126–137.
24	北京市统计局．北京统计年鉴2020［M］．北京：中国统计出版社，2021.

指标项	乘客平均候车时间/min	线路满载率	线路运营匹配度	线路客流强度/（人·（km）^-1）
优化前	3.46	0.82	79.4	10.38
优化后	3.05	0.74	85.5	11.29
优化效果	减少11.8%	减少9.8%	增加7.7%	增加8.7%

[1]	ZHAO Xiaomei, ZHU Xiangyuan, WANG Qin, et al. Operational Reliability Optimization Strategies of Multi-type Bus Lines [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(8): 32-39.
[2]	CHEN Yanyan, WANG Zifan, SUN Haodong, et al. Stuby on the Activity Patterns and Regularity of Public Transport Passengers [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(8): 40-50.
[3]	QIU Yudong, WANG Zhan, XIE Zhishen. Optimization for Steel Frames with Semirigid Connections Based on Hybrid Algorithms [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(6): 72-77.
[4]	BIE Yiming, ZHU Aoze, CONG Yuan. Electric Bus Scheduling Method Considering Differences in the State of Health of Batteries [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 11-21.
[5]	YANG Min, CHEN Shantao, JIANG Ruiyu, et al. Flexible Bus Scheduling Optimization for Integrated Hub Connections in the Context of MaaS [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(10): 22-30.
[6]	QIN Yaqin, QIAN Zhengfu, XIE Jiming, et al. Cooperative Lane Change Decision-Making Model of Bottleneck Emergency Section in Weaving Area Based on Social Force [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(7): 66-75.
[7]	ZHENG Yajing, LI Yaohui, JIN Wenzhou. Connection Scheme Optimization of Last Trains of Urban Mass Transit Network Based on Considering the Transfer Passengers [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(5): 32-39,72.
[8]	XIA Qinxiang, LI Kai, MA Jun, et al. Die Electrode Scheduling Problem Solution Based on Genetic Algorithm [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(3): 80-87.
[9]	ZHOU Zhong, DENG Zhuoxiang, CHEN Yun, et al. Strength Prediction of Foam Light Soil Based on GA-BP Neural Network [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(11): 125-132.
[10]	LIU Xuan, WANG Zihang, ZHANG Tongrui, et al. Optimal Control Strategy for Lateral Stability of Port Heavy-Duty AGV [J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(8): 113-121.
[11]	LI Jing WANG Chen ZHANG Jiaxu. Vehicle Speed Estimation Based on UniTire Model [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(5): 47-55.
[12]	LUO Yutao, ZHOU Tianyang, XU Xiaotong. Time-Varying LQR Control of Four-Wheel Steer /Drive Vehicle Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(3): 114-122.
[13]	JIN Gang HE Zhihao WANG Yingjun. 5G Frequency Selection Surface Shape Optimization Method Based on Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(11): 95-105.
[14]	LI Jiale LIU Zhenbo WANG Xuefei. Distribution Path Optimization of Electric Vehicles Considering Charging and Discharging Strategy in Smart Grid [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(10): 31-40.
[15]	JIN Wenzhou, HU Weiyang, DENG Jiayi, et al. Flexible Scheduling Model of Demand Ｒesponse Transit Based on Hybrid Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(1): 123-133.