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&amp;context=SearchWebhook&amp;vid=32KUL_KUL:Lirias&amp;lang=en&amp;search_scope=lirias_profile&amp;adaptor=SearchWebhook&amp;tab=LIRIAS&amp;query=any,contains,LIRIAS1988666&amp;offset=0

Note that, 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).

Protobuf type operations_research.SISRRuinStrategy

Definition at line 485 of file SISRRuinStrategy.java.

Inheritance diagram for com.google.ortools.constraintsolver.SISRRuinStrategy.Builder:

Public Member Functions
Builder	clear ()
com.google.protobuf.Descriptors.Descriptor	getDescriptorForType ()
com.google.ortools.constraintsolver.SISRRuinStrategy	getDefaultInstanceForType ()
com.google.ortools.constraintsolver.SISRRuinStrategy	build ()
com.google.ortools.constraintsolver.SISRRuinStrategy	buildPartial ()
Builder	mergeFrom (com.google.protobuf.Message other)
Builder	mergeFrom (com.google.ortools.constraintsolver.SISRRuinStrategy other)
final boolean	isInitialized ()
Builder	mergeFrom (com.google.protobuf.CodedInputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
boolean	hasMaxRemovedSequenceSize ()
int	getMaxRemovedSequenceSize ()
Builder	setMaxRemovedSequenceSize (int value)
Builder	clearMaxRemovedSequenceSize ()
boolean	hasAvgNumRemovedVisits ()
int	getAvgNumRemovedVisits ()
Builder	setAvgNumRemovedVisits (int value)
Builder	clearAvgNumRemovedVisits ()
boolean	hasBypassFactor ()
double	getBypassFactor ()
Builder	setBypassFactor (double value)
Builder	clearBypassFactor ()

Static Public Member Functions
static final com.google.protobuf.Descriptors.Descriptor	getDescriptor ()

Protected Member Functions
com.google.protobuf.GeneratedMessage.FieldAccessorTable	internalGetFieldAccessorTable ()

Member Function Documentation

◆ build()

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.build ( )

Definition at line 534 of file SISRRuinStrategy.java.

◆ buildPartial()

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.buildPartial ( )

Definition at line 543 of file SISRRuinStrategy.java.

◆ clear()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.clear ( )

Definition at line 513 of file SISRRuinStrategy.java.

◆ clearAvgNumRemovedVisits()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.clearAvgNumRemovedVisits ( )

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

optional uint32 avg_num_removed_visits = 2;

Returns: This builder for chaining.

Definition at line 760 of file SISRRuinStrategy.java.

◆ clearBypassFactor()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.clearBypassFactor ( )

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

optional double bypass_factor = 3;

Returns: This builder for chaining.

Definition at line 824 of file SISRRuinStrategy.java.

◆ clearMaxRemovedSequenceSize()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.clearMaxRemovedSequenceSize ( )

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

optional uint32 max_removed_sequence_size = 1;

Returns: This builder for chaining.

Definition at line 700 of file SISRRuinStrategy.java.

◆ getAvgNumRemovedVisits()

int com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getAvgNumRemovedVisits ( )

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

optional uint32 avg_num_removed_visits = 2;

Returns: The avgNumRemovedVisits.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 731 of file SISRRuinStrategy.java.

◆ getBypassFactor()

double com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getBypassFactor ( )

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

optional double bypass_factor = 3;

Returns: The bypassFactor.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 793 of file SISRRuinStrategy.java.

◆ getDefaultInstanceForType()

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getDefaultInstanceForType ( )

Definition at line 529 of file SISRRuinStrategy.java.

◆ getDescriptor()

final com.google.protobuf.Descriptors.Descriptor com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getDescriptor ( )

static

Definition at line 490 of file SISRRuinStrategy.java.

◆ getDescriptorForType()

com.google.protobuf.Descriptors.Descriptor com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getDescriptorForType ( )

Definition at line 524 of file SISRRuinStrategy.java.

◆ getMaxRemovedSequenceSize()

int com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.getMaxRemovedSequenceSize ( )

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

optional uint32 max_removed_sequence_size = 1;

Returns: The maxRemovedSequenceSize.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 671 of file SISRRuinStrategy.java.

◆ hasAvgNumRemovedVisits()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.hasAvgNumRemovedVisits ( )

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

optional uint32 avg_num_removed_visits = 2;

Returns: Whether the avgNumRemovedVisits field is set.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 718 of file SISRRuinStrategy.java.

◆ hasBypassFactor()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.hasBypassFactor ( )

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

optional double bypass_factor = 3;

Returns: Whether the bypassFactor field is set.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 779 of file SISRRuinStrategy.java.

◆ hasMaxRemovedSequenceSize()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.hasMaxRemovedSequenceSize ( )

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

optional uint32 max_removed_sequence_size = 1;

Returns: Whether the maxRemovedSequenceSize field is set.

Implements com.google.ortools.constraintsolver.SISRRuinStrategyOrBuilder.

Definition at line 658 of file SISRRuinStrategy.java.

◆ internalGetFieldAccessorTable()

com.google.protobuf.GeneratedMessage.FieldAccessorTable com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.internalGetFieldAccessorTable ( )

protected

Definition at line 496 of file SISRRuinStrategy.java.

◆ isInitialized()

final boolean com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.isInitialized ( )

Definition at line 595 of file SISRRuinStrategy.java.

◆ mergeFrom() [1/3]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.mergeFrom ( com.google.ortools.constraintsolver.SISRRuinStrategy other )

Definition at line 578 of file SISRRuinStrategy.java.

◆ mergeFrom() [2/3]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.mergeFrom	(	com.google.protobuf.CodedInputStream	input,
		com.google.protobuf.ExtensionRegistryLite	extensionRegistry ) throws java.io.IOException

Definition at line 600 of file SISRRuinStrategy.java.

◆ mergeFrom() [3/3]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.mergeFrom ( com.google.protobuf.Message other )

Definition at line 569 of file SISRRuinStrategy.java.

◆ setAvgNumRemovedVisits()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.setAvgNumRemovedVisits ( int value )

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

optional uint32 avg_num_removed_visits = 2;

Parameters

value The avgNumRemovedVisits to set.

Returns: This builder for chaining.

Definition at line 744 of file SISRRuinStrategy.java.

◆ setBypassFactor()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.setBypassFactor ( double value )

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

optional double bypass_factor = 3;

Parameters

value The bypassFactor to set.

Returns: This builder for chaining.

Definition at line 807 of file SISRRuinStrategy.java.

◆ setMaxRemovedSequenceSize()

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.setMaxRemovedSequenceSize ( int value )

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

optional uint32 max_removed_sequence_size = 1;

Parameters

value The maxRemovedSequenceSize to set.

Returns: This builder for chaining.

Definition at line 684 of file SISRRuinStrategy.java.

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

build/java/ortools-java/src/main/java/com/google/ortools/constraintsolver/SISRRuinStrategy.java

Detailed Description

Public Member Functions

Static Public Member Functions

Protected Member Functions

Member Function Documentation

◆ build()

◆ buildPartial()

◆ clear()

◆ clearAvgNumRemovedVisits()

◆ clearBypassFactor()

◆ clearMaxRemovedSequenceSize()

◆ getAvgNumRemovedVisits()

◆ getBypassFactor()

◆ getDefaultInstanceForType()

◆ getDescriptor()

◆ getDescriptorForType()

◆ getMaxRemovedSequenceSize()

◆ hasAvgNumRemovedVisits()

◆ hasBypassFactor()

◆ hasMaxRemovedSequenceSize()

◆ internalGetFieldAccessorTable()

◆ isInitialized()

◆ mergeFrom() [1/3]

◆ mergeFrom() [2/3]

◆ mergeFrom() [3/3]

◆ setAvgNumRemovedVisits()

◆ setBypassFactor()

◆ setMaxRemovedSequenceSize()