Order Dispatch of Ridesharing on Road Network with Location Protection under Differential Privacy

MPhil Thesis Defence


Title: "Order Dispatch of Ridesharing on Road Network with Location Protection 
under Differential Privacy"

By

Miss Manli YU


Abstract

Recently, ridesharing attracts great interest due to its benefits of 
saving cost, increasing profit, easing the traffic congestion and reducing 
the environment pollution. Privacy such as location information also 
arouses people's wide concern due to the safety reasons in recent decades. 
In this thesis, we investigate the order dispatch problem in ridesharing 
on road networks with consideration of the location privacy of the 
passengers, targeted at maximizing the number of the served passengers, 
and satisfying the deadline constraint of the orders and the capacity 
constraint of the vehicles.

Differential privacy can provide strong privacy without the adversary's 
auxiliary information. In this thesis, we utilize the 
ε-geo-graph-indistinguishability on graph to protect the location 
privacy of the passengers for the first time, where ε is the 
privacy budget. We prove the hardness (NP-hard) for the order dispatch 
problem in ridesharing with privacy protection, then we propose three 
approximate approaches, including the greedy algorithm, the group 
algorithm and the random algorithm. Through extensive experiments, we 
demonstrate the effectiveness and efficiency of our proposed algorithms on 
both real and synthetic data sets. The experiment results show that there 
is a tradeoff between the utility and the privacy protection, that is, 
with a larger privacy budget ε, a larger number of the served 
passengers and lower average dispatch time are obtained.


Date:  			Tuesday, 23 November 2021

Time:			3:00pm - 5:00pm

Zoom meeting:
https://hkust.zoom.us/j/5744176162?pwd=V0hmMktVckM5L01GbWRJMmVNelprQT09

Committee Members:	Prof. Lei Chen (Supervisor)
 			Prof. Qiong Luo (Chairperson)
 			Dr. Yangqiu Song


**** ALL are Welcome ****