Module vrp_core::solver

source ·
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

  • processing
    Contains pre and post processing logic.
  • search
    The mutation module specifies building blocks for mutation operator used by evolution.

Structs

  • HeuristicKeys
    Specifies keys used by heuristic.
  • 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.

Enums

Traits

  • HeuristicFilter
    A type to use a filtering by meta heuristics name. The corresponding function returns true if heuristic can be used.

Functions

Type Aliases