TSP++
A performant solution to the TSP, utilizing ball trees, kOpt, and LKH heuristics; written in C++.
Technology Stack
Motivation
After a highly rewarding academic team experience tackling the Traveling Salesman Problem (TSP) using manually optimized 2-opt and 3-opt algorithms alongside brute-force nearest neighbor searches, I became deeply fascinated with NP-hard problems, particularly the TSP. With newfound enthusiasm and available time, I pursued an advanced, highly optimized implementation.
Visualization
I aimed to visualize near-optimal solutions interactively, leveraging a 3D representation to intuitively understand algorithmic decisions.
Performance
To push the boundaries of computational performance—and enhance my coding skills—I selected modern C++23 for its unmatched performance potential and latest language features.
Advanced Algorithms
Driven by curiosity and ambition, I sought hands-on experience with sophisticated spatial data structures (Ball Trees inspired by kd-trees) and scalable k-opt algorithms.
Features
High-Speed Ball Tree Construction
Implements highly efficient Ball Trees for rapid spatial indexing, achieving ~1ms construction time even with datasets exceeding 2,500 destinations. Enables ultra-fast nearest neighbor searches and optimized LKH candidate construction.
k-Opt with LKH Heuristics
Advanced k-opt implementation utilizing Lin–Kernighan–Helsgaun (LKH) heuristics, optimized for performance through preemptive work-stealing and mutex locks to rapidly correct global and local tour maxima.
O(1) Distance Caching
Employs a triangular distance matrix caching strategy, significantly enhancing performance with constant-time lookups and logarithmic cost reductions per iteration.
Tour State Caching
Robust integration with Boost Serialization facilitates binary tour state serialization, allowing incremental tour improvements with minimal computational overhead.
WebSocket Integration
Boost WebSocket ensures a fast, responsive communication pipeline between backend and frontend, implementing a persistent connection structure akin to REST APIs.
Cesium Rendering Engine
Custom-developed CesiumJS engine leverages backend-accelerated rendering and animation through WebSockets, greatly enhancing frontend responsiveness, especially with extensive tour datasets.
Optimized Priority Deque
Introduces the highly efficient BoundedPriorityDeque.hpp—a circular buffer with constant-time critical operations. Integral for performance gains in ball tree queries, k-opt optimizations, and more.
Multi-Threaded Ball Tree Queries
Ball tree nearest neighbor queries are multi-threaded with priority-based search pruning, effectively reducing complexity to O(log n) and evenly distributing computational loads across threads.
Multi-Threaded k-Opt
Employs advanced multi-threading techniques in k-opt, enabling threads to dynamically preempt and mutex-lock other tasks, rapidly identifying and eliminating global maxima in solution paths.
Future Plans
Complete LKH Implementation
Continue refining the k-opt algorithm by fully integrating proven Lin–Kernighan–Helsgaun heuristic optimizations as detailed in Keld Helsgaun’s extensive research.
Machine Learning Integration
Explore modern machine learning methods to intelligently prune inferior candidate solutions early, significantly reducing computational effort and further enhancing optimization outcomes.
Open-Source Initiative
Plan to progressively open-source this solution. Initial efforts will focus on extracting unique, high-performance data structures into standalone, reusable libraries, with the eventual goal of publicly releasing the full source code.