""" 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