distance he wants to save, but time. He draws up a new table that gives the
travel time between the different cities in his territory.
When the problem was focused on mileages, James knew that the sum of the
distances along two sides of a triangle is always greater than the length of the
third side; in this case the graph is called Euclidean and much is known about
solution methods. This is not the case when the problem is one of time. Flying
on main routes is often faster than side routes and James Cook notes that in
going from El Paso to Chicago it is quicker to fly via Dallas. The so-called triangle
inequality does not apply.
The greedy method applied to the time-problem produces a total time of 22
hours on the route BCDEAB, whereas there are two distinct optimum routes
BCADEB and BCDAEB totalling 14 hours each. Of these two routes, the first is
4113 miles, and the second 3407 miles. James Cook is happy that by choosing
BCDAEB he has saved the most. As a future project he will consider the route
with least cost.
From seconds to centuries
The real difficulty associated with the travelling salesperson problem occurs
when there is a large number of cities. Because James Cook is such a brilliant
employee it is not long before he is promoted to being a supervisor. He now has
to visit 13 cities from Bismarck instead of the previous 4. He is unhappy about
using the greedy method, and prefers to look at a complete listing of the routes.
He sets out to list the possible routes for his 13 cities. He soon discovers there
would be as many as 3.1 x 10^9 routes to examine. Put another way, if a
computer took one second to print out a route it would take about a century to
print them all. A problem with 100 cities as input would tie up the computer for
millennia.
Some sophisticated methods have been applied to the travelling salesperson