rmp-route-optimizer 0.1.0

# RMP Route Optimizer

[![Crates.io](https://img.shields.io/crates/v/rmp-route-optimizer.svg)](https://crates.io/crates/rmp-route-optimizer)
[![Documentation](https://docs.rs/rmp-route-optimizer/badge.svg)](https://docs.rs/rmp-route-optimizer)
[![License](https://img.shields.io/crates/l/rmp-route-optimizer.svg)](https://github.com/trashroute/rmp-route-optimizer#license)

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`:

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

## Quick Start

```rust
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:

```rust
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:

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

### Street Sweeping

Plan efficient street cleaning routes:

```rust
// 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:

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

## Features Flags

```toml
[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:

```bash
cargo run --example simple_route
cargo run --example waste_collection
```

## Testing

Run the test suite:

```bash
cargo test
```

Run with logging:

```bash
RUST_LOG=debug cargo test -- --nocapture
```

## Contributing

Contributions are welcome! Please:

1. Fork the repository
2. Create a feature branch
3. Add tests for new functionality
4. Ensure all tests pass
5. Submit a pull request

## License

Licensed under either of:

- Apache License, Version 2.0 ([LICENSE-APACHE](LICENSE-APACHE))
- MIT license ([LICENSE-MIT](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

## Links

- [Documentation](https://docs.rs/rmp-route-optimizer)
- [Repository](https://github.com/trashroute/rmp-route-optimizer)
- [Issue Tracker](https://github.com/trashroute/rmp-route-optimizer/issues)
- [Crates.io](https://crates.io/crates/rmp-route-optimizer)

## Support

For questions and support:

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