On solving a real-world dial-a-ride problem for disabled passenger transportation in Barcelona

This paper addresses a real-world dial-a-ride problem (DARP) arising in Barcelona’s Special Municipal Transportation Service (SMTS) for individuals with reduced mobility. This problem is characterized as a rich heterogeneous DARP, incorporating additional attributes such as different vehicle types and capacities, multiple depots, varying user requirements, including the need for an accompanying person, and introducing discounts in shared trips. We formulate this problem as a mixed-integer linear programming model and solve realistic instances with a matheuristic approach that combines iterated local search with a set partitioning procedure. The latter extends a state-of-the-art algorithm for the multi-depot heterogeneous DARP by introducing efficient problem-specific move evaluation approaches to enhance local search performance, especially when managing accompanying persons. Computational experiments show a significant cost reduction of approximately 33% compared to the current solution used by SMTS, projecting annual savings of nearly €1 million. This result highlights the effectiveness of our approach in enhancing service efficiency and reducing operational costs in transportation services for people with reduced mobility. Finally, a sensitivity analysis is conducted to assess how variations in critical factors, such as time windows, maximum ride duration, and shared trip discounts, affect the average ride time and the number of vehicles used.