TWO TIME WINDOW DISCRETIZATION METHODS FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOW CONSTRAINTS
In this paper, the authors discuss the convergence of two time window discretization methods for the traveling salesman problem with time window constraints. These methods are general and can be applied to other vehicle routing and scheduling problems with time windows. The first method provides a feasible solution to the problem while the second provides a lower bound for the minimization problem. Analysis shows that as the discretization interval tends towards zero the lower bounding method converges to the optimal solution while the method used to develop feasible solutions does not. This result suggests that improving the feasible solution by using smaller partition, though useful in many cases, is not always so.
- Record URL:
-
Corporate Authors:
Institute of Transportation Studies
University of California, Irvine
Irvine, CA United States 92717 -
Authors:
- Wang, X
- Regan, A C
- Publication Date: 2002-7
Language
- English
Media Info
- Features: Figures; References;
- Pagination: 22 p.
Subject/Index Terms
- TRT Terms: Freight transportation; Routing; Scheduling; Time windows; Traveling salesman problem; Trucking
- Subject Areas: Freight Transportation; Highways; Motor Carriers; Society; I10: Economics and Administration;
Filing Info
- Accession Number: 00964140
- Record Type: Publication
- Report/Paper Numbers: UCI-ITS-LI-WP-02-7
- Files: TRIS
- Created Date: Oct 14 2003 12:00AM