Online matching with its applications to ridesharing

• Main Author: Wang, Hao
• Other Authors: Bei Xiaohui
• Format: Thesis-Doctor of Philosophy
• Language: English
• Published: Nanyang Technological University 2022
• Subjects: Engineering::Computer science and engineering::Theory of computation
• Online Access: https://hdl.handle.net/10356/155387
• Institution: Nanyang Technological University

This thesis studies an online matching problem with its applications to ridesharing. Matching is a well-known problem with a long history and significant impact on both theoretical computer science and practice. Ridesharing is a new service that connects passengers and drivers with available vehicles using mobile apps. Its online nature makes us focus on the problem of online matching. It brings new inspirations and challenges to the area of online matching and its generations because of different scenarios of ridesharing. In this thesis, we mainly focus on two specific ridesharing scenarios: ride hitch and ridesourcing, and develop two novel online matching models to characterize these problems. For ride hitch, we design an online matching with capacity constraints model and present multiple online algorithms based on linear programs. For ridesourcing, we propose a new online matching with delays model with a real-time allocation algorithm to balance the waiting time cost and the matching quality. We give performance guarantees of our algorithms by theoretical analysis and show their effectiveness by extensive numerical studies.