The Model Of Travelling Salesman Problem Under Uncertain Environment And It's Algorithm

Travelling salesman problem is a kind of integer programming problems which is described easily but solved difficultly.The traveling salesman problem has been one of the optimization problem of widespread research because of that it is the most basic route problem,and it's very difficult to solve by the possible path along is growing exponentially with the growth of the number of cities.First of all,some research about the traveling salesman problem was done under the uncertain environment.1.Assuming that the cost of travel between the cities has the uncertainty distribution,a model with variance constrain to minimize the cost is established based on uncertainty theory.And,in order to solve the model,a modified genetic algorithm is given.2.Assuming that the cost of travel between the cities were uncertain random variable.A new model,whose goal is to minimize the expect value of cost and constraint is chance left measure,is established based on chance theory,it is called chance left constraint model of travelling salesman problem.And a new algorithm is given which is combined by simulations of chance measure and genetic algorithm,it is caled GASO algorithm.At the same time,numerical examples which were in view of the above two models respectively were given to verify the effectiveness of the models.