Cache the distance between points i and j.

The Vec2s can be forgotten now, because we’re only interested in topological properties, not the coordinates themselves. Once the calculation is done, the result permutation can be obtained with pathToPoints.

Cache for the (symmetrical) distance between points. See distances.

Permute the input vector with the result of a TSP optimization.

Abstract point in the TSP algorithms. Corresponds to the \(i\)-th input point.

Interpret the input as a path as-is. The simplest possible TSP solver. :-)

(image code)

>>> :{
haddockRender "Numerics/Optimization/TSP/input_path.svg" 300 200 $ \_ -> do
   points <- liftIO $ do
       gen <- MWC.initialize (V.fromList [])
       uniform <- uniformlyDistributedPoints gen (shrinkBoundingBox 10 [zero, Vec2 300 200]) 32
       pure uniform
   setLineJoin LineJoinRound
   let path = inputPath points
       tour = Polygon (V.toList (pathToPoints points path))
   cairoScope $ do
       setColor (mma 0)
       for_ points $ \p -> sketch (Circle p 3) >> fill
   cairoScope $ do
       setColor (mma 1)
       sketch tour
       stroke
:}
Generated file: size 11KB, crc32: 0xde10a233

Starting at the \(i\)-th point, create a path by taking the nearest neighbour. This algorithm is very simple and fast, but yields surprisingly short paths for everyday inputs.

It is an excellent starting point for more accurate but slower algorithms, such as tsp2optPath.

(image code)

>>> :{
haddockRender "Numerics/Optimization/TSP/nearest_neighbour_path.svg" 300 200 $ \_ -> do
   points <- liftIO $ do
       gen <- MWC.initialize (V.fromList [])
       uniform <- uniformlyDistributedPoints gen (shrinkBoundingBox 10 [zero, Vec2 300 200]) 32
       pure uniform
   setLineJoin LineJoinRound
   let dm = distances points
       path = tspNearestNeighbourPath dm
       tour = Polygon (V.toList (pathToPoints points path))
   cairoScope $ do
       setColor (mma 0)
       for_ points $ \p -> sketch (Circle p 3) >> fill
   cairoScope $ do
       setColor (mma 2)
       sketch tour
       stroke
:}
Generated file: size 11KB, crc32: 0x1474da44

Move towards a local minimum using the 2-opt algorithm: delete 2 edges, and if the reconnected version is shorter than the original. The result of this algorithm is guaranteed to be at most as large as its input.

Starting this algoritm from a path optimized by tspNearestNeighbourPath speeds it up considerably, although this usually yields a different but similarly good result than applying it directly.

(image code)

>>> :{
haddockRender "Numerics/Optimization/TSP/2-opt.svg" 300 200 $ \_ -> do
   points <- liftIO $ do
       gen <- MWC.initialize (V.fromList [])
       uniform <- uniformlyDistributedPoints gen (shrinkBoundingBox 10 [zero, Vec2 300 200]) 32
       pure uniform
   setLineJoin LineJoinRound
   let dm = distances points
       path = tsp2optPath dm (tspNearestNeighbourPath dm)
       tour = Polygon (V.toList (pathToPoints points path))
   cairoScope $ do
       setColor (mma 0)
       for_ points $ \p -> sketch (Circle p 3) >> fill
   cairoScope $ do
       setColor (mma 3)
       sketch tour
       stroke
:}
Generated file: size 11KB, crc32: 0x73c4af54

Inplace version of tsp2optPath.

How much would the path length change if the two segments were swapped?

Does not modify the input vector, but marked as unsafe because out of bounds will error.

For a bit more on the args’ constraints, see unsafeCommit3optSwap.

Perform a 2-opt swap as specified.

The requirements on \(i,j\) are not checked, hence unsafe. For details see unsafeCommit3optSwap.

Move towards a local minimum using the 3-opt algorithm: delete 3 edges, and if the reconnected version is shorter than the original. The result of this algorithm is guaranteed to be at most as large as its input.

3-opt yields higher quality results than 2-opt, but is considerably slower. It is highly advised to only run it on already optimized paths, e.g. starting from tspNearestNeighbourPath or tsp2optPath.

(image code)

>>> :{
haddockRender "Numerics/Optimization/TSP/3-opt.svg" 300 200 $ \_ -> do
   points <- liftIO $ do
       gen <- MWC.initialize (V.fromList [])
       uniform <- uniformlyDistributedPoints gen (shrinkBoundingBox 10 [zero, Vec2 300 200]) 32
       pure uniform
   setLineJoin LineJoinRound
   let dm = distances points
       path = tsp3optPath dm (tspNearestNeighbourPath dm)
       tour = Polygon (V.toList (pathToPoints points path))
   cairoScope $ do
       setColor (mma 0)
       for_ points $ \p -> sketch (Circle p 3) >> fill
   cairoScope $ do
       setColor (mma 4)
       sketch tour
       stroke
:}
Generated file: size 11KB, crc32: 0x6c4e9493

Inplace version of tsp3optPath.

Swapping cases of 3-opt. Created by unsafePlan3optSwap, consumed by unsafeCommit3optSwap.

If an improvement can be made by 3 segments, which case yields the largest improvement, and by what amount?

Does not modify the input vector, but marked as unsafe because out of bounds will error.

For a bit more on the args’ constraints, see unsafeCommit3optSwap.

Perform a 3-opt swap as specified.

The requirements on \(i,j,k\) are not checked, hence unsafe. Their purpose is making a minimal search of the problem space possible, exploiting all symmetries available by a symmetrical distance function and the 3-opt swaps:

• We can choose \(i<j<k\) WLOG, because 3-opt swaps are 3-symmetric.
• \(i\) needs to leave space for \(i+1,j,j+1,k,k+1\), hence the \(n-5\).
• Similarly, \(j\) needs to leave space for \(j+1,k,k+1\), hence the \(n-3\).
• \(k\) can point to the very end, leaving \(k+1\) to cycle around to the beginning.