salesman.sq

Minimization of the travel of a salesman

The problem of the salesman consists in minimizing the closed travel which links a set of towns. All towns must be visited exactly once. No known algorithm exists, except for an exhaustive search. The proposed SQ file is not intended to provide an efficient optimization method, but to show how Sysquake can be used with an idle handler to run continuously. The ability to move the towns interactively and to observe how the travel is optimized in subtle ways is fascinating.

First contact

A salesman must visit all the towns and come back to his starting point. He wants to minimize the length of the total journey. The figure represents each town with a circle, and the journey with a red line. The position of the towns and the initial journey are chosen randomly. At each optimization step, a swap is performed to reduce the total length. What is obtained is usually a local minimum, i.e. there are smaller journeys which cannot be obtained with a single swap.

To add some fun to the optimization, the salesman must avoid crossing the river too many times. Crossing the river adds a penalty which can be chosen in the Settings menu (a negative penalty means that the salesman likes crossing the river). The river and each town can be moved interactively with the mouse. The river may also be put in Automatic Rotation mode in the Settings menu.

Figures

Travel

The towns are displayed as black circles; the travel is displayed as a closed red line which links all the towns; and the river is displayed as a vertical line, blue if it is associated with a positive penalty (which minimizes the number of crossings) and green if it is associated with a negative penalty. The towns and the river can be moved interactively.

Statistics

The total length of the travel is displayed against the number of iterations of the optimization. A threshold is displayed as a horizontal line and can be adjusted interactively. When it is above the current local minimum, permutations which can increase the length of the travel up to this level are allowed and chosen randomly. When the level is decreased, the length may reach a lower local minimum.

Settings

Improve

Performs one step of optimization, i.e. one permutation which will either decrease the total length of the travel or pick randomly a permutation below the threshold fixed in the Statistics figure.

Automatic Run

When checked, the optimization runs automatically.

Automatic River Rotation

When checked, the river rotates slowly.

Number of Towns

A dialog is displayed, where the number of towns can be changed. If the OK button is clicked (whether the number of towns has been changed or not), the town positions are chosen randomly.

River Penalty

A dialog is displayed, where the penalty associated with each crossing of the river can be changed. The penalty is expressed as a distance, positive to reduce the number of crossings and negative to increase it. When you choose a large value (e.g. 100), the river is crossed only twice if there are towns on each side. This is clearly visible when you move the river if Automatic Run is checked.