Real-Time Optimization for Dynamic Ride-Sharing

Throughout the last decade, the advent of novel mobility services such as ride-hailing,
car-sharing, and ride-sharing has shaped urban mobility. While these types of services
offer flexible on-demand transportation for customers, they may also increase the load
on the, already strained, road infrastructure and exacerbate traffic congestion problems.
One potential way to remedy this problem is the increased usage of dynamic ride-sharing
services. In this type of service, multiple customer trips are combined into share a vehicle simultaneously.
This leads to more efficient vehicle utilization, reduced prices for customers,
and less traffic congestion at the cost of slight delays compared to direct transportation in
ride-hailing services.

In this thesis, we consider the planning and operation of such dynamic ride-sharing
services. We present a wider look at the planning context of dynamic ride-sharing and
discuss planning problems on the strategical, tactical, and operational level. Subsequently,
our focus is on two operational planning problems: dynamic vehicle routing, and idle
vehicle repositioning.

Regarding vehicle routing, we introduce the vehicle routing problem for dynamic ridesharing
... mehr
and present a solution procedure. Our algorithmic approach consists of two
phases: a fast insertion heuristic, and a local search improvement phase. The former
handles incoming trip requests and quickly assigns them to suitable vehicles while the
latter is responsible for continuously improving the current routing plan. This way, we
enable fast response times for customers while simultaneously effectively utilizing available
computational resources.

Concerning the idle vehicle repositioning problem, we propose a mathematical model that
takes repositioning decisions and adequately reflects available vehicle resources as well as
a forecast of the upcoming trip request demand. This model is embedded into a real-time
planning algorithm that regularly re-optimizes the movement of idle vehicles. Through an
adaptive parameter calculation process, our algorithm dynamically adapts to changes in
the current system state.

To evaluate our algorithms, we present a modular simulation-based evaluation framework.
We envision that this framework may also be used by other researchers and developers.
In this thesis, we perform computational evaluations on a variety of scenarios based on
real-world data from Chengdu, New York City, and Hamburg. The computational results
show that we are able to produce high-quality solutions in real-time, enabling the usage in
high-demand settings. In addition, our algorithms perform robustly in a variety of settings
and are quickly adapted to new application settings, such as the deployment in a new city.