Most of the models for vehicle routing problems reported in the literature assumed constant travel times. Also numerous heuristics have been developed for problems with time window restriction only, but few for those with time-varying traffic congestion.
The travel time between two locations is not only affected by the distance traveled, but by many other factors including the time of the day. Therefore, the application of these models to real-world problems is gradually being increased .
In this paper, we consider a vehicle routing problem with time-dependent travel time and present a model based on time-dependent travel speeds which satisfies the "Non-passing" property. To solve the problem, a tabu search algorithm is proposed. This algorithm is composed of the route construction procedure and the route improvement procedure to improve the solution obtained by the route construction procedure.
The algorithm was tested on problems composed of 10, 15, 30, 50 nodes and one depot. In case of problems with 10, 15 nodes, the solutions obtained by the tabu search heuristic were compared with the optimal solutions. On average, objective values of problems with 10 nodes were within 0.123% and those of problems with 15 nodes were within 0.165%, compared to the optimal objective values. Therefore, computational results show that the proposed tabu search algorithm can find near optimal solutions.
