#vrp #optimization

vrp-core

A core algorithms to solve a Vehicle Routing Problem

29 stable releases

new 1.6.2 Oct 18, 2020
1.6.1 Oct 15, 2020
1.5.7 Sep 29, 2020
1.4.2 Aug 20, 2020
1.1.0 Apr 27, 2020

#113 in Algorithms

Download history 113/week @ 2020-06-28 61/week @ 2020-07-05 42/week @ 2020-07-12 34/week @ 2020-07-19 50/week @ 2020-07-26 21/week @ 2020-08-02 48/week @ 2020-08-09 38/week @ 2020-08-16 13/week @ 2020-08-23 43/week @ 2020-08-30 129/week @ 2020-09-06 74/week @ 2020-09-13 63/week @ 2020-09-20 105/week @ 2020-09-27 42/week @ 2020-10-04 39/week @ 2020-10-11

231 downloads per month
Used in 4 crates

Apache-2.0

360KB
7.5K SLoC

Description

The core crate contains main buildings blocks for constructing heuristics and metaheuristic to solve rich Vehicle Routing Problem.

Please check the repository for more details.


lib.rs:

A core crate contains main buildings blocks for constructing heuristics and metaheuristic to solve rich Vehicle Routing Problem.

Key points

A basic idea of the core crate is to design a library which can be used to solve multiple variations of Vehicle Routing Problem (VRP) known also as a rich VRP. In order to achieve that, it defines essential domain models and implements default metaheuristic with preconfigured properties.

Another goal is an intuitive design: it should be relatively easy to start using it without prior knowledge of the domain. That's why the API design does not try to generalize models and implementations in order to develop a general purpose metaheuristic.

Extra functionality, already developed on top of this crate, is available via following crates:

  • vrp-scientific crate supports VRP variations used in scientific benchmarks
  • vrp-pragmatic crate supports custom json format which can be used to model real world scenarios
  • vrp-cli crate provides a command line interface and static library with all available functionality provided by the project

Meanwhile, the project tries to keep the list of dependencies relatively small, but "Not invented HERE" syndrome should be also avoided.

The next sections explain some basic concepts such as types used to model VRP definition, constructive heuristics, metaheuristic, etc. Start exploring them, if you are curious about internal implementation or library extension. It you are looking just for user documentation, check! the user guide documentation.

Modeling VRP

Model definitions can be split into three groups:

  • common group contains common models: time-specific, location, distance, etc.
  • problem group contains VRP definition models: job, vehicle, cost-specific, etc.
  • solution group contains models which used to represent a VRP solution: route, tour, activity, etc.

Check corresponding modules for details.

Constructive heuristic

A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends it until a complete solution is obtained.

The crate implements various constructive heuristics in construction module.

Metaheuristic

A metaheuristic is a high-level algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. One of its goals is to guide the search process towards optimal solution.

See more details about it in solver module.

Examples

The most simple way to run solver is to use Builder. You can tweak metaheuristic parameters by calling corresponding methods of the builder instance:

# use vrp_core::models::examples::create_example_problem;
# use std::sync::Arc;
use vrp_core::solver::Builder;
use vrp_core::models::Problem;

// create your VRP problem
let problem: Arc<Problem> = create_example_problem();
// build solver to run 10 secs or 1000 generation
let solver = Builder::new(problem)
    .with_max_time(Some(10))
    .with_max_generations(Some(1000))
    .build()?;
// run solver and get the best known solution within its cost.
let (solution, cost, _) = solver.solve()?;

assert_eq!(cost, 42.);
assert_eq!(solution.routes.len(), 1);
assert_eq!(solution.unassigned.len(), 0);
# Ok::<(), String>(())

Dependencies

~2.5MB
~47K SLoC