A core crate contains main buildings blocks for constructing heuristics and metaheuristic
to solve rich
Vehicle Routing Problem.
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-scientificcrate supports VRP variations used in scientific benchmarks
vrp-pragmaticcrate supports custom json format which can be used to model real world scenarios
vrp-clicrate 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,
user guide documentation.
Model definitions can be split into three groups:
commongroup contains common models: time-specific, location, distance, etc.
problemgroup contains VRP definition models: job, vehicle, cost-specific, etc.
solutiongroup contains models which used to represent a VRP solution: route, tour, activity, etc.
Check corresponding modules for details.
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
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
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::solver::Builder; use vrp_core::models::Problem; use vrp_core::utils::Environment; // create your VRP problem let problem = create_example_problem(); let environment = Arc::new(Environment::default()); // build solver to run 10 secs or 1000 generation let solver = Builder::new(problem, environment) .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);
A collection of reusable algorithms without dependencies on any other module in the project.
This module contains building blocks for constructive heuristics.
A collection of models to represent problem and solution in Vehicle Routing Problem domain.
The solver module contains basic building blocks for a metaheuristic among with the default implementation.
A collection of various utility helpers.