Farthest Insertion
The Nearest Insertion Algorithm works as follows:
1. Find the two cities farthest apart. Let's call them city 'a' and city 'b'. Join them together.
2. City 'c' is the farthest city from the edge between city 'a' and city 'b'. This is incorporated into the tour by
creating an edge between city 'c' and each of cities 'a' and 'b', thus creating a triangular mini-tour.
3. The remaining cities are incorporated as follows:
a) Find the farthest city yet to be incorporated, from any point on the mini-tour (city 'd').
b) Note the edge to which this city is closest.
c) Erase this edge, and create two new edges, between city 'd' each of the cities at the ends of the
erased closest edge.
 |
 |
| Identify the two farthest cities. | Join them together to form a mini-tour, then find the farthest city from any point of this mini-tour. |
 |
 |
| Incorporate this city by drawing a line between it and each of the two cities already on the mini-tour to form a new, three city mini-tour. Now find the farthest city from the new mini-tour. Identify the edge on the mini-tour to which the city is closest (shown in green). | Incorporate this city by erasing the closest edge to the city, and creating new edges between each of the cities at the ends of the former closest line, and the nearest city. Once again find the farthest city from this new mini-tour |
 |
 |
| Repeat the previous step... | ...throughout the tour... |
 |
 |
| ...until there remains only one city to be incorporated, and the only option... | ...is to incorporate it to complete the tour. |