routing_parameters.proto

// Copyright 2010-2014 Google
// 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 the routing library, in particular the
// search parameters such as first solution heuristics and local search
// neighborhoods.

syntax = "proto3";
option java_package = "com.google.ortools.constraintsolver";
option java_multiple_files = true;
option csharp_namespace = "Google.OrTools.ConstraintSolver";

import "constraint_solver/routing_enums.proto";
import "constraint_solver/solver_parameters.proto";

package operations_research;

// Parameters defining the search used to solve vehicle routing problems.
message RoutingSearchParameters {
  // First solution strategies, used as starting point of local search.
  FirstSolutionStrategy.Value first_solution_strategy = 1;
  // These are advanced first solutions strategy settings which should not be
  // modified unless you know what you are doing.
  // Use filtered version of first solution strategy if available.
  bool use_filtered_first_solution_strategy = 2;

  // Local search neighborhood operators used to build a solutions neighborhood.
  message LocalSearchNeighborhoodOperators {
    // --- Intra-route operators ---
    // Operator which moves a single node to another position.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
    // (where (1, 5) are first and last nodes of the path and can therefore not
    // be moved):
    //   1 ->  3  -> [2] ->  4  -> 5
    //   1 ->  3  ->  4  -> [2] -> 5
    //   1 ->  2  ->  4  -> [3] -> 5
    //   1 -> [4] ->  2  ->  3  -> 5
    bool use_relocate = 1;
    // Operator which moves a pair of pickup and delivery nodes to another
    // position where the first node of the pair must be before the second node
    // on the same path.
    // Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are
    // first and last nodes of the path and can therefore not be moved, and
    // (A, B) is a pair of nodes):
    //   1 -> [A] ->  2  -> [B] -> 3
    //   1 ->  2  -> [A] -> [B] -> 3
    bool use_relocate_pair = 2;
    // Relocate neighborhood which moves chains of neighbors.
    // The operator starts by relocating a node n after a node m, then continues
    // moving nodes which were after n as long as the "cost" added is less than
    // the "cost" of the arc (m, n). If the new chain doesn't respect the domain
    // of next variables, it will try reordering the nodes until it finds a
    // valid path.
    // Possible neighbors for path 1 -> A -> B -> C -> D -> E -> 2 (where (1, 2)
    // are first and last nodes of the path and can therefore not be moved, A
    // must be performed before B, and A, D and E are located at the same
    // place):
    // 1 -> A -> C -> [B] -> D -> E -> 2
    // 1 -> A -> C -> D -> [B] -> E -> 2
    // 1 -> A -> C -> D -> E -> [B] -> 2
    // 1 -> A -> B -> D -> [C] -> E -> 2
    // 1 -> A -> B -> D -> E -> [C] -> 2
    // 1 -> A -> [D] -> [E] -> B -> C -> 2
    // 1 -> A -> B -> [D] -> [E] ->  C -> 2
    // 1 -> A -> [E] -> B -> C -> D -> 2
    // 1 -> A -> B -> [E] -> C -> D -> 2
    // 1 -> A -> B -> C -> [E] -> D -> 2
    // This operator is extremelly useful to move chains of nodes which are
    // located at the same place (for instance nodes part of a same stop).
    bool use_relocate_neighbors = 3;
    // Operator which exchanges the positions of two nodes.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
    // (where (1, 5) are first and last nodes of the path and can therefore not
    // be moved):
    //   1 -> [3] -> [2] ->  4  -> 5
    //   1 -> [4] ->  3  -> [2] -> 5
    //   1 ->  2  -> [4] -> [3] -> 5
    bool use_exchange = 4;
    // Operator which cross exchanges the starting chains of 2 paths, including
    // exchanging the whole paths.
    // First and last nodes are not moved.
    // Possible neighbors for the paths 1 -> 2 -> 3 -> 4 -> 5 and 6 -> 7 -> 8
    // (where (1, 5) and (6, 8) are first and last nodes of the paths and can
    // therefore not be moved):
    //   1 -> [7] -> 3 -> 4 -> 5  6 -> [2] -> 8
    //   1 -> [7] -> 4 -> 5       6 -> [2 -> 3] -> 8
    //   1 -> [7] -> 5            6 -> [2 -> 3 -> 4] -> 8
    bool use_cross = 5;
    // Not implemented as of 10/2015.
    bool use_cross_exchange = 6;
    // --- Inter-route operators ---
    // Operator which reverves a sub-chain of a path. It is called TwoOpt
    // because it breaks two arcs on the path; resulting paths are called
    // two-optimal.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5
    // (where (1, 5) are first and last nodes of the path and can therefore not
    // be moved):
    //   1 -> [3 -> 2] -> 4  -> 5
    //   1 -> [4 -> 3  -> 2] -> 5
    //   1 ->  2 -> [4 -> 3] -> 5
    bool use_two_opt = 7;
    // Operator which moves sub-chains of a path of length 1, 2 and 3 to another
    // position in the same path.
    // When the length of the sub-chain is 1, the operator simply moves a node
    // to another position.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a sub-chain
    // length of 2 (where (1, 5) are first and last nodes of the path and can
    // therefore not be moved):
    //   1 ->  4 -> [2 -> 3] -> 5
    //   1 -> [3 -> 4] -> 2  -> 5
    // The OR_OPT operator is a limited version of 3-Opt (breaks 3 arcs on a
    // path).
    bool use_or_opt = 8;
    // Lin-Kernighan operator.
    // While the accumulated local gain is positive, performs a 2-OPT or a 3-OPT
    // move followed by a series of 2-OPT moves. Returns a neighbor for which
    // the global gain is positive.
    bool use_lin_kernighan = 9;
    // Sliding TSP operator.
    // Uses an exact dynamic programming algorithm to solve the TSP
    // corresponding to path sub-chains.
    // For a subchain 1 -> 2 -> 3 -> 4 -> 5 -> 6, solves the TSP on
    // nodes A, 2, 3, 4, 5, where A is a merger of nodes 1 and 6 such that
    // cost(A,i) = cost(1,i) and cost(i,A) = cost(i,6).
    bool use_tsp_opt = 10;
    // --- Operators on unactive nodes ---
    // Operator which inserts an inactive node into a path.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
    // (where 1 and 4 are first and last nodes of the path) are:
    //   1 -> [5] ->  2  ->  3  -> 4
    //   1 ->  2  -> [5] ->  3  -> 4
    //   1 ->  2  ->  3  -> [5] -> 4
    bool use_make_active = 11;
    // Operator which makes path nodes inactive.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first
    // and last nodes of the path) are:
    //   1 -> 3 -> 4 with 2 inactive
    //   1 -> 2 -> 4 with 3 inactive
    bool use_make_inactive = 12;
    // Operator which makes a "chain" of path nodes inactive.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first
    // and last nodes of the path) are:
    //   1 -> 3 -> 4 with 2 inactive
    //   1 -> 2 -> 4 with 3 inactive
    //   1 -> 4 with 2 and 3 inactive
    bool use_make_chain_inactive = 13;
    // Operator which replaces an active node by an inactive one.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
    // (where 1 and 4 are first and last nodes of the path) are:
    //   1 -> [5] ->  3  -> 4 with 2 inactive
    //   1 ->  2  -> [5] -> 4 with 3 inactive
    bool use_swap_active = 14;
    // Operator which makes an inactive node active and an active one inactive.
    // It is similar to SwapActiveOperator excepts that it tries to insert the
    // inactive node in all possible positions instead of just the position of
    // the node made inactive.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
    // (where 1 and 4 are first and last nodes of the path) are:
    //   1 -> [5] ->  3  -> 4 with 2 inactive
    //   1 ->  3  -> [5] -> 4 with 2 inactive
    //   1 -> [5] ->  2  -> 4 with 3 inactive
    //   1 ->  2  -> [5] -> 4 with 3 inactive
    bool use_extended_swap_active = 15;
    // Operator which makes an inactive node active and an active pair of nodes
    // inactive OR makes an inactive pair of nodes active and an active node
    // inactive.
    // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive
    // (where 1 and 4 are first and last nodes of the path and (2,3) is a pair
    // of nodes) are:
    //   1 -> [5] -> 4 with (2,3) inactive
    // Possible neighbors for the path 1 -> 2 -> 3 with (4,5) inactive
    // (where 1 and 3 are first and last nodes of the path and (4,5) is a pair
    // of nodes) are:
    //   1 -> [4] -> [5] -> 3 with 2 inactive
    bool use_node_pair_swap_active = 20;
    // --- Large neighborhood search operators ---
    // Operator which relaxes two sub-chains of three consecutive arcs each.
    // Each sub-chain is defined by a start node and the next three arcs. Those
    // six arcs are relaxed to build a new neighbor.
    // PATH_LNS explores all possible pairs of starting nodes and so defines
    // n^2 neighbors, n being the number of nodes.
    // Note that the two sub-chains can be part of the same path; they even may
    // overlap.
    bool use_path_lns = 16;
    // Operator which relaxes one entire path and all unactive nodes.
    bool use_full_path_lns = 17;
    // TSP-base LNS.
    // Randomly merges consecutive nodes until n "meta"-nodes remain and solves
    // the corresponding TSP.
    // This defines an "unlimited" neighborhood which must be stopped by search
    // limits. To force diversification, the operator iteratively forces each
    // node to serve as base of a meta-node.
    bool use_tsp_lns = 18;
    // Operator which relaxes all inactive nodes and one sub-chain of six
    // consecutive arcs. That way the path can be improved by inserting inactive
    // nodes or swaping arcs.
    bool use_inactive_lns = 19;
  }
  LocalSearchNeighborhoodOperators local_search_operators = 3;

  // Local search metaheuristics used to guide the search.
  LocalSearchMetaheuristic.Value local_search_metaheuristic = 4;
  // These are advanced settings which should not be modified unless you know
  // what you are doing.
  // Lambda coefficient used to penalize arc costs when GUIDED_LOCAL_SEARCH is
  // used.
  double guided_local_search_lambda_coefficient = 5;

  // --- Search control ---
  // If true, the solver should use depth-first search rather than local search
  // to solve the problem.
  bool use_depth_first_search = 6;
  // Minimum step by which the solution must be improved in local search.
  int64 optimization_step = 7;
  // -- Search limits --
  // Limit to the number of solutions generated during the search.
  int64 solution_limit = 8;
  // Limit in milliseconds to the time spent in the search.
  int64 time_limit_ms = 9;
  // Limit in milliseconds to the time spent in the completion search for each
  // local search neighbor.
  int64 lns_time_limit_ms = 10;

  // --- Propagation control ---
  // These are advanced settings which should not be modified unless you know
  // what you are doing.
  // Use constraints with light propagation in routing model. Extra propagation
  // is only necessary when using depth-first search or for models which
  // require strong propagation to finalize the value of secondary variables.
  // Changing this setting to true will slow down the search in most cases and
  // increase memory consumption in all cases.
  bool use_light_propagation = 11;

  // --- Miscellaneous ---
  // Some of these are advanced settings which should not be modified unless you
  // know what you are doing.
  // If true, arc cost evaluators will be fingerprinted. The fingerprint will
  // be used when computing vehicle cost equivalent classes, otherwise the
  // address of the evaluator will be used.
  bool fingerprint_arc_cost_evaluators = 12;
  // Activates search logging. For each solution found during the search, the
  // following will be displayed: its objective value, the maximum objective
  // value since the beginning of the search, the elapsed time since the
  // beginning of the search, the number of branches explored in the search
  // tree, the number of failures in the search tree, the depth of the search
  // tree, the number of local search neighbors explored, the number of local
  // search neighbors filtered by local search filters, the number of local
  // search neighbors accepted, the total memory used and the percentage of the
  // search done.
  bool log_search = 13;
}

// Parameters which have to be set when creating a RoutingModel.
message RoutingModelParameters {
  // Parameters to use in the underlying constraint solver.
  ConstraintSolverParameters solver_parameters = 1;
  // Advanced settings.
  // If set to true reduction of the underlying constraint model will be
  // attempted when all vehicles have exactly the same cost structure. This can
  // result in significant speedups.
  bool reduce_vehicle_cost_model = 2;
  // Cache callback calls if the number of nodes in the model is less or equal
  // to this value.
  int32 max_callback_cache_size = 3;
}