public final class SISRRuinStrategy extends com.google.protobuf.GeneratedMessage implements SISRRuinStrategyOrBuilder
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| Modifier and Type | Class and Description |
|---|---|
static class |
SISRRuinStrategy.Builder
Ruin strategy based on the "Slack Induction by String Removals for Vehicle
Routing Problems" by Jan Christiaens and Greet Vanden Berghe, Transportation
Science 2020.
|
com.google.protobuf.GeneratedMessage.ExtendableBuilder<MessageT extends com.google.protobuf.GeneratedMessage.ExtendableMessage<MessageT>,BuilderT extends com.google.protobuf.GeneratedMessage.ExtendableBuilder<MessageT,BuilderT>>, com.google.protobuf.GeneratedMessage.ExtendableMessage<MessageT extends com.google.protobuf.GeneratedMessage.ExtendableMessage<MessageT>>, com.google.protobuf.GeneratedMessage.ExtendableMessageOrBuilder<MessageT extends com.google.protobuf.GeneratedMessage.ExtendableMessage<MessageT>>, com.google.protobuf.GeneratedMessage.FieldAccessorTable, com.google.protobuf.GeneratedMessage.GeneratedExtension<ContainingT extends com.google.protobuf.Message,T>, com.google.protobuf.GeneratedMessage.UnusedPrivateParameter| Modifier and Type | Field and Description |
|---|---|
static int |
AVG_NUM_REMOVED_VISITS_FIELD_NUMBER |
static int |
BYPASS_FACTOR_FIELD_NUMBER |
static int |
MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER |
| Modifier and Type | Method and Description |
|---|---|
boolean |
equals(java.lang.Object obj) |
int |
getAvgNumRemovedVisits()
Number of visits that are removed on average.
|
double |
getBypassFactor()
Value in [0, 1] ruling the number of preserved customers in the split
sequence removal.
|
static SISRRuinStrategy |
getDefaultInstance() |
SISRRuinStrategy |
getDefaultInstanceForType() |
static com.google.protobuf.Descriptors.Descriptor |
getDescriptor() |
int |
getMaxRemovedSequenceSize()
Maximum number of removed visits per sequence.
|
com.google.protobuf.Parser<SISRRuinStrategy> |
getParserForType() |
int |
getSerializedSize() |
boolean |
hasAvgNumRemovedVisits()
Number of visits that are removed on average.
|
boolean |
hasBypassFactor()
Value in [0, 1] ruling the number of preserved customers in the split
sequence removal.
|
int |
hashCode() |
boolean |
hasMaxRemovedSequenceSize()
Maximum number of removed visits per sequence.
|
protected com.google.protobuf.GeneratedMessage.FieldAccessorTable |
internalGetFieldAccessorTable() |
boolean |
isInitialized() |
static SISRRuinStrategy.Builder |
newBuilder() |
static SISRRuinStrategy.Builder |
newBuilder(SISRRuinStrategy prototype) |
SISRRuinStrategy.Builder |
newBuilderForType() |
protected SISRRuinStrategy.Builder |
newBuilderForType(com.google.protobuf.AbstractMessage.BuilderParent parent) |
static SISRRuinStrategy |
parseDelimitedFrom(java.io.InputStream input) |
static SISRRuinStrategy |
parseDelimitedFrom(java.io.InputStream input,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static SISRRuinStrategy |
parseFrom(byte[] data) |
static SISRRuinStrategy |
parseFrom(byte[] data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static SISRRuinStrategy |
parseFrom(java.nio.ByteBuffer data) |
static SISRRuinStrategy |
parseFrom(java.nio.ByteBuffer data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static SISRRuinStrategy |
parseFrom(com.google.protobuf.ByteString data) |
static SISRRuinStrategy |
parseFrom(com.google.protobuf.ByteString data,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static SISRRuinStrategy |
parseFrom(com.google.protobuf.CodedInputStream input) |
static SISRRuinStrategy |
parseFrom(com.google.protobuf.CodedInputStream input,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static SISRRuinStrategy |
parseFrom(java.io.InputStream input) |
static SISRRuinStrategy |
parseFrom(java.io.InputStream input,
com.google.protobuf.ExtensionRegistryLite extensionRegistry) |
static com.google.protobuf.Parser<SISRRuinStrategy> |
parser() |
SISRRuinStrategy.Builder |
toBuilder() |
void |
writeTo(com.google.protobuf.CodedOutputStream output) |
canUseUnsafe, computeStringSize, computeStringSizeNoTag, emptyBooleanList, emptyDoubleList, emptyFloatList, emptyIntList, emptyList, emptyLongList, getAllFields, getDescriptorForType, getField, getOneofFieldDescriptor, getRepeatedField, getRepeatedFieldCount, getUnknownFields, hasField, hasOneof, internalGetMapField, internalGetMapFieldReflection, isStringEmpty, makeMutableCopy, makeMutableCopy, mergeFromAndMakeImmutableInternal, newFileScopedGeneratedExtension, newInstance, newMessageScopedGeneratedExtension, parseDelimitedWithIOException, parseDelimitedWithIOException, parseUnknownField, parseUnknownFieldProto3, parseWithIOException, parseWithIOException, parseWithIOException, parseWithIOException, serializeBooleanMapTo, serializeIntegerMapTo, serializeLongMapTo, serializeStringMapTo, writeReplace, writeString, writeStringNoTagfindInitializationErrors, getInitializationErrorString, hashFields, toStringaddAll, checkByteStringIsUtf8, toByteArray, toByteString, writeDelimitedTo, writeToclone, finalize, getClass, notify, notifyAll, wait, wait, waitpublic static final int MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER
public static final int AVG_NUM_REMOVED_VISITS_FIELD_NUMBER
public static final int BYPASS_FACTOR_FIELD_NUMBER
public static final com.google.protobuf.Descriptors.Descriptor getDescriptor()
protected com.google.protobuf.GeneratedMessage.FieldAccessorTable internalGetFieldAccessorTable()
internalGetFieldAccessorTable in class com.google.protobuf.GeneratedMessagepublic boolean 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;hasMaxRemovedSequenceSize in interface SISRRuinStrategyOrBuilderpublic int 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;getMaxRemovedSequenceSize in interface SISRRuinStrategyOrBuilderpublic boolean 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;hasAvgNumRemovedVisits in interface SISRRuinStrategyOrBuilderpublic int 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;getAvgNumRemovedVisits in interface SISRRuinStrategyOrBuilderpublic boolean 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;hasBypassFactor in interface SISRRuinStrategyOrBuilderpublic double 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;getBypassFactor in interface SISRRuinStrategyOrBuilderpublic final boolean isInitialized()
isInitialized in interface com.google.protobuf.MessageLiteOrBuilderisInitialized in class com.google.protobuf.GeneratedMessagepublic void writeTo(com.google.protobuf.CodedOutputStream output)
throws java.io.IOException
writeTo in interface com.google.protobuf.MessageLitewriteTo in class com.google.protobuf.GeneratedMessagejava.io.IOExceptionpublic int getSerializedSize()
getSerializedSize in interface com.google.protobuf.MessageLitegetSerializedSize in class com.google.protobuf.GeneratedMessagepublic boolean equals(java.lang.Object obj)
equals in interface com.google.protobuf.Messageequals in class com.google.protobuf.AbstractMessagepublic int hashCode()
hashCode in interface com.google.protobuf.MessagehashCode in class com.google.protobuf.AbstractMessagepublic static SISRRuinStrategy parseFrom(java.nio.ByteBuffer data) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(java.nio.ByteBuffer data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(com.google.protobuf.ByteString data) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(com.google.protobuf.ByteString data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(byte[] data) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(byte[] data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
com.google.protobuf.InvalidProtocolBufferExceptionpublic static SISRRuinStrategy parseFrom(java.io.InputStream input) throws java.io.IOException
java.io.IOExceptionpublic static SISRRuinStrategy parseFrom(java.io.InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
java.io.IOExceptionpublic static SISRRuinStrategy parseDelimitedFrom(java.io.InputStream input) throws java.io.IOException
java.io.IOExceptionpublic static SISRRuinStrategy parseDelimitedFrom(java.io.InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
java.io.IOExceptionpublic static SISRRuinStrategy parseFrom(com.google.protobuf.CodedInputStream input) throws java.io.IOException
java.io.IOExceptionpublic static SISRRuinStrategy parseFrom(com.google.protobuf.CodedInputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws java.io.IOException
java.io.IOExceptionpublic SISRRuinStrategy.Builder newBuilderForType()
newBuilderForType in interface com.google.protobuf.MessagenewBuilderForType in interface com.google.protobuf.MessageLitepublic static SISRRuinStrategy.Builder newBuilder()
public static SISRRuinStrategy.Builder newBuilder(SISRRuinStrategy prototype)
public SISRRuinStrategy.Builder toBuilder()
toBuilder in interface com.google.protobuf.MessagetoBuilder in interface com.google.protobuf.MessageLiteprotected SISRRuinStrategy.Builder newBuilderForType(com.google.protobuf.AbstractMessage.BuilderParent parent)
newBuilderForType in class com.google.protobuf.AbstractMessagepublic static SISRRuinStrategy getDefaultInstance()
public static com.google.protobuf.Parser<SISRRuinStrategy> parser()
public com.google.protobuf.Parser<SISRRuinStrategy> getParserForType()
getParserForType in interface com.google.protobuf.MessagegetParserForType in interface com.google.protobuf.MessageLitegetParserForType in class com.google.protobuf.GeneratedMessagepublic SISRRuinStrategy getDefaultInstanceForType()
getDefaultInstanceForType in interface com.google.protobuf.MessageLiteOrBuildergetDefaultInstanceForType in interface com.google.protobuf.MessageOrBuilderCopyright © 2025. All rights reserved.