Skip to main content

An Algorithmic Study on Ridesharing Problem

Resource type
Thesis type
(Thesis) M.Sc.
Date created
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.
Copyright statement
Copyright is held by the author.
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Scholarly level
Supervisor or Senior Supervisor
Thesis advisor: Gu, Qianping
Member of collection
Download file Size
etd9687_LLiang.pdf 2.18 MB

Views & downloads - as of June 2023

Views: 9
Downloads: 0