smart-dynamic-gravity-tsp-rs

• Dynamic Gravity Algorithm — Physics-inspired heuristic with inertia and angle penalty
• Near-optimal solutions — ~3.0% better than classical greedy on 1000 cities
• Fast execution — ~0.082s for 1000 cities (110x faster than greedy)
• 2-opt optimization — Optional post-processing for improved solutions
• Simple API — Easy to integrate into your projects
• No dependencies — Only uses Rust standard library

Dynamic Gravity — A novel physics-inspired heuristic that simulates attraction and inertia:

• Inertia mechanism — Maintains directional memory for smoother routes
• Angle penalty — Penalizes sharp turns for more natural paths
• 2-opt optimization — Post-processing for improved solutions

Parameters:

Benchmark: 1000 Cities (Random Distribution)

Key insight: Both algorithms have O(n²) complexity, but Dynamic Gravity is 110x faster while also producing better quality solutions (3.0% improvement).

Add to your Cargo.toml:

[dependencies]
smart-dynamic-gravity-tsp = "0.1"

use smart_dynamic_gravity_tsp::{City, dynamic_gravity_solve};

let cities = vec![
    City { x: 0.0, y: 0.0 },
    City { x: 1.0, y: 0.0 },
    City { x: 0.0, y: 1.0 },
    City { x: 1.0, y: 1.0 },
];

let (distance, path) = dynamic_gravity_solve(
    &cities,
    0.9,    // inertia coefficient (0.0-1.0)
    true,   // enable 2-opt optimization
    100,    // 2-opt iterations
    0.3,    // angle penalty weight (0.0-1.0)
    true,   // use angle penalty
    50,     // 2-opt search window
);

println!("Distance: {:.2}", distance);
println!("Path: {:?}", path);

This library is part of the NP Problem Ecosystem — a comprehensive suite of exact and heuristic solvers for the Traveling Salesman Problem:

All projects are grounded in the Position-Candidate-Hypothesis (PCH) paradigm for NP-complete problems.

# Clone repository
git clone https://github.com/smartlegionlab/smart-dynamic-gravity-tsp-rs
cd smart-dynamic-gravity-tsp-rs

# Build
cargo build

# Run tests
cargo test

# Run examples
cargo run --example basic --release
cargo run --example compare --release

# Run benchmarks
cargo bench

# Build documentation
cargo doc --open

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