1// Copyright 2010-2021 Google LLC 2// Licensed under the Apache License, Version 2.0 (the "License"); 3// you may not use this file except in compliance with the License. 4// You may obtain a copy of the License at 5// 6// http://www.apache.org/licenses/LICENSE-2.0 7// 8// Unless required by applicable law or agreed to in writing, software 9// distributed under the License is distributed on an "AS IS" BASIS, 10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11// See the License for the specific language governing permissions and 12// limitations under the License. 13 14// Protocol buffer used to parametrize the routing library, in particular the 15// search parameters such as first solution heuristics and local search 16// neighborhoods. 17 18syntax = "proto3"; 19 20option java_package = "com.google.ortools.constraintsolver"; 21option java_multiple_files = true; 22option csharp_namespace = "Google.OrTools.ConstraintSolver"; 23 24import "google/protobuf/duration.proto"; 25import "ortools/constraint_solver/routing_enums.proto"; 26import "ortools/constraint_solver/solver_parameters.proto"; 27import "ortools/sat/sat_parameters.proto"; 28import "ortools/util/optional_boolean.proto"; 29 30package operations_research; 31 32// Parameters defining the search used to solve vehicle routing problems. 33// 34// If a parameter is unset (or, equivalently, set to its default value), 35// then the routing library will pick its preferred value for that parameter 36// automatically: this should be the case for most parameters. 37// To see those "default" parameters, call GetDefaultRoutingSearchParameters(). 38// Next ID: 49 39message RoutingSearchParameters { 40 // First solution strategies, used as starting point of local search. 41 FirstSolutionStrategy.Value first_solution_strategy = 1; 42 43 // --- Advanced first solutions strategy settings --- 44 // Don't touch these unless you know what you are doing. 45 // 46 // Use filtered version of first solution strategy if available. 47 bool use_unfiltered_first_solution_strategy = 2; 48 // Parameters specific to the Savings first solution heuristic. 49 // Ratio (in ]0, 1]) of neighbors to consider for each node when constructing 50 // the savings. If unspecified, its value is considered to be 1.0. 51 double savings_neighbors_ratio = 14; 52 // The number of neighbors considered for each node in the Savings heuristic 53 // is chosen so that the space used to store the savings doesn't exceed 54 // savings_max_memory_usage_bytes, which must be in ]0, 1e10]. 55 // NOTE: If both savings_neighbors_ratio and savings_max_memory_usage_bytes 56 // are specified, the number of neighbors considered for each node will be the 57 // minimum of the two numbers determined by these parameters. 58 double savings_max_memory_usage_bytes = 23; 59 // Add savings related to reverse arcs when finding the nearest neighbors 60 // of the nodes. 61 bool savings_add_reverse_arcs = 15; 62 // Coefficient of the cost of the arc for which the saving value is being 63 // computed: 64 // Saving(a-->b) = Cost(a-->end) + Cost(start-->b) 65 // - savings_arc_coefficient * Cost(a-->b) 66 // This parameter must be greater than 0, and its default value is 1. 67 double savings_arc_coefficient = 18; 68 // When true, the routes are built in parallel, sequentially otherwise. 69 bool savings_parallel_routes = 19; 70 71 // Ratio (between 0 and 1) of available vehicles in the model on which 72 // farthest nodes of the model are inserted as seeds in the 73 // GlobalCheapestInsertion first solution heuristic. 74 double cheapest_insertion_farthest_seeds_ratio = 16; 75 76 // Ratio (in ]0, 1]) of closest non start/end nodes to consider as neighbors 77 // for each node when creating new insertions in the parallel/sequential 78 // cheapest insertion heuristic. 79 // If not overridden, its default value is 1, meaning all neighbors will be 80 // considered. 81 // The neighborhood ratio is coupled with the corresponding min_neighbors 82 // integer, indicating the minimum number of neighbors to consider for each 83 // node: 84 // num_closest_neighbors = 85 // max(min_neighbors, neighbors_ratio * NUM_NON_START_END_NODES) 86 // This minimum number of neighbors must be greater or equal to 1, its 87 // default value. 88 // 89 // Neighbors ratio and minimum number of neighbors for the first solution 90 // heuristic. 91 double cheapest_insertion_first_solution_neighbors_ratio = 21; 92 int32 cheapest_insertion_first_solution_min_neighbors = 44; 93 // Neighbors ratio and minimum number of neighbors for the heuristic when used 94 // in a local search operator (see 95 // local_search_operators.use_global_cheapest_insertion_path_lns and 96 // local_search_operators.use_global_cheapest_insertion_chain_lns below). 97 double cheapest_insertion_ls_operator_neighbors_ratio = 31; 98 int32 cheapest_insertion_ls_operator_min_neighbors = 45; 99 100 // Whether or not to only consider closest neighbors when initializing the 101 // assignment for the first solution. 102 bool 103 cheapest_insertion_first_solution_use_neighbors_ratio_for_initialization = 104 46; 105 // Whether or not to consider entries making the nodes/pairs unperformed in 106 // the GlobalCheapestInsertion heuristic. 107 bool cheapest_insertion_add_unperformed_entries = 40; 108 109 // If true use minimum matching instead of minimal matching in the 110 // Christofides algorithm. 111 bool christofides_use_minimum_matching = 30; 112 113 // Local search neighborhood operators used to build a solutions neighborhood. 114 // Next ID: 34 115 message LocalSearchNeighborhoodOperators { 116 // --- Inter-route operators --- 117 // Operator which moves a single node to another position. 118 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 119 // (where (1, 5) are first and last nodes of the path and can therefore not 120 // be moved): 121 // 1 -> 3 -> [2] -> 4 -> 5 122 // 1 -> 3 -> 4 -> [2] -> 5 123 // 1 -> 2 -> 4 -> [3] -> 5 124 // 1 -> [4] -> 2 -> 3 -> 5 125 OptionalBoolean use_relocate = 1; 126 // Operator which moves a pair of pickup and delivery nodes to another 127 // position where the first node of the pair must be before the second node 128 // on the same path. Compared to the light_relocate_pair operator, tries all 129 // possible positions of insertion of a pair (not only after another pair). 130 // Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are 131 // first and last nodes of the path and can therefore not be moved, and 132 // (A, B) is a pair of nodes): 133 // 1 -> [A] -> 2 -> [B] -> 3 134 // 1 -> 2 -> [A] -> [B] -> 3 135 OptionalBoolean use_relocate_pair = 2; 136 // Operator which moves a pair of pickup and delivery nodes after another 137 // pair. 138 // Possible neighbors for paths 1 -> A -> B -> 2, 3 -> C -> D -> 4 (where 139 // (1, 2) and (3, 4) are first and last nodes of paths and can therefore not 140 // be moved, and (A, B) and (C, D) are pair of nodes): 141 // 1 -> 2, 3 -> C -> [A] -> D -> [B] -> 4 142 // 1 -> A -> [C] -> B -> [D] -> 2, 3 -> 4 143 OptionalBoolean use_light_relocate_pair = 24; 144 // Relocate neighborhood which moves chains of neighbors. 145 // The operator starts by relocating a node n after a node m, then continues 146 // moving nodes which were after n as long as the "cost" added is less than 147 // the "cost" of the arc (m, n). If the new chain doesn't respect the domain 148 // of next variables, it will try reordering the nodes until it finds a 149 // valid path. 150 // Possible neighbors for path 1 -> A -> B -> C -> D -> E -> 2 (where (1, 2) 151 // are first and last nodes of the path and can therefore not be moved, A 152 // must be performed before B, and A, D and E are located at the same 153 // place): 154 // 1 -> A -> C -> [B] -> D -> E -> 2 155 // 1 -> A -> C -> D -> [B] -> E -> 2 156 // 1 -> A -> C -> D -> E -> [B] -> 2 157 // 1 -> A -> B -> D -> [C] -> E -> 2 158 // 1 -> A -> B -> D -> E -> [C] -> 2 159 // 1 -> A -> [D] -> [E] -> B -> C -> 2 160 // 1 -> A -> B -> [D] -> [E] -> C -> 2 161 // 1 -> A -> [E] -> B -> C -> D -> 2 162 // 1 -> A -> B -> [E] -> C -> D -> 2 163 // 1 -> A -> B -> C -> [E] -> D -> 2 164 // This operator is extremely useful to move chains of nodes which are 165 // located at the same place (for instance nodes part of a same stop). 166 OptionalBoolean use_relocate_neighbors = 3; 167 // Relocate neighborhood that moves subpaths all pickup and delivery 168 // pairs have both pickup and delivery inside the subpath or both outside 169 // the subpath. For instance, for given paths: 170 // 0 -> A -> B -> A' -> B' -> 5 -> 6 -> 8 171 // 7 -> 9 172 // Pairs (A,A') and (B,B') are interleaved, so the expected neighbors are: 173 // 0 -> 5 -> A -> B -> A' -> B' -> 6 -> 8 174 // 7 -> 9 175 // 176 // 0 -> 5 -> 6 -> A -> B -> A' -> B' -> 8 177 // 7 -> 9 178 // 179 // 0 -> 5 -> 6 -> 8 180 // 7 -> A -> B -> A' -> B' -> 9 181 OptionalBoolean use_relocate_subtrip = 25; 182 // Operator which exchanges the positions of two nodes. 183 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 184 // (where (1, 5) are first and last nodes of the path and can therefore not 185 // be moved): 186 // 1 -> [3] -> [2] -> 4 -> 5 187 // 1 -> [4] -> 3 -> [2] -> 5 188 // 1 -> 2 -> [4] -> [3] -> 5 189 OptionalBoolean use_exchange = 4; 190 // Operator which exchanges the positions of two pair of nodes. Pairs 191 // correspond to the pickup and delivery pairs defined in the routing model. 192 // Possible neighbor for the paths 193 // 1 -> A -> B -> 2 -> 3 and 4 -> C -> D -> 5 194 // (where (1, 3) and (4, 5) are first and last nodes of the paths and can 195 // therefore not be moved, and (A, B) and (C,D) are pairs of nodes): 196 // 1 -> [C] -> [D] -> 2 -> 3, 4 -> [A] -> [B] -> 5 197 OptionalBoolean use_exchange_pair = 22; 198 // Operator which exchanges subtrips associated to two pairs of nodes, 199 // see use_relocate_subtrip for a definition of subtrips. 200 OptionalBoolean use_exchange_subtrip = 26; 201 // Operator which cross exchanges the starting chains of 2 paths, including 202 // exchanging the whole paths. 203 // First and last nodes are not moved. 204 // Possible neighbors for the paths 1 -> 2 -> 3 -> 4 -> 5 and 6 -> 7 -> 8 205 // (where (1, 5) and (6, 8) are first and last nodes of the paths and can 206 // therefore not be moved): 207 // 1 -> [7] -> 3 -> 4 -> 5 6 -> [2] -> 8 208 // 1 -> [7] -> 4 -> 5 6 -> [2 -> 3] -> 8 209 // 1 -> [7] -> 5 6 -> [2 -> 3 -> 4] -> 8 210 OptionalBoolean use_cross = 5; 211 // Not implemented yet. TODO(b/68128619): Implement. 212 OptionalBoolean use_cross_exchange = 6; 213 // Operator which detects the relocate_expensive_chain_num_arcs_to_consider 214 // most expensive arcs on a path, and moves the chain resulting from cutting 215 // pairs of arcs among these to another position. 216 // Possible neighbors for paths 1 -> 2 (empty) and 217 // 3 -> A ------> B --> C -----> D -> 4 (where A -> B and C -> D are the 2 218 // most expensive arcs, and the chain resulting from breaking them is 219 // B -> C): 220 // 1 -> [B -> C] -> 2 3 -> A -> D -> 4 221 // 1 -> 2 3 -> [B -> C] -> A -> D -> 4 222 // 1 -> 2 3 -> A -> D -> [B -> C] -> 4 223 OptionalBoolean use_relocate_expensive_chain = 23; 224 // --- Intra-route operators --- 225 // Operator which reverses a subchain of a path. It is called TwoOpt 226 // because it breaks two arcs on the path; resulting paths are called 227 // two-optimal. 228 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5 229 // (where (1, 5) are first and last nodes of the path and can therefore not 230 // be moved): 231 // 1 -> [3 -> 2] -> 4 -> 5 232 // 1 -> [4 -> 3 -> 2] -> 5 233 // 1 -> 2 -> [4 -> 3] -> 5 234 OptionalBoolean use_two_opt = 7; 235 // Operator which moves sub-chains of a path of length 1, 2 and 3 to another 236 // position in the same path. 237 // When the length of the sub-chain is 1, the operator simply moves a node 238 // to another position. 239 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 -> 5, for a sub-chain 240 // length of 2 (where (1, 5) are first and last nodes of the path and can 241 // therefore not be moved): 242 // 1 -> 4 -> [2 -> 3] -> 5 243 // 1 -> [3 -> 4] -> 2 -> 5 244 // The OR_OPT operator is a limited version of 3-Opt (breaks 3 arcs on a 245 // path). 246 OptionalBoolean use_or_opt = 8; 247 // Lin-Kernighan operator. 248 // While the accumulated local gain is positive, performs a 2-OPT or a 3-OPT 249 // move followed by a series of 2-OPT moves. Returns a neighbor for which 250 // the global gain is positive. 251 OptionalBoolean use_lin_kernighan = 9; 252 // Sliding TSP operator. 253 // Uses an exact dynamic programming algorithm to solve the TSP 254 // corresponding to path sub-chains. 255 // For a subchain 1 -> 2 -> 3 -> 4 -> 5 -> 6, solves the TSP on 256 // nodes A, 2, 3, 4, 5, where A is a merger of nodes 1 and 6 such that 257 // cost(A,i) = cost(1,i) and cost(i,A) = cost(i,6). 258 OptionalBoolean use_tsp_opt = 10; 259 // --- Operators on inactive nodes --- 260 // Operator which inserts an inactive node into a path. 261 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive 262 // (where 1 and 4 are first and last nodes of the path) are: 263 // 1 -> [5] -> 2 -> 3 -> 4 264 // 1 -> 2 -> [5] -> 3 -> 4 265 // 1 -> 2 -> 3 -> [5] -> 4 266 OptionalBoolean use_make_active = 11; 267 // Operator which relocates a node while making an inactive one active. 268 // As of 3/2017, the operator is limited to two kinds of moves: 269 // - Relocating a node and replacing it by an inactive node. 270 // Possible neighbor for path 1 -> 5, 2 -> 3 -> 6 and 4 inactive 271 // (where 1,2 and 5,6 are first and last nodes of paths) is: 272 // 1 -> 3 -> 5, 2 -> 4 -> 6. 273 // - Relocating a node and inserting an inactive node next to it. 274 // Possible neighbor for path 1 -> 5, 2 -> 3 -> 6 and 4 inactive 275 // (where 1,2 and 5,6 are first and last nodes of paths) is: 276 // 1 -> 4 -> 3 -> 5, 2 -> 6. 277 OptionalBoolean use_relocate_and_make_active = 21; 278 // Operator which makes path nodes inactive. 279 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first 280 // and last nodes of the path) are: 281 // 1 -> 3 -> 4 with 2 inactive 282 // 1 -> 2 -> 4 with 3 inactive 283 OptionalBoolean use_make_inactive = 12; 284 // Operator which makes a "chain" of path nodes inactive. 285 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 (where 1 and 4 are first 286 // and last nodes of the path) are: 287 // 1 -> 3 -> 4 with 2 inactive 288 // 1 -> 2 -> 4 with 3 inactive 289 // 1 -> 4 with 2 and 3 inactive 290 OptionalBoolean use_make_chain_inactive = 13; 291 // Operator which replaces an active node by an inactive one. 292 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive 293 // (where 1 and 4 are first and last nodes of the path) are: 294 // 1 -> [5] -> 3 -> 4 with 2 inactive 295 // 1 -> 2 -> [5] -> 4 with 3 inactive 296 OptionalBoolean use_swap_active = 14; 297 // Operator which makes an inactive node active and an active one inactive. 298 // It is similar to SwapActiveOperator excepts that it tries to insert the 299 // inactive node in all possible positions instead of just the position of 300 // the node made inactive. 301 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive 302 // (where 1 and 4 are first and last nodes of the path) are: 303 // 1 -> [5] -> 3 -> 4 with 2 inactive 304 // 1 -> 3 -> [5] -> 4 with 2 inactive 305 // 1 -> [5] -> 2 -> 4 with 3 inactive 306 // 1 -> 2 -> [5] -> 4 with 3 inactive 307 OptionalBoolean use_extended_swap_active = 15; 308 // Operator which makes an inactive node active and an active pair of nodes 309 // inactive OR makes an inactive pair of nodes active and an active node 310 // inactive. 311 // Possible neighbors for the path 1 -> 2 -> 3 -> 4 with 5 inactive 312 // (where 1 and 4 are first and last nodes of the path and (2,3) is a pair 313 // of nodes) are: 314 // 1 -> [5] -> 4 with (2,3) inactive 315 // Possible neighbors for the path 1 -> 2 -> 3 with (4,5) inactive 316 // (where 1 and 3 are first and last nodes of the path and (4,5) is a pair 317 // of nodes) are: 318 // 1 -> [4] -> [5] -> 3 with 2 inactive 319 OptionalBoolean use_node_pair_swap_active = 20; 320 // --- Large neighborhood search operators --- 321 // Operator which relaxes two sub-chains of three consecutive arcs each. 322 // Each sub-chain is defined by a start node and the next three arcs. Those 323 // six arcs are relaxed to build a new neighbor. 324 // PATH_LNS explores all possible pairs of starting nodes and so defines 325 // n^2 neighbors, n being the number of nodes. 326 // Note that the two sub-chains can be part of the same path; they even may 327 // overlap. 328 OptionalBoolean use_path_lns = 16; 329 // Operator which relaxes one entire path and all inactive nodes. 330 OptionalBoolean use_full_path_lns = 17; 331 // TSP-base LNS. 332 // Randomly merges consecutive nodes until n "meta"-nodes remain and solves 333 // the corresponding TSP. 334 // This defines an "unlimited" neighborhood which must be stopped by search 335 // limits. To force diversification, the operator iteratively forces each 336 // node to serve as base of a meta-node. 337 OptionalBoolean use_tsp_lns = 18; 338 // Operator which relaxes all inactive nodes and one sub-chain of six 339 // consecutive arcs. That way the path can be improved by inserting inactive 340 // nodes or swapping arcs. 341 OptionalBoolean use_inactive_lns = 19; 342 // --- LNS-like large neighborhood search operators using heuristics --- 343 // Operator which makes all nodes on a route unperformed, and reinserts them 344 // using the GlobalCheapestInsertion heuristic. 345 OptionalBoolean use_global_cheapest_insertion_path_lns = 27; 346 // Same as above but using LocalCheapestInsertion as a heuristic. 347 OptionalBoolean use_local_cheapest_insertion_path_lns = 28; 348 // The following operator relocates an entire route to an empty path and 349 // then tries to insert the unperformed nodes using the global cheapest 350 // insertion heuristic. 351 OptionalBoolean 352 use_relocate_path_global_cheapest_insertion_insert_unperformed = 33; 353 // This operator finds heuristic_expensive_chain_lns_num_arcs_to_consider 354 // most expensive arcs on a route, makes the nodes in between pairs of these 355 // expensive arcs unperformed, and reinserts them using the 356 // GlobalCheapestInsertion heuristic. 357 OptionalBoolean use_global_cheapest_insertion_expensive_chain_lns = 29; 358 // Same as above but using LocalCheapestInsertion as a heuristic for 359 // insertion. 360 OptionalBoolean use_local_cheapest_insertion_expensive_chain_lns = 30; 361 // The following operator makes a node and its 362 // heuristic_close_nodes_lns_num_nodes closest neighbors unperformed along 363 // with each of their corresponding performed pickup/delivery pairs, and 364 // then reinserts them using the GlobalCheapestInsertion heuristic. 365 OptionalBoolean use_global_cheapest_insertion_close_nodes_lns = 31; 366 // Same as above, but insertion positions for nodes are determined by the 367 // LocalCheapestInsertion heuristic. 368 OptionalBoolean use_local_cheapest_insertion_close_nodes_lns = 32; 369 } 370 LocalSearchNeighborhoodOperators local_search_operators = 3; 371 372 // If true, the solver will use multi-armed bandit concatenate operators. It 373 // dynamically chooses the next neighbor operator in order to get the best 374 // objective improvement. 375 bool use_multi_armed_bandit_concatenate_operators = 41; 376 377 // Memory coefficient related to the multi-armed bandit compound operator. 378 // Sets how much the objective improvement of previous accepted neighbors 379 // influence the current average improvement. 380 // This parameter should be between 0 and 1. 381 double multi_armed_bandit_compound_operator_memory_coefficient = 42; 382 383 // Positive parameter defining the exploration coefficient of the multi-armed 384 // bandit compound operator. Sets how often we explore rarely used and 385 // unsuccessful in the past operators 386 double multi_armed_bandit_compound_operator_exploration_coefficient = 43; 387 388 // Number of expensive arcs to consider cutting in the RelocateExpensiveChain 389 // neighborhood operator (see 390 // LocalSearchNeighborhoodOperators.use_relocate_expensive_chain()). 391 // This parameter must be greater than 2. 392 // NOTE(user): The number of neighbors generated by the operator for 393 // relocate_expensive_chain_num_arcs_to_consider = K is around 394 // K*(K-1)/2 * number_of_routes * number_of_nodes. 395 int32 relocate_expensive_chain_num_arcs_to_consider = 20; 396 397 // Number of expensive arcs to consider cutting in the 398 // FilteredHeuristicExpensiveChainLNSOperator operator. 399 int32 heuristic_expensive_chain_lns_num_arcs_to_consider = 32; 400 401 // Number of closest nodes to consider for each node during the destruction 402 // phase of the FilteredHeuristicCloseNodesLNSOperator. 403 int32 heuristic_close_nodes_lns_num_nodes = 35; 404 405 // Local search metaheuristics used to guide the search. 406 LocalSearchMetaheuristic.Value local_search_metaheuristic = 4; 407 // These are advanced settings which should not be modified unless you know 408 // what you are doing. 409 // Lambda coefficient used to penalize arc costs when GUIDED_LOCAL_SEARCH is 410 // used. Must be positive. 411 double guided_local_search_lambda_coefficient = 5; 412 413 // --- Search control --- 414 // 415 // If true, the solver should use depth-first search rather than local search 416 // to solve the problem. 417 bool use_depth_first_search = 6; 418 // If true, use the CP solver to find a solution. Either local or depth-first 419 // search will be used depending on the value of use_depth_first_search. Will 420 // be run before the CP-SAT solver (cf. use_cp_sat). 421 OptionalBoolean use_cp = 28; 422 // If true, use the CP-SAT solver to find a solution. If use_cp is also true, 423 // the CP-SAT solver will be run after the CP solver if there is time 424 // remaining and will use the CP solution as a hint for the CP-SAT search. 425 // As of 5/2019, only TSP models can be solved. 426 OptionalBoolean use_cp_sat = 27; 427 // If true, use the CP-SAT solver to find a solution on generalized routing 428 // model. If use_cp is also true, the CP-SAT solver will be run after the CP 429 // solver if there is time remaining and will use the CP solution as a hint 430 // for the CP-SAT search. 431 OptionalBoolean use_generalized_cp_sat = 47; 432 // If use_cp_sat or use_generalized_cp_sat is true, contains the SAT algorithm 433 // parameters which will be used. 434 sat.SatParameters sat_parameters = 48; 435 // Underlying solver to use in dimension scheduling, respectively for 436 // continuous and mixed models. 437 enum SchedulingSolver { 438 UNSET = 0; 439 GLOP = 1; 440 CP_SAT = 2; 441 } 442 SchedulingSolver continuous_scheduling_solver = 33; 443 SchedulingSolver mixed_integer_scheduling_solver = 34; 444 // Minimum step by which the solution must be improved in local search. 0 445 // means "unspecified". If this value is fractional, it will get rounded to 446 // the nearest integer. 447 double optimization_step = 7; 448 // Number of solutions to collect during the search. Corresponds to the best 449 // solutions found during the search. 0 means "unspecified". 450 int32 number_of_solutions_to_collect = 17; 451 // -- Search limits -- 452 // Limit to the number of solutions generated during the search. 0 means 453 // "unspecified". 454 int64 solution_limit = 8; 455 // Limit to the time spent in the search. 456 google.protobuf.Duration time_limit = 9; 457 // Limit to the time spent in the completion search for each local search 458 // neighbor. 459 google.protobuf.Duration lns_time_limit = 10; 460 461 // Parameters required for the improvement search limit. 462 message ImprovementSearchLimitParameters { 463 // Parameter that regulates exchange rate between objective improvement and 464 // number of neighbors spent. The smaller the value, the sooner the limit 465 // stops the search. Must be positive. 466 double improvement_rate_coefficient = 38; 467 // Parameter that specifies the distance between improvements taken into 468 // consideration for calculating the improvement rate. 469 // Example: For 5 objective improvements = (10, 8, 6, 4, 2), and the 470 // solutions_distance parameter of 2, then the improvement_rate will be 471 // computed for (10, 6), (8, 4), and (6, 2). 472 int32 improvement_rate_solutions_distance = 39; 473 } 474 // The improvement search limit is added to the solver if the following 475 // parameters are set. 476 ImprovementSearchLimitParameters improvement_limit_parameters = 37; 477 478 // --- Propagation control --- 479 // These are advanced settings which should not be modified unless you know 480 // what you are doing. 481 // 482 // Use constraints with full propagation in routing model (instead of 'light' 483 // propagation only). Full propagation is only necessary when using 484 // depth-first search or for models which require strong propagation to 485 // finalize the value of secondary variables. 486 // Changing this setting to true will slow down the search in most cases and 487 // increase memory consumption in all cases. 488 bool use_full_propagation = 11; 489 490 // --- Miscellaneous --- 491 // Some of these are advanced settings which should not be modified unless you 492 // know what you are doing. 493 // 494 // Activates search logging. For each solution found during the search, the 495 // following will be displayed: its objective value, the maximum objective 496 // value since the beginning of the search, the elapsed time since the 497 // beginning of the search, the number of branches explored in the search 498 // tree, the number of failures in the search tree, the depth of the search 499 // tree, the number of local search neighbors explored, the number of local 500 // search neighbors filtered by local search filters, the number of local 501 // search neighbors accepted, the total memory used and the percentage of the 502 // search done. 503 bool log_search = 13; 504 // In logs, cost values will be scaled and offset by the given values in the 505 // following way: log_cost_scaling_factor * (cost + log_cost_offset) 506 double log_cost_scaling_factor = 22; 507 double log_cost_offset = 29; 508 // In logs, this tag will be appended to each line corresponding to a new 509 // solution. Useful to sort out logs when several solves are run in parallel. 510 string log_tag = 36; 511} 512 513// Parameters which have to be set when creating a RoutingModel. 514message RoutingModelParameters { 515 // Parameters to use in the underlying constraint solver. 516 ConstraintSolverParameters solver_parameters = 1; 517 // Advanced settings. 518 // If set to true reduction of the underlying constraint model will be 519 // attempted when all vehicles have exactly the same cost structure. This can 520 // result in significant speedups. 521 bool reduce_vehicle_cost_model = 2; 522 // Cache callback calls if the number of nodes in the model is less or equal 523 // to this value. 524 int32 max_callback_cache_size = 3; 525} 526