TY - UNPB

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

AU - Ye, Jinwen

AU - Pantuso, Giovanni

AU - Pisinger, David

PY - 2023

Y1 - 2023

N2 - This article addresses the first-mile ride-sharing problem, which entails efficiently transportingpassengers from a set of origins to a shared destination. Typical destinations are stations, centralbusiness 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 theAdaptive Large Neighborhood Search (ALNS) meta-heuristic, specifically designed to tackle thisproblem. Through computational experiments on a diverse set of instances, we demonstrate thatthe proposed ALNS approach delivers high quality solutions within a short timeframe, outperforming off-the-shelf MILP solvers. Furthermore, we conduct a comprehensive case study usingsimulation, where we show that significant service rate improvements can be achieved by meansof rebalancing activities.

AB - This article addresses the first-mile ride-sharing problem, which entails efficiently transportingpassengers from a set of origins to a shared destination. Typical destinations are stations, centralbusiness 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 theAdaptive Large Neighborhood Search (ALNS) meta-heuristic, specifically designed to tackle thisproblem. Through computational experiments on a diverse set of instances, we demonstrate thatthe proposed ALNS approach delivers high quality solutions within a short timeframe, outperforming off-the-shelf MILP solvers. Furthermore, we conduct a comprehensive case study usingsimulation, where we show that significant service rate improvements can be achieved by meansof rebalancing activities.

M3 - Preprint

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

PB - Social Science Research Network (SSRN)

ER -