Package Details

Summary

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.

Description

Smart TSP Solver ^v1.0.0

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.

GitHub top language

Research-driven design: This library implements cutting-edge spatial optimization
techniques including dynamic gravitational attraction modeling and angular-radial
spatial indexing for intelligent pathfinding.

🚀 Features

🧠 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

🔬 Scientific Foundation

🧠 Algorithmic Innovations

Library implements two advanced heuristic approaches, each tackling the classic speed-quality trade-off in a unique way.

🧲 Dynamic Gravity Approach

Complexity: O(n²)

Concept: This algorithm models a physical process of attraction, where the next point is selected based on a combination of proximity and current direction of movement. The delta parameter acts as an "inertia coefficient," preventing sharp turns and creating smooth, natural-looking routes.

Strengths	Ideal Use Case
• Predictable execution time • Consistently high solution quality • Efficient cluster traversal	The balance of speed and quality, processing medium-sized datasets

📐 Angular-Radial Method

Complexity: O(n²) with near O(n·log n) practical performance

Concept: A "smart look-ahead" strategy (look_ahead). Points are pre-sorted in a polar coordinate system, which drastically narrows the search space for each subsequent choice. This is equivalent to a navigator scanning the nearest sector on the horizon instead of re-examining the entire map every time.

Strengths	Ideal Use Case
• Best-in-class final route quality • Near-linear practical performance • Exceptional efficiency on clustered data	Offline calculations where route length is critical and tasks require scaling

Hierarchical TSP Solver

A traveling salesman problem (TSP) solver using hierarchical decomposition and metaheuristics.

🧠 Algorithm Overview

Core Philosophy: Divide-and-Conquer with Geometric Intelligence

The solver employs a multi-level hierarchical approach that mirrors
human problem-solving strategies for large-scale routing:

Spatial Decomposition: Recursively partition the problem into manageable clusters
Local Optimization: Solve subproblems optimally within each cluster
Global Integration: Intelligently combine local solutions into a global route
Refinement: Apply local search to polish the final solution

Performance Comparison

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.
*Worst-case complexity. Practical performance is near O(n·log n) due to spatial heuristics

Benchmarking Methodology

All algorithms are compared against a highly optimized greedy implementation featuring:
- Numba JIT compilation with fastmath and caching
- Euclidean distance optimization with squared distance comparisons
- Memory-efficient visited node tracking
- Reproducible results through seed-based initialization

This ensures fair comparison against a professionally implemented baseline rather than naive reference implementations.

📦 Installation

Install

pip install smart-tsp-solver

Example

Launch using Smart TSP Benchmark

pip install smart-tsp-benchmark

from smart_tsp_benchmark.tsp_benchmark import TSPBenchmark, AlgorithmConfig

from smart_tsp_solver import hierarchical_tsp_solver_v2
from smart_tsp_solver.algorithms.angular_radial.v1 import angular_radial_tsp_v1
from smart_tsp_solver.algorithms.angular_radial.v2 import angular_radial_tsp_v2
from smart_tsp_solver.algorithms.dynamic_gravity.v1 import dynamic_gravity_tsp_v1
from smart_tsp_solver.algorithms.dynamic_gravity.v2 import dynamic_gravity_tsp_v2
from smart_tsp_solver.algorithms.other.greedy.v2 import greedy_tsp_v2


def main():
    config = {
        'n_points': 1000,
        'seed': 123,
        'point_generation': 'cluster',
        'use_post_optimization': False,
        'plot_results': True,
        'verbose': True
    }
    benchmark = TSPBenchmark(config=config)
    benchmark.add_algorithm(
        name='Angular-radial v1',
        config=AlgorithmConfig(
            function=angular_radial_tsp_v1,
            params={
                "sort_by": "angle_distance",
                "look_ahead": 100,
                "max_2opt_iter": 100
            },
            post_optimize=True,
            description="Angular-radial v1",
            is_class=False
        )
    )
    benchmark.add_algorithm(
        name='Angular-radial v2',
        config=AlgorithmConfig(
            function=angular_radial_tsp_v2,
            params={
                "sort_by": "angle_distance",
                "look_ahead": 100,
                "max_2opt_iter": 100
            },
            post_optimize=True,
            description="Angular-radial v2",
            is_class=False
        )
    )
    benchmark.add_algorithm(
        name='Dynamic-gravity v1',
        config=AlgorithmConfig(
            function=dynamic_gravity_tsp_v1,
            params={
                "delta": 0.5,
                "fast_2opt_iter": 100
            },
            post_optimize=True,
            description="Dynamic-gravity v1",
            is_class=False
        )
    )
    benchmark.add_algorithm(
        name='Dynamic-gravity v2',
        config=AlgorithmConfig(
            function=dynamic_gravity_tsp_v2,
            params={
                "delta": 0.5,
                "fast_2opt_iter": 100
            },
            post_optimize=True,
            description="Dynamic-gravity v2",
            is_class=False
        )
    )
    benchmark.add_algorithm(
        name='Greedy v2',
        config=AlgorithmConfig(
            function=greedy_tsp_v2,
            params={},
            post_optimize=False,
            description="Classic greedy TSP algorithm",
            is_class=False,
        )
    )
    benchmark.add_algorithm(
        name='Hierarchical TSP',
        config=AlgorithmConfig(
            function=hierarchical_tsp_solver_v2,
            params={
                "cluster_size": 100,
                "post_optimize": True
            },
            post_optimize=False,
            description="Hierarchical clustering TSP solver",
            is_class=False
        )
    )
    benchmark.run_benchmark()


if __name__ == '__main__':
    main()

🚀 Example

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

📊 Comprehensive Performance Analysis

Experimental Results

📊 Smart TSP Algorithms Benchmark Report

Our comprehensive benchmarking reveals a clear performance-quality tradeoff across different problem scales, highlighting the strengths of each algorithm.

🔵 Dataset: 100 Points (Random Distribution)

Key Insight: For small-scale problems, the Dynamic-gravity v2 algorithm demonstrates the best balance, achieving near-optimal path quality while maintaining near-real-time performance.

Algorithm	Time (s)	Δ vs Best	Route Length	Δ vs Best	Parameters
Greedy v2	0.0015	BASELINE	1026.37	+20.66%	`start_point=0`
Dynamic-gravity v1	0.0071	+367%	850.86	+0.03%	`delta=0.5`
Dynamic-gravity v2	0.0071	+367%	856.14	+0.65%	`delta=0.5`
Angular-radial v2	0.0086	+469%	850.62	BASELINE	`look_ahead=100`
Angular-radial v1	0.0812	+5243%	850.62	BASELINE	`look_ahead=100`

🔴 Dataset: 1001 Points (Large Random Distribution)

Key Insight: For large-scale problems, Angular-radial v2 becomes the undisputed leader in solution quality (providing a 17.3% shorter route than the Greedy algorithm). Its acceptable processing time makes it ideal for quality-sensitive offline applications.

Algorithm	Time (s)	Δ vs Best	Route Length	Δ vs Best	Parameters
Greedy v2	0.0023	BASELINE	2985.82	+17.31%	`start_point=0`
Dynamic-gravity v2	0.0186	+696%	2726.36	+7.12%	`delta=0.5`
Dynamic-gravity v1	0.0321	+1269%	2837.78	+11.50%	`delta=0.5`
Angular-radial v2	0.1346	+5647%	2545.21	BASELINE	`look_ahead=1001`
Angular-radial v1	0.2555	+10809%	2545.21	BASELINE	`look_ahead=1001`

🎯 Key Insights & Analysis

Algorithm Evolution (v1 vs. v2):
- Angular-radial v2 shows a ~2x speedup over v1 while delivering identical, best-in-class route quality.
- Dynamic-gravity v2 also demonstrates a significant speed improvement (nearly 2x on 1001 points) over v1, maintaining consistently high solution quality with better stability.
Algorithm Characteristics:
- Greedy v2: Extremely fast (O(n²)), ideal for real-time applications, but sacrifices solution quality (+17-20% longer routes).
- Dynamic-gravity: Offers significantly better quality than the greedy approach. It has O(n²) complexity with higher constant factors, making it the optimal choice for medium-sized problems where a balance between speed and quality is required.
- Angular-radial: The quality leader. Its use of spatial partitioning (O(n log n)) allows it to scale best on large datasets. It is the recommended choice for offline processing where final route cost is the primary concern.
Practical Recommendations:
The library provides a continuum of solutions for different use cases:
- 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 where route cost is paramount.

🎨 Advanced Visualization

LOGO
LOGO
LOGO
Visual analysis showing Angular-radial's optimal sector-based routing, Dynamic-gravity's smooth trajectories, Greedy's suboptimal clustering

🏗️ Architecture & Implementation

Performance Optimization

Numba JIT Compilation: Critical paths compiled to native code
Memory Efficiency: Pre-allocated arrays and minimal copying
Cache Optimization: Intelligent memoization and reuse
Vectorized Operations: NumPy-based efficient computations

👨‍💻 Author

Alexander Suvorov

Researcher specializing in computational optimization and high-performance algorithms
Focused on bridging theoretical computer science with practical engineering applications
This project represents extensive research into spatial optimization techniques

Explore other projects on GitHub.

For those interested in the theoretical foundations:

Exact TSP Solutions (TSP ORACLE): exact-tsp-solver - Optimal solutions for small instances
Smart TSP Benchmark - Smart TSP Benchmark is a professional algorithm testing infrastructure with customizable scenarios and detailed metrics.
Spatial Optimization: Computational geometry approaches for large-scale problems
Heuristic Analysis: Comparative study of modern TSP approaches

📜 License & Disclaimer

BSD 3-Clause License

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

📊 Sample Output

==================================================
          SMART TSP ALGORITHMS BENCHMARK          
==================================================
Points:           100
Seed:           123
Generation:     cluster
Post-opt:       OFF
Algorithms:    
  - Angular-radial v1: 
  - Angular-radial v2: 
  - Dynamic-gravity v1: 
  - Dynamic-gravity v2: 
  - Greedy v2: 
  - Hierarchical TSP: 
==================================================


==================================================
Running Angular-radial v1 algorithm...
Description: Angular-radial v1
Completed in 0.0848 seconds
Route length: 553.66
==================================================

==================================================
Running Angular-radial v2 algorithm...
Description: Angular-radial v2
Completed in 0.0082 seconds
Route length: 553.66
==================================================

==================================================
Running Dynamic-gravity v1 algorithm...
Description: Dynamic-gravity v1
Completed in 0.0070 seconds
Route length: 567.00
==================================================

==================================================
Running Dynamic-gravity v2 algorithm...
Description: Dynamic-gravity v2
Completed in 0.0067 seconds
Route length: 534.90
==================================================

==================================================
Running Greedy v2 algorithm...
Description: Classic greedy TSP algorithm
Completed in 0.0016 seconds
Route length: 609.21
==================================================

==================================================
Running Hierarchical TSP algorithm...
Description: Hierarchical clustering TSP solver
Completed in 0.0343 seconds
Route length: 524.25
==================================================

============================================================================================================================
                                               DETAILED ALGORITHM COMPARISON                                                
============================================================================================================================
Algorithm            | Time (s) |  vs Best  | Length | vs Best | Params                                                     
----------------------------------------------------------------------------------------------------------------------------
Greedy v2            | 0.0016 | BEST | 609.21 | +16.21% |                                                            
Dynamic-gravity v2   | 0.0067 | +332.71%  | 534.90 | +2.03%  | delta=0.5, fast_2opt_iter=100                              
Dynamic-gravity v1   | 0.0070 | +349.52%  | 567.00 | +8.15%  | delta=0.5, fast_2opt_iter=100                              
Angular-radial v2    | 0.0082 | +430.93%  | 553.66 | +5.61%  | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
Hierarchical TSP     | 0.0343 | +2110.90% | 524.25 | BEST | cluster_size=100, post_optimize=True                       
Angular-radial v1    | 0.0848 | +5361.28% | 553.66 | +5.61%  | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
============================================================================================================================

PERFORMANCE ANALYSIS:
- Fastest algorithm(s): Greedy v2 (0.0016 sec)
- Shortest route(s): Hierarchical TSP (524.25 units)

==================================================
          SMART TSP ALGORITHMS BENCHMARK          
==================================================
Points:           50
Seed:           123
Generation:     random
Post-opt:       OFF
Algorithms:    
  - Angular-radial v1: 
  - Angular-radial v2: 
  - Dynamic-gravity v1: 
  - Dynamic-gravity v2: 
  - Greedy v2: 
==================================================


==================================================
Running Angular-radial v1 algorithm...
Description: Angular-radial v1
Parameters: 
Completed in 0.0798 seconds
Route length: 658.16
==================================================

==================================================
Running Angular-radial v2 algorithm...
Description: Angular-radial v2
Parameters: 
Completed in 0.0082 seconds
Route length: 658.16
==================================================

==================================================
Running Dynamic-gravity v1 algorithm...
Description: Dynamic-gravity v1
Parameters: 
Completed in 0.0067 seconds
Route length: 582.13
==================================================

==================================================
Running Dynamic-gravity v2 algorithm...
Description: Dynamic-gravity v2
Parameters: 
Completed in 0.0065 seconds
Route length: 577.06
==================================================

==================================================
Running Greedy v2 algorithm...
Description: Classic greedy TSP algorithm
Parameters: 
Completed in 0.0016 seconds
Route length: 720.50
==================================================

============================================================================================================================
                                               DETAILED ALGORITHM COMPARISON                                                
============================================================================================================================
Algorithm            | Time (s) |  vs Best  | Length | vs Best | Params                                                     
----------------------------------------------------------------------------------------------------------------------------
Greedy v2            | 0.0016 | BEST | 720.50 | +24.86% |                                                            
Dynamic-gravity v2   | 0.0065 | +321.25%  | 577.06 | BEST | delta=0.5, fast_2opt_iter=100                              
Dynamic-gravity v1   | 0.0067 | +328.66%  | 582.13 | +0.88%  | delta=0.5, fast_2opt_iter=100                              
Angular-radial v2    | 0.0082 | +426.35%  | 658.16 | +14.05% | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
Angular-radial v1    | 0.0798 | +5035.05% | 658.16 | +14.05% | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
============================================================================================================================

PERFORMANCE ANALYSIS:
- Fastest algorithm(s): Greedy v2 (0.0016 sec)
- Shortest route(s): Dynamic-gravity v2 (577.06 units)

==================================================
          SMART TSP ALGORITHMS BENCHMARK          
==================================================
Points:           50
Seed:           123
Generation:     cluster
Post-opt:       OFF
Algorithms:    
  - Angular-radial v1: 
  - Angular-radial v2: 
  - Dynamic-gravity v1: 
  - Dynamic-gravity v2: 
  - Greedy v2: 
==================================================


==================================================
Running Angular-radial v1 algorithm...
Description: Angular-radial v1
Parameters: 
Completed in 0.0798 seconds
Route length: 519.29
==================================================

==================================================
Running Angular-radial v2 algorithm...
Description: Angular-radial v2
Parameters: 
Completed in 0.0081 seconds
Route length: 519.29
==================================================

==================================================
Running Dynamic-gravity v1 algorithm...
Description: Dynamic-gravity v1
Parameters: 
Completed in 0.0066 seconds
Route length: 495.87
==================================================

==================================================
Running Dynamic-gravity v2 algorithm...
Description: Dynamic-gravity v2
Parameters: 
Completed in 0.0066 seconds
Route length: 495.87
==================================================

==================================================
Running Greedy v2 algorithm...
Description: Classic greedy TSP algorithm
Parameters: 
Completed in 0.0015 seconds
Route length: 621.53
==================================================

============================================================================================================================
                                               DETAILED ALGORITHM COMPARISON                                                
============================================================================================================================
Algorithm            | Time (s) |  vs Best  | Length | vs Best | Params                                                     
----------------------------------------------------------------------------------------------------------------------------
Greedy v2            | 0.0015 | BEST | 621.53 | +25.34% |                                                            
Dynamic-gravity v2   | 0.0066 | +331.67%  | 495.87 | BEST | delta=0.5, fast_2opt_iter=100                              
Dynamic-gravity v1   | 0.0066 | +333.80%  | 495.87 | BEST | delta=0.5, fast_2opt_iter=100                              
Angular-radial v2    | 0.0081 | +431.08%  | 519.29 | +4.72%  | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
Angular-radial v1    | 0.0798 | +5150.37% | 519.29 | +4.72%  | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
============================================================================================================================

PERFORMANCE ANALYSIS:
- Fastest algorithm(s): Greedy v2 (0.0015 sec)
- Shortest route(s): Dynamic-gravity v1, Dynamic-gravity v2 (495.87 units)

==================================================
          SMART TSP ALGORITHMS BENCHMARK          
==================================================
Points:           100
Seed:           123
Generation:     random
Post-opt:       OFF
Algorithms:    
  - Angular-radial v1: 
  - Angular-radial v2: 
  - Dynamic-gravity v1: 
  - Dynamic-gravity v2: 
  - Greedy v2: 
==================================================


==================================================
Running Angular-radial v1 algorithm...
Description: Angular-radial v1
Parameters: 
Completed in 0.0812 seconds
Route length: 850.62
==================================================

==================================================
Running Angular-radial v2 algorithm...
Description: Angular-radial v2
Parameters: 
Completed in 0.0086 seconds
Route length: 850.62
==================================================

==================================================
Running Dynamic-gravity v1 algorithm...
Description: Dynamic-gravity v1
Parameters: 
Completed in 0.0071 seconds
Route length: 850.86
==================================================

==================================================
Running Dynamic-gravity v2 algorithm...
Description: Dynamic-gravity v2
Parameters: 
Completed in 0.0071 seconds
Route length: 856.14
==================================================

==================================================
Running Greedy v2 algorithm...
Description: Classic greedy TSP algorithm
Parameters: 
Completed in 0.0015 seconds
Route length: 1026.37
==================================================

=============================================================================================================================
                                                DETAILED ALGORITHM COMPARISON                                                
=============================================================================================================================
Algorithm            | Time (s) |  vs Best  |  Length | vs Best | Params                                                     
-----------------------------------------------------------------------------------------------------------------------------
Greedy v2            | 0.0015 | BEST | 1026.37 | +20.66% |                                                            
Dynamic-gravity v1   | 0.0071 | +367.32%  |  850.86 | +0.03%  | delta=0.5, fast_2opt_iter=100                              
Dynamic-gravity v2   | 0.0071 | +367.38%  |  856.14 | +0.65%  | delta=0.5, fast_2opt_iter=100                              
Angular-radial v2    | 0.0086 | +468.54%  | 850.62 | BEST | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
Angular-radial v1    | 0.0812 | +5243.04% | 850.62 | BEST | sort_by=angle_distance, look_ahead=100, max_2opt_iter=100  
=============================================================================================================================

PERFORMANCE ANALYSIS:
- Fastest algorithm(s): Greedy v2 (0.0015 sec)
- Shortest route(s): Angular-radial v1, Angular-radial v2 (850.62 units)

==================================================
          SMART TSP ALGORITHMS BENCHMARK          
==================================================
Points:           1001
Seed:           123
Generation:     random
Post-opt:       OFF
Algorithms:    
  - Angular-radial v1: 
  - Angular-radial v2: 
  - Dynamic-gravity v1: 
  - Dynamic-gravity v2: 
  - Greedy v2: 
==================================================


==================================================
Running Angular-radial v1 algorithm...
Description: Angular-radial v1
Parameters: 
Completed in 0.2555 seconds
Route length: 2545.21
==================================================

==================================================
Running Angular-radial v2 algorithm...
Description: Angular-radial v2
Parameters: 
Completed in 0.1346 seconds
Route length: 2545.21
==================================================

==================================================
Running Dynamic-gravity v1 algorithm...
Description: Dynamic-gravity v1
Parameters: 
Completed in 0.0321 seconds
Route length: 2837.78
==================================================

==================================================
Running Dynamic-gravity v2 algorithm...
Description: Dynamic-gravity v2
Parameters: 
Completed in 0.0186 seconds
Route length: 2726.36
==================================================

==================================================
Running Greedy v2 algorithm...
Description: Classic greedy TSP algorithm
Parameters: 
Completed in 0.0023 seconds
Route length: 2985.82
==================================================

================================================================================================================================
                                                 DETAILED ALGORITHM COMPARISON                                                  
================================================================================================================================
Algorithm            | Time (s) |  vs Best   |  Length | vs Best | Params                                                       
--------------------------------------------------------------------------------------------------------------------------------
Greedy v2            | 0.0023 | BEST | 2985.82 | +17.31% |                                                              
Dynamic-gravity v2   | 0.0186 |  +695.63%  | 2726.36 | +7.12%  | delta=0.5, fast_2opt_iter=1001                               
Dynamic-gravity v1   | 0.0321 | +1269.12%  | 2837.78 | +11.50% | delta=0.5, fast_2opt_iter=1001                               
Angular-radial v2    | 0.1346 | +5646.96%  | 2545.21 | BEST | sort_by=angle_distance, look_ahead=1001, max_2opt_iter=1001  
Angular-radial v1    | 0.2555 | +10808.60% | 2545.21 | BEST | sort_by=angle_distance, look_ahead=1001, max_2opt_iter=1001  
================================================================================================================================

PERFORMANCE ANALYSIS:
- Fastest algorithm(s): Greedy v2 (0.0023 sec)
- Shortest route(s): Angular-radial v1, Angular-radial v2 (2545.21 units)

Disclaimer: Performance results shown are for clustered/random distributions.
Results may vary based on spatial characteristics.
Always evaluate algorithms on your specific problem domains.

Back to Packages