Travelling Salesman Problem in Uncertain Environments

ABSTRACT

In practice, due to the lack of information, imprecise variables which come from experts’ empirical data usually appear. In order to deal with these imprecise variables, uncertainty theory is proposed and has been proved to be an efficient method. This paper introduces uncertainty theory into travelling salesman problem (TSP), in which the link travel times are assumed to be uncertain variables, and then a chance constrained programming model is proposed within the framework of uncertainty theory. The properties of the chance constrained programming model are investigated; furthermore, the uncertain model is proved to be equivalent to a deterministic model. To solve the problem, we design an algorithm based on genetic algorithm. Finally, a numerical example is given, the result of which verifies the effectiveness of the proposed chance constrained programming model and the algorithm.

Keywords:

Chance-constrained programming, genetic algorithm, travelling salesman problem, uncertainty theory.