Description

This project provides a way to solve multiple variations of Vehicle Routing Problem known as rich VRP. It provides custom hyper- and meta-heuristic implementations, shortly described here.

If you use the project in academic work, please consider citing:

@misc{builuk_rosomaxa_2023,
    author       = {Ilya Builuk},
    title        = {{A new solver for rich Vehicle Routing Problem}},
    year         = 2023,
    doi          = {10.5281/zenodo.4624037},
    publisher    = {Zenodo},
    url          = {https://doi.org/10.5281/zenodo.4624037}
}

Design goal

Although performance is constantly in focus, the main idea behind design is extensibility: the project aims to support a wide range of VRP variations known as Rich VRP. This is achieved through various extension points: custom constraints, objective functions, acceptance criteria, etc.

Getting started

For general installation steps and basic usage options, please check the next sections. More detailed overview of the features and full description of the usage is presented in A Vehicle Routing Problem Solver Documentation.

Probably, the easiest way to learn how to use the solver as is, would be to play with interactive tutorial, written as jupyter notebook.

Additionally, you can check vrp-core/examples to see how to use the library and extend it within a new functionality.

Installation

You can install the latest release of the vrp solver in several different ways:

Install with Python

The functionality of vrp-cli is published to pypi.org, so you can just install it using pip and use from python:

pip install vrp-cli
python examples/python-interop/example.py # run test example

The package ships typed pydantic models for every document the solver exchanges as vrp_cli.models, generated from the solver's own rust types, so there is no need to write them by hand:

import vrp_cli
from vrp_cli.models.config import Config, TerminationConfig
from vrp_cli.models.problem import Fleet, Plan, Problem
from vrp_cli.models.solution import Solution

problem = Problem(plan=Plan(jobs=[...]), fleet=Fleet(vehicles=[...], profiles=[...]))
config = Config(termination=TerminationConfig(maxTime=5))

solution = Solution.model_validate_json(
    vrp_cli.solve_pragmatic(
        problem=problem.model_dump_json(exclude_none=True),
        matrices=[],
        config=config.model_dump_json(exclude_none=True),
    )
)
print(solution.statistic.cost)

Alternatively, you can use maturin tool to build solver locally.

Additionally, to jupyter notebook mentioned above, you can find extra information in python example section of the docs. The full source code of python example is available in the repo.

Use from Javascript

The solver runs as WebAssembly in a browser or in node. There is no npm package: either grab vrp_cli_wasm.zip from the latest release, which is a --target web build ready for browsers, or build the target you need locally:

pip install -r vrp-cli/bindings/python/requirements-codegen.txt
npm ci --prefix vrp-cli/bindings/typescript
./vrp-cli/bindings/generate.sh
cd vrp-cli
wasm-pack build --target web                        # browsers
wasm-pack build --target nodejs --out-dir pkg-node  # node

Calls take plain javascript objects and hand them back, and a typed vrp_cli.d.ts is generated next to the package, so typescript callers get completion and type checking without writing any definitions:

import { createRequire } from 'node:module';

// wasm-pack's output, resolved relative to this file
const vrp = createRequire(import.meta.url)('./pkg-node/vrp_cli.js');

const problem = { plan: { jobs: [/* ... */] }, fleet: { vehicles: [/* ... */], profiles: [/* ... */] } };

// passing no matrices lets the solver approximate distances
const solution = vrp.solve_pragmatic(problem, [], { termination: { maxTime: 5 } });
console.log(solution.statistic.cost);

Failures throw an Error whose message is a json array of { code, cause, action } entries. Node 19 or newer is required, since the solver seeds its random number generator from the Web Crypto API.

For a complete runnable version see examples/js-interop and the javascript example section of the docs.

Install from Docker

Another fast way to try vrp solver on your environment is to use docker image (not performance optimized):

• run public image from Github Container Registry:

    docker run -it -v $(pwd):/repo --name vrp-cli --rm ghcr.io/reinterpretcat/vrp/vrp-cli:1.26.0

• build image locally using Dockerfile provided:

docker build -t vrp_solver .
docker run -it -v $(pwd):/repo --rm vrp_solver

Please note that the docker image is built using musl, not glibc standard library. So there might be some performance implications.

Install from Cargo

You can install vrp solver cli tool directly with cargo install:

cargo install vrp-cli

Ensure that your $PATH is properly configured to source the crates binaries, and then run solver using the vrp-cli command.

Install from source

Once pulled the source code, you can build it using cargo:

cargo build --release

Built binaries can be found in the ./target/release directory and can be run using vrp-cli executable, e.g.:

./target/release/vrp-cli solve solomon examples/data/scientific/solomon/C101.100.txt --log

Alternatively, you can try to run the following script from the project root (with pragmatic format only):

./solve_problem.sh examples/data/pragmatic/objectives/berlin.default.problem.json

It will build the executable and automatically launch the solver with the specified VRP definition. Results are stored in the folder where a problem definition is located.

Please note, that master branch normally contains not yet released changes.

Usage

Using from code

If you're using rust, you have multiple options for how the project can be used:

Use customization capabilities

The vrp-core provides API to compose a VRP formulation from various building blocks and even add your own. Start with basic vrp-core/examples, then check the user documentation and code for more details.

Use built-in formats

You can use vrp-scientific, vrp-pragmatic crates to solve a VRP problem defined in pragmatic or scientific format using default metaheuristic. Or you can use CLI interface for that (see below).

If you're using some other language, e.g. java, kotlin, javascript, python, please check interop section in documentation examples to see how to call the library from it (currently, limited to pragmatic format).

Using from command line

vrp-cli crate is designed to use on problems defined in scientific or custom json (aka pragmatic) format:

vrp-cli solve pragmatic problem_definition.json -m routing_matrix.json --max-time=120

Please refer to getting started section in the documentation for more details.

Contribution policy

open source, limited contribution

The goal is to reduce burnout by limiting the maintenance overhead of reviewing and validating third-party code.

Please submit an issue or discussion if you have ideas for improvement.

Status

Permanently experimental. This is my pet project, and I'm not paid for it, so expect a very limited support.