Class SISRRuinStrategy

java.lang.Object
com.google.protobuf.AbstractMessageLite
com.google.protobuf.AbstractMessage
com.google.protobuf.GeneratedMessage
com.google.ortools.constraintsolver.SISRRuinStrategy
All Implemented Interfaces:
SISRRuinStrategyOrBuilder, com.google.protobuf.Message, com.google.protobuf.MessageLite, com.google.protobuf.MessageLiteOrBuilder, com.google.protobuf.MessageOrBuilder, Serializable
@Generated 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
See Also:

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static final 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.

    Nested classes/interfaces inherited from class com.google.protobuf.GeneratedMessage

    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

    Nested classes/interfaces inherited from class com.google.protobuf.AbstractMessage

    com.google.protobuf.AbstractMessage.BuilderParent

    Nested classes/interfaces inherited from class com.google.protobuf.AbstractMessageLite

    com.google.protobuf.AbstractMessageLite.InternalOneOfEnum

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int
    AVG_NUM_REMOVED_VISITS_FIELD_NUMBER
     
    static final int
    BYPASS_FACTOR_FIELD_NUMBER
     
    static final int
    MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER
     

    Fields inherited from class com.google.protobuf.GeneratedMessage

    alwaysUseFieldBuilders, unknownFields

    Fields inherited from class com.google.protobuf.AbstractMessage

    memoizedSize

    Fields inherited from class com.google.protobuf.AbstractMessageLite

    memoizedHashCode

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    equals(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 final 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()
     
    final 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(InputStream input)
     
    static SISRRuinStrategy
    parseDelimitedFrom(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(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(InputStream input)
     
    static SISRRuinStrategy
    parseFrom(InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry)
     
    static SISRRuinStrategy
    parseFrom(ByteBuffer data)
     
    static SISRRuinStrategy
    parseFrom(ByteBuffer data, com.google.protobuf.ExtensionRegistryLite extensionRegistry)
     
    static com.google.protobuf.Parser<SISRRuinStrategy>
    parser()
     
    SISRRuinStrategy.Builder
    toBuilder()
     
    void
    writeTo(com.google.protobuf.CodedOutputStream output)
     

    Methods inherited from class com.google.protobuf.GeneratedMessage

    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, writeStringNoTag

    Methods inherited from class com.google.protobuf.AbstractMessage

    findInitializationErrors, getInitializationErrorString, hashFields, toString

    Methods inherited from class com.google.protobuf.AbstractMessageLite

    addAll, checkByteStringIsUtf8, toByteArray, toByteString, writeDelimitedTo, writeTo

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

    Methods inherited from interface com.google.protobuf.MessageLite

    toByteArray, toByteString, writeDelimitedTo, writeTo

    Methods inherited from interface com.google.protobuf.MessageOrBuilder

    findInitializationErrors, getAllFields, getDescriptorForType, getField, getInitializationErrorString, getOneofFieldDescriptor, getRepeatedField, getRepeatedFieldCount, getUnknownFields, hasField, hasOneof

  • Field Details

    • MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER

      public static final int MAX_REMOVED_SEQUENCE_SIZE_FIELD_NUMBER
      See Also:

    • AVG_NUM_REMOVED_VISITS_FIELD_NUMBER

      public static final int AVG_NUM_REMOVED_VISITS_FIELD_NUMBER
      See Also:

    • BYPASS_FACTOR_FIELD_NUMBER

      public static final int BYPASS_FACTOR_FIELD_NUMBER
      See Also:

  • Method Details

    • getDescriptor

      public static final com.google.protobuf.Descriptors.Descriptor getDescriptor()

    • internalGetFieldAccessorTable

      protected com.google.protobuf.GeneratedMessage.FieldAccessorTable internalGetFieldAccessorTable()
      Specified by:
      internalGetFieldAccessorTable in class com.google.protobuf.GeneratedMessage

    • hasMaxRemovedSequenceSize

      public 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;
      Specified by:
      hasMaxRemovedSequenceSize in interface SISRRuinStrategyOrBuilder
      Returns:
      Whether the maxRemovedSequenceSize field is set.

    • getMaxRemovedSequenceSize

      public 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;
      Specified by:
      getMaxRemovedSequenceSize in interface SISRRuinStrategyOrBuilder
      Returns:
      The maxRemovedSequenceSize.

    • hasAvgNumRemovedVisits

      public 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;
      Specified by:
      hasAvgNumRemovedVisits in interface SISRRuinStrategyOrBuilder
      Returns:
      Whether the avgNumRemovedVisits field is set.

    • getAvgNumRemovedVisits

      public 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;
      Specified by:
      getAvgNumRemovedVisits in interface SISRRuinStrategyOrBuilder
      Returns:
      The avgNumRemovedVisits.

    • hasBypassFactor

      public 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;
      Specified by:
      hasBypassFactor in interface SISRRuinStrategyOrBuilder
      Returns:
      Whether the bypassFactor field is set.

    • getBypassFactor

      public 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;
      Specified by:
      getBypassFactor in interface SISRRuinStrategyOrBuilder
      Returns:
      The bypassFactor.

    • isInitialized

      public final boolean isInitialized()
      Specified by:
      isInitialized in interface com.google.protobuf.MessageLiteOrBuilder
      Overrides:
      isInitialized in class com.google.protobuf.GeneratedMessage

    • writeTo

      public void writeTo(com.google.protobuf.CodedOutputStream output) throws IOException
      Specified by:
      writeTo in interface com.google.protobuf.MessageLite
      Overrides:
      writeTo in class com.google.protobuf.GeneratedMessage
      Throws:
      IOException

    • getSerializedSize

      public int getSerializedSize()
      Specified by:
      getSerializedSize in interface com.google.protobuf.MessageLite
      Overrides:
      getSerializedSize in class com.google.protobuf.GeneratedMessage

    • equals

      public boolean equals(Object obj)
      Specified by:
      equals in interface com.google.protobuf.Message
      Overrides:
      equals in class com.google.protobuf.AbstractMessage

    • hashCode

      public int hashCode()
      Specified by:
      hashCode in interface com.google.protobuf.Message
      Overrides:
      hashCode in class com.google.protobuf.AbstractMessage

    • parseFrom

      public static SISRRuinStrategy parseFrom(ByteBuffer data) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(ByteBuffer data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(com.google.protobuf.ByteString data) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(com.google.protobuf.ByteString data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(byte[] data) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(byte[] data, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws com.google.protobuf.InvalidProtocolBufferException
      Throws:
      com.google.protobuf.InvalidProtocolBufferException

    • parseFrom

      public static SISRRuinStrategy parseFrom(InputStream input) throws IOException
      Throws:
      IOException

    • parseFrom

      public static SISRRuinStrategy parseFrom(InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws IOException
      Throws:
      IOException

    • parseDelimitedFrom

      public static SISRRuinStrategy parseDelimitedFrom(InputStream input) throws IOException
      Throws:
      IOException

    • parseDelimitedFrom

      public static SISRRuinStrategy parseDelimitedFrom(InputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws IOException
      Throws:
      IOException

    • parseFrom

      public static SISRRuinStrategy parseFrom(com.google.protobuf.CodedInputStream input) throws IOException
      Throws:
      IOException

    • parseFrom

      public static SISRRuinStrategy parseFrom(com.google.protobuf.CodedInputStream input, com.google.protobuf.ExtensionRegistryLite extensionRegistry) throws IOException
      Throws:
      IOException

    • newBuilderForType

      public SISRRuinStrategy.Builder newBuilderForType()
      Specified by:
      newBuilderForType in interface com.google.protobuf.Message
      Specified by:
      newBuilderForType in interface com.google.protobuf.MessageLite

    • newBuilder

      public static SISRRuinStrategy.Builder newBuilder()

    • newBuilder

      public static SISRRuinStrategy.Builder newBuilder(SISRRuinStrategy prototype)

    • toBuilder

      public SISRRuinStrategy.Builder toBuilder()
      Specified by:
      toBuilder in interface com.google.protobuf.Message
      Specified by:
      toBuilder in interface com.google.protobuf.MessageLite

    • newBuilderForType

      protected SISRRuinStrategy.Builder newBuilderForType(com.google.protobuf.AbstractMessage.BuilderParent parent)
      Overrides:
      newBuilderForType in class com.google.protobuf.AbstractMessage

    • getDefaultInstance

      public static SISRRuinStrategy getDefaultInstance()

    • parser

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

    • getParserForType

      public com.google.protobuf.Parser<SISRRuinStrategy> getParserForType()
      Specified by:
      getParserForType in interface com.google.protobuf.Message
      Specified by:
      getParserForType in interface com.google.protobuf.MessageLite
      Overrides:
      getParserForType in class com.google.protobuf.GeneratedMessage

    • getDefaultInstanceForType

      public SISRRuinStrategy getDefaultInstanceForType()
      Specified by:
      getDefaultInstanceForType in interface com.google.protobuf.MessageLiteOrBuilder
      Specified by:
      getDefaultInstanceForType in interface com.google.protobuf.MessageOrBuilder