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

Chryssi Malandraki and Mark S. Daskin
Additional contact information
Chryssi Malandraki: Roadnet Technologies, Inc., Timonium, Maryland 21093
Mark S. Daskin: Northwestern University, Evanston, Illinois 60208

Transportation Science, 1992, vol. 26, issue 3, 185-200

Abstract: 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.

Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (80)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.26.3.185 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:26:y:1992:i:3:p:185-200

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().