THESIS
2022
1 online resource (xiii, 162 pages) : illustrations (chiefly color)
Abstract
Shared mobility refers to transportation services that are shared among users. In recent
years, applications of shared mobility have become more and more prevalent in daily
lives. A few examples of these applications include ride-sharing, food delivery, and urban
logistics. One of the most fundamental challenges is the Route Planning in Shared
Mobility (RPSM) problem. Formally speaking, given a set of workers and requests, the
RPSM problem aims to find a suitable route (i.e., a sequence of request’s origin and destination) for each worker to optimize some platform-defined objective.
This thesis studies two mainstream RPSM problems, namely monetary-aware RPSM
and temporal-aware RPSM. In the first problem, we aim to maximize the number of served
requests or the total revenue of the platfo...[
Read more ]
Shared mobility refers to transportation services that are shared among users. In recent
years, applications of shared mobility have become more and more prevalent in daily
lives. A few examples of these applications include ride-sharing, food delivery, and urban
logistics. One of the most fundamental challenges is the Route Planning in Shared
Mobility (RPSM) problem. Formally speaking, given a set of workers and requests, the
RPSM problem aims to find a suitable route (i.e., a sequence of request’s origin and destination) for each worker to optimize some platform-defined objective.
This thesis studies two mainstream RPSM problems, namely monetary-aware RPSM
and temporal-aware RPSM. In the first problem, we aim to maximize the number of served
requests or the total revenue of the platform, which are commonly-seen objectives in ridesharing
platforms like Uber and Didi Chuxing. To address monetary-aware RPSM, our idea
is to iteratively search the most profitable route among the unassigned requests for each
worker, which is much simpler than the existing methods. Unexpectedly, we prove this
simple idea has an approximation ratio better than 0.5, which is nearly optimal. In the
second problem, we aim to minimize the makespan (i.e., maximum travel time) of workers and total latency (i.e., total waiting time) of requests, which are popular objectives
in food delivery and urban logistics. To solve temporal-aware RPSM, we propose a algorithmic
framework that simultaneously approximates both objectives. Leveraging the
data structure of geometric embeddings, hierarchically separated tree (HST), we show this
framework achieves an approximation ratios of O(log n) for either objective, where n is
the number of requests. To further improve the efficiency, we study the construction and
update algorithms of HSTs and propose faster and better solutions to this spatial index,
which can benefit many other applications like clustering and facility location planning.
Finally, extensive experiments on real datasets and synthetic datasets demonstrate that
our proposed solutions outperform the state-of-the-art algorithms by a large margin.
Post a Comment