Expand description
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.
That’s why the concept of dominance is introduced: a solution is said to dominate another solution if its quality is at least as good on every objective and better on at least one. The set of all non-dominated solutions of an optimization problem is called the Pareto set and the projection of this set onto the objective function space is called the Pareto front.
The aim of multi-objective metaheuristics is to approximate the Pareto front as closely as possible (Zitzler et al., 2004) and therefore generate a set of mutually non-dominated solutions called the Pareto set approximation.
This library utilizes NSGA-II
algorithm to apply Pareto-based ranking over population in order
to find Pareto set approximation. However, that Pareto optimality of the solutions cannot be
guaranteed: it is only known that none of the generated solutions dominates the others.
In the end, the top ranked individual is returned as best known solution.
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
- Contains pre and post processing logic.
- The mutation module specifies building blocks for mutation operator used by evolution.
Structs
- Specifies keys used by heuristic.
- Wraps recreate method as
InitialOperator
- A type which encapsulates information needed to perform solution refinement process.
- Solves a Vehicle Routing Problem and returns a (solution, its cost) pair in case of success or error description, if solution cannot be found.
Enums
- Defines instant refinement speed type.
Traits
- A type to use a filtering by meta heuristics name. The corresponding function returns true if heuristic can be used.
Functions
- Creates a heuristic operator probability which uses context state.
- Creates config builder with default settings.
- Creates default heuristic operator (ruin and recreate) with default parameters.
- Creates default init operators.
- Create default processing.
- Creates elitism population algorithm.
- Creates a heuristic operator probability which uses
is_hit
method from passed random object. - Gets default heuristic.
- Creates default telemetry mode.B
- Gets dynamic heuristic using default settings.
- Gets static heuristic using default settings.
- Gets static heuristic using heuristic group.
Type Aliases
- A type alias for domain specific termination type.
- A type for elitism population.
- A type for greedy population.
- A type to filter meta heuristics by name. Returns true if heuristic can be used.
- A type for max generation termination.
- A type for max time termination.
- A type for min variation termination.
- A type alias for evolution config builder.
- A type for rosomaxa population.
- A type for composite termination.
- A type alias for domain specific evolution strategy.
- A type alias for domain specific heuristic.
- A heuristic group type alias.
- A heuristic probability type alias.
- A type alias for domain specific population.
- A type for domain specific heuristic operator.