Always the nearest town
Listing every tour is hopeless for a large network, so a quick rule is used to build one good tour. The nearest-neighbor algorithm starts at a chosen town and always moves to the nearest town not yet visited. When every town has been visited, it returns to the start.
The five towns below are all joined to each other. Start at A. The roads from A cost 3 to B, 8 to C, 6 to D and 9 to E.
Five towns, every pair joined. The tour starts at A, in gold.
Building the tour
From A the nearest town is B, at 3. From B the towns not yet visited are C at 4, D at 7 and E at 5, so the tour goes to C. From C, D is at 2 and E at 6, so it goes to D.
From D only E is left, so the tour has to take the road DE, at 10, although it is the most expensive road in the network. From E it returns to A, at 9.
The tour is A-B-C-D-E-A, and it costs 3 + 4 + 2 + 10 + 9 = 28.
The nearest-neighbor tour from A, in gold, with each town numbered in the order it is visited. It costs 3 + 4 + 2 + 10 + 9 = 28.
An upper bound, not the answer
The tour of 28 can really be driven. So the cheapest tour cannot cost more than 28: it costs 28 or less. That makes 28 an upper bound for the traveling salesman problem on this network.
It is not the cheapest tour. Five towns have tours, and costing all twelve shows the cheapest is A-B-E-C-D-A, at 3 + 5 + 6 + 2 + 6 = 22. Taking the nearest town at every step left the expensive road DE until the end, when there was no choice.
The cheapest of the twelve tours, A-B-E-C-D-A, in gold: 3 + 5 + 6 + 2 + 6 = 22.
Starting somewhere else
The algorithm can start at any town, and different starts can give different tours. From B: B to A at 3, A to D at 6, D to C at 2, C to E at 6, and E back to B at 5, a tour of 22. From C the tour is C-D-A-B-E-C, also 22; from D it is D-C-B-A-E-D, 28; and from E it is E-B-A-D-C-E, 22.
Every one of these is a real tour, so each gives an upper bound, and the best upper bound is the smallest: 22. A tour is a cycle, so one found from B can still be driven starting from A: B-A-D-C-E-B is the same tour as A-D-C-E-B-A.
If two unvisited towns are equally near, either may be chosen, and the two choices can lead to tours of different cost. On this network no such tie ever arises.
The nearest-neighbor tour from B, numbered in order of visiting: B-A-D-C-E-B, 3 + 6 + 2 + 6 + 5 = 22.
The usual mistakes
Forgetting the road home. A-B-C-D-E costs 3 + 4 + 2 + 10 = 19, but the tour must return to A, which adds 9.
Taking a nearest-neighbor tour as the cheapest. It is one real tour, so it says only that the cheapest costs that much or less.
Choosing the larger of two upper bounds. The tours of 28 and 22 are both real, so the cheapest tour is at most 22, and 22 says more.
Moving to a town already visited because it is nearest. From D the nearest town is C, at 2, but C has been visited, so the tour must go on to E.
A delivery van
In the application below, a delivery van’s round trip from its depot is found by the nearest-neighbor algorithm, and then the algorithm is run again from one of the stores to find a better upper bound.
Worked example: A Delivery Van's Round Trip From Its Depot to Five Stores, and a Second Starting Point for the Nearest-Neighbor Algorithm
Question A delivery van leaves its depot D, visits five stores A, B, C, E and F, and returns to D. The table gives the shortest road distances in kilometers: D–A 13, D–B 38, D–C 21, D–E 34, D–F 10, A–B 28, A–C 12, A–E 24, A–F 16, B–C 19, B–E 8, B–F 37, C–E 15, C–F 20, E–F 31. No two distances are equal, so the algorithm never has to break a tie. (a) Use the nearest-neighbor algorithm starting at D to find a round trip and its length. (b) Run the algorithm again starting at store A. Which of the two round trips gives the better upper bound for the shortest round trip, and what is that bound?
1.From D the nearest store is F (10 km). From F the nearest store not yet visited is A (16 km), and from A it is C (12 km).
Each leg is ringed in the row of the place it leaves: D to F, F to A, A to C. 2.From C the nearest store not yet visited is E (15 km, against B at 19 km), and from E it is B (8 km). Every store has now been visited, so the van returns from B to D (38 km).
Then C to E, E to B, and back from B to D. 3.(a) The round trip is D–F–A–C–E–B–D, of length 10 + 16 + 12 + 15 + 8 + 38 = 99 km.
(a) D–F–A–C–E–B–D is 99 km. 4.From A the nearest place is C (12 km), then E (15 km), then B (8 km). From B the nearest place not yet visited is F (37 km, against D at 38 km), then D (10 km), and the trip returns from D to A (13 km). Its length is 12 + 15 + 8 + 37 + 10 + 13 = 95 km.
From A: A–C–E–B–F–D–A is 95 km. 5.This round trip is a cycle, so the van can drive it starting from the depot, as D–A–C–E–B–F–D. (b) The trip found from A is shorter, so the better upper bound is 95 km: the shortest round trip is at most 95 km.
(b) The trip from A, driven from the depot, gives the better upper bound: 95 km.
Answer: (a) D–F–A–C–E–B–D, 99 km; (b) the round trip from A, driven as D–A–C–E–B–F–D, gives the better upper bound of 95 km
Common mistakes
- Leaving out the last leg back to the start. The round trip must close, and the return from B to D adds 38 km to the trip in (a).
- Choosing the larger length, 99 km, as the better upper bound. Both trips can be driven, so the shortest round trip is at most each of them, and the smaller one, 95 km, says more.
More spanning trees and route problems problems, worked step by step →