EFFICIENT ROUTE PLANNING IN SHARED MOBILITY WITH THEORETICAL GUARANTEES

PhD Thesis Proposal 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 proposal 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 ride-sharing. To address 
monetary-aware RPSM, our idea is to iteratively search the most profitable 
route among the unassigned requests for each vehicle, which is much 
simpler than the existing methods. Unexpectedly, we prove this simple 
method has an approximation ratio of 0.5 to the optimal result. Moreover, 
we also design an index called additive tree to improve the efficiency and 
apply randomization to improve the approximation guarantee. 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 theoretically guaranteed solution 
framework for both objectives. It achieves both approximation ratios of 6ρ,
where ρ is the approximation ratio of a core operation, called kTRPSM, 
which plans for one courier a route consisting of k requests. Leveraging a 
spatial index called hierarchically separated tree, we further design an 
efficient approximation algorithm for kTRPSM with ρ = O(log n), where n is 
the number of requests. Finally, extensive experiments on real datasets 
demonstrate that our proposed solutions outperform the state-of-the-arts 
by a large margin.


Date:			Thursday, 20 January 2022

Time:                  	9:00am - 11:00am

Venue: 			Room 3494
 			Lifts 25/26

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Qiong Luo (Chairperson)
 			Prof. Ke Yi
 			Prof. Xiaofang Zhou


**** ALL are Welcome ****