pdp_lns 0.1.1

//! # pdp_lns
//!
//! Adaptive Large Neighbourhood Search (ALNS) solver for the
//! **Pickup and Delivery Problem with Time Windows (PDPTW)**.
//!
//! The solver combines several metaheuristic techniques:
//! - **Multi-start ensemble initialization** — four constructive heuristics
//!   run in parallel, seeding elite and route pools with diverse solutions.
//! - **LNS with adaptive operator selection** — destroy/repair operators
//!   weighted by recent performance (ALNS).
//! - **Guided Ejection Search (GES)** — vehicle-count minimization via
//!   ejection chains with squeeze and perturbation.
//! - **Set Covering (SC)** — MIP-based route recombination from a route pool.
//! - **Crossover operators** — CREX and SREX for elite pool exploitation.
//!
//! ## Quick start
//!
//! ```no_run
//! use pdp_lns::algorithm;
//! use pdp_lns::instance::Instance;
//! use std::path::Path;
//! use std::time::Duration;
//!
//! let inst = Instance::from_file(Path::new("instance.txt"));
//! let solution = algorithm::solve(&inst, Duration::from_secs(60), 42);
//! println!("Vehicles: {}, Distance: {:.2}",
//!     solution.num_vehicles(), solution.total_distance(&inst));
//! ```

// Pedantic lints that are too noisy for algorithmic / solver code
#![allow(
    clippy::similar_names,
    clippy::too_many_lines,
    clippy::too_many_arguments,
    clippy::inline_always,
    clippy::doc_markdown,
    clippy::must_use_candidate,
    clippy::return_self_not_must_use,
    clippy::cast_precision_loss,
    clippy::cast_possible_truncation,
    clippy::cast_possible_wrap,
    clippy::cast_sign_loss,
    clippy::items_after_statements,
    clippy::many_single_char_names,
    clippy::missing_panics_doc,
    clippy::missing_errors_doc,
    clippy::module_name_repetitions,
    clippy::struct_excessive_bools,
    clippy::float_cmp,
    clippy::if_not_else,
    clippy::match_same_arms,
    clippy::match_wildcard_for_single_variants,
    clippy::wildcard_imports
)]

use std::path::Path;
use std::time::Duration;

/// Top-level solver entry points and configuration.
pub mod algorithm;
/// Problem instance representation and I/O.
pub mod instance;
/// Solution representation, feasibility checks, and route utilities.
pub mod solution;

// Internal modules — not part of the public API.
pub(crate) mod arc_scoring;
pub(crate) mod crossover;
pub(crate) mod four_opt;
pub(crate) mod ges;
pub(crate) mod infeasible_tabu;
pub(crate) mod initial_construction;
pub(crate) mod lns;
pub(crate) mod local_search;
pub(crate) mod set_covering;
pub(crate) mod shaking;
pub(crate) mod special_opt;
pub(crate) mod two_k_opt;
pub(crate) mod vlsn;

use instance::Instance;
use solution::Solution;

#[cfg(feature = "python")]
fn parse_initial_method(raw: &str) -> Result<algorithm::InitialSolutionMethod, String> {
    algorithm::InitialSolutionMethod::from_str(raw).ok_or_else(|| {
        format!(
            "unknown initial_method '{raw}', expected one of: legacy, lu2006, ropke2006, cluster2004, hosny2012"
        )
    })
}

/// Solve a PDPTW instance from a file path. Returns the instance and best solution found.
pub fn solve_instance_core(
    instance_file: &str,
    initial_routes: Option<Vec<Vec<usize>>>,
    initial_method: algorithm::InitialSolutionMethod,
    time_limit_secs: u64,
    seed: u64,
) -> Result<(Instance, Solution), String> {
    std::panic::catch_unwind(move || -> Result<(Instance, Solution), String> {
        let inst = Instance::from_file(Path::new(instance_file));
        let initial = build_initial_solution(&inst, initial_routes)?;
        let best = algorithm::solve_with_initial_method(
            &inst,
            Duration::from_secs(time_limit_secs),
            seed,
            initial,
            initial_method,
            None,
        );
        Ok((inst, best))
    })
    .map_err(|_| "solver failed to run".to_string())?
}

/// Solve a PDPTW instance from raw arrays. Returns the instance and best solution found.
#[allow(clippy::too_many_arguments)]
pub fn solve_data_core(
    num_vehicles: usize,
    capacity: i32,
    demand: Vec<i32>,
    early: Vec<f64>,
    late: Vec<f64>,
    service: Vec<f64>,
    pair_delivery: Vec<usize>,
    dist_matrix: Vec<Vec<f64>>,
    coords: Option<Vec<(f64, f64)>>,
    initial_routes: Option<Vec<Vec<usize>>>,
    initial_method: algorithm::InitialSolutionMethod,
    time_limit_secs: u64,
    seed: u64,
) -> Result<(Instance, Solution), String> {
    let inst = Instance::from_raw(
        num_vehicles,
        capacity,
        demand,
        early,
        late,
        service,
        pair_delivery,
        dist_matrix,
        coords,
    )?;
    let initial = build_initial_solution(&inst, initial_routes)?;

    std::panic::catch_unwind(move || {
        let best = algorithm::solve_with_initial_method(
            &inst,
            Duration::from_secs(time_limit_secs),
            seed,
            initial,
            initial_method,
            None,
        );
        (inst, best)
    })
    .map_err(|_| "solver failed to run".to_string())
}

fn build_initial_solution(
    inst: &Instance,
    initial_routes: Option<Vec<Vec<usize>>>,
) -> Result<Option<Solution>, String> {
    match initial_routes {
        Some(routes) => Solution::from_routes(inst, routes).map(Some),
        None => Ok(None),
    }
}

#[cfg(feature = "python")]
use pyo3::exceptions::PyRuntimeError;
#[cfg(feature = "python")]
use pyo3::prelude::*;

#[cfg(feature = "python")]
#[pyclass]
pub struct SolveResult {
    #[pyo3(get)]
    pub vehicles: usize,
    #[pyo3(get)]
    pub distance: f64,
    #[pyo3(get)]
    pub feasible: bool,
    #[pyo3(get)]
    pub routes: Vec<Vec<usize>>,
    #[pyo3(get)]
    pub route_distances: Vec<f64>,
}

#[cfg(feature = "python")]
#[pymethods]
impl SolveResult {
    fn __repr__(&self) -> String {
        format!(
            "SolveResult(vehicles={}, distance={:.2}, feasible={})",
            self.vehicles, self.distance, self.feasible
        )
    }
}

#[cfg(feature = "python")]
fn to_py_result(inst: &Instance, best: &Solution) -> SolveResult {
    let route_distances = best
        .routes
        .iter()
        .map(|r| solution::route_distance(inst, r))
        .collect::<Vec<_>>();

    SolveResult {
        vehicles: best.num_vehicles(),
        distance: best.total_distance(inst),
        feasible: best.is_feasible(inst),
        routes: best.routes.clone(),
        route_distances,
    }
}

#[cfg(feature = "python")]
#[pyfunction(signature = (instance_file, initial_routes=None, initial_method="legacy", time_limit_secs=300, seed=42))]
pub fn solve_instance(
    instance_file: &str,
    initial_routes: Option<Vec<Vec<usize>>>,
    initial_method: &str,
    time_limit_secs: u64,
    seed: u64,
) -> PyResult<SolveResult> {
    let method = parse_initial_method(initial_method).map_err(PyRuntimeError::new_err)?;
    let (inst, best) =
        solve_instance_core(instance_file, initial_routes, method, time_limit_secs, seed)
            .map_err(PyRuntimeError::new_err)?;

    Ok(to_py_result(&inst, &best))
}

#[cfg(feature = "python")]
#[pyfunction(
    signature = (
        num_vehicles,
        capacity,
        demand,
        early,
        late,
        service,
        pair_delivery,
        dist_matrix,
        coords=None,
        initial_routes=None,
        initial_method="legacy",
        time_limit_secs=300,
        seed=42
    )
)]
#[allow(clippy::too_many_arguments)]
pub fn solve_data(
    num_vehicles: usize,
    capacity: i32,
    demand: Vec<i32>,
    early: Vec<f64>,
    late: Vec<f64>,
    service: Vec<f64>,
    pair_delivery: Vec<usize>,
    dist_matrix: Vec<Vec<f64>>,
    coords: Option<Vec<(f64, f64)>>,
    initial_routes: Option<Vec<Vec<usize>>>,
    initial_method: &str,
    time_limit_secs: u64,
    seed: u64,
) -> PyResult<SolveResult> {
    let method = parse_initial_method(initial_method).map_err(PyRuntimeError::new_err)?;
    let (inst, best) = solve_data_core(
        num_vehicles,
        capacity,
        demand,
        early,
        late,
        service,
        pair_delivery,
        dist_matrix,
        coords,
        initial_routes,
        method,
        time_limit_secs,
        seed,
    )
    .map_err(PyRuntimeError::new_err)?;

    Ok(to_py_result(&inst, &best))
}

#[cfg(feature = "python")]
#[pymodule]
fn pdp_lns(m: &Bound<'_, PyModule>) -> PyResult<()> {
    m.add_class::<SolveResult>()?;
    m.add_function(wrap_pyfunction!(solve_instance, m)?)?;
    m.add_function(wrap_pyfunction!(solve_data, m)?)?;
    Ok(())
}

#[cfg(test)]
mod tests {
    use super::solve_data_core;
    use crate::algorithm::InitialSolutionMethod;

    type TinyRawData = (
        usize,
        i32,
        Vec<i32>,
        Vec<f64>,
        Vec<f64>,
        Vec<f64>,
        Vec<usize>,
        Vec<Vec<f64>>,
        Option<Vec<(f64, f64)>>,
    );

    fn tiny_raw() -> TinyRawData {
        (
            1,
            10,
            vec![0, 4, -4],
            vec![0.0, 0.0, 0.0],
            vec![1000.0, 1000.0, 1000.0],
            vec![0.0, 0.0, 0.0],
            vec![0, 2, 0],
            vec![
                vec![0.0, 1.0, 2.0],
                vec![1.0, 0.0, 1.0],
                vec![2.0, 1.0, 0.0],
            ],
            None,
        )
    }

    #[test]
    fn solve_data_core_uses_initial_routes() {
        let (
            num_vehicles,
            capacity,
            demand,
            early,
            late,
            service,
            pair_delivery,
            dist_matrix,
            coords,
        ) = tiny_raw();

        let (inst, best) = solve_data_core(
            num_vehicles,
            capacity,
            demand,
            early,
            late,
            service,
            pair_delivery,
            dist_matrix,
            coords,
            Some(vec![vec![0, 1, 2, 0]]),
            InitialSolutionMethod::Legacy,
            0,
            42,
        )
        .expect("valid initial routes");

        assert!(best.unassigned.is_empty());
        assert!(best.is_feasible(&inst));
    }

    #[test]
    fn solve_data_core_rejects_invalid_initial_routes() {
        let (
            num_vehicles,
            capacity,
            demand,
            early,
            late,
            service,
            pair_delivery,
            dist_matrix,
            coords,
        ) = tiny_raw();

        let err = solve_data_core(
            num_vehicles,
            capacity,
            demand,
            early,
            late,
            service,
            pair_delivery,
            dist_matrix,
            coords,
            Some(vec![vec![0, 2, 1, 0]]),
            InitialSolutionMethod::Legacy,
            0,
            42,
        )
        .err()
        .expect("invalid initial routes should return error");

        assert!(err.contains("route 0"));
    }
}