Module vrp_core::solver::mutation

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

The default implementation of mutation operator is RuinAndRecreateMutation which is based on ruin and recreate principle, introduced by Schrimpf et al. (2000).

Structs

AdjustedStringRemoval	Adjusted string removal ruin strategy based on "Slack Induction by String Removals for Vehicle Routing Problems" by Jan Christiaens, Greet Vanden Berghe.
ClusterRemoval	A ruin strategy which removes job clusters using DBSCAN algorithm.
CompositeLocalSearch	Provides the way to run multiple local search operators with different probability.
CompositeMutation	A mutation operator which uses others based on their weight probability.
CompositeRecreate	Provides the way to run one of multiple recreate methods with different probability.
CompositeRuin	Provides the way to run multiple ruin methods one by one on the same solution.
ExchangeInterRouteBest	A local search operator which tries to exchange jobs in best way between different routes.
ExchangeInterRouteRandom	A local search operator which tries to exchange random jobs between different routes.
ExchangeIntraRouteRandom	A local search operator which tries to exchange jobs in random way inside one route.
JobRemovalLimit	Specifies a limit for amount of jobs to be removed.
NeighbourRemoval	A ruin strategy which removes jobs in neighbourhood of randomly selected job (inclusive).
RandomJobRemoval	A ruin strategy which removes random jobs from solution.
RandomRouteRemoval	A ruin strategy which removes random route from solution.
RecreateWithBlinks	A recreate method as described in "Slack Induction by String Removals for Vehicle Routing Problems" (aka SISR) paper by Jan Christiaens, Greet Vanden Berghe.
RecreateWithCheapest	A recreate method which is equivalent to cheapest insertion heuristic.
RecreateWithGaps	A recreate method which selects on each insertion step only subset of randomly chosen jobs.
RecreateWithNearestNeighbor	A recreate strategy which solution using nearest neighbor algorithm.
RecreateWithPerturbation	A recreate method which perturbs the cost by a factor to introduce randomization.
RecreateWithRegret	A recreate strategy which computes the difference in cost of inserting customer in its best and kth best route, where k is a user-defined parameter. Then it inserts the customer with the max difference in its least cost position.
RecreateWithSkipBest	A recreate strategy which skips best job insertion for insertion.
RuinAndRecreate	A mutation operator based on ruin and recreate principle.
WorstJobRemoval	A ruin strategy which detects the most cost expensive jobs in each route and delete them with their neighbours.

Traits

LocalSearch	Specifies behavior of a local search operator.
Mutation	A trait which defines mutation behavior.
Recreate	A trait which specifies logic to produce a new feasible solution from partial one.
Ruin	A trait which specifies logic to destroy parts of solution.

Type Definitions

RuinGroup

A type which specifies a group of multiple ruin strategies with its probability.