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 the 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 Firstmile 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 result 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 instances, 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 short timeframe in all scenarios. Furthermore, our case study demonstrates the effectiveness of rebalancing in increasing service rates.