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.
CloseRouteRemoval	Removes two random, close to each other, routes from solution.
ClusterRemoval	A ruin strategy which removes job clusters using DBSCAN algorithm.
CompositeLocalOperator	Provides the way to run multiple local search operators with different probability.
CompositeRuin	Provides the way to run multiple ruin methods one by one on the same solution.
ConfigurableRecreate	Provides way to reuse generic behaviour.
DecomposeSearch	A mutation which decomposes original solution into multiple partial solutions, preforms search independently, and then merges partial solution back into one 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.
LocalSearch	A mutation operator which applies local search principles.
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.
RecreateWithFarthest	A recreate method which always insert first the farthest job in empty route and prefers filling non-empty routes first.
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.
RescheduleDeparture	Reschedules departure time of the routes in the solution.
RuinAndRecreate	A mutation operator based on ruin and recreate principle.
RuinLimits	Specifies a limit for amount of jobs to be removed.
WeightedRecreate	Provides the way to run one of multiple recreate methods.
WeightedRuin	Provides the way to pick one ruin from the group ruin methods.
WorstJobRemoval	A ruin strategy which detects the most cost expensive jobs in each route and delete them with their neighbours.

Traits

LocalOperator	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 their probability.