smart-tsp-solver ^v1.0.1

• 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 — O(n²)

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: Predictable execution time, consistently high solution quality, efficient cluster traversal
• Ideal Use Case: The balance of speed and quality, processing medium-sized datasets

Angular-Radial Method — O(n²) with near O(n·log n) practical performance

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.

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

Hierarchical TSP Solver

A TSP solver using hierarchical decomposition and metaheuristics. Core philosophy: Divide-and-Conquer with Geometric Intelligence.

• 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

*Practical performance approaches O(n·log n) due to spatial heuristics.

pip install smart-tsp-solver

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()

Local Development:

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

100 points (cluster):

==================================================
          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... Completed in 0.0848s, Length: 553.66
Running Angular-radial v2... Completed in 0.0082s, Length: 553.66
Running Dynamic-gravity v1... Completed in 0.0070s, Length: 567.00
Running Dynamic-gravity v2... Completed in 0.0067s, Length: 534.90
Running Greedy v2... Completed in 0.0016s, Length: 609.21
Running Hierarchical TSP... Completed in 0.0343s, 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
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
============================================================================================================================

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

50 points (random):

Points: 50 | Generation: random
Fastest: Greedy v2 (0.0016 sec)
Shortest: Dynamic-gravity v2 (577.06 units)

1001 points (random):

Points: 1001 | Generation: random
Fastest: Greedy v2 (0.0023 sec)
Shortest: Angular-radial v1, Angular-radial v2 (2545.21 units)

• Exact TSP Solutions (TSP ORACLE) — Optimal solutions for small instances
• Smart TSP Benchmark — Professional algorithm testing infrastructure
• Position-Candidate-Hypothesis (PCH) Paradigm — A New Research Direction for NP-Complete Problems
• Spatial Optimization: Computational geometry approaches for large-scale problems
• Heuristic Analysis: Comparative study of modern TSP approaches

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

By using this software, you agree to the full disclaimer terms.

Software provided "AS IS" without warranty. You assume all risks.

Full legal disclaimer: See DISCLAIMER.md

License: BSD 3-Clause License

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