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

This is achieved through:

• Avoiding expensive sqrt() operations in the main loop
• Smarter heuristics that build better routes from the start
• Efficient 2-opt optimization with limited search window

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.

📖 Learn more about PCH research

# 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

Publishing:

# Login to crates.io (one time)
cargo login

# Publish new version
# 1. Update version in Cargo.toml
# 2. Run:
cargo publish

# Create and push git tag
git tag v0.1.0
git push origin v0.1.0

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