Algorithms and Heuristics for Time-Window-Constrained Traveling Salesman Problems.

Abstract

This thesis reports on methods for solving traveling salesman problems with time-window constraints. Two types of 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 Stewart's 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 method of Christofides, Mingozzi, and Toth. Computational experience is reported for all the heuristics and algorithms we develop. Keywords: Heuristic, Algorithm, Time Window, Hard Time Window, Soft Time Window, Slack, Branch and Bound, Nearest Neighbor, Penalty Cost, Traveling Salesman Problem, and State-Space Relaxation.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1985
Accession Number
ADA162118

Entities

People

  • Bock J. Chun
  • Sang H. Lee

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Accuracy
  • Air Force
  • Algorithms
  • Boundaries
  • Classification
  • Composite Materials
  • Computations
  • Computer Programming
  • Computers
  • Construction
  • Dynamic Programming
  • Integer Programming
  • Operations Research
  • Schools
  • Security
  • Travel Time
  • United States Air Force Academy

Fields of Study

  • Computer science

Readers

  • Approximation Theory.
  • Operations Research

Technology Areas

  • Space