Time dependent vehicle routing problems: Formulations, properties and heuristic algorithms. (English) Zbl 0758.90029

Malandraki, Chryssi; Daskin, Mark S.

Transp. Sci. 26, No. 3, 185-200 (1992).

Summary: 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 algorithm 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.

MSC:

90B06	Transportation, logistics and supply chain management
90C11	Mixed integer programming
90-08	Computational methods for problems pertaining to operations research and mathematical programming
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C05	Linear programming

Keywords:

mixed integer linear programming; time dependent vehicle routing; heuristic algorithms; cutting planes