🥮 mooncakes.io

    moonbit-vrp-solver

    Vehicle-routing heuristics in pure MoonBit, with CVRP and VRPTW support.

    vrp
    alns
    cvrp
    vrptw
    logistics
    wasm
    Download zip
    Version
    0.2.1
    License
    Apache-2.0
    Repository
    Last updated
    2 months ago
    Downloads
    30

    No dependencies

    #moonbit-vrp-solver

    Pure MoonBit heuristics for capacity-constrained vehicle routing (CVRP) and vehicle routing with time windows (VRPTW). The repository is both a reusable library and a small command-line application: data models, constraints, constructive heuristics, destroy/repair neighborhoods, local search, parsing, reports, and benchmark runners are available as separate MoonBit packages.

    #Checked quick start

    ///|
    test "README quick start" {
      let config = SolveConfig::default().tune(iterations=8)
      let result = solve(micro_cvrp_sample(), config~)
      assert_true(result.best().is_feasible())
      assert_true(result.completion_ratio() == 1.0)
    }

    #Core capabilities

    • CVRP and VRPTW models with private record representation and public accessors.
    • Euclidean, rounded Euclidean (EUC_2D), Manhattan, and Chebyshev distance metrics.
    • Capacity, time-window, duration, fleet-size, assignment, and route-integrity validation with structured diagnostics.
    • Clarke–Wright savings, nearest-neighbor, cheapest insertion, demand-first, radial, balanced, and deterministic generated-instance seeds.
    • ALNS with random, Shaw, worst, route, cluster, and time-critical destruction; greedy, regret-2, demand-first, and time-window repair; optional 2-opt, relocate, swap, reverse, local search, multi-start, portfolio, and simulated annealing drivers.
    • Strict CVRPLIB/TSPLIB CVRP parsing and Solomon-style VRPTW parsing.
    • Text, Markdown, CSV, compact route encoding, diagnostics, and ASCII route maps.
    • A traceable CVRPLIB Augerat A-n32-k5 fixture and reproducible benchmark CLI.

    #Quick start

    Install the current stable MoonBit toolchain, then run the built-in example:

    moon run cmd/main

    Select another bundled sample with VRP_SAMPLE:

    VRP_SAMPLE=small-cvrp moon run cmd/main

    Library usage:

    import "pqx123-lgtm/moonbit-vrp-solver" @vrp

    fn solve_demo {
      let instance = @vrp.micro_cvrp_sample()
      let config = @vrp.SolveConfig::default().tune(iterations=120)
      let result = @vrp.solve(instance, config~)
      println(@vrp.solution_text_detailed(result))
    }

    README.mbt.md contains the checked MoonBit quick-start example used by the MoonBit documentation workflow.

    #CLI

    The application entry point is cmd/main and prints a text solution report. The benchmark entry point is cmd/benchmark:

    moon run cmd/benchmark

    The benchmark command parses the embedded CVRPLIB A-n32-k5 text, runs the actual solver, and prints the known reference value, seed objective, best objective, gap, feasibility, route count, iterations, and elapsed milliseconds. Set VRP_BENCHMARK_ITERATIONS to change the iteration budget (the CLI clamps it to a safe range).

    #Architecture

    core/          models, distance matrices, constraints, validation, route edits
constructive/  seeds and construction strategy comparison
instance/      samples, deterministic generators, CVRPLIB/Solomon parsers
operators/     destruction, repair, relatedness, and neighborhood moves
search/        ALNS, local search, multi-start, portfolio, simulated annealing
report/        text, Markdown, CSV, diagnostics, and ASCII output
benchmark/     traceable benchmark fixture and result model
cmd/           thin CLI consumers of the public library

    The root package re-exports the stable application-facing API. Internal random number generation is kept under internal/rng; callers do not need to depend on implementation details.

    #Benchmark

    The repository includes benchmarks/A-n32-k5.vrp, a CVRPLIB Augerat Set A instance with 31 customers, five vehicles, capacity 100, rounded Euclidean distance, and published known value 784. The raw fixture and provenance are documented in benchmarks/README.md. Solver output is generated at run time; elapsed time and heuristic quality are not hard-coded as claims.

    For a longer report, run:

    moon run cmd/benchmark > benchmark-output.txt

    #Testing and quality checks

    moon update
moon fmt --check
moon info
moon check --target all --deny-warn
moon test --target all
moon build --target all
moon run cmd/main
moon run cmd/benchmark

    The test suite covers parser failures, empty and infeasible instances, duplicate assignments, time windows, deterministic generators, all major neighborhoods, solver reproducibility, report exports, and real benchmark execution. Build artifacts under _build/ are ignored and are not included in the source-size measurement.

    #CI and publishing

    GitHub Actions runs MoonBit checks on Ubuntu, macOS, and Windows using the current stable installer. It checks all targets, formatting, generated public interfaces, tests, builds, and the CLI. A separate manual workflow runs the benchmark, and a manual publish workflow runs prepublish checks before moon publish; credentials are supplied through the GitHub Actions secret and are never committed.

    #License

    Apache-2.0. See LICENSE. The project implementation is original MoonBit code. Algorithm families are credited in docs/source-notes.md, and benchmark data provenance is recorded separately so code, fixtures, generated files, and external references remain distinguishable.

    AnnealingConfig

    source

    Parameters for the optional simulated-annealing driver.

    AnnealingRun

    source

    BenchmarkCase

    source

    BenchmarkResult

    source

    CatalogEntry

    source

    Public metadata for the built-in examples and regression fixtures.

    ConstraintSummary

    source

    Aggregated route and assignment metrics suitable for dashboards and reports.

    CostBreakdown

    source

    Customer

    source

    Depot

    source

    DestroyOperator

    source

    DistanceMetric

    source

    Distance functions supported by the instance builder.

    FeasibilityAssessment

    source

    FeasibilityPolicy

    source

    Numerical policy used by integrations that need explicit tolerances.

    GeneratorConfig

    source

    Parameters for deterministic synthetic CVRP/VRPTW instances.

    ImprovementReport

    source

    LocalSearchConfig

    source

    Controls deterministic neighborhood improvement after construction or ALNS.

    MultiStartRun

    source

    Result of comparing several deterministic construction strategies.

    NeighborhoodKind

    source

    Neighborhoods implemented by the local improvement layer.

    ParseError

    source

    Errors returned when a benchmark instance is not structurally valid.

    PortfolioResult

    source

    Result of a solver portfolio run across construction and improvement modes.

    ProblemVariant

    source

    RelatednessWeights

    source

    Weights used when ranking related customers for destroy operators.

    RepairOperator

    source

    RouteEncodingError

    source

    Checked errors for the compact route exchange format.

    RouteMetrics

    source

    RoutePlan

    source

    RouteProfile

    source

    A normalized view of one route's resource consumption.

    SearchSummary

    source

    A compact convergence summary for CLI and benchmark output.

    Solution

    source

    SolveConfig

    source

    SolveResult

    source

    SolveStats

    source

    ValidationIssue

    source

    Structural and feasibility diagnostics for instances and solutions.

    ValidationReport

    source

    VehicleProfile

    source

    VrpInstance

    source

    a_n32_k5_case

    source

    a_n32_k5_text

    source
    let a_n32_k5_text : String

    Original benchmark text from the Augerat Set A CVRPLIB family.

    The fixture keeps the published node numbering, EUC_2D convention, vehicle capacity, and five-vehicle limit. It is parsed at runtime by the same parser that users can call for their own TSPLIB-compatible files.

    acceptance_probability

    source
    fn acceptance_probability(delta : Double, temperature : Double) -> Double

    Computes the Metropolis acceptance probability for a positive delta.

    all_sample_names

    source
    fn all_sample_names() -> Array[String]

    All built-in examples, including edge cases used by the test suite.

    analyze_instance

    source

    Computes demand, geometry, and time-window statistics in one pass.

    anneal

    source

    Runs a deterministic simulated-annealing search from a Clarke-Wright seed.

    ascii_route_map

    source
    fn ascii_route_map(instance : 
    VrpInstance    , solution : 
    Solution    , width : Int, height : Int) -> String

    Renders a dependency-free ASCII map for terminal demos and CI artifacts.

    ascii_route_map_with_legend

    source
    fn ascii_route_map_with_legend(instance : 
    VrpInstance    , solution : 
    Solution    , width : Int, height : Int) -> String

    Adds a legend to an ASCII map so routes remain identifiable in plain text.

    assess_solution

    source

    Evaluates a solution against a caller-provided tolerance policy.

    balanced_dispatch_sample

    source

    benchmark_header

    source
    fn benchmark_header(instance : 
    VrpInstance    , source : String, known_best : Double) -> String

    A short markdown benchmark header with explicit provenance fields.

    benchmark_result_markdown

    source
    fn benchmark_result_markdown(result : 
    SolveResult    , source : String, known_best : Double) -> String

    Produces a complete markdown section for one solver result.

    best_relocate

    source

    Searches all single-customer relocations and keeps the best strict improvement.

    best_reverse

    source

    Searches a complete route reversal neighborhood.

    best_swap

    source

    Searches all swaps between route positions and keeps the best improvement.

    build_route

    source

    build_solution

    source

    catalog_customer_total

    source
    fn catalog_customer_total() -> Int

    catalog_find

    source

    catalog_names

    source
    fn catalog_names() -> Array[String]

    catalog_overview

    source
    fn catalog_overview() -> String

    catalog_variant_count

    source

    clarke_wright_seed

    source

    decode_routes

    source

    Decodes the compact route format and assigns every omitted customer to the returned solution's unassigned list.

    demand_first_repair

    source

    Repairs large deliveries first, reducing late capacity failures.

    destroy_fraction

    source

    Removes a bounded fraction of assigned stops with a selected strategy.

    destroy_solution

    source

    encode_routes

    source

    Encodes routes as id,id;id,id, using external customer labels.

    feasible_insertions

    source

    generate_cvrp

    source

    Creates a deterministic CVRP instance for load testing and tutorials.

    generate_vrptw

    source

    Creates a deterministic Solomon-style VRPTW instance.

    generated_stress_sample

    source

    A moderate deterministic stress case generated from a documented seed.

    greedy_repair

    source

    infeasible_capacity_sample

    source

    A structurally valid but capacity-infeasible case for error-path tests.

    instance_fingerprint

    source
    fn instance_fingerprint(instance : 
    VrpInstance    ) -> String

    Produces a stable human-readable identity for regression fixtures.

    instance_overview

    source
    fn instance_overview(instance : 
    VrpInstance    ) -> String

    Returns a stable, one-line instance description for logs and benchmark tables.

    Performs bounded deterministic improvement and never accepts a worse solution.

    make_instance

    source

    make_instance_with_metric

    source

    Builds an instance with an explicit distance convention.

    micro_cvrp_sample

    source

    The smallest non-empty case, useful for embedding and smoke tests.

    parse_cvrp

    source

    Parses the CVRPLIB/TSPLIB CVRP text format.

    parse_instance

    source

    Parses either a CVRP or Solomon document based on its identifying headers.

    parse_solomon

    source

    Parses the Solomon 100-customer style VRPTW format.

    regret2_repair

    source

    relatedness_score

    source

    Scores two customers by spatial, demand, and temporal similarity.

    repair_solution

    source

    repair_until_stable

    source

    Repeatedly applies greedy repair until no unassigned count changes.

    repair_with_priority

    source

    Selects a repair order according to the structure of the instance.

    result_text

    source

    route_balance_score

    source

    Measures how evenly a solution uses its vehicle capacities.

    route_markdown

    source

    Produces a compact markdown table that can be pasted into a report.

    route_metrics_csv

    source

    Exports one row per route with the metrics needed by a spreadsheet.

    route_metrics_text

    source
    fn route_metrics_text(route : 
    RoutePlan    ) -> String

    Returns one line of route-level metrics for lightweight logging.

    route_profile

    source

    run_case

    source

    sample_by_name

    source

    sample_catalog

    source

    sample_names

    source
    fn sample_names() -> Array[String]

    small_cvrp_sample

    source

    solution_csv

    source

    Exports one row per route position for spreadsheet and plotting tools.

    solution_diagnostics

    source

    Renders resource utilization and validation status for a human report.

    solution_markdown

    source
    fn solution_markdown(result : 
    SolveResult    ) -> String

    solution_markdown_detailed

    source
    fn solution_markdown_detailed(result : 
    SolveResult    ) -> String

    Adds diagnostics and a route table to the existing markdown report.

    solution_report_bundle

    source
    fn solution_report_bundle(result : 
    SolveResult    , width : Int, height : Int) -> String

    Produces the report fragments commonly needed by a terminal application.

    solution_signature

    source

    Returns a stable route signature for equality/regression assertions.

    solution_text

    source

    solution_text_detailed

    source
    fn solution_text_detailed(result : 
    SolveResult    ) -> String

    Renders the same route metrics in a concise text block for CLI logs.

    solve

    source

    solve_portfolio

    source

    Evaluates a broad but bounded strategy portfolio and returns its best run.

    solve_with_seed

    source

    solve_with_strategies

    source

    Solves the same instance from several independent constructive seeds.

    Converts a solver result into stable, machine-readable metrics.

    summarize_solution

    source
    fn summarize_solution(result : 
    SolveResult    ) -> String

    tight_vrptw_sample

    source

    A deliberately tight VRPTW case for testing waiting and lateness logic.

    time_window_repair

    source

    Repairs tight time windows before relaxed deliveries.

    urban_vrptw_sample

    source

    validate_instance

    source

    Checks data invariants without running a solver.

    validate_solution

    source

    Checks that every customer is assigned exactly once or explicitly unassigned.

    variable_neighborhood_descent

    source

    Runs a bounded variable-neighborhood descent over the core move operators.

    Source Files

    Powered by MoonBit

    Site sourceReport issueModulesSkillsCLIBuild queueStatistics

    © 2026 mooncakes.io