com.google.ortools.constraintsolver.SISRRuinStrategy Class Reference

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

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)

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

Member Function Documentation

equals()

boolean com.google.ortools.constraintsolver.SISRRuinStrategy.equals

(

final java.lang.Object

obj

)

Definition at line 260 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 \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 175 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 \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 206 of file SISRRuinStrategy.java.

getDefaultInstance()

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

static

Definition at line 839 of file SISRRuinStrategy.java.

getDefaultInstanceForType()

com.google.ortools.constraintsolver.SISRRuinStrategy com.google.ortools.constraintsolver.SISRRuinStrategy.getDefaultInstanceForType

(

)

Definition at line 875 of file SISRRuinStrategy.java.

getDescriptor()

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

static

Definition at line 108 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 146 of file SISRRuinStrategy.java.

getParserForType()

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

(

)

Definition at line 870 of file SISRRuinStrategy.java.

getSerializedSize()

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

(

)

Definition at line 237 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 \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 162 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 \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 192 of file SISRRuinStrategy.java.

hashCode()

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

(

)

Definition at line 290 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 133 of file SISRRuinStrategy.java.

internalGetFieldAccessorTable()

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

protected

Definition at line 114 of file SISRRuinStrategy.java.

isInitialized()

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

(

)

Definition at line 212 of file SISRRuinStrategy.java.

newBuilder() [1/2]

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

static

Definition at line 388 of file SISRRuinStrategy.java.

newBuilder() [2/2]

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

static

Definition at line 391 of file SISRRuinStrategy.java.

newBuilderForType() [1/2]

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

(

)

Definition at line 387 of file SISRRuinStrategy.java.

newBuilderForType() [2/2]

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

protected

Definition at line 401 of file SISRRuinStrategy.java.

parseDelimitedFrom() [1/2]

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

static

Definition at line 359 of file SISRRuinStrategy.java.

parseDelimitedFrom() [2/2]

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

parseFrom() [1/10]

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

static

Definition at line 336 of file SISRRuinStrategy.java.

parseFrom() [2/10]

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

parseFrom() [3/10]

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

parseFrom() [4/10]

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

parseFrom() [5/10]

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

static

Definition at line 372 of file SISRRuinStrategy.java.

parseFrom() [6/10]

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

parseFrom() [7/10]

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

static

Definition at line 346 of file SISRRuinStrategy.java.

parseFrom() [8/10]

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

parseFrom() [9/10]

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

static

Definition at line 314 of file SISRRuinStrategy.java.

parseFrom() [10/10]

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

parser()

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

static

Definition at line 865 of file SISRRuinStrategy.java.

toBuilder()

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

(

)

Definition at line 395 of file SISRRuinStrategy.java.

writeTo()

void com.google.ortools.constraintsolver.SISRRuinStrategy.writeTo

(

com.google.protobuf.CodedOutputStream

output

)

throws java.io.IOException

Definition at line 222 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 150 of file SISRRuinStrategy.java.

BYPASS_FACTOR_FIELD_NUMBER

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

static

Definition at line 179 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 121 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