A salesman is to visit each one of 4 towns and return to the start. The distance from town to town is given in the table below.
| From\To |
A |
B |
C |
D |
| A |
- |
1 |
4 |
5 |
| B |
3 |
- |
1 |
2 |
| C |
2 |
4 |
- |
3 |
| D |
5 |
2 |
6 |
- |
The distance between towns is not the same in the other direction, because of one way systems and diversions etc. The problem is to find the order in which towns must be visited so that the distance travelled is minimised, and the distance travelled.
This is a problem in integer programming. We start but subtracting the smallest entry in each row from other entries in that row, obtaining the table below.
| From\To |
A |
B |
C |
D |
| A |
- |
0 |
3 |
4 |
| B |
2 |
- |
0 |
1 |
| C |
0 |
2 |
- |
1 |
| D |
3 |
0 |
4 |
- |
Now do the same for the columns.
| From\To |
A |
B |
C |
D |
| A |
- |
0 |
3 |
3 |
| B |
2 |
- |
0 |
0 |
| C |
0 |
2 |
- |
0 |
| D |
3 |
0 |
4 |
- |
The first and second rows were reduced by 1 each, and the third and fourth rows by two each. Then the fourth column was reduced by one. The sum of all these is seven, and this represents a lower bound for the distance that must be travelled, since each town must be accessed by some route. Now replace each zero by the sum of the smallest entry in the corresponding row and the smallest entry in the corresponding column and ignore all other entries.
| From\To |
A |
B |
C |
D |
| A |
|
3 |
0 |
0 |
| B |
|
|
3 |
0 |
| C |
2 |
|
|
0 |
| D |
|
3 |
|
|
Take one of the largest values in this table, AB=3. If AB is not in the circuit, the we will leave A for some other town than B and B will be reached from some other town than A, and a 3 can be added to the lower bound. If AB is in the circuit, exclude the row A and column B and the entry BA, since that would take us straight back to A without C and D having been visited.
| From\To |
A |
C |
D |
| B |
|
0 |
0 |
| C |
0 |
|
0 |
| D |
3 |
4 |
|
Reduce the last row by 3 and add this to the lower bound, using AB as part of the route.
| From\To |
A |
C |
D |
| B |
|
0 |
0 |
| C |
0 |
|
0 |
| D |
0 |
1 |
|
This gives us the table below for the sums of the lowest remaining entries in row and column.
| From\To |
A |
C |
D |
| B |
|
1 |
0 |
| C |
0 |
|
0 |
| D |
1 |
|
|
If we do not take BC as part of the route, then the lower bound increases by 1 to 11. If BC is not in the route, cross out row B and column C, and and entry CA. giving:
The circuit is completed using CD, DA total length 10. If we do not use BC, then we know already that the length of any circuit is at least 11. Going back one step, a circuit not including AB has length at least 10. A circuit must cover at length at least 10 to visit every town. A route of length 10 is ABCDA.
