Iteration Methods for the Stochastic Traveling Salesman Problem

The traveling salesman problem is the task about how to make a circuit of given points within the minimum cost or distance, assuming that the cost depends proportionally on distance. When solving this problem we usually need to use the time as the objective function. But the time spent by a single realization of transport on a given route may differ depending on the actual traffic situation. So this criterion has a stochastic character. Using this point of view, the evaluation of a particular route consists of two components, the first is the proper time, meaning e.g. its expected value, of the transportation and the second is the reliability/probability that a given time will not be exceeded. So we have two criteria, i.e. a multiplecriteria task is obtained. However, the methods for solving the traveling salesman problem cannot usually be associated with the stochastic approaches and the multiplecriteria methods. This contribution shows, that the iteration methods for the traveling salesman problem, e.g. k-opt, Lin-Kernighan etc.), are suitable to be modified for this purpose and one version is applied here on several test instances.