Abstract: his paper firstly proposes a uncertain traveling salesman problem (TSP) model. This model assumes that the distance between two vertices is dynamic. With the view of application, this model considers the uncertain situations in the traffic system. Compared to the classical TSP problem, this mo del is more flexible and also has more application value. This mode is more properly for vehicle to choose the best route. This paper also proposes a hybrid app roach which is based on the ant system to solve the problem of uncertain TSP, namely, a 3-opt method is used to do the local optimization. Experiment results show that this approach can accelerate the convergence.

Key words: uncertain programming, uncertain traveling salesman problem, ant algorithm