RMP Route Optimizer

A high-performance route optimization library for waste collection, logistics, and delivery services using Eulerian circuit algorithms.

Features

Eulerian Circuit Optimization: Solves the Chinese Postman Problem for efficient route planning
Geographic Awareness: Uses Haversine distance for accurate real-world routing
Side-of-Street Routing: Supports pickup side constraints (left/right/either)
Graph Augmentation: Automatically adds edges to make graphs Eulerian
High Performance: Optimized Rust implementation with minimal allocations
Zero-copy Serialization: Efficient data structures with serde support

Installation

Add this to your Cargo.toml:

[dependencies]
rmp-route-optimizer = "0.1.0"

Quick Start

use rmp_route_optimizer::{RouteOptimizer, Node, Edge, PickupSide};

fn main() {
    // Create nodes (locations)
    let nodes = vec![
        Node::new(1, 40.7128, -74.0060),  // New York
        Node::new(2, 40.7138, -74.0070),
        Node::new(3, 40.7148, -74.0080),
    ];

    // Create edges (roads)
    let edges = vec![
        Edge::new(1, 2, 100.0, false, PickupSide::Either),
        Edge::new(2, 3, 100.0, false, PickupSide::Either),
        Edge::new(3, 1, 100.0, false, PickupSide::Either),
    ];

    // Optimize route
    let optimizer = RouteOptimizer::new(nodes, edges);
    let circuit = optimizer.optimize_eulerian(1, false).unwrap();

    println!("Optimized route: {:?}", circuit.nodes);
    println!("Total cost: {:.2} meters", circuit.total_cost);
    println!("Augmenting edges: {}", circuit.augmenting_edges);
}

Use Cases

Waste Collection

Optimize garbage truck routes to minimize fuel consumption and time:

use rmp_route_optimizer::{RouteOptimizer, Node, Edge, PickupSide};

// Define collection points
let collection_points = vec![
    Node::new(1, 40.7128, -74.0060),
    Node::new(2, 40.7138, -74.0070),
    // ... more points
];

// Define streets with pickup sides
let streets = vec![
    Edge::new(1, 2, 150.0, false, PickupSide::Right),
    // ... more streets
];

let optimizer = RouteOptimizer::new(collection_points, streets);
let route = optimizer.optimize_eulerian(1, true).unwrap();

Delivery Services

Optimize package delivery routes:

// Similar setup but with delivery locations
let route = optimizer.optimize_eulerian(depot_id, false).unwrap();

Street Sweeping

Plan efficient street cleaning routes:

// Use PickupSide::Either for street sweeping
let streets = vec![
    Edge::new(1, 2, 200.0, false, PickupSide::Either),
];

API Overview

Core Types

Node: Geographic location with ID, latitude, and longitude
Edge: Road segment connecting two nodes with cost and constraints
PickupSide: Enum for side-of-street constraints (Left/Right/Either)
EulerianCircuit: Optimized route result with nodes, edges, and total cost

Main API

RouteOptimizer::new(nodes, edges): Create optimizer instance
optimize_eulerian(start_node, enforce_right_side): Find optimal route
haversine_distance(node1, node2): Calculate geographic distance

Performance

Typical performance on modern hardware:

Small graphs (10-50 nodes): <10ms
Medium graphs (50-200 nodes): 10-100ms
Large graphs (200-1000 nodes): 100ms-1s
Memory usage: ~200-500MB for typical workloads

Algorithm Details

The library implements the Chinese Postman Problem solution:

Graph Construction: Build directed/undirected graph from nodes and edges
Eulerian Check: Verify if all vertices have even degree
Graph Augmentation: Add minimum-weight edges to make graph Eulerian
Circuit Finding: Use Hierholzer's algorithm to find Eulerian circuit
Cost Calculation: Sum edge costs along the circuit

Features Flags

[dependencies]
rmp-route-optimizer = { version = "0.1.0", features = ["async", "logging"] }

async: Enable async/await support with Tokio
logging: Enable tracing integration for debugging

Examples

See the examples/ directory for more:

simple_route.rs - Basic route optimization
waste_collection.rs - Real-world waste collection scenario

Run examples:

cargo run --example simple_route
cargo run --example waste_collection

Testing

Run the test suite:

cargo test

Run with logging:

RUST_LOG=debug cargo test -- --nocapture

Contributing

Contributions are welcome! Please:

Fork the repository
Create a feature branch
Add tests for new functionality
Ensure all tests pass
Submit a pull request

License

Licensed under either of:

Apache License, Version 2.0 (LICENSE-APACHE)
MIT license (LICENSE-MIT)

at your option.

Acknowledgments

Based on research in graph theory and the Chinese Postman Problem
Inspired by real-world waste collection optimization needs
Built with Rust for performance and safety

Support

For questions and support:

Open an issue on GitHub
Email: dev@rmp.ca
Website: https://rmp.ca

rmp-route-optimizer 0.1.0