The previous example demonstrates the use of TravelingSalesman with edge weights corresponding directly to geometric distances between vertices. In many instances of the traveling salesman problem, the weights do not correspond so directly to the geometry.
Fortunately, TravelingSalesman can also compute a tour when given an arbitrary weight matrix. To illustrate this, let us extend the previous example of a tour of 100 African cities to incorporate the idea that there might be some increased cost associated with traversing an international border.
First let us get the matrix of Euclidean distances from the previous example:
|
>
|
|
Now we can construct a new weight matrix in which the weight is doubled whenever the cities connected are in distinct countries.
|
>
|
|
We can now pass the weight matrix directly to TravelingSalesman to get a new tour.
|
>
|
|
|
| (1.2.1) |
|
>
|
|
|
| (1.2.2) |
This new tour is similar to the previous one in many respects, but notably does not visit Sudan or the Democratic Republic of the Congo twice as the first one did, illustrating the effect of our increased edge weights.
|
>
|
|
Finally we can draw the original tour (in green) and the new tour (in red) to see the effect of the altered weights.
|
>
|
|
