1.1. Mathematical Model#

We now wish to formulate a mathematical model of this problem. In order to do this, we must first introduce some notation to describe the input in a concise way. First of all, let the variable \(n\) denote the number of cities. For the particular input above, \(n=7\). Next, we can index our cities as \(1,2,3,4,5,6,7\) (sometimes the shorthand \(1,2,\ldots,7\) is used to indicate this). NY can correspond to city 1, Syracuse to city 2, and so forth. (If we are describing an arbitrary input, then we simply refer to cities 1 through \(n\), and this can then be denoted \(1,2,\ldots,n\), even if we have not specified the value that \(n\) takes.) Then, we need some way to describe the costs. (The costs in our example are monetary, but they generally can also be lengths, durations, etc.) A doubly indexed array (or equivalently, a two-dimensional array) can represent the table given above. Let \(C[i,j]\) denote the cost of going from city \(i\) to city \(j\), where \(i\) and \(j\) are variables that each can take any integer value between 1 and \(n\). Again, another shorthand notation for this is that the costs are \(C[i,j],\) \(i=1,2,\ldots,n\), \(j=1,2,\ldots,n\). One final observation about the input: in our example, the costs had the property that \(C[i,j]=C[j,i]\) for each \(i=1,2,\ldots,n\), and each \(j=1,2,\ldots,n\). In this case, the input is said to be symmetric. There are cases in which the input might not be symmetric, but this does not change any of the underlying ideas involved.

Now that we have given a way to describe the input, how do we describe a feasible solution? We can describe the first tour proposed above by saying that city 1 is first, city 3 is second, city 4 is third, and so forth. A more mathematical description of this is to write that \(\pi(1)=1\) (meaning that city 1 is first), \(\pi(2)=3\) (meaning that city 3 is second), \(\pi(3)=4\), \(\pi(4)=5\), \(\pi(5)=6\), \(\pi(6)=7\), and \(\pi(7)=2\). We leave it implicit that as the last part of the tour we return from city \(\pi(7)\) to city \(\pi(1)\). So the general meaning of \(\pi(i)=j\) is that city \(j\) is the \(i\)th city of the tour; to specify the tour, we must give a value to \(\pi(i)\) for each \(i=1,\ldots,n\). What properties must hold for a specification of \(\pi(i)\), \(i=1,\ldots,n\), to be feasible? Each city must be visited, and each city must be visited at most once. That is, for each \(j=1,\ldots,n\), there must exist exactly one \(i\) (from amongst the integers 1 through \(n\)) such that \(\pi(i)=j\). Here, \(\pi\) is called a permutation. Notice that we did not require the first city in the ordering to be the home city of the salesman. There is a good reason for this: a circle does not start or end at any particular point! As long as we have some permutation, we can interpret the cycle as starting at the home city. For example, for the first tour proposed above, we could equally well have set \(\pi\) so that \(\pi(1)=6\), \(\pi(2)=7\), \(\pi(3)=2\), \(\pi(4)=1\), \(\pi(5)=3\), \(\pi(6)=4\), and \(\pi(7)=5\). (Make sure that you understand why the two specifications represent the same tour.) Given any permutation \(\pi\), we can convert it into an equivalent one in which the first city is the home city by starting with the home city and tracing cyclically around the tour \(\pi\).

Now, how do we give a mathematical description of the objective function? In our example, we simply added \(C[\pi(1), \pi (2)]\), \(C[\pi(2),\pi(3)]\), and so forth through \(C[\pi(6),\pi(7)]\) and then added the last part (returning home) \(C[\pi(7),\pi(1)]\). The mathematical shorthand to replace “and so forth” is done with a summation sign as follows:

\[\sum_{i=1}^6 C[\pi(i),\pi(i+1)] + C[\pi(7),\pi(1)],\]

and so in general, the objective function is

\[\sum_{i=1}^{n-1} C[\pi(i),\pi(i+1)] + C[\pi(n),\pi(1)].\]

In summary, the traveling salesman problem can now be described as the following mathematically precise computational task.

Traveling salesman problem

input:

  • an integer \(n\) specifying the number of cities, and

  • an array \(C[i,j]\), for \(i=1,2,\ldots,n\), \(j=1,2,\ldots,n\) (not necessarily symmetric)

output:

  • a permutation \(\pi\) of \(1,2,\ldots,n\)

goal: minimize the cost of the tour, i.e.,

\[\text{minimize} \sum_{i=1}^{n-1} C[\pi(i),\pi(i+1)] + C[\pi(n),\pi(1)]\]

Notice that in our way of describing things, the word “problem” does not refer to one specific input, but rather to a general computational task that, for any input of a certain type, seeks the desired output.

Example#

Consider the following TSP problem consisting of 23 US cities. Fun fact: This instance comes from the Beyoncé On the Run II Tour.

# Imports -- make sure you run this cell!
# This cell contains multiple import statements. Each import statement gives the notebook access to pre-bundled
# python code that serves some functionality. The second import statement imports all of the python code in the
# file tsp.py. You can open this file and examine it if you so choose!

import urllib.request
urllib.request.urlretrieve('https://engri-1101.github.io/textbook/modules/tsp.py', "tsp.py")
from tsp import *
import vinal as vl
import pandas as pd
from IPython.display import Image
from bokeh.io import output_notebook, show
output_notebook()

# This cell imports a CSV file called us_cities_23.csv. We will often import CSV files.
# The data from the CSV file is put in the variable nodes.
# Using display(), we can see the contents of this file: each city (node) and its (x,y) position.

nodes = pd.read_csv('https://engri-1101.github.io/textbook/data/tsp/us_cities_23.csv', index_col=0)
display(nodes)

We can use the function vl.create_network() to create a graph from this CSV file of nodes.

# The help command returns information about what parameters this function takes
help(vl.create_network)

Since we only have a dataframe of nodes, the next function will generate the distances between them. The parameter manhattan indicates how the distances should be computed. If it is true, the Manhattan distance is computed. Otherwise, the Euclidean distance is computed. For a city located at \((a,b)\) and a city at \((c,d)\), the Manhattan distance is \(|c-a| + |d-b|\) (horizontal distance plus the vertical distance). The Euclidean distance is \(\sqrt{(c-a)^2 + (d-b)^2}\) (straight-line distance).

# Create the graph using the Euclidean distances
G = vl.create_network(nodes, manhattan=False)

Q: What is the input for this problem? Is it symmetric? Does it violate the triangle inequality?

A: \(n = 23\) cities, and \(C[i,j]\), for \(i=1,2,\ldots,n\), \(j=1,2,\ldots,n\), is the distance between city \(i\) and city \(j\). Both Manhattan and Euclidean distances here are symmetric and satisfy the triangle inequality.

Now we can find a tour manually. Running the cell below will generate a visual of the 23 cities. Click on the cities one at a time to create a tour. Clicking on the last node will automatically complete the tour. In the lower left, you will see the cost of the tour update as you create it. In the lower right, you will see the tour.

urllib.request.urlretrieve('https://engri-1101.github.io/textbook/other/us.png', "us.png")
show(vl.create_tour_plot(G, width=600, height=375, image='us.png'))

Q: What was the smallest tour cost you found?

Q: What difficulties did you encounter in choosing your tour?

Q: What methods did you use in finding this tour? Did you just eyeball it, or did you try to develop and apply a simple algorithm? Once you had a feasible tour, did you try to improve upon it by changing it a little at a time, or did you start again from scratch to try to find a better route?