Model and Algorithm considering Time-Varying Travel Times to Solve Static Multidepot Dial-a-Ride Problem

This paper studies a static dial-a-ride problem (DARP) with time-varying travel times, soft time windows, and multiple depots. A static DARP model is formulated as a mixed-integer programming problem. To validate the model, several random small network problems are solved by using the commercial optimization package CPLEX. Three heuristic algorithms based on sequential insertion, parallel insertion, and clustering first-routing second are proposed to solve this problem within a reasonable time for implementation in a real-world situation. The results of the three heuristic methods are compared with the results obtained from exact solution by CPLEX to validate and evaluate the three heuristic algorithms. Computational results show that the three heuristic algorithms are superior to the exact algorithm in relation to the calculation time as the problem size (in number of demands) increases. Of the three heuristic algorithms, the one based on sequential insertion is more efficient than the other heuristic algorithms based on parallel insertion and clustering first-routing second.