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:

cargo build --release

Run solver:

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:

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:

pip install -e .

Use with raw data (without instance files):

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:

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

Examples:

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

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