C++23 TSP solution demoed with CesiumJS, exploring the use of Ball Trees in Nearest Neighbor searches, optimized with LKH/kOpt heuristics.
.jpg&w=3840&q=75)
Meson
Conan
Following a highly-rewarding academic team project experience in the TSP using hard-coded optimizations for 2opt and 3opt, with brute force nearest neighbor searches; at the end of the semester I was left with a newfound obsession with the TSP (really np-hard problems in general) and a lot of time on my hands.
I so, so badly desired to achieve a near optimal solution, especially if I could visualize it in 3D (see CesiumTSP).
Seeking the limits of computational performance (and to improve my skills), I chose C++ for this project. It makes use of modern C++23 standard features.
An interest in gaining hands-on experience in things like kd-trees (which inspired the Ball Tree) and kOpt which could scale beyond hard-coded limits.
Utilizes ball-trees, highly efficient spatial data structures for nearest neighbor searching as well as LKH kOpt candidate construction.
kOpt using LKH heuristics such as gain, in a preempted work-stealing environment allowing for highly-effective maxima corrections in both local and global tour scope.
Utilizes a triangular distance matrix to efficiently store and retrieve distance calculations in O(1) time, enabling a sort of logarithmic cost-reduction function across iterations.
Boost serialization integrated into all critical stateful components allows binary serialization of tours, enabling iterative improvement with minimal overhead.
Utilizes boost web socket to communicate with frontend, similar request/response structure to REST in a persistent connection environment.
Custom designed CesiumJS rendering engine, works via web-socket and allows offloading of polyline rendering and animation to the backend, significantly speeding up the frontends responsiveness on large tours.
Inspired the BoundedPriorityDeque.hpp library, a highly efficient circular buffer with O(1) critical operations. Used in ball tree construction/querying, kOpt, and other optimization frameworks.
Nearest neighbor ball tree queries utilize a multi-threaded, priority based search pruning that prunes half the search points (making it O(log n)) and distributes threads among remaining inner nodes.
kOpt benefits from tasks which when faced with an outlier edge (determined via heuristics), may preempt or lock the mutex of other threads determined to have the best candidates to reduce the edge. This approach allows for the elimination of global maxima amongst locally scoped tasks.
The current kOpt solution takes inspiration from many concepts in Lin–Kernighan Heuristics, including later optimizations to the heuristic proposed by Keld Helsgaun who has been publishing TSP research for ~30 years. Full implementation is planned long-term.
Take advantage of modern machine learning algorithms as a heuristic to eliminate poor candidate solutions from consideration altogether.
I would like to share this solution publicly when its viable to do so. At the current moment, my focus is on extracting some of the more useful and niche data structures I implement from the code into standalone libraries. Eventually the full source code will be publicly displayed.
Single-header, lightweight, and performant bounded priority dequeue with wide applicability via templating. Implemented in C++ as a circular buffer.
This is a modern TSP visualizer built with CesiumJS, Vite, TS, React, Zustand, RHF, and other robust frameworks for a highly-immersive experience.