Ruin strategy based on the "Slack Induction by String Removals for Vehicle Routing Problems" by Jan Christiaens and Greet Vanden Berghe, Transportation Science 2020. Link to paper: https://kuleuven.limo.libis.be/discovery/fulldisplay?docid=lirias1988666&context=SearchWebhook&vid=32KUL_KUL:Lirias&lang=en&search_scope=lirias_profile&adaptor=SearchWebhook&tab=LIRIAS&query=any,contains,LIRIAS1988666&offset=0. More...

Inheritance diagram for Google.OrTools.ConstraintSolver.SISRRuinStrategy:

Public Member Functions
	SISRRuinStrategy ()

	SISRRuinStrategy (SISRRuinStrategy other)

SISRRuinStrategy	Clone ()

void	ClearMaxRemovedSequenceSize ()
	Clears the value of the "max_removed_sequence_size" field.

void	ClearAvgNumRemovedVisits ()
	Clears the value of the "avg_num_removed_visits" field.

void	ClearBypassFactor ()
	Clears the value of the "bypass_factor" field.

override bool	Equals (object other)

bool	Equals (SISRRuinStrategy other)

override int	GetHashCode ()

override string	ToString ()

void	WriteTo (pb::CodedOutputStream output)

int	CalculateSize ()

void	MergeFrom (SISRRuinStrategy other)

void	MergeFrom (pb::CodedInputStream input)

Static Public Attributes
const int	MaxRemovedSequenceSizeFieldNumber = 1
	Field number for the "max_removed_sequence_size" field.

const int	AvgNumRemovedVisitsFieldNumber = 2
	Field number for the "avg_num_removed_visits" field.

const int	BypassFactorFieldNumber = 3
	Field number for the "bypass_factor" field.

Properties
static pb::MessageParser< SISRRuinStrategy >	Parser `[get]`

static pbr::MessageDescriptor	Descriptor `[get]`

uint	MaxRemovedSequenceSize `[get, set]`
	Maximum number of removed visits per sequence. The parameter name in the paper is L^{max} and the suggested value is 10.

bool	HasMaxRemovedSequenceSize `[get]`
	Gets whether the "max_removed_sequence_size" field is set.

uint	AvgNumRemovedVisits `[get, set]`
	Number of visits that are removed on average. The parameter name in the paper is \bar{c} and the suggested value is 10.

bool	HasAvgNumRemovedVisits `[get]`
	Gets whether the "avg_num_removed_visits" field is set.

double	BypassFactor `[get, set]`
	Value in [0, 1] ruling the number of preserved customers in the split sequence removal. The parameter name in the paper is \alpha and the suggested value is 0.01.

bool	HasBypassFactor `[get]`
	Gets whether the "bypass_factor" field is set.

Detailed Description

Ruin strategy based on the "Slack Induction by String Removals for Vehicle Routing Problems" by Jan Christiaens and Greet Vanden Berghe, Transportation Science 2020. Link to paper: https://kuleuven.limo.libis.be/discovery/fulldisplay?docid=lirias1988666&context=SearchWebhook&vid=32KUL_KUL:Lirias&lang=en&search_scope=lirias_profile&adaptor=SearchWebhook&tab=LIRIAS&query=any,contains,LIRIAS1988666&offset=0.

Note

, in this implementation, the notion of "string" is replaced by "sequence". The main idea of this ruin is to remove a number of geographically close sequences of nodes. In particular, at every ruin application, a maximum number max_ruined_routes of routes are disrupted. The value for max_ruined_routes is defined as (4 * avg_num_removed_visits) / (1 + max_sequence_size) + 1 with

avg_num_removed_visits: user-defined parameter ruling the average number of visits that are removed in face of several ruin applications (see also the proto message below)
max_sequence_size is defined as min{max_removed_sequence_size, average_route_size} with
- max_removed_sequence_size: user-defined parameter that specifies the maximum number of visits removed from a single route (see also the proto message below)
- average_route_size: the average size of a non-empty route in the current solution The actual number of ruined routes is then obtained as floor(U(1, max_ruined_routes + 1)) where U is a continuous uniform distribution of real values in the given interval. The routes affected by the ruin procedure are selected as follows. First, a non start/end seed node is randomly selected. The route serving this node is the first ruined route. Then, until the required number of routes has been ruined, neighbor nodes of the initial seed node are scanned and the associated not yet ruined routes are disrupted. Nodes defining the selected routes are designated as seed nodes for the "sequence" and "split sequence" removal procedures described below. For every selected route, a maximum number route_max_sequence_size of nodes are removed. In particular, route_max_sequence_size is defined as min{route_size, max_sequence_size} with route_size being the size of the current route. Then, the actual number of removed nodes num_removed_nodes is defined as floor(U(1, route_max_sequence_size + 1)) where U is a continuous uniform distribution of real values in the given interval. As mentioned above, the selected num_removed_nodes number of nodes is removed either via the "sequence" removal or "split sequence" removal procedures. The two removal procedures are executed with equal probabilities. The "sequence" removal procedure removes a randomly selected sequence of size num_removed_nodes that includes the seed node. The "split sequence" removal procedure also removes a randomly selected sequence of size num_removed_nodes that includes the seed node, but it can possibly preserve a subsequence of contiguous nodes. In particular, the procedure first selects a sequence of size num_removed_nodes + num_bypassed, then num_bypassed contiguous nodes in the selected sequence are preserved while the others removed. The definition of num_bypassed is as follows. First num_bypassed = 1. The current value of num_bypassed is maintaned if U(0, 1) < bypass_factor * U(0, 1) or the maximum value for num_bypassed, equal to route_size - num_removed_nodes is reached. The value is incremented of a unit otherwise, and the process is repeated. The value assigned to bypass_factor affects the number of preserved visits (see also the proto message below).

Definition at line 636 of file RoutingIls.pb.cs.

Constructor & Destructor Documentation

◆ SISRRuinStrategy() [1/2]

Google.OrTools.ConstraintSolver.SISRRuinStrategy.SISRRuinStrategy ( )

inline

Definition at line 662 of file RoutingIls.pb.cs.

◆ SISRRuinStrategy() [2/2]

Google.OrTools.ConstraintSolver.SISRRuinStrategy.SISRRuinStrategy ( SISRRuinStrategy other )

inline

Definition at line 670 of file RoutingIls.pb.cs.

Member Function Documentation

◆ CalculateSize()

int Google.OrTools.ConstraintSolver.SISRRuinStrategy.CalculateSize ( )

inline

Definition at line 866 of file RoutingIls.pb.cs.

◆ ClearAvgNumRemovedVisits()

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.ClearAvgNumRemovedVisits ( )

inline

Clears the value of the "avg_num_removed_visits" field.

Definition at line 742 of file RoutingIls.pb.cs.

◆ ClearBypassFactor()

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.ClearBypassFactor ( )

inline

Clears the value of the "bypass_factor" field.

Definition at line 774 of file RoutingIls.pb.cs.

◆ ClearMaxRemovedSequenceSize()

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.ClearMaxRemovedSequenceSize ( )

inline

Clears the value of the "max_removed_sequence_size" field.

Definition at line 711 of file RoutingIls.pb.cs.

◆ Clone()

SISRRuinStrategy Google.OrTools.ConstraintSolver.SISRRuinStrategy.Clone ( )

inline

Definition at line 680 of file RoutingIls.pb.cs.

◆ Equals() [1/2]

override bool Google.OrTools.ConstraintSolver.SISRRuinStrategy.Equals ( object other )

inline

Definition at line 780 of file RoutingIls.pb.cs.

◆ Equals() [2/2]

bool Google.OrTools.ConstraintSolver.SISRRuinStrategy.Equals ( SISRRuinStrategy other )

inline

Definition at line 786 of file RoutingIls.pb.cs.

◆ GetHashCode()

override int Google.OrTools.ConstraintSolver.SISRRuinStrategy.GetHashCode ( )

inline

Definition at line 801 of file RoutingIls.pb.cs.

◆ MergeFrom() [1/2]

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.MergeFrom ( pb.CodedInputStream input )

inline

Definition at line 903 of file RoutingIls.pb.cs.

◆ MergeFrom() [2/2]

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.MergeFrom ( SISRRuinStrategy other )

inline

Definition at line 885 of file RoutingIls.pb.cs.

◆ ToString()

override string Google.OrTools.ConstraintSolver.SISRRuinStrategy.ToString ( )

inline

Definition at line 814 of file RoutingIls.pb.cs.

◆ WriteTo()

void Google.OrTools.ConstraintSolver.SISRRuinStrategy.WriteTo ( pb.CodedOutputStream output )

inline

Definition at line 820 of file RoutingIls.pb.cs.

Member Data Documentation

◆ AvgNumRemovedVisitsFieldNumber

const int Google.OrTools.ConstraintSolver.SISRRuinStrategy.AvgNumRemovedVisitsFieldNumber = 2

static

Field number for the "avg_num_removed_visits" field.

Definition at line 716 of file RoutingIls.pb.cs.

◆ BypassFactorFieldNumber

const int Google.OrTools.ConstraintSolver.SISRRuinStrategy.BypassFactorFieldNumber = 3

static

Field number for the "bypass_factor" field.

Definition at line 747 of file RoutingIls.pb.cs.

◆ MaxRemovedSequenceSizeFieldNumber

const int Google.OrTools.ConstraintSolver.SISRRuinStrategy.MaxRemovedSequenceSizeFieldNumber = 1

static

Field number for the "max_removed_sequence_size" field.

Definition at line 685 of file RoutingIls.pb.cs.

Property Documentation

◆ AvgNumRemovedVisits

uint Google.OrTools.ConstraintSolver.SISRRuinStrategy.AvgNumRemovedVisits

getset

Number of visits that are removed on average. The parameter name in the paper is \bar{c} and the suggested value is 10.

Definition at line 726 of file RoutingIls.pb.cs.

◆ BypassFactor

double Google.OrTools.ConstraintSolver.SISRRuinStrategy.BypassFactor

getset

Value in [0, 1] ruling the number of preserved customers in the split sequence removal. The parameter name in the paper is \alpha and the suggested value is 0.01.

Definition at line 758 of file RoutingIls.pb.cs.

◆ Descriptor

pbr.MessageDescriptor Google.OrTools.ConstraintSolver.SISRRuinStrategy.Descriptor

staticget

Definition at line 650 of file RoutingIls.pb.cs.

◆ HasAvgNumRemovedVisits

bool Google.OrTools.ConstraintSolver.SISRRuinStrategy.HasAvgNumRemovedVisits

get

Gets whether the "avg_num_removed_visits" field is set.

Definition at line 736 of file RoutingIls.pb.cs.

◆ HasBypassFactor

bool Google.OrTools.ConstraintSolver.SISRRuinStrategy.HasBypassFactor

get

Gets whether the "bypass_factor" field is set.

Definition at line 768 of file RoutingIls.pb.cs.

◆ HasMaxRemovedSequenceSize

bool Google.OrTools.ConstraintSolver.SISRRuinStrategy.HasMaxRemovedSequenceSize

get

Gets whether the "max_removed_sequence_size" field is set.

Definition at line 705 of file RoutingIls.pb.cs.

◆ MaxRemovedSequenceSize

uint Google.OrTools.ConstraintSolver.SISRRuinStrategy.MaxRemovedSequenceSize

getset

Maximum number of removed visits per sequence. The parameter name in the paper is L^{max} and the suggested value is 10.

Definition at line 695 of file RoutingIls.pb.cs.

◆ Parser

pb.MessageParser<SISRRuinStrategy> Google.OrTools.ConstraintSolver.SISRRuinStrategy.Parser

staticget

Definition at line 646 of file RoutingIls.pb.cs.

The documentation for this class was generated from the following file:

build/dotnet/Google.OrTools/ortools/constraint_solver/RoutingIls.pb.cs

Public Member Functions

Static Public Attributes

Properties

Detailed Description

Constructor & Destructor Documentation

◆ SISRRuinStrategy() [1/2]

◆ SISRRuinStrategy() [2/2]

Member Function Documentation

◆ CalculateSize()

◆ ClearAvgNumRemovedVisits()

◆ ClearBypassFactor()

◆ ClearMaxRemovedSequenceSize()

◆ Clone()

◆ Equals() [1/2]

◆ Equals() [2/2]

◆ GetHashCode()

◆ MergeFrom() [1/2]

◆ MergeFrom() [2/2]

◆ ToString()

◆ WriteTo()

Member Data Documentation

◆ AvgNumRemovedVisitsFieldNumber

◆ BypassFactorFieldNumber

◆ MaxRemovedSequenceSizeFieldNumber

Property Documentation

◆ AvgNumRemovedVisits

◆ BypassFactor

◆ Descriptor

◆ HasAvgNumRemovedVisits

◆ HasBypassFactor

◆ HasMaxRemovedSequenceSize

◆ MaxRemovedSequenceSize

◆ Parser