Algorithms and heuristics for time-window-constrained traveling salesman problems
Chun, Bock Jin
Lee, Sang Heon
Rosenthal, Richard E.
Washburn, Alan R.
MetadataShow full item record
This thesis reports on methods for solving traveling salesman problems with time-window constraints- Two types of time windows are considered: hard time windows, which are inviolable, and soft time windows, which are violable at a cost. For both cases, we develop several heuristic procedures, including some that are based on Stewards [Ref-6] effective heuristics for the traveling salesman problem without time-window constraints. In addition, we develop exact algorithms for each case, which are based on the state-space relaxation dynamic programming metnod of Christo fides, Mingozzi, and Toth [Ref.5]. Computational experience is reported for all the heuristics and algorithms we develop.
Approved for public release; distribution in unlimited.
Showing items related by title, author, creator and subject.
Martins, Gustavo H. A. (2003-06);This dissertation investigates Multidimensional Packing Problems (MD-PPs): the Pallet Loading Problem (PLP), the Multidimensional Knapsack Problem (MD-KP), and the Multidimensional Bin Packing Problem (MD-BPP). In these ...
Tirumalai, Parthasarathy; Butler, Jon T. (1988-05);We compare the performance of three heuristic algorithms [3,6,13] for the minimization of sum-of-products expressions realized by the newly developed multiplevalued programmable logic arrays . Heuristic methods are ...
Negelspach, Greg L. (Monterey, California. Naval Postgraduate School, 1994-09);Optimal scheduling of parallel programs onto multiprocessor computers is an exponentially hard problem. Because of this, most scheduling algorithms in use today rely on heuristics to determine the best balance of computation ...