Module vrp_core::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.

The default implementation can be roughly described as "Multi-objective Parthenogenesis based Evolutionary Algorithm with Ruin and Recreate Mutation Operator".

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.

This crate contains NSGA-II buildings blocks which can be found in nsga2 module.

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.

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.

Implementation blocks can be found in mutation module.

Solver usage

Check Builder and Solver documentation to see how to run VRP solver.

Modules

mutation	The mutation module specifies building blocks for mutation operator used by evolution.
objectives	The objective module specifies various objective functions for solving Vehicle Routing Problem.
selection	Contains offspring selection algorithms.
termination	The termination module contains logic which defines termination criteria for metaheuristic, e.g. when to stop evolution in evolutionary algorithms.

Structs

Builder	Provides configurable way to build Vehile Routing Problem Solver instance using fluent interface style.
DominancePopulation	A simple evolution aware implementation of Population trait with the the following characteristics:
Metrics	Encapsulates different measurements regarding algorithm evaluation.
RefinementContext	A type which encapsulates information needed to perform solution refinement process.
Solver	A Vehicle Routing Problem Solver based on evolutionary algorithm.
Statistics	A refinement statistics to track evolution progress.
Telemetry	Provides way to collect metrics and write information into log.

Enums

TelemetryMode

Specifies a telemetry mode.

Constants

SOLUTION_ORDER_KEY

A key to store solution order information.

Traits

Population

A trait which models a population with individuals (solutions).

Type Definitions

Individual

Represents solution in population defined as actual solution.