Adaptive Large Neighborhood Search for Order Dispatching and Vacant Vehicle Rebalancing in First-Mile Ride-Sharing Services

This article addresses the first-mile ride-sharing problem, which entails efficiently transporting passengers from a set of origins to a shared destination. Typical destinations are stations, central business districts, or hospitals. Successful optimization of this problem has the potential to alleviate congestion, reduce pollution, and enhance the overall efficiency of transportation systems. However, the inherent complexity of simultaneous order dispatching and vacant vehicle rebalancing often leads to time-consuming computations. In this study, we present an extension of the Adaptive Large Neighborhood Search (ALNS) meta-heuristic, specifically designed to tackle this problem. Through computational experiments on a diverse set of instances, we demonstrate that the proposed ALNS approach delivers high quality solutions within a short timeframe, outperforming off-the-shelf MILP solvers. Furthermore, we conduct a comprehensive case study using simulation, where we show that significant service rate improvements can be achieved by means of rebalancing activities