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.