Module solver

The solver module contains basic building blocks for a metaheuristic among with the default implementation.

Metaheuristic

A metaheuristic is a high-level algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. Examples of metaheuristics include genetic/evolutionary algorithms, tabu search, simulated annealing, variable neighborhood search, (adaptive) large neighborhood search, ant colony optimization, etc.

Multi-objective decision maker

Most VRPs, frequently used to model real cases, are set up with a single objective (e.g. minimizing the cost of the solution), however the majority of the problems encountered in logistics industry, are multi-objective in nature as the complexity of real-life logistics planning often cannot be reduced to cost only. Such non-cost factors are:

• balancing work across multiple workers
• minimization or maximization of fleet usage
• minimization of unassigned jobs

In most of the cases, these additional factors are contradicting to the cost minimization objective which, in fact, leads to nontrivial multi-objective optimization problem, where no single solution exists that simultaneously optimizes each objective.

Evolutionary algorithm

An evolutionary algorithm (EA) is a generic population-based metaheuristic optimization algorithm. This crate provides a custom implementation of EA which can be divided into the following steps:

• initialization: on this step, an initial population is created using different construction heuristics.
• main loop begin: enter an evolution loop
  • selection: an individual is selected from population. Best-fit individuals have more chances to be selected.
  • mutation: a mutation operator is applied to selected individual. Default implementation uses ruin and recreate principle described in next section.
  • population adjustments: new individual is added to population, then the population is sorted and shrinked to keep it under specific size limits with best-fit individuals and some intermediate.
• main loop end: exit evolution loop when one of termination criteria are met. See termination module for details.

As there is no crossover operator involved and offspring is produced from one parent, this algorithm can be characterized as parthenogenesis based EA. This approach eliminates design of feasible crossover operator which is a challenging task in case of VRP.

Population

A custom algorithm is implemented to maintain diversity and guide the search maintaining trade of between exploration and exploitation of solution space. See rosomaxa crate for details.

Ruin and Recreate principle

A ruin and recreate principle is introduced by Schrimpf et al. (2000) and key idea here is to ruin a quite large fraction of the solution and try to restore the solution as best as it is possible in order to get a new solution better than the previous one. Original algorithm can be described as a large neighborhood search that combines elements of simulated annealing and threshold-accepting algorithms, but this crate only reuses ruin/recreate idea as a mutation operator.

Additionally..

The solver is not limited by R&R principle, additionally it utilizes some other heuristics and their combinations. They are picked based on their performance in terms of search quality and latency introduced. Reinforcement technics are used here.

Modules

processing

Contains pre and post processing logic.

search

The mutation module specifies building blocks for mutation operator used by evolution.

Structs

RecreateInitialOperator

Wraps recreate method as InitialOperator

RefinementContext

A type which encapsulates information needed to perform solution refinement process.

Solver

Solves a Vehicle Routing Problem and returns a (solution, its cost) pair in case of success or error description, if solution cannot be found.

VrpConfigBuilder

Provides the way to get ProblemConfigBuilder with reasonable defaults for VRP domain.

Enums

RefinementSpeed

Defines instant refinement speed type.

Traits

HeuristicFilterExtraProperty

Extends Extras within a new HeuristicFilterExtraProperty.

SolutionWeightsSolutionState

Extends SolutionState within a new SolutionWeightsSolutionState.

Functions

create_context_operator_probability

Creates a heuristic operator probability which uses context state.

create_default_heuristic_operator

Creates default heuristic operator (ruin and recreate) with default parameters.

create_default_init_operators

Creates default init operators.

create_default_processing

Create default processing.

create_elitism_population

Creates elitism population algorithm.

create_scalar_operator_probability

Creates a heuristic operator probability which uses is_hit method from passed random object.

get_default_heuristic

Gets default heuristic.

get_default_telemetry_mode

Creates default telemetry mode.B

get_dynamic_heuristic

Gets dynamic heuristic using default settings.

get_static_heuristic

Gets static heuristic using default settings.

get_static_heuristic_from_heuristic_group

Gets static heuristic using heuristic group.

Type Aliases

DynTermination

A type alias for domain specific termination type.

ElitismPopulation

A type for elitism population.

GreedyPopulation

A type for greedy population.

HeuristicFilterFn

A type to filter meta heuristics by name. Returns true if heuristic can be used.

MaxGenerationTermination

A type for max generation termination.

MaxTimeTermination

A type for max time termination.

MinVariationTermination

A type for min variation termination.

ProblemConfigBuilder

A type alias for evolution config builder.

RosomaxaPopulation

A type for rosomaxa population.

TargetCompositeTermination

A type for composite termination.

TargetEvolutionStrategy

A type alias for domain specific evolution strategy.

TargetHeuristic

A type alias for domain specific heuristic.

TargetHeuristicGroup

A heuristic group type alias.

TargetHeuristicProbability

A heuristic probability type alias.

TargetPopulation

A type alias for domain specific population.

TargetSearchOperator

A type for domain specific heuristic operator.