Time dependent vehicle routing problem with a multi ant colony system

The Time Dependent Vehicle Routing Problem (TDVRP) consists in optimally routing a fleet of vehicles of fixed capacity when travel times are time dependent, in the sense that the time employed to traverse each given arc, depends on the r time of the day the travel starts from its originating node. The optimization method consists in finding solutions that minimize two hierarchical objectives: the number of tours and the total travel time. Optimization of total travel time is a continuous optimization problem that in our approach is solved by discretizing the time space in a suitable number of subspaces. New time dependent local search procedures are also introduced, as well as conditions that guarantee that feasible moves are sought for in constant time. This variant of the classic Vehicle Routing Problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. In this paper it is shown that when dealing with time constraints like hard delivery time windows for customers, the known solutions for the classic case become unfeasible and the degree of unfeasibility increases with the variability of traffic conditions, while if no hard time constraints are present, the classic solutions become suboptimal. Finally an application of the model to a real case is presented. The model is integrated with a robust shortest path algorithm to compute time dependent paths between each customer pairs of the time dependent model. (C) 2006 Elsevier B.V. All rights reserved.