Project 'hard problems': traveling salesman problem

Selected Topics in Mathematical Optimization: 2017-2018

Michiel Stock (email)

YOUR NAME(S) HERE

In [ ]:
# everything you need for the TSP!
from tsp_utils import *

%matplotlib inline

The traveling salesman problem

Traveling salesman problem (TSP): Given a list of cities and the distances between each pair of cities, find the tour with the lowest possible total cost that visits each city exactly once and returns to the origin city.

  • $n$ cities $x_1,\ldots,x_n$.
  • Cost matrix $C[x_i, x_j]$ (possibly symmetric and/or triangle inequality).
  • Search space is all permutations of cities: size of $(n-1)!$.
  • Objective function: sum of costs of the paths.

For this problem, the 'cities' are represented as points on the 2D plane. The $x,y$-coordinates are stored in the Numpy array coordinates and the distances between two cities are found in the Numpy array distances.

In [ ]:
coordinates[:10]
In [ ]:
n = len(coordinates)
print('There are {} cities.'.format(n))
In [ ]:
distances[:10,:10]

Cities are referred by their respective index. A tour is implemented as a list of the permutation of the indices of $n$ cities, e.g. [0, 1, 2, ..., n-1]. Note that the cost is invariant w.r.t. cyclic permutations, i.e. the cost is the same independent from which city the tour starts.

In [ ]:
tour = list(range(n))

tour

Some simple function are provided to compute the length of a given tour and to plot the cities and a tour.

In [ ]:
cost = compute_tour_cost(tour, distances)
print('Cost of tour is {:.3f}'.format(cost))

fig, ax = plt.subplots(figsize=(8, 8))
plot_cities(ax, coordinates, color=blue)  # plot cities as a scatter plot
plot_tour(ax, tour, coordinates, distances, color=red, title=True)  # add the tour

A tour can be saved and loaded in a JSON file. You have to hand in your best tour!

In [ ]:
save_tour('Data/my_tour.json', tour)

loaded_tour = load_tour('Data/my_tour.json')
In [ ]:
!rm Data/my_tour.json

Assignments

Implement two heuristic algorithms for finding a low-cost tour:

  • write a report in the notebook discussing your strategy and the final results;
  • embed the code with sufficient documentation;
  • plot your final best tour in your notebook with the total cost.

Project

DESCRIBE YOUR STRATEGY

In [ ]:
# CELLS FOR CODE!
# TINY EXAMPLE FROM MICHIEL

import itertools as it

def yield_some_permutations(tour, mtry):
    """
    Yields mtry permutations of a tour.
    """
    count = 0
    for perm in it.permutations(tour):
        yield perm
        count += 1
        if count > mtry:
            break

def lazy_brute_force(distances, mtry=10000):
    n, _ = distances.shape
    return min(yield_some_permutations(list(range(n)), mtry),
                key=lambda t : compute_tour_cost(t, distances))
In [ ]:
%timeit

best_tour = lazy_brute_force(distances, mtry=10000)
In [ ]:
cost = compute_tour_cost(best_tour, distances)
print('Cost of tour is {:.3f}'.format(cost))  # improvement!

fig, ax = plt.subplots(figsize=(8, 8))
plot_cities(ax, coordinates, color=blue)  # plot cities as a scatter plot
plot_tour(ax, best_tour, coordinates, distances, color=orange, title=True)  # add the tour

DESCRIBE YOUR RESULTS