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