Unified route planning for shared mobility: An insertion-based framework

• Main Authors: TONG, Yongxin, ZENG, Yuxiang, ZHOU, Zimu, CHEN, Lei, XU, Ke.
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2022
• Subjects: Route planning; Ride-sharing; Insertion; Dynamic programming; Databases and Information Systems; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/7218; https://ink.library.smu.edu.sg/context/sis_research/article/8221/viewcontent/tods21_tong.pdf
• Institution: Singapore Management University

There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery, and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is route planning. Given a set of workers and requests, route planning finds for each worker a route, i.e., a sequence of locations to pick up and drop off passengers/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called insertion. In addition, previous route planning solutions fail to exploit the appearance patterns of future requests hidden in historical data for optimization. In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We propose two insertion-based frameworks to solve the URPSM problem. The first is built upon the plain-insertion widely used in prior studies, which processes online requests only, whereas the second relies on a new insertion operator called prophet-insertion that handles both online and predicted requests. Novel dynamic programming algorithms are designed to accelerate both insertions to only linear time. Theoretical analysis shows that no online algorithm can have a constant competitive ratio for the URPSM problem under the competitive analysis model, yet our prophet-insertion-based framework can achieve a constant optimality ratio under the instance-optimality model. Extensive experimental results on real datasets show that our insertion-based solutions outperform the state-of-the-art algorithms in both effectiveness and efficiency by a large margin (e.g., up to 30× more effective in the objective and up to 20× faster).