《计算机应用研究》|Application Research of Computers

基于增强学习的网格化出租车调度方法

Grid-based taxi dispatching method based on reinforcement learning

免费全文下载 (已被下载 次)  
获取PDF全文
作者 何胜学
机构 上海理工大学 管理学院,上海 200093
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)03-024-0762-05
DOI 10.19734/j.issn.1001-3695.2017.11.0995
摘要 高度信息化的网格化城市管理可以为出租车运营优化提供新的实时动态乘客需求信息和车辆位置信息。以此为契机,针对城市出租车空驶率高和司乘匹配率低的问题,提出了一种网格化的出租车实时动态调度的增强学习控制方法。通过为出租车提供空驶巡游的动态最佳路线,新的控制方法旨在提高出租车的服务效率,并降低乘客的等待时间。首先,以城市单元网格为基础,明确出租车调度的关键问题;其次,以空驶路线的动态调整为控制手段,建立调度的增强学习模型;最后,给出求解模型的Q学习算法,并通过算例验证新调度方法的有效性。研究表明新方法可以有效提高司乘匹配率、增加总的出租车运营收入、减少乘客平均等车时间和总的出租车空驶时间。
关键词 城市交通;出租车调度;增强学习;网格化管理;自适应式控制
基金项目 上海市自然科学基金资助项目(18ZR1426200)
上海理工大学人文社科攀登重点项目(SK17PA02)
上海市一流学科建设项目(S1201YLXK)
本文URL http://www.arocmag.com/article/01-2019-03-024.html
英文标题 Grid-based taxi dispatching method based on reinforcement learning
作者英文名 He Shengxue
机构英文名 BusinessSchool,UniversityofShanghaiforScience&Technology,Shanghai200093,China
英文摘要 Highly-informed grid-based city management can supply the real time passenger information and the position information of taxis for taxi operation optimization. On this account, this paper proposed a grid-based taxi dispatching dynamic control method based on reinforcement learning to solve the problem of the high vacant taxis rate and the low matching rate between taxis and passengers. By providing the optimal cruising routes for the vacant taxis, the new control method aimed to improve the service level of taxis and to lower the waiting time of passengers. Firstly, based on the grids of city, this paper clarified the key problem of taxi dispatching. Secondly, by using the adjustment of vacant taxi route as the control action, it formulated the reinforcement learning model of taxi dispatching. At last, it proposed the corresponding Q learning algorithm to solve the new model. Numerical example demonstrates the effectiveness of the new dispatching method. The results show that the new method can not only increase the match rate between taxis and passengers and the total income of operation of taxi service, but also reduce the average waiting time of passengers and the total travel time of vacant taxis.
英文关键词 urban transportation; taxi dispatching; reinforcement learning; grid management; adaptive control
参考文献 查看稿件参考文献
  [1] 祝进城, 帅斌, 孙朝苑, 等. 固定费率下城市出租车拥挤收费模型与算法[J] . 计算机应用研究, 2013, 30(8):2288-2291, 2322. (Zhu Jincheng, Shuai Bin, Sun Chaoyuan, et al. Modeling and algorithm of taxicabs’ payment for congestion charges in road pricing zone under toll given[J] . Application Research of Computers, 2013, 30(8):2288-2291, 2322. )
[2] Zhan Xianyuan, Qian Xinwu, Ukkusuri S V. A graph-based approach to measuring the efficiency of an urban taxi service system[J] . IEEE Trans on Intelligent Transportation Systems, 2016, 17(9):2479-2489.
[3] 胡继华, 黄泽, 邓俊. 考虑出行方向的广州出租车时空可达性研究[J] . 计算机应用研究, 2014, 31(2):454-456, 460. (Hu Jihua, Huang Ze, Deng Jun. Research on space-time accessibility conside-ring direction of travel[J] . Application Research of Computers, 2014, 31(2):454-456, 460. )
[4] Jung J, Chow J Y, Jayakrishnan R, et al. Stochastic dynamic itine-rary interception refueling location problem with queue delay for electric taxi charging stations[J] . Transportation Research Part C, 2014, 40(1):123-142.
[5] Sayarshad H R, Chow J Y. Survey and empirical evaluation of non-homogeneous arrival process models with taxi data[J] . Journal of Advanced Transportation, 2016, 50(7):1275-1294.
[6] Zhang Wenbo, Ukkusuri S V. Optimal fleet size and fare setting in emerging taxi markets with stochastic demand[J] . Computer-Aided Civil and Infrastructure Engineering, 2016, 31(9):647-660.
[7] He Fang, Shen Z M. Modeling taxi services with smart phone-based e-hailing applications[J] . Transportation Research Part C, 2015, 58(1):93-106.
[8] Wang Xiaolei, He Fang, Yang Hai, et al. Pricing strategies for a taxi hailing platform[J] . Transportation Research Part E, 2016, 93(2):212-231.
[9] Wong R, Szeto W, Wong S. A cell-based logit-opportunity taxi customer-search model[J] . Transportation Research Part C, 2014, 48(1):84-96.
[10] Amirgholy M, Gonzales E J. Demand responsive transit systems with time-dependent demand:user equilibrium, system optimum, and management strategy[J] . Transportation Research Part B, 2016, 92(2):234-252.
[11] Yang Teng, Yang Hai, Wong S C. Taxi services with search frictions and congestion externalities[J] . Journal of Advanced Transportation, 2014, 48(6):575-587.
[12] Zha Liteng, Yin Yafeng, Yang Hai. Economic analysis of ride-sourcing markets[J] . Transportation Research Part C, 2016, 71(2):249-266.
[13] Nie Yu. How can the taxi industry survive the tide of ride sourcing?Evidence from Shenzhen, China[J] . Transportation Research Part C, 2017, 79(2):242-256.
[14] Pillac V, Gendreau M, Gueret C, et al. A review of dynamic vehicle routing problems[J] . European Journal of Operations Research, 2013, 225(1):1-11.
[15] Hosni H, Naoum-Sawaya J, Artail H. The shared-taxi problem:formulation and solution methods[J] . Transportation Research Part B, 2014, 70(3):303-318.
[16] Jung J, Jayakrishnan R, Park J Y. Dynamic shared-taxi dispatch algorithm with hybrid-simulated annealing[J] . Computer-Aided Civil and Infrastructure Engineering, 2016, 31(4):275-291.
[17] Agatz N, Erera A, Savelsbergh M, et al. Optimization for dynamic ride-sharing:a review[J] . European Journal of Operations Research, 2012, 223(2):295-303.
[18] Nourinejad M, Roorda M J. Agent based model for dynamic ride sharing[J] . Transportation Research Part C, 2016, 64(1):117-132.
[19] Warren B P. Approximate dynamic programming-solving the curses of dimensionality[M] . Hoboken:Wiley, 2011.
[20] Dimitri P B, John N T, John T. Neuro-dynamic programming[M] . Nashua:Athena Scientific, 1996.
收稿日期 2017/11/7
修回日期 2017/12/26
页码 762-766
中图分类号 U491
文献标志码 A