Smart TSP Solver v1.0.1
High-performance Python library for solving the Traveling Salesman Problem
Novel heuristic approaches that outperform classical methods by ~25% on real-world clustered data.
Smart TSP Solver is a high-performance Python library for solving the Traveling Salesman Problem (TSP) using novel heuristic approaches. Features advanced algorithms that outperform classical methods by ~25% on real-world clustered data while maintaining practical computational efficiency.
Research-driven design: This library implements cutting-edge spatial optimization techniques including dynamic gravitational attraction modeling and angular-radial spatial indexing for intelligent pathfinding.
- Dynamic Gravity Algorithms — physics-inspired approach simulating momentum and gravitational attraction for natural, efficient routing
- Angular-Radial Methods — space-partitioning heuristics with adaptive look-ahead for superior performance on geographical data
- Benchmarking Framework — professional-grade testing infrastructure with configurable scenarios and detailed metrics
- High-Performance Core — Numba JIT compilation with cache optimization for near-native execution speed
Dynamic Gravity Approach — Complexity: O(n²)
- Models a physical process of attraction where the next point is selected based on proximity and current direction of movement
deltaparameter acts as an "inertia coefficient," preventing sharp turns and creating smooth, natural-looking routes- Ideal for: balanced speed and quality, processing medium-sized datasets
Angular-Radial Method — Complexity: O(n²) with near O(n·log n) practical performance
- "Smart look-ahead" strategy (
look_ahead) with points pre-sorted in a polar coordinate system - Drastically narrows the search space for each subsequent choice
- Ideal for: offline calculations where route length is critical and tasks require scaling
| Algorithm | Complexity | Quality | Speed | Primary Use Case |
|---|---|---|---|---|
| Greedy v2 | O(n²) | ███░░ | █████ | Real-time, microseconds |
| Dynamic-gravity v2 | O(n²) | █████ | ████░ | Balanced, milliseconds |
| Angular-radial v2 | O(n²)* | █████ | ███░░ | Quality, offline |
*Practical performance approaches O(n·log n) due to spatial heuristics.
Algorithm Evolution (v1 vs. v2)
- Angular-radial v2 — ~2x speedup over v1 with identical, best-in-class route quality
- Dynamic-gravity v2 — nearly 2x speedup on 1001 points over v1, maintaining high solution quality with better stability
Algorithm Characteristics
- Greedy v2 — extremely fast (
O(n²)), ideal for real-time applications, sacrifices solution quality (+17-20% longer routes) - Dynamic-gravity — optimal choice for medium-sized problems where balance between speed and quality is required
- Angular-radial — quality leader, spatial partitioning allows best scaling on large datasets
Practical Recommendations
- Microsecond Response: Greedy v2 for interactive and real-time systems
- Millisecond Response: Dynamic-gravity v2 for balanced needs and medium-scale problems
- Best Quality: Angular-radial v2 for final calculations and offline processing
pip install smart-tsp-solver
With Benchmark:
pip install smart-tsp-benchmark
git clone https://github.com/smartlegionlab/smart-tsp-solver.git cd smart-tsp-solver python -m venv venv source venv/bin/activate pip install -r requirements.txt python main.py
