Dynamic Fleet Management of Shared Autonomous Vehicles with
Rolling Horizon Optimization

doi:10.16097/j.cnki.1009-6744.2022.03.006

Abstract

Abstract: The shared autonomous vehicle (SAV) is an essential component in future urban transportation systems. This paper investigates an optimization approach to the dynamic operationof a SAV fleet with stochastic demand. A timespace network is first constructed to characterize the fleet management problem. Different types of time-space arcs are generated to indicate the vehicle-trip assignment and empty vehicle relocation. Under the framework of approximated dynamic programming, this paper develops a mathematic programming model to maximize the operational profit, in which the flow of nodes is taken as vehicle states and the flow of arcs is taken as decision variables. The rolling horizon optimization, also referred as lookahead policy, is designed for the optimization problem. A stochastic program with a lookahead horizon is developed and solved by the CPLEX solver. A numerical case study is performed with the Sioux Falls network. The rolling horizon optimization approach can provide effective operational decisions of dynamic fleet management. Considering the computational time limit, a long lookahead horizon with a medium- size sample would produce better optimization results. The objective of maximizing the operational benefit while minimizing the passenger waiting time would also result in more effective decisions of the dynamic fleet management.

Key words: urban traffic, shared mobility, autonomous vehicles, rolling horizon, dynamic program, stochastic demand

摘要： 共享自动驾驶汽车被视为未来城市交通系统的重要组成部分。本文考虑随机订单需求研究共享自动驾驶汽车的动态调度优化方法。通过建立车辆调度时空网络，分别针对订单分配与空车移位生成车辆运行时间弧，提出车辆调度问题的刻画方法。基于马尔科夫决策框架，以时空节点流量为状态，以时空弧流量为决策变量，建立最大化系统净收益的车辆动态调度优化模型。采取滚动时域优化思想，建立含前视时间窗的随机规划模型，并利用CPLEX优化引擎，滚动求解车辆动态调度决策结果。Sioux Falls网络算例结果表明，滚动时域优化方法可保证车辆动态调度决策效果，提升系统运营效率。在计算时间限制下，滚动时域方法应优先采用长时间窗中等规模样本。在最大化系统净收益的同时进一步最小化乘客等待时间，可有效提升车辆动态调度决策效果。

关键词: 城市交通, 共享出行, 自动驾驶, 滚动时域, 动态规划, 随机需求

CLC Number:

U121

CHEN Yao , BAI Yun , ZHANG An-ying , MAO Bao-hua , CHEN Shao-kuan. Dynamic Fleet Management of Shared Autonomous Vehicles with Rolling Horizon Optimization[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 45-52.

陈垚, 柏赟, 张安英, 毛保华, 陈绍宽. 基于滚动时域优化的共享自动驾驶汽车动态调度方法[J]. 交通运输系统工程与信息, 2022, 22(3): 45-52.

Add to citation manager EndNote|Ris|BibTeX

URL: http://www.tseit.org.cn/EN/10.16097/j.cnki.1009-6744.2022.03.006

http://www.tseit.org.cn/EN/Y2022/V22/I3/45

References

[1] 胡笳, 罗书源, 赖金涛, 等. 自动驾驶对交通运输系统规划的影响综述[J]. 交通运输系统工程与信息, 2021, 21(5): 52-65. [HU J, LUO S Y, LAI J T, et al. A review of the impact of autonomous driving on transportation planning[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 52-65.]

[2] 陈喜群. 网约共享出行研究综述[J]. 交通运输系统工程与信息, 2021, 21(5): 77-90. [CHEN X Q. Review of app-based ridesharing mobility research[J]. Journal of Transportation Systems Engineering and Information Technology, 2021, 21(5): 77-90.]

[3] 姚晓锐, 王冠, 杨超. 未来城市自动驾驶共享汽车规模研究: 以上海为例[J]. 交通运输系统工程与信息, 2019, 19(6): 85- 91. [YAO X R, WANG G, YANG C. Exploring fleet size of shared autonomous vehicles in future city: A case study in Shanghai[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(6): 85-91.]

[4] GUO H, CHEN Y, LIU Y. Shared autonomous vehicle management considering competition with human-driven private vehicles[J]. Transportation Research Part C: Emerging Technologies, 2022, 136: 103547.

[5] DANDL F, HYLAND M, BOGENBERGER K, et al. Evaluating the impact of spatio-temporal demand forecast aggregation on the operational performance of shared autonomous mobility fleets[J]. Transportation, 2019, 46(6): 1-22.

[6] FAGNANT D J, KOCKELMAN K M. The travel and environmental implications of shared autonomous vehicles, using agent-based model scenarios[J]. Transportation Research Part C: Emerging Technologies, 2014, 40: 1-13.

[7] 姚荣涵, 梁亚林, 刘锴, 等. 考虑合乘的共享自动驾驶汽车选择行为实证分析[J]. 交通运输系统工程与信息, 2020, 20(1): 228-233. [YAO R H, LIANG Y L, LIU K, et al. Empirical analysis of choice behavior for shared autonomous vehicles with concern of ride-sharing [J]. Journal of Transportation Systems Engineering and Information Technology, 2020, 20(1): 228-233.]

[8] SEO T, ASAKURA Y. Multi-objective linear optimization problem for strategic planning of shared autonomous vehicle operation and infrastructure design [J]. IEEE Transactions on Intelligent. Transportation Systems, 2022, 23(4): 3816-3828.

[9] HYLAND M, MAHMASSANI H S. Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign AVs to immediate traveler demand requests[J]. Transportation Research Part C: Emerging Technologies, 2018, 92: 278-297.

[10] HÖRL S, RUCH C, BECKER F, et al. Fleet operational policies for automated mobility: A simulation assessment for Zurich[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 20-31.

[11] MAO C, LIU Y, SHEN Z J. Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach[J]. Transportation Research Part C: Emerging Technologies, 2020, 115: 102626.

[12] KANG D, LEVIN M W. Maximum-stability dispatch policy for shared autonomous vehicles[J]. Transportation Research Part B: Methodology, 2021, 148: 132-151.

[13] AI-KANJ L, NASCIMENTO J, POWELL W B. Approximate dynamic programming for planning a ridehailing system using autonomous fleets of electric vehicles[J]. European Journal of Operational Research, 2020, 284: 1088-1106.

[14] POWELL W B, SIMAO H P, BOUZAIENE-AYARI B. Approximate dynamic programming in transportation and logistics: A unified framework[J]. Euro Journal on Transportation & Logistics, 2012, 1(3): 237-284.

[15] CHEN Y, MAO B, BAI Y, et al. Optimal coordination of last trains for maximum transfer accessibility with heterogeneous walking time[J]. Journal of Advanced Transportation, 2019, 2019: 9692024.

[16] Transportation Networks for Research Core Team. Transportation networks for research [EB/OL]. (2021- 10- 22) [2021- 11- 09]. https: // github. com/ bstabler/ TransportationNetworks.

Dynamic Fleet Management of Shared Autonomous Vehicles with Rolling Horizon Optimization

基于滚动时域优化的共享自动驾驶汽车动态调度方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LI Wan-ying, GUAN Hong-zhi, HAN Yan , CAO Yang-liu. Pricing Game Model of Travel Service Chain Under Social Preference View [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 11-22.
[2]	CHEN Peng , TANG Peng , YAN Wei-xi , SUN Qiu-yue. Modeling and Simulation of Pedestrian Crossing Behavior at Uncontrolled Mid-block Crosswalk [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 79-88.
[3]	LI Tong-fei, CAO Ya-ning, DOU Xue-ping , XIONG Jie, XU Yan, ZHOU Wen-han. Layout Optimization of Smart Intersections Under Novel Mixed Traffic Flow [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 302-312.
[4]	JIANG Yang-sheng , YU Gao-shang, HU Lu, LI Yan. Refined Classification of Urban Rail Transit Stations Based on Clustered Station's Passenger Traffic Flow Features [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 106-112.
[5]	YUAN Hong-xia , XU Ling , YAN Yu-song , JIANG Wen-hui. Accessibility to Urban Rail Transit Based on Enhanced Two-step Floating Catchment Area Method [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 113-119.
[6]	LIU Ming-min, HE Hong-jie, JIN An. An Auxiliary Model for Preliminary Planning of Rail Transit Networks and Lines with Given Station Locations [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 120-128.
[7]	ZHU Shun-ying , LIAO Ling-yun, WU Jing-an, CHANG Hong-guang, WANG Hong. Urban Passenger Transportation Mode Carbon Emission Efficiency Difference: A Case Study of Xiangyang City [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 158-166.
[8]	FENG Hai-xia , WANG Xing-yu , XIAN Hua-cai , LIU Xin-hua , LI Jian , NING Er-wei. Impact of Urban Traffic Operations on Vehicle Carbon Dioxide Emission [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 167-175.
[9]	LIU Jia-lin , JIA Bin , LIU Zheng , JIANG Rui , LI Xin-gang. Collaborative Optimization of Multimodal Evacuation Traffic Fleet Configuration and Lane Allocation [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 176-185.
[10]	WU Jing-xian, QIAN Yi-nan, HAN Yin. Relationship Between Built Environment and Elderly Active Travel of Based on Group Heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 194-201.
[11]	LI Jun-xian , SHEN Zhou-biao , TONG Wen-cong , WU Zhi-zhou. A Fuzzy Temporal Network Model for Identifying Critical Intersections in Urban Road Network [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 202-209.
[12]	XIE Liang-hui , ZHANG Zhen-ji, GONG Da-qing. A Heuristic Close Contact Tracing Method for Urban Rail Transit [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 218-227.
[13]	WANG Xiao-ning , CUI Zi-yu , ZHANG Yu. Decision Making of Opening Gated Community Considering Traffic Impact on Environment [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(4): 228-235.
[14]	YANG Ya-zao, TANG Hao-dong, PENG yong. Residents' Travel Mode Choice Behavior in Post-COVID-19 era Considering Preference Differences [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 15-24.
[15]	CHEN Qi-xiang , LV Bin , CHEN Xi-qun , HAO Bin-bin, HE Jia-xi. Impacts of Built Environment on Competition and Cooperation Relationship Between Taxi and Subway Considering Spatial Heterogeneity [J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(3): 25-35.