PhD Defense Jinwen Ye

Title: Optimization in First-mile Ride-sharing Problems


This thesis presents mathematical models and methods for supporting the decision-making process in first-mile ride-sharing services and is structured into four chapters. The first chapter is an introduction to the background of First-mile Ride-sharing Problems and the optimization methodologies. It is followed by three self-contained chapters.

The second chapter Fleet Size Control in First-mile Ride-sharing Problem considers fleet size optimization in first-mile ride-sharing problem. The problem is formulated as a MIP model and numerical experiments are presented on a small-scale system. Results show that, by employing and controlling the drivers, the operator can achieve higher profits and service rates compared to hiring independent drivers.

The third chapter Order Dispatching and Vacant Vehicles Rebalancing for the First- mile Ride-sharing Problem formulates a mathematical programming model to optimize the vehicle rebalancing and order matching process simultaneously. Particularly, we propose and compare two methods to identify rebalancing centers based on historical data. Numerical experiments are
conducted in a rolling horizon framework on small-scale instances, and the results demonstrate the consistent effectiveness of rebalancing. The fourth chapter Adaptive Large Neighborhood Search for Order Dispatching and Vacant Vehicle Rebalancing in First-Mile Ride-Sharing Services further discusses the rebalancing in first-mile ride-sharing problems for large-scale cases. To solve large-scale in- stances, we specifically design and implement an extension of the Adaptive Large Neighborhood Search (ALNS) meta-heuristic. Tailor-made destroy and repair operators are designed and tested through computational experiments.

Results on a diverse set of instances show that our proposed ALNS outperform commercial solvers for small-scale instances as well as large-scale instances, as ALNS delivers high-quality solutions in a short timeframe in all scenarios. Furthermore, our
case study demonstrates the effectiveness of rebalancing in increasing service rates.

Thesis for download

Advisor: Giovanni Pantuso,  University of Copenhagen

Assessment Committee: 
Trine K. Boomsma, chair, University of Copenhagen
Art Paolo Toth, University of Bologna
Jose Fernando Oliveira, University of Porto