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

pdp_lns 0.1.1