Analysis on Model and Algorithm of Static Dial-A-Ride Problems Using Lower Bound

摘要

This paper studies a static dial-a-ride problem with time varying travel times, soft time windows, and multiple depots. Kim and Haghani (2011) formulated a static DARP model as a mixed integer programming and in order to validate the model, several random small network problems are solved using 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. It is necessary to find a lower bound of objective function for optimization problems to minimize objective functions. In this paper, a lower bound was found for the developed model by Kim and Haghani (2011). Also, the results of three heuristic methods are compared with the results obtained from exact solution by CPLEX and lower bound to validate and evaluate three heuristic algorithms. Computational results show that three heuristic algorithms are superior compared to the exact algorithm and lower bound solution in terms of the calculation time as the problem size (in terms of the number of demands) increases. Also among the three heuristic algorithms, the heuristic algorithm based on parallel insertion is more efficient than other heuristic algorithms that are based on sequential insertion and clustering first-routing second.