As of October 1, 2016, the SWUTC concluded its 28 years of operation and is no longer an active center of the Texas A&M Transportation Institute. The archived SWUTC website remains available here.

600451-00034-1 Dissertation Abstract

Optimization and Mechanism Design for Ridesharing Services

Wei Lu, December, 2014

This research studies operations research problems of ridesharing services. In the first part of the research, the large-scale ridesharing optimization problem (RSP) is formally defined with its complexity analyzed. A mixed-integer program is then developed to solve RSP to optimality. Since RSP is NP-hard, heuristic algorithms are developed to efficiently solve larger instances of RSP. The quality of heuristic solutions is evaluated by comparing with benchmark algorithms. Experimental results showed that the solutions produced by heuristic are good-enough approximation of the optimum and outperformed the matching solution by a non-trivial margin. The second part of this dissertation studies the fairness and stability problems in ridesharing. The fair cost allocation problem in ridesharing is formulated as a cooperative game. An algorithm based on coalition generation techniques is developed to efficiently find the nucleolus of this game. Experiments showed that this algorithm could save significant amount of computational resources compared to the enumeration method. The output of this research provides both insights and tools for understanding and operating large-scale ridesharing services.

Keywords: Ridesharing, Optimization, Heuristic, Mixed-integer Programming, Game Theory, Mechanism Design, Nucleolus

ENTIRE REPORT (Adobe Acrobat File – 916 KB)