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

Jinwen Ye*, Giovanni Pantuso, David Pisinger

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

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.
Original languageEnglish
JournalJournal
Publication statusAccepted/In press - 2024

Keywords

  • Adaptive Large Neighborhood Search
  • Ride-sharing
  • First-mile
  • Rebalancing
  • Metaheuristic

Fingerprint

Dive into the research topics of 'Adaptive Large Neighborhood Search for Order Dispatching and Vacant Vehicle Rebalancing in First-Mile Ride-Sharing Services'. Together they form a unique fingerprint.

Cite this