Abstract: Traveling salesman problem is an important combinatorial optimization problem. The uncertain traveling salesman problem was considered. For each edge, an interval data was used to describe the uncertain travel time. In the framework of robust optimization, a model was developed. The prominent feature of this model is that the degree of conservativeness is adjustable. An exact algorithm and an ant colony optimization approach were proposed to deal with this model. Compared with the exact algorithm, the experimental results show that the proposed ant colony ptimization approach can obtain optimal or near optimal solutions within very shorter time. Finally, the property of the model was studied. The results support that the robust solution is useful in the uncertain environment.

Key words: Traveling salesman problem, Robust optimization, Exact algorithm