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)