com.google.ortools.constraintsolver.SISRRuinStrategy.Builder Class Reference

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 ()

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

Member Function Documentation

build()

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

(

)

Definition at line 533 of file SISRRuinStrategy.java.

buildPartial()

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

(

)

Definition at line 542 of file SISRRuinStrategy.java.

clear()

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

(

)

Definition at line 512 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 \bar{c} and the suggested value is 10.

optional uint32 avg_num_removed_visits = 2;

Returns

This builder for chaining.

Definition at line 759 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 \alpha and the
suggested value is 0.01.

optional double bypass_factor = 3;

Returns

This builder for chaining.

Definition at line 823 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 699 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 \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 730 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 \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 792 of file SISRRuinStrategy.java.

getDefaultInstanceForType()

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

(

)

Definition at line 528 of file SISRRuinStrategy.java.

getDescriptor()

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

static

Definition at line 489 of file SISRRuinStrategy.java.

getDescriptorForType()

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

(

)

Definition at line 523 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 670 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 \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 717 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 \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 778 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 657 of file SISRRuinStrategy.java.

internalGetFieldAccessorTable()

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

protected

Definition at line 495 of file SISRRuinStrategy.java.

isInitialized()

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

(

)

Definition at line 594 of file SISRRuinStrategy.java.

mergeFrom() [1/3]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.mergeFrom

(

com.google.ortools.constraintsolver.SISRRuinStrategy

other

)

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

mergeFrom() [3/3]

Builder com.google.ortools.constraintsolver.SISRRuinStrategy.Builder.mergeFrom

(

com.google.protobuf.Message

other

)

Definition at line 568 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 \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 743 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 \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 806 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 683 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