A Compressed-Annealing Heuristic for the Traveling Salesman Problem with Time Windows
Jeffrey W. Ohlmann, Barrett W. Thomas
INFORMS Journal on Computing · 2007 · Volume 19 · Issue 1
Abstract
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.
Keywords
traveling salesman, time windows, heuristics, simulated annealing, penalty methods
Enable JavaScript for citation tools and additional paper interactions.