The Dial-A-Ride Problem with Transfers and Walking

: This paper introduces the Dial-a-Ride Problem with Transfers and Walking (DARPTW), a generalization of the classical DARP in which passenger itineraries may include multiple transfers and walking segments. The objective is to minimize a bi-criteria function comprising total vehicle travel time and the total journey time of all users. Incorporating transfers and walking provides operational flexibility, enabling load balancing, reduced service areas, and walking shortcuts to avoid unnecessary vehicle detours, but also substantially increases problem complexity, as DARPTW generalizes the already NP-hard DARP. To address this challenge, we propose an Adaptive Large Neighborhood Search (ALNS) framework that integrates a feasibility check and a scheduling heuristic. The feasibility check is accurate and computationally efficient, while the scheduler is highly efficient, allowing the approach to support iterative or near real-time routing. Computational experiments based on real-world data from Bubble-Dan in Tel Aviv demonstrate that ALNS consistently produces high-quality feasible solutions across diverse instances and scales with problem size, whereas exact methods quickly become intractable. A focused analysis of transfer policies shows that transfers are most beneficial under constrained conditions, such as limited walking flexibility or vehicle capacity, where they improve feasibility and routing efficiency.