"""
tsp_simple.py: Construction and local optimization for the TSP.
The Traveling Salesman Problem (TSP) is a combinatorial optimization
problem, where given a map (a set of cities and their positions), one
wants to find an order for visiting all the cities in such a way that
the travel distance is minimal.
This file contains a set of functions which are less efficient than
those in file 'tsp.py', but which are easier to understant by beginners.
Copyright (c) by Joao Pedro PEDROSO and Mikio KUBO, 2007
"""
import math
import random
import numpy
def exchange_cost(tour, i, j, D):
"""Calculate the cost of exchanging two arcs in a tour.
Determine the variation in the tour length if
arcs (i,i+1) and (j,j+1) are removed,
and replaced by (i,j) and (i+1,j+1)
(note the exception for the last arc).
Parameters:
-t -- a tour
-i -- position of the first arc
-j>i -- position of the second arc
"""
if j < len(tour)-1:
return (D[tour[i],tour[j]] + D[tour[i+1],tour[j+1]]) - \
(D[tour[i],tour[i+1]] + D[tour[j],tour[j+1]])
else:
return (D[tour[i],tour[j]] + D[tour[i+1],tour[0]]) - \
(D[tour[i],tour[i+1]] + D[tour[j],tour[0]])
def exchange(tour, i, j):
"""Exchange arcs (i,i+1) and (j,j+1) with (i,j) and (i+1,j+1).
For the given tour 't', remove the arcs (i,i+1) and (j,j+1) and
insert (i,j) and (i+1,j+1).
This is done by inverting the sublist of cities between i and j.
"""
n = len(tour)
assert i>=0 and i ',
z = localsearch(tour, z, D) # local search starting from the random tour
print tour, z
print
# greedy construction
print "greedy construction with nearest neighbor + local search:"
for i in range(n):
tour = nearest_neighbor(n, i, D) # create a greedy tour, visiting city 'i' first
z = length(tour, D)
print "nneigh:", tour, z, ' --> ',
z = localsearch(tour, z, D)
print tour, z
print
# multi-start local search
print "random start local search:"
niter = 100
tour,z = multistart_localsearch(niter, n, D, report_sol)
assert z == length(tour, D)
print "best found solution (%d iterations): z = %g" % (niter, z)
print tour
print