Ayari M., Nasri S., Bouziri H., Aggoune-Mtalaa W.
Communications in Computer and Information Science, vol. 2854 CCIS, pp. 176-189, 2026
The Dial-A-Ride Problem (DARP) is a core challenge in intelligent transportation systems, involving the routing of vehicles to serve passengers with specific pickup, drop-off, and time constraints. While insertion heuristics combined with Case-Based Reasoning (CBR), as seen in the Insertion-Based Reasoning DARP (IBR-DARP) method, provide efficient initial solutions, they often struggle to escape local optima. This paper introduces a novel Tabu Search-based Dial-A-Ride Problem (TS-DARP) approach that enhances IBR-DARP by integrating a metaheuristic optimization phase. The key innovation lies in the revise step, where a tabu search algorithm, equipped with relocation and swap move operators, iteratively improves the solution. This mechanism allows TS-DARP to explore a broader solution space and avoid cycling, effectively escaping local optima that limit purely heuristic methods. The algorithm was rigorously evaluated against IBR-DARP on a set of standard benchmark instances. Results demonstrate that TS-DARP significantly outperforms the baseline in 9 out of 11 cases, achieving reductions in Total Travel Cost (TTC) of up to 17.08%. The consistent improvements across problems of varying size and complexity confirm the robustness and scalability of the approach. By successfully marrying the rapid solution-building of CBR with the powerful global search capabilities of tabu search, TS-DARP provides a more adaptive and effective optimization strategy for complex on-demand transportation planning.
