OR-Tools  8.1
routing_parameters.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 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 
15 
16 #include "absl/strings/str_cat.h"
17 #include "absl/time/time.h"
18 #include "google/protobuf/descriptor.h"
19 #include "google/protobuf/duration.pb.h"
20 #include "google/protobuf/message.h"
21 #include "google/protobuf/text_format.h"
22 #include "ortools/base/logging.h"
23 #include "ortools/base/protoutil.h"
28 
29 namespace operations_research {
30 
31 RoutingModelParameters DefaultRoutingModelParameters() {
32  RoutingModelParameters parameters;
33  ConstraintSolverParameters* const solver_parameters =
34  parameters.mutable_solver_parameters();
35  *solver_parameters = Solver::DefaultSolverParameters();
36  solver_parameters->set_compress_trail(
37  ConstraintSolverParameters::COMPRESS_WITH_ZLIB);
38  solver_parameters->set_skip_locally_optimal_paths(true);
39  parameters.set_reduce_vehicle_cost_model(true);
40  return parameters;
41 }
42 
43 // static
44 RoutingSearchParameters DefaultRoutingSearchParameters() {
45  static const char* const kSearchParameters =
46  "first_solution_strategy: AUTOMATIC "
47  "use_unfiltered_first_solution_strategy: false "
48  "savings_neighbors_ratio: 1 "
49  "savings_max_memory_usage_bytes: 6e9 "
50  "savings_add_reverse_arcs: false "
51  "savings_arc_coefficient: 1 "
52  "savings_parallel_routes: false "
53  "cheapest_insertion_farthest_seeds_ratio: 0 "
54  "cheapest_insertion_first_solution_neighbors_ratio: 1 "
55  "cheapest_insertion_ls_operator_neighbors_ratio: 1 "
56  "cheapest_insertion_add_unperformed_entries: false "
57  "local_search_operators {"
58  " use_relocate: BOOL_TRUE"
59  " use_relocate_pair: BOOL_TRUE"
60  " use_light_relocate_pair: BOOL_TRUE"
61  " use_relocate_subtrip: BOOL_TRUE"
62  " use_relocate_neighbors: BOOL_FALSE"
63  " use_exchange: BOOL_TRUE"
64  " use_exchange_pair: BOOL_TRUE"
65  " use_exchange_subtrip: BOOL_TRUE"
66  " use_cross: BOOL_TRUE"
67  " use_cross_exchange: BOOL_FALSE"
68  " use_relocate_expensive_chain: BOOL_TRUE"
69  " use_two_opt: BOOL_TRUE"
70  " use_or_opt: BOOL_TRUE"
71  " use_lin_kernighan: BOOL_TRUE"
72  " use_tsp_opt: BOOL_FALSE"
73  " use_make_active: BOOL_TRUE"
74  " use_relocate_and_make_active: BOOL_FALSE" // costly if true by default
75  " use_make_inactive: BOOL_TRUE"
76  " use_make_chain_inactive: BOOL_FALSE"
77  " use_swap_active: BOOL_TRUE"
78  " use_extended_swap_active: BOOL_FALSE"
79  " use_node_pair_swap_active: BOOL_TRUE"
80  " use_path_lns: BOOL_FALSE"
81  " use_full_path_lns: BOOL_FALSE"
82  " use_tsp_lns: BOOL_FALSE"
83  " use_inactive_lns: BOOL_FALSE"
84  " use_global_cheapest_insertion_path_lns: BOOL_TRUE"
85  " use_local_cheapest_insertion_path_lns: BOOL_TRUE"
86  " use_relocate_path_global_cheapest_insertion_insert_unperformed: "
87  "BOOL_TRUE"
88  " use_global_cheapest_insertion_expensive_chain_lns: BOOL_FALSE"
89  " use_local_cheapest_insertion_expensive_chain_lns: BOOL_FALSE"
90  " use_global_cheapest_insertion_close_nodes_lns: BOOL_FALSE"
91  " use_local_cheapest_insertion_close_nodes_lns: BOOL_FALSE"
92  "}"
93  "use_multi_armed_bandit_concatenate_operators: false "
94  "multi_armed_bandit_compound_operator_memory_coefficient: 0.04 "
95  "multi_armed_bandit_compound_operator_exploration_coefficient: 1e12 "
96  "relocate_expensive_chain_num_arcs_to_consider: 4 "
97  "heuristic_expensive_chain_lns_num_arcs_to_consider: 4 "
98  "heuristic_close_nodes_lns_num_nodes: 5 "
99  "local_search_metaheuristic: AUTOMATIC "
100  "guided_local_search_lambda_coefficient: 0.1 "
101  "use_depth_first_search: false "
102  "use_cp: BOOL_TRUE "
103  "use_cp_sat: BOOL_FALSE "
104  "continuous_scheduling_solver: GLOP "
105  "mixed_integer_scheduling_solver: CP_SAT "
106  "optimization_step: 0.0 "
107  "number_of_solutions_to_collect: 1 "
108  // No "time_limit" by default.
109  "solution_limit: 0x7fffffffffffffff " // kint64max
110  "lns_time_limit: { seconds:0 nanos:100000000 } " // 0.1s
111  "use_full_propagation: false "
112  "log_search: false "
113  "log_cost_scaling_factor: 1.0 "
114  "log_cost_offset: 0.0";
115  RoutingSearchParameters parameters;
116  if (!google::protobuf::TextFormat::ParseFromString(kSearchParameters,
117  &parameters)) {
118  LOG(DFATAL) << "Unsupported default search parameters: "
119  << kSearchParameters;
120  }
121  const std::string error = FindErrorInRoutingSearchParameters(parameters);
122  LOG_IF(DFATAL, !error.empty())
123  << "The default search parameters aren't valid: " << error;
124  return parameters;
125 }
126 
127 namespace {
128 bool IsValidNonNegativeDuration(const google::protobuf::Duration& d) {
129  const auto status_or_duration = util_time::DecodeGoogleApiProto(d);
130  return status_or_duration.ok() &&
131  status_or_duration.value() >= absl::ZeroDuration();
132 }
133 } // namespace
134 
136  const RoutingSearchParameters& search_parameters) {
137  using absl::StrCat;
138  // Check that all local search operators are set to either BOOL_TRUE or
139  // BOOL_FALSE (and not BOOL_UNSPECIFIED).
140  {
141  using Reflection = google::protobuf::Reflection;
142  using Descriptor = google::protobuf::Descriptor;
143  using FieldDescriptor = google::protobuf::FieldDescriptor;
144  const RoutingSearchParameters::LocalSearchNeighborhoodOperators& operators =
145  search_parameters.local_search_operators();
146  const Reflection* ls_reflection = operators.GetReflection();
147  const Descriptor* ls_descriptor = operators.GetDescriptor();
148  for (int /*this is NOT the field's tag number*/ field_index = 0;
149  field_index < ls_descriptor->field_count(); ++field_index) {
150  const FieldDescriptor* field = ls_descriptor->field(field_index);
151  if (field->type() != FieldDescriptor::TYPE_ENUM ||
152  field->enum_type() != OptionalBoolean_descriptor()) {
153  DLOG(FATAL)
154  << "In RoutingSearchParameters::LocalSearchNeighborhoodOperators,"
155  << " field '" << field->name() << "' is not an OptionalBoolean.";
156  return "The file 'routing_search_parameters.proto' itself is invalid!";
157  }
158  const int value = ls_reflection->GetEnum(operators, field)->number();
159  if (!OptionalBoolean_IsValid(value) || value == 0) {
160  return StrCat("local_search_neighborhood_operator.", field->name(),
161  " should be set to BOOL_TRUE or BOOL_FALSE instead of ",
163  " (value: ", value, ")");
164  }
165  }
166  }
167  {
168  const double ratio = search_parameters.savings_neighbors_ratio();
169  if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
170  return StrCat("Invalid savings_neighbors_ratio:", ratio);
171  }
172  }
173  {
174  const double max_memory =
175  search_parameters.savings_max_memory_usage_bytes();
176  if (std::isnan(max_memory) || max_memory <= 0 || max_memory > 1e10) {
177  return StrCat("Invalid savings_max_memory_usage_bytes: ", max_memory);
178  }
179  }
180  {
181  const double coefficient = search_parameters.savings_arc_coefficient();
182  if (std::isnan(coefficient) || coefficient <= 0 ||
183  std::isinf(coefficient)) {
184  return StrCat("Invalid savings_arc_coefficient:", coefficient);
185  }
186  }
187  {
188  const double ratio =
189  search_parameters.cheapest_insertion_farthest_seeds_ratio();
190  if (std::isnan(ratio) || ratio < 0 || ratio > 1) {
191  return StrCat("Invalid cheapest_insertion_farthest_seeds_ratio:", ratio);
192  }
193  }
194  {
195  const double ratio =
196  search_parameters.cheapest_insertion_first_solution_neighbors_ratio();
197  if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
198  return StrCat(
199  "Invalid cheapest_insertion_first_solution_neighbors_ratio: ", ratio);
200  }
201  }
202  {
203  const double ratio =
204  search_parameters.cheapest_insertion_ls_operator_neighbors_ratio();
205  if (std::isnan(ratio) || ratio <= 0 || ratio > 1) {
206  return StrCat("Invalid cheapest_insertion_ls_operator_neighbors_ratio: ",
207  ratio);
208  }
209  }
210  {
211  const int32 num_arcs =
212  search_parameters.relocate_expensive_chain_num_arcs_to_consider();
213  if (num_arcs < 2 || num_arcs > 1e6) {
214  return StrCat("Invalid relocate_expensive_chain_num_arcs_to_consider: ",
215  num_arcs, ". Must be between 2 and 10^6 (included).");
216  }
217  }
218  {
219  const int32 num_arcs =
220  search_parameters.heuristic_expensive_chain_lns_num_arcs_to_consider();
221  if (num_arcs < 2 || num_arcs > 1e6) {
222  return StrCat(
223  "Invalid heuristic_expensive_chain_lns_num_arcs_to_consider: ",
224  num_arcs, ". Must be between 2 and 10^6 (included).");
225  }
226  }
227  {
228  const int32 num_nodes =
229  search_parameters.heuristic_close_nodes_lns_num_nodes();
230  if (num_nodes < 0 || num_nodes > 1e4) {
231  return StrCat("Invalid heuristic_close_nodes_lns_num_nodes: ", num_nodes,
232  ". Must be between 0 and 10000 (included).");
233  }
234  }
235  {
236  const double gls_coefficient =
237  search_parameters.guided_local_search_lambda_coefficient();
238  if (std::isnan(gls_coefficient) || gls_coefficient < 0 ||
239  std::isinf(gls_coefficient)) {
240  return StrCat("Invalid guided_local_search_lambda_coefficient: ",
241  gls_coefficient);
242  }
243  }
244  {
245  const double step = search_parameters.optimization_step();
246  if (std::isnan(step) || step < 0.0) {
247  return StrCat("Invalid optimization_step: ", step);
248  }
249  }
250  {
251  const int32 num = search_parameters.number_of_solutions_to_collect();
252  if (num < 1) return StrCat("Invalid number_of_solutions_to_collect:", num);
253  }
254  {
255  const int64 lim = search_parameters.solution_limit();
256  if (lim < 1) return StrCat("Invalid solution_limit:", lim);
257  }
258  if (!IsValidNonNegativeDuration(search_parameters.time_limit())) {
259  return "Invalid time_limit: " +
260  search_parameters.time_limit().ShortDebugString();
261  }
262  if (!IsValidNonNegativeDuration(search_parameters.lns_time_limit())) {
263  return "Invalid lns_time_limit: " +
264  search_parameters.lns_time_limit().ShortDebugString();
265  }
266  if (!FirstSolutionStrategy::Value_IsValid(
267  search_parameters.first_solution_strategy())) {
268  return StrCat("Invalid first_solution_strategy: ",
269  search_parameters.first_solution_strategy());
270  }
271  if (!LocalSearchMetaheuristic::Value_IsValid(
272  search_parameters.local_search_metaheuristic())) {
273  return StrCat("Invalid metaheuristic: ",
274  search_parameters.local_search_metaheuristic());
275  }
276 
277  const double scaling_factor = search_parameters.log_cost_scaling_factor();
278  if (scaling_factor == 0 || std::isnan(scaling_factor) ||
279  std::isinf(scaling_factor)) {
280  return StrCat("Invalid value for log_cost_scaling_factor: ",
281  scaling_factor);
282  }
283  const double offset = search_parameters.log_cost_offset();
284  if (std::isnan(offset) || std::isinf(offset)) {
285  return StrCat("Invalid value for log_cost_offset: ", offset);
286  }
287  const RoutingSearchParameters::SchedulingSolver continuous_scheduling_solver =
288  search_parameters.continuous_scheduling_solver();
289  if (continuous_scheduling_solver == RoutingSearchParameters::UNSET ||
290  continuous_scheduling_solver == RoutingSearchParameters::CP_SAT) {
291  return StrCat("Invalid value for continuous_scheduling_solver: ",
292  RoutingSearchParameters::SchedulingSolver_Name(
293  continuous_scheduling_solver));
294  }
295  const RoutingSearchParameters::SchedulingSolver
296  mixed_integer_scheduling_solver =
297  search_parameters.mixed_integer_scheduling_solver();
298  if (mixed_integer_scheduling_solver == RoutingSearchParameters::UNSET) {
299  return StrCat("Invalid value for mixed_integer_scheduling_solver: ",
300  RoutingSearchParameters::SchedulingSolver_Name(
301  mixed_integer_scheduling_solver));
302  }
303 
304  if (search_parameters.has_improvement_limit_parameters()) {
305  const double improvement_rate_coefficient =
306  search_parameters.improvement_limit_parameters()
307  .improvement_rate_coefficient();
308  if (std::isnan(improvement_rate_coefficient) ||
309  improvement_rate_coefficient <= 0) {
310  return StrCat(
311  "Invalid value for "
312  "improvement_limit_parameters.improvement_rate_coefficient: ",
313  improvement_rate_coefficient);
314  }
315 
316  const int32 improvement_rate_solutions_distance =
317  search_parameters.improvement_limit_parameters()
318  .improvement_rate_solutions_distance();
319  if (improvement_rate_solutions_distance <= 0) {
320  return StrCat(
321  "Invalid value for "
322  "improvement_limit_parameters.improvement_rate_solutions_distance: ",
323  improvement_rate_solutions_distance);
324  }
325  }
326 
327  {
328  const double memory_coefficient =
329  search_parameters
330  .multi_armed_bandit_compound_operator_memory_coefficient();
331  if (std::isnan(memory_coefficient) || memory_coefficient < 0 ||
332  memory_coefficient > 1) {
333  return StrCat(
334  "Invalid value for "
335  "multi_armed_bandit_compound_operator_memory_coefficient: ",
336  memory_coefficient);
337  }
338  }
339  {
340  const double exploration_coefficient =
341  search_parameters
342  .multi_armed_bandit_compound_operator_exploration_coefficient();
343  if (std::isnan(exploration_coefficient) || exploration_coefficient < 0) {
344  return StrCat(
345  "Invalid value for "
346  "multi_armed_bandit_compound_operator_exploration_coefficient: ",
347  exploration_coefficient);
348  }
349  }
350 
351  return ""; // = Valid (No error).
352 }
353 
354 } // namespace operations_research
operations_research::DefaultRoutingModelParameters
RoutingModelParameters DefaultRoutingModelParameters()
Definition: routing_parameters.cc:31
LOG
#define LOG(severity)
Definition: base/logging.h:420
FATAL
const int FATAL
Definition: log_severity.h:32
logging.h
value
int64 value
Definition: demon_profiler.cc:43
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
protoutil.h
int64
int64_t int64
Definition: integral_types.h:34
routing_enums.pb.h
operations_research::DefaultRoutingSearchParameters
RoutingSearchParameters DefaultRoutingSearchParameters()
Definition: routing_parameters.cc:44
DLOG
#define DLOG(severity)
Definition: base/logging.h:875
operations_research::FindErrorInRoutingSearchParameters
std::string FindErrorInRoutingSearchParameters(const RoutingSearchParameters &search_parameters)
Returns an empty std::string if the routing search parameters are valid, and a non-empty,...
Definition: routing_parameters.cc:135
int32
int int32
Definition: integral_types.h:33
ratio
Fractional ratio
Definition: revised_simplex.cc:1802
constraint_solver.h
util_time::DecodeGoogleApiProto
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
Definition: protoutil.h:40
operations_research::OptionalBoolean_Name
const std::string & OptionalBoolean_Name(T enum_t_value)
Definition: optional_boolean.pb.h:73
LOG_IF
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
routing_parameters.h
coefficient
int64 coefficient
Definition: routing_search.cc:972
operations_research::OptionalBoolean_IsValid
bool OptionalBoolean_IsValid(int value)
Definition: optional_boolean.pb.cc:52
optional_boolean.pb.h
operations_research::Solver::DefaultSolverParameters
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
Definition: constraint_solver.cc:118
operations_research::OptionalBoolean_descriptor
const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor * OptionalBoolean_descriptor()
Definition: optional_boolean.pb.cc:48
parameters
SatParameters parameters
Definition: cp_model_fz_solver.cc:108
operations_research::OptionalBoolean
OptionalBoolean
Definition: optional_boolean.pb.h:59
solver_parameters.pb.h