46 The travelling salesperson
James Cook, based in Bismarck (North Dakota, USA), is a super salesperson for the
Electra company, a manufacturer of carpet cleaners. The fact that he has won
salesperson of the year for three years straight is evidence of his ability. His sales area
takes in the cities of Albuquerque, Chigaco, Dallas and El Paso, and he visits each of
them in a round trip once a month. The question he sets himself is how to make the trip
and at the same time minimize the total mileage travelled. It is the classical travelling
salesperson problem.
James has drawn up a mileage chart showing distances between the cities. For
example, the distance between Bismarck and Dallas is 1020 miles, found at the
intersection (shaded) of the Bismarck column with the Dallas row.
The greedy method
Being a practical person, James Cook sketches a map of the sales area but
doesn’t worry about accuracy so long as it tells him roughly where the cities are
and the distances between them. One route he often takes starts from Bismarck
travelling to Chicago, Albuquerque, Dallas and El Paso in turn before returning to
Bismarck. This is the route BCADEB but he realizes this trip of 4113 miles in total
is expensive in terms of the distance travelled. Can he do better?
Making a plan of the sales area should not disguise the fact that James is not
in the mood for detailed planning – he wants to get out there and sell. Looking at
a map in his office in Bismarck he sees that the nearest city is Chicago. It is 706
miles away as against 883 to Albuquerque, 1020 miles to Dallas, and 1100 miles
to El Paso. He starts for Chicago immediately without an overall plan. When he
gets to Chicago and completes his business there he looks for the nearest city to
go to. He chooses Dallas in preference to Albuquerque and El Paso, because it is