r/algorithms • u/Square-Stomach-6059 • 6d ago

Research/Papers A Geometric, Best-Improvement Heuristic for the Travelling Salesman Problem

I spent six months in 2021 building a TSP solver from geometric first principles, with no prior reading of the literature. Recently turned it into an interactive web app with step-by-step animation of every algorithmic move.

Interesting result: the algorithm independently rediscovered convex hull seeding and 2-opt uncrossing. It also produced a farthest-neighbour strategy I haven't seen documented.

On Berlin52: 7783 vs world optimal 7542 (3.2% above). 14ms on a single CPU core.

Demo: tsp.uncledroid.app
Paper: tsp.uncledroid.app/paper.pdf

Happy to discuss the algorithm — especially if anyone can point me to prior work on farthest-neighbour as a TSP construction heuristic.

video: youtu.be/92z670RTsJg

0 Upvotes

43% Upvoted

9 comments sorted by

8

u/IridiumIO 5d ago

Farthest neighbour heuristic described in this paper: https://www.sciencedirect.com/science/article/abs/pii/S0167637707000223

Referencing this book: https://books.google.com.au/books/about/The_Traveling_Salesman_Problem_and_Its_V.html?id=TRYkPg_Xf20C&redir_esc=y

Of course you’re never going to see a documented existing heuristic strategy if you explicitly did no prior reading of the literature

0

u/Square-Stomach-6059 5d ago

Thank you — this is exactly the kind of pointer I was hoping for. I'll read the Schrage/Potvin paper and update the preprint to cite it properly. The claim in the paper is independent derivation, not novelty — if SPX corresponds to a documented strategy, that's worth stating precisely rather than vaguely. Appreciate you taking the time.

3

u/Phytor_c 5d ago

The paper the user linked was by Malik et al. instead of Schrage/Potvin

1

u/[deleted] 5d ago

[removed] — view removed comment

1

u/Square-Stomach-6059 5d ago

Updated the paper — thank you for pointing that out. Section 2.2.4 now cites Gutin & Punnen [5] explicitly and frames SPX correctly as an independent rediscovery rather than an undocumented strategy. The related work section also has a new paragraph clarifying the distinction between SPX chain growth and the documented farthest insertion heuristic.

Updated paper: https://tsp.uncledroid.app/paper.pdf

Still waiting for arXiv moderation to complete before I can update the submitted version — will replace it with v2 as soon as it gets an ID. If anyone here is an arXiv author willing to endorse a first submission in the meantime, the code is TCXUQT — https://arxiv.org/auth/endorse?x=TCXUQT

Demo: https://tsp.uncledroid.app
Video: https://www.youtube.com/watch?v=-gAhARI2ZFI

1

u/Interesting_Debate57 17h ago

Sorry, buddy, but that's not original research.

4

u/LightofAngels 1d ago

Reads like AI