Dynamic Scheduling of Demand Responsive Transit Based on Model Predictive Control

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

Abstract

Abstract:

As a typical representative of the new mode of shared public transport, demand responsive transit (DRT) systems are facing the challenge of efficiently processing travel demand and real-time planning of vehicle routes. Traditional dynamic scheduling methods for DRT primarily focus on adjusting vehicle routes after demand has been realized, which often limits their ability to effectively respond to dynamic fluctuations in travel demand. Therefore, this study introduced a Model Predictive Control (MPC) approach and develops a dynamic scheduling model for DRT based on a multi-period rolling optimization framework. The model used potential future stage passenger flow information to optimize current stage scheduling decisions and timely re-planning according to the latest disclosed information to cope with the uncertainty and dynamic changes of demand. In terms of solution methods, this study integrated the adaptive large neighborhood search (ALNS) strategy to design the MPC-ALNS algorithm. It iteratively optimized the vehicle scheduling sequence through a two-phase heuristic approach. Numerical experimental results demonstrate that in ideal scenarios without prediction deviation, compared to traditional dynamic scheduling methods, the proposed method significantly reduces the total cost of the system by 14.54%. Even in a pessimistic scenario with a 30% prediction deviation, it still achieves a cost optimization of 5.27%, and various passenger service indicators show superior performance, indicating strong universal applicability in different stochastic environments. At the same time, the experiment further verified the stable optimization performance of the method in dealing with different orders and vehicle scales, and analyzed the sensitivity of the rejection cost and proposed the setting idea of the optimal rejection cost suitable for different operating scenarios.

Key words: transportation engineering, demand responsive transit, dynamic scheduling, model predictive control, adaptive large neighborhood search algorithm

CLC Number:

U491.1+7

JIN Wenzhou, ZHANG Yong, SUN Jie. Dynamic Scheduling of Demand Responsive Transit Based on Model Predictive Control[J]. Journal of South China University of Technology(Natural Science Edition), 2025, 53(6): 77-90.

Figures/Tables 14

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Fig.8

Table 2

Table 3

Fig.9

Table 4

Fig.10

References 17

1	VANSTEENWEGEN P， MELIS L， AKTAS D，et al ．A survey on demand-responsive public bus systems［J］．Transportation Research Part C：Emerging Technologies，2022，137：103573/1-39.
2	宋翠颖，王鹤玲，田泽尚，等．需求响应式公交车辆调度模型和算法研究综述［J］．北京交通大学学报，2023，47（4）：31-44.
	SONG Cuiying， WANG Heling， TIAN Zeshang，et al ．Review of demand-responsive transit vehicle scheduling models and algorithms［J］．Journal of Beijing Jiaotong University，2023，47（4）：31-44.
3	LIU Y N， OUYANG Y F ．Mobility service design via joint optimization of transit networks and demand-responsive services［J］．Transportation Research Part B：Methodological，2021，151：22-41.
4	靳文舟，胡为洋，邓嘉怡，等．基于混合算法的需求响应公交灵活调度模型［J］．华南理工大学学报（自然科学版），2021，49（1）：123-133.
	JIN Wenzhou， HU Weiyang， Deng Jiayi，et al ．Fle-xible scheduling model of demand response transit based on hybrid algorithm［J］．Journal of South China University of Technology （Natural Science Edition），2021，49（1）：123-133.
5	胡迪，靳文舟．基于站点优化的需求响应公交调度研究［J］．深圳大学学报理工版，2022，39（2）：209-215.
	HU Di， JIN Wenzhou ．Flex-route demand response transit scheduling based on station optimization［J］．Journal of Shenzhen University Science and Engineering，2022，39（2）：209-215.
6	LI X， WANG T Q， XU W H，et al ．A novel model and algorithm for designing an eco-oriented demand responsive transit （DRT） system［J］．Transportation Research Part E：Logistics and Transportation Review，2022，157：102556/1-33.
7	靳文舟，杜昊，巫威眺．基于ALNS-TS算法的半灵活型需求响应公交调度问题［J］．深圳大学学报理工版，2023，40（4）：425-434.
	JIN Wenzhou， DU Hao， WU Weitiao ．Semi-flexible demand responsive transit scheduling based on ALNS-TS algorithm［J］．Journal of Shenzhen University Science and Engineering，2023，40（4）：425-434.
8	郭梅雪，靳文舟，巫威眺．考虑充换电的模块化需求响应公交路径优化［J］．交通运输工程与信息学报，2024，22（3）：34-51.
	GUO Meixue， JIN Wenzhou， WU Weitiao ．Optimization of modular demand-responsive transit routes consi-dering charging and battery swapping［J］．Journal of Transportation Engineering and Information，2024，22（3）：34-51.
9	韩博文．考虑实时需求的需求响应式公交调度方法研究［J］．广西师范大学学报（自然科学版），2019，37（3）：9-20.
	HAN Bowen ．Demand responsive transit scheduling method considering real-time demand［J］．Journal of Guangxi Normal University （Natural Science Edition），2019，37（3）：9-20.
10	HUANG D， GU Y， WANG S，et al ．A two-phase optimization model for the demand-responsive customized bus network design［J］．Transportation Research Part C：Emerging Technologies，2020，111：1-21.
11	巫威眺，周霄，朱彦辰，等．考虑乘客时空灵活性的需求响应客货联运动态调度［J］．交通运输系统工程与信息，2023，23（4）：211-227.
	WU Wei-tiao， ZHOU Xiao， ZHU Yan-chen，et al ．Demand-responsive dynamic scheduling considering passengers’ spatio temporal flexibility for passenger and freight transportation［J］．Journal of Transportation Systems Engineering and Information Technology，2023，23（4）：211-227.
12	ALBAREDA-SAMBOLA M， FERNÁNDEZ E， LAPORTE G ．The dynamic multiperiod vehicle routing problem with probabilistic information［J］．Computers & Operations Research，2014，48：31-39.
13	NÚÑEZ A， CORTÉS C E， SÁEZ D，et al ．Multiobjective model predictive control for dynamic pickup and delivery problems［J］．Control Engineering Practice，2014，32：73-86.
14	刘亚杰，吴志永．灾后动态环境下基于MPC的应急运输实时调度［J］．控制与决策，2018，33（12）：2131-2141.
	LIU Ya-jie， WU Zhi-yong ．Real-time relief transportation planning based on MPC in post-disaster dynamic environment［J］．Control and Decision，2018，33（12）：2131-2141.
15	石建力，谢丽蓉．近似动态规划求解随机需求分批配送车辆路径问题［J］．运筹与管理，2023，32（5）：16-22.
	SHI Jianli， XIE Lirong ．Approximate dynamic programming for the split delivery vehicle routing problem with stochastic demands［J］．Operations Research and Management Science，2023，32（5）：16-22.
16	LI G L， CHEN Y X， WANG Y M，et al ．City-scale synthetic individual-level vehicle trip data［J］．Scientific Data，2023，10（1）：96/1-18.
17	刘小寒，马晓磊，刘钲可．面向公共交通的电动自动驾驶模块车调度优化［J］．中国公路学报，2022，35（3）：240-248.
	LIU Xiao-han， MA Xiao-lei， LIU Zheng-ke ．Dispatch optimization of electric autonomous modular vehicles for public transport［J］．China Journal of Highway and Transport，2022，35（3）：240-248.

订单编号	成行人数	编号		期望上车时刻	可接受最晚上车时刻	最晚容忍上车时刻
订单编号	成行人数	上车站点	下车站点	期望上车时刻	可接受最晚上车时刻	最晚容忍上车时刻
1	2	14	11	08：01：00	08：10：00	08：14：00
2	1	55	6	08：01：00	08：09：00	08：13：00
3	1	32	53	08：02：00	08：08：00	08：17：00
︙	︙	︙	︙	︙	︙	︙
119	3	20	50	09：00：00	09：05：00	09：10：00
120	4	6	50	09：00：00	09：07：00	09：14：00

车场编号	车辆编号	车辆服务订单路径
①	1	p₆→o₃→o₆→o₁₃→p₂→d₁₃→o₂₆→d₆→d₃→p₂₇→d₂₆→o₆₀→o₄₁→p₃→o₄₃→p₁₁→d₄₁→d₄₃→o₇₄→o₆₈→o₇₉→d₆₀→o₈₂→p₉→d₈₂→o₁₀₄→d₆₈→d₇₉→o₁₁₆→o₁₁₄→d₁₀₄→d₇₄→d₁₁₄→d₁₁₆
①	2	p₆→p₅→o₂₄→o₂₂→o₃₀→p₁₁→d₂₄→d₃₀→d₂₂→p₄→o₅₈→o₆₁→o₁₄₃→p₃₈→o₆₄→o₈₉→o₇₈→d₆₁→d₁₄₃→p₆→o₉₂→d₆₄→d₈₉→d₇₈→d₅₈→o₁₁₁→d₉₂→d₁₁₁
①	3	p₆→o₇→o₈→p₂₁→d₇→o₃₁→p₆→o₅₄→p₅₃→d₃₁→o₅₉→d₈→d₅₄→o₇₀→o₅₀→o₅₅→p₆→d₅₀→o₇₃→d₇₀→d₅₅→p₅₇→d₇₃→d₅₉→o₁₀₁→o₉₉→o₁₁₃→o₁₁₀→d₉₉→o₁₁₉→d₁₁₃→o₁₂₀→d₁₀₁→d₁₁₀→d₁₂₀→d₁₁₉
①	4	p₆→o₁→p₁₁→d₁→o₂₁→o₂₀→o₁₉→p₃₈→o₄₆→o₃₆→d₂₀→p₃₉→d₄₆→d₂₁→p₃₅→d₁₉→d₃₆→p₄₂→o₇₆→o₈₃→o₉₈→d₇₆→d₈₃→o₁₀₆→d₁₀₆→d₉₈
②	5	p₁→o₁₈→p₂₈→o₁₆→d₁₈→o₁₇→o₁₃₅→p₁₃→o₂₉→d₁₆→o₃₇→o₅₆→d₁₃₅→d₁₇→p₁₂→o₅₂→d₂₉→d₅₂→d₃₇→o₆₉→p₅₁→p₄₀→d₆₉→o₈₈→d₅₆→o₁₀₂→d₈₈→d₁₀₂
②	6	p₁→o₉→p₅₀→d₉→o₂₇→o₁₂→o₃₂→p₆→o₃₄→d₂₇→d₁₂→p₈→d₃₄→o₅₃→d₃₂→o₆₂→o₅₁→p₂₉→o₇₂→d₆₂→d₅₁→p₄→d₅₃→o₁₀₃→d₇₂→o₁₀₈→o₁₁₂→d₁₀₃→o₁₁₅→d₁₀₈→o₁₁₇→d₁₁₅→d₁₁₂→d₁₁₇
③	7	p₅₀→o₁₁→o₅→p₃₂→d₅→d₁₁→o₁₅→o₄₀→p₄₃→d₄₀→p₂₈→o₄₇→d₄₇→p₂₇→o₆₃→d₁₅→o₈₄→p₅₂→d₈₄→o₁₆₀→o₉₅→o₁₁₈→o₉₄→d₆₃→d₉₅→d₁₁₈→d₁₆₀→d₉₄
③	8	p₅₀→o₁₄→p₅₃→d₁₄→o₃₉→o₃₃→o₃₈→p₂₇→d₃₃→d₃₈→p₃→d₃₉→o₈₀→p₉→o₁₀₀→o₉₆→o₉₃→o₈₅→p₁₇→d₈₀→o₁₀₅→o₉₀→o₁₀₇→d₁₀₅→o₁₆₈→d₈₅→d₉₃→d₁₀₇→d₁₆₈→d₉₀→d₉₆→d₁₀₀

评估指标		指标值
服务指标	乘客总量/人	270
	服务总量/人	231
	乘客总在车时长/min	1 242.29
	乘客时间窗惩罚总时长/min	786.23
	乘客服务率/%	85.56
	额外时间系数	2.06
	人均惩罚时间/min	3.4
运营指标	出车总数量/辆	8
	车辆行驶里程/km	360.64
	车辆等待时长/min	30.64
	车均行驶里程/km	45.08
	车均等待时间/min	3.83
	目标函数值/元	1 717.04

规模场景	对比算法	目标函数值/元	乘客服务率/%	额外时间系数	人均惩罚时间/min	车均行驶里程/km	车均等待时间/min
120个订单，8辆车	MPC	1 779.50	84.04	2.07	3.28	45.70	3.39
120个订单，8辆车	传统动态调度	1 946.93	83.19	2.15	4.72	46.02	1.14
180个订单，12辆车	MPC	2 591.93	85.12	1.94	3.06	46.46	3.41
180个订单，12辆车	传统动态调度	2 886.35	84.21	2.12	4.53	46.40	2.14
240个订单，16辆车	MPC	3 309.88	86.73	1.94	2.57	45.94	5.21
240个订单，16辆车	传统动态调度	3 713.23	85.25	2.01	3.84	45.89	2.78

[1]	WEN Shengping, SU Yilong, QU Hongyi. Design of a Cascade Controller of Trajectory Tracking for Omnidirectional AGV Driven by Mecanum Wheels [J]. Journal of South China University of Technology(Natural Science Edition), 2025, 53(1): 49-61.
[2]	YUAN Renteng, WANG Chenzhu, XIANG Qiaojun, ZHENG Ou, DING Shengxuan. Trajectory Data-Driven Model for Vehicle Lane Change Intention Recognition [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(6): 34-44.
[3]	LONG Xueqin, WANG Han, WANG Ruixuan. Taxi Trajectory Characteristics Analysis Based on Frequent Sequence Mining [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(6): 24-33.
[4]	ZHANG Wenhui, LIU Tuo, SONG Yajing, et al. Identification of Hazardous Driving Hotspots of Conventional Urban Bus Based on Spatial Autocorrelation [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(4): 138-150.
[5]	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.
[6]	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.
[7]	YAO Qiangqiang, TIAN Ying, WANG Shengyuan, et al. Research on Path Tracking Control Strategy of Intelligent Vehicles Based on Force Drive [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(2): 33-41,57.
[8]	Chao-Yi Li. Model predicted control for underactuated ship path following based on extended state observer [J]. Journal of South China University of Technology(Natural Science Edition), 2021, 49(12): 143-152.
[9]	ZHANG Jiaxu, YANG Xiong, SHI Zhengtang, et al. Path Planning and Tracking Control for Emergency Lane Change and Obstacle Avoidance of Vehicles [J]. Journal of South China University of Technology(Natural Science Edition), 2020, 48(9): 86-93,106.
[10]	YIN Huajie, GUO Zhiyu, ZENG Jun. Simplified Predictive Torque Control for Induction Motor with Sliding Mode Speed-Sensorless [J]. Journal of South China University of Technology(Natural Science Edition), 2020, 48(12): 18-26.
[11]	ZHANG Nian LUO Xia ZHANG Ke. Bus Travel Choice Reversals Based on the Equate-to-Differentiate Theory [J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(9): 61-67.
[12]	QIN Datong QIN Ling. Energy Management Strategy for a Power-split Hybrid Electric Vehicle Based on Explicit Stochastic Model Predictive Control [J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(7): 112-120.
[13]	SUN Chuanyang ZHANG Xin XI Lihe CHEN Hongwei . Design for the Steering Controller of Autonomous Vehicles at the Limits of Handling [J]. Journal of South China University of Technology (Natural Science Edition), 2018, 46(3): 78-85.
[14]	DU Guiping DU Fada. Application of Finite Set Model Predictive Control in VIENNA Ｒectifier [J]. Journal of South China University of Technology(Natural Science Edition), 2018, 46(10): 9-14.
[15]	CHAI Linguo CAI Baigen SHANGGUAN Wei WANG Jian WANG Huashen. A Construction Approach Based on Kinematic Simulation Environment for Networked Intelligent Vehicles [J]. Journal of South China University of Technology (Natural Science Edition), 2018, 46(1): 66-77.