routing_ils.proto

// Copyright 2010-2024 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Protocol buffer used to parametrize an iterated local search (ILS) approach.
// ILS is an iterative metaheuristic in which every iteration consists in
// performing a perturbation followed by an improvement step on a reference
// solution to generate a neighbor solution.
// The neighbor solution is accepted as the new reference solution according
// to an acceptance criterion.
// The best found solution is eventually returned.

syntax = "proto3";

import "ortools/constraint_solver/routing_enums.proto";

package operations_research;

// Ruin strategies, used in perturbation based on ruin and recreate approaches.
message RuinStrategy {
  enum Value {
    // Unspecified value.
    UNSET = 0;

    // Removes a number of spatially close routes.
    SPATIALLY_CLOSE_ROUTES_REMOVAL = 1;
  }
}

// Parameters to configure a perturbation based on a ruin and recreate approach.
message RuinRecreateParameters {
  // Strategy defining how a reference solution is ruined.
  RuinStrategy.Value ruin_strategy = 1;

  // Strategy defining how a reference solution is recreated.
  FirstSolutionStrategy.Value recreate_strategy = 2;

  // Number of routes removed during a ruin application defined on routes.
  uint32 num_ruined_routes = 3;
}

// Defines how a reference solution is perturbed.
message PerturbationStrategy {
  enum Value {
    // Unspecified value.
    UNSET = 0;

    // Performs a perturbation in a ruin and recreate fashion.
    RUIN_AND_RECREATE = 1;
  }
}

// Determines when a neighbor solution, obtained by the application of a
// perturbation and improvement step to a reference solution, is used to
// replace the reference solution.
message AcceptanceStrategy {
  enum Value {
    // Unspecified value.
    UNSET = 0;

    // Accept only solutions that are improving with respect to the reference
    // one.
    GREEDY_DESCENT = 1;
  }
}

// Specifies the behavior of a search based on ILS.
message IteratedLocalSearchParameters {
  // Determines how a reference solution S is perturbed to obtain a neighbor
  // solution S'.
  PerturbationStrategy.Value perturbation_strategy = 1;

  // Parameters to customize a ruin and recreate perturbation.
  RuinRecreateParameters ruin_recreate_parameters = 2;

  // Determines whether solution S', obtained from the perturbation, should be
  // optimized with a local search application.
  bool improve_perturbed_solution = 3;

  // Determines when the neighbor solution S', possibly improved if
  // `improve_perturbed_solution` is true, replaces the reference solution S.
  AcceptanceStrategy.Value acceptance_strategy = 4;
}