Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms

The time dependent vehicle routing problem (TDVRP) is defined as follows. A vehicle fleet of fixed capacities serves customers of fixed demands from a central depot. Customers are assigned to vehicles and the vehicles routed so that the total time of the routes is minimized. The travel time between two customers or between a customer and the depot depends on the distance between the points and time of day. Time windows for serving the customers may also be present. The time dependent traveling salesman problem (TDTSP) is a special case of the TDVRP in which only one vehicle of infinite capacity is available. Mixed integer linear programming formulations of the TDVRP and the TDTSP are presented that treat the travel time functions as step functions. The characteristics and properties of the TDVRP preclude modification of most of the algorithms that have been developed for the vehicle routing problem. Several simple heuristic algorithms are given for the TDTSP and TDVRP without time windows based on the nearest-neighbor heuristic. A mathematical-programming-based heuristic for the TDTSP without time windows using cutting planes is also briefly discussed. Test results on small, randomly generated problems are reported.