An Algorithmic Study on Ridesharing Problem

The ridesharing problem is to share personal vehicles by individuals (participants) with similar itineraries. A trip in the ridesharing problem is a participant and his/her itinerary. To realize a trip is to deliver the participant to his/her destination by a vehicle satisfying the itinerary requirement. In this thesis, we focus on two optimization goals: minimize the number of vehicles and minimize the total travel distance of vehicles to realize all trips. The minimization problems are complex and NP-hard because of many parameters. We simplify the problems by considering only some of the parameters. We prove that some simplified minimization problems are NP-hard while a further simplified variant is polynomial time solvable. These suggest a boundary between the NP-hard and polynomial time solvable cases. We also propose a novel approach for finding a maximum matching in hypergraphs with special properties, extending the well-known maximum matching theorem in graphs to hypergraphs.