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...
| 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 |
| _version_ | 1824455176462794752 |
|---|---|
| author | Wang, Hao |
| author2 | Bei Xiaohui |
| author_facet | Bei Xiaohui Wang, Hao |
| author_sort | Wang, Hao |
| collection | NTU |
| description | 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. |
| first_indexed | 2025-02-19T03:34:03Z |
| format | Thesis-Doctor of Philosophy |
| id | ntu-10356/155387 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:34:03Z |
| publishDate | 2022 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1553872023-02-28T23:59:15Z Online matching with its applications to ridesharing Wang, Hao Bei Xiaohui School of Physical and Mathematical Sciences xhbei@ntu.edu.sg Engineering::Computer science and engineering::Theory of computation 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. Doctor of Philosophy 2022-02-21T00:33:05Z 2022-02-21T00:33:05Z 2022 Thesis-Doctor of Philosophy Wang, H. (2022). Online matching with its applications to ridesharing. Doctoral thesis, Nanyang Technological University, Singapore. https://hdl.handle.net/10356/155387 https://hdl.handle.net/10356/155387 10.32657/10356/155387 en This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License (CC BY-NC 4.0). application/pdf Nanyang Technological University |
| spellingShingle | Engineering::Computer science and engineering::Theory of computation Wang, Hao Online matching with its applications to ridesharing |
| title | Online matching with its applications to ridesharing |
| title_full | Online matching with its applications to ridesharing |
| title_fullStr | Online matching with its applications to ridesharing |
| title_full_unstemmed | Online matching with its applications to ridesharing |
| title_short | Online matching with its applications to ridesharing |
| title_sort | online matching with its applications to ridesharing |
| topic | Engineering::Computer science and engineering::Theory of computation |
| url | https://hdl.handle.net/10356/155387 |
| work_keys_str_mv | AT wanghao onlinematchingwithitsapplicationstoridesharing |