This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Ohlmann, J. W. Articles by Thomas, B. W. Search for Related Content

A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows

Department of Management Sciences, University of Iowa, 108 John Pappajohn Business Building, Iowa City, Iowa 52242-1994
Department of Management Sciences, University of Iowa, 108 John Pappajohn Business Building, Iowa City, Iowa 52242-1994
jeffrey-ohlmann{at}uiowa.edu
barrett-thomas{at}uiowa.edu

This paper describes a variant of simulated annealing incorporating a variable penalty method to solve the traveling-salesman problem with time windows (TSPTW). Augmenting temperature from traditional simulated annealing with the concept of pressure (analogous to the value of the penalty multiplier), compressed annealing relaxes the time-window constraints by integrating a penalty method within a stochastic search procedure. Computational results validate the value of a variable-penalty method versus a static-penalty approach. Compressed annealing compares favorably with benchmark results in the literature, obtaining best known results for numerous instances.

Key words: traveling salesman; time windows; heuristics; simulated annealing; penalty methods
History: received January 2004; revised December 2004; accepted April 2005.

This article has been cited by other articles:

				A. M. Campbell and B. W. Thomas Probabilistic Traveling Salesman Problem with Deadlines Transportation Science, February 1, 2008; 42(1): 1 - 21. [Abstract] [PDF]