Goal

Find shortest Hamilton path or cycle

The Algorithm

Step 1: Initialisation, greedy

• Do nearest neighbour from start point if fixed start point, or any point

Step 2: Optimisation, untwisting

• still_optimisable = true
• while still_optimisable: # 2-opt until no longer optimisable
• still_optimisable = false
• With all possible trunk (sequence of vertices) lengths
• Scan from start point, if reversing a trunk gives better total distance
• Reverse that trunk, and mark still_optimisable = true

Trunk Reversing Example

• Trunk length = 3
• Scan from C and reverse CDE
• Remember: It’s reversing, not swapping C and E, it’s totally wrong to swap when in between them are not single node D.

Optimisation: Before 1 reversing

Route: AB-CDE-FGH (above)

Optimisation: After 1 reversing

Route: AB-EDC-FGH (above)

Reading

• Large-scale TSP https://www.frontiersin.org/articles/10.3389/frobt.2021.689908/full
• Optimisation Strategies (above)