Online matching with its applications to ridesharing
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 vehi...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis-Doctor of Philosophy |
| Language: | English |
| Published: |
Nanyang Technological University
2022
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/155387 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|