pdp_lns 0.1.1

# PDP-LNS

A Rust solver for the Pickup and Delivery Problem with Time Windows (PDPTW), focused on Li & Lim benchmark instances.

The project combines Large Neighborhood Search (LNS), Guided Ejection Search (GES), and local improvement operators to build high-quality feasible routes under time and capacity constraints.

## Features

- Fast CLI solver for PDPTW instances
- Hybrid search pipeline with multiple neighborhood operators
- Benchmark automation script with optional BKS download and comparison
- Built-in feasibility checks and route-level reporting

## Project Layout

- `src/`: solver implementation (instance parsing, neighborhoods, local search, LNS/GES orchestration)
- `instances/`: benchmark instance files and best-known solutions tables
- `src/bin/benchmark_lilim.rs`: batch benchmark runner and summary generator
- `benchmark_results/`: optional local benchmark outputs (generated, not versioned)

## Requirements

- Rust toolchain (stable, Rust 1.87+)
- Python 3.9+ (only for Python bindings)

## Quick Start

Build release binary:

```bash
cargo build --release
```

Run solver:

```bash
target/release/pdp_lns instances/lrc101.txt 300 42
```

Arguments:

- `instance_file`: path to Li & Lim instance
- `time_limit_secs`: optional time limit in seconds (default: `300`)
- `seed`: optional RNG seed (default: `42`)
- `initial_method`: optional initial solution method: `legacy` (old behavior), `lu2006` (Lu&Dessouky 2006), `ropke2006` (Ropke&Pisinger 2006 sequential insertion), `cluster2004` (cluster-paper embedded insertion), or `hosny2012` (2012 PBQ best-request constructor), default `legacy`

Example with Lu&Dessouky initial construction:

```bash
target/release/pdp_lns instances/lrc101.txt 300 42 lu2006
```

Runtime flags (environment variables):

- `BNB_REPAIR_ENABLE=0|1`: disable/enable branch-and-bound repair inside LNS (default: enabled).

## Python Package

Install locally:

```bash
pip install -e .
```

Use with raw data (without instance files):

```python
import pdp_lns

result = pdp_lns.solve_data(
    num_vehicles=2,
    capacity=10,
    demand=[0, 4, -4],
    early=[0.0, 0.0, 0.0],
    late=[1000.0, 1000.0, 1000.0],
    service=[0.0, 0.0, 0.0],
    pair_delivery=[0, 2, 0],
    dist_matrix=[
        [0.0, 1.0, 2.0],
        [1.0, 0.0, 1.0],
        [2.0, 1.0, 0.0],
    ],
    # optional coordinates for CLP term in Lu&Dessouky construction
    coords=[(0.0, 0.0), (1.0, 0.0), (2.0, 0.0)],
    # optional warm start (routes must be depot-bookended and feasible)
    initial_routes=[[0, 1, 2, 0]],
    # optional switch between initial builders: "legacy" | "lu2006"
    initial_method="legacy",
    time_limit_secs=30,
    seed=42,
)

print(result.vehicles, result.distance, result.feasible)
```

## Benchmarking

Run a benchmark group in parallel:

```bash
cargo run --release --bin benchmark_lilim -- --groups LRC2 --time-limit 60 --jobs 8
```

Examples:

```bash
# Run all discovered instances
cargo run --release --bin benchmark_lilim -- --groups ALL

# Run selected instances only
cargo run --release --bin benchmark_lilim -- --instances lrc101 LR1_4_1

# Fixed seed for all jobs
cargo run --release --bin benchmark_lilim -- --groups ALL_BKS --seed-mode fixed

# Use Lu&Dessouky 2006 initial construction
cargo run --release --bin benchmark_lilim -- --groups LR1 --initial-method lu2006
```

## Development

Useful local checks:

```bash
cargo fmt --all
cargo check --all-targets
cargo clippy --all-targets -- -D warnings
cargo test
```

Release workflow checklist: see `PUBLISHING.md`.

## Reproducibility Notes

- Results depend on time limit, machine, and seed.
- Benchmark script supports fixed seeds and offset seeds for parallel runs.
- The repository contains generated benchmark artifacts; refresh them when reporting new results.

## License

This project is released under the MIT License. See `LICENSE`.

## Community

- Contribution guide: `CONTRIBUTING.md`
- Code of conduct: `CODE_OF_CONDUCT.md`
- Security reporting: `SECURITY.md`
- Citation metadata: `CITATION.cff`

## Acknowledgments

- Li & Lim PDPTW benchmark instances
- SINTEF TOP PDPTW benchmark pages and best-known solutions