Efficient route planning in shared mobility with theoretical guarantees

Abstract

Shared mobility refers to transportation services that are shared among users. In recent years, applications of shared mobility have become more and more prevalent in daily lives. A few examples of these applications include ride-sharing, food delivery, and urban logistics. One of the most fundamental challenges is the Route Planning in Shared Mobility (RPSM) problem. Formally speaking, given a set of workers and requests, the RPSM problem aims to find a suitable route (i.e., a sequence of request’s origin and destination) for each worker to optimize some platform-defined objective. This thesis studies two mainstream RPSM problems, namely monetary-aware RPSM and temporal-aware RPSM. In the first problem, we aim to maximize the number of served requests or the total revenue of the platform, which are commonly-seen objectives in ridesharing platforms like Uber and Didi Chuxing. To address monetary-aware RPSM, our idea is to iteratively search the most profitable route among the unassigned requests for each worker, which is much simpler than the existing methods. Unexpectedly, we prove this simple idea has an approximation ratio better than 0.5, which is nearly optimal. In the second problem, we aim to minimize the makespan (i.e., maximum travel time) of workers and total latency (i.e., total waiting time) of requests, which are popular objectives in food delivery and urban logistics. To solve temporal-aware RPSM, we propose a algorithmic framework that simultaneously approximates both objectives. Leveraging the data structure of geometric embeddings, hierarchically separated tree (HST), we show this framework achieves an approximation ratios of O(log n) for either objective, where n is the number of requests. To further improve the efficiency, we study the construction and update algorithms of HSTs and propose faster and better solutions to this spatial index, which can benefit many other applications like clustering and facility location planning. Finally, extensive experiments on real datasets and synthetic datasets demonstrate that our proposed solutions outperform the state-of-the-art algorithms by a large margin.

Date of Award	2022
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology
Supervisor	Lei CHEN (Supervisor)