OR-Tools  8.2
routing_flags.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 <map>
17#include <vector>
18
19#include "absl/status/status.h"
20#include "absl/time/time.h"
24#include "ortools/constraint_solver/routing_enums.pb.h"
26#include "ortools/util/optional_boolean.pb.h"
27
28// --- Routing search flags ---
29
30// Neighborhood activation/deactivation
31ABSL_FLAG(bool, routing_no_lns, false,
32 "Routing: forbids use of Large Neighborhood Search.");
33ABSL_FLAG(bool, routing_no_fullpathlns, true,
34 "Routing: forbids use of Full-path Large Neighborhood Search.");
35ABSL_FLAG(bool, routing_no_relocate, false,
36 "Routing: forbids use of Relocate neighborhood.");
37ABSL_FLAG(bool, routing_no_relocate_neighbors, true,
38 "Routing: forbids use of RelocateNeighbors neighborhood.");
39ABSL_FLAG(bool, routing_no_relocate_subtrip, false,
40 "Routing: forbids use of RelocateSubtrips neighborhood.");
41ABSL_FLAG(bool, routing_no_exchange, false,
42 "Routing: forbids use of Exchange neighborhood.");
43ABSL_FLAG(bool, routing_no_exchange_subtrip, false,
44 "Routing: forbids use of ExchangeSubtrips neighborhood.");
45ABSL_FLAG(bool, routing_no_cross, false,
46 "Routing: forbids use of Cross neighborhood.");
47ABSL_FLAG(bool, routing_no_2opt, false,
48 "Routing: forbids use of 2Opt neighborhood.");
49ABSL_FLAG(bool, routing_no_oropt, false,
50 "Routing: forbids use of OrOpt neighborhood.");
51ABSL_FLAG(bool, routing_no_make_active, false,
52 "Routing: forbids use of MakeActive/SwapActive/MakeInactive "
53 "neighborhoods.");
54ABSL_FLAG(bool, routing_no_lkh, false,
55 "Routing: forbids use of LKH neighborhood.");
56ABSL_FLAG(bool, routing_no_relocate_expensive_chain, false,
57 "Routing: forbids use of RelocateExpensiveChain operator.");
58ABSL_FLAG(bool, routing_no_tsp, true,
59 "Routing: forbids use of TSPOpt neighborhood.");
60ABSL_FLAG(bool, routing_no_tsplns, true,
61 "Routing: forbids use of TSPLNS neighborhood.");
62ABSL_FLAG(bool, routing_use_chain_make_inactive, false,
63 "Routing: use chain version of MakeInactive neighborhood.");
64ABSL_FLAG(bool, routing_use_extended_swap_active, false,
65 "Routing: use extended version of SwapActive neighborhood.");
66
67// Meta-heuristics
68ABSL_FLAG(bool, routing_guided_local_search, false, "Routing: use GLS.");
69ABSL_FLAG(double, routing_guided_local_search_lambda_coefficient, 0.1,
70 "Lambda coefficient in GLS.");
71ABSL_FLAG(bool, routing_simulated_annealing, false,
72 "Routing: use simulated annealing.");
73ABSL_FLAG(bool, routing_tabu_search, false, "Routing: use tabu search.");
74ABSL_FLAG(bool, routing_generic_tabu_search, false,
75 "Routing: use tabu search based on a list of values.");
76
77// Search limits
78ABSL_FLAG(int64, routing_solution_limit, kint64max,
79 "Routing: number of solutions limit.");
80ABSL_FLAG(int64, routing_time_limit, kint64max, "Routing: time limit in ms.");
81ABSL_FLAG(int64, routing_lns_time_limit, 100,
82 "Routing: time limit in ms for LNS sub-decisionbuilder.");
83
84// Search control
85ABSL_FLAG(std::string, routing_first_solution, "",
86 "Routing first solution heuristic. See SetupParametersFromFlags "
87 "in the code to get a full list.");
88ABSL_FLAG(bool, routing_use_filtered_first_solutions, true,
89 "Use filtered version of first solution heuristics if available.");
90ABSL_FLAG(double, savings_neighbors_ratio, 1,
91 "Ratio of neighbors to consider for each node when "
92 "constructing the savings.");
93ABSL_FLAG(bool, savings_add_reverse_arcs, false,
94 "Add savings related to reverse arcs when finding the nearest "
95 "neighbors of the nodes.");
96ABSL_FLAG(double, savings_arc_coefficient, 1.0,
97 "Coefficient of the cost of the arc for which the saving value "
98 "is being computed.");
99ABSL_FLAG(double, cheapest_insertion_farthest_seeds_ratio, 0,
100 "Ratio of available vehicles in the model on which farthest "
101 "nodes of the model are inserted as seeds.");
102ABSL_FLAG(double, cheapest_insertion_first_solution_neighbors_ratio, 1.0,
103 "Ratio of nodes considered as neighbors in the "
104 "GlobalCheapestInsertion first solution heuristic.");
105ABSL_FLAG(bool, routing_dfs, false,
106 "Routing: use a complete depth-first search.");
107ABSL_FLAG(double, routing_optimization_step, 0.0, "Optimization step.");
108ABSL_FLAG(int, routing_number_of_solutions_to_collect, 1,
109 "Number of solutions to collect.");
110ABSL_FLAG(int, routing_relocate_expensive_chain_num_arcs_to_consider, 4,
111 "Number of arcs to consider in the RelocateExpensiveChain "
112 "neighborhood operator.");
113
114// Propagation control
115ABSL_FLAG(bool, routing_use_light_propagation, true,
116 "Use constraints with light propagation in routing model.");
117
118// Cache settings.
119ABSL_FLAG(bool, routing_cache_callbacks, false, "Cache callback calls.");
120ABSL_FLAG(int64, routing_max_cache_size, 1000,
121 "Maximum cache size when callback caching is on.");
122
123// Misc
124ABSL_FLAG(bool, routing_trace, false, "Routing: trace search.");
125ABSL_FLAG(bool, routing_profile, false, "Routing: profile search.");
126
127// --- Routing model flags ---
128ABSL_FLAG(bool, routing_use_homogeneous_costs, true,
129 "Routing: use homogeneous cost model when possible.");
130ABSL_FLAG(bool, routing_gzip_compress_trail, false,
131 "Use gzip to compress the trail, zippy otherwise.");
132
133namespace operations_research {
134
135void SetFirstSolutionStrategyFromFlags(RoutingSearchParameters* parameters) {
136 CHECK(parameters != nullptr);
137 const std::map<std::string, FirstSolutionStrategy::Value>
138 first_solution_string_to_parameters = {
139 {"PathCheapestArc", FirstSolutionStrategy::PATH_CHEAPEST_ARC},
140 {"PathMostConstrainedArc",
141 FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC},
142 {"EvaluatorStrategy", FirstSolutionStrategy::EVALUATOR_STRATEGY},
143 {"Savings", FirstSolutionStrategy::SAVINGS},
144 {"Sweep", FirstSolutionStrategy::SWEEP},
145 {"Christofides", FirstSolutionStrategy::CHRISTOFIDES},
146 {"AllUnperformed", FirstSolutionStrategy::ALL_UNPERFORMED},
147 {"BestInsertion", FirstSolutionStrategy::BEST_INSERTION},
148 {"GlobalCheapestInsertion",
149 FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION},
150 {"SequentialGlobalCheapestInsertion",
151 FirstSolutionStrategy::SEQUENTIAL_CHEAPEST_INSERTION},
152 {"LocalCheapestInsertion",
153 FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION},
154 {"GlobalCheapestArc", FirstSolutionStrategy::GLOBAL_CHEAPEST_ARC},
155 {"LocalCheapestArc", FirstSolutionStrategy::LOCAL_CHEAPEST_ARC},
156 {"DefaultStrategy", FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE},
157 {"", FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE}};
159 if (gtl::FindCopy(first_solution_string_to_parameters,
160 absl::GetFlag(FLAGS_routing_first_solution), &strategy)) {
161 parameters->set_first_solution_strategy(strategy);
162 }
163 parameters->set_use_unfiltered_first_solution_strategy(
164 !absl::GetFlag(FLAGS_routing_use_filtered_first_solutions));
165 parameters->set_savings_neighbors_ratio(
166 absl::GetFlag(FLAGS_savings_neighbors_ratio));
167 parameters->set_savings_max_memory_usage_bytes(6e9);
168 parameters->set_savings_add_reverse_arcs(
169 absl::GetFlag(FLAGS_savings_add_reverse_arcs));
170 parameters->set_savings_arc_coefficient(
171 absl::GetFlag(FLAGS_savings_arc_coefficient));
172 parameters->set_cheapest_insertion_farthest_seeds_ratio(
173 absl::GetFlag(FLAGS_cheapest_insertion_farthest_seeds_ratio));
174 parameters->set_cheapest_insertion_first_solution_neighbors_ratio(
175 absl::GetFlag(FLAGS_cheapest_insertion_first_solution_neighbors_ratio));
176 parameters->set_cheapest_insertion_first_solution_min_neighbors(1);
177}
178
179void SetLocalSearchMetaheuristicFromFlags(RoutingSearchParameters* parameters) {
180 CHECK(parameters != nullptr);
181 if (absl::GetFlag(FLAGS_routing_tabu_search)) {
182 parameters->set_local_search_metaheuristic(
183 LocalSearchMetaheuristic::TABU_SEARCH);
184 } else if (absl::GetFlag(FLAGS_routing_generic_tabu_search)) {
185 parameters->set_local_search_metaheuristic(
186 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH);
187 } else if (absl::GetFlag(FLAGS_routing_simulated_annealing)) {
188 parameters->set_local_search_metaheuristic(
189 LocalSearchMetaheuristic::SIMULATED_ANNEALING);
190 } else if (absl::GetFlag(FLAGS_routing_guided_local_search)) {
191 parameters->set_local_search_metaheuristic(
192 LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH);
193 }
194 parameters->set_guided_local_search_lambda_coefficient(
195 absl::GetFlag(FLAGS_routing_guided_local_search_lambda_coefficient));
196}
197
198namespace {
199OptionalBoolean ToOptionalBoolean(bool x) { return x ? BOOL_TRUE : BOOL_FALSE; }
200} // namespace
201
203 RoutingSearchParameters* parameters) {
204 CHECK(parameters != nullptr);
205 parameters->set_cheapest_insertion_ls_operator_neighbors_ratio(1.0);
206 parameters->set_cheapest_insertion_ls_operator_min_neighbors(1);
207 RoutingSearchParameters::LocalSearchNeighborhoodOperators* const
208 local_search_operators = parameters->mutable_local_search_operators();
209
210 // TODO(user): Remove these overrides: they should be set by the caller, via
211 // a baseline RoutingSearchParameters obtained from DefaultSearchParameters().
212 local_search_operators->set_use_relocate_pair(BOOL_TRUE);
213 local_search_operators->set_use_light_relocate_pair(BOOL_TRUE);
214 local_search_operators->set_use_exchange_pair(BOOL_TRUE);
215 local_search_operators->set_use_relocate_and_make_active(BOOL_FALSE);
216 local_search_operators->set_use_node_pair_swap_active(BOOL_FALSE);
217 local_search_operators->set_use_cross_exchange(BOOL_FALSE);
218 local_search_operators->set_use_global_cheapest_insertion_path_lns(BOOL_TRUE);
219 local_search_operators->set_use_local_cheapest_insertion_path_lns(BOOL_TRUE);
220 local_search_operators
221 ->set_use_relocate_path_global_cheapest_insertion_insert_unperformed(
222 BOOL_TRUE);
223 local_search_operators->set_use_global_cheapest_insertion_expensive_chain_lns(
224 BOOL_FALSE);
225 local_search_operators->set_use_local_cheapest_insertion_expensive_chain_lns(
226 BOOL_FALSE);
227 local_search_operators->set_use_global_cheapest_insertion_close_nodes_lns(
228 BOOL_FALSE);
229 local_search_operators->set_use_local_cheapest_insertion_close_nodes_lns(
230 BOOL_FALSE);
231
232 local_search_operators->set_use_relocate(
233 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_relocate)));
234 local_search_operators->set_use_relocate_neighbors(
235 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_relocate_neighbors)));
236 local_search_operators->set_use_relocate_subtrip(
237 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_relocate_subtrip)));
238 local_search_operators->set_use_exchange_subtrip(
239 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_exchange_subtrip)));
240 local_search_operators->set_use_exchange(
241 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_exchange)));
242 local_search_operators->set_use_cross(
243 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_cross)));
244 local_search_operators->set_use_two_opt(
245 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_2opt)));
246 local_search_operators->set_use_or_opt(
247 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_oropt)));
248 local_search_operators->set_use_lin_kernighan(
249 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_lkh)));
250 local_search_operators->set_use_relocate_expensive_chain(ToOptionalBoolean(
251 !absl::GetFlag(FLAGS_routing_no_relocate_expensive_chain)));
252 local_search_operators->set_use_tsp_opt(
253 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_tsp)));
254 local_search_operators->set_use_make_active(
255 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_make_active)));
256 local_search_operators->set_use_make_inactive(
257 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_use_chain_make_inactive) &&
258 !absl::GetFlag(FLAGS_routing_no_make_active)));
259 local_search_operators->set_use_make_chain_inactive(
260 ToOptionalBoolean(absl::GetFlag(FLAGS_routing_use_chain_make_inactive) &&
261 !absl::GetFlag(FLAGS_routing_no_make_active)));
262 local_search_operators->set_use_swap_active(ToOptionalBoolean(
263 !absl::GetFlag(FLAGS_routing_use_extended_swap_active) &&
264 !absl::GetFlag(FLAGS_routing_no_make_active)));
265 local_search_operators->set_use_extended_swap_active(
266 ToOptionalBoolean(absl::GetFlag(FLAGS_routing_use_extended_swap_active) &&
267 !absl::GetFlag(FLAGS_routing_no_make_active)));
268 local_search_operators->set_use_path_lns(
269 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_lns)));
270 local_search_operators->set_use_inactive_lns(
271 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_lns)));
272 local_search_operators->set_use_full_path_lns(
273 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_fullpathlns)));
274 local_search_operators->set_use_tsp_lns(
275 ToOptionalBoolean(!absl::GetFlag(FLAGS_routing_no_tsplns)));
276}
277
278void SetSearchLimitsFromFlags(RoutingSearchParameters* parameters) {
279 CHECK(parameters != nullptr);
280 parameters->set_use_depth_first_search(absl::GetFlag(FLAGS_routing_dfs));
281 parameters->set_use_cp(BOOL_TRUE);
282 parameters->set_use_cp_sat(BOOL_FALSE);
283 parameters->set_optimization_step(
284 absl::GetFlag(FLAGS_routing_optimization_step));
285 parameters->set_number_of_solutions_to_collect(
286 absl::GetFlag(FLAGS_routing_number_of_solutions_to_collect));
287 parameters->set_solution_limit(absl::GetFlag(FLAGS_routing_solution_limit));
288 if (absl::GetFlag(FLAGS_routing_time_limit) != kint64max) {
290 absl::Milliseconds(absl::GetFlag(FLAGS_routing_time_limit)),
291 parameters->mutable_time_limit()));
292 }
293 if (absl::GetFlag(FLAGS_routing_lns_time_limit) != kint64max) {
295 absl::Milliseconds(absl::GetFlag(FLAGS_routing_lns_time_limit)),
296 parameters->mutable_lns_time_limit()));
297 }
298}
299
300void SetMiscellaneousParametersFromFlags(RoutingSearchParameters* parameters) {
301 CHECK(parameters != nullptr);
302 parameters->set_use_full_propagation(
303 !absl::GetFlag(FLAGS_routing_use_light_propagation));
304 parameters->set_log_search(absl::GetFlag(FLAGS_routing_trace));
305 parameters->set_log_cost_scaling_factor(1.0);
306 parameters->set_relocate_expensive_chain_num_arcs_to_consider(absl::GetFlag(
307 FLAGS_routing_relocate_expensive_chain_num_arcs_to_consider));
308 parameters->set_heuristic_expensive_chain_lns_num_arcs_to_consider(4);
309 parameters->set_heuristic_close_nodes_lns_num_nodes(5);
310 parameters->set_continuous_scheduling_solver(RoutingSearchParameters::GLOP);
311 parameters->set_mixed_integer_scheduling_solver(
312 RoutingSearchParameters::CP_SAT);
313}
314
315RoutingSearchParameters BuildSearchParametersFromFlags() {
316 RoutingSearchParameters parameters;
322 const std::string error = FindErrorInRoutingSearchParameters(parameters);
323 LOG_IF(DFATAL, !error.empty())
324 << "Error in the routing search parameters built from flags: " << error;
325 return parameters;
326}
327
328RoutingModelParameters BuildModelParametersFromFlags() {
329 RoutingModelParameters parameters;
330 ConstraintSolverParameters* const solver_parameters =
331 parameters.mutable_solver_parameters();
332 *solver_parameters = Solver::DefaultSolverParameters();
333 parameters.set_reduce_vehicle_cost_model(
334 absl::GetFlag(FLAGS_routing_use_homogeneous_costs));
335 if (absl::GetFlag(FLAGS_routing_cache_callbacks)) {
336 parameters.set_max_callback_cache_size(
337 absl::GetFlag(FLAGS_routing_max_cache_size));
338 }
339 solver_parameters->set_profile_local_search(
340 absl::GetFlag(FLAGS_routing_profile));
341 return parameters;
342}
343
344} // namespace operations_research
#define LOG_IF(severity, condition)
Definition: base/logging.h:479
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_OK(x)
Definition: base/logging.h:40
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
SatParameters parameters
static const int64 kint64max
int64_t int64
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Definition: map_util.h:155
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void SetLocalSearchMetaheuristicFromFlags(RoutingSearchParameters *parameters)
std::string FindErrorInRoutingSearchParameters(const RoutingSearchParameters &search_parameters)
Returns an empty std::string if the routing search parameters are valid, and a non-empty,...
RoutingSearchParameters BuildSearchParametersFromFlags()
Builds routing search parameters from flags.
void AddLocalSearchNeighborhoodOperatorsFromFlags(RoutingSearchParameters *parameters)
void SetFirstSolutionStrategyFromFlags(RoutingSearchParameters *parameters)
void SetMiscellaneousParametersFromFlags(RoutingSearchParameters *parameters)
void SetSearchLimitsFromFlags(RoutingSearchParameters *parameters)
RoutingModelParameters BuildModelParametersFromFlags()
Builds routing search parameters from flags.
inline ::absl::StatusOr< google::protobuf::Duration > EncodeGoogleApiProto(absl::Duration d)
Definition: protoutil.h:25
ABSL_FLAG(bool, routing_no_lns, false, "Routing: forbids use of Large Neighborhood Search.")