Order dispatching optimization in ride-sourcing market by considering cross service modes

Abstract

To meet personalized travel demand, ride-sourcing platforms provide differentiated service modes for travelers. These service modes are usually operated independently, and because of the heterogeneity of travel demand, the fragmented ride-sourcing services struggle with imbalances between supply and demand within each sub-market. For that, cross-mode dispatching can be adopted to reduce the vehicle idle time and improve passengers’ experience. However, it may undermine the efficiency of the premium mode, such as increased matching failures. To consider the long-term impact of cross-mode dispatching, the dispatching problem of multi-service modes is modeled by the Markov decision process. A multi-service mode dispatching framework is proposed, comprised of a simulator and a two-stage reinforcement learning algorithm. The simulator provides environment support while avoiding matching failures of premium mode caused by cross-mode dispatching. The two-stage reinforcement learning algorithm refines requests based on the k-nearest neighbor algorithm to solve the problem of the dynamic change of the candidate request set. Experiments show that the framework fulfills 3.1% additional basic requests without the decreasing of fulfilled premium requests, by cross-mode dispatching, demonstrating the feasibility of the cross-mode dispatching and the performance of the framework. Sensitivity analyses are designed to test the robustness of the framework under different scenarios.

Keywords

ride-sourcing / multi-service modes / cross-mode dispatching / reinforcement learning / emerging transportation systems

References

[1] WangH, YangH. Ridesourcing systems: A framework and review [J]. Transportation Research Part B: Methodological, 2019, 129: 122-155

[2] GuoD, LiC, YanW, et al. . Optimal path planning method of electric vehicles considering power supply [J]. Journal of Central South University, 2022, 29(1): 331-345

[3] TaoY, HuangM, ChenY, et al. . Review of optimized layout of electric vehicle charging infrastructures [J]. Journal of Central South University, 2021, 28(10): 3268-3278

[4] LiY, SunH, LvY. Collaborative matching of ridesplitting and connection in the ridesourcing market [J]. Fundamental Research, 2021, 1(5): 517-533

[5] ZhangJ, SongG, YuL, et al. . Identification and characteristics analysis of bottlenecks on urban expressways based on floating car data [J]. Journal of Central South University, 2018, 25(8): 2014-2024

[6] WangJ, HuangH. Operations on an on-demand ride service system with express and limousine [J]. Transportation Research Part B: Methodological, 2022, 155: 348-373

[7] ZHOU Ya-qian, KE Jin-tao, YANG Hai. Price of competition and market fragmentation in ride-sourcing markets [EB/OL]. [2021-08-31]. https://ssrn.com/abstract=3913104. DOI: https://doi.org/10.2139/ssrn.3913104.

[8] OhS, SeshadriR, AzevedoC L, et al. . Assessing the impacts of automated mobility-on-demand through agent-based simulation: A study of Singapore [J]. Transportation Research Part A: Policy and Practice, 2020, 138: 367-388

[9] MaoC, LiuY, ShenZ. Dispatch of autonomous vehicles for taxi services: A deep reinforcement learning approach [J]. Transportation Research Part C: Emerging Technologies, 2020, 115: 102626

[10] Al-KanjL, NascimentoJ, PowellW B. Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles [J]. European Journal of Operational Research, 2020, 284(3): 1088-1106

[11] LiM, QinZ, JiaoY, et al. Efficient ridesharing order dispatching with mean field multi-agent reinforcement learning [C], 2019, New York, NY, USA, ACM

[12] XuZ, LiZ, GuanQ, et al. Large-scale order dispatch in on-demand ride-hailing platforms [C], 2018, New Yook, NY, USA, ACM: 905-913

[13] GaoG, XiaoM, ZhaoZOptimal multi-taxi dispatch for mobile taxi-hailing systems [C], 2016, Philadelphia, PA, USA, IEEE: 294303

[14] ZhangL, HuT, MinY, et al. A taxi order dispatch model based on combinatorial optimization [C], 2017, New York, NY, USA, ACM

[15] TangX, QinZ T, ZhangF, et al. A deep value-network based approach for multi-driver order dispatching [C], 2019, New York, NY, USA, ACM

[16] AlisoltaniN, ZargayounaM, LeclercqL. A sequential clustering method for the taxi-dispatching problem considering traffic dynamics [J]. IEEE Intelligent Transportation Systems Magazine, 2020, 12(4): 169-181

[17] XuZ, LiZ, GuanQ, et al. Large-scale order dispatch in on-demand ride-hailing platforms [C], 2018, NY, USA, ACM: 905913

[18] GodfreyG A, PowellW B. An adaptive dynamic programming algorithm for dynamic fleet management, I: Single period travel times [J]. Transportation Science, 2002, 36(1): 21-39

[19] Al-KanjL, NascimentoJ, PowellW B. Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles [J]. European Journal of Operational Research, 2020, 284(3): 1088-1106

[20] JinJ, ZhouM, ZhangW, et al. CoRide: Joint order dispatching and fleet management for multi-scale ride-hailing platforms [C], 2019, New York, NY, USA, ACM: 19831992

[21] TangX, ZhangF, QinZ, et al. Value function is all You need: A unified learning framework for ride hailing platforms [C], 2021, New York, NY, USA, ACM

[22] DULAC-ARNOLD G, EVANS R, HASSELT H V, et al. Deep reinforcement learning in large discrete action spaces [EB/OL]. [2022-02-02]. https://arxiv.org/abs/1512.07679.

[23] XuD, WangY, JiaL, et al. . Realtime Road traffic states estimation based on kernel-KNN matching of road traffic spatial characteristics [J]. Journal of Central South University, 2016, 23(9): 2453-2464

[24] BhatnagarS, SuttonR S, GhavamzadehM, et al. . Natural actor-critic algorithms [J]. Automatica, 2009, 45(11): 2471-2482

[25] HaoH, LiuZ, ZhaoF, et al. . Natural gas as vehicle fuel in China: A review [J]. Renewable and Sustainable Energy Reviews, 2016, 62: 521-533