21 #include <initializer_list>
28 #include "absl/base/casts.h"
29 #include "absl/container/flat_hash_map.h"
30 #include "absl/container/flat_hash_set.h"
31 #include "absl/memory/memory.h"
32 #include "absl/strings/str_cat.h"
33 #include "absl/strings/str_format.h"
34 #include "absl/time/time.h"
35 #include "google/protobuf/duration.pb.h"
36 #include "google/protobuf/text_format.h"
48 #include "ortools/constraint_solver/routing_enums.pb.h"
59 #include "ortools/util/optional_boolean.pb.h"
64 class LocalSearchPhaseParameters;
68 "The number of sectors the space is divided before it is sweeped "
82 class SetValuesFromTargets :
public DecisionBuilder {
84 SetValuesFromTargets(std::vector<IntVar*> variables,
85 std::vector<int64> targets)
86 : variables_(std::move(variables)),
87 targets_(std::move(targets)),
89 steps_(variables_.size(), 0) {
90 DCHECK_EQ(variables_.size(), targets_.size());
92 Decision* Next(Solver*
const solver)
override {
93 int index = index_.Value();
94 while (
index < variables_.size() && variables_[
index]->Bound()) {
97 index_.SetValue(solver,
index);
98 if (
index >= variables_.size())
return nullptr;
99 const int64 variable_min = variables_[
index]->Min();
100 const int64 variable_max = variables_[
index]->Max();
103 if (targets_[
index] <= variable_min) {
104 return solver->MakeAssignVariableValue(variables_[
index], variable_min);
105 }
else if (targets_[
index] >= variable_max) {
106 return solver->MakeAssignVariableValue(variables_[
index], variable_max);
113 if (
value < variable_min || variable_max <
value) {
114 step = GetNextStep(step);
125 steps_.SetValue(solver,
index, GetNextStep(step));
126 return solver->MakeAssignVariableValueOrDoNothing(variables_[
index],
133 return (step > 0) ? -step :
CapSub(1, step);
135 const std::vector<IntVar*> variables_;
136 const std::vector<int64> targets_;
138 RevArray<int64> steps_;
144 std::vector<IntVar*> variables,
145 std::vector<int64> targets) {
147 new SetValuesFromTargets(std::move(variables), std::move(targets)));
152 bool DimensionFixedTransitsEqualTransitEvaluatorForVehicle(
153 const RoutingDimension& dimension,
int vehicle) {
154 const RoutingModel*
const model = dimension.model();
155 int node =
model->Start(vehicle);
156 while (!
model->IsEnd(node)) {
157 if (!
model->NextVar(node)->Bound()) {
160 const int next =
model->NextVar(node)->Value();
161 if (dimension.transit_evaluator(vehicle)(node,
next) !=
162 dimension.FixedTransitVar(node)->Value()) {
170 bool DimensionFixedTransitsEqualTransitEvaluators(
171 const RoutingDimension& dimension) {
172 for (
int vehicle = 0; vehicle < dimension.model()->vehicles(); vehicle++) {
173 if (!DimensionFixedTransitsEqualTransitEvaluatorForVehicle(dimension,
181 class SetCumulsFromLocalDimensionCosts :
public DecisionBuilder {
183 SetCumulsFromLocalDimensionCosts(
184 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer>>*
186 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer>>*
188 SearchMonitor* monitor,
bool optimize_and_pack =
false)
189 : local_optimizers_(*local_optimizers),
190 local_mp_optimizers_(*local_mp_optimizers),
192 optimize_and_pack_(optimize_and_pack) {}
193 Decision* Next(Solver*
const solver)
override {
197 bool should_fail =
false;
198 for (
int i = 0; i < local_optimizers_.size(); ++i) {
199 const auto& local_optimizer = local_optimizers_[i];
200 const RoutingDimension*
const dimension = local_optimizer->dimension();
201 RoutingModel*
const model = dimension->model();
203 const auto compute_cumul_values =
204 [
this, &
next](LocalDimensionCumulOptimizer* optimizer,
int vehicle,
205 std::vector<int64>* cumul_values,
206 std::vector<int64>* break_start_end_values) {
207 if (optimize_and_pack_) {
208 return optimizer->ComputePackedRouteCumuls(
209 vehicle,
next, cumul_values, break_start_end_values);
211 return optimizer->ComputeRouteCumuls(vehicle,
next, cumul_values,
212 break_start_end_values);
215 for (
int vehicle = 0; vehicle <
model->vehicles(); ++vehicle) {
217 DCHECK(DimensionFixedTransitsEqualTransitEvaluatorForVehicle(*dimension,
219 const bool vehicle_has_break_constraint =
220 dimension->HasBreakConstraints() &&
221 !dimension->GetBreakIntervalsOfVehicle(vehicle).empty();
222 LocalDimensionCumulOptimizer*
const optimizer =
223 vehicle_has_break_constraint ? local_mp_optimizers_[i].get()
224 : local_optimizer.get();
225 DCHECK(optimizer !=
nullptr);
226 std::vector<int64> cumul_values;
227 std::vector<int64> break_start_end_values;
229 optimizer, vehicle, &cumul_values, &break_start_end_values);
236 cumul_values.clear();
237 break_start_end_values.clear();
238 DCHECK(local_mp_optimizers_[i] !=
nullptr);
239 if (compute_cumul_values(local_mp_optimizers_[i].get(), vehicle,
240 &cumul_values, &break_start_end_values) ==
250 std::vector<IntVar*> cp_variables;
251 std::vector<int64> cp_values;
252 std::swap(cp_values, cumul_values);
254 int current =
model->Start(vehicle);
256 cp_variables.push_back(dimension->CumulVar(current));
257 if (!
model->IsEnd(current)) {
258 current =
model->NextVar(current)->Value();
269 std::swap(cp_variables[1], cp_variables.back());
270 std::swap(cp_values[1], cp_values.back());
271 if (dimension->HasBreakConstraints()) {
273 dimension->GetBreakIntervalsOfVehicle(vehicle)) {
274 cp_variables.push_back(
interval->SafeStartExpr(0)->Var());
275 cp_variables.push_back(
interval->SafeEndExpr(0)->Var());
277 cp_values.insert(cp_values.end(), break_start_end_values.begin(),
278 break_start_end_values.end());
281 for (
int i = 0; i < cp_values.size(); ++i) {
283 cp_values[i] = cp_variables[i]->Min();
286 if (!solver->SolveAndCommit(
288 std::move(cp_values)),
302 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer>>&
304 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer>>&
305 local_mp_optimizers_;
306 SearchMonitor*
const monitor_;
307 const bool optimize_and_pack_;
310 class SetCumulsFromGlobalDimensionCosts :
public DecisionBuilder {
312 SetCumulsFromGlobalDimensionCosts(
313 const std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer>>*
315 SearchMonitor* monitor,
bool optimize_and_pack =
false)
316 : global_optimizers_(*global_optimizers),
318 optimize_and_pack_(optimize_and_pack) {}
319 Decision* Next(Solver*
const solver)
override {
323 bool should_fail =
false;
324 for (
const auto& global_optimizer : global_optimizers_) {
325 const RoutingDimension* dimension = global_optimizer->dimension();
326 RoutingModel*
const model = dimension->model();
330 DCHECK(DimensionFixedTransitsEqualTransitEvaluators(*dimension));
332 std::vector<int64> cumul_values;
333 std::vector<int64> break_start_end_values;
334 const bool cumuls_optimized =
336 ? global_optimizer->ComputePackedCumuls(
next, &cumul_values,
337 &break_start_end_values)
338 : global_optimizer->ComputeCumuls(
next, &cumul_values,
339 &break_start_end_values);
340 if (!cumuls_optimized) {
346 std::vector<IntVar*> cp_variables = dimension->cumuls();
347 std::vector<int64> cp_values;
348 std::swap(cp_values, cumul_values);
349 if (dimension->HasBreakConstraints()) {
350 const int num_vehicles =
model->vehicles();
351 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
353 dimension->GetBreakIntervalsOfVehicle(vehicle)) {
354 cp_variables.push_back(
interval->SafeStartExpr(0)->Var());
355 cp_variables.push_back(
interval->SafeEndExpr(0)->Var());
358 cp_values.insert(cp_values.end(), break_start_end_values.begin(),
359 break_start_end_values.end());
362 for (
int i = 0; i < cp_values.size(); ++i) {
364 cp_values[i] = cp_variables[i]->Min();
367 if (!solver->SolveAndCommit(
369 std::move(cp_values)),
382 const std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer>>&
384 SearchMonitor*
const monitor_;
385 const bool optimize_and_pack_;
391 const Assignment* original_assignment, absl::Duration duration_limit) {
393 if (original_assignment ==
nullptr)
return nullptr;
394 if (duration_limit <= absl::ZeroDuration())
return original_assignment;
395 if (global_dimension_optimizers_.empty() &&
396 local_dimension_optimizers_.empty()) {
397 DCHECK(local_dimension_mp_optimizers_.empty());
398 return original_assignment;
405 Assignment* packed_assignment = solver_->MakeAssignment();
409 std::vector<DecisionBuilder*> decision_builders;
410 decision_builders.push_back(solver_->MakeRestoreAssignment(preassignment_));
411 decision_builders.push_back(
412 solver_->MakeRestoreAssignment(packed_assignment));
413 decision_builders.push_back(
414 solver_->RevAlloc(
new SetCumulsFromLocalDimensionCosts(
415 &local_dimension_optimizers_, &local_dimension_mp_optimizers_,
416 GetOrCreateLargeNeighborhoodSearchLimit(),
418 decision_builders.push_back(
419 solver_->RevAlloc(
new SetCumulsFromGlobalDimensionCosts(
420 &global_dimension_optimizers_,
421 GetOrCreateLargeNeighborhoodSearchLimit(),
423 decision_builders.push_back(
424 CreateFinalizerForMinimizedAndMaximizedVariables());
427 solver_->Compose(decision_builders);
428 solver_->Solve(restore_pack_and_finalize,
429 packed_dimensions_assignment_collector_, limit);
431 if (packed_dimensions_assignment_collector_->
solution_count() != 1) {
432 LOG(
ERROR) <<
"The given assignment is not valid for this model, or cannot "
437 packed_assignment->
Copy(original_assignment);
439 packed_dimensions_assignment_collector_->
solution(0));
441 return packed_assignment;
446 class DifferentFromValues :
public Constraint {
448 DifferentFromValues(
Solver* solver,
IntVar*
var, std::vector<int64> values)
449 :
Constraint(solver), var_(
var), values_(std::move(values)) {}
450 void Post()
override {}
451 void InitialPropagate()
override { var_->RemoveValues(values_); }
452 std::string DebugString()
const override {
return "DifferentFromValues"; }
453 void Accept(ModelVisitor*
const visitor)
const override {
463 const std::vector<int64> values_;
477 template <
typename F>
478 class LightFunctionElementConstraint :
public Constraint {
480 LightFunctionElementConstraint(Solver*
const solver, IntVar*
const var,
481 IntVar*
const index, F values,
482 std::function<
bool()> deep_serialize)
483 : Constraint(solver),
486 values_(std::move(values)),
487 deep_serialize_(std::move(deep_serialize)) {}
488 ~LightFunctionElementConstraint()
override {}
490 void Post()
override {
492 solver(),
this, &LightFunctionElementConstraint::IndexBound,
494 index_->WhenBound(demon);
497 void InitialPropagate()
override {
498 if (index_->Bound()) {
503 std::string DebugString()
const override {
504 return "LightFunctionElementConstraint";
507 void Accept(ModelVisitor*
const visitor)
const override {
514 if (deep_serialize_()) {
515 visitor->VisitInt64ToInt64Extension(values_, index_->Min(),
522 void IndexBound() { var_->SetValue(values_(index_->Min())); }
525 IntVar*
const index_;
527 std::function<bool()> deep_serialize_;
530 template <
typename F>
531 Constraint* MakeLightElement(Solver*
const solver, IntVar*
const var,
532 IntVar*
const index, F values,
533 std::function<
bool()> deep_serialize) {
534 return solver->RevAlloc(
new LightFunctionElementConstraint<F>(
535 solver,
var,
index, std::move(values), std::move(deep_serialize)));
543 template <
typename F>
544 class LightFunctionElement2Constraint :
public Constraint {
546 LightFunctionElement2Constraint(Solver*
const solver, IntVar*
const var,
547 IntVar*
const index1, IntVar*
const index2,
549 std::function<
bool()> deep_serialize)
550 : Constraint(solver),
554 values_(std::move(values)),
555 deep_serialize_(std::move(deep_serialize)) {}
556 ~LightFunctionElement2Constraint()
override {}
557 void Post()
override {
559 solver(),
this, &LightFunctionElement2Constraint::IndexBound,
561 index1_->WhenBound(demon);
562 index2_->WhenBound(demon);
564 void InitialPropagate()
override { IndexBound(); }
566 std::string DebugString()
const override {
567 return "LightFunctionElement2Constraint";
570 void Accept(ModelVisitor*
const visitor)
const override {
579 const int64 index1_min = index1_->Min();
580 const int64 index1_max = index1_->Max();
583 if (deep_serialize_()) {
584 for (
int i = index1_min; i <= index1_max; ++i) {
585 visitor->VisitInt64ToInt64Extension(
586 [
this, i](
int64 j) {
return values_(i, j); }, index2_->Min(),
595 if (index1_->Bound() && index2_->Bound()) {
596 var_->SetValue(values_(index1_->Min(), index2_->Min()));
601 IntVar*
const index1_;
602 IntVar*
const index2_;
604 std::function<bool()> deep_serialize_;
607 template <
typename F>
608 Constraint* MakeLightElement2(Solver*
const solver, IntVar*
const var,
609 IntVar*
const index1, IntVar*
const index2,
610 F values, std::function<
bool()> deep_serialize) {
611 return solver->RevAlloc(
new LightFunctionElement2Constraint<F>(
612 solver,
var, index1, index2, std::move(values),
613 std::move(deep_serialize)));
617 template <
class A,
class B>
618 static int64 ReturnZero(A
a, B
b) {
624 for (
int i = 0; i < size1; i++) {
625 for (
int j = 0; j < size2; j++) {
650 : nodes_(index_manager.num_nodes()),
651 vehicles_(index_manager.num_vehicles()),
652 max_active_vehicles_(vehicles_),
653 fixed_cost_of_vehicle_(vehicles_, 0),
655 linear_cost_factor_of_vehicle_(vehicles_, 0),
656 quadratic_cost_factor_of_vehicle_(vehicles_, 0),
657 vehicle_amortized_cost_factors_set_(false),
658 consider_empty_route_costs_(vehicles_, false),
660 costs_are_homogeneous_across_vehicles_(
662 cache_callbacks_(false),
664 vehicle_pickup_delivery_policy_(vehicles_, PICKUP_AND_DELIVERY_NO_ORDER),
665 has_hard_type_incompatibilities_(false),
666 has_temporal_type_incompatibilities_(false),
667 has_same_vehicle_type_requirements_(false),
668 has_temporal_type_requirements_(false),
672 manager_(index_manager) {
674 vehicle_to_transit_cost_.assign(
678 cache_callbacks_ = (nodes_ <=
parameters.max_callback_cache_size());
681 ConstraintSolverParameters solver_parameters =
684 solver_ = absl::make_unique<Solver>(
"Routing", solver_parameters);
690 index_to_pickup_index_pairs_.resize(size);
691 index_to_delivery_index_pairs_.resize(size);
693 index_to_type_policy_.resize(index_manager.
num_indices());
696 for (
int v = 0; v < index_manager.
num_vehicles(); ++v) {
698 index_to_vehicle_[starts_[v]] = v;
700 index_to_vehicle_[ends_[v]] = v;
703 const std::vector<RoutingIndexManager::NodeIndex>& index_to_node =
705 index_to_equivalence_class_.resize(index_manager.
num_indices());
706 for (
int i = 0; i < index_to_node.size(); ++i) {
707 index_to_equivalence_class_[i] = index_to_node[i].value();
709 allowed_vehicles_.resize(
Size() + vehicles_);
712 void RoutingModel::Initialize() {
713 const int size =
Size();
715 solver_->MakeIntVarArray(size, 0, size + vehicles_ - 1,
"Nexts", &nexts_);
716 solver_->AddConstraint(solver_->MakeAllDifferent(nexts_,
false));
717 index_to_disjunctions_.resize(size + vehicles_);
720 solver_->MakeIntVarArray(size + vehicles_, -1, vehicles_ - 1,
"Vehicles",
723 solver_->MakeBoolVarArray(size,
"Active", &active_);
725 solver_->MakeBoolVarArray(vehicles_,
"ActiveVehicle", &vehicle_active_);
727 solver_->MakeBoolVarArray(vehicles_,
"VehicleCostsConsidered",
728 &vehicle_costs_considered_);
730 solver_->MakeBoolVarArray(size + vehicles_,
"IsBoundToEnd",
735 preassignment_ = solver_->MakeAssignment();
742 absl::flat_hash_set<RangeIntToIntFunction*> value_functions_delete;
743 absl::flat_hash_set<RangeMinMaxIndexFunction*> index_functions_delete;
744 for (
const auto& cache_line : state_dependent_transit_evaluators_cache_) {
745 for (
const auto& key_transit : *cache_line) {
746 value_functions_delete.insert(key_transit.second.transit);
747 index_functions_delete.insert(key_transit.second.transit_plus_identity);
758 return model->RegisterPositiveTransitCallback(std::move(
callback));
764 RoutingModel*
model) {
766 return model->RegisterPositiveUnaryTransitCallback(std::move(
callback));
768 return model->RegisterUnaryTransitCallback(std::move(
callback));
773 return RegisterUnaryCallback(
774 [
this, values = std::move(values)](
int64 i) {
778 std::all_of(std::cbegin(values), std::cend(values),
779 [](
int64 transit) {
return transit >= 0; }),
784 const int index = unary_transit_evaluators_.size();
785 unary_transit_evaluators_.push_back(std::move(
callback));
787 return unary_transit_evaluators_[
index](i);
792 std::vector<std::vector<int64> > values) {
793 bool all_transits_positive =
true;
794 for (
const std::vector<int64>& transit_values : values) {
795 all_transits_positive =
796 std::all_of(std::cbegin(transit_values), std::cend(transit_values),
797 [](
int64 transit) {
return transit >= 0; });
798 if (!all_transits_positive) {
802 return RegisterCallback(
803 [
this, values = std::move(values)](
int64 i,
int64 j) {
807 all_transits_positive,
this);
812 is_transit_evaluator_positive_.push_back(
true);
813 DCHECK(TransitCallbackPositive(
819 if (cache_callbacks_) {
821 std::vector<int64> cache(size * size, 0);
822 for (
int i = 0; i < size; ++i) {
823 for (
int j = 0; j < size; ++j) {
824 cache[i * size + j] =
callback(i, j);
827 transit_evaluators_.push_back(
828 [cache, size](
int64 i,
int64 j) {
return cache[i * size + j]; });
830 transit_evaluators_.push_back(std::move(
callback));
832 if (transit_evaluators_.size() != unary_transit_evaluators_.size()) {
833 DCHECK_EQ(transit_evaluators_.size(), unary_transit_evaluators_.size() + 1);
834 unary_transit_evaluators_.push_back(
nullptr);
836 if (transit_evaluators_.size() != is_transit_evaluator_positive_.size()) {
838 is_transit_evaluator_positive_.size() + 1);
839 is_transit_evaluator_positive_.push_back(
false);
841 return transit_evaluators_.size() - 1;
845 is_transit_evaluator_positive_.push_back(
true);
853 state_dependent_transit_evaluators_cache_.push_back(
854 absl::make_unique<StateDependentTransitCallbackCache>());
855 StateDependentTransitCallbackCache*
const cache =
856 state_dependent_transit_evaluators_cache_.back().get();
857 state_dependent_transit_evaluators_.push_back(
862 cache->insert({CacheKey(i, j),
value});
865 return state_dependent_transit_evaluators_.size() - 1;
868 void RoutingModel::AddNoCycleConstraintInternal() {
869 if (no_cycle_constraint_ ==
nullptr) {
870 no_cycle_constraint_ = solver_->MakeNoCycle(nexts_, active_);
871 solver_->AddConstraint(no_cycle_constraint_);
877 const std::string&
name) {
878 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
879 std::vector<int64> capacities(vehicles_,
capacity);
880 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
881 std::move(capacities),
882 fix_start_cumul_to_zero,
name);
887 bool fix_start_cumul_to_zero,
const std::string&
name) {
888 std::vector<int64> capacities(vehicles_,
capacity);
889 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
890 std::move(capacities),
891 fix_start_cumul_to_zero,
name);
895 int evaluator_index,
int64 slack_max, std::vector<int64> vehicle_capacities,
896 bool fix_start_cumul_to_zero,
const std::string&
name) {
897 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
898 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
899 std::move(vehicle_capacities),
900 fix_start_cumul_to_zero,
name);
904 const std::vector<int>& evaluator_indices,
int64 slack_max,
905 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
906 const std::string&
name) {
907 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
908 std::move(vehicle_capacities),
909 fix_start_cumul_to_zero,
name);
912 bool RoutingModel::AddDimensionWithCapacityInternal(
913 const std::vector<int>& evaluator_indices,
int64 slack_max,
914 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
915 const std::string&
name) {
916 CHECK_EQ(vehicles_, vehicle_capacities.size());
917 return InitializeDimensionInternal(
918 evaluator_indices, std::vector<int>(), slack_max, fix_start_cumul_to_zero,
922 bool RoutingModel::InitializeDimensionInternal(
923 const std::vector<int>& evaluator_indices,
924 const std::vector<int>& state_dependent_evaluator_indices,
int64 slack_max,
925 bool fix_start_cumul_to_zero, RoutingDimension* dimension) {
926 CHECK(dimension !=
nullptr);
927 CHECK_EQ(vehicles_, evaluator_indices.size());
928 CHECK((dimension->base_dimension_ ==
nullptr &&
929 state_dependent_evaluator_indices.empty()) ||
930 vehicles_ == state_dependent_evaluator_indices.size());
933 dimension_name_to_index_[dimension->name()] = dimension_index;
934 dimensions_.push_back(dimension);
935 dimension->Initialize(evaluator_indices, state_dependent_evaluator_indices,
937 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
938 nexts_, active_, dimension->cumuls(), dimension->transits()));
939 if (fix_start_cumul_to_zero) {
940 for (
int i = 0; i < vehicles_; ++i) {
941 IntVar*
const start_cumul = dimension->CumulVar(
Start(i));
943 start_cumul->SetValue(0);
954 const std::string& dimension_name) {
955 const int evaluator_index =
958 return std::make_pair(evaluator_index,
960 fix_start_cumul_to_zero, dimension_name));
964 std::vector<int64> values,
int64 capacity,
bool fix_start_cumul_to_zero,
965 const std::string& dimension_name) {
967 return std::make_pair(evaluator_index,
969 fix_start_cumul_to_zero, dimension_name));
974 bool fix_start_cumul_to_zero,
const std::string& dimension_name) {
976 return std::make_pair(evaluator_index,
978 fix_start_cumul_to_zero, dimension_name));
990 CHECK(callback_ !=
nullptr);
994 int64 Min()
const override {
996 const int idx_min = index_->Min();
997 const int idx_max = index_->Max() + 1;
998 return (idx_min < idx_max) ? callback_->RangeMin(idx_min, idx_max)
1001 void SetMin(
int64 new_min)
override {
1002 const int64 old_min = Min();
1003 const int64 old_max = Max();
1004 if (old_min < new_min && new_min <= old_max) {
1005 const int64 old_idx_min = index_->Min();
1006 const int64 old_idx_max = index_->Max() + 1;
1007 if (old_idx_min < old_idx_max) {
1008 const int64 new_idx_min = callback_->RangeFirstInsideInterval(
1009 old_idx_min, old_idx_max, new_min, old_max + 1);
1010 index_->SetMin(new_idx_min);
1011 if (new_idx_min < old_idx_max) {
1012 const int64 new_idx_max = callback_->RangeLastInsideInterval(
1013 new_idx_min, old_idx_max, new_min, old_max + 1);
1014 index_->SetMax(new_idx_max);
1019 int64 Max()
const override {
1021 const int idx_min = index_->Min();
1022 const int idx_max = index_->Max() + 1;
1023 return (idx_min < idx_max) ? callback_->RangeMax(idx_min, idx_max)
1026 void SetMax(
int64 new_max)
override {
1027 const int64 old_min = Min();
1028 const int64 old_max = Max();
1029 if (old_min <= new_max && new_max < old_max) {
1030 const int64 old_idx_min = index_->Min();
1031 const int64 old_idx_max = index_->Max() + 1;
1032 if (old_idx_min < old_idx_max) {
1033 const int64 new_idx_min = callback_->RangeFirstInsideInterval(
1034 old_idx_min, old_idx_max, old_min, new_max + 1);
1035 index_->SetMin(new_idx_min);
1036 if (new_idx_min < old_idx_max) {
1037 const int64 new_idx_max = callback_->RangeLastInsideInterval(
1038 new_idx_min, old_idx_max, old_min, new_max + 1);
1039 index_->SetMax(new_idx_max);
1044 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
1047 const RangeIntToIntFunction*
const callback_;
1048 IntVar*
const index_;
1051 IntExpr* MakeRangeMakeElementExpr(
const RangeIntToIntFunction*
callback,
1052 IntVar*
index, Solver* s) {
1053 return s->RegisterIntExpr(
1059 const std::vector<int>& dependent_transits,
1061 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
1062 const std::string&
name) {
1063 const std::vector<int> pure_transits(vehicles_, 0);
1065 pure_transits, dependent_transits, base_dimension, slack_max,
1066 std::move(vehicle_capacities), fix_start_cumul_to_zero,
name);
1071 int64 vehicle_capacity,
bool fix_start_cumul_to_zero,
1072 const std::string&
name) {
1074 0, transit, dimension, slack_max, vehicle_capacity,
1075 fix_start_cumul_to_zero,
name);
1078 bool RoutingModel::AddDimensionDependentDimensionWithVehicleCapacityInternal(
1079 const std::vector<int>& pure_transits,
1080 const std::vector<int>& dependent_transits,
1082 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
1083 const std::string&
name) {
1084 CHECK_EQ(vehicles_, vehicle_capacities.size());
1086 if (base_dimension ==
nullptr) {
1088 name, RoutingDimension::SelfBased());
1091 name, base_dimension);
1093 return InitializeDimensionInternal(pure_transits, dependent_transits,
1094 slack_max, fix_start_cumul_to_zero,
1099 int pure_transit,
int dependent_transit,
1101 int64 vehicle_capacity,
bool fix_start_cumul_to_zero,
1102 const std::string&
name) {
1103 std::vector<int> pure_transits(vehicles_, pure_transit);
1104 std::vector<int> dependent_transits(vehicles_, dependent_transit);
1105 std::vector<int64> vehicle_capacities(vehicles_, vehicle_capacity);
1106 return AddDimensionDependentDimensionWithVehicleCapacityInternal(
1107 pure_transits, dependent_transits, base_dimension, slack_max,
1108 std::move(vehicle_capacities), fix_start_cumul_to_zero,
name);
1114 const std::function<
int64(
int64)> g = [&f](
int64 x) {
return f(x) + x; };
1122 std::vector<std::string> dimension_names;
1123 for (
const auto& dimension_name_index : dimension_name_to_index_) {
1124 dimension_names.push_back(dimension_name_index.first);
1126 std::sort(dimension_names.begin(), dimension_names.end());
1127 return dimension_names;
1133 if (dim_index < 0 || dim_index >= global_optimizer_index_.
size() ||
1134 global_optimizer_index_[dim_index] < 0) {
1137 const int optimizer_index = global_optimizer_index_[dim_index];
1138 DCHECK_LT(optimizer_index, global_dimension_optimizers_.size());
1139 return global_dimension_optimizers_[optimizer_index].get();
1145 if (dim_index < 0 || dim_index >= local_optimizer_index_.
size() ||
1146 local_optimizer_index_[dim_index] < 0) {
1149 const int optimizer_index = local_optimizer_index_[dim_index];
1150 DCHECK_LT(optimizer_index, local_dimension_optimizers_.size());
1151 return local_dimension_optimizers_[optimizer_index].get();
1157 if (dim_index < 0 || dim_index >= local_optimizer_index_.
size() ||
1158 local_optimizer_index_[dim_index] < 0) {
1161 const int optimizer_index = local_optimizer_index_[dim_index];
1162 DCHECK_LT(optimizer_index, local_dimension_mp_optimizers_.size());
1163 return local_dimension_mp_optimizers_[optimizer_index].get();
1171 const std::string& dimension_name)
const {
1177 const std::string& dimension_name)
const {
1178 return *dimensions_[
gtl::FindOrDie(dimension_name_to_index_, dimension_name)];
1182 const std::string& dimension_name)
const {
1185 return dimensions_[
index];
1192 for (
int i = 0; i < vehicles_; ++i) {
1200 CHECK_LT(evaluator_index, transit_evaluators_.size());
1201 vehicle_to_transit_cost_[vehicle] = evaluator_index;
1205 for (
int i = 0; i < vehicles_; ++i) {
1212 return fixed_cost_of_vehicle_[vehicle];
1218 fixed_cost_of_vehicle_[vehicle] =
cost;
1222 int64 linear_cost_factor,
int64 quadratic_cost_factor) {
1223 for (
int v = 0; v < vehicles_; v++) {
1230 int64 quadratic_cost_factor,
1235 if (linear_cost_factor + quadratic_cost_factor > 0) {
1236 vehicle_amortized_cost_factors_set_ =
true;
1238 linear_cost_factor_of_vehicle_[vehicle] = linear_cost_factor;
1239 quadratic_cost_factor_of_vehicle_[vehicle] = quadratic_cost_factor;
1245 struct CostClassComparator {
1252 struct VehicleClassComparator {
1253 bool operator()(
const RoutingModel::VehicleClass&
a,
1254 const RoutingModel::VehicleClass&
b)
const {
1264 void RoutingModel::ComputeCostClasses(
1267 cost_classes_.reserve(vehicles_);
1268 cost_classes_.clear();
1269 cost_class_index_of_vehicle_.assign(vehicles_,
CostClassIndex(-1));
1270 std::map<CostClass, CostClassIndex, CostClassComparator> cost_class_map;
1273 const CostClass zero_cost_class(0);
1274 cost_classes_.push_back(zero_cost_class);
1275 DCHECK_EQ(cost_classes_[kCostClassIndexOfZeroCost].evaluator_index, 0);
1276 cost_class_map[zero_cost_class] = kCostClassIndexOfZeroCost;
1281 has_vehicle_with_zero_cost_class_ =
false;
1282 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1283 CostClass cost_class(vehicle_to_transit_cost_[vehicle]);
1287 const int64 coeff = dimension->vehicle_span_cost_coefficients()[vehicle];
1288 if (coeff == 0)
continue;
1289 cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1290 .push_back({dimension->vehicle_to_class(vehicle), coeff, dimension});
1292 std::sort(cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1294 cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1300 if (cost_class_index == kCostClassIndexOfZeroCost) {
1301 has_vehicle_with_zero_cost_class_ =
true;
1302 }
else if (cost_class_index == num_cost_classes) {
1303 cost_classes_.push_back(cost_class);
1305 cost_class_index_of_vehicle_[vehicle] = cost_class_index;
1319 costs_are_homogeneous_across_vehicles_ &= has_vehicle_with_zero_cost_class_
1326 return std::tie(
a.cost_class_index,
a.fixed_cost,
a.start_equivalence_class,
1327 a.end_equivalence_class,
a.unvisitable_nodes_fprint,
1328 a.dimension_start_cumuls_min,
a.dimension_start_cumuls_max,
1329 a.dimension_end_cumuls_min,
a.dimension_end_cumuls_max,
1330 a.dimension_capacities,
a.dimension_evaluator_classes) <
1331 std::tie(
b.cost_class_index,
b.fixed_cost,
b.start_equivalence_class,
1332 b.end_equivalence_class,
b.unvisitable_nodes_fprint,
1333 b.dimension_start_cumuls_min,
b.dimension_start_cumuls_max,
1334 b.dimension_end_cumuls_min,
b.dimension_end_cumuls_max,
1335 b.dimension_capacities,
b.dimension_evaluator_classes);
1338 void RoutingModel::ComputeVehicleClasses() {
1339 vehicle_classes_.reserve(vehicles_);
1340 vehicle_classes_.clear();
1342 std::map<VehicleClass, VehicleClassIndex, VehicleClassComparator>
1344 const int nodes_unvisitability_num_bytes = (vehicle_vars_.size() + 7) / 8;
1345 std::unique_ptr<char[]> nodes_unvisitability_bitmask(
1346 new char[nodes_unvisitability_num_bytes]);
1347 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1350 vehicle_class.
fixed_cost = fixed_cost_of_vehicle_[vehicle];
1352 index_to_equivalence_class_[
Start(vehicle)];
1354 index_to_equivalence_class_[
End(vehicle)];
1356 IntVar*
const start_cumul_var = dimension->cumuls()[
Start(vehicle)];
1358 start_cumul_var->
Min());
1360 start_cumul_var->
Max());
1361 IntVar*
const end_cumul_var = dimension->cumuls()[
End(vehicle)];
1365 dimension->vehicle_capacities()[vehicle]);
1367 dimension->vehicle_to_class(vehicle));
1369 memset(nodes_unvisitability_bitmask.get(), 0,
1370 nodes_unvisitability_num_bytes);
1374 (!vehicle_var->
Contains(vehicle) ||
1376 nodes_unvisitability_bitmask[
index / CHAR_BIT] |= 1U
1377 << (
index % CHAR_BIT);
1381 nodes_unvisitability_bitmask.get(), nodes_unvisitability_num_bytes);
1384 &vehicle_class_map, vehicle_class, num_vehicle_classes);
1385 if (vehicle_class_index == num_vehicle_classes) {
1386 vehicle_classes_.push_back(vehicle_class);
1388 vehicle_class_index_of_vehicle_[vehicle] = vehicle_class_index;
1392 void RoutingModel::ComputeVehicleTypes() {
1393 const int nodes_squared = nodes_ * nodes_;
1394 std::vector<int>& type_index_of_vehicle =
1396 std::vector<std::set<VehicleTypeContainer::VehicleClassEntry>>&
1397 sorted_vehicle_classes_per_type =
1399 std::vector<std::deque<int>>& vehicles_per_vehicle_class =
1402 type_index_of_vehicle.resize(vehicles_);
1403 sorted_vehicle_classes_per_type.clear();
1404 sorted_vehicle_classes_per_type.reserve(vehicles_);
1405 vehicles_per_vehicle_class.clear();
1408 absl::flat_hash_map<int64, int> type_to_type_index;
1410 for (
int v = 0; v < vehicles_; v++) {
1414 const int64 type = cost_class * nodes_squared + start * nodes_ + end;
1416 const auto& vehicle_type_added = type_to_type_index.insert(
1417 std::make_pair(type, type_to_type_index.size()));
1419 const int index = vehicle_type_added.first->second;
1422 const VehicleTypeContainer::VehicleClassEntry class_entry = {
1425 if (vehicle_type_added.second) {
1428 sorted_vehicle_classes_per_type.push_back({class_entry});
1432 sorted_vehicle_classes_per_type[
index].insert(class_entry);
1434 vehicles_per_vehicle_class[vehicle_class].push_back(v);
1435 type_index_of_vehicle[v] =
index;
1439 void RoutingModel::FinalizeVisitTypes() {
1445 single_nodes_of_type_.clear();
1446 single_nodes_of_type_.resize(num_visit_types_);
1447 pair_indices_of_type_.clear();
1448 pair_indices_of_type_.resize(num_visit_types_);
1449 std::vector<absl::flat_hash_set<int>> pair_indices_added_for_type(
1454 if (visit_type < 0) {
1457 const std::vector<std::pair<int, int>>& pickup_index_pairs =
1458 index_to_pickup_index_pairs_[
index];
1459 const std::vector<std::pair<int, int>>& delivery_index_pairs =
1460 index_to_delivery_index_pairs_[
index];
1461 if (pickup_index_pairs.empty() && delivery_index_pairs.empty()) {
1462 single_nodes_of_type_[visit_type].push_back(
index);
1464 for (
const std::vector<std::pair<int, int>>* index_pairs :
1465 {&pickup_index_pairs, &delivery_index_pairs}) {
1466 for (
const std::pair<int, int>& index_pair : *index_pairs) {
1467 const int pair_index = index_pair.first;
1468 if (pair_indices_added_for_type[visit_type].insert(pair_index).second) {
1469 pair_indices_of_type_[visit_type].push_back(pair_index);
1475 TopologicallySortVisitTypes();
1478 void RoutingModel::TopologicallySortVisitTypes() {
1479 if (!has_same_vehicle_type_requirements_ &&
1480 !has_temporal_type_requirements_) {
1483 std::vector<std::pair<double, double>> type_requirement_tightness(
1484 num_visit_types_, {0, 0});
1485 std::vector<absl::flat_hash_set<int>> type_to_dependent_types(
1487 SparseBitset<> types_in_requirement_graph(num_visit_types_);
1488 std::vector<int> in_degree(num_visit_types_, 0);
1489 for (
int type = 0; type < num_visit_types_; type++) {
1490 int num_alternative_required_types = 0;
1491 int num_required_sets = 0;
1492 for (
const std::vector<absl::flat_hash_set<int>>*
1493 required_type_alternatives :
1494 {&required_type_alternatives_when_adding_type_index_[type],
1495 &required_type_alternatives_when_removing_type_index_[type],
1496 &same_vehicle_required_type_alternatives_per_type_index_[type]}) {
1497 for (
const absl::flat_hash_set<int>& alternatives :
1498 *required_type_alternatives) {
1499 types_in_requirement_graph.Set(type);
1500 num_required_sets++;
1501 for (
int required_type : alternatives) {
1502 type_requirement_tightness[required_type].second +=
1503 1.0 / alternatives.size();
1504 types_in_requirement_graph.Set(required_type);
1505 num_alternative_required_types++;
1506 if (type_to_dependent_types[required_type].insert(type).second) {
1512 if (num_alternative_required_types > 0) {
1513 type_requirement_tightness[type].first += 1.0 * num_required_sets *
1515 num_alternative_required_types;
1520 topologically_sorted_visit_types_.clear();
1521 std::vector<int> current_types_with_zero_indegree;
1522 for (
int type : types_in_requirement_graph.PositionsSetAtLeastOnce()) {
1523 DCHECK(type_requirement_tightness[type].first > 0 ||
1524 type_requirement_tightness[type].second > 0);
1525 if (in_degree[type] == 0) {
1526 current_types_with_zero_indegree.push_back(type);
1530 int num_types_added = 0;
1531 while (!current_types_with_zero_indegree.empty()) {
1534 topologically_sorted_visit_types_.push_back({});
1535 std::vector<int>& topological_group =
1536 topologically_sorted_visit_types_.back();
1537 std::vector<int> next_types_with_zero_indegree;
1538 for (
int type : current_types_with_zero_indegree) {
1539 topological_group.push_back(type);
1541 for (
int dependent_type : type_to_dependent_types[type]) {
1542 DCHECK_GT(in_degree[dependent_type], 0);
1543 if (--in_degree[dependent_type] == 0) {
1544 next_types_with_zero_indegree.push_back(dependent_type);
1555 std::sort(topological_group.begin(), topological_group.end(),
1556 [&type_requirement_tightness](
int type1,
int type2) {
1557 const auto& tightness1 = type_requirement_tightness[type1];
1558 const auto& tightness2 = type_requirement_tightness[type2];
1559 return tightness1 > tightness2 ||
1560 (tightness1 == tightness2 && type1 < type2);
1563 current_types_with_zero_indegree.swap(next_types_with_zero_indegree);
1566 const int num_types_in_requirement_graph =
1567 types_in_requirement_graph.NumberOfSetCallsWithDifferentArguments();
1568 DCHECK_LE(num_types_added, num_types_in_requirement_graph);
1569 if (num_types_added < num_types_in_requirement_graph) {
1571 topologically_sorted_visit_types_.clear();
1576 const std::vector<int64>& indices,
int64 penalty,
int64 max_cardinality) {
1578 for (
int i = 0; i < indices.size(); ++i) {
1583 disjunctions_.
push_back({indices, {penalty, max_cardinality}});
1585 index_to_disjunctions_[
index].push_back(disjunction_index);
1587 return disjunction_index;
1590 std::vector<std::pair<int64, int64>>
1592 std::vector<std::pair<int64, int64>> var_index_pairs;
1593 for (
const Disjunction& disjunction : disjunctions_) {
1594 const std::vector<int64>&
var_indices = disjunction.indices;
1598 if (index_to_disjunctions_[v0].size() == 1 &&
1599 index_to_disjunctions_[v1].size() == 1) {
1604 std::sort(var_index_pairs.begin(), var_index_pairs.end());
1605 return var_index_pairs;
1610 for (Disjunction& disjunction : disjunctions_) {
1611 bool has_one_potentially_active_var =
false;
1612 for (
const int64 var_index : disjunction.indices) {
1614 has_one_potentially_active_var =
true;
1618 if (!has_one_potentially_active_var) {
1619 disjunction.value.max_cardinality = 0;
1625 const std::vector<int64>& indices = disjunctions_[disjunction].indices;
1626 const int indices_size = indices.
size();
1627 std::vector<IntVar*> disjunction_vars(indices_size);
1628 for (
int i = 0; i < indices_size; ++i) {
1633 const int64 max_cardinality =
1634 disjunctions_[disjunction].value.max_cardinality;
1635 IntVar* no_active_var = solver_->MakeBoolVar();
1636 IntVar* number_active_vars = solver_->MakeIntVar(0, max_cardinality);
1637 solver_->AddConstraint(
1638 solver_->MakeSumEquality(disjunction_vars, number_active_vars));
1639 solver_->AddConstraint(solver_->MakeIsDifferentCstCt(
1640 number_active_vars, max_cardinality, no_active_var));
1641 const int64 penalty = disjunctions_[disjunction].value.penalty;
1643 no_active_var->SetMax(0);
1646 return solver_->MakeProd(no_active_var, penalty)->Var();
1651 const std::vector<int64>& indices,
int64 cost) {
1652 if (!indices.empty()) {
1653 ValuedNodes<int64> same_vehicle_cost;
1655 same_vehicle_cost.indices.push_back(
index);
1657 same_vehicle_cost.value =
cost;
1658 same_vehicle_costs_.push_back(same_vehicle_cost);
1664 auto& allowed_vehicles = allowed_vehicles_[
index];
1665 allowed_vehicles.clear();
1667 allowed_vehicles.insert(vehicle);
1672 AddPickupAndDeliverySetsInternal({pickup}, {delivery});
1681 pickup_delivery_disjunctions_.push_back(
1682 {pickup_disjunction, delivery_disjunction});
1685 void RoutingModel::AddPickupAndDeliverySetsInternal(
1686 const std::vector<int64>& pickups,
const std::vector<int64>& deliveries) {
1687 if (pickups.empty() || deliveries.empty()) {
1691 const int pair_index = pickup_delivery_pairs_.size();
1692 for (
int pickup_index = 0; pickup_index < pickups.size(); pickup_index++) {
1693 const int64 pickup = pickups[pickup_index];
1695 index_to_pickup_index_pairs_[pickup].emplace_back(pair_index, pickup_index);
1697 for (
int delivery_index = 0; delivery_index < deliveries.size();
1699 const int64 delivery = deliveries[delivery_index];
1701 index_to_delivery_index_pairs_[delivery].emplace_back(pair_index,
1704 pickup_delivery_pairs_.push_back({pickups, deliveries});
1708 int64 node_index)
const {
1709 CHECK_LT(node_index, index_to_pickup_index_pairs_.size());
1710 return index_to_pickup_index_pairs_[node_index];
1714 int64 node_index)
const {
1715 CHECK_LT(node_index, index_to_delivery_index_pairs_.size());
1716 return index_to_delivery_index_pairs_[node_index];
1722 vehicle_pickup_delivery_policy_[vehicle] = policy;
1728 for (
int i = 0; i < vehicles_; ++i) {
1736 return vehicle_pickup_delivery_policy_[vehicle];
1741 for (
int i = 0; i <
Nexts().size(); ++i) {
1751 IntVar* RoutingModel::CreateSameVehicleCost(
int vehicle_index) {
1752 const std::vector<int64>& indices =
1753 same_vehicle_costs_[vehicle_index].indices;
1754 CHECK(!indices.empty());
1755 std::vector<IntVar*> vehicle_counts;
1756 solver_->MakeIntVarArray(vehicle_vars_.size() + 1, 0, indices.size() + 1,
1758 std::vector<int64> vehicle_values(vehicle_vars_.size() + 1);
1759 for (
int i = 0; i < vehicle_vars_.size(); ++i) {
1760 vehicle_values[i] = i;
1762 vehicle_values[vehicle_vars_.size()] = -1;
1763 std::vector<IntVar*> vehicle_vars;
1764 vehicle_vars.reserve(indices.size());
1766 vehicle_vars.push_back(vehicle_vars_[
index]);
1768 solver_->AddConstraint(solver_->MakeDistribute(vehicle_vars, vehicle_counts));
1769 std::vector<IntVar*> vehicle_used;
1770 for (
int i = 0; i < vehicle_vars_.size() + 1; ++i) {
1771 vehicle_used.push_back(
1772 solver_->MakeIsGreaterOrEqualCstVar(vehicle_counts[i], 1));
1774 vehicle_used.push_back(solver_->MakeIntConst(-1));
1776 ->MakeProd(solver_->MakeMax(solver_->MakeSum(vehicle_used), 0),
1777 same_vehicle_costs_[vehicle_index].value)
1782 extra_operators_.push_back(ls_operator);
1789 void RoutingModel::AppendHomogeneousArcCosts(
1790 const RoutingSearchParameters&
parameters,
int node_index,
1791 std::vector<IntVar*>* cost_elements) {
1792 CHECK(cost_elements !=
nullptr);
1793 const auto arc_cost_evaluator = [
this, node_index](
int64 next_index) {
1800 IntVar*
const base_cost_var = solver_->MakeIntVar(0,
kint64max);
1801 solver_->AddConstraint(MakeLightElement(
1802 solver_.get(), base_cost_var, nexts_[node_index], arc_cost_evaluator,
1803 [
this]() { return enable_deep_serialization_; }));
1805 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
1806 cost_elements->push_back(
var);
1808 IntExpr*
const expr =
1809 solver_->MakeElement(arc_cost_evaluator, nexts_[node_index]);
1810 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
1811 cost_elements->push_back(
var);
1815 void RoutingModel::AppendArcCosts(
const RoutingSearchParameters&
parameters,
1817 std::vector<IntVar*>* cost_elements) {
1818 CHECK(cost_elements !=
nullptr);
1824 IntVar*
const base_cost_var = solver_->MakeIntVar(0,
kint64max);
1825 solver_->AddConstraint(MakeLightElement2(
1826 solver_.get(), base_cost_var, nexts_[node_index],
1827 vehicle_vars_[node_index],
1828 [
this, node_index](
int64 to,
int64 vehicle) {
1829 return GetArcCostForVehicle(node_index, to, vehicle);
1831 [
this]() { return enable_deep_serialization_; }));
1833 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
1834 cost_elements->push_back(
var);
1836 IntVar*
const vehicle_class_var =
1840 return SafeGetCostClassInt64OfVehicle(
index);
1842 vehicle_vars_[node_index])
1844 IntExpr*
const expr = solver_->MakeElement(
1848 nexts_[node_index], vehicle_class_var);
1849 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
1850 cost_elements->push_back(
var);
1854 int RoutingModel::GetVehicleStartClass(
int64 start_index)
const {
1855 const int vehicle = index_to_vehicle_[start_index];
1862 std::string RoutingModel::FindErrorInSearchParametersForModel(
1863 const RoutingSearchParameters& search_parameters)
const {
1865 search_parameters.first_solution_strategy();
1866 if (GetFirstSolutionDecisionBuilder(search_parameters) ==
nullptr) {
1867 return absl::StrCat(
1868 "Undefined first solution strategy: ",
1869 FirstSolutionStrategy::Value_Name(first_solution_strategy),
1870 " (int value: ", first_solution_strategy,
")");
1872 if (search_parameters.first_solution_strategy() ==
1873 FirstSolutionStrategy::SWEEP &&
1875 return "Undefined sweep arranger for ROUTING_SWEEP strategy.";
1880 void RoutingModel::QuietCloseModel() {
1891 same_vehicle_components_.SetNumberOfNodes(
model->Size());
1892 for (
const std::string&
name :
model->GetAllDimensionNames()) {
1894 const std::vector<IntVar*>& cumuls = dimension->
cumuls();
1895 for (
int i = 0; i < cumuls.size(); ++i) {
1896 cumul_to_dim_indices_[cumuls[i]] = {dimension, i};
1899 const std::vector<IntVar*>& vehicle_vars =
model->VehicleVars();
1900 for (
int i = 0; i < vehicle_vars.size(); ++i) {
1901 vehicle_var_to_indices_[vehicle_vars[i]] = i;
1903 RegisterInspectors();
1907 const std::vector<int> node_to_same_vehicle_component_id =
1908 same_vehicle_components_.GetComponentIds();
1909 model_->InitSameVehicleGroups(
1910 same_vehicle_components_.GetNumberOfComponents());
1911 for (
int node = 0; node < model_->Size(); ++node) {
1912 model_->SetSameVehicleGroup(node,
1913 node_to_same_vehicle_component_id[node]);
1919 const Constraint*
const constraint)
override {
1923 IntExpr*
const expr)
override {
1925 [](
const IntExpr* expr) {})(expr);
1928 const std::vector<int64>& values)
override {
1930 [](
const std::vector<int64>& int_array) {})(values);
1934 using ExprInspector = std::function<void(
const IntExpr*)>;
1935 using ArrayInspector = std::function<void(
const std::vector<int64>&)>;
1936 using ConstraintInspector = std::function<void()>;
1938 void RegisterInspectors() {
1939 expr_inspectors_[kExpressionArgument] = [
this](
const IntExpr* expr) {
1942 expr_inspectors_[kLeftArgument] = [
this](
const IntExpr* expr) {
1945 expr_inspectors_[kRightArgument] = [
this](
const IntExpr* expr) {
1948 array_inspectors_[kStartsArgument] =
1949 [
this](
const std::vector<int64>& int_array) {
1950 starts_argument_ = int_array;
1952 array_inspectors_[kEndsArgument] =
1953 [
this](
const std::vector<int64>& int_array) {
1954 ends_argument_ = int_array;
1956 constraint_inspectors_[kNotMember] = [
this]() {
1957 std::pair<RoutingDimension*, int> dim_index;
1960 const int index = dim_index.second;
1961 dimension->forbidden_intervals_[
index].InsertIntervals(starts_argument_,
1963 VLOG(2) << dimension->name() <<
" " <<
index <<
": "
1964 << dimension->forbidden_intervals_[
index].DebugString();
1967 starts_argument_.clear();
1968 ends_argument_.clear();
1970 constraint_inspectors_[kEquality] = [
this]() {
1972 int right_index = 0;
1973 if (
gtl::FindCopy(vehicle_var_to_indices_, left_, &left_index) &&
1974 gtl::FindCopy(vehicle_var_to_indices_, right_, &right_index)) {
1975 VLOG(2) <<
"Vehicle variables for " << left_index <<
" and "
1976 << right_index <<
" are equal.";
1977 same_vehicle_components_.AddEdge(left_index, right_index);
1982 constraint_inspectors_[kLessOrEqual] = [
this]() {
1983 std::pair<RoutingDimension*, int> left_index;
1984 std::pair<RoutingDimension*, int> right_index;
1985 if (
gtl::FindCopy(cumul_to_dim_indices_, left_, &left_index) &&
1986 gtl::FindCopy(cumul_to_dim_indices_, right_, &right_index)) {
1988 if (dimension == right_index.first) {
1989 VLOG(2) <<
"For dimension " << dimension->name() <<
", cumul for "
1990 << left_index.second <<
" is less than " << right_index.second
1992 dimension->path_precedence_graph_.AddArc(left_index.second,
1993 right_index.second);
2003 absl::flat_hash_map<const IntExpr*, std::pair<RoutingDimension*, int>>
2004 cumul_to_dim_indices_;
2005 absl::flat_hash_map<const IntExpr*, int> vehicle_var_to_indices_;
2006 absl::flat_hash_map<std::string, ExprInspector> expr_inspectors_;
2007 absl::flat_hash_map<std::string, ArrayInspector> array_inspectors_;
2008 absl::flat_hash_map<std::string, ConstraintInspector> constraint_inspectors_;
2009 const IntExpr*
expr_ =
nullptr;
2010 const IntExpr* left_ =
nullptr;
2011 const IntExpr* right_ =
nullptr;
2012 std::vector<int64> starts_argument_;
2013 std::vector<int64> ends_argument_;
2016 void RoutingModel::DetectImplicitPickupAndDeliveries() {
2017 std::vector<int> non_pickup_delivery_nodes;
2018 for (
int node = 0; node <
Size(); ++node) {
2021 non_pickup_delivery_nodes.push_back(node);
2025 std::set<std::pair<int64, int64>> implicit_pickup_deliveries;
2027 if (dimension->class_evaluators_.size() != 1) {
2032 if (transit ==
nullptr)
continue;
2033 absl::flat_hash_map<int64, std::vector<int64>> nodes_by_positive_demand;
2034 absl::flat_hash_map<int64, std::vector<int64>> nodes_by_negative_demand;
2035 for (
int node : non_pickup_delivery_nodes) {
2038 nodes_by_positive_demand[
demand].push_back(node);
2040 nodes_by_negative_demand[-
demand].push_back(node);
2043 for (
const auto& [
demand, positive_nodes] : nodes_by_positive_demand) {
2044 const std::vector<int64>*
const negative_nodes =
2046 if (negative_nodes !=
nullptr) {
2047 for (
int64 positive_node : positive_nodes) {
2048 for (
int64 negative_node : *negative_nodes) {
2049 implicit_pickup_deliveries.insert({positive_node, negative_node});
2055 implicit_pickup_delivery_pairs_without_alternatives_.clear();
2056 for (
auto [pickup, delivery] : implicit_pickup_deliveries) {
2057 implicit_pickup_delivery_pairs_without_alternatives_.emplace_back(
2058 std::vector<int64>({pickup}), std::vector<int64>({delivery}));
2065 if (!error.empty()) {
2067 LOG(
ERROR) <<
"Invalid RoutingSearchParameters: " << error;
2077 dimension->CloseModel(UsesLightPropagation(
parameters));
2080 ComputeVehicleClasses();
2081 ComputeVehicleTypes();
2082 FinalizeVisitTypes();
2083 vehicle_start_class_callback_ = [
this](
int64 start) {
2084 return GetVehicleStartClass(start);
2087 AddNoCycleConstraintInternal();
2089 const int size =
Size();
2092 for (
int i = 0; i < vehicles_; ++i) {
2093 const int64 start = starts_[i];
2094 const int64 end = ends_[i];
2095 solver_->AddConstraint(
2096 solver_->MakeEquality(vehicle_vars_[start], solver_->MakeIntConst(i)));
2097 solver_->AddConstraint(
2098 solver_->MakeEquality(vehicle_vars_[end], solver_->MakeIntConst(i)));
2099 solver_->AddConstraint(
2100 solver_->MakeIsDifferentCstCt(nexts_[start], end, vehicle_active_[i]));
2101 if (consider_empty_route_costs_[i]) {
2102 vehicle_costs_considered_[i]->SetMin(1);
2104 solver_->AddConstraint(solver_->MakeEquality(
2105 vehicle_active_[i], vehicle_costs_considered_[i]));
2110 if (vehicles_ > max_active_vehicles_) {
2111 solver_->AddConstraint(
2112 solver_->MakeSumLessOrEqual(vehicle_active_, max_active_vehicles_));
2120 if (vehicles_ > 1) {
2121 std::vector<IntVar*> zero_transit(size, solver_->MakeIntConst(0));
2122 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
2123 nexts_, active_, vehicle_vars_, zero_transit));
2128 for (
int i = 0; i < size; ++i) {
2130 active_[i]->SetValue(1);
2136 const absl::flat_hash_set<VisitTypePolicy>*
const infeasible_policies =
2138 if (infeasible_policies !=
nullptr &&
2140 active_[i]->SetValue(0);
2145 for (
int i = 0; i < allowed_vehicles_.size(); ++i) {
2146 const auto& allowed_vehicles = allowed_vehicles_[i];
2147 if (!allowed_vehicles.empty()) {
2149 vehicles.reserve(allowed_vehicles.size() + 1);
2151 for (
int vehicle : allowed_vehicles) {
2159 for (
int i = 0; i < size; ++i) {
2161 solver_->AddConstraint(solver_->RevAlloc(
2162 new DifferentFromValues(solver_.get(), nexts_[i], starts_)));
2164 solver_->AddConstraint(
2165 solver_->MakeIsDifferentCstCt(nexts_[i], i, active_[i]));
2170 for (
int i = 0; i < size; ++i) {
2171 solver_->AddConstraint(
2172 solver_->MakeIsDifferentCstCt(vehicle_vars_[i], -1, active_[i]));
2176 solver_->AddConstraint(
2181 for (
int i = 0; i < vehicles_; ++i) {
2182 std::vector<int64> forbidden_ends;
2183 forbidden_ends.reserve(vehicles_ - 1);
2184 for (
int j = 0; j < vehicles_; ++j) {
2186 forbidden_ends.push_back(ends_[j]);
2189 solver_->AddConstraint(solver_->RevAlloc(
new DifferentFromValues(
2190 solver_.get(), nexts_[starts_[i]], std::move(forbidden_ends))));
2194 for (
const int64 end : ends_) {
2195 is_bound_to_end_[end]->SetValue(1);
2198 std::vector<IntVar*> cost_elements;
2200 if (vehicles_ > 0) {
2201 for (
int node_index = 0; node_index < size; ++node_index) {
2203 AppendHomogeneousArcCosts(
parameters, node_index, &cost_elements);
2205 AppendArcCosts(
parameters, node_index, &cost_elements);
2208 if (vehicle_amortized_cost_factors_set_) {
2209 std::vector<IntVar*> route_lengths;
2210 solver_->MakeIntVarArray(vehicles_, 0, size, &route_lengths);
2211 solver_->AddConstraint(
2212 solver_->MakeDistribute(vehicle_vars_, route_lengths));
2213 std::vector<IntVar*> vehicle_used;
2214 for (
int i = 0; i < vehicles_; i++) {
2216 vehicle_used.push_back(
2217 solver_->MakeIsGreaterCstVar(route_lengths[i], 2));
2220 ->MakeProd(solver_->MakeOpposite(solver_->MakeSquare(
2221 solver_->MakeSum(route_lengths[i], -2))),
2222 quadratic_cost_factor_of_vehicle_[i])
2224 cost_elements.push_back(
var);
2226 IntVar*
const vehicle_usage_cost =
2227 solver_->MakeScalProd(vehicle_used, linear_cost_factor_of_vehicle_)
2229 cost_elements.push_back(vehicle_usage_cost);
2234 dimension->SetupGlobalSpanCost(&cost_elements);
2235 dimension->SetupSlackAndDependentTransitCosts();
2236 const std::vector<int64>& span_costs =
2237 dimension->vehicle_span_cost_coefficients();
2238 const std::vector<int64>& span_ubs = dimension->vehicle_span_upper_bounds();
2239 const bool has_span_constraint =
2240 std::any_of(span_costs.begin(), span_costs.end(),
2241 [](
int64 coeff) { return coeff != 0; }) ||
2242 std::any_of(span_ubs.begin(), span_ubs.end(),
2243 [](
int64 value) { return value < kint64max; }) ||
2244 dimension->HasSoftSpanUpperBounds() ||
2245 dimension->HasQuadraticCostSoftSpanUpperBounds();
2246 if (has_span_constraint) {
2247 std::vector<IntVar*> spans(
vehicles(),
nullptr);
2248 std::vector<IntVar*> total_slacks(
vehicles(),
nullptr);
2250 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2252 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2254 if (span_costs[vehicle] != 0) {
2255 total_slacks[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2258 if (dimension->HasSoftSpanUpperBounds()) {
2259 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2260 if (spans[vehicle])
continue;
2262 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2263 if (bound_cost.
cost == 0)
continue;
2264 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2267 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2268 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2269 if (spans[vehicle])
continue;
2271 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2272 if (bound_cost.
cost == 0)
continue;
2273 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2276 solver_->AddConstraint(
2280 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2281 if (!spans[vehicle] && !total_slacks[vehicle])
continue;
2282 if (spans[vehicle]) {
2291 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2292 if (span_costs[vehicle] == 0)
continue;
2293 DCHECK(total_slacks[vehicle] !=
nullptr);
2294 IntVar*
const slack_amount =
2296 ->MakeProd(vehicle_costs_considered_[vehicle],
2297 total_slacks[vehicle])
2299 IntVar*
const slack_cost =
2300 solver_->MakeProd(slack_amount, span_costs[vehicle])->Var();
2301 cost_elements.push_back(slack_cost);
2303 span_costs[vehicle]);
2305 if (dimension->HasSoftSpanUpperBounds()) {
2306 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2307 const auto bound_cost =
2308 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2309 if (bound_cost.cost == 0 || bound_cost.bound ==
kint64max)
continue;
2310 DCHECK(spans[vehicle] !=
nullptr);
2313 IntVar*
const span_violation_amount =
2316 vehicle_costs_considered_[vehicle],
2318 solver_->MakeSum(spans[vehicle], -bound_cost.bound),
2321 IntVar*
const span_violation_cost =
2322 solver_->MakeProd(span_violation_amount, bound_cost.cost)->Var();
2323 cost_elements.push_back(span_violation_cost);
2328 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2329 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2330 const auto bound_cost =
2331 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2332 if (bound_cost.cost == 0 || bound_cost.bound ==
kint64max)
continue;
2333 DCHECK(spans[vehicle] !=
nullptr);
2336 IntExpr* max0 = solver_->MakeMax(
2337 solver_->MakeSum(spans[vehicle], -bound_cost.bound), 0);
2338 IntVar*
const squared_span_violation_amount =
2340 ->MakeProd(vehicle_costs_considered_[vehicle],
2341 solver_->MakeSquare(max0))
2343 IntVar*
const span_violation_cost =
2344 solver_->MakeProd(squared_span_violation_amount, bound_cost.cost)
2346 cost_elements.push_back(span_violation_cost);
2355 IntVar* penalty_var = CreateDisjunction(i);
2356 if (penalty_var !=
nullptr) {
2357 cost_elements.push_back(penalty_var);
2362 dimension->SetupCumulVarSoftLowerBoundCosts(&cost_elements);
2363 dimension->SetupCumulVarSoftUpperBoundCosts(&cost_elements);
2364 dimension->SetupCumulVarPiecewiseLinearCosts(&cost_elements);
2367 for (
int i = 0; i < same_vehicle_costs_.size(); ++i) {
2368 cost_elements.push_back(CreateSameVehicleCost(i));
2370 cost_ = solver_->MakeSum(cost_elements)->Var();
2374 std::vector<std::pair<int, int>> pickup_delivery_precedences;
2375 for (
const auto& pair : pickup_delivery_pairs_) {
2376 DCHECK(!pair.first.empty() && !pair.second.empty());
2377 for (
int pickup : pair.first) {
2378 for (
int delivery : pair.second) {
2379 pickup_delivery_precedences.emplace_back(pickup, delivery);
2383 std::vector<int> lifo_vehicles;
2384 std::vector<int> fifo_vehicles;
2385 for (
int i = 0; i < vehicles_; ++i) {
2386 switch (vehicle_pickup_delivery_policy_[i]) {
2390 lifo_vehicles.push_back(
Start(i));
2393 fifo_vehicles.push_back(
Start(i));
2397 solver_->AddConstraint(solver_->MakePathPrecedenceConstraint(
2398 nexts_, pickup_delivery_precedences, lifo_vehicles, fifo_vehicles));
2401 enable_deep_serialization_ =
false;
2402 std::unique_ptr<RoutingModelInspector> inspector(
2404 solver_->Accept(inspector.get());
2405 enable_deep_serialization_ =
true;
2411 dimension->GetPathPrecedenceGraph();
2412 std::vector<std::pair<int, int>> path_precedences;
2414 for (
const auto head : graph[
tail]) {
2415 path_precedences.emplace_back(
tail,
head);
2418 if (!path_precedences.empty()) {
2419 solver_->AddConstraint(solver_->MakePathTransitPrecedenceConstraint(
2420 nexts_, dimension->transits(), path_precedences));
2425 dimension->GetNodePrecedences()) {
2426 const int64 first_node = node_precedence.first_node;
2427 const int64 second_node = node_precedence.second_node;
2428 IntExpr*
const nodes_are_selected =
2429 solver_->MakeMin(active_[first_node], active_[second_node]);
2430 IntExpr*
const cumul_difference = solver_->MakeDifference(
2431 dimension->CumulVar(second_node), dimension->CumulVar(first_node));
2432 IntVar*
const cumul_difference_is_ge_offset =
2433 solver_->MakeIsGreaterOrEqualCstVar(cumul_difference,
2434 node_precedence.offset);
2437 solver_->AddConstraint(solver_->MakeLessOrEqual(
2438 nodes_are_selected->
Var(), cumul_difference_is_ge_offset));
2442 DetectImplicitPickupAndDeliveries();
2451 CreateFirstSolutionDecisionBuilders(
parameters);
2452 error = FindErrorInSearchParametersForModel(
parameters);
2453 if (!error.empty()) {
2455 LOG(
ERROR) <<
"Invalid RoutingSearchParameters for this model: " << error;
2462 Link(std::pair<int, int> link,
double value,
int vehicle_class,
2466 vehicle_class(vehicle_class),
2467 start_depot(start_depot),
2468 end_depot(end_depot) {}
2492 bool check_assignment,
int64 num_indices,
2493 const std::vector<Link>& links_list)
2494 : assignment_(assignment),
2496 check_assignment_(check_assignment),
2497 solver_(model_->
solver()),
2498 num_indices_(num_indices),
2499 links_list_(links_list),
2500 nexts_(model_->
Nexts()),
2501 in_route_(num_indices_, -1),
2503 index_to_chain_index_(num_indices, -1),
2504 index_to_vehicle_class_index_(num_indices, -1) {
2506 const std::vector<std::string> dimension_names =
2507 model_->GetAllDimensionNames();
2508 dimensions_.assign(dimension_names.size(),
nullptr);
2509 for (
int i = 0; i < dimension_names.size(); ++i) {
2510 dimensions_[i] = &model_->GetDimensionOrDie(dimension_names[i]);
2513 cumuls_.resize(dimensions_.size());
2514 for (std::vector<int64>& cumuls :
cumuls_) {
2515 cumuls.resize(num_indices_);
2517 new_possible_cumuls_.resize(dimensions_.size());
2523 model_->solver()->TopPeriodicCheck();
2526 if (!model_->IsStart(
index) && !model_->IsEnd(
index)) {
2527 std::vector<int> route(1,
index);
2528 routes_.push_back(route);
2529 in_route_[
index] = routes_.size() - 1;
2533 for (
const Link& link : links_list_) {
2534 model_->solver()->TopPeriodicCheck();
2535 const int index1 = link.link.first;
2536 const int index2 = link.link.second;
2537 const int vehicle_class = link.vehicle_class;
2538 const int64 start_depot = link.start_depot;
2539 const int64 end_depot = link.end_depot;
2542 if (index_to_vehicle_class_index_[index1] < 0) {
2543 for (
int dimension_index = 0; dimension_index < dimensions_.size();
2544 ++dimension_index) {
2545 cumuls_[dimension_index][index1] =
2546 std::max(dimensions_[dimension_index]->GetTransitValue(
2547 start_depot, index1, 0),
2548 dimensions_[dimension_index]->CumulVar(index1)->Min());
2551 if (index_to_vehicle_class_index_[index2] < 0) {
2552 for (
int dimension_index = 0; dimension_index < dimensions_.size();
2553 ++dimension_index) {
2554 cumuls_[dimension_index][index2] =
2555 std::max(dimensions_[dimension_index]->GetTransitValue(
2556 start_depot, index2, 0),
2557 dimensions_[dimension_index]->CumulVar(index2)->Min());
2561 const int route_index1 = in_route_[index1];
2562 const int route_index2 = in_route_[index2];
2564 route_index1 >= 0 && route_index2 >= 0 &&
2565 FeasibleMerge(routes_[route_index1], routes_[route_index2], index1,
2566 index2, route_index1, route_index2, vehicle_class,
2567 start_depot, end_depot);
2568 if (Merge(merge, route_index1, route_index2)) {
2569 index_to_vehicle_class_index_[index1] = vehicle_class;
2570 index_to_vehicle_class_index_[index2] = vehicle_class;
2574 model_->solver()->TopPeriodicCheck();
2578 for (
int chain_index = 0; chain_index < chains_.size(); ++chain_index) {
2580 final_chains_.push_back(chains_[chain_index]);
2583 std::sort(final_chains_.begin(), final_chains_.end(), ChainComparator);
2584 for (
int route_index = 0; route_index < routes_.size(); ++route_index) {
2586 final_routes_.push_back(routes_[route_index]);
2589 std::sort(final_routes_.begin(), final_routes_.end(), RouteComparator);
2591 const int extra_vehicles =
std::max(
2592 0,
static_cast<int>(final_chains_.size()) - model_->vehicles());
2594 int chain_index = 0;
2595 for (chain_index = extra_vehicles; chain_index < final_chains_.size();
2597 if (chain_index - extra_vehicles >= model_->vehicles()) {
2600 const int start = final_chains_[chain_index].head;
2601 const int end = final_chains_[chain_index].tail;
2603 model_->NextVar(model_->Start(chain_index - extra_vehicles)));
2604 assignment_->SetValue(
2605 model_->NextVar(model_->Start(chain_index - extra_vehicles)), start);
2606 assignment_->Add(nexts_[end]);
2607 assignment_->SetValue(nexts_[end],
2608 model_->End(chain_index - extra_vehicles));
2612 for (
int route_index = 0; route_index < final_routes_.size();
2614 if (chain_index - extra_vehicles >= model_->vehicles()) {
2617 DCHECK_LT(route_index, final_routes_.size());
2618 const int head = final_routes_[route_index].front();
2619 const int tail = final_routes_[route_index].back();
2622 model_->NextVar(model_->Start(chain_index - extra_vehicles)));
2623 assignment_->SetValue(
2624 model_->NextVar(model_->Start(chain_index - extra_vehicles)),
head);
2625 assignment_->Add(nexts_[
tail]);
2626 assignment_->SetValue(nexts_[
tail],
2627 model_->End(chain_index - extra_vehicles));
2635 if (!assignment_->Contains(
next)) {
2636 assignment_->Add(
next);
2645 return final_routes_;
2649 enum MergeStatus { FIRST_SECOND, SECOND_FIRST, NO_MERGE };
2652 bool operator()(
const std::vector<int>& route1,
2653 const std::vector<int>& route2)
const {
2654 return (route1.size() < route2.size());
2665 bool operator()(
const Chain& chain1,
const Chain& chain2)
const {
2666 return (chain1.nodes < chain2.nodes);
2670 bool Head(
int node)
const {
2671 return (node == routes_[in_route_[node]].front());
2674 bool Tail(
int node)
const {
2675 return (node == routes_[in_route_[node]].back());
2678 bool FeasibleRoute(
const std::vector<int>& route,
int64 route_cumul,
2679 int dimension_index) {
2681 std::vector<int>::const_iterator it = route.begin();
2682 int64 cumul = route_cumul;
2683 while (it != route.end()) {
2684 const int previous = *it;
2685 const int64 cumul_previous = cumul;
2689 if (it == route.end()) {
2692 const int next = *it;
2693 int64 available_from_previous =
2694 cumul_previous + dimension.GetTransitValue(previous,
next, 0);
2695 int64 available_cumul_next =
2698 const int64 slack = available_cumul_next - available_from_previous;
2699 if (slack > dimension.SlackVar(previous)->Max()) {
2700 available_cumul_next =
2701 available_from_previous + dimension.SlackVar(previous)->Max();
2704 if (available_cumul_next > dimension.CumulVar(
next)->Max()) {
2707 if (available_cumul_next <=
cumuls_[dimension_index][
next]) {
2710 cumul = available_cumul_next;
2715 bool CheckRouteConnection(
const std::vector<int>& route1,
2716 const std::vector<int>& route2,
int dimension_index,
2718 const int tail1 = route1.back();
2719 const int head2 = route2.front();
2720 const int tail2 = route2.back();
2722 int non_depot_node = -1;
2723 for (
int node = 0; node < num_indices_; ++node) {
2724 if (!model_->IsStart(node) && !model_->IsEnd(node)) {
2725 non_depot_node = node;
2730 const int64 depot_threshold =
2731 std::max(dimension.SlackVar(non_depot_node)->Max(),
2732 dimension.CumulVar(non_depot_node)->Max());
2734 int64 available_from_tail1 =
cumuls_[dimension_index][tail1] +
2735 dimension.GetTransitValue(tail1, head2, 0);
2736 int64 new_available_cumul_head2 =
2739 const int64 slack = new_available_cumul_head2 - available_from_tail1;
2740 if (slack > dimension.SlackVar(tail1)->Max()) {
2741 new_available_cumul_head2 =
2742 available_from_tail1 + dimension.SlackVar(tail1)->Max();
2745 bool feasible_route =
true;
2746 if (new_available_cumul_head2 > dimension.CumulVar(head2)->Max()) {
2749 if (new_available_cumul_head2 <=
cumuls_[dimension_index][head2]) {
2754 FeasibleRoute(route2, new_available_cumul_head2, dimension_index);
2755 const int64 new_possible_cumul_tail2 =
2757 ? new_possible_cumuls_[dimension_index][tail2]
2758 :
cumuls_[dimension_index][tail2];
2760 if (!feasible_route || (new_possible_cumul_tail2 +
2761 dimension.GetTransitValue(tail2, end_depot, 0) >
2768 bool FeasibleMerge(
const std::vector<int>& route1,
2769 const std::vector<int>& route2,
int node1,
int node2,
2770 int route_index1,
int route_index2,
int vehicle_class,
2772 if ((route_index1 == route_index2) || !(Tail(node1) && Head(node2))) {
2777 if (!((index_to_vehicle_class_index_[node1] == -1 &&
2778 index_to_vehicle_class_index_[node2] == -1) ||
2779 (index_to_vehicle_class_index_[node1] == vehicle_class &&
2780 index_to_vehicle_class_index_[node2] == -1) ||
2781 (index_to_vehicle_class_index_[node1] == -1 &&
2782 index_to_vehicle_class_index_[node2] == vehicle_class) ||
2783 (index_to_vehicle_class_index_[node1] == vehicle_class &&
2784 index_to_vehicle_class_index_[node2] == vehicle_class))) {
2790 for (
int dimension_index = 0; dimension_index < dimensions_.size();
2791 ++dimension_index) {
2792 new_possible_cumuls_[dimension_index].clear();
2793 merge = merge && CheckRouteConnection(route1, route2, dimension_index,
2794 start_depot, end_depot);
2802 bool CheckTempAssignment(Assignment*
const temp_assignment,
2803 int new_chain_index,
int old_chain_index,
int head1,
2804 int tail1,
int head2,
int tail2) {
2807 if (new_chain_index >= model_->vehicles())
return false;
2808 const int start = head1;
2809 temp_assignment->Add(model_->NextVar(model_->Start(new_chain_index)));
2810 temp_assignment->SetValue(model_->NextVar(model_->Start(new_chain_index)),
2812 temp_assignment->Add(nexts_[tail1]);
2813 temp_assignment->SetValue(nexts_[tail1], head2);
2814 temp_assignment->Add(nexts_[tail2]);
2815 temp_assignment->SetValue(nexts_[tail2], model_->End(new_chain_index));
2816 for (
int chain_index = 0; chain_index < chains_.size(); ++chain_index) {
2817 if ((chain_index != new_chain_index) &&
2818 (chain_index != old_chain_index) &&
2820 const int start = chains_[chain_index].head;
2821 const int end = chains_[chain_index].tail;
2822 temp_assignment->Add(model_->NextVar(model_->Start(chain_index)));
2823 temp_assignment->SetValue(model_->NextVar(model_->Start(chain_index)),
2825 temp_assignment->Add(nexts_[end]);
2826 temp_assignment->SetValue(nexts_[end], model_->End(chain_index));
2829 return solver_->Solve(solver_->MakeRestoreAssignment(temp_assignment));
2832 bool UpdateAssignment(
const std::vector<int>& route1,
2833 const std::vector<int>& route2) {
2834 bool feasible =
true;
2835 const int head1 = route1.front();
2836 const int tail1 = route1.back();
2837 const int head2 = route2.front();
2838 const int tail2 = route2.back();
2839 const int chain_index1 = index_to_chain_index_[head1];
2840 const int chain_index2 = index_to_chain_index_[head2];
2841 if (chain_index1 < 0 && chain_index2 < 0) {
2842 const int chain_index = chains_.size();
2843 if (check_assignment_) {
2844 Assignment*
const temp_assignment =
2845 solver_->MakeAssignment(assignment_);
2846 feasible = CheckTempAssignment(temp_assignment, chain_index, -1, head1,
2847 tail1, head2, tail2);
2854 index_to_chain_index_[head1] = chain_index;
2855 index_to_chain_index_[tail2] = chain_index;
2856 chains_.push_back(chain);
2858 }
else if (chain_index1 >= 0 && chain_index2 < 0) {
2859 if (check_assignment_) {
2860 Assignment*
const temp_assignment =
2861 solver_->MakeAssignment(assignment_);
2863 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
2864 head1, tail1, head2, tail2);
2867 index_to_chain_index_[tail2] = chain_index1;
2868 chains_[chain_index1].head = head1;
2869 chains_[chain_index1].tail = tail2;
2870 ++chains_[chain_index1].nodes;
2872 }
else if (chain_index1 < 0 && chain_index2 >= 0) {
2873 if (check_assignment_) {
2874 Assignment*
const temp_assignment =
2875 solver_->MakeAssignment(assignment_);
2877 CheckTempAssignment(temp_assignment, chain_index2, chain_index1,
2878 head1, tail1, head2, tail2);
2881 index_to_chain_index_[head1] = chain_index2;
2882 chains_[chain_index2].head = head1;
2883 chains_[chain_index2].tail = tail2;
2884 ++chains_[chain_index2].nodes;
2887 if (check_assignment_) {
2888 Assignment*
const temp_assignment =
2889 solver_->MakeAssignment(assignment_);
2891 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
2892 head1, tail1, head2, tail2);
2895 index_to_chain_index_[tail2] = chain_index1;
2896 chains_[chain_index1].head = head1;
2897 chains_[chain_index1].tail = tail2;
2898 chains_[chain_index1].nodes += chains_[chain_index2].nodes;
2899 deleted_chains_.insert(chain_index2);
2903 assignment_->Add(nexts_[tail1]);
2904 assignment_->SetValue(nexts_[tail1], head2);
2909 bool Merge(
bool merge,
int index1,
int index2) {
2911 if (UpdateAssignment(routes_[index1], routes_[index2])) {
2913 for (
const int node : routes_[index2]) {
2914 in_route_[node] = index1;
2915 routes_[index1].push_back(node);
2917 for (
int dimension_index = 0; dimension_index < dimensions_.size();
2918 ++dimension_index) {
2919 for (
const std::pair<int, int64> new_possible_cumul :
2920 new_possible_cumuls_[dimension_index]) {
2921 cumuls_[dimension_index][new_possible_cumul.first] =
2922 new_possible_cumul.second;
2925 deleted_routes_.insert(index2);
2932 Assignment*
const assignment_;
2934 const bool check_assignment_;
2935 Solver*
const solver_;
2936 const int64 num_indices_;
2937 const std::vector<Link> links_list_;
2938 std::vector<IntVar*> nexts_;
2939 std::vector<const RoutingDimension*> dimensions_;
2940 std::vector<std::vector<int64>>
cumuls_;
2941 std::vector<absl::flat_hash_map<int, int64>> new_possible_cumuls_;
2942 std::vector<std::vector<int>> routes_;
2943 std::vector<int> in_route_;
2944 absl::flat_hash_set<int> deleted_routes_;
2945 std::vector<std::vector<int>> final_routes_;
2946 std::vector<Chain> chains_;
2947 absl::flat_hash_set<int> deleted_chains_;
2948 std::vector<Chain> final_chains_;
2949 std::vector<int> index_to_chain_index_;
2950 std::vector<int> index_to_vehicle_class_index_;
2956 :
index(
index), angle(angle), distance(distance) {}
2977 : coordinates_(2 * points.size(), 0), sectors_(1) {
2978 for (
int64 i = 0; i < points.size(); ++i) {
2979 coordinates_[2 * i] = points[i].first;
2980 coordinates_[2 * i + 1] = points[i].second;
2987 const double pi_rad = 3.14159265;
2989 const int x0 = coordinates_[0];
2990 const int y0 = coordinates_[1];
2992 std::vector<SweepIndex> sweep_indices;
2993 for (
int64 index = 0; index < static_cast<int>(coordinates_.size()) / 2;
2995 const int x = coordinates_[2 *
index];
2996 const int y = coordinates_[2 *
index + 1];
2997 const double x_delta = x - x0;
2998 const double y_delta = y - y0;
2999 double square_distance = x_delta * x_delta + y_delta * y_delta;
3000 double angle = square_distance == 0 ? 0 : std::atan2(y_delta, x_delta);
3001 angle = angle >= 0 ? angle : 2 * pi_rad + angle;
3003 sweep_indices.push_back(sweep_index);
3005 std::sort(sweep_indices.begin(), sweep_indices.end(),
3008 const int size =
static_cast<int>(sweep_indices.size()) / sectors_;
3009 for (
int sector = 0; sector < sectors_; ++sector) {
3010 std::vector<SweepIndex> cluster;
3011 std::vector<SweepIndex>::iterator begin =
3012 sweep_indices.begin() + sector * size;
3013 std::vector<SweepIndex>::iterator end =
3014 sector == sectors_ - 1 ? sweep_indices.end()
3015 : sweep_indices.begin() + (sector + 1) * size;
3018 for (
const SweepIndex& sweep_index : sweep_indices) {
3019 indices->push_back(sweep_index.index);
3029 : model_(
model), check_assignment_(check_assignment) {}
3038 route_constructor_ = absl::make_unique<RouteConstructor>(
3039 assignment, model_, check_assignment_, num_indices_, links_);
3041 route_constructor_->Construct();
3042 route_constructor_.reset(
nullptr);
3051 const int depot = model_->
GetDepot();
3053 if (absl::GetFlag(FLAGS_sweep_sectors) > 0 &&
3054 absl::GetFlag(FLAGS_sweep_sectors) < num_indices_) {
3057 std::vector<int64> indices;
3059 for (
int i = 0; i < indices.size() - 1; ++i) {
3060 const int64 first = indices[i];
3061 const int64 second = indices[i + 1];
3062 if ((model_->
IsStart(first) || !model_->
IsEnd(first)) &&
3064 if (first != depot && second != depot) {
3065 Link link(std::make_pair(first, second), 0, 0, depot, depot);
3066 links_.push_back(link);
3072 RoutingModel*
const model_;
3073 std::unique_ptr<RouteConstructor> route_constructor_;
3074 const bool check_assignment_;
3076 std::vector<Link> links_;
3084 class AllUnperformed :
public DecisionBuilder {
3087 explicit AllUnperformed(RoutingModel*
const model) : model_(
model) {}
3088 ~AllUnperformed()
override {}
3089 Decision* Next(Solver*
const solver)
override {
3092 model_->CostVar()->FreezeQueue();
3093 for (
int i = 0; i < model_->Size(); ++i) {
3094 if (!model_->IsStart(i)) {
3095 model_->ActiveVar(i)->SetValue(0);
3098 model_->CostVar()->UnfreezeQueue();
3103 RoutingModel*
const model_;
3108 monitors_.push_back(monitor);
3114 AtSolutionCallbackMonitor(
Solver* solver, std::function<
void()>
callback)
3116 bool AtSolution()
override {
3122 std::function<void()> callback_;
3128 new AtSolutionCallbackMonitor(solver_.get(), std::move(
callback))));
3138 std::vector<const Assignment*>* solutions) {
3143 absl::Duration GetTimeLimit(
const RoutingSearchParameters&
parameters) {
3144 if (!
parameters.has_time_limit())
return absl::InfiniteDuration();
3148 absl::Duration GetLnsTimeLimit(
const RoutingSearchParameters&
parameters) {
3149 if (!
parameters.has_lns_time_limit())
return absl::InfiniteDuration();
3156 void MakeAllUnperformed(
const RoutingModel*
model, Assignment* assignment) {
3157 assignment->Clear();
3158 for (
int i = 0; i <
model->Nexts().size(); ++i) {
3159 if (!
model->IsStart(i)) {
3160 assignment->Add(
model->NextVar(i))->SetValue(i);
3163 for (
int vehicle = 0; vehicle <
model->vehicles(); ++vehicle) {
3164 assignment->Add(
model->NextVar(
model->Start(vehicle)))
3165 ->SetValue(
model->End(vehicle));
3170 bool RoutingModel::AppendAssignmentIfFeasible(
3171 const Assignment& assignment,
3172 std::vector<std::unique_ptr<Assignment>>* assignments) {
3174 solver_->Solve(restore_tmp_assignment_, collect_one_assignment_,
3175 GetOrCreateLimit());
3177 assignments->push_back(absl::make_unique<Assignment>(solver_.get()));
3178 assignments->back()->Copy(collect_one_assignment_->
solution(0));
3184 void RoutingModel::LogSolution(
const RoutingSearchParameters&
parameters,
3185 const std::string& description,
3188 const double cost_scaling_factor =
parameters.log_cost_scaling_factor();
3189 const double cost_offset =
parameters.log_cost_offset();
3190 const std::string cost_string =
3191 cost_scaling_factor == 1.0 && cost_offset == 0.0
3192 ? absl::StrCat(solution_cost)
3194 "%d (%.8lf)", solution_cost,
3195 cost_scaling_factor * (solution_cost + cost_offset));
3197 "%s (%s, time = %d ms, memory used = %s)", description, cost_string,
3198 solver_->wall_time() - start_time_ms, memory_str);
3203 std::vector<const Assignment*>* solutions) {
3204 const int64 start_time_ms = solver_->wall_time();
3207 if (solutions !=
nullptr) solutions->clear();
3221 const int time_limit_shares = 1 + !global_dimension_optimizers_.empty() +
3222 !local_dimension_optimizers_.empty();
3223 const absl::Duration first_solution_lns_time_limit =
3226 first_solution_lns_limit_->
UpdateLimits(first_solution_lns_time_limit,
3229 std::vector<std::unique_ptr<Assignment>> solution_pool;
3231 if (
nullptr == assignment) {
3232 bool solution_found =
false;
3235 AppendAssignmentIfFeasible(matching, &solution_pool)) {
3237 LogSolution(
parameters,
"Min-Cost Flow Solution",
3238 solution_pool.back()->ObjectiveValue(), start_time_ms);
3240 solution_found =
true;
3242 if (!solution_found) {
3246 MakeAllUnperformed(
this, &unperformed);
3247 if (AppendAssignmentIfFeasible(unperformed, &solution_pool) &&
3249 LogSolution(
parameters,
"All Unperformed Solution",
3250 solution_pool.back()->ObjectiveValue(), start_time_ms);
3252 const absl::Duration elapsed_time =
3253 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3254 const absl::Duration time_left =
3256 if (time_left >= absl::ZeroDuration()) {
3260 solver_->Solve(solve_db_, monitors_);
3265 solver_->Solve(improve_db_, monitors_);
3270 const int solution_count = collect_assignments_->
solution_count();
3272 solution_count >= 1 ? collect_assignments_->
solution(solution_count - 1)
3276 AppendAssignmentIfFeasible(sat_solution, &solution_pool) &&
3278 LogSolution(
parameters,
"SAT", solution_pool.back()->ObjectiveValue(),
3283 const absl::Duration elapsed_time =
3284 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3285 const int solution_count = collect_assignments_->
solution_count();
3286 if (solution_count >= 1 || !solution_pool.empty()) {
3288 if (solutions !=
nullptr) {
3289 for (
int i = 0; i < solution_count; ++i) {
3290 solutions->push_back(
3291 solver_->MakeAssignment(collect_assignments_->
solution(i)));
3293 for (
const auto& solution : solution_pool) {
3294 if (solutions->empty() ||
3295 solution->ObjectiveValue() < solutions->back()->ObjectiveValue()) {
3296 solutions->push_back(solver_->MakeAssignment(solution.get()));
3299 return solutions->back();
3302 solution_count >= 1 ? collect_assignments_->
solution(solution_count - 1)
3304 for (
const auto& solution : solution_pool) {
3305 if (best_assignment ==
nullptr ||
3307 best_assignment = solution.get();
3310 return solver_->MakeAssignment(best_assignment);
3312 if (elapsed_time >= GetTimeLimit(
parameters)) {
3324 const int size =
Size();
3330 source_model->
Nexts());
3332 std::vector<IntVar*> source_vars(size + size + vehicles_);
3333 std::vector<IntVar*> target_vars(size + size + vehicles_);
3343 source_assignment, source_vars);
3361 LOG(
WARNING) <<
"Non-closed model not supported.";
3365 LOG(
WARNING) <<
"Non-homogeneous vehicle costs not supported";
3368 if (!disjunctions_.
empty()) {
3370 <<
"Node disjunction constraints or optional nodes not supported.";
3373 const int num_nodes =
Size() + vehicles_;
3380 std::unique_ptr<IntVarIterator> iterator(
3381 nexts_[
tail]->MakeDomainIterator(
false));
3404 return linear_sum_assignment.
GetCost();
3409 bool RoutingModel::RouteCanBeUsedByVehicle(
const Assignment& assignment,
3410 int start_index,
int vehicle)
const {
3412 IsStart(start_index) ?
Next(assignment, start_index) : start_index;
3413 while (!
IsEnd(current_index)) {
3415 if (!vehicle_var->
Contains(vehicle)) {
3418 const int next_index =
Next(assignment, current_index);
3419 CHECK_NE(next_index, current_index) <<
"Inactive node inside a route";
3420 current_index = next_index;
3425 bool RoutingModel::ReplaceUnusedVehicle(
3426 int unused_vehicle,
int active_vehicle,
3427 Assignment*
const compact_assignment)
const {
3428 CHECK(compact_assignment !=
nullptr);
3432 const int unused_vehicle_start =
Start(unused_vehicle);
3433 IntVar*
const unused_vehicle_start_var =
NextVar(unused_vehicle_start);
3434 const int unused_vehicle_end =
End(unused_vehicle);
3435 const int active_vehicle_start =
Start(active_vehicle);
3436 const int active_vehicle_end =
End(active_vehicle);
3437 IntVar*
const active_vehicle_start_var =
NextVar(active_vehicle_start);
3438 const int active_vehicle_next =
3439 compact_assignment->Value(active_vehicle_start_var);
3440 compact_assignment->SetValue(unused_vehicle_start_var, active_vehicle_next);
3441 compact_assignment->SetValue(active_vehicle_start_var,
End(active_vehicle));
3444 int current_index = active_vehicle_next;
3445 while (!
IsEnd(current_index)) {
3446 IntVar*
const vehicle_var =
VehicleVar(current_index);
3447 compact_assignment->SetValue(vehicle_var, unused_vehicle);
3448 const int next_index =
Next(*compact_assignment, current_index);
3449 if (
IsEnd(next_index)) {
3450 IntVar*
const last_next_var =
NextVar(current_index);
3451 compact_assignment->SetValue(last_next_var,
End(unused_vehicle));
3453 current_index = next_index;
3458 const std::vector<IntVar*>& transit_variables = dimension->transits();
3459 IntVar*
const unused_vehicle_transit_var =
3460 transit_variables[unused_vehicle_start];
3461 IntVar*
const active_vehicle_transit_var =
3462 transit_variables[active_vehicle_start];
3463 const bool contains_unused_vehicle_transit_var =
3464 compact_assignment->Contains(unused_vehicle_transit_var);
3465 const bool contains_active_vehicle_transit_var =
3466 compact_assignment->Contains(active_vehicle_transit_var);
3467 if (contains_unused_vehicle_transit_var !=
3468 contains_active_vehicle_transit_var) {
3470 LOG(
INFO) <<
"The assignment contains transit variable for dimension '"
3471 << dimension->name() <<
"' for some vehicles, but not for all";
3474 if (contains_unused_vehicle_transit_var) {
3475 const int64 old_unused_vehicle_transit =
3476 compact_assignment->Value(unused_vehicle_transit_var);
3477 const int64 old_active_vehicle_transit =
3478 compact_assignment->Value(active_vehicle_transit_var);
3479 compact_assignment->SetValue(unused_vehicle_transit_var,
3480 old_active_vehicle_transit);
3481 compact_assignment->SetValue(active_vehicle_transit_var,
3482 old_unused_vehicle_transit);
3486 const std::vector<IntVar*>& cumul_variables = dimension->cumuls();
3487 IntVar*
const unused_vehicle_cumul_var =
3488 cumul_variables[unused_vehicle_end];
3489 IntVar*
const active_vehicle_cumul_var =
3490 cumul_variables[active_vehicle_end];
3491 const int64 old_unused_vehicle_cumul =
3492 compact_assignment->Value(unused_vehicle_cumul_var);
3493 const int64 old_active_vehicle_cumul =
3494 compact_assignment->Value(active_vehicle_cumul_var);
3495 compact_assignment->SetValue(unused_vehicle_cumul_var,
3496 old_active_vehicle_cumul);
3497 compact_assignment->SetValue(active_vehicle_cumul_var,
3498 old_unused_vehicle_cumul);
3505 return CompactAssignmentInternal(assignment,
false);
3510 return CompactAssignmentInternal(assignment,
true);
3513 Assignment* RoutingModel::CompactAssignmentInternal(
3514 const Assignment& assignment,
bool check_compact_assignment)
const {
3518 <<
"The costs are not homogeneous, routes cannot be rearranged";
3522 std::unique_ptr<Assignment> compact_assignment(
new Assignment(&assignment));
3523 for (
int vehicle = 0; vehicle < vehicles_ - 1; ++vehicle) {
3527 const int vehicle_start =
Start(vehicle);
3528 const int vehicle_end =
End(vehicle);
3530 int swap_vehicle = vehicles_ - 1;
3531 bool has_more_vehicles_with_route =
false;
3532 for (; swap_vehicle > vehicle; --swap_vehicle) {
3539 has_more_vehicles_with_route =
true;
3540 const int swap_vehicle_start =
Start(swap_vehicle);
3541 const int swap_vehicle_end =
End(swap_vehicle);
3550 if (RouteCanBeUsedByVehicle(*compact_assignment, swap_vehicle_start,
3556 if (swap_vehicle == vehicle) {
3557 if (has_more_vehicles_with_route) {
3561 LOG(
INFO) <<
"No vehicle that can be swapped with " << vehicle
3568 if (!ReplaceUnusedVehicle(vehicle, swap_vehicle,
3569 compact_assignment.get())) {
3574 if (check_compact_assignment &&
3575 !solver_->CheckAssignment(compact_assignment.get())) {
3577 LOG(
WARNING) <<
"The compacted assignment is not a valid solution";
3580 return compact_assignment.release();
3583 int RoutingModel::FindNextActive(
int index,
3584 const std::vector<int64>& indices)
const {
3587 const int size = indices.size();
3598 preassignment_->
Clear();
3599 IntVar* next_var =
nullptr;
3600 int lock_index = FindNextActive(-1, locks);
3601 const int size = locks.size();
3602 if (lock_index < size) {
3603 next_var =
NextVar(locks[lock_index]);
3604 preassignment_->
Add(next_var);
3605 for (lock_index = FindNextActive(lock_index, locks); lock_index < size;
3606 lock_index = FindNextActive(lock_index, locks)) {
3607 preassignment_->
SetValue(next_var, locks[lock_index]);
3608 next_var =
NextVar(locks[lock_index]);
3609 preassignment_->
Add(next_var);
3616 const std::vector<std::vector<int64>>& locks,
bool close_routes) {
3617 preassignment_->
Clear();
3622 const RoutingSearchParameters&
parameters)
const {
3624 GetFilteredFirstSolutionDecisionBuilderOrNull(
parameters);
3630 const RoutingSearchParameters&
parameters)
const {
3632 GetFilteredFirstSolutionDecisionBuilderOrNull(
parameters);
3638 if (collect_assignments_->
solution_count() == 1 && assignment_ !=
nullptr) {
3640 return assignment_->
Save(file_name);
3648 CHECK(assignment_ !=
nullptr);
3649 if (assignment_->
Load(file_name)) {
3650 return DoRestoreAssignment();
3657 CHECK(assignment_ !=
nullptr);
3659 return DoRestoreAssignment();
3662 Assignment* RoutingModel::DoRestoreAssignment() {
3666 solver_->Solve(restore_assignment_, monitors_);
3669 return collect_assignments_->
solution(0);
3678 const std::vector<std::vector<int64>>& routes,
bool ignore_inactive_indices,
3679 bool close_routes,
Assignment*
const assignment)
const {
3680 CHECK(assignment !=
nullptr);
3682 LOG(
ERROR) <<
"The model is not closed yet";
3685 const int num_routes = routes.size();
3686 if (num_routes > vehicles_) {
3687 LOG(
ERROR) <<
"The number of vehicles in the assignment (" << routes.size()
3688 <<
") is greater than the number of vehicles in the model ("
3689 << vehicles_ <<
")";
3693 absl::flat_hash_set<int> visited_indices;
3695 for (
int vehicle = 0; vehicle < num_routes; ++vehicle) {
3696 const std::vector<int64>& route = routes[vehicle];
3697 int from_index =
Start(vehicle);
3698 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
3699 visited_indices.insert(from_index);
3700 if (!insert_result.second) {
3701 LOG(
ERROR) <<
"Index " << from_index <<
" (start node for vehicle "
3702 << vehicle <<
") was already used";
3706 for (
const int64 to_index : route) {
3707 if (to_index < 0 || to_index >=
Size()) {
3708 LOG(
ERROR) <<
"Invalid index: " << to_index;
3713 if (active_var->
Max() == 0) {
3714 if (ignore_inactive_indices) {
3717 LOG(
ERROR) <<
"Index " << to_index <<
" is not active";
3722 insert_result = visited_indices.insert(to_index);
3723 if (!insert_result.second) {
3724 LOG(
ERROR) <<
"Index " << to_index <<
" is used multiple times";
3729 if (!vehicle_var->
Contains(vehicle)) {
3730 LOG(
ERROR) <<
"Vehicle " << vehicle <<
" is not allowed at index "
3736 if (!assignment->
Contains(from_var)) {
3737 assignment->
Add(from_var);
3739 assignment->
SetValue(from_var, to_index);
3741 from_index = to_index;
3746 if (!assignment->
Contains(last_var)) {
3747 assignment->
Add(last_var);
3754 for (
int vehicle = num_routes; vehicle < vehicles_; ++vehicle) {
3755 const int start_index =
Start(vehicle);
3758 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
3759 visited_indices.insert(start_index);
3760 if (!insert_result.second) {
3761 LOG(
ERROR) <<
"Index " << start_index <<
" is used multiple times";
3766 if (!assignment->
Contains(start_var)) {
3767 assignment->
Add(start_var);
3778 if (!assignment->
Contains(next_var)) {
3779 assignment->
Add(next_var);
3790 const std::vector<std::vector<int64>>& routes,
3791 bool ignore_inactive_indices) {
3799 return DoRestoreAssignment();
3804 std::vector<std::vector<int64>>*
const routes)
const {
3806 CHECK(routes !=
nullptr);
3808 const int model_size =
Size();
3809 routes->resize(vehicles_);
3810 for (
int vehicle = 0; vehicle < vehicles_; ++vehicle) {
3811 std::vector<int64>*
const vehicle_route = &routes->at(vehicle);
3812 vehicle_route->clear();
3814 int num_visited_indices = 0;
3815 const int first_index =
Start(vehicle);
3819 int current_index = assignment.
Value(first_var);
3820 while (!
IsEnd(current_index)) {
3821 vehicle_route->push_back(current_index);
3826 current_index = assignment.
Value(next_var);
3828 ++num_visited_indices;
3829 CHECK_LE(num_visited_indices, model_size)
3830 <<
"The assignment contains a cycle";
3838 std::vector<std::vector<int64>> route_indices(
vehicles());
3839 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
3841 LOG(DFATAL) <<
"GetRoutesFromAssignment() called on incomplete solution:"
3842 <<
" NextVar(" << vehicle <<
") is unbound.";
3845 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
3847 route_indices[vehicle].push_back(
index);
3850 route_indices[vehicle].push_back(
index);
3853 return route_indices;
3857 int64 RoutingModel::GetArcCostForClassInternal(
3858 int64 from_index,
int64 to_index, CostClassIndex cost_class_index)
const {
3861 DCHECK_LT(cost_class_index, cost_classes_.size());
3862 CostCacheElement*
const cache = &cost_cache_[from_index];
3864 if (cache->index ==
static_cast<int>(to_index) &&
3865 cache->cost_class_index == cost_class_index) {
3869 const CostClass& cost_class = cost_classes_[cost_class_index];
3870 const auto& evaluator = transit_evaluators_[cost_class.evaluator_index];
3872 cost =
CapAdd(evaluator(from_index, to_index),
3873 GetDimensionTransitCostSum(from_index, to_index, cost_class));
3874 }
else if (!
IsEnd(to_index)) {
3878 evaluator(from_index, to_index),
3879 CapAdd(GetDimensionTransitCostSum(from_index, to_index, cost_class),
3880 fixed_cost_of_vehicle_[index_to_vehicle_[from_index]]));
3884 if (consider_empty_route_costs_[index_to_vehicle_[from_index]]) {
3886 CapAdd(evaluator(from_index, to_index),
3887 GetDimensionTransitCostSum(from_index, to_index, cost_class));
3892 *cache = {
static_cast<int>(to_index), cost_class_index,
cost};
3901 int vehicle)
const {
3915 return assignment.
Value(next_var);
3919 int64 vehicle)
const {
3920 if (from_index != to_index && vehicle >= 0) {
3921 return GetArcCostForClassInternal(from_index, to_index,
3930 int64 cost_class_index)
const {
3931 if (from_index != to_index) {
3932 return GetArcCostForClassInternal(from_index, to_index,
3940 int64 to_index)
const {
3944 if (!is_bound_to_end_ct_added_.
Switched()) {
3947 std::vector<IntVar*> zero_transit(
Size(), solver_->MakeIntConst(0));
3948 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
3949 nexts_, active_, is_bound_to_end_, zero_transit));
3950 is_bound_to_end_ct_added_.
Switch(solver_.get());
3952 if (is_bound_to_end_[to_index]->Min() == 1)
return kint64max;
3957 int64 RoutingModel::GetDimensionTransitCostSum(
3958 int64 i,
int64 j,
const CostClass& cost_class)
const {
3960 for (
const auto& evaluator_and_coefficient :
3961 cost_class.dimension_transit_evaluator_class_and_cost_coefficient) {
3962 DCHECK_GT(evaluator_and_coefficient.cost_coefficient, 0);
3965 CapProd(evaluator_and_coefficient.cost_coefficient,
3966 evaluator_and_coefficient.dimension->GetTransitValueFromClass(
3967 i, j, evaluator_and_coefficient.transit_evaluator_class)));
3983 const bool mandatory1 = active_[to1]->Min() == 1;
3984 const bool mandatory2 = active_[to2]->Min() == 1;
3986 if (mandatory1 != mandatory2)
return mandatory1;
3993 const int64 src_vehicle = src_vehicle_var->
Max();
3994 if (src_vehicle_var->
Bound()) {
4001 mandatory1 ? to1_vehicle_var->
Bound() : (to1_vehicle_var->
Size() <= 2);
4003 mandatory2 ? to2_vehicle_var->
Bound() : (to2_vehicle_var->
Size() <= 2);
4006 if (bound1 != bound2)
return bound1;
4009 const int64 vehicle1 = to1_vehicle_var->
Max();
4010 const int64 vehicle2 = to2_vehicle_var->
Max();
4013 if ((vehicle1 == src_vehicle) != (vehicle2 == src_vehicle)) {
4014 return vehicle1 == src_vehicle;
4019 if (vehicle1 != src_vehicle)
return to1 < to2;
4030 const std::vector<IntVar*>& cumul_vars =
4032 IntVar*
const dim1 = cumul_vars[to1];
4033 IntVar*
const dim2 = cumul_vars[to2];
4036 if (dim1->
Max() != dim2->
Max())
return dim1->
Max() < dim2->
Max();
4045 const int64 cost_class_index =
4046 SafeGetCostClassInt64OfVehicle(src_vehicle);
4051 if (cost1 != cost2)
return cost1 < cost2;
4058 if (num_vehicles1 != num_vehicles2)
return num_vehicles1 < num_vehicles2;
4067 DCHECK_EQ(index_to_visit_type_.size(), index_to_type_policy_.size());
4068 index_to_visit_type_[
index] = type;
4069 index_to_type_policy_[
index] = policy;
4070 num_visit_types_ =
std::max(num_visit_types_, type + 1);
4075 return index_to_visit_type_[
index];
4079 DCHECK_LT(type, single_nodes_of_type_.size());
4080 return single_nodes_of_type_[type];
4084 DCHECK_LT(type, pair_indices_of_type_.size());
4085 return pair_indices_of_type_[type];
4091 return index_to_type_policy_[
index];
4095 hard_incompatible_types_per_type_index_.resize(num_visit_types_);
4096 temporal_incompatible_types_per_type_index_.resize(num_visit_types_);
4097 same_vehicle_required_type_alternatives_per_type_index_.resize(
4099 required_type_alternatives_when_adding_type_index_.resize(num_visit_types_);
4100 required_type_alternatives_when_removing_type_index_.resize(num_visit_types_);
4105 hard_incompatible_types_per_type_index_.size());
4106 has_hard_type_incompatibilities_ =
true;
4108 hard_incompatible_types_per_type_index_[type1].insert(type2);
4109 hard_incompatible_types_per_type_index_[type2].insert(type1);
4114 temporal_incompatible_types_per_type_index_.size());
4115 has_temporal_type_incompatibilities_ =
true;
4117 temporal_incompatible_types_per_type_index_[type1].insert(type2);
4118 temporal_incompatible_types_per_type_index_[type2].insert(type1);
4121 const absl::flat_hash_set<int>&
4124 DCHECK_LT(type, hard_incompatible_types_per_type_index_.size());
4125 return hard_incompatible_types_per_type_index_[type];
4128 const absl::flat_hash_set<int>&
4131 DCHECK_LT(type, temporal_incompatible_types_per_type_index_.size());
4132 return temporal_incompatible_types_per_type_index_[type];
4138 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4140 same_vehicle_required_type_alternatives_per_type_index_.size());
4142 if (required_type_alternatives.empty()) {
4146 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4147 trivially_infeasible_visit_types_to_policies_[dependent_type];
4154 has_same_vehicle_type_requirements_ =
true;
4155 same_vehicle_required_type_alternatives_per_type_index_[dependent_type]
4156 .push_back(std::move(required_type_alternatives));
4160 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4162 required_type_alternatives_when_adding_type_index_.size());
4164 if (required_type_alternatives.empty()) {
4168 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4169 trivially_infeasible_visit_types_to_policies_[dependent_type];
4175 has_temporal_type_requirements_ =
true;
4176 required_type_alternatives_when_adding_type_index_[dependent_type].push_back(
4177 std::move(required_type_alternatives));
4181 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4183 required_type_alternatives_when_removing_type_index_.size());
4185 if (required_type_alternatives.empty()) {
4189 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4190 trivially_infeasible_visit_types_to_policies_[dependent_type];
4197 has_temporal_type_requirements_ =
true;
4198 required_type_alternatives_when_removing_type_index_[dependent_type]
4199 .push_back(std::move(required_type_alternatives));
4202 const std::vector<absl::flat_hash_set<int>>&
4206 same_vehicle_required_type_alternatives_per_type_index_.size());
4207 return same_vehicle_required_type_alternatives_per_type_index_[type];
4210 const std::vector<absl::flat_hash_set<int>>&
4213 DCHECK_LT(type, required_type_alternatives_when_adding_type_index_.size());
4214 return required_type_alternatives_when_adding_type_index_[type];
4217 const std::vector<absl::flat_hash_set<int>>&
4220 DCHECK_LT(type, required_type_alternatives_when_removing_type_index_.size());
4221 return required_type_alternatives_when_removing_type_index_[type];
4229 int64 var_index)
const {
4230 if (active_[var_index]->Min() == 1)
return kint64max;
4231 const std::vector<DisjunctionIndex>& disjunction_indices =
4233 if (disjunction_indices.size() != 1)
return default_value;
4238 return std::max(
int64{0}, disjunctions_[disjunction_index].value.penalty);
4243 const std::string& dimension_to_print)
const {
4244 for (
int i = 0; i <
Size(); ++i) {
4247 <<
"DebugOutputVehicleSchedules() called on incomplete solution:"
4248 <<
" NextVar(" << i <<
") is unbound.";
4253 absl::flat_hash_set<std::string> dimension_names;
4254 if (dimension_to_print.empty()) {
4256 dimension_names.insert(all_dimension_names.begin(),
4257 all_dimension_names.end());
4259 dimension_names.insert(dimension_to_print);
4261 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4262 int empty_vehicle_range_start = vehicle;
4267 if (empty_vehicle_range_start != vehicle) {
4268 if (empty_vehicle_range_start == vehicle - 1) {
4269 absl::StrAppendFormat(&output,
"Vehicle %d: empty",
4270 empty_vehicle_range_start);
4272 absl::StrAppendFormat(&output,
"Vehicles %d-%d: empty",
4273 empty_vehicle_range_start, vehicle - 1);
4275 output.append(
"\n");
4278 absl::StrAppendFormat(&output,
"Vehicle %d:", vehicle);
4282 absl::StrAppendFormat(&output,
"%d Vehicle(%d) ",
index,
4283 solution_assignment.
Value(vehicle_var));
4287 absl::StrAppendFormat(&output,
"%s(%d..%d) ", dimension->name(),
4288 solution_assignment.
Min(
var),
4289 solution_assignment.
Max(
var));
4294 if (
IsEnd(
index)) output.append(
"Route end ");
4296 output.append(
"\n");
4299 output.append(
"Unperformed nodes: ");
4300 bool has_unperformed =
false;
4301 for (
int i = 0; i <
Size(); ++i) {
4304 absl::StrAppendFormat(&output,
"%d ", i);
4305 has_unperformed =
true;
4308 if (!has_unperformed) output.append(
"None");
4309 output.append(
"\n");
4316 std::vector<std::vector<std::pair<int64, int64>>> cumul_bounds(
vehicles());
4317 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4319 LOG(DFATAL) <<
"GetCumulBounds() called on incomplete solution:"
4320 <<
" NextVar(" << vehicle <<
") is unbound.";
4324 for (
int vehicle_id = 0; vehicle_id <
vehicles(); ++vehicle_id) {
4327 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4328 solution_assignment.
Max(dim_var));
4332 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4333 solution_assignment.
Max(dim_var));
4336 return cumul_bounds;
4340 Assignment* RoutingModel::GetOrCreateAssignment() {
4341 if (assignment_ ==
nullptr) {
4342 assignment_ = solver_->MakeAssignment();
4343 assignment_->
Add(nexts_);
4345 assignment_->
Add(vehicle_vars_);
4352 Assignment* RoutingModel::GetOrCreateTmpAssignment() {
4353 if (tmp_assignment_ ==
nullptr) {
4354 tmp_assignment_ = solver_->MakeAssignment();
4355 tmp_assignment_->
Add(nexts_);
4357 return tmp_assignment_;
4360 RegularLimit* RoutingModel::GetOrCreateLimit() {
4361 if (limit_ ==
nullptr) {
4368 RegularLimit* RoutingModel::GetOrCreateLocalSearchLimit() {
4369 if (ls_limit_ ==
nullptr) {
4377 RegularLimit* RoutingModel::GetOrCreateLargeNeighborhoodSearchLimit() {
4378 if (lns_limit_ ==
nullptr) {
4387 RoutingModel::GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit() {
4388 if (first_solution_lns_limit_ ==
nullptr) {
4389 first_solution_lns_limit_ =
4393 return first_solution_lns_limit_;
4396 LocalSearchOperator* RoutingModel::CreateInsertionOperator() {
4397 LocalSearchOperator* insertion_operator =
4398 CreateCPOperator<MakeActiveOperator>();
4399 if (!pickup_delivery_pairs_.empty()) {
4400 insertion_operator = solver_->ConcatenateOperators(
4401 {CreatePairOperator<MakePairActiveOperator>(), insertion_operator});
4403 if (!implicit_pickup_delivery_pairs_without_alternatives_.empty()) {
4404 insertion_operator = solver_->ConcatenateOperators(
4405 {CreateOperator<MakePairActiveOperator>(
4406 implicit_pickup_delivery_pairs_without_alternatives_),
4407 insertion_operator});
4409 return insertion_operator;
4412 LocalSearchOperator* RoutingModel::CreateMakeInactiveOperator() {
4413 LocalSearchOperator* make_inactive_operator =
4414 CreateCPOperator<MakeInactiveOperator>();
4415 if (!pickup_delivery_pairs_.empty()) {
4416 make_inactive_operator = solver_->ConcatenateOperators(
4417 {CreatePairOperator<MakePairInactiveOperator>(),
4418 make_inactive_operator});
4420 return make_inactive_operator;
4423 void RoutingModel::CreateNeighborhoodOperators(
4425 local_search_operators_.clear();
4426 local_search_operators_.resize(LOCAL_SEARCH_OPERATOR_COUNTER,
nullptr);
4430 std::pair<RoutingLocalSearchOperator, Solver::LocalSearchOperators>>
4435 for (
const auto [type, op] : operator_by_type) {
4436 local_search_operators_[type] =
4438 ? solver_->MakeOperator(nexts_, op)
4439 : solver_->MakeOperator(nexts_, vehicle_vars_, op);
4444 const std::vector<std::pair<RoutingLocalSearchOperator,
4446 operator_by_type = {{LIN_KERNIGHAN,
Solver::LK},
4449 for (
const auto [type, op] : operator_by_type) {
4452 local_search_operators_[type] =
4454 ? solver_->MakeOperator(nexts_, std::move(arc_cost), op)
4455 : solver_->MakeOperator(nexts_, vehicle_vars_,
4456 std::move(arc_cost), op);
4461 local_search_operators_[RELOCATE] = CreateCPOperator<Relocate>();
4462 local_search_operators_[EXCHANGE] = CreateCPOperator<Exchange>();
4463 local_search_operators_[CROSS] = CreateCPOperator<Cross>();
4464 local_search_operators_[TWO_OPT] = CreateCPOperator<TwoOpt>();
4465 local_search_operators_[RELOCATE_AND_MAKE_ACTIVE] =
4466 CreateCPOperator<RelocateAndMakeActiveOperator>();
4467 local_search_operators_[MAKE_ACTIVE_AND_RELOCATE] =
4468 CreateCPOperator<MakeActiveAndRelocate>();
4469 local_search_operators_[MAKE_CHAIN_INACTIVE] =
4470 CreateCPOperator<MakeChainInactiveOperator>();
4471 local_search_operators_[SWAP_ACTIVE] = CreateCPOperator<SwapActiveOperator>();
4472 local_search_operators_[EXTENDED_SWAP_ACTIVE] =
4473 CreateCPOperator<ExtendedSwapActiveOperator>();
4476 local_search_operators_[MAKE_ACTIVE] = CreateInsertionOperator();
4477 local_search_operators_[MAKE_INACTIVE] = CreateMakeInactiveOperator();
4478 local_search_operators_[RELOCATE_PAIR] =
4479 CreatePairOperator<PairRelocateOperator>();
4480 std::vector<LocalSearchOperator*> light_relocate_pair_operators;
4481 light_relocate_pair_operators.push_back(
4482 CreatePairOperator<LightPairRelocateOperator>());
4483 local_search_operators_[LIGHT_RELOCATE_PAIR] =
4484 solver_->ConcatenateOperators(light_relocate_pair_operators);
4485 local_search_operators_[EXCHANGE_PAIR] =
4486 CreatePairOperator<PairExchangeOperator>();
4487 local_search_operators_[EXCHANGE_RELOCATE_PAIR] =
4488 CreatePairOperator<PairExchangeRelocateOperator>();
4489 local_search_operators_[RELOCATE_NEIGHBORS] =
4490 CreateOperator<MakeRelocateNeighborsOperator>(
4492 local_search_operators_[NODE_PAIR_SWAP] = solver_->ConcatenateOperators(
4493 {CreatePairOperator<IndexPairSwapActiveOperator>(),
4494 CreatePairOperator<SwapIndexPairOperator>(),
4495 CreatePairOperator<PairNodeSwapActiveOperator<true>>(),
4496 CreatePairOperator<PairNodeSwapActiveOperator<false>>()});
4497 local_search_operators_[RELOCATE_SUBTRIP] =
4498 CreatePairOperator<RelocateSubtrip>();
4499 local_search_operators_[EXCHANGE_SUBTRIP] =
4500 CreatePairOperator<ExchangeSubtrip>();
4502 const auto arc_cost_for_path_start =
4504 const int vehicle = index_to_vehicle_[start_index];
4505 const int64 arc_cost =
4507 return (before_node != start_index ||
IsEnd(after_node))
4511 local_search_operators_[RELOCATE_EXPENSIVE_CHAIN] =
4512 solver_->RevAlloc(
new RelocateExpensiveChain(
4516 vehicle_start_class_callback_,
4517 parameters.relocate_expensive_chain_num_arcs_to_consider(),
4518 arc_cost_for_path_start));
4521 const auto make_global_cheapest_insertion_filtered_heuristic =
4523 using Heuristic = GlobalCheapestInsertionFilteredHeuristic;
4524 Heuristic::GlobalCheapestInsertionParameters ls_gci_parameters;
4525 ls_gci_parameters.is_sequential =
false;
4526 ls_gci_parameters.farthest_seeds_ratio = 0.0;
4527 ls_gci_parameters.neighbors_ratio =
4528 parameters.cheapest_insertion_ls_operator_neighbors_ratio();
4529 ls_gci_parameters.min_neighbors =
4530 parameters.cheapest_insertion_ls_operator_min_neighbors();
4531 ls_gci_parameters.use_neighbors_ratio_for_initialization =
true;
4532 ls_gci_parameters.add_unperformed_entries =
4533 parameters.cheapest_insertion_add_unperformed_entries();
4534 return absl::make_unique<Heuristic>(
4537 GetOrCreateFeasibilityFilterManager(
parameters), ls_gci_parameters);
4539 const auto make_local_cheapest_insertion_filtered_heuristic =
4541 return absl::make_unique<LocalCheapestInsertionFilteredHeuristic>(
4543 GetOrCreateFeasibilityFilterManager(
parameters));
4545 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
4546 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
4547 make_global_cheapest_insertion_filtered_heuristic(),
4548 parameters.heuristic_close_nodes_lns_num_nodes()));
4550 local_search_operators_[LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
4551 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
4552 make_local_cheapest_insertion_filtered_heuristic(),
4553 parameters.heuristic_close_nodes_lns_num_nodes()));
4555 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_PATH_LNS] =
4556 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
4557 make_global_cheapest_insertion_filtered_heuristic()));
4559 local_search_operators_[LOCAL_CHEAPEST_INSERTION_PATH_LNS] =
4560 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
4561 make_local_cheapest_insertion_filtered_heuristic()));
4563 local_search_operators_
4564 [RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED] =
4566 new RelocatePathAndHeuristicInsertUnperformedOperator(
4567 make_global_cheapest_insertion_filtered_heuristic()));
4569 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
4570 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
4571 make_global_cheapest_insertion_filtered_heuristic(),
4572 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
4573 arc_cost_for_path_start));
4575 local_search_operators_[LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
4576 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
4577 make_local_cheapest_insertion_filtered_heuristic(),
4578 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
4579 arc_cost_for_path_start));
4582 #define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method, operators) \
4583 if (search_parameters.local_search_operators().use_##operator_method() == \
4585 operators.push_back(local_search_operators_[operator_type]); \
4588 LocalSearchOperator* RoutingModel::ConcatenateOperators(
4589 const RoutingSearchParameters& search_parameters,
4590 const std::vector<LocalSearchOperator*>& operators)
const {
4591 if (search_parameters.use_multi_armed_bandit_concatenate_operators()) {
4592 return solver_->MultiArmedBanditConcatenateOperators(
4595 .multi_armed_bandit_compound_operator_memory_coefficient(),
4597 .multi_armed_bandit_compound_operator_exploration_coefficient(),
4600 return solver_->ConcatenateOperators(operators);
4603 LocalSearchOperator* RoutingModel::GetNeighborhoodOperators(
4604 const RoutingSearchParameters& search_parameters)
const {
4605 std::vector<LocalSearchOperator*> operator_groups;
4606 std::vector<LocalSearchOperator*> operators = extra_operators_;
4607 if (!pickup_delivery_pairs_.empty()) {
4611 if (search_parameters.local_search_operators().use_relocate_pair() ==
4621 if (vehicles_ > 1) {
4632 if (!pickup_delivery_pairs_.empty() ||
4633 search_parameters.local_search_operators().use_relocate_neighbors() ==
4635 operators.push_back(local_search_operators_[RELOCATE_NEIGHBORS]);
4638 search_parameters.local_search_metaheuristic();
4639 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4640 local_search_metaheuristic !=
4641 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4642 local_search_metaheuristic !=
4643 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4650 if (!disjunctions_.
empty()) {
4667 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4676 global_cheapest_insertion_path_lns, operators);
4678 local_cheapest_insertion_path_lns, operators);
4680 RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,
4681 relocate_path_global_cheapest_insertion_insert_unperformed, operators);
4684 global_cheapest_insertion_expensive_chain_lns,
4687 local_cheapest_insertion_expensive_chain_lns,
4690 global_cheapest_insertion_close_nodes_lns,
4693 local_cheapest_insertion_close_nodes_lns, operators);
4694 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4698 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4699 local_search_metaheuristic !=
4700 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4701 local_search_metaheuristic !=
4702 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4705 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4706 local_search_metaheuristic !=
4707 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4708 local_search_metaheuristic !=
4709 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4714 if (!disjunctions_.
empty()) {
4717 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4719 return solver_->ConcatenateOperators(operator_groups);
4722 #undef CP_ROUTING_PUSH_OPERATOR
4726 if (dimension->GetUnaryTransitEvaluator(0) !=
nullptr)
return true;
4733 void ConvertVectorInt64ToVectorInt(
const std::vector<int64>&
input,
4734 std::vector<int>* output) {
4735 const int n =
input.size();
4737 int* data = output->data();
4738 for (
int i = 0; i < n; ++i) {
4739 const int element =
static_cast<int>(
input[i]);
4747 std::vector<LocalSearchFilterManager::FilterEvent>
4748 RoutingModel::GetOrCreateLocalSearchFilters(
4749 const RoutingSearchParameters&
parameters,
bool filter_cost) {
4750 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
4751 const auto kRelax = LocalSearchFilterManager::FilterEventType::kRelax;
4761 std::vector<LocalSearchFilterManager::FilterEvent> filters;
4763 if (filter_cost && vehicle_amortized_cost_factors_set_) {
4771 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
4774 filters.push_back({sum, kAccept});
4776 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
4777 nexts_, vehicle_vars_,
4782 filters.push_back({sum, kAccept});
4786 filters.push_back({solver_->MakeVariableDomainFilter(), kAccept});
4788 if (vehicles_ > max_active_vehicles_) {
4792 if (!disjunctions_.
empty()) {
4796 if (!pickup_delivery_pairs_.empty()) {
4799 vehicle_pickup_delivery_policy_),
4809 const PathState* path_state_reference =
nullptr;
4811 std::vector<int> path_starts;
4812 std::vector<int> path_ends;
4813 ConvertVectorInt64ToVectorInt(starts_, &path_starts);
4814 ConvertVectorInt64ToVectorInt(ends_, &path_ends);
4816 auto path_state = absl::make_unique<PathState>(
4817 Size() +
vehicles(), std::move(path_starts), std::move(path_ends));
4818 path_state_reference = path_state.get();
4830 if (!dimension->HasBreakConstraints())
continue;
4833 filters.insert(filters.end(), extra_filters_.begin(), extra_filters_.end());
4837 LocalSearchFilterManager* RoutingModel::GetOrCreateLocalSearchFilterManager(
4839 if (!local_search_filter_manager_) {
4840 local_search_filter_manager_ =
4841 solver_->RevAlloc(
new LocalSearchFilterManager(
4844 return local_search_filter_manager_;
4847 std::vector<LocalSearchFilterManager::FilterEvent>
4848 RoutingModel::GetOrCreateFeasibilityFilters(
4850 return GetOrCreateLocalSearchFilters(
parameters,
false);
4853 LocalSearchFilterManager* RoutingModel::GetOrCreateFeasibilityFilterManager(
4855 if (!feasibility_filter_manager_) {
4856 feasibility_filter_manager_ =
4857 solver_->RevAlloc(
new LocalSearchFilterManager(
4860 return feasibility_filter_manager_;
4863 LocalSearchFilterManager*
4864 RoutingModel::GetOrCreateStrongFeasibilityFilterManager(
4866 if (!strong_feasibility_filter_manager_) {
4867 std::vector<LocalSearchFilterManager::FilterEvent> filters =
4870 LocalSearchFilterManager::FilterEventType::kAccept});
4871 strong_feasibility_filter_manager_ =
4872 solver_->RevAlloc(
new LocalSearchFilterManager(std::move(filters)));
4874 return strong_feasibility_filter_manager_;
4878 bool AllTransitsPositive(
const RoutingDimension& dimension) {
4879 for (
int vehicle = 0; vehicle < dimension.model()->vehicles(); vehicle++) {
4880 if (!dimension.AreVehicleTransitsPositive(vehicle)) {
4888 void RoutingModel::StoreDimensionCumulOptimizers(
4890 Assignment* packed_dimensions_collector_assignment =
4891 solver_->MakeAssignment();
4892 packed_dimensions_collector_assignment->AddObjective(
CostVar());
4893 const int num_dimensions = dimensions_.size();
4894 local_optimizer_index_.
resize(num_dimensions, -1);
4895 global_optimizer_index_.
resize(num_dimensions, -1);
4898 if (dimension->global_span_cost_coefficient() > 0 ||
4899 !dimension->GetNodePrecedences().empty()) {
4901 global_optimizer_index_[dim] = global_dimension_optimizers_.size();
4902 global_dimension_optimizers_.push_back(
4903 absl::make_unique<GlobalDimensionCumulOptimizer>(dimension));
4904 packed_dimensions_collector_assignment->Add(dimension->cumuls());
4905 if (!AllTransitsPositive(*dimension)) {
4906 dimension->SetOffsetForGlobalOptimizer(0);
4910 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4913 std::min(offset, dimension->CumulVar(
Start(vehicle))->Min() - 1);
4915 dimension->SetOffsetForGlobalOptimizer(
std::max(
Zero(), offset));
4917 bool has_span_cost =
false;
4918 bool has_span_limit =
false;
4919 std::vector<int64> vehicle_offsets(
vehicles());
4920 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4921 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
4922 has_span_cost =
true;
4924 if (dimension->GetSpanUpperBoundForVehicle(vehicle) <
kint64max) {
4925 has_span_limit =
true;
4928 vehicle_offsets[vehicle] =
4929 dimension->AreVehicleTransitsPositive(vehicle)
4931 dimension->CumulVar(
Start(vehicle))->Min() - 1)
4934 bool has_soft_lower_bound =
false;
4935 bool has_soft_upper_bound =
false;
4936 for (
int i = 0; i < dimension->cumuls().size(); ++i) {
4937 if (dimension->HasCumulVarSoftLowerBound(i)) {
4938 has_soft_lower_bound =
true;
4940 if (dimension->HasCumulVarSoftUpperBound(i)) {
4941 has_soft_upper_bound =
true;
4944 int num_linear_constraints = 0;
4945 if (has_span_cost) ++num_linear_constraints;
4946 if (has_span_limit) ++num_linear_constraints;
4947 if (dimension->HasSoftSpanUpperBounds()) ++num_linear_constraints;
4948 if (has_soft_lower_bound) ++num_linear_constraints;
4949 if (has_soft_upper_bound) ++num_linear_constraints;
4950 if (dimension->HasBreakConstraints()) ++num_linear_constraints;
4951 if (num_linear_constraints >= 2) {
4952 dimension->SetVehicleOffsetsForLocalOptimizer(
4953 std::move(vehicle_offsets));
4954 local_optimizer_index_[dim] = local_dimension_optimizers_.size();
4955 local_dimension_optimizers_.push_back(
4956 absl::make_unique<LocalDimensionCumulOptimizer>(
4957 dimension,
parameters.continuous_scheduling_solver()));
4958 bool has_intervals =
false;
4959 for (
const SortedDisjointIntervalList& intervals :
4960 dimension->forbidden_intervals()) {
4963 if (intervals.NumIntervals() > 0) {
4964 has_intervals =
true;
4968 if (dimension->HasBreakConstraints() || has_intervals) {
4969 local_dimension_mp_optimizers_.push_back(
4970 absl::make_unique<LocalDimensionCumulOptimizer>(
4971 dimension,
parameters.mixed_integer_scheduling_solver()));
4973 local_dimension_mp_optimizers_.push_back(
nullptr);
4975 packed_dimensions_collector_assignment->Add(dimension->cumuls());
4978 DCHECK_EQ(local_dimension_mp_optimizers_.size(),
4979 local_dimension_optimizers_.size());
4985 for (IntVar*
const extra_var : extra_vars_) {
4986 packed_dimensions_collector_assignment->Add(extra_var);
4988 for (IntervalVar*
const extra_interval : extra_intervals_) {
4989 packed_dimensions_collector_assignment->Add(extra_interval);
4992 packed_dimensions_assignment_collector_ = solver_->MakeFirstSolutionCollector(
4993 packed_dimensions_collector_assignment);
4998 std::vector<RoutingDimension*> dimensions;
5000 bool has_soft_or_span_cost =
false;
5001 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5002 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
5003 has_soft_or_span_cost =
true;
5007 if (!has_soft_or_span_cost) {
5008 for (
int i = 0; i < dimension->cumuls().size(); ++i) {
5009 if (dimension->HasCumulVarSoftUpperBound(i) ||
5010 dimension->HasCumulVarSoftLowerBound(i)) {
5011 has_soft_or_span_cost =
true;
5016 if (has_soft_or_span_cost) dimensions.push_back(dimension);
5022 RoutingModel::CreateFinalizerForMinimizedAndMaximizedVariables() {
5023 std::stable_sort(finalizer_variable_cost_pairs_.begin(),
5024 finalizer_variable_cost_pairs_.end(),
5025 [](
const std::pair<IntVar*, int64>& var_cost1,
5026 const std::pair<IntVar*, int64>& var_cost2) {
5027 return var_cost1.second > var_cost2.second;
5029 const int num_variables = finalizer_variable_cost_pairs_.size() +
5030 finalizer_variable_target_pairs_.size();
5031 std::vector<IntVar*> variables;
5032 std::vector<int64> targets;
5033 variables.reserve(num_variables);
5034 targets.reserve(num_variables);
5035 for (
const auto& variable_cost : finalizer_variable_cost_pairs_) {
5036 variables.push_back(variable_cost.first);
5039 for (
const auto& variable_target : finalizer_variable_target_pairs_) {
5040 variables.push_back(variable_target.first);
5041 targets.push_back(variable_target.second);
5044 std::move(targets));
5047 DecisionBuilder* RoutingModel::CreateSolutionFinalizer(SearchLimit* lns_limit) {
5048 std::vector<DecisionBuilder*> decision_builders;
5049 decision_builders.push_back(solver_->MakePhase(
5052 if (!local_dimension_optimizers_.empty()) {
5053 decision_builders.push_back(
5054 solver_->RevAlloc(
new SetCumulsFromLocalDimensionCosts(
5055 &local_dimension_optimizers_, &local_dimension_mp_optimizers_,
5058 if (!global_dimension_optimizers_.empty()) {
5059 decision_builders.push_back(
5060 solver_->RevAlloc(
new SetCumulsFromGlobalDimensionCosts(
5061 &global_dimension_optimizers_, lns_limit)));
5063 decision_builders.push_back(
5064 CreateFinalizerForMinimizedAndMaximizedVariables());
5066 return solver_->Compose(decision_builders);
5069 void RoutingModel::CreateFirstSolutionDecisionBuilders(
5070 const RoutingSearchParameters& search_parameters) {
5071 first_solution_decision_builders_.resize(
5072 FirstSolutionStrategy_Value_Value_ARRAYSIZE,
nullptr);
5073 first_solution_filtered_decision_builders_.resize(
5074 FirstSolutionStrategy_Value_Value_ARRAYSIZE,
nullptr);
5075 DecisionBuilder*
const finalize_solution =
5076 CreateSolutionFinalizer(GetOrCreateLargeNeighborhoodSearchLimit());
5078 first_solution_decision_builders_
5079 [FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE] = finalize_solution;
5081 first_solution_decision_builders_
5082 [FirstSolutionStrategy::GLOBAL_CHEAPEST_ARC] = solver_->MakePhase(
5090 first_solution_decision_builders_[FirstSolutionStrategy::LOCAL_CHEAPEST_ARC] =
5093 first_solution_decision_builders_[FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5095 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5096 first_solution_filtered_decision_builders_
5097 [FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5098 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5099 absl::make_unique<EvaluatorCheapestAdditionFilteredHeuristic>(
5104 GetOrCreateFeasibilityFilterManager(search_parameters))));
5105 first_solution_decision_builders_
5106 [FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5107 solver_->Try(first_solution_filtered_decision_builders_
5108 [FirstSolutionStrategy::PATH_CHEAPEST_ARC],
5109 first_solution_decision_builders_
5110 [FirstSolutionStrategy::PATH_CHEAPEST_ARC]);
5117 first_solution_decision_builders_
5118 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] =
5120 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5121 first_solution_filtered_decision_builders_
5122 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] =
5123 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5124 absl::make_unique<ComparatorCheapestAdditionFilteredHeuristic>(
5126 GetOrCreateFeasibilityFilterManager(search_parameters))));
5127 first_solution_decision_builders_
5128 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] = solver_->Try(
5129 first_solution_filtered_decision_builders_
5130 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC],
5131 first_solution_decision_builders_
5132 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC]);
5135 if (first_solution_evaluator_ !=
nullptr) {
5136 first_solution_decision_builders_
5137 [FirstSolutionStrategy::EVALUATOR_STRATEGY] = solver_->MakePhase(
5140 first_solution_decision_builders_
5141 [FirstSolutionStrategy::EVALUATOR_STRATEGY] =
nullptr;
5144 first_solution_decision_builders_[FirstSolutionStrategy::ALL_UNPERFORMED] =
5145 solver_->RevAlloc(
new AllUnperformed(
this));
5147 RegularLimit*
const ls_limit =
5150 DecisionBuilder*
const finalize = solver_->MakeSolveOnce(
5151 finalize_solution, GetOrCreateLargeNeighborhoodSearchLimit());
5152 LocalSearchPhaseParameters*
const insertion_parameters =
5153 solver_->MakeLocalSearchPhaseParameters(
5154 nullptr, CreateInsertionOperator(), finalize, ls_limit,
5155 GetOrCreateLocalSearchFilterManager(search_parameters));
5156 std::vector<IntVar*> decision_vars = nexts_;
5158 decision_vars.insert(decision_vars.end(), vehicle_vars_.begin(),
5159 vehicle_vars_.end());
5163 first_solution_decision_builders_[FirstSolutionStrategy::BEST_INSERTION] =
5164 solver_->MakeNestedOptimize(
5165 solver_->MakeLocalSearchPhase(
5166 decision_vars, solver_->RevAlloc(
new AllUnperformed(
this)),
5167 insertion_parameters),
5168 GetOrCreateAssignment(),
false, optimization_step);
5169 first_solution_decision_builders_[FirstSolutionStrategy::BEST_INSERTION] =
5170 solver_->Compose(first_solution_decision_builders_
5171 [FirstSolutionStrategy::BEST_INSERTION],
5175 GlobalCheapestInsertionFilteredHeuristic::GlobalCheapestInsertionParameters
5177 gci_parameters.is_sequential =
false;
5178 gci_parameters.farthest_seeds_ratio =
5179 search_parameters.cheapest_insertion_farthest_seeds_ratio();
5180 gci_parameters.neighbors_ratio =
5181 search_parameters.cheapest_insertion_first_solution_neighbors_ratio();
5182 gci_parameters.min_neighbors =
5183 search_parameters.cheapest_insertion_first_solution_min_neighbors();
5184 gci_parameters.use_neighbors_ratio_for_initialization =
false;
5185 gci_parameters.add_unperformed_entries =
5186 search_parameters.cheapest_insertion_add_unperformed_entries();
5187 for (
bool is_sequential : {
false,
true}) {
5189 is_sequential ? FirstSolutionStrategy::SEQUENTIAL_CHEAPEST_INSERTION
5190 : FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION;
5191 gci_parameters.is_sequential = is_sequential;
5193 first_solution_filtered_decision_builders_[first_solution_strategy] =
5194 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5195 absl::make_unique<GlobalCheapestInsertionFilteredHeuristic>(
5201 GetOrCreateFeasibilityFilterManager(search_parameters),
5203 IntVarFilteredDecisionBuilder*
const strong_gci =
5204 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5205 absl::make_unique<GlobalCheapestInsertionFilteredHeuristic>(
5211 GetOrCreateStrongFeasibilityFilterManager(search_parameters),
5213 first_solution_decision_builders_[first_solution_strategy] = solver_->Try(
5214 first_solution_filtered_decision_builders_[first_solution_strategy],
5215 solver_->Try(strong_gci, first_solution_decision_builders_
5216 [FirstSolutionStrategy::BEST_INSERTION]));
5220 first_solution_filtered_decision_builders_
5221 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION] =
5222 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5223 absl::make_unique<LocalCheapestInsertionFilteredHeuristic>(
5228 GetOrCreateFeasibilityFilterManager(search_parameters))));
5229 IntVarFilteredDecisionBuilder*
const strong_lci =
5230 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5231 absl::make_unique<LocalCheapestInsertionFilteredHeuristic>(
5236 GetOrCreateStrongFeasibilityFilterManager(search_parameters))));
5237 first_solution_decision_builders_
5238 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION] = solver_->Try(
5239 first_solution_filtered_decision_builders_
5240 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION],
5241 solver_->Try(strong_lci,
5242 first_solution_decision_builders_
5243 [FirstSolutionStrategy::BEST_INSERTION]));
5245 SavingsFilteredHeuristic::SavingsParameters savings_parameters;
5246 savings_parameters.neighbors_ratio =
5247 search_parameters.savings_neighbors_ratio();
5248 savings_parameters.max_memory_usage_bytes =
5249 search_parameters.savings_max_memory_usage_bytes();
5250 savings_parameters.add_reverse_arcs =
5251 search_parameters.savings_add_reverse_arcs();
5252 savings_parameters.arc_coefficient =
5253 search_parameters.savings_arc_coefficient();
5254 LocalSearchFilterManager* filter_manager =
nullptr;
5255 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5256 filter_manager = GetOrCreateFeasibilityFilterManager(search_parameters);
5259 if (search_parameters.savings_parallel_routes()) {
5260 IntVarFilteredDecisionBuilder* savings_db =
5261 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5262 absl::make_unique<ParallelSavingsFilteredHeuristic>(
5263 this, &manager_, savings_parameters, filter_manager)));
5264 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5265 first_solution_filtered_decision_builders_
5266 [FirstSolutionStrategy::SAVINGS] = savings_db;
5269 first_solution_decision_builders_[FirstSolutionStrategy::SAVINGS] =
5270 solver_->Try(savings_db,
5271 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5272 absl::make_unique<ParallelSavingsFilteredHeuristic>(
5273 this, &manager_, savings_parameters,
5274 GetOrCreateStrongFeasibilityFilterManager(
5275 search_parameters)))));
5277 IntVarFilteredDecisionBuilder* savings_db =
5278 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5279 absl::make_unique<SequentialSavingsFilteredHeuristic>(
5280 this, &manager_, savings_parameters, filter_manager)));
5281 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5282 first_solution_filtered_decision_builders_
5283 [FirstSolutionStrategy::SAVINGS] = savings_db;
5286 first_solution_decision_builders_[FirstSolutionStrategy::SAVINGS] =
5287 solver_->Try(savings_db,
5288 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5289 absl::make_unique<SequentialSavingsFilteredHeuristic>(
5290 this, &manager_, savings_parameters,
5291 GetOrCreateStrongFeasibilityFilterManager(
5292 search_parameters)))));
5295 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP] =
5296 solver_->RevAlloc(
new SweepBuilder(
this,
true));
5297 DecisionBuilder* sweep_builder =
5298 solver_->RevAlloc(
new SweepBuilder(
this,
false));
5299 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP] =
5302 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP]);
5304 first_solution_decision_builders_[FirstSolutionStrategy::CHRISTOFIDES] =
5305 solver_->RevAlloc(
new IntVarFilteredDecisionBuilder(
5306 absl::make_unique<ChristofidesFilteredHeuristic>(
5307 this, GetOrCreateFeasibilityFilterManager(search_parameters),
5308 search_parameters.christofides_use_minimum_matching())));
5311 const bool has_precedences = std::any_of(
5312 dimensions_.begin(), dimensions_.end(),
5314 if (pickup_delivery_pairs_.empty() && !has_precedences) {
5315 automatic_first_solution_strategy_ =
5316 FirstSolutionStrategy::PATH_CHEAPEST_ARC;
5318 automatic_first_solution_strategy_ =
5319 FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION;
5321 first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC] =
5322 first_solution_decision_builders_[automatic_first_solution_strategy_];
5323 first_solution_decision_builders_[FirstSolutionStrategy::UNSET] =
5324 first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC];
5327 DecisionBuilder* RoutingModel::GetFirstSolutionDecisionBuilder(
5328 const RoutingSearchParameters& search_parameters)
const {
5330 search_parameters.first_solution_strategy();
5331 if (first_solution_strategy < first_solution_decision_builders_.size()) {
5332 return first_solution_decision_builders_[first_solution_strategy];
5338 IntVarFilteredDecisionBuilder*
5339 RoutingModel::GetFilteredFirstSolutionDecisionBuilderOrNull(
5340 const RoutingSearchParameters& search_parameters)
const {
5342 search_parameters.first_solution_strategy();
5343 return first_solution_filtered_decision_builders_[first_solution_strategy];
5346 LocalSearchPhaseParameters* RoutingModel::CreateLocalSearchParameters(
5347 const RoutingSearchParameters& search_parameters) {
5348 SearchLimit* lns_limit = GetOrCreateLargeNeighborhoodSearchLimit();
5349 return solver_->MakeLocalSearchPhaseParameters(
5350 CostVar(), GetNeighborhoodOperators(search_parameters),
5351 solver_->MakeSolveOnce(CreateSolutionFinalizer(lns_limit), lns_limit),
5352 GetOrCreateLocalSearchLimit(),
5353 GetOrCreateLocalSearchFilterManager(search_parameters));
5356 DecisionBuilder* RoutingModel::CreateLocalSearchDecisionBuilder(
5357 const RoutingSearchParameters& search_parameters) {
5358 const int size =
Size();
5359 DecisionBuilder* first_solution =
5360 GetFirstSolutionDecisionBuilder(search_parameters);
5361 LocalSearchPhaseParameters*
const parameters =
5362 CreateLocalSearchParameters(search_parameters);
5363 SearchLimit* first_solution_lns_limit =
5364 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
5365 DecisionBuilder*
const first_solution_sub_decision_builder =
5366 solver_->MakeSolveOnce(CreateSolutionFinalizer(first_solution_lns_limit),
5367 first_solution_lns_limit);
5369 return solver_->MakeLocalSearchPhase(nexts_, first_solution,
5370 first_solution_sub_decision_builder,
5373 const int all_size = size + size + vehicles_;
5374 std::vector<IntVar*> all_vars(all_size);
5375 for (
int i = 0; i < size; ++i) {
5376 all_vars[i] = nexts_[i];
5378 for (
int i = size; i < all_size; ++i) {
5379 all_vars[i] = vehicle_vars_[i - size];
5381 return solver_->MakeLocalSearchPhase(all_vars, first_solution,
5382 first_solution_sub_decision_builder,
5387 void RoutingModel::SetupDecisionBuilders(
5388 const RoutingSearchParameters& search_parameters) {
5389 if (search_parameters.use_depth_first_search()) {
5390 SearchLimit* first_lns_limit =
5391 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
5392 solve_db_ = solver_->Compose(
5393 GetFirstSolutionDecisionBuilder(search_parameters),
5394 solver_->MakeSolveOnce(CreateSolutionFinalizer(first_lns_limit),
5397 solve_db_ = CreateLocalSearchDecisionBuilder(search_parameters);
5399 CHECK(preassignment_ !=
nullptr);
5400 DecisionBuilder* restore_preassignment =
5401 solver_->MakeRestoreAssignment(preassignment_);
5402 solve_db_ = solver_->Compose(restore_preassignment, solve_db_);
5404 solver_->Compose(restore_preassignment,
5405 solver_->MakeLocalSearchPhase(
5406 GetOrCreateAssignment(),
5407 CreateLocalSearchParameters(search_parameters)));
5408 restore_assignment_ = solver_->Compose(
5409 solver_->MakeRestoreAssignment(GetOrCreateAssignment()),
5410 CreateSolutionFinalizer(GetOrCreateLargeNeighborhoodSearchLimit()));
5411 restore_tmp_assignment_ = solver_->Compose(
5412 restore_preassignment,
5413 solver_->MakeRestoreAssignment(GetOrCreateTmpAssignment()),
5414 CreateSolutionFinalizer(GetOrCreateLargeNeighborhoodSearchLimit()));
5417 void RoutingModel::SetupMetaheuristics(
5418 const RoutingSearchParameters& search_parameters) {
5419 SearchMonitor* optimize;
5421 search_parameters.local_search_metaheuristic();
5424 bool limit_too_long = !search_parameters.has_time_limit() &&
5425 search_parameters.solution_limit() ==
kint64max;
5428 switch (metaheuristic) {
5429 case LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH:
5431 optimize = solver_->MakeGuidedLocalSearch(
5434 optimization_step, nexts_,
5435 search_parameters.guided_local_search_lambda_coefficient());
5437 optimize = solver_->MakeGuidedLocalSearch(
5442 optimization_step, nexts_, vehicle_vars_,
5443 search_parameters.guided_local_search_lambda_coefficient());
5446 case LocalSearchMetaheuristic::SIMULATED_ANNEALING:
5448 solver_->MakeSimulatedAnnealing(
false, cost_, optimization_step, 100);
5450 case LocalSearchMetaheuristic::TABU_SEARCH:
5451 optimize = solver_->MakeTabuSearch(
false, cost_, optimization_step,
5452 nexts_, 10, 10, .8);
5454 case LocalSearchMetaheuristic::GENERIC_TABU_SEARCH: {
5455 std::vector<operations_research::IntVar*> tabu_vars;
5456 if (tabu_var_callback_) {
5457 tabu_vars = tabu_var_callback_(
this);
5459 tabu_vars.push_back(cost_);
5461 optimize = solver_->MakeGenericTabuSearch(
false, cost_, optimization_step,
5466 limit_too_long =
false;
5467 optimize = solver_->MakeMinimize(cost_, optimization_step);
5469 if (limit_too_long) {
5470 LOG(
WARNING) << LocalSearchMetaheuristic::Value_Name(metaheuristic)
5471 <<
" specified without sane timeout: solve may run forever.";
5473 monitors_.push_back(optimize);
5477 tabu_var_callback_ = std::move(tabu_var_callback);
5480 void RoutingModel::SetupAssignmentCollector(
5481 const RoutingSearchParameters& search_parameters) {
5482 Assignment* full_assignment = solver_->MakeAssignment();
5484 full_assignment->
Add(dimension->cumuls());
5486 for (IntVar*
const extra_var : extra_vars_) {
5487 full_assignment->
Add(extra_var);
5489 for (IntervalVar*
const extra_interval : extra_intervals_) {
5490 full_assignment->
Add(extra_interval);
5492 full_assignment->
Add(nexts_);
5493 full_assignment->
Add(active_);
5494 full_assignment->
Add(vehicle_vars_);
5497 collect_assignments_ = solver_->MakeNBestValueSolutionCollector(
5498 full_assignment, search_parameters.number_of_solutions_to_collect(),
5500 collect_one_assignment_ =
5501 solver_->MakeFirstSolutionCollector(full_assignment);
5502 monitors_.push_back(collect_assignments_);
5505 void RoutingModel::SetupTrace(
5506 const RoutingSearchParameters& search_parameters) {
5507 if (search_parameters.log_search()) {
5508 Solver::SearchLogParameters search_log_parameters;
5509 search_log_parameters.branch_period = 10000;
5510 search_log_parameters.objective =
nullptr;
5511 search_log_parameters.variable = cost_;
5512 search_log_parameters.scaling_factor =
5513 search_parameters.log_cost_scaling_factor();
5514 search_log_parameters.offset = search_parameters.log_cost_offset();
5515 if (!search_parameters.log_tag().empty()) {
5516 const std::string& tag = search_parameters.log_tag();
5517 search_log_parameters.display_callback = [tag]() {
return tag; };
5519 search_log_parameters.display_callback =
nullptr;
5521 search_log_parameters.display_on_new_solutions_only =
false;
5522 monitors_.push_back(solver_->MakeSearchLog(search_log_parameters));
5526 void RoutingModel::SetupImprovementLimit(
5527 const RoutingSearchParameters& search_parameters) {
5528 if (search_parameters.has_improvement_limit_parameters()) {
5529 monitors_.push_back(solver_->MakeImprovementLimit(
5530 cost_,
false, search_parameters.log_cost_scaling_factor(),
5531 search_parameters.log_cost_offset(),
5532 search_parameters.improvement_limit_parameters()
5533 .improvement_rate_coefficient(),
5534 search_parameters.improvement_limit_parameters()
5535 .improvement_rate_solutions_distance()));
5539 void RoutingModel::SetupSearchMonitors(
5540 const RoutingSearchParameters& search_parameters) {
5541 monitors_.push_back(GetOrCreateLimit());
5542 SetupImprovementLimit(search_parameters);
5543 SetupMetaheuristics(search_parameters);
5544 SetupAssignmentCollector(search_parameters);
5545 SetupTrace(search_parameters);
5548 bool RoutingModel::UsesLightPropagation(
5549 const RoutingSearchParameters& search_parameters)
const {
5550 return !search_parameters.use_full_propagation() &&
5551 !search_parameters.use_depth_first_search() &&
5552 search_parameters.first_solution_strategy() !=
5553 FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE;
5560 finalizer_variable_cost_pairs_.size());
5561 if (
index < finalizer_variable_cost_pairs_.size()) {
5562 const int64 old_cost = finalizer_variable_cost_pairs_[
index].second;
5563 finalizer_variable_cost_pairs_[
index].second =
CapAdd(old_cost,
cost);
5565 finalizer_variable_cost_pairs_.emplace_back(
var,
cost);
5571 if (finalizer_variable_target_set_.contains(
var))
return;
5572 finalizer_variable_target_set_.insert(
var);
5573 finalizer_variable_target_pairs_.emplace_back(
var, target);
5584 void RoutingModel::SetupSearch(
5585 const RoutingSearchParameters& search_parameters) {
5586 SetupDecisionBuilders(search_parameters);
5587 SetupSearchMonitors(search_parameters);
5591 extra_vars_.push_back(
var);
5595 extra_intervals_.push_back(
interval);
5600 class PathSpansAndTotalSlacks :
public Constraint {
5604 std::vector<IntVar*> spans,
5605 std::vector<IntVar*> total_slacks)
5608 dimension_(dimension),
5609 spans_(std::move(spans)),
5610 total_slacks_(std::move(total_slacks)) {
5611 CHECK_EQ(spans_.size(), model_->vehicles());
5612 CHECK_EQ(total_slacks_.size(), model_->vehicles());
5613 vehicle_demons_.resize(model_->vehicles());
5616 std::string DebugString()
const override {
return "PathSpansAndTotalSlacks"; }
5618 void Post()
override {
5619 const int num_nodes = model_->VehicleVars().size();
5620 const int num_transits = model_->Nexts().size();
5621 for (
int node = 0; node < num_nodes; ++node) {
5623 model_->solver(),
this, &PathSpansAndTotalSlacks::PropagateNode,
5624 "PathSpansAndTotalSlacks::PropagateNode", node);
5625 dimension_->CumulVar(node)->WhenRange(demon);
5626 model_->VehicleVar(node)->WhenBound(demon);
5627 if (node < num_transits) {
5628 dimension_->TransitVar(node)->WhenRange(demon);
5629 dimension_->FixedTransitVar(node)->WhenBound(demon);
5630 model_->NextVar(node)->WhenBound(demon);
5633 for (
int vehicle = 0; vehicle < spans_.size(); ++vehicle) {
5634 if (!spans_[vehicle] && !total_slacks_[vehicle])
continue;
5636 solver(),
this, &PathSpansAndTotalSlacks::PropagateVehicle,
5637 "PathSpansAndTotalSlacks::PropagateVehicle", vehicle);
5638 vehicle_demons_[vehicle] = demon;
5639 if (spans_[vehicle]) spans_[vehicle]->WhenRange(demon);
5640 if (total_slacks_[vehicle]) total_slacks_[vehicle]->WhenRange(demon);
5641 if (dimension_->HasBreakConstraints()) {
5642 for (IntervalVar*
b : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
5643 b->WhenAnything(demon);
5650 void InitialPropagate()
override {
5651 for (
int vehicle = 0; vehicle < spans_.size(); ++vehicle) {
5652 if (!spans_[vehicle] && !total_slacks_[vehicle])
continue;
5653 PropagateVehicle(vehicle);
5661 void PropagateNode(
int node) {
5662 if (!model_->VehicleVar(node)->Bound())
return;
5663 const int vehicle = model_->VehicleVar(node)->Min();
5664 if (vehicle < 0 || vehicle_demons_[vehicle] ==
nullptr)
return;
5665 EnqueueDelayedDemon(vehicle_demons_[vehicle]);
5673 int64 SpanMin(
int vehicle,
int64 sum_fixed_transits) {
5675 const int64 span_min = spans_[vehicle] ? spans_[vehicle]->Min() :
kint64max;
5676 const int64 total_slack_min =
5677 total_slacks_[vehicle] ? total_slacks_[vehicle]->Min() :
kint64max;
5678 return std::min(span_min,
CapAdd(total_slack_min, sum_fixed_transits));
5680 int64 SpanMax(
int vehicle,
int64 sum_fixed_transits) {
5682 const int64 span_max = spans_[vehicle] ? spans_[vehicle]->Max() :
kint64min;
5683 const int64 total_slack_max =
5684 total_slacks_[vehicle] ? total_slacks_[vehicle]->Max() :
kint64min;
5685 return std::max(span_max,
CapAdd(total_slack_max, sum_fixed_transits));
5687 void SetSpanMin(
int vehicle,
int64 min,
int64 sum_fixed_transits) {
5689 if (spans_[vehicle]) {
5690 spans_[vehicle]->SetMin(
min);
5692 if (total_slacks_[vehicle]) {
5693 total_slacks_[vehicle]->SetMin(
CapSub(
min, sum_fixed_transits));
5696 void SetSpanMax(
int vehicle,
int64 max,
int64 sum_fixed_transits) {
5698 if (spans_[vehicle]) {
5699 spans_[vehicle]->SetMax(
max);
5701 if (total_slacks_[vehicle]) {
5702 total_slacks_[vehicle]->SetMax(
CapSub(
max, sum_fixed_transits));
5707 void SynchronizeSpanAndTotalSlack(
int vehicle,
int64 sum_fixed_transits) {
5709 IntVar* span = spans_[vehicle];
5710 IntVar* total_slack = total_slacks_[vehicle];
5711 if (!span || !total_slack)
return;
5712 span->SetMin(
CapAdd(total_slack->Min(), sum_fixed_transits));
5713 span->SetMax(
CapAdd(total_slack->Max(), sum_fixed_transits));
5714 total_slack->SetMin(
CapSub(span->Min(), sum_fixed_transits));
5715 total_slack->SetMax(
CapSub(span->Max(), sum_fixed_transits));
5718 void PropagateVehicle(
int vehicle) {
5719 DCHECK(spans_[vehicle] || total_slacks_[vehicle]);
5720 const int start = model_->Start(vehicle);
5721 const int end = model_->End(vehicle);
5727 int curr_node = start;
5728 while (!model_->IsEnd(curr_node)) {
5729 const IntVar* next_var = model_->NextVar(curr_node);
5730 if (!next_var->Bound())
return;
5731 path_.push_back(curr_node);
5732 curr_node = next_var->Value();
5737 int64 sum_fixed_transits = 0;
5738 for (
const int node : path_) {
5739 const IntVar* fixed_transit_var = dimension_->FixedTransitVar(node);
5740 if (!fixed_transit_var->Bound())
return;
5741 sum_fixed_transits =
5742 CapAdd(sum_fixed_transits, fixed_transit_var->Value());
5745 SynchronizeSpanAndTotalSlack(vehicle, sum_fixed_transits);
5752 if (dimension_->HasBreakConstraints() &&
5753 !dimension_->GetBreakIntervalsOfVehicle(vehicle).empty()) {
5754 const int64 vehicle_start_max = dimension_->CumulVar(start)->Max();
5755 const int64 vehicle_end_min = dimension_->CumulVar(end)->Min();
5757 int64 min_break_duration = 0;
5758 for (IntervalVar* br : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
5759 if (!br->MustBePerformed())
continue;
5760 if (vehicle_start_max < br->EndMin() &&
5761 br->StartMax() < vehicle_end_min) {
5762 min_break_duration =
CapAdd(min_break_duration, br->DurationMin());
5765 SetSpanMin(vehicle,
CapAdd(min_break_duration, sum_fixed_transits),
5766 sum_fixed_transits);
5772 const int64 slack_max =
5773 CapSub(SpanMax(vehicle, sum_fixed_transits), sum_fixed_transits);
5774 const int64 max_additional_slack =
CapSub(slack_max, min_break_duration);
5775 for (IntervalVar* br : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
5776 if (!br->MustBePerformed())
continue;
5778 if (vehicle_start_max >= br->EndMin() &&
5779 br->StartMax() < vehicle_end_min) {
5780 if (br->DurationMin() > max_additional_slack) {
5783 br->SetEndMax(vehicle_start_max);
5784 dimension_->CumulVar(start)->SetMin(br->EndMin());
5789 if (vehicle_start_max < br->EndMin() &&
5790 br->StartMax() >= vehicle_end_min) {
5791 if (br->DurationMin() > max_additional_slack) {
5792 br->SetStartMin(vehicle_end_min);
5793 dimension_->CumulVar(end)->SetMax(br->StartMax());
5801 IntVar* start_cumul = dimension_->CumulVar(start);
5802 IntVar* end_cumul = dimension_->CumulVar(end);
5809 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
5811 SetSpanMax(vehicle, span_ub, sum_fixed_transits);
5813 const int64 span_min = SpanMin(vehicle, sum_fixed_transits);
5814 const int64 span_max = SpanMax(vehicle, sum_fixed_transits);
5815 const int64 slack_from_lb =
CapSub(span_max, span_lb);
5816 const int64 slack_from_ub =
CapSub(span_ub, span_min);
5832 for (
const int node : path_) {
5833 span_lb =
CapAdd(span_lb, dimension_->TransitVar(node)->Min());
5834 span_ub =
CapAdd(span_ub, dimension_->TransitVar(node)->Max());
5836 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
5837 SetSpanMax(vehicle, span_ub, sum_fixed_transits);
5841 const int64 span_min = SpanMin(vehicle, sum_fixed_transits);
5842 const int64 span_max = SpanMax(vehicle, sum_fixed_transits);
5843 const int64 slack_from_lb =
CapSub(span_max, span_lb);
5844 const int64 slack_from_ub =
5846 for (
const int node : path_) {
5847 IntVar* transit_var = dimension_->TransitVar(node);
5848 const int64 transit_i_min = transit_var->Min();
5849 const int64 transit_i_max = transit_var->Max();
5853 transit_var->SetMax(
CapAdd(transit_i_min, slack_from_lb));
5854 transit_var->SetMin(
CapSub(transit_i_max, slack_from_ub));
5859 path_.push_back(end);
5870 int64 arrival_time = dimension_->CumulVar(start)->Min();
5871 for (
int i = 1; i < path_.size(); ++i) {
5874 dimension_->FixedTransitVar(path_[i - 1])->Min()),
5875 dimension_->CumulVar(path_[i])->Min());
5877 int64 departure_time = arrival_time;
5878 for (
int i = path_.size() - 2; i >= 0; --i) {
5881 dimension_->FixedTransitVar(path_[i])->Min()),
5882 dimension_->CumulVar(path_[i])->Max());
5884 const int64 span_lb =
CapSub(arrival_time, departure_time);
5885 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
5886 const int64 maximum_deviation =
5887 CapSub(SpanMax(vehicle, sum_fixed_transits), span_lb);
5888 const int64 start_lb =
CapSub(departure_time, maximum_deviation);
5889 dimension_->CumulVar(start)->SetMin(start_lb);
5893 int64 departure_time = dimension_->CumulVar(end)->Max();
5894 for (
int i = path_.size() - 2; i >= 0; --i) {
5895 const int curr_node = path_[i];
5898 dimension_->FixedTransitVar(curr_node)->Min()),
5899 dimension_->CumulVar(curr_node)->Max());
5901 int arrival_time = departure_time;
5902 for (
int i = 1; i < path_.size(); ++i) {
5905 dimension_->FixedTransitVar(path_[i - 1])->Min()),
5906 dimension_->CumulVar(path_[i])->Min());
5908 const int64 span_lb =
CapSub(arrival_time, departure_time);
5909 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
5910 const int64 maximum_deviation =
5911 CapSub(SpanMax(vehicle, sum_fixed_transits), span_lb);
5912 dimension_->CumulVar(end)->SetMax(
5913 CapAdd(arrival_time, maximum_deviation));
5917 const RoutingModel*
const model_;
5918 const RoutingDimension*
const dimension_;
5919 std::vector<IntVar*> spans_;
5920 std::vector<IntVar*> total_slacks_;
5921 std::vector<int> path_;
5922 std::vector<Demon*> vehicle_demons_;
5929 std::vector<IntVar*> total_slacks) {
5931 CHECK_EQ(vehicles_, total_slacks.size());
5933 new PathSpansAndTotalSlacks(
this, dimension, spans, total_slacks));
5941 std::vector<int64> vehicle_capacities,
5942 const std::string&
name,
5944 : vehicle_capacities_(std::move(vehicle_capacities)),
5945 base_dimension_(base_dimension),
5946 global_span_cost_coefficient_(0),
5949 global_optimizer_offset_(0) {
5952 vehicle_span_cost_coefficients_.assign(
model->vehicles(), 0);
5955 RoutingDimension::RoutingDimension(RoutingModel*
model,
5956 std::vector<int64> vehicle_capacities,
5957 const std::string&
name, SelfBased)
5958 : RoutingDimension(
model, std::move(vehicle_capacities),
name, this) {}
5961 cumul_var_piecewise_linear_cost_.clear();
5964 void RoutingDimension::Initialize(
5965 const std::vector<int>& transit_evaluators,
5966 const std::vector<int>& state_dependent_transit_evaluators,
5969 InitializeTransits(transit_evaluators, state_dependent_transit_evaluators,
5983 class LightRangeLessOrEqual :
public Constraint {
5985 LightRangeLessOrEqual(Solver*
const s, IntExpr*
const l, IntExpr*
const r);
5986 ~LightRangeLessOrEqual()
override {}
5987 void Post()
override;
5988 void InitialPropagate()
override;
5989 std::string DebugString()
const override;
5990 IntVar* Var()
override {
5991 return solver()->MakeIsLessOrEqualVar(left_, right_);
5994 void Accept(ModelVisitor*
const visitor)
const override {
6005 IntExpr*
const left_;
6006 IntExpr*
const right_;
6010 LightRangeLessOrEqual::LightRangeLessOrEqual(Solver*
const s, IntExpr*
const l,
6012 : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
6014 void LightRangeLessOrEqual::Post() {
6016 solver(),
this, &LightRangeLessOrEqual::CheckRange,
"CheckRange");
6017 left_->WhenRange(demon_);
6018 right_->WhenRange(demon_);
6021 void LightRangeLessOrEqual::InitialPropagate() {
6022 left_->SetMax(right_->Max());
6023 right_->SetMin(left_->Min());
6024 if (left_->Max() <= right_->Min()) {
6029 void LightRangeLessOrEqual::CheckRange() {
6030 if (left_->Min() > right_->Max()) {
6033 if (left_->Max() <= right_->Min()) {
6038 std::string LightRangeLessOrEqual::DebugString()
const {
6039 return left_->DebugString() +
" < " + right_->DebugString();
6044 void RoutingDimension::InitializeCumuls() {
6045 Solver*
const solver = model_->
solver();
6047 const auto capacity_range = std::minmax_element(vehicle_capacities_.begin(),
6048 vehicle_capacities_.end());
6049 const int64 min_capacity = *capacity_range.first;
6051 const int64 max_capacity = *capacity_range.second;
6052 solver->MakeIntVarArray(size, 0, max_capacity, name_, &cumuls_);
6054 for (
int v = 0; v < model_->
vehicles(); v++) {
6055 const int64 vehicle_capacity = vehicle_capacities_[v];
6056 cumuls_[model_->
Start(v)]->SetMax(vehicle_capacity);
6057 cumuls_[model_->
End(v)]->SetMax(vehicle_capacity);
6060 forbidden_intervals_.resize(size);
6061 capacity_vars_.clear();
6062 if (min_capacity != max_capacity) {
6063 solver->MakeIntVarArray(size, 0,
kint64max, &capacity_vars_);
6064 for (
int i = 0; i < size; ++i) {
6065 IntVar*
const capacity_var = capacity_vars_[i];
6066 if (i < model_->Size()) {
6067 IntVar*
const capacity_active = solver->MakeBoolVar();
6068 solver->AddConstraint(
6069 solver->MakeLessOrEqual(model_->
ActiveVar(i), capacity_active));
6070 solver->AddConstraint(solver->MakeIsLessOrEqualCt(
6071 cumuls_[i], capacity_var, capacity_active));
6073 solver->AddConstraint(
6074 solver->MakeLessOrEqual(cumuls_[i], capacity_var));
6081 template <
int64 value>
6086 void ComputeTransitClasses(
const std::vector<int>& evaluator_indices,
6087 std::vector<int>* class_evaluators,
6088 std::vector<int64>* vehicle_to_class) {
6089 CHECK(class_evaluators !=
nullptr);
6090 CHECK(vehicle_to_class !=
nullptr);
6091 class_evaluators->clear();
6092 vehicle_to_class->resize(evaluator_indices.size(), -1);
6093 absl::flat_hash_map<int, int64> evaluator_to_class;
6094 for (
int i = 0; i < evaluator_indices.size(); ++i) {
6095 const int evaluator_index = evaluator_indices[i];
6096 int evaluator_class = -1;
6097 if (!
gtl::FindCopy(evaluator_to_class, evaluator_index, &evaluator_class)) {
6098 evaluator_class = class_evaluators->size();
6099 evaluator_to_class[evaluator_index] = evaluator_class;
6100 class_evaluators->push_back(evaluator_index);
6102 (*vehicle_to_class)[i] = evaluator_class;
6107 void RoutingDimension::InitializeTransitVariables(
int64 slack_max) {
6108 CHECK(!class_evaluators_.empty());
6109 CHECK(base_dimension_ ==
nullptr ||
6110 !state_dependent_class_evaluators_.empty());
6112 Solver*
const solver = model_->
solver();
6113 const int size = model_->
Size();
6116 return (0 <=
index &&
index < state_dependent_vehicle_to_class_.size())
6117 ? state_dependent_vehicle_to_class_[
index]
6118 : state_dependent_class_evaluators_.size();
6120 const std::string slack_name = name_ +
" slack";
6121 const std::string transit_name = name_ +
" fixed transit";
6123 for (
int64 i = 0; i < size; ++i) {
6124 fixed_transits_[i] =
6127 if (base_dimension_ !=
nullptr) {
6128 if (state_dependent_class_evaluators_.size() == 1) {
6129 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6130 for (
int64 j = 0; j < cumuls_.size(); ++j) {
6131 transition_variables[j] =
6132 MakeRangeMakeElementExpr(
6134 ->StateDependentTransitCallback(
6135 state_dependent_class_evaluators_[0])(i, j)
6137 base_dimension_->
CumulVar(i), solver)
6140 dependent_transits_[i] =
6141 solver->MakeElement(transition_variables, model_->
NextVar(i))
6144 IntVar*
const vehicle_class_var =
6146 ->MakeElement(dependent_vehicle_class_function,
6149 std::vector<IntVar*> transit_for_vehicle;
6150 transit_for_vehicle.reserve(state_dependent_class_evaluators_.size() +
6152 for (
int evaluator : state_dependent_class_evaluators_) {
6153 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6154 for (
int64 j = 0; j < cumuls_.size(); ++j) {
6155 transition_variables[j] =
6156 MakeRangeMakeElementExpr(
6159 base_dimension_->
CumulVar(i), solver)
6162 transit_for_vehicle.push_back(
6163 solver->MakeElement(transition_variables, model_->
NextVar(i))
6166 transit_for_vehicle.push_back(solver->MakeIntConst(0));
6167 dependent_transits_[i] =
6168 solver->MakeElement(transit_for_vehicle, vehicle_class_var)->Var();
6171 dependent_transits_[i] = solver->MakeIntConst(0);
6175 IntExpr* transit_expr = fixed_transits_[i];
6176 if (dependent_transits_[i]->Min() != 0 ||
6177 dependent_transits_[i]->Max() != 0) {
6178 transit_expr = solver->MakeSum(transit_expr, dependent_transits_[i]);
6181 if (slack_max == 0) {
6182 slacks_[i] = solver->MakeIntConst(0);
6185 solver->MakeIntVar(0, slack_max, absl::StrCat(slack_name, i));
6186 transit_expr = solver->MakeSum(slacks_[i], transit_expr);
6188 transits_[i] = transit_expr->Var();
6192 void RoutingDimension::InitializeTransits(
6193 const std::vector<int>& transit_evaluators,
6194 const std::vector<int>& state_dependent_transit_evaluators,
6197 CHECK(base_dimension_ ==
nullptr ||
6198 model_->
vehicles() == state_dependent_transit_evaluators.size());
6199 const int size = model_->
Size();
6200 transits_.resize(size,
nullptr);
6201 fixed_transits_.resize(size,
nullptr);
6202 slacks_.resize(size,
nullptr);
6203 dependent_transits_.resize(size,
nullptr);
6204 ComputeTransitClasses(transit_evaluators, &class_evaluators_,
6205 &vehicle_to_class_);
6206 if (base_dimension_ !=
nullptr) {
6207 ComputeTransitClasses(state_dependent_transit_evaluators,
6208 &state_dependent_class_evaluators_,
6209 &state_dependent_vehicle_to_class_);
6212 InitializeTransitVariables(slack_max);
6217 std::vector<int64>* values) {
6218 const int num_nodes = path.size();
6219 values->resize(num_nodes - 1);
6220 for (
int i = 0; i < num_nodes - 1; ++i) {
6221 (*values)[i] = evaluator(path[i], path[i + 1]);
6226 : model_(
model), occurrences_of_type_(
model.GetNumberOfVisitTypes()) {}
6229 int vehicle,
const std::function<
int64(
int64)>& next_accessor) {
6236 for (
int pos = 0; pos < current_route_visits_.size(); pos++) {
6237 const int64 current_visit = current_route_visits_[pos];
6244 DCHECK_LT(type, occurrences_of_type_.size());
6245 int& num_type_added = occurrences_of_type_[type].num_type_added_to_vehicle;
6246 int& num_type_removed =
6247 occurrences_of_type_[type].num_type_removed_from_vehicle;
6248 DCHECK_LE(num_type_removed, num_type_added);
6250 num_type_removed == num_type_added) {
6260 if (policy == VisitTypePolicy::TYPE_ADDED_TO_VEHICLE ||
6261 policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED) {
6264 if (policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED ||
6265 policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
6273 int vehicle,
const std::function<
int64(
int64)>& next_accessor) {
6276 std::fill(occurrences_of_type_.begin(), occurrences_of_type_.end(),
6282 current_route_visits_.clear();
6284 current = next_accessor(current)) {
6287 VisitTypePolicy::TYPE_ON_VEHICLE_UP_TO_VISIT) {
6288 occurrences_of_type_[type].position_of_last_type_on_vehicle_up_to_visit =
6289 current_route_visits_.size();
6291 current_route_visits_.push_back(current);
6313 check_hard_incompatibilities_(check_hard_incompatibilities) {}
6315 bool TypeIncompatibilityChecker::HasRegulationsToCheck()
const {
6317 (check_hard_incompatibilities_ &&
6326 bool TypeIncompatibilityChecker::CheckTypeRegulations(
int type,
6327 VisitTypePolicy policy,
6329 if (policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
6334 for (
int incompatible_type :
6340 if (check_hard_incompatibilities_) {
6341 for (
int incompatible_type :
6351 bool TypeRequirementChecker::HasRegulationsToCheck()
const {
6356 bool TypeRequirementChecker::CheckRequiredTypesCurrentlyOnRoute(
6357 const std::vector<absl::flat_hash_set<int>>& required_type_alternatives,
6359 for (
const absl::flat_hash_set<int>& requirement_alternatives :
6360 required_type_alternatives) {
6361 bool has_one_of_alternatives =
false;
6362 for (
int type_alternative : requirement_alternatives) {
6364 has_one_of_alternatives =
true;
6368 if (!has_one_of_alternatives) {
6375 bool TypeRequirementChecker::CheckTypeRegulations(
int type,
6376 VisitTypePolicy policy,
6380 if (!CheckRequiredTypesCurrentlyOnRoute(
6386 if (!CheckRequiredTypesCurrentlyOnRoute(
6393 types_with_same_vehicle_requirements_on_route_.insert(type);
6398 bool TypeRequirementChecker::FinalizeCheck()
const {
6399 for (
int type : types_with_same_vehicle_requirements_on_route_) {
6400 for (
const absl::flat_hash_set<int>& requirement_alternatives :
6402 bool has_one_of_alternatives =
false;
6403 for (
const int type_alternative : requirement_alternatives) {
6405 has_one_of_alternatives =
true;
6409 if (!has_one_of_alternatives) {
6420 incompatibility_checker_(
model, true),
6421 requirement_checker_(
model),
6422 vehicle_demons_(
model.vehicles()) {}
6424 void TypeRegulationsConstraint::PropagateNodeRegulations(
int node) {
6431 if (vehicle < 0)
return;
6432 DCHECK(vehicle_demons_[vehicle] !=
nullptr);
6436 void TypeRegulationsConstraint::CheckRegulationsOnVehicle(
int vehicle) {
6437 const auto next_accessor = [
this, vehicle](
int64 node) {
6442 return model_.
End(vehicle);
6444 if (!incompatibility_checker_.
CheckVehicle(vehicle, next_accessor) ||
6445 !requirement_checker_.
CheckVehicle(vehicle, next_accessor)) {
6451 for (
int vehicle = 0; vehicle < model_.
vehicles(); vehicle++) {
6453 solver(),
this, &TypeRegulationsConstraint::CheckRegulationsOnVehicle,
6454 "CheckRegulationsOnVehicle", vehicle);
6456 for (
int node = 0; node < model_.
Size(); node++) {
6458 solver(),
this, &TypeRegulationsConstraint::PropagateNodeRegulations,
6459 "PropagateNodeRegulations", node);
6466 for (
int vehicle = 0; vehicle < model_.
vehicles(); vehicle++) {
6467 CheckRegulationsOnVehicle(vehicle);
6471 void RoutingDimension::CloseModel(
bool use_light_propagation) {
6473 const auto capacity_lambda = [
this](
int64 vehicle) {
6474 return vehicle >= 0 ? vehicle_capacities_[vehicle] :
kint64max;
6476 for (
int i = 0; i < capacity_vars_.size(); ++i) {
6477 IntVar*
const vehicle_var = model_->
VehicleVar(i);
6478 IntVar*
const capacity_var = capacity_vars_[i];
6479 if (use_light_propagation) {
6481 solver, capacity_var, vehicle_var, capacity_lambda,
6482 [
this]() {
return model_->enable_deep_serialization_; }));
6490 return IthElementOrValue<-1>(vehicle_to_class_,
index);
6492 for (
int i = 0; i < fixed_transits_.size(); ++i) {
6493 IntVar*
const next_var = model_->
NextVar(i);
6494 IntVar*
const fixed_transit = fixed_transits_[i];
6495 const auto transit_vehicle_evaluator = [
this, i](
int64 to,
6499 if (use_light_propagation) {
6500 if (class_evaluators_.size() == 1) {
6501 const int class_evaluator_index = class_evaluators_[0];
6502 const auto& unary_callback =
6504 if (unary_callback ==
nullptr) {
6506 solver, fixed_transit, next_var,
6507 [
this, i](
int64 to) {
6510 [
this]() {
return model_->enable_deep_serialization_; }));
6512 fixed_transit->SetValue(unary_callback(i));
6516 solver, fixed_transit, next_var, model_->
VehicleVar(i),
6517 transit_vehicle_evaluator,
6518 [
this]() {
return model_->enable_deep_serialization_; }));
6521 if (class_evaluators_.size() == 1) {
6522 const int class_evaluator_index = class_evaluators_[0];
6523 const auto& unary_callback =
6525 if (unary_callback ==
nullptr) {
6527 fixed_transit, solver
6529 [
this, i](
int64 to) {
6531 class_evaluators_[0])(i, to);
6536 fixed_transit->SetValue(unary_callback(i));
6539 IntVar*
const vehicle_class_var =
6543 fixed_transit, solver
6545 next_var, vehicle_class_var)
6551 GlobalVehicleBreaksConstraint* constraint =
6558 int64 vehicle)
const {
6574 if (next_start >
max)
break;
6575 if (next_start < interval->start) {
6580 if (next_start <=
max) {
6589 CHECK_LT(vehicle, vehicle_span_upper_bounds_.size());
6591 vehicle_span_upper_bounds_[vehicle] = upper_bound;
6597 CHECK_LT(vehicle, vehicle_span_cost_coefficients_.size());
6599 vehicle_span_cost_coefficients_[vehicle] =
coefficient;
6614 if (!
cost.IsNonDecreasing()) {
6615 LOG(
WARNING) <<
"Only non-decreasing cost functions are supported.";
6618 if (
cost.Value(0) < 0) {
6619 LOG(
WARNING) <<
"Only positive cost functions are supported.";
6622 if (
index >= cumul_var_piecewise_linear_cost_.size()) {
6623 cumul_var_piecewise_linear_cost_.resize(
index + 1);
6625 PiecewiseLinearCost& piecewise_linear_cost =
6626 cumul_var_piecewise_linear_cost_[
index];
6627 piecewise_linear_cost.var = cumuls_[
index];
6628 piecewise_linear_cost.cost = absl::make_unique<PiecewiseLinearFunction>(
cost);
6632 return (
index < cumul_var_piecewise_linear_cost_.size() &&
6633 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr);
6638 if (
index < cumul_var_piecewise_linear_cost_.size() &&
6639 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr) {
6640 return cumul_var_piecewise_linear_cost_[
index].cost.get();
6650 const int vehicle =
model->VehicleIndex(
index);
6652 return solver->
MakeProd(expr,
model->VehicleCostsConsideredVar(vehicle))
6659 void RoutingDimension::SetupCumulVarPiecewiseLinearCosts(
6660 std::vector<IntVar*>* cost_elements)
const {
6661 CHECK(cost_elements !=
nullptr);
6662 Solver*
const solver = model_->
solver();
6663 for (
int i = 0; i < cumul_var_piecewise_linear_cost_.size(); ++i) {
6664 const PiecewiseLinearCost& piecewise_linear_cost =
6665 cumul_var_piecewise_linear_cost_[i];
6666 if (piecewise_linear_cost.var !=
nullptr) {
6667 IntExpr*
const expr = solver->MakePiecewiseLinearExpr(
6668 piecewise_linear_cost.var, *piecewise_linear_cost.cost);
6669 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
6670 cost_elements->push_back(cost_var);
6680 if (
index >= cumul_var_soft_upper_bound_.size()) {
6681 cumul_var_soft_upper_bound_.resize(
index + 1, {
nullptr, 0, 0});
6683 cumul_var_soft_upper_bound_[
index] = {cumuls_[
index], upper_bound,
6688 return (
index < cumul_var_soft_upper_bound_.size() &&
6689 cumul_var_soft_upper_bound_[
index].var !=
nullptr);
6693 if (
index < cumul_var_soft_upper_bound_.size() &&
6694 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
6695 return cumul_var_soft_upper_bound_[
index].bound;
6697 return cumuls_[
index]->Max();
6702 if (
index < cumul_var_soft_upper_bound_.size() &&
6703 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
6704 return cumul_var_soft_upper_bound_[
index].coefficient;
6709 void RoutingDimension::SetupCumulVarSoftUpperBoundCosts(
6710 std::vector<IntVar*>* cost_elements)
const {
6711 CHECK(cost_elements !=
nullptr);
6713 for (
int i = 0; i < cumul_var_soft_upper_bound_.size(); ++i) {
6714 const SoftBound& soft_bound = cumul_var_soft_upper_bound_[i];
6715 if (soft_bound.var !=
nullptr) {
6717 solver->
MakeSum(soft_bound.var, -soft_bound.bound), 0,
6718 soft_bound.coefficient);
6719 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
6720 cost_elements->push_back(cost_var);
6724 soft_bound.coefficient);
6731 if (
index >= cumul_var_soft_lower_bound_.size()) {
6732 cumul_var_soft_lower_bound_.resize(
index + 1, {
nullptr, 0, 0});
6734 cumul_var_soft_lower_bound_[
index] = {cumuls_[
index], lower_bound,
6739 return (
index < cumul_var_soft_lower_bound_.size() &&
6740 cumul_var_soft_lower_bound_[
index].var !=
nullptr);
6744 if (
index < cumul_var_soft_lower_bound_.size() &&
6745 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
6746 return cumul_var_soft_lower_bound_[
index].bound;
6748 return cumuls_[
index]->Min();
6753 if (
index < cumul_var_soft_lower_bound_.size() &&
6754 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
6755 return cumul_var_soft_lower_bound_[
index].coefficient;
6760 void RoutingDimension::SetupCumulVarSoftLowerBoundCosts(
6761 std::vector<IntVar*>* cost_elements)
const {
6762 CHECK(cost_elements !=
nullptr);
6764 for (
int i = 0; i < cumul_var_soft_lower_bound_.size(); ++i) {
6765 const SoftBound& soft_bound = cumul_var_soft_lower_bound_[i];
6766 if (soft_bound.var !=
nullptr) {
6769 soft_bound.coefficient);
6770 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
6771 cost_elements->push_back(cost_var);
6775 soft_bound.coefficient);
6780 void RoutingDimension::SetupGlobalSpanCost(
6781 std::vector<IntVar*>* cost_elements)
const {
6782 CHECK(cost_elements !=
nullptr);
6783 Solver*
const solver = model_->
solver();
6784 if (global_span_cost_coefficient_ != 0) {
6785 std::vector<IntVar*> end_cumuls;
6786 for (
int i = 0; i < model_->
vehicles(); ++i) {
6787 end_cumuls.push_back(solver
6788 ->MakeProd(model_->vehicle_costs_considered_[i],
6789 cumuls_[model_->
End(i)])
6792 IntVar*
const max_end_cumul = solver->
MakeMax(end_cumuls)->
Var();
6794 max_end_cumul, global_span_cost_coefficient_);
6795 std::vector<IntVar*> start_cumuls;
6796 for (
int i = 0; i < model_->
vehicles(); ++i) {
6797 IntVar* global_span_cost_start_cumul = solver->MakeIntVar(0,
kint64max);
6798 solver->AddConstraint(solver->MakeIfThenElseCt(
6799 model_->vehicle_costs_considered_[i], cumuls_[model_->
Start(i)],
6800 max_end_cumul, global_span_cost_start_cumul));
6801 start_cumuls.push_back(global_span_cost_start_cumul);
6803 IntVar*
const min_start_cumul = solver->MakeMin(start_cumuls)->Var();
6805 min_start_cumul, global_span_cost_coefficient_);
6810 for (
int var_index = 0; var_index < model_->
Size(); ++var_index) {
6812 slacks_[var_index], global_span_cost_coefficient_);
6813 cost_elements->push_back(
6816 model_->vehicle_costs_considered_[0],
6819 solver->MakeSum(transits_[var_index],
6820 dependent_transits_[var_index]),
6821 global_span_cost_coefficient_),
6826 IntVar*
const end_range =
6827 solver->MakeDifference(max_end_cumul, min_start_cumul)->Var();
6828 end_range->SetMin(0);
6829 cost_elements->push_back(
6830 solver->MakeProd(end_range, global_span_cost_coefficient_)->Var());
6836 std::vector<IntervalVar*> breaks,
int vehicle,
6837 std::vector<int64> node_visit_transits) {
6838 if (breaks.empty())
return;
6840 [node_visit_transits = std::move(node_visit_transits)](
int64 from,
int64 to) {
6841 return node_visit_transits[from];
6847 std::vector<IntervalVar*> breaks,
int vehicle,
6848 std::vector<int64> node_visit_transits,
6850 if (breaks.empty())
return;
6852 [node_visit_transits](
int64 from,
int64 to) {
6853 return node_visit_transits[from];
6855 const int delay_evaluator =
6862 std::vector<IntervalVar*> breaks,
int vehicle,
int pre_travel_evaluator,
6863 int post_travel_evaluator) {
6866 if (breaks.empty())
return;
6868 vehicle_break_intervals_[vehicle] = std::move(breaks);
6869 vehicle_pre_travel_evaluators_[vehicle] = pre_travel_evaluator;
6870 vehicle_post_travel_evaluators_[vehicle] = post_travel_evaluator;
6891 DCHECK(!break_constraints_are_initialized_);
6892 const int num_vehicles = model_->
vehicles();
6893 vehicle_break_intervals_.resize(num_vehicles);
6894 vehicle_pre_travel_evaluators_.resize(num_vehicles, -1);
6895 vehicle_post_travel_evaluators_.resize(num_vehicles, -1);
6896 vehicle_break_distance_duration_.resize(num_vehicles);
6897 break_constraints_are_initialized_ =
true;
6901 return break_constraints_are_initialized_;
6905 int vehicle)
const {
6907 DCHECK_LT(vehicle, vehicle_break_intervals_.size());
6908 return vehicle_break_intervals_[vehicle];
6913 DCHECK_LT(vehicle, vehicle_pre_travel_evaluators_.size());
6914 return vehicle_pre_travel_evaluators_[vehicle];
6919 DCHECK_LT(vehicle, vehicle_post_travel_evaluators_.size());
6920 return vehicle_post_travel_evaluators_[vehicle];
6929 vehicle_break_distance_duration_[vehicle].emplace_back(distance, duration);
6938 const std::vector<std::pair<int64, int64>>&
6941 DCHECK_LT(vehicle, vehicle_break_distance_duration_.size());
6942 return vehicle_break_distance_duration_[vehicle];
6948 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
6949 pickup_to_delivery_limits_per_pair_index_.resize(pair_index + 1);
6951 pickup_to_delivery_limits_per_pair_index_[pair_index] =
6952 std::move(limit_function);
6956 return !pickup_to_delivery_limits_per_pair_index_.empty();
6961 int delivery)
const {
6964 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
6968 pickup_to_delivery_limits_per_pair_index_[pair_index];
6969 if (!pickup_to_delivery_limit_function) {
6975 return pickup_to_delivery_limit_function(pickup, delivery);
6978 void RoutingDimension::SetupSlackAndDependentTransitCosts()
const {
6979 if (model_->
vehicles() == 0)
return;
6981 bool all_vehicle_span_costs_are_equal =
true;
6982 for (
int i = 1; i < model_->
vehicles(); ++i) {
6983 all_vehicle_span_costs_are_equal &= vehicle_span_cost_coefficients_[i] ==
6984 vehicle_span_cost_coefficients_[0];
6987 if (all_vehicle_span_costs_are_equal &&
6988 vehicle_span_cost_coefficients_[0] == 0) {
7000 std::vector<const RoutingDimension*> dimensions_with_relevant_slacks = {
this};
7002 const RoutingDimension*
next =
7003 dimensions_with_relevant_slacks.back()->base_dimension_;
7004 if (
next ==
nullptr ||
next == dimensions_with_relevant_slacks.back()) {
7007 dimensions_with_relevant_slacks.push_back(
next);
7010 for (
auto it = dimensions_with_relevant_slacks.rbegin();
7011 it != dimensions_with_relevant_slacks.rend(); ++it) {
7012 for (
int i = 0; i < model_->
vehicles(); ++i) {
7018 for (IntVar*
const slack : (*it)->slacks_) {
#define DCHECK_LE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define CHECK_NE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
void resize(size_type new_size)
void push_back(const value_type &x)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
int64 Value(const IntVar *const var) const
bool Load(const std::string &filename)
Loads an assignment from a file; does not add variables to the assignment (only the variables contain...
int64 Min(const IntVar *const var) const
bool Contains(const IntVar *const var) const
bool Save(const std::string &filename) const
Saves the assignment to a file.
void AddObjective(IntVar *const v)
int64 ObjectiveValue() const
int64 Max(const IntVar *const var) const
void CopyIntersection(const Assignment *assignment)
Copies the intersection of the two assignments to the current assignment.
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
IntVarElement * Add(IntVar *const var)
bool Bound(const IntVar *const var) const
This is the base class for all expressions that are not variables.
A constraint is the main modeling object.
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
A Demon is the base element of a propagation queue.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
The class IntExpr is the base of all integer expressions in constraint programming.
virtual IntVar * Var()=0
Creates a variable from the expression.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64 Max() const =0
virtual int64 Min() const =0
Decision builder building a solution using heuristics with local search filters to evaluate its feasi...
int64 number_of_rejects() const
int64 number_of_decisions() const
Returns statistics from its underlying heuristic.
The class IntVar is a subset of IntExpr.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
virtual uint64 Size() const =0
This method returns the number of values in the domain of the variable.
Interval variables are often used in scheduling.
CostValue GetCost() const
void SetArcCost(ArcIndex arc, CostValue cost)
The base class for all local search operators.
static int64 FastInt64Round(double x)
static const char kIndex2Argument[]
static const char kMinArgument[]
static const char kTargetArgument[]
static const char kMaxArgument[]
static const char kLessOrEqual[]
static const char kLeftArgument[]
static const char kVarsArgument[]
static const char kRightArgument[]
static const char kValuesArgument[]
static const char kIndexArgument[]
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
void set_name(const std::string &name)
Usual limit based on wall_time, number of explored branches and number of failures in the search tree...
void UpdateLimits(absl::Duration time, int64 branches, int64 failures, int64 solutions)
void Switch(Solver *const solver)
RouteConstructor(Assignment *const assignment, RoutingModel *const model, bool check_assignment, int64 num_indices, const std::vector< Link > &links_list)
const std::vector< std::vector< int > > & final_routes() const
Dimensions represent quantities accumulated at nodes along the routes.
void SetCumulVarPiecewiseLinearCost(int64 index, const PiecewiseLinearFunction &cost)
Sets a piecewise linear cost on the cumul variable of a given variable index.
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
RoutingModel * model() const
Returns the model on which the dimension was created.
void SetSpanUpperBoundForVehicle(int64 upper_bound, int vehicle)
!defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON)
bool HasPickupToDeliveryLimits() const
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
int64 GetCumulVarSoftLowerBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
bool HasCumulVarSoftLowerBound(int64 index) const
Returns true if a soft lower bound has been set for a given variable index.
void SetSpanCostCoefficientForAllVehicles(int64 coefficient)
int64 GetCumulVarSoftLowerBound(int64 index) const
Returns the soft lower bound of a cumul variable for a given variable index.
std::function< int64(int, int)> PickupToDeliveryLimitFunction
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery a...
void SetBreakDistanceDurationOfVehicle(int64 distance, int64 duration, int vehicle)
With breaks supposed to be consecutive, this forces the distance between breaks of size at least mini...
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
void InitializeBreaks()
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_tr...
int64 GetTransitValue(int64 from_index, int64 to_index, int64 vehicle) const
Returns the transition value for a given pair of nodes (as var index); this value is the one taken by...
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
void SetPickupToDeliveryLimitFunctionForPair(PickupToDeliveryLimitFunction limit_function, int pair_index)
int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup, int delivery) const
void SetSpanCostCoefficientForVehicle(int64 coefficient, int vehicle)
Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once.
int64 GetCumulVarSoftUpperBound(int64 index) const
Returns the soft upper bound of a cumul variable for a given variable index.
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
void SetCumulVarSoftUpperBound(int64 index, int64 upper_bound, int64 coefficient)
Sets a soft upper bound to the cumul variable of a given variable index.
const PiecewiseLinearFunction * GetCumulVarPiecewiseLinearCost(int64 index) const
Returns the piecewise linear cost of a cumul variable for a given variable index.
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64 index, int64 min_value, int64 max_value) const
Returns allowed intervals for a given node in a given interval.
const std::string & name() const
Returns the name of the dimension.
void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound, int64 coefficient)
Sets a soft lower bound to the cumul variable of a given variable index.
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator)
Sets the breaks for a given vehicle.
bool HasCumulVarPiecewiseLinearCost(int64 index) const
Returns true if a piecewise linear cost has been set for a given variable index.
void SetGlobalSpanCostCoefficient(int64 coefficient)
Sets a cost proportional to the global dimension span, that is the difference between the largest val...
bool HasCumulVarSoftUpperBound(int64 index) const
Returns true if a soft upper bound has been set for a given variable index.
int64 GetCumulVarSoftUpperBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
Manager for any NodeIndex <-> variable index conversion.
std::vector< NodeIndex > GetIndexToNodeMap() const
int64 GetEndIndex(int vehicle) const
int num_unique_depots() const
complete.
NodeIndex IndexToNode(int64 index) const
int64 GetStartIndex(int vehicle) const
friend class RoutingModelInspector
bool AddDimensionWithVehicleTransitAndCapacity(const std::vector< int > &evaluator_indices, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int64 GetNumberOfDecisionsInFirstSolution(const RoutingSearchParameters &search_parameters) const
Returns statistics on first solution search, number of decisions sent to filters, number of decisions...
void SetFixedCostOfAllVehicles(int64 cost)
Sets the fixed cost of all vehicle routes.
void AddAtSolutionCallback(std::function< void()> callback)
Adds a callback called each time a solution is found during the search.
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
std::pair< int, bool > AddConstantDimensionWithSlack(int64 value, int64 capacity, int64 slack_max, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'value'; 'capacity' is t...
Assignment * RestoreAssignment(const Assignment &solution)
Restores an assignment as a solution in the routing model and returns the new solution.
std::function< std::vector< operations_research::IntVar * >(RoutingModel *)> GetTabuVarsCallback
Sets the callback returning the variable to use for the Tabu Search metaheuristic.
void AddSearchMonitor(SearchMonitor *const monitor)
Adds a search monitor to the search used to solve the routing model.
int nodes() const
Sizes and indices Returns the number of nodes in the model.
bool ArcIsMoreConstrainedThanArc(int64 from, int64 to1, int64 to2)
Returns whether the arc from->to1 is more constrained than from->to2, taking into account,...
void AddLocalSearchOperator(LocalSearchOperator *ls_operator)
Adds a local search operator to the set of operators used to solve the vehicle routing problem.
Assignment * ReadAssignmentFromRoutes(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices)
Restores the routes as the current solution.
void AddVariableTargetToFinalizer(IntVar *var, int64 target)
Add a variable to set the closest possible to the target value in the solution finalizer.
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
const std::vector< int > & GetPairIndicesOfType(int type) const
RoutingTransitCallback1 TransitCallback1
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType(int type) const
void AddPickupAndDelivery(int64 pickup, int64 delivery)
Notifies that index1 and index2 form a pair of nodes which should belong to the same route.
std::string DebugOutputAssignment(const Assignment &solution_assignment, const std::string &dimension_to_print) const
Print some debugging information about an assignment, including the feasible intervals of the CumulVa...
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType(int type) const
Returns the set of requirement alternatives when removing the given type.
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(int vehicle) const
int64 Size() const
Returns the number of next variables in the model.
int64 UnperformedPenalty(int64 var_index) const
Get the "unperformed" penalty of a node.
void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy)
Sets the Pickup and delivery policy of all vehicles.
Assignment * ReadAssignment(const std::string &file_name)
Reads an assignment from a file and returns the current solution.
Assignment * CompactAssignment(const Assignment &assignment) const
Returns a compacted version of the given assignment, in which all vehicles with id lower or equal to ...
bool ApplyLocksToAllVehicles(const std::vector< std::vector< int64 >> &locks, bool close_routes)
Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for rout...
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
void AddToAssignment(IntVar *const var)
Adds an extra variable to the vehicle routing assignment.
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
int64 Next(const Assignment &assignment, int64 index) const
Assignment inspection Returns the variable index of the node directly after the node corresponding to...
void AddVariableMinimizedByFinalizer(IntVar *var)
Adds a variable to minimize in the solution finalizer.
VisitTypePolicy
Set the node visit types and incompatibilities/requirements between the types (see below).
@ TYPE_ADDED_TO_VEHICLE
When visited, the number of types 'T' on the vehicle increases by one.
@ ADDED_TYPE_REMOVED_FROM_VEHICLE
When visited, one instance of type 'T' previously added to the route (TYPE_ADDED_TO_VEHICLE),...
@ TYPE_ON_VEHICLE_UP_TO_VISIT
With the following policy, the visit enforces that type 'T' is considered on the route from its start...
@ TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED
The visit doesn't have an impact on the number of types 'T' on the route, as it's (virtually) added a...
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension with transits depending on the cumuls of another dimension.
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
Creates a cached StateDependentTransit from an std::function.
int64 GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
void SetFixedCostOfVehicle(int64 cost, int vehicle)
Sets the fixed cost of one vehicle route.
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
For every vehicle of the routing model:
friend class RoutingDimension
int64 GetArcCostForVehicle(int64 from_index, int64 to_index, int64 vehicle) const
Returns the cost of the transit arc between two nodes for a given vehicle.
LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer(const RoutingDimension &dimension) const
const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType(int type) const
Returns the set of same-vehicle requirement alternatives for the given type.
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
std::vector< std::vector< int64 > > GetRoutesFromAssignment(const Assignment &assignment)
Converts the solution in the given assignment to routes for all vehicles.
bool HasTemporalTypeRequirements() const
Solver * solver() const
Returns the underlying constraint solver.
void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
Same as AddPickupAndDelivery but notifying that the performed node from the disjunction of index 'pic...
RoutingTransitCallback2 TransitCallback2
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
int64 GetArcCostForFirstSolution(int64 from_index, int64 to_index) const
Returns the cost of the arc in the context of the first solution strategy.
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
std::function< StateDependentTransit(int64, int64)> VariableIndexEvaluator2
const Assignment * SolveFromAssignmentWithParameters(const Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
@ ROUTING_SUCCESS
Problem solved successfully after calling RoutingModel::Solve().
@ ROUTING_FAIL
No solution found to the problem after calling RoutingModel::Solve().
@ ROUTING_INVALID
Model, model parameters or flags are not valid.
@ ROUTING_FAIL_TIMEOUT
Time limit reached before finding a solution with RoutingModel::Solve().
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
void AddTemporalTypeIncompatibility(int type1, int type2)
std::vector< std::pair< int64, int64 > > GetPerfectBinaryDisjunctions() const
Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "...
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
const std::vector< int > & GetSingleNodesOfType(int type) const
void SetVisitType(int64 index, int type, VisitTypePolicy type_policy)
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType(int type) const
Returns the set of requirement alternatives when adding the given type.
bool RoutesToAssignment(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices, bool close_routes, Assignment *const assignment) const
Fills an assignment from a specification of the routes of the vehicles.
void AddHardTypeIncompatibility(int type1, int type2)
Incompatibilities: Two nodes with "hard" incompatible types cannot share the same route at all,...
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback)
void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback)
void CloseVisitTypes()
This function should be called once all node visit types have been set and prior to adding any incomp...
std::pair< int, bool > AddVectorDimension(std::vector< int64 > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i]' for node i; ...
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
void IgnoreDisjunctionsAlreadyForcedToZero()
SPECIAL: Makes the solver ignore all the disjunctions whose active variables are all trivially zero (...
void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy, int vehicle)
const Assignment * SolveWithParameters(const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
Solves the current routing model with the given parameters.
int RegisterTransitCallback(TransitCallback2 callback)
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
const Assignment * PackCumulsOfOptimizerDimensionsFromAssignment(const Assignment *original_assignment, absl::Duration duration_limit)
For every dimension in the model with an optimizer in local/global_dimension_optimizers_,...
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
void AddWeightedVariableMinimizedByFinalizer(IntVar *var, int64 cost)
Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more ...
int GetVisitType(int64 index) const
RoutingDimensionIndex DimensionIndex
void AssignmentToRoutes(const Assignment &assignment, std::vector< std::vector< int64 >> *const routes) const
Converts the solution in the given assignment to routes for all vehicles.
std::pair< int, bool > AddMatrixDimension(std::vector< std::vector< int64 > > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i][next(i)]' for...
IntVar * ApplyLocks(const std::vector< int64 > &locks)
Applies a lock chain to the next search.
DisjunctionIndex AddDisjunction(const std::vector< int64 > &indices, int64 penalty=kNoPenalty, int64 max_cardinality=1)
Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active.
Assignment * CompactAndCheckAssignment(const Assignment &assignment) const
Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not ...
void AddSoftSameVehicleConstraint(const std::vector< int64 > &indices, int64 cost)
Adds a soft constraint to force a set of variable indices to be on the same vehicle.
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
bool HasHardTypeIncompatibilities() const
Returns true iff any hard (resp.
void AddRequiredTypeAlternativesWhenRemovingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
The following requirements apply when visiting dependent nodes that remove their type from the route,...
std::vector< std::vector< std::pair< int64, int64 > > > GetCumulBounds(const Assignment &solution_assignment, const RoutingDimension &dimension)
Returns a vector cumul_bounds, for which cumul_bounds[i][j] is a pair containing the minimum and maxi...
int64 GetHomogeneousCost(int64 from_index, int64 to_index) const
Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns t...
int RegisterPositiveTransitCallback(TransitCallback2 callback)
PickupAndDeliveryPolicy
Types of precedence policy applied to pickup and delivery pairs.
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
void CloseModelWithParameters(const RoutingSearchParameters &search_parameters)
Same as above taking search parameters (as of 10/2015 some the parameters have to be set when closing...
int vehicles() const
Returns the number of vehicle routes in the model.
void AddVariableMaximizedByFinalizer(IntVar *var)
Adds a variable to maximize in the solution finalizer (see above for information on the solution fina...
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
bool HasTypeRegulations() const
Returns true iff the model has any incompatibilities or requirements set on node types.
RoutingVehicleClassIndex VehicleClassIndex
int RegisterUnaryTransitVector(std::vector< int64 > values)
Registers 'callback' and returns its index.
bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
void AddIntervalToAssignment(IntervalVar *const interval)
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
Sets the cost function of the model such that the cost of a segment of a route between node 'from' an...
void SetAmortizedCostFactorsOfAllVehicles(int64 linear_cost_factor, int64 quadratic_cost_factor)
The following methods set the linear and quadratic cost factors of vehicles (must be positive values)...
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
bool HasSameVehicleTypeRequirements() const
Returns true iff any same-route (resp.
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
void SetAssignmentFromOtherModelAssignment(Assignment *target_assignment, const RoutingModel *source_model, const Assignment *source_assignment)
Given a "source_model" and its "source_assignment", resets "target_assignment" with the IntVar variab...
void AddSameVehicleRequiredTypeAlternatives(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
Requirements: NOTE: As of 2019-04, cycles in the requirement graph are not supported,...
const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType(int type) const
Returns visit types incompatible with a given type.
int RegisterTransitMatrix(std::vector< std::vector< int64 > > values)
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int RegisterUnaryTransitCallback(TransitCallback1 callback)
int64 Start(int vehicle) const
Model inspection.
int64 GetDepot() const
Returns the variable index of the first starting or ending node of all routes.
bool WriteAssignment(const std::string &file_name) const
Writes the current solution to a file containing an AssignmentProto.
RoutingCostClassIndex CostClassIndex
bool HasTemporalTypeIncompatibilities() const
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
const TransitCallback2 & TransitCallback(int callback_index) const
int GetNumOfSingletonNodes() const
Returns the number of non-start/end nodes which do not appear in a pickup/delivery pair.
void AddRequiredTypeAlternativesWhenAddingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
If type_D depends on type_R when adding type_D, any node_D of type_D and VisitTypePolicy TYPE_ADDED_T...
void CloseModel()
Closes the current routing model; after this method is called, no modification to the model can be do...
static const DimensionIndex kNoDimension
Constant used to express the "no dimension" index, returned when a dimension name does not correspond...
bool CostsAreHomogeneousAcrossVehicles() const
Whether costs are homogeneous across all vehicles.
void SetAmortizedCostFactorsOfVehicle(int64 linear_cost_factor, int64 quadratic_cost_factor, int vehicle)
Sets the linear and quadratic cost factor of the given vehicle.
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
const Assignment * Solve(const Assignment *assignment=nullptr)
Solves the current routing model; closes the current model.
static const DisjunctionIndex kNoDisjunction
Constant used to express the "no disjunction" index, returned when a node does not appear in any disj...
void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle)
Sets the cost function for a given vehicle route.
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
int64 UnperformedPenaltyOrValue(int64 default_value, int64 var_index) const
Same as above except that it returns default_value instead of 0 when penalty is not well defined (def...
int64 ComputeLowerBound()
Computes a lower bound to the routing problem solving a linear assignment problem.
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
bool IsVehicleUsed(const Assignment &assignment, int vehicle) const
Returns true if the route of 'vehicle' is non empty in 'assignment'.
int64 GetNumberOfRejectsInFirstSolution(const RoutingSearchParameters &search_parameters) const
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
RoutingDisjunctionIndex DisjunctionIndex
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
IntVar * ActiveVar(int64 index) const
Returns the active variable of the node corresponding to index.
VisitTypePolicy GetVisitTypePolicy(int64 index) const
void SetAllowedVehiclesForIndex(const std::vector< int > &vehicles, int64 index)
Sets the vehicles which can visit a given node.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
RoutingModelInspector(RoutingModel *model)
void EndVisitConstraint(const std::string &type_name, const Constraint *const constraint) override
void EndVisitModel(const std::string &solver_name) override
~RoutingModelInspector() override
void VisitIntegerArrayArgument(const std::string &arg_name, const std::vector< int64 > &values) override
void VisitIntegerExpressionArgument(const std::string &type_name, IntExpr *const expr) override
Visit integer expression argument.
static const char kLightElement2[]
static const char kRemoveValues[]
static const char kLightElement[]
Constraint types.
A search monitor is a simple set of callbacks to monitor all search events.
int solution_count() const
Returns how many solutions were stored during the search.
Assignment * solution(int n) const
Returns the nth solution.
IntExpr * MakeElement(const std::vector< int64 > &values, IntVar *const index)
values[index]
Constraint * MakeEquality(IntExpr *const left, IntExpr *const right)
left == right
std::function< bool(int64, int64, int64)> VariableValueComparator
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
void AddConstraint(Constraint *const c)
Adds the constraint 'c' to the model.
@ FULLPATHLNS
Operator which relaxes one entire path and all inactive nodes, thus defining num_paths neighbors.
@ OROPT
Relocate: OROPT and RELOCATE.
@ PATHLNS
Operator which relaxes two sub-chains of three consecutive arcs each.
@ UNACTIVELNS
Operator which relaxes all inactive nodes and one sub-chain of six consecutive arcs.
@ CHOOSE_STATIC_GLOBAL_BEST
Pairs are compared at the first call of the selector, and results are cached.
IntExpr * MakeMax(const std::vector< IntVar * > &vars)
std::max(vars)
IntExpr * MakeDifference(IntExpr *const left, IntExpr *const right)
left - right
std::function< int64(int64)> IndexEvaluator1
Callback typedefs.
static ConstraintSolverParameters DefaultSolverParameters()
Create a ConstraintSolverParameters proto with all the default values.
T * RevAlloc(T *object)
Registers the given object as being reversible.
@ CHOOSE_FIRST_UNBOUND
Select the first unbound variable.
@ CHOOSE_PATH
Selects the next unbound variable on a path, the path being defined by the variables: var[i] correspo...
std::function< int64(int64, int64)> IndexEvaluator2
IntExpr * MakeSemiContinuousExpr(IntExpr *const expr, int64 fixed_charge, int64 step)
Semi continuous Expression (x <= 0 -> f(x) = 0; x > 0 -> f(x) = ax + b) a >= 0 and b >= 0.
IntExpr * MakeSum(IntExpr *const left, IntExpr *const right)
left + right.
Assignment * MakeAssignment()
This method creates an empty assignment.
IntExpr * MakeProd(IntExpr *const left, IntExpr *const right)
left * right
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
EvaluatorLocalSearchOperators
This enum is used in Solver::MakeOperator associated with an evaluator to specify the neighborhood to...
@ TSPOPT
Sliding TSP operator.
@ LK
Lin-Kernighan local search.
@ LE
Move is accepted when the current objective value <= objective.Max.
This class represents a sorted list of disjoint, closed intervals.
Iterator InsertInterval(int64 start, int64 end)
Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ...
ConstIterator end() const
IntervalSet::iterator Iterator
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
void ArrangeIndices(std::vector< int64 > *indices)
SweepArranger(const std::vector< std::pair< int64, int64 >> &points)
void SetSectors(int sectors)
Decision * Next(Solver *const solver) override
This is the main method of the decision builder class.
SweepBuilder(RoutingModel *const model, bool check_assignment)
TypeIncompatibilityChecker(const RoutingModel &model, bool check_hard_incompatibilities)
virtual bool HasRegulationsToCheck() const =0
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
bool CheckVehicle(int vehicle, const std::function< int64(int64)> &next_accessor)
virtual void OnInitializeCheck()
TypeRegulationsChecker(const RoutingModel &model)
virtual bool FinalizeCheck() const
bool TypeCurrentlyOnRoute(int type, int pos) const
Returns true iff there's at least one instance of the given type on the route when scanning the route...
const RoutingModel & model_
void InitializeCheck(int vehicle, const std::function< int64(int64)> &next_accessor)
bool TypeOccursOnRoute(int type) const
Returns true iff any occurrence of the given type was seen on the route, i.e.
The following constraint ensures that incompatibilities and requirements between types are respected.
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
TypeRegulationsConstraint(const RoutingModel &model)
IntegerRange< NodeIndex > AllNodes() const
const std::vector< IntVar * > cumuls_
static const int64 kint64max
static const int64 kint64min
void STLDeleteElements(T *container)
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
bool FindCopy(const Collection &collection, const Key &key, Value *const value)
Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
bool ContainsKey(const Collection &collection, const Key &key)
const Collection::value_type::second_type * FindOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
const Collection::value_type::second_type & FindOrDie(const Collection &collection, const typename Collection::value_type::first_type &key)
std::function< int64(const Model &)> Value(IntegerVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool SolveModelWithSat(const RoutingModel &model, const RoutingSearchParameters &search_parameters, const Assignment *initial_solution, Assignment *solution)
Attempts to solve the model using the cp-sat solver.
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
int64 CapSub(int64 x, int64 y)
RoutingModelParameters DefaultRoutingModelParameters()
Demon * MakeConstraintDemon0(Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
std::string FindErrorInRoutingSearchParameters(const RoutingSearchParameters &search_parameters)
Returns an empty std::string if the routing search parameters are valid, and a non-empty,...
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
struct operations_research::SweepIndexSortAngle SweepIndexAngleComparator
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
uint64 ThoroughHash(const char *bytes, size_t len)
int64 CapAdd(int64 x, int64 y)
DimensionSchedulingStatus
struct operations_research::SweepIndexSortDistance SweepIndexDistanceComparator
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
int64 One()
This method returns 1.
struct operations_research::LinkSort LinkComparator
int64 CapProd(int64 x, int64 y)
std::function< int64(int64, int64)> RoutingTransitCallback2
RoutingSearchParameters DefaultRoutingSearchParameters()
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
std::function< int64(int64)> RoutingTransitCallback1
RangeMinMaxIndexFunction * MakeCachedRangeMinMaxIndexFunction(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
std::string MemoryUsage()
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
bool HasUnaryDimension(const std::vector< RoutingDimension * > &dimensions)
static const int kUnassigned
RangeIntToIntFunction * MakeCachedIntToIntFunction(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
LocalSearchFilter * MakePathStateFilter(Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
DecisionBuilder * MakeSetValuesFromTargets(Solver *solver, std::vector< IntVar * > variables, std::vector< int64 > targets)
A decision builder which tries to assign values to variables as close as possible to target values fi...
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
static int input(yyscan_t yyscanner)
ABSL_FLAG(int64, sweep_sectors, 1, "The number of sectors the space is divided before it is sweeped " "by the ray.")
#define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method, operators)
std::vector< int > var_indices
Link(std::pair< int, int > link, double value, int vehicle_class, int64 start_depot, int64 end_depot)
std::pair< int, int > link
bool operator()(const Link &link1, const Link &link2) const
static bool LessThan(const CostClass &a, const CostClass &b)
Comparator for STL containers and algorithms.
What follows is relevant for models with time/state dependent transits.
int64 fixed_cost
Contrarily to CostClass, here we need strict equivalence.
absl::StrongVector< DimensionIndex, int64 > dimension_capacities
absl::StrongVector< DimensionIndex, int64 > dimension_evaluator_classes
dimension_evaluators[d]->Run(from, to) is the transit value of arc from->to for a dimension d.
int start_equivalence_class
Vehicle start and end equivalence classes.
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_min
Bounds of cumul variables at start and end vehicle nodes.
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_min
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_max
int end_equivalence_class
uint64 unvisitable_nodes_fprint
Fingerprint of unvisitable non-start/end nodes.
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_max
CostClassIndex cost_class_index
The cost class of the vehicle.
std::vector< int > type_index_of_vehicle
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
std::vector< std::deque< int > > vehicles_per_vehicle_class
SweepIndex(const int64 index, const double angle, const double distance)
bool operator()(const SweepIndex &node1, const SweepIndex &node2) const
bool operator()(const SweepIndex &node1, const SweepIndex &node2) const
int position_of_last_type_on_vehicle_up_to_visit
Position of the last node of policy TYPE_ON_VEHICLE_UP_TO_VISIT visited on the route.
int num_type_added_to_vehicle
Number of TYPE_ADDED_TO_VEHICLE and TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED node type policies seen on ...
int num_type_removed_from_vehicle
Number of ADDED_TYPE_REMOVED_FROM_VEHICLE (effectively removing a type from the route) and TYPE_SIMUL...