Trip-vehicle matching and vehicle routing optimization for ride-sharing
Date
2022-08
Authors
Tian, Ye
Major Professor
Advisor
Liu, Jia
Rajan, Hridesh
Aduri, Pavankumar
Li, Qi
Zhang, Wensheng
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Abstract
In recent years, ride-sharing systems have emerged as one of the quintessential examples of sharing economy that can effectively leverage excessive and under-utilized vehicle resources to address many challenges in modern transportation systems (e.g., CO$_2$ emissions, growing fuel prices) and achieve ``triple-win'' between the riders, enlisted drivers, and the ride-sharing platform.
Lying at the heart of most ride-sharing systems is the problem of joint trip-vehicle matching and routing optimization, which is highly challenging and results in this area remain rather limited. In this thesis, we studied both planning setting and real-time setting for ride-sharing problems.
In the planning setting, available drivers and rider demands are given beforehand. We proposed an analytical framework to state the problem and reformulate it as a mixed-integer linear program, which can be solved by global optimization methods.
To efficiently solve large-sized problem instances, we developed a memory-augmented time-expansion (MATE) approach which leverages the special problem structure to facilitate approximate (or even exact) algorithm designs.
In the real-time setting, rider demands are not available in advance. We proposed a reinforcement learning formulation for ride-sharing that jointly optimizes the rewards and experiences from the perspectives of the drivers and riders, respectively.
Then we developed a reactive model-free deep RL approach based on proximal policy optimization (PPO) to solve the joint trip-vehicle matching and routing optimization problem.
Finally, we conduct extensive simulations to analyze and verify the performance of our ride-sharing system using real-world datasets.
Simulations results show that the proposed framework outperforms a greedy and the receding horizon control (RHC) algorithms under all testing demand patterns.
Series Number
Journal Issue
Is Version Of
Versions
Series
Academic or Administrative Unit
Type
dissertation