In this paper, we examine a variant of the symmetric traveling salesman problem in which travel time uncertainty is modeled by interval ranges. We introduce a new model that incorporates some ideas from existing robust optimization models - most importantly, the ability to control the model’s level of conservatism - but does so without increasing computation time. We discuss theoretical properties of this model and demonstrate its performance compared to other robust optimization approaches in a series of computational experiments.

traveling salesman, robust optimization, interval data, Soyster.