Elastic Net for the Travelling Salesman Problem
by marimo team
Draw a set of cities and watch Durbin & Willshaw's elastic net method unfurl a rubber-band tour through them.
About this notebook
This notebook shows the elastic net method for the travelling salesman problem, from Durbin and Willshaw (1987). The travelling salesman problem asks for the shortest closed tour that visits every city once. You draw your own cities, so there is no fixed dataset. The code uses numpy for the math and matplotlib for the plots. It draws the city canvas with the ScatterWidget from drawdata and the frame control with the PlaySlider from wigglystuff.
You click and drag on the canvas to place cities. Two sliders set the pull strength alpha and the path elasticity beta. You click the run button to compute the tour. A play slider steps through the saved iterations. Each frame draws the elastic band as it stretches out from a small ring near the centre. The title shows the current radius K and the checkpoint number. A second plot reads the settled path into a discrete tour and reports the tour length.
The algorithm places path points on a loop and moves them by gradient descent on an energy function. It starts K at 0.2 and reduces K by one percent every 25 iterations. This slow sharpening plays the same role as lowering the temperature in simulated annealing. After K reaches its final value the code runs 500 more steps so the path can settle. The random seed is fixed at 0. There is no caching and no GPU code.
