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"
33 ConstraintSolverParameters*
const solver_parameters =
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);
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"
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: "
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"
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 "
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 "
109 "solution_limit: 0x7fffffffffffffff "
110 "lns_time_limit: { seconds:0 nanos:100000000 } "
111 "use_full_propagation: false "
113 "log_cost_scaling_factor: 1.0 "
114 "log_cost_offset: 0.0";
116 if (!google::protobuf::TextFormat::ParseFromString(kSearchParameters,
118 LOG(DFATAL) <<
"Unsupported default search parameters: "
119 << kSearchParameters;
122 LOG_IF(DFATAL, !error.empty())
123 <<
"The default search parameters aren't valid: " << error;
128 bool IsValidNonNegativeDuration(
const google::protobuf::Duration& d) {
130 return status_or_duration.ok() &&
131 status_or_duration.value() >= absl::ZeroDuration();
136 const RoutingSearchParameters& search_parameters) {
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 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 ||
154 <<
"In RoutingSearchParameters::LocalSearchNeighborhoodOperators,"
155 <<
" field '" << field->name() <<
"' is not an OptionalBoolean.";
156 return "The file 'routing_search_parameters.proto' itself is invalid!";
158 const int value = ls_reflection->GetEnum(operators, field)->number();
160 return StrCat(
"local_search_neighborhood_operator.", field->name(),
161 " should be set to BOOL_TRUE or BOOL_FALSE instead of ",
163 " (value: ",
value,
")");
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);
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);
181 const double coefficient = search_parameters.savings_arc_coefficient();
184 return StrCat(
"Invalid savings_arc_coefficient:",
coefficient);
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);
196 search_parameters.cheapest_insertion_first_solution_neighbors_ratio();
197 if (std::isnan(
ratio) || ratio <= 0 || ratio > 1) {
199 "Invalid cheapest_insertion_first_solution_neighbors_ratio: ",
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: ",
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).");
219 const int32 num_arcs =
220 search_parameters.heuristic_expensive_chain_lns_num_arcs_to_consider();
221 if (num_arcs < 2 || num_arcs > 1e6) {
223 "Invalid heuristic_expensive_chain_lns_num_arcs_to_consider: ",
224 num_arcs,
". Must be between 2 and 10^6 (included).");
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).");
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: ",
245 const double step = search_parameters.optimization_step();
246 if (std::isnan(step) || step < 0.0) {
247 return StrCat(
"Invalid optimization_step: ", step);
251 const int32 num = search_parameters.number_of_solutions_to_collect();
252 if (num < 1)
return StrCat(
"Invalid number_of_solutions_to_collect:", num);
255 const int64 lim = search_parameters.solution_limit();
256 if (lim < 1)
return StrCat(
"Invalid solution_limit:", lim);
258 if (!IsValidNonNegativeDuration(search_parameters.time_limit())) {
259 return "Invalid time_limit: " +
260 search_parameters.time_limit().ShortDebugString();
262 if (!IsValidNonNegativeDuration(search_parameters.lns_time_limit())) {
263 return "Invalid lns_time_limit: " +
264 search_parameters.lns_time_limit().ShortDebugString();
266 if (!FirstSolutionStrategy::Value_IsValid(
267 search_parameters.first_solution_strategy())) {
268 return StrCat(
"Invalid first_solution_strategy: ",
269 search_parameters.first_solution_strategy());
271 if (!LocalSearchMetaheuristic::Value_IsValid(
272 search_parameters.local_search_metaheuristic())) {
273 return StrCat(
"Invalid metaheuristic: ",
274 search_parameters.local_search_metaheuristic());
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: ",
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);
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));
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));
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) {
312 "improvement_limit_parameters.improvement_rate_coefficient: ",
313 improvement_rate_coefficient);
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) {
322 "improvement_limit_parameters.improvement_rate_solutions_distance: ",
323 improvement_rate_solutions_distance);
328 const double memory_coefficient =
330 .multi_armed_bandit_compound_operator_memory_coefficient();
331 if (std::isnan(memory_coefficient) || memory_coefficient < 0 ||
332 memory_coefficient > 1) {
335 "multi_armed_bandit_compound_operator_memory_coefficient: ",
340 const double exploration_coefficient =
342 .multi_armed_bandit_compound_operator_exploration_coefficient();
343 if (std::isnan(exploration_coefficient) || exploration_coefficient < 0) {
346 "multi_armed_bandit_compound_operator_exploration_coefficient: ",
347 exploration_coefficient);