The A Priori Dynamic Traveling Salesman Problem with Time Windows

Allan Larsen (), Oli B. G. Madsen () and Marius M. Solomon ()
Additional contact information
Allan Larsen: IMM, Informatics and Mathematical Modeling, Technical University of Denmark, Richard Petersens Plads, Building 321, DK 2800 Kongens Lyngby, Denmark
Oli B. G. Madsen: CTT, Center for Traffic and Transport, Technical University of Denmark, Bygningstorvet, Building 115, DK 2800 Kongens Lyngby, Denmark
Marius M. Solomon: Department of Management Sciences, College of Business Administration, Northeastern University, 314 Hayden Hall, 360 Huntington Avenue, Boston, Massachusetts 02115

Transportation Science, 2004, vol. 38, issue 4, 459-472

Abstract: In this paper we examine the traveling saleman problem with time windows for various degrees of dynamism. In contrast to the static problem, where the dispatcher can plan ahead, in the dynamic version, part or all of the necessary information becomes available only during the day of operation. We seek to minimize lateness and examine the impact of this criterion choice on the distance traveled. Our focus on lateness is motivated by the problem faced by overnight mail service providers. We propose a real-time solution method that requires the vehicle, when idle, to wait at the current customer location until it can service another customer without being early. In addition, we develop several enhanced versions of this method that may reposition the vehicle at a location different from that of the current customer based on a priori information on future requests. The results we obtained on both randomly generated data and on a real-world case study indicate that all policies proved capable of significantly reducing lateness. Our results also show that this can be accomplished with only small distance increases. The basic policy outperformed the other methods primarily when lateness and distance were equally minimized and proved very robust in all environments studied. When only lateness was considered, the policy to reposition the vehicle at a location near the current customer generally provided the largest reductions in average lateness and the number of late customers. It also produced the least extra distance to be traveled among the relocation policies.

Keywords: dynamic vehicle routing; time windows; heuristics; computational analysis (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0070 (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:38:y:2004:i:4:p:459-472

Access Statistics for this article

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