EFFICIENT ROUTE PLANNING IN SHARED MOBILITY WITH THEORETICAL GUARANTEES

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "EFFICIENT ROUTE PLANNING IN SHARED MOBILITY WITH THEORETICAL 
GUARANTEES"

By

Mr. Yuxiang ZENG


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:			Thursday, 10 March 2022

Time:			2:00pm - 4:00pm

Zoom Meeting:		https://hkust.zoom.us/j/7984542692

Chairperson:		Prof. Xueqing ZHANG (CIVL)

Committee Members:	Prof. Lei CHEN (Supervisor)
 			Prof. Qiong LUO
 			Prof. Xiaofang ZHOU
 			Prof. Can YANG (MATH)
 			Prof. Jianliang XU (HKBU)


**** ALL are Welcome ****