Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
com.google.ortools.constraintsolver.SISRRuinStrategy Class Reference

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 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 87 of file SISRRuinStrategy.java.

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

Classes

class  Builder

Public Member Functions

boolean hasMaxRemovedSequenceSize ()
int getMaxRemovedSequenceSize ()
boolean hasAvgNumRemovedVisits ()
int getAvgNumRemovedVisits ()
boolean hasBypassFactor ()
double getBypassFactor ()
final boolean isInitialized ()
void writeTo (com.google.protobuf.CodedOutputStream output) throws java.io.IOException
int getSerializedSize ()
boolean equals (final java.lang.Object obj)
int hashCode ()
Builder newBuilderForType ()
Builder toBuilder ()
com.google.protobuf.Parser< SISRRuinStrategy > getParserForType ()
com.google.ortools.constraintsolver.SISRRuinStrategy getDefaultInstanceForType ()

Static Public Member Functions

static final com.google.protobuf.Descriptors.Descriptor getDescriptor ()
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (java.nio.ByteBuffer data) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (java.nio.ByteBuffer data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (com.google.protobuf.ByteString data) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (com.google.protobuf.ByteString data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (byte[] data) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (byte[] data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (java.io.InputStream input) throws java.io.IOException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (java.io.InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseDelimitedFrom (java.io.InputStream input) throws java.io.IOException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseDelimitedFrom (java.io.InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (com.google.protobuf.CodedInputStream input) throws java.io.IOException
static com.google.ortools.constraintsolver.SISRRuinStrategy parseFrom (com.google.protobuf.CodedInputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
static Builder newBuilder ()
static Builder newBuilder (com.google.ortools.constraintsolver.SISRRuinStrategy prototype)
static com.google.ortools.constraintsolver.SISRRuinStrategy getDefaultInstance ()
static com.google.protobuf.Parser< SISRRuinStrategy > parser ()

Static Public Attributes

static final int MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER = 1
static final int AVG_NUM_REMOVED_VISITS_FIELD_NUMBER = 2
static final int BYPASS_FACTOR_FIELD_NUMBER = 3

Protected Member Functions

com.google.protobuf.GeneratedMessage.FieldAccessorTable internalGetFieldAccessorTable ()
Builder newBuilderForType (com.google.protobuf.GeneratedMessage.BuilderParent parent)

Member Function Documentation

◆ equals()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.equals ( final java.lang.Object obj)

Definition at line 261 of file SISRRuinStrategy.java.

◆ getAvgNumRemovedVisits()

int com.google.ortools.constraintsolver.SISRRuinStrategy.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 176 of file SISRRuinStrategy.java.

◆ getBypassFactor()

double com.google.ortools.constraintsolver.SISRRuinStrategy.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 207 of file SISRRuinStrategy.java.

◆ getDefaultInstance()

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.getDefaultInstance ( )
static

Definition at line 840 of file SISRRuinStrategy.java.

◆ getDefaultInstanceForType()

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

Definition at line 876 of file SISRRuinStrategy.java.

◆ getDescriptor()

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

Definition at line 109 of file SISRRuinStrategy.java.

◆ getMaxRemovedSequenceSize()

int com.google.ortools.constraintsolver.SISRRuinStrategy.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 147 of file SISRRuinStrategy.java.

◆ getParserForType()

com.google.protobuf.Parser< SISRRuinStrategy > com.google.ortools.constraintsolver.SISRRuinStrategy.getParserForType ( )

Definition at line 871 of file SISRRuinStrategy.java.

◆ getSerializedSize()

int com.google.ortools.constraintsolver.SISRRuinStrategy.getSerializedSize ( )

Definition at line 238 of file SISRRuinStrategy.java.

◆ hasAvgNumRemovedVisits()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.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 163 of file SISRRuinStrategy.java.

◆ hasBypassFactor()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.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 193 of file SISRRuinStrategy.java.

◆ hashCode()

int com.google.ortools.constraintsolver.SISRRuinStrategy.hashCode ( )

Definition at line 291 of file SISRRuinStrategy.java.

◆ hasMaxRemovedSequenceSize()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.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 134 of file SISRRuinStrategy.java.

◆ internalGetFieldAccessorTable()

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

Definition at line 115 of file SISRRuinStrategy.java.

◆ isInitialized()

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

Definition at line 213 of file SISRRuinStrategy.java.

◆ newBuilder() [1/2]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.newBuilder ( )
static

Definition at line 389 of file SISRRuinStrategy.java.

◆ newBuilder() [2/2]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.newBuilder ( com.google.ortools.constraintsolver.SISRRuinStrategy prototype)
static

Definition at line 392 of file SISRRuinStrategy.java.

◆ newBuilderForType() [1/2]

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

Definition at line 388 of file SISRRuinStrategy.java.

◆ newBuilderForType() [2/2]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.newBuilderForType ( com.google.protobuf.GeneratedMessage.BuilderParent parent)
protected

Definition at line 402 of file SISRRuinStrategy.java.

◆ parseDelimitedFrom() [1/2]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseDelimitedFrom ( java.io.InputStream input) throws java.io.IOException
static

Definition at line 360 of file SISRRuinStrategy.java.

◆ parseDelimitedFrom() [2/2]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseDelimitedFrom ( java.io.InputStream input,
com.google.protobuf.ExtensionRegistryLite extensionRegistry ) throws java.io.IOException
static

Definition at line 366 of file SISRRuinStrategy.java.

◆ parseFrom() [1/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( byte[] data) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 337 of file SISRRuinStrategy.java.

◆ parseFrom() [2/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( byte[] data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry ) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 341 of file SISRRuinStrategy.java.

◆ parseFrom() [3/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( com.google.protobuf.ByteString data) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 326 of file SISRRuinStrategy.java.

◆ parseFrom() [4/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( com.google.protobuf.ByteString data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry ) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 331 of file SISRRuinStrategy.java.

◆ parseFrom() [5/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( com.google.protobuf.CodedInputStream input) throws java.io.IOException
static

Definition at line 373 of file SISRRuinStrategy.java.

◆ parseFrom() [6/10]

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

Definition at line 379 of file SISRRuinStrategy.java.

◆ parseFrom() [7/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( java.io.InputStream input) throws java.io.IOException
static

Definition at line 347 of file SISRRuinStrategy.java.

◆ parseFrom() [8/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( java.io.InputStream input,
com.google.protobuf.ExtensionRegistryLite extensionRegistry ) throws java.io.IOException
static

Definition at line 352 of file SISRRuinStrategy.java.

◆ parseFrom() [9/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( java.nio.ByteBuffer data) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 315 of file SISRRuinStrategy.java.

◆ parseFrom() [10/10]

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.parseFrom ( java.nio.ByteBuffer data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry ) throws com.google.protobuf.InvalidProtocolBufferException
static

Definition at line 320 of file SISRRuinStrategy.java.

◆ parser()

com.google.protobuf.Parser< SISRRuinStrategy > com.google.ortools.constraintsolver.SISRRuinStrategy.parser ( )
static

Definition at line 866 of file SISRRuinStrategy.java.

◆ toBuilder()

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

Definition at line 396 of file SISRRuinStrategy.java.

◆ writeTo()

void com.google.ortools.constraintsolver.SISRRuinStrategy.writeTo ( com.google.protobuf.CodedOutputStream output) throws java.io.IOException

Definition at line 223 of file SISRRuinStrategy.java.

Member Data Documentation

◆ AVG_NUM_REMOVED_VISITS_FIELD_NUMBER

final int com.google.ortools.constraintsolver.SISRRuinStrategy.AVG_NUM_REMOVED_VISITS_FIELD_NUMBER = 2
static

Definition at line 151 of file SISRRuinStrategy.java.

◆ BYPASS_FACTOR_FIELD_NUMBER

final int com.google.ortools.constraintsolver.SISRRuinStrategy.BYPASS_FACTOR_FIELD_NUMBER = 3
static

Definition at line 180 of file SISRRuinStrategy.java.

◆ MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER

final int com.google.ortools.constraintsolver.SISRRuinStrategy.MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER = 1
static

Definition at line 122 of file SISRRuinStrategy.java.

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