MODEL AND ALGORITHM FOR SOLVING STATIC MULTI DEPOT DIAL-A-RIDE PROBLEM CONSIDERING TIME VARYING TRAVEL TIMES

摘要

This paper studies a static dial-a-ride problem with time varying travel times, soft timewindows, multiple depots. In this paper, a static DARP model is formulated as a mixed integerprograming and in order to validate the model, several random small network problems are solvedusing commercial optimization package, CPLEX. Three heuristic algorithms based on sequentialinsertion, parallel insertion, and clustering first-routing second are proposed to solve this problemwithin a reasonable time for implementation in a real-world situation. Also, the results of threeheuristic methods are compared with the results obtained from exact solution by CPLEX to validateand evaluate three heuristic algorithms.Computational results show that three heuritic algorithms are superior compared to the exactalgorithm 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 seqeuntialinsertion is more efficient than other heuristic algorithms that are based on parallel insertion andclustering first-routing second (166 words).