Augmented simulated annealing algorithm for the TSP

An augmented version of the simulated annealing algorithm is described. A cyclic itinerary of a traveling salesman is determined by a permutation of N objects, where N is the number of cities. A pool of permutations is simultaneously optimized. Four operators for transformation of permutations are used. The first three operators act on single permutations, whereas the last (exchange) operator acts on a pair of permutations. This last operator exchanges segments between two permutations. The suggested method is illustrated by calculation of the optimum length of a cyclic path on randomly positioned vertices as well as for graphs with vertices situated at nodes of a square grid.