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...[ Read more ]

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.