33 #include <type_traits>
37 #include "absl/container/flat_hash_map.h"
38 #include "absl/container/flat_hash_set.h"
39 #include "absl/flags/flag.h"
40 #include "absl/functional/bind_front.h"
41 #include "absl/status/statusor.h"
42 #include "absl/strings/str_cat.h"
43 #include "absl/strings/str_format.h"
44 #include "absl/strings/string_view.h"
45 #include "absl/time/time.h"
58 #include "ortools/constraint_solver/routing_enums.pb.h"
64 #include "ortools/constraint_solver/routing_parameters.pb.h"
67 #include "ortools/constraint_solver/solver_parameters.pb.h"
73 #include "ortools/util/optional_boolean.pb.h"
83 class ExtendedSwapActiveOperator;
84 class LocalSearchPhaseParameters;
85 class MakeActiveAndRelocate;
86 class MakeActiveOperator;
87 class MakeChainInactiveOperator;
88 class MakeInactiveOperator;
90 class RelocateAndMakeActiveOperator;
91 class SwapActiveOperator;
103 std::string line_prefix)
const {
104 std::string s = absl::StrFormat(
"%stravel_cost_coefficient: %ld", line_prefix,
107 absl::StrAppendFormat(&s,
"\ntransition[%d] {\n%s\n}\n", i,
114 std::string line_prefix)
const {
115 return absl::StrFormat(
124 line_prefix, pre_travel_transit_value, line_prefix,
125 post_travel_transit_value, line_prefix,
126 compressed_travel_value_lower_bound, line_prefix,
127 travel_value_upper_bound, line_prefix,
128 travel_start_dependent_travel.DebugString(line_prefix + "\t"),
129 line_prefix, travel_compression_cost.DebugString(line_prefix +
"\t"));
134 if (x_anchors.size() <= 10) {
135 return "{ " +
DUMP_VARS(x_anchors, y_anchors).str() +
"}";
137 return absl::StrFormat(
"{\n%s%s\n%s%s\n}", line_prefix,
150 SetValuesFromTargets(std::vector<IntVar*> variables,
151 std::vector<int64_t> targets)
152 : variables_(std::move(variables)),
153 targets_(std::move(targets)),
155 steps_(variables_.size(), 0) {
156 DCHECK_EQ(variables_.size(), targets_.size());
159 int index = index_.Value();
160 while (
index < variables_.size() && variables_[
index]->Bound()) {
164 if (
index >= variables_.size())
return nullptr;
165 const int64_t variable_min = variables_[
index]->Min();
166 const int64_t variable_max = variables_[
index]->Max();
169 if (targets_[
index] <= variable_min) {
171 }
else if (targets_[
index] >= variable_max) {
174 int64_t step = steps_[
index];
179 if (
value < variable_min || variable_max <
value) {
180 step = GetNextStep(step);
198 int64_t GetNextStep(int64_t step)
const {
199 return (step > 0) ? -step :
CapSub(1, step);
201 const std::vector<IntVar*> variables_;
202 const std::vector<int64_t> targets_;
210 std::vector<IntVar*> variables,
211 std::vector<int64_t> targets) {
213 new SetValuesFromTargets(std::move(variables), std::move(targets)));
218 bool DimensionFixedTransitsEqualTransitEvaluatorForVehicle(
221 int node =
model->Start(vehicle);
222 while (!
model->IsEnd(node)) {
223 if (!
model->NextVar(node)->Bound()) {
226 const int next =
model->NextVar(node)->Value();
227 if (dimension.transit_evaluator(vehicle)(node,
next) !=
228 dimension.FixedTransitVar(node)->Value()) {
236 bool DimensionFixedTransitsEqualTransitEvaluators(
238 for (
int vehicle = 0; vehicle < dimension.model()->
vehicles(); vehicle++) {
239 if (!DimensionFixedTransitsEqualTransitEvaluatorForVehicle(dimension,
249 void ConcatenateRouteCumulAndBreakVarAndValues(
251 const std::vector<int64_t>& cumul_values,
252 const std::vector<int64_t>& break_values, std::vector<IntVar*>* variables,
253 std::vector<int64_t>* values) {
254 *values = cumul_values;
258 int current =
model.Start(vehicle);
260 variables->push_back(dimension.CumulVar(current));
261 if (!
model.IsEnd(current)) {
262 current =
model.NextVar(current)->Value();
273 std::swap(variables->at(1), variables->back());
274 std::swap(values->at(1), values->back());
275 if (dimension.HasBreakConstraints()) {
277 dimension.GetBreakIntervalsOfVehicle(vehicle)) {
278 variables->push_back(
interval->SafeStartExpr(0)->Var());
279 variables->push_back(
interval->SafeEndExpr(0)->Var());
281 values->insert(values->end(), break_values.begin(), break_values.end());
284 for (
int j = 0; j < values->size(); ++j) {
286 values->at(j) = variables->at(j)->Min();
289 DCHECK_EQ(variables->size(), values->size());
292 class SetCumulsFromLocalDimensionCosts :
public DecisionBuilder {
294 SetCumulsFromLocalDimensionCosts(
295 LocalDimensionCumulOptimizer* local_optimizer,
296 LocalDimensionCumulOptimizer* local_mp_optimizer, SearchMonitor* monitor,
297 bool optimize_and_pack =
false,
298 std::vector<RoutingModel::RouteDimensionTravelInfo>
299 dimension_travel_info_per_route = {})
300 : local_optimizer_(local_optimizer),
301 local_mp_optimizer_(local_mp_optimizer),
303 optimize_and_pack_(optimize_and_pack),
304 dimension_travel_info_per_route_(
305 std::move(dimension_travel_info_per_route)) {
306 DCHECK(dimension_travel_info_per_route_.empty() ||
307 dimension_travel_info_per_route_.size() ==
308 local_optimizer_->dimension()->model()->vehicles());
310 const std::vector<int>& resource_groups =
311 dimension->model()->GetDimensionResourceGroupIndices(dimension);
312 DCHECK_LE(resource_groups.size(), optimize_and_pack ? 1 : 0);
313 resource_group_index_ = resource_groups.empty() ? -1 : resource_groups[0];
316 Decision*
Next(Solver*
const solver)
override {
322 bool should_fail =
false;
323 for (
int vehicle = 0; vehicle <
model->vehicles(); ++vehicle) {
326 DCHECK(DimensionFixedTransitsEqualTransitEvaluatorForVehicle(dimension,
328 const bool vehicle_has_break_constraint =
329 dimension.HasBreakConstraints() &&
330 !dimension.GetBreakIntervalsOfVehicle(vehicle).empty();
331 LocalDimensionCumulOptimizer*
const optimizer =
332 vehicle_has_break_constraint ? local_mp_optimizer_ : local_optimizer_;
333 DCHECK(optimizer !=
nullptr);
334 std::vector<int64_t> cumul_values;
335 std::vector<int64_t> break_start_end_values;
337 ComputeCumulAndBreakValuesForVehicle(
338 optimizer, vehicle, &cumul_values, &break_start_end_values);
345 DCHECK(local_mp_optimizer_ !=
nullptr);
346 if (ComputeCumulAndBreakValuesForVehicle(local_mp_optimizer_, vehicle,
348 &break_start_end_values) ==
358 std::vector<IntVar*> cp_variables;
359 std::vector<int64_t> cp_values;
360 ConcatenateRouteCumulAndBreakVarAndValues(
361 dimension, vehicle, cumul_values, break_start_end_values,
362 &cp_variables, &cp_values);
365 std::move(cp_values)),
378 using Resource = RoutingModel::ResourceGroup::Resource;
379 using RouteDimensionTravelInfo = RoutingModel::RouteDimensionTravelInfo;
382 LocalDimensionCumulOptimizer* optimizer,
int vehicle,
383 std::vector<int64_t>* cumul_values,
384 std::vector<int64_t>* break_start_end_values) {
385 cumul_values->clear();
386 break_start_end_values->clear();
388 const auto next = [
model](int64_t n) {
return model->NextVar(n)->Value(); };
389 const RouteDimensionTravelInfo& dimension_travel_info =
390 dimension_travel_info_per_route_.empty()
391 ? RouteDimensionTravelInfo()
392 : dimension_travel_info_per_route_[vehicle];
393 if (optimize_and_pack_) {
394 const int resource_index =
395 resource_group_index_ < 0
397 :
model->ResourceVar(vehicle, resource_group_index_)->Value();
398 const Resource*
const resource =
399 resource_index < 0 ? nullptr
400 : &
model->GetResourceGroup(resource_group_index_)
401 ->GetResource(resource_index);
402 return optimizer->ComputePackedRouteCumuls(
403 vehicle,
next, dimension_travel_info, resource, cumul_values,
404 break_start_end_values);
407 return optimizer->ComputeRouteCumuls(vehicle,
next, dimension_travel_info,
409 break_start_end_values);
413 LocalDimensionCumulOptimizer*
const local_optimizer_;
414 LocalDimensionCumulOptimizer*
const local_mp_optimizer_;
416 int resource_group_index_;
417 SearchMonitor*
const monitor_;
418 const bool optimize_and_pack_;
419 const std::vector<RouteDimensionTravelInfo> dimension_travel_info_per_route_;
422 class SetCumulsFromGlobalDimensionCosts :
public DecisionBuilder {
424 SetCumulsFromGlobalDimensionCosts(
425 GlobalDimensionCumulOptimizer* global_optimizer,
426 GlobalDimensionCumulOptimizer* global_mp_optimizer,
427 SearchMonitor* monitor,
bool optimize_and_pack =
false,
428 std::vector<RoutingModel::RouteDimensionTravelInfo>
429 dimension_travel_info_per_route = {})
430 : global_optimizer_(global_optimizer),
431 global_mp_optimizer_(global_mp_optimizer),
433 optimize_and_pack_(optimize_and_pack),
434 dimension_travel_info_per_route_(
435 std::move(dimension_travel_info_per_route)) {
436 DCHECK(dimension_travel_info_per_route_.empty() ||
437 dimension_travel_info_per_route_.size() ==
438 global_optimizer_->dimension()->model()->vehicles());
441 Decision*
Next(Solver*
const solver)
override {
445 bool should_fail =
false;
448 DCHECK(DimensionFixedTransitsEqualTransitEvaluators(*dimension));
451 GlobalDimensionCumulOptimizer*
const optimizer =
452 model->GetDimensionResourceGroupIndices(dimension).empty()
454 : global_mp_optimizer_;
455 std::vector<int64_t> cumul_values;
456 std::vector<int64_t> break_start_end_values;
457 std::vector<std::vector<int>> resource_indices_per_group;
459 ComputeCumulBreakAndResourceValues(optimizer, &cumul_values,
460 &break_start_end_values,
461 &resource_indices_per_group);
468 ComputeCumulBreakAndResourceValues(
469 global_mp_optimizer_, &cumul_values, &break_start_end_values,
470 &resource_indices_per_group);
480 std::vector<IntVar*> cp_variables = dimension->cumuls();
481 std::vector<int64_t> cp_values;
483 if (dimension->HasBreakConstraints()) {
484 const int num_vehicles =
model->vehicles();
485 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
487 dimension->GetBreakIntervalsOfVehicle(vehicle)) {
488 cp_variables.push_back(
interval->SafeStartExpr(0)->Var());
489 cp_variables.push_back(
interval->SafeEndExpr(0)->Var());
492 cp_values.insert(cp_values.end(), break_start_end_values.begin(),
493 break_start_end_values.end());
496 model->GetDimensionResourceGroupIndices(dimension)) {
497 const std::vector<int>& resource_values =
498 resource_indices_per_group[rg_index];
499 DCHECK(!resource_values.empty());
500 cp_values.insert(cp_values.end(), resource_values.begin(),
501 resource_values.end());
502 const std::vector<IntVar*>& resource_vars =
503 model->ResourceVars(rg_index);
504 DCHECK_EQ(resource_vars.size(), resource_values.size());
505 cp_variables.insert(cp_variables.end(), resource_vars.begin(),
506 resource_vars.end());
509 for (
int j = 0; j < cp_values.size(); ++j) {
511 cp_values[j] = cp_variables[j]->Min();
516 std::move(cp_values)),
530 GlobalDimensionCumulOptimizer* optimizer,
531 std::vector<int64_t>* cumul_values,
532 std::vector<int64_t>* break_start_end_values,
533 std::vector<std::vector<int>>* resource_indices_per_group) {
534 DCHECK_NE(optimizer,
nullptr);
535 cumul_values->clear();
536 break_start_end_values->clear();
537 resource_indices_per_group->clear();
539 const auto next = [
model](int64_t n) {
return model->NextVar(n)->Value(); };
540 return optimize_and_pack_
541 ? optimizer->ComputePackedCumuls(
542 next, dimension_travel_info_per_route_, cumul_values,
543 break_start_end_values, resource_indices_per_group)
544 : optimizer->ComputeCumuls(
545 next, dimension_travel_info_per_route_, cumul_values,
546 break_start_end_values, resource_indices_per_group);
549 GlobalDimensionCumulOptimizer*
const global_optimizer_;
550 GlobalDimensionCumulOptimizer*
const global_mp_optimizer_;
551 SearchMonitor*
const monitor_;
552 const bool optimize_and_pack_;
553 const std::vector<RoutingModel::RouteDimensionTravelInfo>
554 dimension_travel_info_per_route_;
557 class SetCumulsFromResourceAssignmentCosts :
public DecisionBuilder {
559 SetCumulsFromResourceAssignmentCosts(
560 LocalDimensionCumulOptimizer* lp_optimizer,
561 LocalDimensionCumulOptimizer* mp_optimizer, SearchMonitor* monitor)
562 : model_(*lp_optimizer->dimension()->
model()),
563 dimension_(*lp_optimizer->dimension()),
564 lp_optimizer_(lp_optimizer),
565 mp_optimizer_(mp_optimizer),
570 Decision*
Next(Solver*
const solver)
override {
571 bool should_fail =
false;
573 const int num_vehicles = model_.vehicles();
574 std::vector<std::vector<int64_t>> assignment_costs(num_vehicles);
575 std::vector<std::vector<std::vector<int64_t>>> cumul_values(num_vehicles);
576 std::vector<std::vector<std::vector<int64_t>>> break_values(num_vehicles);
578 const auto next = [&
model = model_](int64_t n) {
579 return model.NextVar(n)->Value();
581 DCHECK(DimensionFixedTransitsEqualTransitEvaluators(dimension_));
583 for (
int v : resource_group_.GetVehiclesRequiringAResource()) {
585 v, resource_group_,
next, dimension_.transit_evaluator(v),
586 true, lp_optimizer_, mp_optimizer_,
587 &assignment_costs[v], &cumul_values[v], &break_values[v])) {
593 std::vector<int> resource_indices(num_vehicles);
597 resource_group_.GetVehiclesRequiringAResource(),
598 resource_group_.Size(),
599 [&assignment_costs](
int v) { return &assignment_costs[v]; },
600 &resource_indices) < 0;
603 DCHECK_EQ(resource_indices.size(), num_vehicles);
604 const int num_resources = resource_group_.Size();
605 for (
int v : resource_group_.GetVehiclesRequiringAResource()) {
606 if (
next(model_.Start(v)) == model_.End(v) &&
607 !model_.IsVehicleUsedWhenEmpty(v)) {
610 const int resource_index = resource_indices[v];
611 DCHECK_GE(resource_index, 0);
612 DCHECK_EQ(cumul_values[v].size(), num_resources);
613 DCHECK_EQ(break_values[v].size(), num_resources);
614 const std::vector<int64_t>& optimal_cumul_values =
615 cumul_values[v][resource_index];
616 const std::vector<int64_t>& optimal_break_values =
617 break_values[v][resource_index];
618 std::vector<IntVar*> cp_variables;
619 std::vector<int64_t> cp_values;
620 ConcatenateRouteCumulAndBreakVarAndValues(
621 dimension_, v, optimal_cumul_values, optimal_break_values,
622 &cp_variables, &cp_values);
624 const std::vector<IntVar*>& resource_vars =
625 model_.ResourceVars(rg_index_);
626 DCHECK_EQ(resource_vars.size(), resource_indices.size());
627 cp_variables.insert(cp_variables.end(), resource_vars.begin(),
628 resource_vars.end());
629 cp_values.insert(cp_values.end(), resource_indices.begin(),
630 resource_indices.end());
633 std::move(cp_values)),
650 LocalDimensionCumulOptimizer* lp_optimizer_;
651 LocalDimensionCumulOptimizer* mp_optimizer_;
660 const Assignment* original_assignment, absl::Duration duration_limit,
661 bool* time_limit_was_reached) {
663 if (original_assignment ==
nullptr)
return nullptr;
664 if (duration_limit <= absl::ZeroDuration()) {
665 if (time_limit_was_reached) *time_limit_was_reached =
true;
666 return original_assignment;
668 if (global_dimension_optimizers_.empty() &&
669 local_dimension_optimizers_.empty()) {
670 return original_assignment;
672 RegularLimit*
const limit = GetOrCreateLimit();
679 Assignment* packed_assignment = solver_->MakeAssignment();
680 packed_assignment->Add(
Nexts());
683 const std::vector<int>& resource_groups =
685 if (resource_groups.size() == 1) {
687 packed_assignment->Add(resource_vars_[resource_groups[0]]);
690 packed_assignment->CopyIntersection(original_assignment);
692 std::vector<DecisionBuilder*> decision_builders;
693 decision_builders.push_back(solver_->MakeRestoreAssignment(preassignment_));
694 decision_builders.push_back(
695 solver_->MakeRestoreAssignment(packed_assignment));
696 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
701 decision_builders.push_back(
702 solver_->RevAlloc(
new SetCumulsFromLocalDimensionCosts(
703 lp_optimizer.get(), mp_optimizer.get(),
704 GetOrCreateLargeNeighborhoodSearchLimit(),
707 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
708 decision_builders.push_back(
709 solver_->RevAlloc(
new SetCumulsFromGlobalDimensionCosts(
710 lp_optimizer.get(), mp_optimizer.get(),
711 GetOrCreateLargeNeighborhoodSearchLimit(),
714 decision_builders.push_back(
715 CreateFinalizerForMinimizedAndMaximizedVariables());
717 DecisionBuilder* restore_pack_and_finalize =
718 solver_->Compose(decision_builders);
719 solver_->Solve(restore_pack_and_finalize,
720 optimized_dimensions_assignment_collector_, limit);
721 const bool limit_was_reached = limit->Check();
722 if (time_limit_was_reached) *time_limit_was_reached = limit_was_reached;
723 if (optimized_dimensions_assignment_collector_->
solution_count() != 1) {
724 if (limit_was_reached) {
725 VLOG(1) <<
"The packing reached the time limit.";
729 LOG(ERROR) <<
"The given assignment is not valid for this model, or"
730 " cannot be packed.";
735 packed_assignment->Copy(original_assignment);
736 packed_assignment->CopyIntersection(
737 optimized_dimensions_assignment_collector_->
solution(0));
739 return packed_assignment;
747 return sweep_arranger_.get();
753 const int size = routing_model.
Size();
754 node_index_to_neighbors_by_cost_class_.clear();
755 if (num_neighbors >= size) {
756 all_nodes_.resize(routing_model.
Size());
757 std::iota(all_nodes_.begin(), all_nodes_.end(), 0);
760 node_index_to_neighbors_by_cost_class_.resize(size);
763 for (
int node_index = 0; node_index < size; node_index++) {
764 node_index_to_neighbors_by_cost_class_[node_index].resize(num_cost_classes);
765 for (
int cc = 0; cc < num_cost_classes; cc++) {
766 node_index_to_neighbors_by_cost_class_[node_index][cc] =
767 std::make_unique<SparseBitset<int>>(size);
771 std::vector<std::pair< int64_t,
int>> cost_nodes;
772 cost_nodes.reserve(size);
773 for (
int node_index = 0; node_index < size; ++node_index) {
774 DCHECK(!routing_model.
IsEnd(node_index));
775 if (routing_model.
IsStart(node_index)) {
781 for (
int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
783 RoutingCostClassIndex(cost_class))) {
788 for (
int after_node = 0; after_node < size; ++after_node) {
789 if (after_node != node_index && !routing_model.
IsStart(after_node)) {
790 cost_nodes.push_back(
792 node_index, after_node, cost_class),
796 std::nth_element(cost_nodes.begin(),
797 cost_nodes.begin() + num_neighbors - 1,
799 cost_nodes.resize(num_neighbors);
801 auto& node_neighbors =
802 node_index_to_neighbors_by_cost_class_[node_index][cost_class];
803 for (
const auto& costed_node : cost_nodes) {
804 const int neighbor = costed_node.second;
805 node_neighbors->Set(neighbor);
808 DCHECK(!routing_model.
IsEnd(neighbor) &&
809 !routing_model.
IsStart(neighbor));
810 node_index_to_neighbors_by_cost_class_[neighbor][cost_class]->Set(
816 for (
int vehicle = 0; vehicle < routing_model.
vehicles(); vehicle++) {
817 const int vehicle_start = routing_model.
Start(vehicle);
818 node_neighbors->Set(vehicle_start);
819 node_index_to_neighbors_by_cost_class_[vehicle_start][cost_class]->Set(
826 const RoutingModel::NodeNeighborsByCostClass*
828 std::unique_ptr<NodeNeighborsByCostClass>* node_neighbors_by_cost_class_ptr =
829 gtl::FindOrNull(node_neighbors_by_cost_class_per_size_, num_neighbors);
830 if (node_neighbors_by_cost_class_ptr !=
nullptr) {
831 return node_neighbors_by_cost_class_ptr->get();
833 std::unique_ptr<NodeNeighborsByCostClass>& node_neighbors_by_cost_class =
834 node_neighbors_by_cost_class_per_size_
835 .insert(std::make_pair(num_neighbors,
836 std::make_unique<NodeNeighborsByCostClass>()))
838 node_neighbors_by_cost_class->ComputeNeighbors(*
this, num_neighbors);
839 return node_neighbors_by_cost_class.get();
844 class DifferentFromValues :
public Constraint {
846 DifferentFromValues(Solver*
solver, IntVar*
var, std::vector<int64_t> values)
847 : Constraint(
solver), var_(
var), values_(std::move(values)) {}
848 void Post()
override {}
849 void InitialPropagate()
override { var_->RemoveValues(values_); }
850 std::string DebugString()
const override {
return "DifferentFromValues"; }
851 void Accept(ModelVisitor*
const visitor)
const override {
861 const std::vector<int64_t> values_;
871 void ComputeVehicleChainStartEndInfo(
873 std::vector<int>* vehicle_index_of_start_chain_end) {
874 vehicle_index_of_start_chain_end->resize(
model.Size() +
model.vehicles(), -1);
876 for (
int vehicle = 0; vehicle <
model.vehicles(); ++vehicle) {
877 int64_t node =
model.Start(vehicle);
878 while (!
model.IsEnd(node) &&
model.NextVar(node)->Bound()) {
879 node =
model.NextVar(node)->Value();
881 vehicle_index_of_start_chain_end->at(node) = vehicle;
887 class ResourceAssignmentConstraint :
public Constraint {
889 ResourceAssignmentConstraint(
890 const ResourceGroup* resource_group,
894 resource_group_(*resource_group),
895 vehicle_resource_vars_(*vehicle_resource_vars),
896 vehicle_to_start_bound_vars_per_dimension_(
model->
vehicles()),
897 vehicle_to_end_bound_vars_per_dimension_(
model->
vehicles()) {
898 DCHECK_EQ(vehicle_resource_vars_.size(), model_.vehicles());
900 const std::vector<RoutingDimension*>&
dimensions = model_.GetDimensions();
901 for (
int v = 0; v < model_.vehicles(); v++) {
902 IntVar*
const resource_var = vehicle_resource_vars_[v];
903 model->AddToAssignment(resource_var);
905 model->AddVariableTargetToFinalizer(resource_var, -1);
907 if (!resource_group_.VehicleRequiresAResource(v)) {
911 vehicle_to_start_bound_vars_per_dimension_[v].resize(
dimensions.size());
912 vehicle_to_end_bound_vars_per_dimension_[v].resize(
dimensions.size());
915 resource_group_.GetAffectedDimensionIndices()) {
918 model->AddVariableMinimizedByFinalizer(dim->CumulVar(model_.End(v)));
919 model->AddVariableMaximizedByFinalizer(dim->CumulVar(model_.Start(v)));
920 for (ResourceBoundVars* bound_vars :
921 {&vehicle_to_start_bound_vars_per_dimension_[v][d.value()],
922 &vehicle_to_end_bound_vars_per_dimension_[v][d.value()]}) {
923 bound_vars->lower_bound =
926 bound_vars->upper_bound =
934 void Post()
override {}
936 void InitialPropagate()
override {
937 if (!AllResourceAssignmentsFeasible()) {
940 SetupResourceConstraints();
944 bool AllResourceAssignmentsFeasible() {
945 DCHECK(!model_.GetResourceGroups().empty());
947 std::vector<int64_t> end_chain_starts;
948 std::vector<int> vehicle_index_of_start_chain_end;
949 ComputeVehicleChainStartEndInfo(model_, &end_chain_starts,
950 &vehicle_index_of_start_chain_end);
951 const auto next = [&
model = model_, &end_chain_starts,
952 &vehicle_index_of_start_chain_end](int64_t node) {
953 if (
model.NextVar(node)->Bound())
return model.NextVar(node)->Value();
954 const int vehicle = vehicle_index_of_start_chain_end[node];
961 return end_chain_starts[vehicle];
964 const std::vector<RoutingDimension*>&
dimensions = model_.GetDimensions();
966 resource_group_.GetAffectedDimensionIndices()) {
967 if (!ResourceAssignmentFeasibleForDimension(*
dimensions[d.value()],
975 bool ResourceAssignmentFeasibleForDimension(
977 const std::function<int64_t(int64_t)>&
next) {
978 LocalDimensionCumulOptimizer*
const optimizer =
979 model_.GetMutableLocalCumulLPOptimizer(dimension);
981 if (optimizer ==
nullptr)
return true;
983 LocalDimensionCumulOptimizer*
const mp_optimizer =
984 model_.GetMutableLocalCumulMPOptimizer(dimension);
985 DCHECK_NE(mp_optimizer,
nullptr);
986 const auto transit = [&dimension](int64_t node, int64_t ) {
992 return std::max<int64_t>(dimension.FixedTransitVar(node)->Min(), 0);
995 std::vector<std::vector<int64_t>> assignment_costs(model_.vehicles());
996 for (
int v : resource_group_.GetVehiclesRequiringAResource()) {
998 v, resource_group_,
next, transit,
1000 model_.GetMutableLocalCumulLPOptimizer(dimension),
1001 model_.GetMutableLocalCumulMPOptimizer(dimension),
1002 &assignment_costs[v],
nullptr,
nullptr)) {
1009 resource_group_.GetVehiclesRequiringAResource(),
1010 resource_group_.Size(),
1011 [&assignment_costs](
int v) { return &assignment_costs[v]; },
1015 void SetupResourceConstraints() {
1016 Solver*
const s =
solver();
1019 s->AddConstraint(s->MakeAllDifferentExcept(vehicle_resource_vars_, -1));
1020 const std::vector<RoutingDimension*>&
dimensions = model_.GetDimensions();
1021 for (
int v = 0; v < model_.vehicles(); v++) {
1022 IntVar*
const resource_var = vehicle_resource_vars_[v];
1023 if (!resource_group_.VehicleRequiresAResource(v)) {
1024 resource_var->SetValue(-1);
1029 s->MakeEquality(model_.VehicleRouteConsideredVar(v),
1030 s->MakeIsDifferentCstVar(resource_var, -1)));
1034 resource_group_.GetAffectedDimensionIndices()) {
1035 const int d = dim_index.value();
1040 for (
bool start_cumul : {
true,
false}) {
1041 IntVar*
const cumul_var = start_cumul ? dim->CumulVar(model_.Start(v))
1042 : dim->CumulVar(model_.End(v));
1044 IntVar*
const resource_lb_var =
1046 ? vehicle_to_start_bound_vars_per_dimension_[v][d].lower_bound
1047 : vehicle_to_end_bound_vars_per_dimension_[v][d].lower_bound;
1048 s->AddConstraint(s->MakeLightElement(
1049 [dim, start_cumul, &resource_group = resource_group_](
int r) {
1050 if (r < 0) return std::numeric_limits<int64_t>::min();
1051 return start_cumul ? resource_group.GetResources()[r]
1052 .GetDimensionAttributes(dim)
1055 : resource_group.GetResources()[r]
1056 .GetDimensionAttributes(dim)
1060 resource_lb_var, resource_var,
1061 [&
model = model_]() {
1062 return model.enable_deep_serialization();
1064 s->AddConstraint(s->MakeGreaterOrEqual(cumul_var, resource_lb_var));
1066 IntVar*
const resource_ub_var =
1068 ? vehicle_to_start_bound_vars_per_dimension_[v][d].upper_bound
1069 : vehicle_to_end_bound_vars_per_dimension_[v][d].upper_bound;
1070 s->AddConstraint(s->MakeLightElement(
1071 [dim, start_cumul, &resource_group = resource_group_](
int r) {
1072 if (r < 0) return std::numeric_limits<int64_t>::max();
1073 return start_cumul ? resource_group.GetResources()[r]
1074 .GetDimensionAttributes(dim)
1077 : resource_group.GetResources()[r]
1078 .GetDimensionAttributes(dim)
1082 resource_ub_var, resource_var,
1083 [&
model = model_]() {
1084 return model.enable_deep_serialization();
1086 s->AddConstraint(s->MakeLessOrEqual(cumul_var, resource_ub_var));
1092 struct ResourceBoundVars {
1098 const ResourceGroup& resource_group_;
1099 const std::vector<IntVar*>& vehicle_resource_vars_;
1103 std::vector<std::vector<ResourceBoundVars>>
1104 vehicle_to_start_bound_vars_per_dimension_;
1105 std::vector<std::vector<ResourceBoundVars>>
1106 vehicle_to_end_bound_vars_per_dimension_;
1109 Constraint* MakeResourceConstraint(
1110 const ResourceGroup* resource_group,
1112 return model->solver()->RevAlloc(
new ResourceAssignmentConstraint(
1113 resource_group, vehicle_resource_vars,
model));
1117 template <
class A,
class B>
1118 static int64_t ReturnZero(A, B) {
1124 for (
int i = 0; i < size1; i++) {
1125 for (
int j = 0; j < size2; j++) {
1150 : nodes_(index_manager.num_nodes()),
1151 vehicles_(index_manager.num_vehicles()),
1152 max_active_vehicles_(vehicles_),
1153 fixed_cost_of_vehicle_(vehicles_, 0),
1154 cost_class_index_of_vehicle_(vehicles_, CostClassIndex(-1)),
1155 linear_cost_factor_of_vehicle_(vehicles_, 0),
1156 quadratic_cost_factor_of_vehicle_(vehicles_, 0),
1157 vehicle_amortized_cost_factors_set_(false),
1158 vehicle_used_when_empty_(vehicles_, false),
1160 costs_are_homogeneous_across_vehicles_(
1162 cache_callbacks_(false),
1163 vehicle_class_index_of_vehicle_(vehicles_, VehicleClassIndex(-1)),
1164 vehicle_pickup_delivery_policy_(vehicles_, PICKUP_AND_DELIVERY_NO_ORDER),
1165 has_hard_type_incompatibilities_(false),
1166 has_temporal_type_incompatibilities_(false),
1167 has_same_vehicle_type_requirements_(false),
1168 has_temporal_type_requirements_(false),
1169 num_visit_types_(0),
1170 paths_metadata_(index_manager),
1171 manager_(index_manager) {
1173 vehicle_to_transit_cost_.assign(
1177 cache_callbacks_ = (nodes_ <=
parameters.max_callback_cache_size());
1180 ConstraintSolverParameters solver_parameters =
1183 solver_ = std::make_unique<Solver>(
"Routing", solver_parameters);
1188 const int64_t size =
Size();
1189 index_to_pickup_index_pairs_.resize(size);
1190 index_to_delivery_index_pairs_.resize(size);
1192 index_to_type_policy_.resize(index_manager.
num_indices());
1194 const std::vector<RoutingIndexManager::NodeIndex>& index_to_node =
1196 index_to_equivalence_class_.resize(index_manager.
num_indices());
1197 for (
int i = 0; i < index_to_node.size(); ++i) {
1198 index_to_equivalence_class_[i] = index_to_node[i].value();
1200 allowed_vehicles_.resize(
Size() + vehicles_);
1203 void RoutingModel::Initialize() {
1204 const int size =
Size();
1206 solver_->MakeIntVarArray(size, 0, size + vehicles_ - 1,
"Nexts", &nexts_);
1207 solver_->AddConstraint(solver_->MakeAllDifferent(nexts_,
false));
1208 index_to_disjunctions_.resize(size + vehicles_);
1211 solver_->MakeIntVarArray(size + vehicles_, -1, vehicles_ - 1,
"Vehicles",
1214 solver_->MakeBoolVarArray(size,
"Active", &active_);
1216 solver_->MakeBoolVarArray(vehicles_,
"ActiveVehicle", &vehicle_active_);
1218 solver_->MakeBoolVarArray(vehicles_,
"VehicleCostsConsidered",
1219 &vehicle_route_considered_);
1221 solver_->MakeBoolVarArray(size + vehicles_,
"IsBoundToEnd",
1224 cost_cache_.clear();
1226 preassignment_ = solver_->MakeAssignment();
1233 absl::flat_hash_set<RangeIntToIntFunction*> value_functions_delete;
1234 absl::flat_hash_set<RangeMinMaxIndexFunction*> index_functions_delete;
1235 for (
const auto& cache_line : state_dependent_transit_evaluators_cache_) {
1236 for (
const auto& key_transit : *cache_line) {
1237 value_functions_delete.insert(key_transit.second.transit);
1238 index_functions_delete.insert(key_transit.second.transit_plus_identity);
1247 RoutingModel*
model) {
1249 return model->RegisterPositiveTransitCallback(std::move(
callback));
1255 RoutingModel*
model) {
1257 return model->RegisterPositiveUnaryTransitCallback(std::move(
callback));
1259 return model->RegisterUnaryTransitCallback(std::move(
callback));
1264 bool is_positive = std::all_of(std::cbegin(values), std::cend(values),
1265 [](int64_t transit) {
return transit >= 0; });
1266 return RegisterUnaryCallback(
1267 [
this, values = std::move(values)](int64_t i) {
1274 const int index = unary_transit_evaluators_.size();
1275 unary_transit_evaluators_.push_back(std::move(
callback));
1277 return unary_transit_evaluators_[
index](i);
1282 std::vector<std::vector<int64_t> > values) {
1283 bool all_transits_positive =
true;
1284 for (
const std::vector<int64_t>& transit_values : values) {
1285 all_transits_positive =
1286 std::all_of(std::cbegin(transit_values), std::cend(transit_values),
1287 [](int64_t transit) {
return transit >= 0; });
1288 if (!all_transits_positive) {
1292 return RegisterCallback(
1293 [
this, values = std::move(values)](int64_t i, int64_t j) {
1297 all_transits_positive,
this);
1302 is_transit_evaluator_positive_.push_back(
true);
1303 DCHECK(TransitCallbackPositive(
1309 if (cache_callbacks_) {
1311 std::vector<int64_t> cache(size * size, 0);
1312 for (
int i = 0; i < size; ++i) {
1313 for (
int j = 0; j < size; ++j) {
1314 cache[i * size + j] =
callback(i, j);
1317 transit_evaluators_.push_back(
1318 [cache, size](int64_t i, int64_t j) {
return cache[i * size + j]; });
1320 transit_evaluators_.push_back(std::move(
callback));
1322 if (transit_evaluators_.size() != unary_transit_evaluators_.size()) {
1323 DCHECK_EQ(transit_evaluators_.size(), unary_transit_evaluators_.size() + 1);
1324 unary_transit_evaluators_.push_back(
nullptr);
1326 if (transit_evaluators_.size() != is_transit_evaluator_positive_.size()) {
1327 DCHECK_EQ(transit_evaluators_.size(),
1328 is_transit_evaluator_positive_.size() + 1);
1329 is_transit_evaluator_positive_.push_back(
false);
1331 return transit_evaluators_.size() - 1;
1335 is_transit_evaluator_positive_.push_back(
true);
1342 VariableIndexEvaluator2
callback) {
1343 state_dependent_transit_evaluators_cache_.push_back(
1344 std::make_unique<StateDependentTransitCallbackCache>());
1345 StateDependentTransitCallbackCache*
const cache =
1346 state_dependent_transit_evaluators_cache_.back().get();
1347 state_dependent_transit_evaluators_.push_back(
1348 [cache,
callback](int64_t i, int64_t j) {
1349 StateDependentTransit
value;
1352 cache->insert({CacheKey(i, j),
value});
1355 return state_dependent_transit_evaluators_.size() - 1;
1358 void RoutingModel::AddNoCycleConstraintInternal() {
1359 if (no_cycle_constraint_ ==
nullptr) {
1360 no_cycle_constraint_ = solver_->MakeNoCycle(nexts_, active_);
1361 solver_->AddConstraint(no_cycle_constraint_);
1366 int64_t
capacity,
bool fix_start_cumul_to_zero,
1367 const std::string&
name) {
1368 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
1369 std::vector<int64_t> capacities(vehicles_,
capacity);
1370 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
1371 std::move(capacities),
1372 fix_start_cumul_to_zero,
name);
1376 const std::vector<int>& evaluator_indices, int64_t slack_max,
1378 std::vector<int64_t> capacities(vehicles_,
capacity);
1379 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
1380 std::move(capacities),
1381 fix_start_cumul_to_zero,
name);
1385 int evaluator_index, int64_t slack_max,
1386 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
1388 const std::vector<int> evaluator_indices(vehicles_, evaluator_index);
1389 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
1390 std::move(vehicle_capacities),
1391 fix_start_cumul_to_zero,
name);
1395 const std::vector<int>& evaluator_indices, int64_t slack_max,
1396 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
1397 const std::string&
name) {
1398 return AddDimensionWithCapacityInternal(evaluator_indices, slack_max,
1399 std::move(vehicle_capacities),
1400 fix_start_cumul_to_zero,
name);
1403 bool RoutingModel::AddDimensionWithCapacityInternal(
1404 const std::vector<int>& evaluator_indices, int64_t slack_max,
1405 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
1406 const std::string&
name) {
1407 CHECK_EQ(vehicles_, vehicle_capacities.size());
1408 return InitializeDimensionInternal(
1409 evaluator_indices, std::vector<int>(), slack_max, fix_start_cumul_to_zero,
1413 bool RoutingModel::InitializeDimensionInternal(
1414 const std::vector<int>& evaluator_indices,
1415 const std::vector<int>& state_dependent_evaluator_indices,
1416 int64_t slack_max,
bool fix_start_cumul_to_zero,
1417 RoutingDimension* dimension) {
1418 CHECK(dimension !=
nullptr);
1419 CHECK_EQ(vehicles_, evaluator_indices.size());
1420 CHECK((dimension->base_dimension_ ==
nullptr &&
1421 state_dependent_evaluator_indices.empty()) ||
1422 vehicles_ == state_dependent_evaluator_indices.size());
1425 dimension_name_to_index_[dimension->name()] = dimension_index;
1426 dimensions_.push_back(dimension);
1427 dimension->Initialize(evaluator_indices, state_dependent_evaluator_indices,
1429 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
1430 nexts_, active_, dimension->cumuls(), dimension->transits()));
1431 if (fix_start_cumul_to_zero) {
1432 for (
int i = 0; i < vehicles_; ++i) {
1433 IntVar*
const start_cumul = dimension->CumulVar(
Start(i));
1434 CHECK_EQ(0, start_cumul->Min());
1435 start_cumul->SetValue(0);
1446 bool fix_start_cumul_to_zero,
const std::string& dimension_name) {
1447 const int evaluator_index =
1450 return std::make_pair(evaluator_index,
1452 fix_start_cumul_to_zero, dimension_name));
1456 std::vector<int64_t> values, int64_t
capacity,
bool fix_start_cumul_to_zero,
1457 const std::string& dimension_name) {
1459 return std::make_pair(evaluator_index,
1461 fix_start_cumul_to_zero, dimension_name));
1465 std::vector<std::vector<int64_t>> values, int64_t
capacity,
1466 bool fix_start_cumul_to_zero,
const std::string& dimension_name) {
1468 return std::make_pair(evaluator_index,
1470 fix_start_cumul_to_zero, dimension_name));
1477 class RangeMakeElementExpr :
public BaseIntExpr {
1479 RangeMakeElementExpr(
const RangeIntToIntFunction*
callback, IntVar*
index,
1481 : BaseIntExpr(s), callback_(ABSL_DIE_IF_NULL(
callback)), index_(
index) {
1482 CHECK(callback_ !=
nullptr);
1483 CHECK(
index !=
nullptr);
1486 int64_t Min()
const override {
1488 const int idx_min = index_->Min();
1489 const int idx_max = index_->Max() + 1;
1490 return (idx_min < idx_max) ? callback_->RangeMin(idx_min, idx_max)
1493 void SetMin(int64_t new_min)
override {
1494 const int64_t old_min = Min();
1495 const int64_t old_max = Max();
1496 if (old_min < new_min && new_min <= old_max) {
1497 const int64_t old_idx_min = index_->Min();
1498 const int64_t old_idx_max = index_->Max() + 1;
1499 if (old_idx_min < old_idx_max) {
1500 const int64_t new_idx_min = callback_->RangeFirstInsideInterval(
1501 old_idx_min, old_idx_max, new_min, old_max + 1);
1502 index_->SetMin(new_idx_min);
1503 if (new_idx_min < old_idx_max) {
1504 const int64_t new_idx_max = callback_->RangeLastInsideInterval(
1505 new_idx_min, old_idx_max, new_min, old_max + 1);
1506 index_->SetMax(new_idx_max);
1511 int64_t Max()
const override {
1513 const int idx_min = index_->Min();
1514 const int idx_max = index_->Max() + 1;
1515 return (idx_min < idx_max) ? callback_->RangeMax(idx_min, idx_max)
1518 void SetMax(int64_t new_max)
override {
1519 const int64_t old_min = Min();
1520 const int64_t old_max = Max();
1521 if (old_min <= new_max && new_max < old_max) {
1522 const int64_t old_idx_min = index_->Min();
1523 const int64_t old_idx_max = index_->Max() + 1;
1524 if (old_idx_min < old_idx_max) {
1525 const int64_t new_idx_min = callback_->RangeFirstInsideInterval(
1526 old_idx_min, old_idx_max, old_min, new_max + 1);
1527 index_->SetMin(new_idx_min);
1528 if (new_idx_min < old_idx_max) {
1529 const int64_t new_idx_max = callback_->RangeLastInsideInterval(
1530 new_idx_min, old_idx_max, old_min, new_max + 1);
1531 index_->SetMax(new_idx_max);
1536 void WhenRange(Demon* d)
override { index_->WhenRange(d); }
1539 const RangeIntToIntFunction*
const callback_;
1540 IntVar*
const index_;
1551 const std::vector<int>& dependent_transits,
1552 const RoutingDimension* base_dimension, int64_t slack_max,
1553 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
1555 const std::vector<int> pure_transits(vehicles_, 0);
1557 pure_transits, dependent_transits, base_dimension, slack_max,
1558 std::move(vehicle_capacities), fix_start_cumul_to_zero,
name);
1563 int64_t vehicle_capacity,
bool fix_start_cumul_to_zero,
1564 const std::string&
name) {
1566 0, transit, dimension, slack_max, vehicle_capacity,
1567 fix_start_cumul_to_zero,
name);
1570 bool RoutingModel::AddDimensionDependentDimensionWithVehicleCapacityInternal(
1571 const std::vector<int>& pure_transits,
1572 const std::vector<int>& dependent_transits,
1573 const RoutingDimension* base_dimension, int64_t slack_max,
1574 std::vector<int64_t> vehicle_capacities,
bool fix_start_cumul_to_zero,
1575 const std::string&
name) {
1576 CHECK_EQ(vehicles_, vehicle_capacities.size());
1578 if (base_dimension ==
nullptr) {
1580 name, RoutingDimension::SelfBased());
1585 return InitializeDimensionInternal(pure_transits, dependent_transits,
1586 slack_max, fix_start_cumul_to_zero,
1591 int pure_transit,
int dependent_transit,
1592 const RoutingDimension* base_dimension, int64_t slack_max,
1593 int64_t vehicle_capacity,
bool fix_start_cumul_to_zero,
1594 const std::string&
name) {
1595 std::vector<int> pure_transits(vehicles_, pure_transit);
1596 std::vector<int> dependent_transits(vehicles_, dependent_transit);
1597 std::vector<int64_t> vehicle_capacities(vehicles_, vehicle_capacity);
1598 return AddDimensionDependentDimensionWithVehicleCapacityInternal(
1599 pure_transits, dependent_transits, base_dimension, slack_max,
1600 std::move(vehicle_capacities), fix_start_cumul_to_zero,
name);
1604 const std::function<int64_t(int64_t)>& f, int64_t domain_start,
1605 int64_t domain_end) {
1606 const std::function<int64_t(int64_t)> g = [&f](int64_t x) {
1616 std::vector<std::string> dimension_names;
1617 for (
const auto& dimension_name_index : dimension_name_to_index_) {
1618 dimension_names.push_back(dimension_name_index.first);
1620 std::sort(dimension_names.begin(), dimension_names.end());
1621 return dimension_names;
1626 const int optimizer_index = GetGlobalCumulOptimizerIndex(dimension);
1627 return optimizer_index < 0
1629 : global_dimension_optimizers_[optimizer_index].lp_optimizer.get();
1634 const int optimizer_index = GetGlobalCumulOptimizerIndex(dimension);
1635 return optimizer_index < 0
1637 : global_dimension_optimizers_[optimizer_index].mp_optimizer.get();
1640 int RoutingModel::GetGlobalCumulOptimizerIndex(
1641 const RoutingDimension& dimension)
const {
1643 const DimensionIndex dim_index = GetDimensionIndex(dimension.name());
1644 if (dim_index < 0 || dim_index >= global_optimizer_index_.
size() ||
1645 global_optimizer_index_[dim_index] < 0) {
1648 const int optimizer_index = global_optimizer_index_[dim_index];
1649 DCHECK_LT(optimizer_index, global_dimension_optimizers_.size());
1650 return optimizer_index;
1655 const int optimizer_index = GetLocalCumulOptimizerIndex(dimension);
1656 return optimizer_index < 0
1658 : local_dimension_optimizers_[optimizer_index].lp_optimizer.get();
1663 const int optimizer_index = GetLocalCumulOptimizerIndex(dimension);
1664 return optimizer_index < 0
1666 : local_dimension_optimizers_[optimizer_index].mp_optimizer.get();
1669 int RoutingModel::GetLocalCumulOptimizerIndex(
1670 const RoutingDimension& dimension)
const {
1672 const DimensionIndex dim_index = GetDimensionIndex(dimension.name());
1673 if (dim_index < 0 || dim_index >= local_optimizer_index_.
size() ||
1674 local_optimizer_index_[dim_index] < 0) {
1677 const int optimizer_index = local_optimizer_index_[dim_index];
1678 DCHECK_LT(optimizer_index, local_dimension_optimizers_.size());
1679 return optimizer_index;
1683 return dimension_name_to_index_.contains(dimension_name);
1687 const std::string& dimension_name)
const {
1693 const std::string& dimension_name)
const {
1694 return *dimensions_[
gtl::FindOrDie(dimension_name_to_index_, dimension_name)];
1698 const std::string& dimension_name)
const {
1701 return dimensions_[
index];
1707 ResourceGroup::Attributes::Attributes()
1708 : start_domain_(
Domain::AllValues()), end_domain_(
Domain::AllValues()) {
1714 : start_domain_(std::move(start_domain)),
1715 end_domain_(std::move(end_domain)) {}
1723 GetDefaultAttributes());
1726 void ResourceGroup::Resource::SetDimensionAttributes(
1728 DCHECK(dimension_attributes_.empty())
1729 <<
"As of 2021/07, each resource can only constrain a single dimension.";
1732 model_->GetDimensionIndex(dimension->
name());
1734 DCHECK(!dimension_attributes_.contains(dimension_index));
1735 dimension_attributes_[dimension_index] = std::move(attributes);
1740 static const Attributes*
const kAttributes =
new Attributes();
1741 return *kAttributes;
1745 DCHECK_EQ(resource_groups_.size(), resource_vars_.size());
1747 resource_groups_.push_back(std::make_unique<ResourceGroup>(
this));
1750 const int rg_index = resource_groups_.size() - 1;
1751 resource_vars_.push_back({});
1753 absl::StrCat(
"Resources[", rg_index,
"]"),
1754 &resource_vars_.back());
1760 resources_.push_back(Resource(model_));
1761 resources_.back().SetDimensionAttributes(std::move(attributes), dimension);
1764 model_->GetDimensionIndex(dimension->
name());
1766 affected_dimension_indices_.insert(dimension_index);
1768 DCHECK_EQ(affected_dimension_indices_.size(), 1)
1769 <<
"As of 2021/07, each ResourceGroup can only affect a single "
1770 "RoutingDimension at a time.";
1772 return resources_.size() - 1;
1776 DCHECK_LT(vehicle, vehicle_requires_resource_.size());
1777 if (vehicle_requires_resource_[vehicle])
return;
1778 vehicle_requires_resource_[vehicle] =
true;
1779 vehicles_requiring_resource_.push_back(vehicle);
1787 return dimension_resource_group_indices_[dim];
1791 CHECK_LT(0, vehicles_);
1792 for (
int i = 0; i < vehicles_; ++i) {
1799 CHECK_LT(vehicle, vehicles_);
1800 CHECK_LT(evaluator_index, transit_evaluators_.size());
1801 vehicle_to_transit_cost_[vehicle] = evaluator_index;
1805 for (
int i = 0; i < vehicles_; ++i) {
1811 CHECK_LT(vehicle, vehicles_);
1812 return fixed_cost_of_vehicle_[vehicle];
1816 CHECK_LT(vehicle, vehicles_);
1818 fixed_cost_of_vehicle_[vehicle] =
cost;
1822 int64_t linear_cost_factor, int64_t quadratic_cost_factor) {
1823 for (
int v = 0; v < vehicles_; v++) {
1830 int64_t linear_cost_factor, int64_t quadratic_cost_factor,
int vehicle) {
1831 CHECK_LT(vehicle, vehicles_);
1832 DCHECK_GE(linear_cost_factor, 0);
1833 DCHECK_GE(quadratic_cost_factor, 0);
1834 if (linear_cost_factor + quadratic_cost_factor > 0) {
1835 vehicle_amortized_cost_factors_set_ =
true;
1837 linear_cost_factor_of_vehicle_[vehicle] = linear_cost_factor;
1838 quadratic_cost_factor_of_vehicle_[vehicle] = quadratic_cost_factor;
1844 struct CostClassComparator {
1845 bool operator()(
const RoutingModel::CostClass&
a,
1846 const RoutingModel::CostClass&
b)
const {
1851 struct VehicleClassComparator {
1852 bool operator()(
const RoutingModel::VehicleClass&
a,
1853 const RoutingModel::VehicleClass&
b)
const {
1863 void RoutingModel::ComputeCostClasses(
1864 const RoutingSearchParameters& ) {
1866 cost_classes_.reserve(vehicles_);
1867 cost_classes_.clear();
1868 cost_class_index_of_vehicle_.assign(vehicles_,
CostClassIndex(-1));
1869 std::map<CostClass, CostClassIndex, CostClassComparator> cost_class_map;
1872 const CostClass zero_cost_class(0);
1873 cost_classes_.push_back(zero_cost_class);
1874 DCHECK_EQ(cost_classes_[kCostClassIndexOfZeroCost].evaluator_index, 0);
1875 cost_class_map[zero_cost_class] = kCostClassIndexOfZeroCost;
1880 has_vehicle_with_zero_cost_class_ =
false;
1881 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1882 CostClass cost_class(vehicle_to_transit_cost_[vehicle]);
1886 const int64_t coeff =
1888 if (coeff == 0)
continue;
1889 cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1892 std::sort(cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1894 cost_class.dimension_transit_evaluator_class_and_cost_coefficient
1900 if (cost_class_index == kCostClassIndexOfZeroCost) {
1901 has_vehicle_with_zero_cost_class_ =
true;
1902 }
else if (cost_class_index == num_cost_classes) {
1903 cost_classes_.push_back(cost_class);
1905 cost_class_index_of_vehicle_[vehicle] = cost_class_index;
1919 costs_are_homogeneous_across_vehicles_ &= has_vehicle_with_zero_cost_class_
1926 return std::tie(
a.cost_class_index,
a.fixed_cost,
a.used_when_empty,
1927 a.start_equivalence_class,
a.end_equivalence_class,
1928 a.unvisitable_nodes_fprint,
a.dimension_start_cumuls_min,
1929 a.dimension_start_cumuls_max,
a.dimension_end_cumuls_min,
1930 a.dimension_end_cumuls_max,
a.dimension_capacities,
1931 a.dimension_evaluator_classes,
1932 a.required_resource_group_indices) <
1933 std::tie(
b.cost_class_index,
b.fixed_cost,
b.used_when_empty,
1934 b.start_equivalence_class,
b.end_equivalence_class,
1935 b.unvisitable_nodes_fprint,
b.dimension_start_cumuls_min,
1936 b.dimension_start_cumuls_max,
b.dimension_end_cumuls_min,
1937 b.dimension_end_cumuls_max,
b.dimension_capacities,
1938 b.dimension_evaluator_classes,
1939 b.required_resource_group_indices);
1942 void RoutingModel::ComputeVehicleClasses() {
1943 vehicle_classes_.reserve(vehicles_);
1944 vehicle_classes_.clear();
1946 std::map<VehicleClass, VehicleClassIndex, VehicleClassComparator>
1948 const int nodes_unvisitability_num_bytes = (vehicle_vars_.size() + 7) / 8;
1949 std::unique_ptr<char[]> nodes_unvisitability_bitmask(
1950 new char[nodes_unvisitability_num_bytes]);
1951 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
1953 vehicle_class.cost_class_index = cost_class_index_of_vehicle_[vehicle];
1955 vehicle_class.used_when_empty = vehicle_used_when_empty_[vehicle];
1957 index_to_equivalence_class_[
Start(vehicle)];
1959 index_to_equivalence_class_[
End(vehicle)];
1963 start_cumul_var->
Min());
1965 start_cumul_var->
Max());
1974 memset(nodes_unvisitability_bitmask.get(), 0,
1975 nodes_unvisitability_num_bytes);
1977 IntVar*
const vehicle_var = vehicle_vars_[
index];
1979 (!vehicle_var->Contains(vehicle) ||
1981 nodes_unvisitability_bitmask[
index / CHAR_BIT] |= 1U
1982 << (
index % CHAR_BIT);
1986 nodes_unvisitability_bitmask.get(), nodes_unvisitability_num_bytes);
1987 for (
int rg_index = 0; rg_index < resource_groups_.size(); rg_index++) {
1989 vehicle_class.required_resource_group_indices.push_back(rg_index);
1996 if (vehicle_class_index == num_vehicle_classes) {
1999 vehicle_class_index_of_vehicle_[vehicle] = vehicle_class_index;
2003 void RoutingModel::ComputeVehicleTypes() {
2004 const int nodes_squared = nodes_ * nodes_;
2005 std::vector<int>& type_index_of_vehicle =
2006 vehicle_type_container_.type_index_of_vehicle;
2007 std::vector<std::set<VehicleTypeContainer::VehicleClassEntry>>&
2008 sorted_vehicle_classes_per_type =
2009 vehicle_type_container_.sorted_vehicle_classes_per_type;
2010 std::vector<std::deque<int>>& vehicles_per_vehicle_class =
2011 vehicle_type_container_.vehicles_per_vehicle_class;
2013 type_index_of_vehicle.resize(vehicles_);
2014 sorted_vehicle_classes_per_type.clear();
2015 sorted_vehicle_classes_per_type.reserve(vehicles_);
2016 vehicles_per_vehicle_class.clear();
2019 absl::flat_hash_map<int64_t, int> type_to_type_index;
2021 for (
int v = 0; v < vehicles_; v++) {
2022 const int start = manager_.IndexToNode(
Start(v)).value();
2023 const int end = manager_.IndexToNode(
End(v)).value();
2025 const int64_t type = cost_class * nodes_squared +
start * nodes_ +
end;
2027 const auto& vehicle_type_added = type_to_type_index.insert(
2028 std::make_pair(type, type_to_type_index.size()));
2030 const int index = vehicle_type_added.first->second;
2033 const VehicleTypeContainer::VehicleClassEntry class_entry = {
2036 if (vehicle_type_added.second) {
2038 DCHECK_EQ(sorted_vehicle_classes_per_type.size(),
index);
2039 sorted_vehicle_classes_per_type.push_back({class_entry});
2042 DCHECK_LT(
index, sorted_vehicle_classes_per_type.size());
2043 sorted_vehicle_classes_per_type[
index].insert(class_entry);
2046 type_index_of_vehicle[v] =
index;
2050 void RoutingModel::FinalizeVisitTypes() {
2056 single_nodes_of_type_.clear();
2057 single_nodes_of_type_.resize(num_visit_types_);
2058 pair_indices_of_type_.clear();
2059 pair_indices_of_type_.resize(num_visit_types_);
2060 std::vector<absl::flat_hash_set<int>> pair_indices_added_for_type(
2065 if (visit_type < 0) {
2068 const std::vector<std::pair<int, int>>& pickup_index_pairs =
2069 index_to_pickup_index_pairs_[
index];
2070 const std::vector<std::pair<int, int>>& delivery_index_pairs =
2071 index_to_delivery_index_pairs_[
index];
2072 if (pickup_index_pairs.empty() && delivery_index_pairs.empty()) {
2073 single_nodes_of_type_[visit_type].push_back(
index);
2075 for (
const std::vector<std::pair<int, int>>* index_pairs :
2076 {&pickup_index_pairs, &delivery_index_pairs}) {
2077 for (
const std::pair<int, int>& index_pair : *index_pairs) {
2078 const int pair_index = index_pair.first;
2079 if (pair_indices_added_for_type[visit_type].insert(pair_index).second) {
2080 pair_indices_of_type_[visit_type].push_back(pair_index);
2086 TopologicallySortVisitTypes();
2089 void RoutingModel::TopologicallySortVisitTypes() {
2090 if (!has_same_vehicle_type_requirements_ &&
2091 !has_temporal_type_requirements_) {
2094 std::vector<std::pair<double, double>> type_requirement_tightness(
2095 num_visit_types_, {0, 0});
2096 std::vector<absl::flat_hash_set<int>> type_to_dependent_types(
2098 SparseBitset<> types_in_requirement_graph(num_visit_types_);
2099 std::vector<int> in_degree(num_visit_types_, 0);
2100 for (
int type = 0; type < num_visit_types_; type++) {
2101 int num_alternative_required_types = 0;
2102 int num_required_sets = 0;
2103 for (
const std::vector<absl::flat_hash_set<int>>*
2104 required_type_alternatives :
2105 {&required_type_alternatives_when_adding_type_index_[type],
2106 &required_type_alternatives_when_removing_type_index_[type],
2107 &same_vehicle_required_type_alternatives_per_type_index_[type]}) {
2108 for (
const absl::flat_hash_set<int>& alternatives :
2109 *required_type_alternatives) {
2110 types_in_requirement_graph.Set(type);
2111 num_required_sets++;
2112 for (
int required_type : alternatives) {
2113 type_requirement_tightness[required_type].second +=
2114 1.0 / alternatives.size();
2115 types_in_requirement_graph.Set(required_type);
2116 num_alternative_required_types++;
2117 if (type_to_dependent_types[required_type].insert(type).second) {
2123 if (num_alternative_required_types > 0) {
2124 type_requirement_tightness[type].first += 1.0 * num_required_sets *
2126 num_alternative_required_types;
2131 topologically_sorted_visit_types_.clear();
2132 std::vector<int> current_types_with_zero_indegree;
2133 for (
int type : types_in_requirement_graph.PositionsSetAtLeastOnce()) {
2134 DCHECK(type_requirement_tightness[type].first > 0 ||
2135 type_requirement_tightness[type].second > 0);
2136 if (in_degree[type] == 0) {
2137 current_types_with_zero_indegree.push_back(type);
2141 int num_types_added = 0;
2142 while (!current_types_with_zero_indegree.empty()) {
2145 topologically_sorted_visit_types_.push_back({});
2146 std::vector<int>& topological_group =
2147 topologically_sorted_visit_types_.back();
2148 std::vector<int> next_types_with_zero_indegree;
2149 for (
int type : current_types_with_zero_indegree) {
2150 topological_group.push_back(type);
2152 for (
int dependent_type : type_to_dependent_types[type]) {
2153 DCHECK_GT(in_degree[dependent_type], 0);
2154 if (--in_degree[dependent_type] == 0) {
2155 next_types_with_zero_indegree.push_back(dependent_type);
2166 std::sort(topological_group.begin(), topological_group.end(),
2167 [&type_requirement_tightness](
int type1,
int type2) {
2168 const auto& tightness1 = type_requirement_tightness[type1];
2169 const auto& tightness2 = type_requirement_tightness[type2];
2170 return tightness1 > tightness2 ||
2171 (tightness1 == tightness2 && type1 < type2);
2174 current_types_with_zero_indegree.swap(next_types_with_zero_indegree);
2177 const int num_types_in_requirement_graph =
2178 types_in_requirement_graph.NumberOfSetCallsWithDifferentArguments();
2179 DCHECK_LE(num_types_added, num_types_in_requirement_graph);
2180 if (num_types_added < num_types_in_requirement_graph) {
2182 topologically_sorted_visit_types_.clear();
2187 const std::vector<int64_t>& indices, int64_t penalty,
2188 int64_t max_cardinality) {
2189 CHECK_GE(max_cardinality, 1);
2190 for (
int i = 0; i < indices.size(); ++i) {
2195 disjunctions_.push_back({indices, {penalty, max_cardinality}});
2196 for (
const int64_t
index : indices) {
2197 index_to_disjunctions_[
index].push_back(disjunction_index);
2199 return disjunction_index;
2203 for (
const auto& [indices,
value] : disjunctions_) {
2210 for (
const auto& [indices,
value] : disjunctions_) {
2211 if (indices.size() >
value.max_cardinality)
return true;
2216 std::vector<std::pair<int64_t, int64_t>>
2218 std::vector<std::pair<int64_t, int64_t>> var_index_pairs;
2219 for (
const Disjunction& disjunction : disjunctions_) {
2220 const std::vector<int64_t>&
var_indices = disjunction.indices;
2224 if (index_to_disjunctions_[v0].size() == 1 &&
2225 index_to_disjunctions_[v1].size() == 1) {
2230 std::sort(var_index_pairs.begin(), var_index_pairs.end());
2231 return var_index_pairs;
2236 for (Disjunction& disjunction : disjunctions_) {
2237 bool has_one_potentially_active_var =
false;
2238 for (
const int64_t var_index : disjunction.indices) {
2240 has_one_potentially_active_var =
true;
2244 if (!has_one_potentially_active_var) {
2245 disjunction.value.max_cardinality = 0;
2251 const std::vector<int64_t>& indices = disjunctions_[disjunction].indices;
2252 const int indices_size = indices.size();
2253 std::vector<IntVar*> disjunction_vars(indices_size);
2254 for (
int i = 0; i < indices_size; ++i) {
2255 const int64_t
index = indices[i];
2259 const int64_t max_cardinality =
2260 disjunctions_[disjunction].value.max_cardinality;
2261 IntVar* no_active_var = solver_->MakeBoolVar();
2262 IntVar* number_active_vars = solver_->MakeIntVar(0, max_cardinality);
2263 solver_->AddConstraint(
2264 solver_->MakeSumEquality(disjunction_vars, number_active_vars));
2265 solver_->AddConstraint(solver_->MakeIsDifferentCstCt(
2266 number_active_vars, max_cardinality, no_active_var));
2267 const int64_t penalty = disjunctions_[disjunction].value.penalty;
2269 no_active_var->SetMax(0);
2272 return solver_->MakeProd(no_active_var, penalty)->Var();
2277 const std::vector<int64_t>& indices, int64_t
cost) {
2278 if (!indices.empty()) {
2279 ValuedNodes<int64_t> same_vehicle_cost;
2280 for (
const int64_t
index : indices) {
2281 same_vehicle_cost.indices.push_back(
index);
2283 same_vehicle_cost.value =
cost;
2284 same_vehicle_costs_.push_back(same_vehicle_cost);
2290 auto& allowed_vehicles = allowed_vehicles_[
index];
2291 allowed_vehicles.clear();
2293 allowed_vehicles.insert(vehicle);
2298 AddPickupAndDeliverySetsInternal({pickup}, {delivery});
2305 AddPickupAndDeliverySetsInternal(
2308 pickup_delivery_disjunctions_.push_back(
2309 {pickup_disjunction, delivery_disjunction});
2312 void RoutingModel::AddPickupAndDeliverySetsInternal(
2313 const std::vector<int64_t>& pickups,
2314 const std::vector<int64_t>& deliveries) {
2315 if (pickups.empty() || deliveries.empty()) {
2318 const int64_t size =
Size();
2319 const int pair_index = pickup_delivery_pairs_.size();
2320 for (
int pickup_index = 0; pickup_index < pickups.size(); pickup_index++) {
2321 const int64_t pickup = pickups[pickup_index];
2322 CHECK_LT(pickup, size);
2323 index_to_pickup_index_pairs_[pickup].emplace_back(pair_index, pickup_index);
2325 for (
int delivery_index = 0; delivery_index < deliveries.size();
2327 const int64_t delivery = deliveries[delivery_index];
2328 CHECK_LT(delivery, size);
2329 index_to_delivery_index_pairs_[delivery].emplace_back(pair_index,
2332 pickup_delivery_pairs_.push_back({pickups, deliveries});
2336 int64_t node_index)
const {
2337 CHECK_LT(node_index, index_to_pickup_index_pairs_.size());
2338 return index_to_pickup_index_pairs_[node_index];
2342 int64_t node_index)
const {
2343 CHECK_LT(node_index, index_to_delivery_index_pairs_.size());
2344 return index_to_delivery_index_pairs_[node_index];
2349 CHECK_LT(vehicle, vehicles_);
2350 vehicle_pickup_delivery_policy_[vehicle] = policy;
2355 CHECK_LT(0, vehicles_);
2356 for (
int i = 0; i < vehicles_; ++i) {
2363 CHECK_LT(vehicle, vehicles_);
2364 return vehicle_pickup_delivery_policy_[vehicle];
2369 for (
int i = 0; i <
Nexts().size(); ++i) {
2379 IntVar* RoutingModel::CreateSameVehicleCost(
int vehicle_index) {
2380 const std::vector<int64_t>& indices =
2381 same_vehicle_costs_[vehicle_index].indices;
2382 CHECK(!indices.empty());
2383 std::vector<IntVar*> vehicle_counts;
2384 solver_->MakeIntVarArray(vehicle_vars_.size() + 1, 0, indices.size() + 1,
2386 std::vector<int64_t> vehicle_values(vehicle_vars_.size() + 1);
2387 for (
int i = 0; i < vehicle_vars_.size(); ++i) {
2388 vehicle_values[i] = i;
2390 vehicle_values[vehicle_vars_.size()] = -1;
2391 std::vector<IntVar*> vehicle_vars;
2392 vehicle_vars.reserve(indices.size());
2393 for (
const int64_t
index : indices) {
2394 vehicle_vars.push_back(vehicle_vars_[
index]);
2396 solver_->AddConstraint(solver_->MakeDistribute(vehicle_vars, vehicle_counts));
2397 std::vector<IntVar*> vehicle_used;
2398 for (
int i = 0; i < vehicle_vars_.size() + 1; ++i) {
2399 vehicle_used.push_back(
2400 solver_->MakeIsGreaterOrEqualCstVar(vehicle_counts[i], 1));
2402 vehicle_used.push_back(solver_->MakeIntConst(-1));
2404 ->MakeProd(solver_->MakeMax(solver_->MakeSum(vehicle_used), 0),
2405 same_vehicle_costs_[vehicle_index].value)
2410 extra_operators_.push_back(ls_operator);
2419 void RoutingModel::AppendHomogeneousArcCosts(
2420 const RoutingSearchParameters&
parameters,
int node_index,
2421 std::vector<IntVar*>* cost_elements) {
2422 CHECK(cost_elements !=
nullptr);
2423 const auto arc_cost_evaluator = [
this, node_index](int64_t next_index) {
2430 IntVar*
const base_cost_var =
2432 solver_->AddConstraint(solver_->MakeLightElement(
2433 arc_cost_evaluator, base_cost_var, nexts_[node_index],
2434 [
this]() { return enable_deep_serialization_; }));
2436 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
2437 cost_elements->push_back(
var);
2439 IntExpr*
const expr =
2440 solver_->MakeElement(arc_cost_evaluator, nexts_[node_index]);
2441 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
2442 cost_elements->push_back(
var);
2446 void RoutingModel::AppendArcCosts(
const RoutingSearchParameters&
parameters,
2448 std::vector<IntVar*>* cost_elements) {
2449 CHECK(cost_elements !=
nullptr);
2450 DCHECK_GT(vehicles_, 0);
2455 IntVar*
const base_cost_var =
2457 solver_->AddConstraint(solver_->MakeLightElement(
2458 [
this, node_index](int64_t to, int64_t vehicle) {
2459 return GetArcCostForVehicle(node_index, to, vehicle);
2461 base_cost_var, nexts_[node_index], vehicle_vars_[node_index],
2462 [
this]() { return enable_deep_serialization_; }));
2464 solver_->MakeProd(base_cost_var, active_[node_index])->Var();
2465 cost_elements->push_back(
var);
2467 IntVar*
const vehicle_class_var =
2470 [
this](int64_t
index) {
2471 return SafeGetCostClassInt64OfVehicle(
index);
2473 vehicle_vars_[node_index])
2475 IntExpr*
const expr = solver_->MakeElement(
2479 nexts_[node_index], vehicle_class_var);
2480 IntVar*
const var = solver_->MakeProd(expr, active_[node_index])->Var();
2481 cost_elements->push_back(
var);
2485 int RoutingModel::GetVehicleStartClass(int64_t start_index)
const {
2493 std::string RoutingModel::FindErrorInSearchParametersForModel(
2494 const RoutingSearchParameters& search_parameters)
const {
2496 search_parameters.first_solution_strategy();
2497 if (GetFirstSolutionDecisionBuilder(search_parameters) ==
nullptr) {
2498 return absl::StrCat(
2499 "Undefined first solution strategy: ",
2500 FirstSolutionStrategy::Value_Name(first_solution_strategy),
2501 " (int value: ", first_solution_strategy,
")");
2503 if (search_parameters.first_solution_strategy() ==
2504 FirstSolutionStrategy::SWEEP &&
2506 return "Undefined sweep arranger for ROUTING_SWEEP strategy.";
2511 void RoutingModel::QuietCloseModel() {
2522 same_vehicle_components_.SetNumberOfNodes(
model->Size());
2523 for (
const std::string&
name :
model->GetAllDimensionNames()) {
2525 const std::vector<IntVar*>& cumuls = dimension->
cumuls();
2526 for (
int i = 0; i < cumuls.size(); ++i) {
2527 cumul_to_dim_indices_[cumuls[i]] = {dimension, i};
2530 const std::vector<IntVar*>& vehicle_vars =
model->VehicleVars();
2531 for (
int i = 0; i < vehicle_vars.size(); ++i) {
2532 vehicle_var_to_indices_[vehicle_vars[i]] = i;
2534 RegisterInspectors();
2537 void EndVisitModel(
const std::string& )
override {
2538 const std::vector<int> node_to_same_vehicle_component_id =
2539 same_vehicle_components_.GetComponentIds();
2540 model_->InitSameVehicleGroups(
2541 same_vehicle_components_.GetNumberOfComponents());
2542 for (
int node = 0; node < model_->Size(); ++node) {
2543 model_->SetSameVehicleGroup(node,
2544 node_to_same_vehicle_component_id[node]);
2549 void EndVisitConstraint(
const std::string& type_name,
2553 void VisitIntegerExpressionArgument(
const std::string& type_name,
2554 IntExpr*
const expr)
override {
2556 [](
const IntExpr*) {})(expr);
2558 void VisitIntegerArrayArgument(
const std::string& arg_name,
2559 const std::vector<int64_t>& values)
override {
2561 [](
const std::vector<int64_t>&) {})(values);
2565 using ExprInspector = std::function<void(
const IntExpr*)>;
2566 using ArrayInspector = std::function<void(
const std::vector<int64_t>&)>;
2567 using ConstraintInspector = std::function<void()>;
2569 void RegisterInspectors() {
2570 expr_inspectors_[kExpressionArgument] = [
this](
const IntExpr* expr) {
2573 expr_inspectors_[kLeftArgument] = [
this](
const IntExpr* expr) {
2576 expr_inspectors_[kRightArgument] = [
this](
const IntExpr* expr) {
2579 array_inspectors_[kStartsArgument] =
2580 [
this](
const std::vector<int64_t>& int_array) {
2581 starts_argument_ = int_array;
2583 array_inspectors_[kEndsArgument] =
2584 [
this](
const std::vector<int64_t>& int_array) {
2585 ends_argument_ = int_array;
2587 constraint_inspectors_[kNotMember] = [
this]() {
2588 std::pair<RoutingDimension*, int> dim_index;
2591 const int index = dim_index.second;
2592 dimension->forbidden_intervals_[
index].InsertIntervals(starts_argument_,
2594 VLOG(2) << dimension->name() <<
" " <<
index <<
": "
2595 << dimension->forbidden_intervals_[
index].DebugString();
2598 starts_argument_.clear();
2599 ends_argument_.clear();
2601 constraint_inspectors_[kEquality] = [
this]() {
2603 int right_index = 0;
2604 if (
gtl::FindCopy(vehicle_var_to_indices_, left_, &left_index) &&
2605 gtl::FindCopy(vehicle_var_to_indices_, right_, &right_index)) {
2606 VLOG(2) <<
"Vehicle variables for " << left_index <<
" and "
2607 << right_index <<
" are equal.";
2608 same_vehicle_components_.AddEdge(left_index, right_index);
2613 constraint_inspectors_[kLessOrEqual] = [
this]() {
2614 std::pair<RoutingDimension*, int> left_index;
2615 std::pair<RoutingDimension*, int> right_index;
2616 if (
gtl::FindCopy(cumul_to_dim_indices_, left_, &left_index) &&
2617 gtl::FindCopy(cumul_to_dim_indices_, right_, &right_index)) {
2619 if (dimension == right_index.first) {
2620 VLOG(2) <<
"For dimension " << dimension->name() <<
", cumul for "
2621 << left_index.second <<
" is less than " << right_index.second
2623 dimension->path_precedence_graph_.AddArc(left_index.second,
2624 right_index.second);
2634 absl::flat_hash_map<const IntExpr*, std::pair<RoutingDimension*, int>>
2635 cumul_to_dim_indices_;
2636 absl::flat_hash_map<const IntExpr*, int> vehicle_var_to_indices_;
2637 absl::flat_hash_map<std::string, ExprInspector> expr_inspectors_;
2638 absl::flat_hash_map<std::string, ArrayInspector> array_inspectors_;
2639 absl::flat_hash_map<std::string, ConstraintInspector> constraint_inspectors_;
2640 const IntExpr*
expr_ =
nullptr;
2641 const IntExpr* left_ =
nullptr;
2642 const IntExpr* right_ =
nullptr;
2643 std::vector<int64_t> starts_argument_;
2644 std::vector<int64_t> ends_argument_;
2647 void RoutingModel::DetectImplicitPickupAndDeliveries() {
2648 std::vector<int> non_pickup_delivery_nodes;
2649 for (
int node = 0; node <
Size(); ++node) {
2652 non_pickup_delivery_nodes.push_back(node);
2656 std::set<std::pair<int64_t, int64_t>> implicit_pickup_deliveries;
2658 if (dimension->class_evaluators_.size() != 1) {
2663 if (transit ==
nullptr)
continue;
2664 absl::flat_hash_map<int64_t, std::vector<int64_t>> nodes_by_positive_demand;
2665 absl::flat_hash_map<int64_t, std::vector<int64_t>> nodes_by_negative_demand;
2666 for (
int node : non_pickup_delivery_nodes) {
2667 const int64_t
demand = transit(node);
2669 nodes_by_positive_demand[
demand].push_back(node);
2671 nodes_by_negative_demand[-
demand].push_back(node);
2674 for (
const auto& [
demand, positive_nodes] : nodes_by_positive_demand) {
2675 const std::vector<int64_t>*
const negative_nodes =
2677 if (negative_nodes !=
nullptr) {
2678 for (int64_t positive_node : positive_nodes) {
2679 for (int64_t negative_node : *negative_nodes) {
2680 implicit_pickup_deliveries.insert({positive_node, negative_node});
2686 implicit_pickup_delivery_pairs_without_alternatives_.clear();
2687 for (
auto [pickup, delivery] : implicit_pickup_deliveries) {
2688 implicit_pickup_delivery_pairs_without_alternatives_.emplace_back(
2689 std::vector<int64_t>({pickup}), std::vector<int64_t>({delivery}));
2696 if (!error.empty()) {
2698 LOG(ERROR) <<
"Invalid RoutingSearchParameters: " << error;
2702 LOG(WARNING) <<
"Model already closed";
2708 dimension->CloseModel(UsesLightPropagation(
parameters));
2711 dimension_resource_group_indices_.resize(dimensions_.size());
2712 for (
int rg_index = 0; rg_index < resource_groups_.size(); rg_index++) {
2713 const ResourceGroup& resource_group = *resource_groups_[rg_index];
2714 if (resource_group.GetVehiclesRequiringAResource().empty())
continue;
2716 resource_group.GetAffectedDimensionIndices()) {
2717 dimension_resource_group_indices_[dim_index].push_back(rg_index);
2722 ComputeVehicleClasses();
2723 ComputeVehicleTypes();
2724 FinalizeVisitTypes();
2725 vehicle_start_class_callback_ = [
this](int64_t
start) {
2726 return GetVehicleStartClass(
start);
2729 AddNoCycleConstraintInternal();
2731 const int size =
Size();
2734 for (
int i = 0; i < vehicles_; ++i) {
2736 const int64_t
end =
End(i);
2737 solver_->AddConstraint(
2738 solver_->MakeEquality(vehicle_vars_[
start], solver_->MakeIntConst(i)));
2739 solver_->AddConstraint(
2740 solver_->MakeEquality(vehicle_vars_[
end], solver_->MakeIntConst(i)));
2741 solver_->AddConstraint(
2742 solver_->MakeIsDifferentCstCt(nexts_[
start],
end, vehicle_active_[i]));
2743 if (vehicle_used_when_empty_[i]) {
2744 vehicle_route_considered_[i]->SetMin(1);
2746 solver_->AddConstraint(solver_->MakeEquality(
2747 vehicle_active_[i], vehicle_route_considered_[i]));
2752 if (vehicles_ > max_active_vehicles_) {
2753 solver_->AddConstraint(
2754 solver_->MakeSumLessOrEqual(vehicle_active_, max_active_vehicles_));
2762 if (vehicles_ > 1) {
2763 std::vector<IntVar*> zero_transit(size, solver_->MakeIntConst(0));
2764 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
2765 nexts_, active_, vehicle_vars_, zero_transit));
2770 for (
int i = 0; i < size; ++i) {
2772 active_[i]->SetValue(1);
2778 const absl::flat_hash_set<VisitTypePolicy>*
const infeasible_policies =
2780 if (infeasible_policies !=
nullptr &&
2781 infeasible_policies->contains(index_to_type_policy_[i])) {
2782 active_[i]->SetValue(0);
2787 for (
int i = 0; i < allowed_vehicles_.size(); ++i) {
2788 const auto& allowed_vehicles = allowed_vehicles_[i];
2789 if (!allowed_vehicles.empty()) {
2791 vehicles.reserve(allowed_vehicles.size() + 1);
2793 for (
int vehicle : allowed_vehicles) {
2801 for (
int i = 0; i < size; ++i) {
2803 solver_->AddConstraint(solver_->RevAlloc(
new DifferentFromValues(
2804 solver_.get(), nexts_[i], paths_metadata_.Starts())));
2806 solver_->AddConstraint(
2807 solver_->MakeIsDifferentCstCt(nexts_[i], i, active_[i]));
2812 for (
int i = 0; i < size; ++i) {
2813 solver_->AddConstraint(
2814 solver_->MakeIsDifferentCstCt(vehicle_vars_[i], -1, active_[i]));
2818 solver_->AddConstraint(
2819 solver_->RevAlloc(
new TypeRegulationsConstraint(*
this)));
2823 for (
int i = 0; i < vehicles_; ++i) {
2824 std::vector<int64_t> forbidden_ends;
2825 forbidden_ends.reserve(vehicles_ - 1);
2826 for (
int j = 0; j < vehicles_; ++j) {
2828 forbidden_ends.push_back(
End(j));
2831 solver_->AddConstraint(solver_->RevAlloc(
new DifferentFromValues(
2832 solver_.get(), nexts_[
Start(i)], std::move(forbidden_ends))));
2836 for (
const int64_t
end : paths_metadata_.Ends()) {
2837 is_bound_to_end_[
end]->SetValue(1);
2840 std::vector<IntVar*> cost_elements;
2842 if (vehicles_ > 0) {
2843 for (
int node_index = 0; node_index < size; ++node_index) {
2845 AppendHomogeneousArcCosts(
parameters, node_index, &cost_elements);
2847 AppendArcCosts(
parameters, node_index, &cost_elements);
2850 if (vehicle_amortized_cost_factors_set_) {
2851 std::vector<IntVar*> route_lengths;
2852 solver_->MakeIntVarArray(vehicles_, 0, size, &route_lengths);
2853 solver_->AddConstraint(
2854 solver_->MakeDistribute(vehicle_vars_, route_lengths));
2855 std::vector<IntVar*> vehicle_used;
2856 for (
int i = 0; i < vehicles_; i++) {
2858 vehicle_used.push_back(
2859 solver_->MakeIsGreaterCstVar(route_lengths[i], 2));
2862 ->MakeProd(solver_->MakeOpposite(solver_->MakeSquare(
2863 solver_->MakeSum(route_lengths[i], -2))),
2864 quadratic_cost_factor_of_vehicle_[i])
2866 cost_elements.push_back(
var);
2868 IntVar*
const vehicle_usage_cost =
2869 solver_->MakeScalProd(vehicle_used, linear_cost_factor_of_vehicle_)
2871 cost_elements.push_back(vehicle_usage_cost);
2876 dimension->SetupGlobalSpanCost(&cost_elements);
2877 dimension->SetupSlackAndDependentTransitCosts();
2878 const std::vector<int64_t>& span_costs =
2879 dimension->vehicle_span_cost_coefficients();
2880 const std::vector<int64_t>& span_ubs =
2881 dimension->vehicle_span_upper_bounds();
2882 const bool has_span_constraint =
2883 std::any_of(span_costs.begin(), span_costs.end(),
2884 [](int64_t coeff) { return coeff != 0; }) ||
2885 std::any_of(span_ubs.begin(), span_ubs.end(),
2887 return value < std::numeric_limits<int64_t>::max();
2889 dimension->HasSoftSpanUpperBounds() ||
2890 dimension->HasQuadraticCostSoftSpanUpperBounds();
2891 if (has_span_constraint) {
2892 std::vector<IntVar*> spans(
vehicles(),
nullptr);
2893 std::vector<IntVar*> total_slacks(
vehicles(),
nullptr);
2895 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2897 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2899 if (span_costs[vehicle] != 0) {
2900 total_slacks[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle],
"");
2903 if (dimension->HasSoftSpanUpperBounds()) {
2904 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2905 if (spans[vehicle])
continue;
2906 const BoundCost bound_cost =
2907 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2908 if (bound_cost.cost == 0)
continue;
2909 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2912 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2913 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2914 if (spans[vehicle])
continue;
2915 const BoundCost bound_cost =
2916 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2917 if (bound_cost.cost == 0)
continue;
2918 spans[vehicle] = solver_->MakeIntVar(0, span_ubs[vehicle]);
2921 solver_->AddConstraint(
2925 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2926 if (!spans[vehicle] && !total_slacks[vehicle])
continue;
2927 if (spans[vehicle]) {
2937 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2938 if (span_costs[vehicle] == 0)
continue;
2939 DCHECK(total_slacks[vehicle] !=
nullptr);
2940 IntVar*
const slack_amount =
2942 ->MakeProd(vehicle_route_considered_[vehicle],
2943 total_slacks[vehicle])
2945 IntVar*
const slack_cost =
2946 solver_->MakeProd(slack_amount, span_costs[vehicle])->Var();
2947 cost_elements.push_back(slack_cost);
2949 span_costs[vehicle]);
2951 if (dimension->HasSoftSpanUpperBounds()) {
2952 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2953 const auto bound_cost =
2954 dimension->GetSoftSpanUpperBoundForVehicle(vehicle);
2955 if (bound_cost.cost == 0 ||
2958 DCHECK(spans[vehicle] !=
nullptr);
2961 IntVar*
const span_violation_amount =
2964 vehicle_route_considered_[vehicle],
2966 solver_->MakeSum(spans[vehicle], -bound_cost.bound),
2969 IntVar*
const span_violation_cost =
2970 solver_->MakeProd(span_violation_amount, bound_cost.cost)->Var();
2971 cost_elements.push_back(span_violation_cost);
2976 if (dimension->HasQuadraticCostSoftSpanUpperBounds()) {
2977 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
2978 const auto bound_cost =
2979 dimension->GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
2980 if (bound_cost.cost == 0 ||
2983 DCHECK(spans[vehicle] !=
nullptr);
2986 IntExpr* max0 = solver_->MakeMax(
2987 solver_->MakeSum(spans[vehicle], -bound_cost.bound), 0);
2988 IntVar*
const squared_span_violation_amount =
2990 ->MakeProd(vehicle_route_considered_[vehicle],
2991 solver_->MakeSquare(max0))
2993 IntVar*
const span_violation_cost =
2994 solver_->MakeProd(squared_span_violation_amount, bound_cost.cost)
2996 cost_elements.push_back(span_violation_cost);
3005 IntVar* penalty_var = CreateDisjunction(i);
3006 if (penalty_var !=
nullptr) {
3007 cost_elements.push_back(penalty_var);
3012 dimension->SetupCumulVarSoftLowerBoundCosts(&cost_elements);
3013 dimension->SetupCumulVarSoftUpperBoundCosts(&cost_elements);
3014 dimension->SetupCumulVarPiecewiseLinearCosts(&cost_elements);
3017 for (
int i = 0; i < same_vehicle_costs_.size(); ++i) {
3018 cost_elements.push_back(CreateSameVehicleCost(i));
3020 cost_ = solver_->MakeSum(cost_elements)->Var();
3021 cost_->set_name(
"Cost");
3024 std::vector<std::pair<int, int>> pickup_delivery_precedences;
3025 for (
const auto& pair : pickup_delivery_pairs_) {
3026 DCHECK(!pair.first.empty() && !pair.second.empty());
3027 for (
int pickup : pair.first) {
3028 for (
int delivery : pair.second) {
3029 pickup_delivery_precedences.emplace_back(pickup, delivery);
3033 std::vector<int> lifo_vehicles;
3034 std::vector<int> fifo_vehicles;
3035 for (
int i = 0; i < vehicles_; ++i) {
3036 switch (vehicle_pickup_delivery_policy_[i]) {
3040 lifo_vehicles.push_back(
Start(i));
3043 fifo_vehicles.push_back(
Start(i));
3047 solver_->AddConstraint(solver_->MakePathPrecedenceConstraint(
3048 nexts_, pickup_delivery_precedences, lifo_vehicles, fifo_vehicles));
3051 enable_deep_serialization_ =
false;
3052 std::unique_ptr<RoutingModelInspector> inspector(
3054 solver_->Accept(inspector.get());
3055 enable_deep_serialization_ =
true;
3060 const ReverseArcListGraph<int, int>& graph =
3061 dimension->GetPathPrecedenceGraph();
3062 std::vector<std::pair<int, int>> path_precedences;
3063 for (
const auto tail : graph.AllNodes()) {
3064 for (
const auto head : graph[
tail]) {
3065 path_precedences.emplace_back(
tail,
head);
3068 if (!path_precedences.empty()) {
3069 solver_->AddConstraint(solver_->MakePathTransitPrecedenceConstraint(
3070 nexts_, dimension->transits(), path_precedences));
3074 for (
const RoutingDimension::NodePrecedence& node_precedence :
3075 dimension->GetNodePrecedences()) {
3076 const int64_t first_node = node_precedence.first_node;
3077 const int64_t second_node = node_precedence.second_node;
3078 IntExpr*
const nodes_are_selected =
3079 solver_->MakeMin(active_[first_node], active_[second_node]);
3080 IntExpr*
const cumul_difference = solver_->MakeDifference(
3081 dimension->CumulVar(second_node), dimension->CumulVar(first_node));
3082 IntVar*
const cumul_difference_is_ge_offset =
3083 solver_->MakeIsGreaterOrEqualCstVar(cumul_difference,
3084 node_precedence.offset);
3087 solver_->AddConstraint(solver_->MakeLessOrEqual(
3088 nodes_are_selected->Var(), cumul_difference_is_ge_offset));
3092 if (!resource_groups_.empty()) {
3093 DCHECK_EQ(resource_vars_.size(), resource_groups_.size());
3094 for (
int rg = 0; rg < resource_groups_.size(); ++rg) {
3095 const auto& resource_group = resource_groups_[rg];
3096 const int max_resource_index = resource_group->Size() - 1;
3097 std::vector<IntVar*>& vehicle_res_vars = resource_vars_[rg];
3098 for (IntVar* res_var : vehicle_res_vars) {
3099 res_var->SetMax(max_resource_index);
3101 solver_->AddConstraint(MakeResourceConstraint(resource_group.get(),
3102 &vehicle_res_vars,
this));
3106 DetectImplicitPickupAndDeliveries();
3115 CreateFirstSolutionDecisionBuilders(
parameters);
3116 error = FindErrorInSearchParametersForModel(
parameters);
3117 if (!error.empty()) {
3119 LOG(ERROR) <<
"Invalid RoutingSearchParameters for this model: " << error;
3132 class RestoreDimensionValuesForUnchangedRoutes :
public DecisionBuilder {
3136 model_->AddAtSolutionCallback([
this]() { AtSolution(); });
3137 next_last_value_.resize(model_->Nexts().size(), -1);
3142 Decision*
Next(Solver*
const s)
override {
3143 if (!must_return_decision_)
return nullptr;
3144 s->SaveAndSetValue(&must_return_decision_,
false);
3145 return MakeDecision(s);
3152 is_initialized_ =
true;
3153 const int num_nodes = model_->VehicleVars().size();
3154 node_to_integer_variable_indices_.resize(num_nodes);
3155 node_to_interval_variable_indices_.resize(num_nodes);
3157 for (
const std::string& dimension_name : model_->GetAllDimensionNames()) {
3159 model_->GetDimensionOrDie(dimension_name);
3161 for (
const std::vector<IntVar*>& dimension_variables :
3162 {dimension.cumuls(), dimension.slacks()}) {
3163 const int num_dimension_variables = dimension_variables.size();
3164 DCHECK_LE(num_dimension_variables, num_nodes);
3165 for (
int node = 0; node < num_dimension_variables; ++node) {
3166 node_to_integer_variable_indices_[node].push_back(
3167 integer_variables_.size());
3168 integer_variables_.push_back(dimension_variables[node]);
3172 for (
int vehicle = 0; vehicle < model_->vehicles(); ++vehicle) {
3173 if (!dimension.HasBreakConstraints())
continue;
3174 const int vehicle_start = model_->Start(vehicle);
3176 dimension.GetBreakIntervalsOfVehicle(vehicle)) {
3177 node_to_interval_variable_indices_[vehicle_start].push_back(
3178 interval_variables_.size());
3179 interval_variables_.push_back(
interval);
3183 integer_variables_last_min_.resize(integer_variables_.size());
3184 interval_variables_last_start_min_.resize(interval_variables_.size());
3185 interval_variables_last_end_max_.resize(interval_variables_.size());
3188 Decision* MakeDecision(Solver*
const s) {
3189 if (!is_initialized_)
return nullptr;
3191 std::vector<int> unchanged_vehicles;
3192 const int num_vehicles = model_->vehicles();
3193 for (
int v = 0; v < num_vehicles; ++v) {
3194 bool unchanged =
true;
3195 for (
int current = model_->Start(v); !model_->IsEnd(current);
3196 current = next_last_value_[current]) {
3197 if (!model_->NextVar(current)->Bound() ||
3198 next_last_value_[current] != model_->NextVar(current)->Value()) {
3203 if (unchanged) unchanged_vehicles.push_back(v);
3207 if (unchanged_vehicles.size() == num_vehicles)
return nullptr;
3210 std::vector<IntVar*> vars;
3211 std::vector<int64_t> values;
3212 for (
const int vehicle : unchanged_vehicles) {
3213 for (
int current = model_->Start(vehicle);
true;
3214 current = next_last_value_[current]) {
3215 for (
const int index : node_to_integer_variable_indices_[current]) {
3216 vars.push_back(integer_variables_[
index]);
3217 values.push_back(integer_variables_last_min_[
index]);
3219 for (
const int index : node_to_interval_variable_indices_[current]) {
3220 const int64_t
start_min = interval_variables_last_start_min_[
index];
3221 const int64_t
end_max = interval_variables_last_end_max_[
index];
3223 vars.push_back(interval_variables_[
index]->SafeStartExpr(0)->Var());
3224 values.push_back(interval_variables_last_start_min_[
index]);
3225 vars.push_back(interval_variables_[
index]->SafeEndExpr(0)->Var());
3226 values.push_back(interval_variables_last_end_max_[
index]);
3228 vars.push_back(interval_variables_[
index]->PerformedExpr()->Var());
3229 values.push_back(0);
3232 if (model_->IsEnd(current))
break;
3235 return s->MakeAssignVariablesValuesOrDoNothing(vars, values);
3239 if (!is_initialized_) Initialize();
3240 const int num_integers = integer_variables_.size();
3243 for (
int i = 0; i < num_integers; ++i) {
3244 integer_variables_last_min_[i] = integer_variables_[i]->Min();
3246 const int num_intervals = interval_variables_.size();
3247 for (
int i = 0; i < num_intervals; ++i) {
3248 const bool is_performed = interval_variables_[i]->MustBePerformed();
3249 interval_variables_last_start_min_[i] =
3250 is_performed ? interval_variables_[i]->StartMin() : 0;
3251 interval_variables_last_end_max_[i] =
3252 is_performed ? interval_variables_[i]->EndMax() : -1;
3254 const int num_nodes = next_last_value_.size();
3255 for (
int node = 0; node < num_nodes; ++node) {
3256 if (model_->IsEnd(node))
continue;
3257 next_last_value_[node] = model_->NextVar(node)->Value();
3265 std::vector<int> next_last_value_;
3268 std::vector<std::vector<int>> node_to_integer_variable_indices_;
3269 std::vector<std::vector<int>> node_to_interval_variable_indices_;
3271 std::vector<IntVar*> integer_variables_;
3272 std::vector<int64_t> integer_variables_last_min_;
3273 std::vector<IntervalVar*> interval_variables_;
3274 std::vector<int64_t> interval_variables_last_start_min_;
3275 std::vector<int64_t> interval_variables_last_end_max_;
3277 bool is_initialized_ =
false;
3278 bool must_return_decision_ =
true;
3284 return model->solver()->RevAlloc(
3285 new RestoreDimensionValuesForUnchangedRoutes(
model));
3289 monitors_.push_back(monitor);
3293 class AtSolutionCallbackMonitor :
public SearchMonitor {
3295 AtSolutionCallbackMonitor(Solver*
solver, std::function<
void()>
callback)
3297 bool AtSolution()
override {
3304 std::function<void()> callback_;
3310 new AtSolutionCallbackMonitor(solver_.get(), std::move(
callback))));
3320 std::vector<const Assignment*>* solutions) {
3325 absl::Duration GetTimeLimit(
const RoutingSearchParameters&
parameters) {
3326 if (!
parameters.has_time_limit())
return absl::InfiniteDuration();
3330 absl::Duration GetLnsTimeLimit(
const RoutingSearchParameters&
parameters) {
3331 if (!
parameters.has_lns_time_limit())
return absl::InfiniteDuration();
3339 Assignment* assignment) {
3340 assignment->Clear();
3341 for (
int i = 0; i <
model->Nexts().size(); ++i) {
3342 if (!
model->IsStart(i)) {
3343 assignment->Add(
model->NextVar(i))->SetValue(i);
3346 for (
int vehicle = 0; vehicle <
model->vehicles(); ++vehicle) {
3347 assignment->Add(
model->NextVar(
model->Start(vehicle)))
3348 ->SetValue(
model->End(vehicle));
3353 bool RoutingModel::AppendAssignmentIfFeasible(
3354 const Assignment& assignment,
3355 std::vector<std::unique_ptr<Assignment>>* assignments) {
3356 tmp_assignment_->CopyIntersection(&assignment);
3357 solver_->Solve(restore_tmp_assignment_, collect_one_assignment_,
3358 GetOrCreateLimit());
3359 if (collect_one_assignment_->solution_count() == 1) {
3360 assignments->push_back(std::make_unique<Assignment>(solver_.get()));
3361 assignments->back()->Copy(collect_one_assignment_->solution(0));
3367 void RoutingModel::LogSolution(
const RoutingSearchParameters&
parameters,
3368 const std::string& description,
3369 int64_t solution_cost, int64_t start_time_ms) {
3371 const double cost_scaling_factor =
parameters.log_cost_scaling_factor();
3372 const double cost_offset =
parameters.log_cost_offset();
3373 const std::string cost_string =
3374 cost_scaling_factor == 1.0 && cost_offset == 0.0
3375 ? absl::StrCat(solution_cost)
3377 "%d (%.8lf)", solution_cost,
3378 cost_scaling_factor * (solution_cost + cost_offset));
3379 LOG(INFO) << absl::StrFormat(
3380 "%s (%s, time = %d ms, memory used = %s)", description, cost_string,
3381 solver_->wall_time() - start_time_ms, memory_str);
3386 std::vector<const Assignment*>* solutions) {
3392 const std::vector<const Assignment*>& assignments,
3394 std::vector<const Assignment*>* solutions) {
3395 const int64_t start_time_ms = solver_->wall_time();
3398 if (solutions !=
nullptr) solutions->clear();
3404 if (!solver_->CheckConstraint(solver_->MakeTrueConstraint())) {
3409 const auto update_time_limits = [
this, start_time_ms, &
parameters]() {
3410 const absl::Duration elapsed_time =
3411 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3412 const absl::Duration time_left = GetTimeLimit(
parameters) - elapsed_time;
3413 if (time_left >= absl::ZeroDuration()) {
3421 time_buffer_ =
std::min(absl::Seconds(1), time_left * 0.05);
3426 if (!update_time_limits()) {
3430 lns_limit_->UpdateLimits(
3438 const int time_limit_shares = 1 + !global_dimension_optimizers_.empty() +
3439 !local_dimension_optimizers_.empty();
3440 const absl::Duration first_solution_lns_time_limit =
3443 first_solution_lns_limit_->UpdateLimits(
3447 std::vector<std::unique_ptr<Assignment>> solution_pool;
3448 std::vector<const Assignment*> first_solution_assignments;
3449 for (
const Assignment* assignment : assignments) {
3450 if (assignment !=
nullptr) first_solution_assignments.push_back(assignment);
3452 local_optimum_reached_ =
false;
3455 if (first_solution_assignments.empty()) {
3456 bool solution_found =
false;
3457 Assignment matching(solver_.get());
3459 AppendAssignmentIfFeasible(matching, &solution_pool)) {
3461 LogSolution(
parameters,
"Min-Cost Flow Solution",
3462 solution_pool.back()->ObjectiveValue(), start_time_ms);
3464 solution_found =
true;
3465 local_optimum_reached_ =
true;
3467 if (!solution_found) {
3470 Assignment unperformed(solver_.get());
3471 MakeAllUnperformedInAssignment(
this, &unperformed);
3472 if (AppendAssignmentIfFeasible(unperformed, &solution_pool) &&
3474 LogSolution(
parameters,
"All Unperformed Solution",
3475 solution_pool.back()->ObjectiveValue(), start_time_ms);
3477 local_optimum_reached_ =
false;
3478 if (update_time_limits()) {
3479 solver_->Solve(solve_db_, monitors_);
3483 for (
const Assignment* assignment : first_solution_assignments) {
3484 assignment_->CopyIntersection(assignment);
3485 solver_->Solve(improve_db_, monitors_);
3486 if (collect_assignments_->solution_count() >= 1 ||
3487 !update_time_limits()) {
3495 parameters.use_generalized_cp_sat() == BOOL_TRUE ||
3497 collect_assignments_->solution_count() == 0 && solution_pool.empty())) {
3498 VLOG(1) <<
"Solving with CP-SAT";
3499 const int solution_count = collect_assignments_->solution_count();
3500 Assignment*
const cp_solution =
3501 solution_count >= 1 ? collect_assignments_->solution(solution_count - 1)
3503 Assignment sat_solution(solver_.get());
3505 AppendAssignmentIfFeasible(sat_solution, &solution_pool) &&
3507 LogSolution(
parameters,
"SAT", solution_pool.back()->ObjectiveValue(),
3509 local_optimum_reached_ =
true;
3512 VLOG(1) <<
"Objective lower bound: " << objective_lower_bound_;
3513 const absl::Duration elapsed_time =
3514 absl::Milliseconds(solver_->wall_time() - start_time_ms);
3515 const int solution_count = collect_assignments_->solution_count();
3516 if (solution_count >= 1 || !solution_pool.empty()) {
3517 status_ = local_optimum_reached_
3520 if (solutions !=
nullptr) {
3521 int64_t min_objective_value =
kint64max;
3522 for (
int i = 0; i < solution_count; ++i) {
3523 solutions->push_back(
3524 solver_->MakeAssignment(collect_assignments_->solution(i)));
3525 min_objective_value =
3526 std::min(min_objective_value, solutions->back()->ObjectiveValue());
3528 for (
const auto& solution : solution_pool) {
3529 if (solutions->empty() ||
3530 solution->ObjectiveValue() < solutions->back()->ObjectiveValue()) {
3531 solutions->push_back(solver_->MakeAssignment(solution.get()));
3533 min_objective_value =
3534 std::min(min_objective_value, solutions->back()->ObjectiveValue());
3536 if (min_objective_value <= objective_lower_bound_) {
3539 return solutions->back();
3541 Assignment* best_assignment =
3542 solution_count >= 1 ? collect_assignments_->solution(solution_count - 1)
3544 for (
const auto& solution : solution_pool) {
3545 if (best_assignment ==
nullptr ||
3546 solution->ObjectiveValue() < best_assignment->ObjectiveValue()) {
3547 best_assignment = solution.get();
3550 if (best_assignment->ObjectiveValue() <= objective_lower_bound_) {
3553 return solver_->MakeAssignment(best_assignment);
3555 if (elapsed_time >= GetTimeLimit(
parameters)) {
3565 Assignment* target_assignment,
const RoutingModel* source_model,
3566 const Assignment* source_assignment) {
3567 const int size =
Size();
3568 DCHECK_EQ(size, source_model->Size());
3569 CHECK_EQ(target_assignment->solver(), solver_.get());
3573 source_model->Nexts());
3575 std::vector<IntVar*> source_vars(size + size + vehicles_);
3576 std::vector<IntVar*> target_vars(size + size + vehicles_);
3578 source_vars[
index] = source_model->NextVar(
index);
3582 source_vars[size +
index] = source_model->VehicleVar(
index);
3586 source_assignment, source_vars);
3589 target_assignment->AddObjective(cost_);
3604 LOG(WARNING) <<
"Non-closed model not supported.";
3608 LOG(WARNING) <<
"Non-homogeneous vehicle costs not supported";
3611 if (!disjunctions_.empty()) {
3613 <<
"Node disjunction constraints or optional nodes not supported.";
3616 const int num_nodes =
Size() + vehicles_;
3623 std::unique_ptr<IntVarIterator> iterator(
3624 nexts_[
tail]->MakeDomainIterator(
false));
3647 return linear_sum_assignment.
GetCost();
3652 bool RoutingModel::RouteCanBeUsedByVehicle(
const Assignment& assignment,
3653 int start_index,
int vehicle)
const {
3655 IsStart(start_index) ?
Next(assignment, start_index) : start_index;
3656 while (!
IsEnd(current_index)) {
3658 if (!vehicle_var->
Contains(vehicle)) {
3661 const int next_index =
Next(assignment, current_index);
3662 CHECK_NE(next_index, current_index) <<
"Inactive node inside a route";
3663 current_index = next_index;
3668 bool RoutingModel::ReplaceUnusedVehicle(
3669 int unused_vehicle,
int active_vehicle,
3670 Assignment*
const compact_assignment)
const {
3671 CHECK(compact_assignment !=
nullptr);
3675 const int unused_vehicle_start =
Start(unused_vehicle);
3676 IntVar*
const unused_vehicle_start_var =
NextVar(unused_vehicle_start);
3677 const int unused_vehicle_end =
End(unused_vehicle);
3678 const int active_vehicle_start =
Start(active_vehicle);
3679 const int active_vehicle_end =
End(active_vehicle);
3680 IntVar*
const active_vehicle_start_var =
NextVar(active_vehicle_start);
3681 const int active_vehicle_next =
3682 compact_assignment->Value(active_vehicle_start_var);
3683 compact_assignment->SetValue(unused_vehicle_start_var, active_vehicle_next);
3684 compact_assignment->SetValue(active_vehicle_start_var,
End(active_vehicle));
3687 int current_index = active_vehicle_next;
3688 while (!
IsEnd(current_index)) {
3689 IntVar*
const vehicle_var =
VehicleVar(current_index);
3690 compact_assignment->SetValue(vehicle_var, unused_vehicle);
3691 const int next_index =
Next(*compact_assignment, current_index);
3692 if (
IsEnd(next_index)) {
3693 IntVar*
const last_next_var =
NextVar(current_index);
3694 compact_assignment->SetValue(last_next_var,
End(unused_vehicle));
3696 current_index = next_index;
3701 const std::vector<IntVar*>& transit_variables = dimension->transits();
3702 IntVar*
const unused_vehicle_transit_var =
3703 transit_variables[unused_vehicle_start];
3704 IntVar*
const active_vehicle_transit_var =
3705 transit_variables[active_vehicle_start];
3706 const bool contains_unused_vehicle_transit_var =
3707 compact_assignment->Contains(unused_vehicle_transit_var);
3708 const bool contains_active_vehicle_transit_var =
3709 compact_assignment->Contains(active_vehicle_transit_var);
3710 if (contains_unused_vehicle_transit_var !=
3711 contains_active_vehicle_transit_var) {
3713 LOG(INFO) <<
"The assignment contains transit variable for dimension '"
3714 << dimension->name() <<
"' for some vehicles, but not for all";
3717 if (contains_unused_vehicle_transit_var) {
3718 const int64_t old_unused_vehicle_transit =
3719 compact_assignment->Value(unused_vehicle_transit_var);
3720 const int64_t old_active_vehicle_transit =
3721 compact_assignment->Value(active_vehicle_transit_var);
3722 compact_assignment->SetValue(unused_vehicle_transit_var,
3723 old_active_vehicle_transit);
3724 compact_assignment->SetValue(active_vehicle_transit_var,
3725 old_unused_vehicle_transit);
3729 const std::vector<IntVar*>& cumul_variables = dimension->cumuls();
3730 IntVar*
const unused_vehicle_cumul_var =
3731 cumul_variables[unused_vehicle_end];
3732 IntVar*
const active_vehicle_cumul_var =
3733 cumul_variables[active_vehicle_end];
3734 const int64_t old_unused_vehicle_cumul =
3735 compact_assignment->Value(unused_vehicle_cumul_var);
3736 const int64_t old_active_vehicle_cumul =
3737 compact_assignment->Value(active_vehicle_cumul_var);
3738 compact_assignment->SetValue(unused_vehicle_cumul_var,
3739 old_active_vehicle_cumul);
3740 compact_assignment->SetValue(active_vehicle_cumul_var,
3741 old_unused_vehicle_cumul);
3748 return CompactAssignmentInternal(assignment,
false);
3752 const Assignment& assignment)
const {
3753 return CompactAssignmentInternal(assignment,
true);
3756 Assignment* RoutingModel::CompactAssignmentInternal(
3757 const Assignment& assignment,
bool check_compact_assignment)
const {
3758 CHECK_EQ(assignment.solver(), solver_.get());
3761 <<
"The costs are not homogeneous, routes cannot be rearranged";
3765 std::unique_ptr<Assignment> compact_assignment(
new Assignment(&assignment));
3766 for (
int vehicle = 0; vehicle < vehicles_ - 1; ++vehicle) {
3770 const int vehicle_start =
Start(vehicle);
3771 const int vehicle_end =
End(vehicle);
3773 int swap_vehicle = vehicles_ - 1;
3774 bool has_more_vehicles_with_route =
false;
3775 for (; swap_vehicle > vehicle; --swap_vehicle) {
3782 has_more_vehicles_with_route =
true;
3783 const int swap_vehicle_start =
Start(swap_vehicle);
3784 const int swap_vehicle_end =
End(swap_vehicle);
3785 if (manager_.IndexToNode(vehicle_start) !=
3786 manager_.IndexToNode(swap_vehicle_start) ||
3787 manager_.IndexToNode(vehicle_end) !=
3788 manager_.IndexToNode(swap_vehicle_end)) {
3793 if (RouteCanBeUsedByVehicle(*compact_assignment, swap_vehicle_start,
3799 if (swap_vehicle == vehicle) {
3800 if (has_more_vehicles_with_route) {
3804 LOG(INFO) <<
"No vehicle that can be swapped with " << vehicle
3811 if (!ReplaceUnusedVehicle(vehicle, swap_vehicle,
3812 compact_assignment.get())) {
3817 if (check_compact_assignment &&
3818 !solver_->CheckAssignment(compact_assignment.get())) {
3820 LOG(WARNING) <<
"The compacted assignment is not a valid solution";
3823 return compact_assignment.release();
3826 int RoutingModel::FindNextActive(
int index,
3827 const std::vector<int64_t>& indices)
const {
3830 const int size = indices.size();
3840 CHECK_EQ(vehicles_, 1);
3841 preassignment_->Clear();
3842 IntVar* next_var =
nullptr;
3843 int lock_index = FindNextActive(-1, locks);
3844 const int size = locks.size();
3845 if (lock_index < size) {
3846 next_var =
NextVar(locks[lock_index]);
3847 preassignment_->Add(next_var);
3848 for (lock_index = FindNextActive(lock_index, locks); lock_index < size;
3849 lock_index = FindNextActive(lock_index, locks)) {
3850 preassignment_->SetValue(next_var, locks[lock_index]);
3852 preassignment_->Add(next_var);
3859 const std::vector<std::vector<int64_t>>& locks,
bool close_routes) {
3860 preassignment_->Clear();
3867 GetFilteredFirstSolutionDecisionBuilderOrNull(
parameters);
3875 GetFilteredFirstSolutionDecisionBuilderOrNull(
parameters);
3881 if (collect_assignments_->solution_count() == 1 && assignment_ !=
nullptr) {
3882 assignment_->CopyIntersection(collect_assignments_->solution(0));
3883 return assignment_->Save(file_name);
3891 CHECK(assignment_ !=
nullptr);
3892 if (assignment_->Load(file_name)) {
3893 return DoRestoreAssignment();
3900 CHECK(assignment_ !=
nullptr);
3901 assignment_->CopyIntersection(&solution);
3902 return DoRestoreAssignment();
3905 Assignment* RoutingModel::DoRestoreAssignment() {
3909 solver_->Solve(restore_assignment_, monitors_);
3910 if (collect_assignments_->solution_count() == 1) {
3912 return collect_assignments_->solution(0);
3921 const std::vector<std::vector<int64_t>>& routes,
3922 bool ignore_inactive_indices,
bool close_routes,
3923 Assignment*
const assignment)
const {
3924 CHECK(assignment !=
nullptr);
3926 LOG(ERROR) <<
"The model is not closed yet";
3929 const int num_routes = routes.size();
3930 if (num_routes > vehicles_) {
3931 LOG(ERROR) <<
"The number of vehicles in the assignment (" << routes.size()
3932 <<
") is greater than the number of vehicles in the model ("
3933 << vehicles_ <<
")";
3937 absl::flat_hash_set<int> visited_indices;
3939 for (
int vehicle = 0; vehicle < num_routes; ++vehicle) {
3940 const std::vector<int64_t>& route = routes[vehicle];
3941 int from_index =
Start(vehicle);
3942 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
3943 visited_indices.insert(from_index);
3944 if (!insert_result.second) {
3945 LOG(ERROR) <<
"Index " << from_index <<
" (start node for vehicle "
3946 << vehicle <<
") was already used";
3950 for (
const int64_t to_index : route) {
3951 if (to_index < 0 || to_index >=
Size()) {
3952 LOG(ERROR) <<
"Invalid index: " << to_index;
3956 IntVar*
const active_var =
ActiveVar(to_index);
3957 if (active_var->Max() == 0) {
3958 if (ignore_inactive_indices) {
3961 LOG(ERROR) <<
"Index " << to_index <<
" is not active";
3966 insert_result = visited_indices.insert(to_index);
3967 if (!insert_result.second) {
3968 LOG(ERROR) <<
"Index " << to_index <<
" is used multiple times";
3972 const IntVar*
const vehicle_var =
VehicleVar(to_index);
3973 if (!vehicle_var->Contains(vehicle)) {
3974 LOG(ERROR) <<
"Vehicle " << vehicle <<
" is not allowed at index "
3979 IntVar*
const from_var =
NextVar(from_index);
3980 if (!assignment->Contains(from_var)) {
3981 assignment->Add(from_var);
3983 assignment->SetValue(from_var, to_index);
3985 from_index = to_index;
3989 IntVar*
const last_var =
NextVar(from_index);
3990 if (!assignment->Contains(last_var)) {
3991 assignment->Add(last_var);
3993 assignment->SetValue(last_var,
End(vehicle));
3998 for (
int vehicle = num_routes; vehicle < vehicles_; ++vehicle) {
3999 const int start_index =
Start(vehicle);
4002 std::pair<absl::flat_hash_set<int>::iterator,
bool> insert_result =
4003 visited_indices.insert(start_index);
4004 if (!insert_result.second) {
4005 LOG(ERROR) <<
"Index " << start_index <<
" is used multiple times";
4009 IntVar*
const start_var =
NextVar(start_index);
4010 if (!assignment->Contains(start_var)) {
4011 assignment->Add(start_var);
4013 assignment->SetValue(start_var,
End(vehicle));
4020 if (!visited_indices.contains(
index)) {
4022 if (!assignment->Contains(next_var)) {
4023 assignment->Add(next_var);
4025 assignment->SetValue(next_var,
index);
4034 const std::vector<std::vector<int64_t>>& routes,
4035 bool ignore_inactive_indices) {
4043 return DoRestoreAssignment();
4047 const Assignment& assignment,
4048 std::vector<std::vector<int64_t>>*
const routes)
const {
4050 CHECK(routes !=
nullptr);
4052 const int model_size =
Size();
4053 routes->resize(vehicles_);
4054 for (
int vehicle = 0; vehicle < vehicles_; ++vehicle) {
4055 std::vector<int64_t>*
const vehicle_route = &routes->at(vehicle);
4056 vehicle_route->clear();
4058 int num_visited_indices = 0;
4059 const int first_index =
Start(vehicle);
4060 const IntVar*
const first_var =
NextVar(first_index);
4061 CHECK(assignment.Contains(first_var));
4062 CHECK(assignment.Bound(first_var));
4063 int current_index = assignment.Value(first_var);
4064 while (!
IsEnd(current_index)) {
4065 vehicle_route->push_back(current_index);
4067 const IntVar*
const next_var =
NextVar(current_index);
4068 CHECK(assignment.Contains(next_var));
4069 CHECK(assignment.Bound(next_var));
4070 current_index = assignment.Value(next_var);
4072 ++num_visited_indices;
4073 CHECK_LE(num_visited_indices, model_size)
4074 <<
"The assignment contains a cycle";
4081 const Assignment& assignment) {
4082 std::vector<std::vector<int64_t>> route_indices(
vehicles());
4083 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4084 if (!assignment.Bound(
NextVar(vehicle))) {
4085 LOG(DFATAL) <<
"GetRoutesFromAssignment() called on incomplete solution:"
4086 <<
" NextVar(" << vehicle <<
") is unbound.";
4089 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4091 route_indices[vehicle].push_back(
index);
4094 route_indices[vehicle].push_back(
index);
4097 return route_indices;
4101 int64_t RoutingModel::GetArcCostForClassInternal(
4102 int64_t from_index, int64_t to_index,
4105 DCHECK_GE(cost_class_index, 0);
4106 DCHECK_LT(cost_class_index, cost_classes_.size());
4107 CostCacheElement*
const cache = &cost_cache_[from_index];
4109 if (cache->index ==
static_cast<int>(to_index) &&
4110 cache->cost_class_index == cost_class_index) {
4114 const CostClass& cost_class = cost_classes_[cost_class_index];
4115 const auto& evaluator = transit_evaluators_[cost_class.evaluator_index];
4117 cost =
CapAdd(evaluator(from_index, to_index),
4118 GetDimensionTransitCostSum(from_index, to_index, cost_class));
4119 }
else if (!
IsEnd(to_index)) {
4123 evaluator(from_index, to_index),
4124 CapAdd(GetDimensionTransitCostSum(from_index, to_index, cost_class),
4129 if (vehicle_used_when_empty_[
VehicleIndex(from_index)]) {
4131 CapAdd(evaluator(from_index, to_index),
4132 GetDimensionTransitCostSum(from_index, to_index, cost_class));
4137 *cache = {
static_cast<int>(to_index), cost_class_index,
cost};
4142 int vehicle)
const {
4143 CHECK_GE(vehicle, 0);
4144 CHECK_LT(vehicle, vehicles_);
4145 CHECK_EQ(solver_.get(), assignment.solver());
4147 CHECK(assignment.Contains(start_var));
4148 return !
IsEnd(assignment.Value(start_var));
4152 CHECK_EQ(solver_.get(), assignment.
solver());
4154 CHECK(assignment.
Contains(next_var));
4155 CHECK(assignment.
Bound(next_var));
4156 return assignment.
Value(next_var);
4160 int64_t vehicle)
const {
4161 if (from_index != to_index && vehicle >= 0) {
4162 return GetArcCostForClassInternal(from_index, to_index,
4170 int64_t from_index, int64_t to_index,
4171 int64_t cost_class_index)
const {
4172 if (from_index != to_index) {
4173 return GetArcCostForClassInternal(from_index, to_index,
4181 int64_t to_index)
const {
4185 if (!is_bound_to_end_ct_added_.Switched()) {
4188 std::vector<IntVar*> zero_transit(
Size(), solver_->MakeIntConst(0));
4189 solver_->AddConstraint(solver_->MakeDelayedPathCumul(
4190 nexts_, active_, is_bound_to_end_, zero_transit));
4191 is_bound_to_end_ct_added_.Switch(solver_.get());
4193 if (is_bound_to_end_[to_index]->Min() == 1)
4199 int64_t RoutingModel::GetDimensionTransitCostSum(
4200 int64_t i, int64_t j,
const CostClass& cost_class)
const {
4202 for (
const auto& evaluator_and_coefficient :
4203 cost_class.dimension_transit_evaluator_class_and_cost_coefficient) {
4204 DCHECK_GT(evaluator_and_coefficient.cost_coefficient, 0);
4207 CapProd(evaluator_and_coefficient.cost_coefficient,
4208 evaluator_and_coefficient.dimension->GetTransitValueFromClass(
4209 i, j, evaluator_and_coefficient.transit_evaluator_class)));
4225 const bool mandatory1 = active_[to1]->Min() == 1;
4226 const bool mandatory2 = active_[to2]->Min() == 1;
4228 if (mandatory1 != mandatory2)
return mandatory1;
4231 IntVar*
const src_vehicle_var =
VehicleVar(from);
4235 const int64_t src_vehicle = src_vehicle_var->Max();
4236 if (src_vehicle_var->Bound()) {
4237 IntVar*
const to1_vehicle_var =
VehicleVar(to1);
4238 IntVar*
const to2_vehicle_var =
VehicleVar(to2);
4243 mandatory1 ? to1_vehicle_var->Bound() : (to1_vehicle_var->Size() <= 2);
4245 mandatory2 ? to2_vehicle_var->Bound() : (to2_vehicle_var->Size() <= 2);
4248 if (bound1 != bound2)
return bound1;
4251 const int64_t vehicle1 = to1_vehicle_var->Max();
4252 const int64_t vehicle2 = to2_vehicle_var->Max();
4255 if ((vehicle1 == src_vehicle) != (vehicle2 == src_vehicle)) {
4256 return vehicle1 == src_vehicle;
4261 if (vehicle1 != src_vehicle)
return to1 < to2;
4272 const std::vector<IntVar*>& cumul_vars =
4274 IntVar*
const dim1 = cumul_vars[to1];
4275 IntVar*
const dim2 = cumul_vars[to2];
4278 if (dim1->Max() != dim2->Max())
return dim1->Max() < dim2->Max();
4287 const int64_t cost_class_index =
4288 SafeGetCostClassInt64OfVehicle(src_vehicle);
4289 const int64_t cost1 =
4292 const int64_t cost2 =
4295 if (cost1 != cost2)
return cost1 < cost2;
4302 if (num_vehicles1 != num_vehicles2)
return num_vehicles1 < num_vehicles2;
4311 CHECK_LT(
index, index_to_visit_type_.size());
4312 DCHECK_EQ(index_to_visit_type_.size(), index_to_type_policy_.size());
4313 index_to_visit_type_[
index] = type;
4314 index_to_type_policy_[
index] = policy;
4315 num_visit_types_ =
std::max(num_visit_types_, type + 1);
4319 CHECK_LT(
index, index_to_visit_type_.size());
4320 return index_to_visit_type_[
index];
4324 DCHECK_LT(type, single_nodes_of_type_.size());
4325 return single_nodes_of_type_[type];
4329 DCHECK_LT(type, pair_indices_of_type_.size());
4330 return pair_indices_of_type_[type];
4334 int64_t
index)
const {
4335 CHECK_LT(
index, index_to_type_policy_.size());
4336 return index_to_type_policy_[
index];
4340 hard_incompatible_types_per_type_index_.resize(num_visit_types_);
4341 temporal_incompatible_types_per_type_index_.resize(num_visit_types_);
4342 same_vehicle_required_type_alternatives_per_type_index_.resize(
4344 required_type_alternatives_when_adding_type_index_.resize(num_visit_types_);
4345 required_type_alternatives_when_removing_type_index_.resize(num_visit_types_);
4350 hard_incompatible_types_per_type_index_.size());
4351 has_hard_type_incompatibilities_ =
true;
4353 hard_incompatible_types_per_type_index_[type1].insert(type2);
4354 hard_incompatible_types_per_type_index_[type2].insert(type1);
4359 temporal_incompatible_types_per_type_index_.size());
4360 has_temporal_type_incompatibilities_ =
true;
4362 temporal_incompatible_types_per_type_index_[type1].insert(type2);
4363 temporal_incompatible_types_per_type_index_[type2].insert(type1);
4366 const absl::flat_hash_set<int>&
4369 DCHECK_LT(type, hard_incompatible_types_per_type_index_.size());
4370 return hard_incompatible_types_per_type_index_[type];
4373 const absl::flat_hash_set<int>&
4376 DCHECK_LT(type, temporal_incompatible_types_per_type_index_.size());
4377 return temporal_incompatible_types_per_type_index_[type];
4383 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4384 DCHECK_LT(dependent_type,
4385 same_vehicle_required_type_alternatives_per_type_index_.size());
4387 if (required_type_alternatives.empty()) {
4391 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4392 trivially_infeasible_visit_types_to_policies_[dependent_type];
4399 has_same_vehicle_type_requirements_ =
true;
4400 same_vehicle_required_type_alternatives_per_type_index_[dependent_type]
4401 .push_back(std::move(required_type_alternatives));
4405 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4406 DCHECK_LT(dependent_type,
4407 required_type_alternatives_when_adding_type_index_.size());
4409 if (required_type_alternatives.empty()) {
4413 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4414 trivially_infeasible_visit_types_to_policies_[dependent_type];
4420 has_temporal_type_requirements_ =
true;
4421 required_type_alternatives_when_adding_type_index_[dependent_type].push_back(
4422 std::move(required_type_alternatives));
4426 int dependent_type, absl::flat_hash_set<int> required_type_alternatives) {
4427 DCHECK_LT(dependent_type,
4428 required_type_alternatives_when_removing_type_index_.size());
4430 if (required_type_alternatives.empty()) {
4434 absl::flat_hash_set<VisitTypePolicy>& infeasible_policies =
4435 trivially_infeasible_visit_types_to_policies_[dependent_type];
4442 has_temporal_type_requirements_ =
true;
4443 required_type_alternatives_when_removing_type_index_[dependent_type]
4444 .push_back(std::move(required_type_alternatives));
4447 const std::vector<absl::flat_hash_set<int>>&
4451 same_vehicle_required_type_alternatives_per_type_index_.size());
4452 return same_vehicle_required_type_alternatives_per_type_index_[type];
4455 const std::vector<absl::flat_hash_set<int>>&
4458 DCHECK_LT(type, required_type_alternatives_when_adding_type_index_.size());
4459 return required_type_alternatives_when_adding_type_index_[type];
4462 const std::vector<absl::flat_hash_set<int>>&
4465 DCHECK_LT(type, required_type_alternatives_when_removing_type_index_.size());
4466 return required_type_alternatives_when_removing_type_index_[type];
4474 int64_t var_index)
const {
4475 if (active_[var_index]->Min() == 1)
4477 const std::vector<DisjunctionIndex>& disjunction_indices =
4479 if (disjunction_indices.size() != 1)
return default_value;
4484 return std::max(int64_t{0}, disjunctions_[disjunction_index].value.penalty);
4488 const Assignment& solution_assignment,
4489 const std::string& dimension_to_print)
const {
4490 for (
int i = 0; i <
Size(); ++i) {
4491 if (!solution_assignment.Bound(
NextVar(i))) {
4493 <<
"DebugOutputVehicleSchedules() called on incomplete solution:"
4494 <<
" NextVar(" << i <<
") is unbound.";
4499 absl::flat_hash_set<std::string> dimension_names;
4500 if (dimension_to_print.empty()) {
4502 dimension_names.insert(all_dimension_names.begin(),
4503 all_dimension_names.end());
4505 dimension_names.insert(dimension_to_print);
4507 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4508 int empty_vehicle_range_start = vehicle;
4513 if (empty_vehicle_range_start != vehicle) {
4514 if (empty_vehicle_range_start == vehicle - 1) {
4515 absl::StrAppendFormat(&output,
"Vehicle %d: empty",
4516 empty_vehicle_range_start);
4518 absl::StrAppendFormat(&output,
"Vehicles %d-%d: empty",
4519 empty_vehicle_range_start, vehicle - 1);
4521 output.append(
"\n");
4524 absl::StrAppendFormat(&output,
"Vehicle %d:", vehicle);
4528 absl::StrAppendFormat(&output,
"%d Vehicle(%d) ",
index,
4529 solution_assignment.Value(vehicle_var));
4531 if (dimension_names.contains(dimension->name())) {
4532 const IntVar*
const var = dimension->CumulVar(
index);
4533 absl::StrAppendFormat(&output,
"%s(%d..%d) ", dimension->name(),
4534 solution_assignment.Min(
var),
4535 solution_assignment.Max(
var));
4540 if (
IsEnd(
index)) output.append(
"Route end ");
4542 output.append(
"\n");
4545 output.append(
"Unperformed nodes: ");
4546 bool has_unperformed =
false;
4547 for (
int i = 0; i <
Size(); ++i) {
4549 solution_assignment.Value(
NextVar(i)) == i) {
4550 absl::StrAppendFormat(&output,
"%d ", i);
4551 has_unperformed =
true;
4554 if (!has_unperformed) output.append(
"None");
4555 output.append(
"\n");
4560 std::vector<std::vector<std::pair<int64_t, int64_t>>>
4563 std::vector<std::vector<std::pair<int64_t, int64_t>>> cumul_bounds(
4565 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
4567 LOG(DFATAL) <<
"GetCumulBounds() called on incomplete solution:"
4568 <<
" NextVar(" << vehicle <<
") is unbound.";
4572 for (
int vehicle_id = 0; vehicle_id <
vehicles(); ++vehicle_id) {
4575 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4576 solution_assignment.
Max(dim_var));
4580 cumul_bounds[vehicle_id].emplace_back(solution_assignment.
Min(dim_var),
4581 solution_assignment.
Max(dim_var));
4584 return cumul_bounds;
4588 Assignment* RoutingModel::GetOrCreateAssignment() {
4589 if (assignment_ ==
nullptr) {
4590 assignment_ = solver_->MakeAssignment();
4591 assignment_->Add(nexts_);
4593 assignment_->Add(vehicle_vars_);
4595 assignment_->AddObjective(cost_);
4600 Assignment* RoutingModel::GetOrCreateTmpAssignment() {
4601 if (tmp_assignment_ ==
nullptr) {
4602 tmp_assignment_ = solver_->MakeAssignment();
4603 tmp_assignment_->Add(nexts_);
4605 return tmp_assignment_;
4608 RegularLimit* RoutingModel::GetOrCreateLimit() {
4609 if (limit_ ==
nullptr) {
4610 limit_ = solver_->MakeLimit(
4618 RegularLimit* RoutingModel::GetOrCreateLocalSearchLimit() {
4619 if (ls_limit_ ==
nullptr) {
4620 ls_limit_ = solver_->MakeLimit(absl::InfiniteDuration(),
4628 RegularLimit* RoutingModel::GetOrCreateLargeNeighborhoodSearchLimit() {
4629 if (lns_limit_ ==
nullptr) {
4630 lns_limit_ = solver_->MakeLimit(
4639 RoutingModel::GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit() {
4640 if (first_solution_lns_limit_ ==
nullptr) {
4641 first_solution_lns_limit_ = solver_->MakeLimit(
4646 return first_solution_lns_limit_;
4649 LocalSearchOperator* RoutingModel::CreateInsertionOperator() {
4650 LocalSearchOperator* insertion_operator =
4651 CreateCPOperator<MakeActiveOperator>();
4652 if (!pickup_delivery_pairs_.empty()) {
4653 insertion_operator = solver_->ConcatenateOperators(
4654 {CreatePairOperator<MakePairActiveOperator>(), insertion_operator});
4656 if (!implicit_pickup_delivery_pairs_without_alternatives_.empty()) {
4657 insertion_operator = solver_->ConcatenateOperators(
4658 {CreateOperator<MakePairActiveOperator>(
4659 implicit_pickup_delivery_pairs_without_alternatives_),
4660 insertion_operator});
4662 return insertion_operator;
4665 LocalSearchOperator* RoutingModel::CreateMakeInactiveOperator() {
4666 LocalSearchOperator* make_inactive_operator =
4667 CreateCPOperator<MakeInactiveOperator>();
4668 if (!pickup_delivery_pairs_.empty()) {
4669 make_inactive_operator = solver_->ConcatenateOperators(
4670 {CreatePairOperator<MakePairInactiveOperator>(),
4671 make_inactive_operator});
4673 return make_inactive_operator;
4676 void RoutingModel::CreateNeighborhoodOperators(
4678 local_search_operators_.clear();
4679 local_search_operators_.resize(LOCAL_SEARCH_OPERATOR_COUNTER,
nullptr);
4683 std::pair<RoutingLocalSearchOperator, Solver::LocalSearchOperators>>
4688 for (
const auto [type, op] : operator_by_type) {
4689 local_search_operators_[type] =
4691 ? solver_->MakeOperator(nexts_, op)
4692 : solver_->MakeOperator(nexts_, vehicle_vars_, op);
4697 const std::vector<std::pair<RoutingLocalSearchOperator,
4699 operator_by_type = {{LIN_KERNIGHAN,
Solver::LK},
4702 for (
const auto [type, op] : operator_by_type) {
4705 local_search_operators_[type] =
4707 ? solver_->MakeOperator(nexts_, std::move(arc_cost), op)
4708 : solver_->MakeOperator(nexts_, vehicle_vars_,
4709 std::move(arc_cost), op);
4714 local_search_operators_[RELOCATE] = CreateCPOperator<Relocate>();
4715 local_search_operators_[EXCHANGE] = CreateCPOperator<Exchange>();
4716 local_search_operators_[CROSS] = CreateCPOperator<Cross>();
4717 local_search_operators_[TWO_OPT] = CreateCPOperator<TwoOpt>();
4718 local_search_operators_[RELOCATE_AND_MAKE_ACTIVE] =
4719 CreateCPOperator<RelocateAndMakeActiveOperator>();
4720 local_search_operators_[MAKE_ACTIVE_AND_RELOCATE] =
4721 CreateCPOperator<MakeActiveAndRelocate>();
4722 local_search_operators_[MAKE_CHAIN_INACTIVE] =
4723 CreateCPOperator<MakeChainInactiveOperator>();
4724 local_search_operators_[SWAP_ACTIVE] = CreateCPOperator<SwapActiveOperator>();
4725 local_search_operators_[EXTENDED_SWAP_ACTIVE] =
4726 CreateCPOperator<ExtendedSwapActiveOperator>();
4727 std::vector<std::vector<int64_t>> alternative_sets(disjunctions_.size());
4728 for (
const RoutingModel::Disjunction& disjunction : disjunctions_) {
4729 alternative_sets.push_back(disjunction.indices);
4731 local_search_operators_[SHORTEST_PATH_SWAP_ACTIVE] =
4732 CreateOperator<SwapActiveToShortestPathOperator>(
4733 std::move(alternative_sets),
4737 local_search_operators_[MAKE_ACTIVE] = CreateInsertionOperator();
4738 local_search_operators_[MAKE_INACTIVE] = CreateMakeInactiveOperator();
4739 local_search_operators_[RELOCATE_PAIR] =
4740 CreatePairOperator<PairRelocateOperator>();
4741 std::vector<LocalSearchOperator*> light_relocate_pair_operators;
4742 light_relocate_pair_operators.push_back(
4743 CreateOperator<LightPairRelocateOperator>(
4744 pickup_delivery_pairs_, [
this](int64_t
start) {
4748 light_relocate_pair_operators.push_back(
4749 CreatePairOperator<GroupPairAndRelocateOperator>());
4750 local_search_operators_[LIGHT_RELOCATE_PAIR] =
4751 solver_->ConcatenateOperators(light_relocate_pair_operators);
4752 local_search_operators_[EXCHANGE_PAIR] = solver_->ConcatenateOperators(
4753 {CreatePairOperator<PairExchangeOperator>(),
4754 CreatePairOperator<SwapIndexPairOperator>()});
4755 local_search_operators_[EXCHANGE_RELOCATE_PAIR] =
4756 CreatePairOperator<PairExchangeRelocateOperator>();
4757 local_search_operators_[RELOCATE_NEIGHBORS] =
4758 CreateOperator<MakeRelocateNeighborsOperator>(
4760 local_search_operators_[NODE_PAIR_SWAP] = solver_->ConcatenateOperators(
4761 {CreatePairOperator<IndexPairSwapActiveOperator>(),
4762 CreatePairOperator<PairNodeSwapActiveOperator<true>>(),
4763 CreatePairOperator<PairNodeSwapActiveOperator<false>>()});
4764 local_search_operators_[RELOCATE_SUBTRIP] =
4765 CreatePairOperator<RelocateSubtrip>();
4766 local_search_operators_[EXCHANGE_SUBTRIP] =
4767 CreatePairOperator<ExchangeSubtrip>();
4769 const auto arc_cost_for_path_start =
4770 [
this](int64_t before_node, int64_t after_node, int64_t start_index) {
4772 const int64_t arc_cost =
4774 return (before_node != start_index ||
IsEnd(after_node))
4778 local_search_operators_[RELOCATE_EXPENSIVE_CHAIN] =
4779 solver_->RevAlloc(
new RelocateExpensiveChain(
4783 vehicle_start_class_callback_,
4784 parameters.relocate_expensive_chain_num_arcs_to_consider(),
4785 arc_cost_for_path_start));
4788 const auto make_global_cheapest_insertion_filtered_heuristic =
4790 using Heuristic = GlobalCheapestInsertionFilteredHeuristic;
4791 Heuristic::GlobalCheapestInsertionParameters ls_gci_parameters;
4792 ls_gci_parameters.is_sequential =
false;
4793 ls_gci_parameters.farthest_seeds_ratio = 0.0;
4794 ls_gci_parameters.neighbors_ratio =
4795 parameters.cheapest_insertion_ls_operator_neighbors_ratio();
4796 ls_gci_parameters.min_neighbors =
4797 parameters.cheapest_insertion_ls_operator_min_neighbors();
4798 ls_gci_parameters.use_neighbors_ratio_for_initialization =
true;
4799 ls_gci_parameters.add_unperformed_entries =
4800 parameters.cheapest_insertion_add_unperformed_entries();
4801 return std::make_unique<Heuristic>(
4802 this, [
this]() {
return CheckLimit(time_buffer_); },
4805 GetOrCreateLocalSearchFilterManager(
4810 const auto make_local_cheapest_insertion_filtered_heuristic =
4812 return std::make_unique<LocalCheapestInsertionFilteredHeuristic>(
4813 this, [
this]() {
return CheckLimit(time_buffer_); },
4815 parameters.local_cheapest_insertion_pickup_delivery_strategy(),
4816 GetOrCreateLocalSearchFilterManager(
4820 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
4821 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
4822 make_global_cheapest_insertion_filtered_heuristic(),
4823 parameters.heuristic_close_nodes_lns_num_nodes()));
4825 local_search_operators_[LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS] =
4826 solver_->RevAlloc(
new FilteredHeuristicCloseNodesLNSOperator(
4827 make_local_cheapest_insertion_filtered_heuristic(),
4828 parameters.heuristic_close_nodes_lns_num_nodes()));
4830 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_PATH_LNS] =
4831 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
4832 make_global_cheapest_insertion_filtered_heuristic()));
4834 local_search_operators_[LOCAL_CHEAPEST_INSERTION_PATH_LNS] =
4835 solver_->RevAlloc(
new FilteredHeuristicPathLNSOperator(
4836 make_local_cheapest_insertion_filtered_heuristic()));
4838 local_search_operators_
4839 [RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED] =
4841 new RelocatePathAndHeuristicInsertUnperformedOperator(
4842 make_global_cheapest_insertion_filtered_heuristic()));
4844 local_search_operators_[GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
4845 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
4846 make_global_cheapest_insertion_filtered_heuristic(),
4847 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
4848 arc_cost_for_path_start));
4850 local_search_operators_[LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS] =
4851 solver_->RevAlloc(
new FilteredHeuristicExpensiveChainLNSOperator(
4852 make_local_cheapest_insertion_filtered_heuristic(),
4853 parameters.heuristic_expensive_chain_lns_num_arcs_to_consider(),
4854 arc_cost_for_path_start));
4857 #define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method, operators) \
4858 if (search_parameters.local_search_operators().use_##operator_method() == \
4860 operators.push_back(local_search_operators_[operator_type]); \
4863 LocalSearchOperator* RoutingModel::ConcatenateOperators(
4864 const RoutingSearchParameters& search_parameters,
4865 const std::vector<LocalSearchOperator*>& operators)
const {
4866 if (search_parameters.use_multi_armed_bandit_concatenate_operators()) {
4867 return solver_->MultiArmedBanditConcatenateOperators(
4870 .multi_armed_bandit_compound_operator_memory_coefficient(),
4872 .multi_armed_bandit_compound_operator_exploration_coefficient(),
4875 return solver_->ConcatenateOperators(operators);
4878 LocalSearchOperator* RoutingModel::GetNeighborhoodOperators(
4879 const RoutingSearchParameters& search_parameters)
const {
4880 std::vector<LocalSearchOperator*> operator_groups;
4881 std::vector<LocalSearchOperator*> operators = extra_operators_;
4882 if (!pickup_delivery_pairs_.empty()) {
4886 if (search_parameters.local_search_operators().use_relocate_pair() ==
4896 if (vehicles_ > 1) {
4907 if (!pickup_delivery_pairs_.empty() ||
4908 search_parameters.local_search_operators().use_relocate_neighbors() ==
4910 operators.push_back(local_search_operators_[RELOCATE_NEIGHBORS]);
4913 search_parameters.local_search_metaheuristic();
4914 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4915 local_search_metaheuristic !=
4916 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4917 local_search_metaheuristic !=
4918 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4925 if (!disjunctions_.empty()) {
4942 shortest_path_swap_active, operators);
4944 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4953 global_cheapest_insertion_path_lns, operators);
4955 local_cheapest_insertion_path_lns, operators);
4957 RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,
4958 relocate_path_global_cheapest_insertion_insert_unperformed, operators);
4961 global_cheapest_insertion_expensive_chain_lns,
4964 local_cheapest_insertion_expensive_chain_lns,
4967 global_cheapest_insertion_close_nodes_lns,
4970 local_cheapest_insertion_close_nodes_lns, operators);
4971 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4975 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4976 local_search_metaheuristic !=
4977 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4978 local_search_metaheuristic !=
4979 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4982 if (local_search_metaheuristic != LocalSearchMetaheuristic::TABU_SEARCH &&
4983 local_search_metaheuristic !=
4984 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH &&
4985 local_search_metaheuristic !=
4986 LocalSearchMetaheuristic::SIMULATED_ANNEALING) {
4991 if (!disjunctions_.empty()) {
4994 operator_groups.push_back(ConcatenateOperators(search_parameters, operators));
4996 return solver_->ConcatenateOperators(operator_groups);
4999 #undef CP_ROUTING_PUSH_OPERATOR
5003 void ConvertVectorInt64ToVectorInt(
const std::vector<int64_t>&
input,
5004 std::vector<int>* output) {
5005 const int n =
input.size();
5007 int* data = output->data();
5008 for (
int i = 0; i < n; ++i) {
5009 const int element =
static_cast<int>(
input[i]);
5010 DCHECK_EQ(
input[i],
static_cast<int64_t
>(element));
5017 std::vector<LocalSearchFilterManager::FilterEvent>
5018 RoutingModel::CreateLocalSearchFilters(
5019 const RoutingSearchParameters&
parameters,
const FilterOptions& options) {
5020 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
5021 const auto kRelax = LocalSearchFilterManager::FilterEventType::kRelax;
5031 std::vector<LocalSearchFilterManager::FilterEvent> filter_events;
5035 if (options.filter_objective && vehicle_amortized_cost_factors_set_) {
5036 filter_events.push_back(
5043 if (options.filter_objective) {
5045 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
5049 filter_events.push_back({sum, kAccept, priority});
5051 LocalSearchFilter* sum = solver_->MakeSumObjectiveFilter(
5052 nexts_, vehicle_vars_,
5053 [
this](int64_t i, int64_t j, int64_t k) {
5057 filter_events.push_back({sum, kAccept, priority});
5060 const PathState* path_state_reference =
nullptr;
5062 std::vector<int> path_starts;
5063 std::vector<int> path_ends;
5064 ConvertVectorInt64ToVectorInt(paths_metadata_.Starts(), &path_starts);
5065 ConvertVectorInt64ToVectorInt(paths_metadata_.Ends(), &path_ends);
5066 auto path_state = std::make_unique<PathState>(
5067 Size() +
vehicles(), std::move(path_starts), std::move(path_ends));
5068 path_state_reference = path_state.get();
5069 filter_events.push_back(
5076 filter_events.push_back(
5077 {solver_->MakeVariableDomainFilter(), kAccept, priority});
5079 if (vehicles_ > max_active_vehicles_) {
5080 filter_events.push_back(
5084 if (!disjunctions_.empty()) {
5087 filter_events.push_back(
5089 kAccept, priority});
5103 const int first_lightweight_index = filter_events.size();
5106 for (
int e = first_lightweight_index; e < filter_events.size(); ++e) {
5107 filter_events[e].priority = priority;
5114 if (!pickup_delivery_pairs_.empty()) {
5116 filter_events.push_back(
5118 vehicle_pickup_delivery_policy_),
5119 kAccept, priority});
5124 filter_events.push_back(
5130 const int first_dimension_filter_index = filter_events.size();
5133 false, &filter_events);
5134 int max_priority = priority;
5135 for (
int e = first_dimension_filter_index; e < filter_events.size(); ++e) {
5136 filter_events[e].priority += priority;
5137 max_priority =
std::max(max_priority, filter_events[e].priority);
5139 priority = max_priority;
5146 filter_events.push_back(
5151 if (!extra_filters_.empty()) {
5153 for (
const auto& event : extra_filters_) {
5154 filter_events.push_back({
event.filter,
event.event_type, priority});
5158 if (options.filter_with_cp_solver) {
5162 return filter_events;
5165 LocalSearchFilterManager* RoutingModel::GetOrCreateLocalSearchFilterManager(
5166 const RoutingSearchParameters&
parameters,
const FilterOptions& options) {
5167 LocalSearchFilterManager* local_search_filter_manager =
5169 if (local_search_filter_manager ==
nullptr) {
5170 local_search_filter_manager =
5171 solver_->RevAlloc(
new LocalSearchFilterManager(
5172 CreateLocalSearchFilters(
parameters, options)));
5173 local_search_filter_managers_[options] = local_search_filter_manager;
5175 return local_search_filter_manager;
5180 for (
int vehicle = 0; vehicle < dimension.model()->
vehicles(); vehicle++) {
5181 if (!dimension.AreVehicleTransitsPositive(vehicle)) {
5189 void RoutingModel::StoreDimensionCumulOptimizers(
5191 Assignment* optimized_dimensions_collector_assignment =
5192 solver_->MakeAssignment();
5193 optimized_dimensions_collector_assignment->AddObjective(
CostVar());
5194 const int num_dimensions = dimensions_.size();
5195 local_optimizer_index_.resize(num_dimensions, -1);
5196 global_optimizer_index_.resize(num_dimensions, -1);
5197 if (
parameters.disable_scheduling_beware_this_may_degrade_performance()) {
5202 DCHECK_EQ(dimension->model(),
this);
5203 const int num_resource_groups =
5205 bool needs_optimizer =
false;
5206 if (dimension->global_span_cost_coefficient() > 0 ||
5207 !dimension->GetNodePrecedences().empty() || num_resource_groups > 1) {
5209 needs_optimizer =
true;
5210 global_optimizer_index_[dim] = global_dimension_optimizers_.size();
5211 global_dimension_optimizers_.push_back(
5212 {std::make_unique<GlobalDimensionCumulOptimizer>(
5213 dimension,
parameters.continuous_scheduling_solver()),
5214 std::make_unique<GlobalDimensionCumulOptimizer>(
5215 dimension,
parameters.mixed_integer_scheduling_solver())});
5216 if (!AllTransitsPositive(*dimension)) {
5217 dimension->SetOffsetForGlobalOptimizer(0);
5221 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5222 DCHECK_GE(dimension->CumulVar(
Start(vehicle))->Min(), 0);
5224 std::min(offset, dimension->CumulVar(
Start(vehicle))->Min() - 1);
5226 dimension->SetOffsetForGlobalOptimizer(
std::max(
Zero(), offset));
5230 bool has_span_cost =
false;
5231 bool has_span_limit =
false;
5232 std::vector<int64_t> vehicle_offsets(
vehicles());
5233 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5234 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
5235 has_span_cost =
true;
5237 if (dimension->GetSpanUpperBoundForVehicle(vehicle) <
5239 has_span_limit =
true;
5241 DCHECK_GE(dimension->CumulVar(
Start(vehicle))->Min(), 0);
5242 vehicle_offsets[vehicle] =
5243 dimension->AreVehicleTransitsPositive(vehicle)
5247 bool has_soft_lower_bound =
false;
5248 bool has_soft_upper_bound =
false;
5249 for (
int i = 0; i < dimension->cumuls().size(); ++i) {
5250 if (dimension->HasCumulVarSoftLowerBound(i)) {
5251 has_soft_lower_bound =
true;
5253 if (dimension->HasCumulVarSoftUpperBound(i)) {
5254 has_soft_upper_bound =
true;
5257 int num_linear_constraints = 0;
5258 if (has_span_cost) ++num_linear_constraints;
5259 if (has_span_limit) ++num_linear_constraints;
5260 if (dimension->HasSoftSpanUpperBounds()) ++num_linear_constraints;
5261 if (has_soft_lower_bound) ++num_linear_constraints;
5262 if (has_soft_upper_bound) ++num_linear_constraints;
5263 if (dimension->HasBreakConstraints()) ++num_linear_constraints;
5264 if (num_resource_groups > 0 || num_linear_constraints >= 2) {
5265 needs_optimizer =
true;
5266 dimension->SetVehicleOffsetsForLocalOptimizer(std::move(vehicle_offsets));
5267 local_optimizer_index_[dim] = local_dimension_optimizers_.size();
5268 local_dimension_optimizers_.push_back(
5269 {std::make_unique<LocalDimensionCumulOptimizer>(
5270 dimension,
parameters.continuous_scheduling_solver()),
5271 std::make_unique<LocalDimensionCumulOptimizer>(
5272 dimension,
parameters.mixed_integer_scheduling_solver())});
5274 if (needs_optimizer) {
5275 optimized_dimensions_collector_assignment->Add(dimension->cumuls());
5283 for (IntVar*
const extra_var : extra_vars_) {
5284 optimized_dimensions_collector_assignment->Add(extra_var);
5286 for (IntervalVar*
const extra_interval : extra_intervals_) {
5287 optimized_dimensions_collector_assignment->Add(extra_interval);
5290 optimized_dimensions_assignment_collector_ =
5291 solver_->MakeFirstSolutionCollector(
5292 optimized_dimensions_collector_assignment);
5299 bool has_soft_or_span_cost =
false;
5300 for (
int vehicle = 0; vehicle <
vehicles(); ++vehicle) {
5301 if (dimension->GetSpanCostCoefficientForVehicle(vehicle) > 0) {
5302 has_soft_or_span_cost =
true;
5306 if (!has_soft_or_span_cost) {
5307 for (
int i = 0; i < dimension->cumuls().size(); ++i) {
5308 if (dimension->HasCumulVarSoftUpperBound(i) ||
5309 dimension->HasCumulVarSoftLowerBound(i)) {
5310 has_soft_or_span_cost =
true;
5315 if (has_soft_or_span_cost)
dimensions.push_back(dimension);
5320 std::vector<const RoutingDimension*>
5323 std::vector<const RoutingDimension*> global_optimizer_dimensions;
5324 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
5325 DCHECK_NE(lp_optimizer.get(),
nullptr);
5326 DCHECK_NE(mp_optimizer.get(),
nullptr);
5327 global_optimizer_dimensions.push_back(lp_optimizer->dimension());
5329 return global_optimizer_dimensions;
5332 std::vector<const RoutingDimension*>
5335 std::vector<const RoutingDimension*> local_optimizer_dimensions;
5336 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
5337 DCHECK_NE(lp_optimizer.get(),
nullptr);
5338 DCHECK_NE(mp_optimizer.get(),
nullptr);
5339 local_optimizer_dimensions.push_back(lp_optimizer->dimension());
5341 return local_optimizer_dimensions;
5345 RoutingModel::CreateFinalizerForMinimizedAndMaximizedVariables() {
5346 std::stable_sort(weighted_finalizer_variable_targets_.begin(),
5347 weighted_finalizer_variable_targets_.end(),
5348 [](
const std::pair<VarTarget, int64_t>& var_cost1,
5349 const std::pair<VarTarget, int64_t>& var_cost2) {
5350 return var_cost1.second > var_cost2.second;
5352 const int num_variables = weighted_finalizer_variable_targets_.size() +
5353 finalizer_variable_targets_.size();
5354 std::vector<IntVar*> variables;
5355 std::vector<int64_t> targets;
5356 variables.reserve(num_variables);
5357 targets.reserve(num_variables);
5358 for (
const auto& [var_target,
cost] : weighted_finalizer_variable_targets_) {
5359 variables.push_back(var_target.var);
5360 targets.push_back(var_target.target);
5362 for (
const auto& [
var, target] : finalizer_variable_targets_) {
5364 targets.push_back(target);
5367 std::move(targets));
5371 const RoutingSearchParameters&
parameters)
const {
5377 if (
parameters.local_search_metaheuristic() ==
5378 LocalSearchMetaheuristic::GENERIC_TABU_SEARCH ||
5380 LocalSearchMetaheuristic::TABU_SEARCH) {
5392 DecisionBuilder* RoutingModel::CreateSolutionFinalizer(
5393 const RoutingSearchParameters&
parameters, SearchLimit* lns_limit) {
5394 std::vector<DecisionBuilder*> decision_builders;
5395 decision_builders.push_back(solver_->MakePhase(
5402 decision_builders.push_back(
5405 const bool can_use_dimension_cumul_optimizers =
5406 !
parameters.disable_scheduling_beware_this_may_degrade_performance();
5407 DCHECK(local_dimension_optimizers_.empty() ||
5408 can_use_dimension_cumul_optimizers);
5409 for (
auto& [lp_optimizer, mp_optimizer] : local_dimension_optimizers_) {
5417 decision_builders.push_back(
5418 solver_->RevAlloc(
new SetCumulsFromLocalDimensionCosts(
5419 lp_optimizer.get(), mp_optimizer.get(), lns_limit)));
5423 if (can_use_dimension_cumul_optimizers) {
5429 LocalDimensionCumulOptimizer*
const optimizer =
5431 DCHECK_NE(optimizer,
nullptr);
5432 LocalDimensionCumulOptimizer*
const mp_optimizer =
5434 DCHECK_NE(mp_optimizer,
nullptr);
5435 decision_builders.push_back(
5436 solver_->RevAlloc(
new SetCumulsFromResourceAssignmentCosts(
5437 optimizer, mp_optimizer, lns_limit)));
5441 DCHECK(global_dimension_optimizers_.empty() ||
5442 can_use_dimension_cumul_optimizers);
5443 for (
auto& [lp_optimizer, mp_optimizer] : global_dimension_optimizers_) {
5444 decision_builders.push_back(
5445 solver_->RevAlloc(
new SetCumulsFromGlobalDimensionCosts(
5446 lp_optimizer.get(), mp_optimizer.get(), lns_limit)));
5448 decision_builders.push_back(
5449 CreateFinalizerForMinimizedAndMaximizedVariables());
5451 return solver_->Compose(decision_builders);
5454 void RoutingModel::CreateFirstSolutionDecisionBuilders(
5455 const RoutingSearchParameters& search_parameters) {
5456 first_solution_decision_builders_.resize(
5457 FirstSolutionStrategy_Value_Value_ARRAYSIZE,
nullptr);
5458 first_solution_filtered_decision_builders_.resize(
5459 FirstSolutionStrategy_Value_Value_ARRAYSIZE,
nullptr);
5460 DecisionBuilder*
const finalize_solution = CreateSolutionFinalizer(
5461 search_parameters, GetOrCreateLargeNeighborhoodSearchLimit());
5463 first_solution_decision_builders_
5464 [FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE] = finalize_solution;
5466 first_solution_decision_builders_
5467 [FirstSolutionStrategy::GLOBAL_CHEAPEST_ARC] = solver_->MakePhase(
5469 [
this](int64_t i, int64_t j) {
5477 first_solution_decision_builders_[FirstSolutionStrategy::LOCAL_CHEAPEST_ARC] =
5480 first_solution_decision_builders_[FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5482 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5483 first_solution_filtered_decision_builders_
5484 [FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5485 CreateIntVarFilteredDecisionBuilder<
5486 EvaluatorCheapestAdditionFilteredHeuristic>(
5487 [
this](int64_t i, int64_t j) {
5490 GetOrCreateLocalSearchFilterManager(
5491 search_parameters, {
false,
5493 first_solution_decision_builders_
5494 [FirstSolutionStrategy::PATH_CHEAPEST_ARC] =
5495 solver_->Try(first_solution_filtered_decision_builders_
5496 [FirstSolutionStrategy::PATH_CHEAPEST_ARC],
5497 first_solution_decision_builders_
5498 [FirstSolutionStrategy::PATH_CHEAPEST_ARC]);
5506 first_solution_decision_builders_
5507 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] =
5509 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5510 first_solution_filtered_decision_builders_
5511 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] =
5512 CreateIntVarFilteredDecisionBuilder<
5513 ComparatorCheapestAdditionFilteredHeuristic>(
5515 GetOrCreateLocalSearchFilterManager(
5516 search_parameters, {
false,
5518 first_solution_decision_builders_
5519 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC] = solver_->Try(
5520 first_solution_filtered_decision_builders_
5521 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC],
5522 first_solution_decision_builders_
5523 [FirstSolutionStrategy::PATH_MOST_CONSTRAINED_ARC]);
5526 if (first_solution_evaluator_ !=
nullptr) {
5527 first_solution_decision_builders_
5528 [FirstSolutionStrategy::EVALUATOR_STRATEGY] = solver_->MakePhase(
5531 first_solution_decision_builders_
5532 [FirstSolutionStrategy::EVALUATOR_STRATEGY] =
nullptr;
5535 first_solution_decision_builders_[FirstSolutionStrategy::ALL_UNPERFORMED] =
5538 RegularLimit*
const ls_limit = solver_->MakeLimit(
5542 DecisionBuilder*
const finalize = solver_->MakeSolveOnce(
5543 finalize_solution, GetOrCreateLargeNeighborhoodSearchLimit());
5544 LocalSearchPhaseParameters*
const insertion_parameters =
5545 solver_->MakeLocalSearchPhaseParameters(
5546 nullptr, CreateInsertionOperator(), finalize, ls_limit,
5547 GetOrCreateLocalSearchFilterManager(
5550 std::vector<IntVar*> decision_vars = nexts_;
5552 decision_vars.insert(decision_vars.end(), vehicle_vars_.begin(),
5553 vehicle_vars_.end());
5555 const int64_t optimization_step =
std::max(
5557 first_solution_decision_builders_[FirstSolutionStrategy::BEST_INSERTION] =
5558 solver_->MakeNestedOptimize(
5560 insertion_parameters),
5561 GetOrCreateAssignment(),
false, optimization_step);
5562 first_solution_decision_builders_[FirstSolutionStrategy::BEST_INSERTION] =
5563 solver_->Compose(first_solution_decision_builders_
5564 [FirstSolutionStrategy::BEST_INSERTION],
5568 GlobalCheapestInsertionFilteredHeuristic::GlobalCheapestInsertionParameters
5570 gci_parameters.is_sequential =
false;
5571 gci_parameters.farthest_seeds_ratio =
5572 search_parameters.cheapest_insertion_farthest_seeds_ratio();
5573 gci_parameters.neighbors_ratio =
5574 search_parameters.cheapest_insertion_first_solution_neighbors_ratio();
5575 gci_parameters.min_neighbors =
5576 search_parameters.cheapest_insertion_first_solution_min_neighbors();
5577 gci_parameters.use_neighbors_ratio_for_initialization =
5579 .cheapest_insertion_first_solution_use_neighbors_ratio_for_initialization();
5580 gci_parameters.add_unperformed_entries =
5581 search_parameters.cheapest_insertion_add_unperformed_entries();
5582 for (
bool is_sequential : {
false,
true}) {
5584 is_sequential ? FirstSolutionStrategy::SEQUENTIAL_CHEAPEST_INSERTION
5585 : FirstSolutionStrategy::PARALLEL_CHEAPEST_INSERTION;
5586 gci_parameters.is_sequential = is_sequential;
5588 first_solution_filtered_decision_builders_[first_solution_strategy] =
5589 CreateIntVarFilteredDecisionBuilder<
5590 GlobalCheapestInsertionFilteredHeuristic>(
5591 [
this](int64_t i, int64_t j, int64_t vehicle) {
5595 GetOrCreateLocalSearchFilterManager(
5596 search_parameters, {
false,
5599 IntVarFilteredDecisionBuilder*
const strong_gci =
5600 CreateIntVarFilteredDecisionBuilder<
5601 GlobalCheapestInsertionFilteredHeuristic>(
5602 [
this](int64_t i, int64_t j, int64_t vehicle) {
5606 GetOrCreateLocalSearchFilterManager(
5607 search_parameters, {
false,
5610 first_solution_decision_builders_[first_solution_strategy] = solver_->Try(
5611 first_solution_filtered_decision_builders_[first_solution_strategy],
5612 solver_->Try(strong_gci, first_solution_decision_builders_
5613 [FirstSolutionStrategy::BEST_INSERTION]));
5617 const RoutingSearchParameters::PairInsertionStrategy lci_pair_strategy =
5618 search_parameters.local_cheapest_insertion_pickup_delivery_strategy();
5619 first_solution_filtered_decision_builders_
5620 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION] =
5621 CreateIntVarFilteredDecisionBuilder<
5622 LocalCheapestInsertionFilteredHeuristic>(
5623 [
this](int64_t i, int64_t j, int64_t vehicle) {
5627 GetOrCreateLocalSearchFilterManager(
5628 search_parameters, {
false,
5630 IntVarFilteredDecisionBuilder*
const strong_lci =
5631 CreateIntVarFilteredDecisionBuilder<
5632 LocalCheapestInsertionFilteredHeuristic>(
5633 [
this](int64_t i, int64_t j, int64_t vehicle) {
5637 GetOrCreateLocalSearchFilterManager(
5638 search_parameters, {
false,
5640 first_solution_decision_builders_
5641 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION] = solver_->Try(
5642 first_solution_filtered_decision_builders_
5643 [FirstSolutionStrategy::LOCAL_CHEAPEST_INSERTION],
5644 solver_->Try(strong_lci,
5645 first_solution_decision_builders_
5646 [FirstSolutionStrategy::BEST_INSERTION]));
5649 first_solution_filtered_decision_builders_
5650 [FirstSolutionStrategy::LOCAL_CHEAPEST_COST_INSERTION] =
5651 CreateIntVarFilteredDecisionBuilder<
5652 LocalCheapestInsertionFilteredHeuristic>(
5654 RoutingSearchParameters::BEST_PICKUP_DELIVERY_PAIR,
5655 GetOrCreateLocalSearchFilterManager(
5656 search_parameters, {
true,
5658 IntVarFilteredDecisionBuilder*
const strong_lcci =
5659 CreateIntVarFilteredDecisionBuilder<
5660 LocalCheapestInsertionFilteredHeuristic>(
5662 RoutingSearchParameters::BEST_PICKUP_DELIVERY_PAIR,
5663 GetOrCreateLocalSearchFilterManager(
5664 search_parameters, {
true,
5666 first_solution_decision_builders_
5667 [FirstSolutionStrategy::LOCAL_CHEAPEST_COST_INSERTION] = solver_->Try(
5668 first_solution_filtered_decision_builders_
5669 [FirstSolutionStrategy::LOCAL_CHEAPEST_COST_INSERTION],
5670 solver_->Try(strong_lcci,
5671 first_solution_decision_builders_
5672 [FirstSolutionStrategy::BEST_INSERTION]));
5675 SavingsFilteredHeuristic::SavingsParameters savings_parameters;
5676 savings_parameters.neighbors_ratio =
5677 search_parameters.savings_neighbors_ratio();
5678 savings_parameters.max_memory_usage_bytes =
5679 search_parameters.savings_max_memory_usage_bytes();
5680 savings_parameters.add_reverse_arcs =
5681 search_parameters.savings_add_reverse_arcs();
5682 savings_parameters.arc_coefficient =
5683 search_parameters.savings_arc_coefficient();
5684 LocalSearchFilterManager* filter_manager =
nullptr;
5685 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5686 filter_manager = GetOrCreateLocalSearchFilterManager(
5691 if (search_parameters.savings_parallel_routes()) {
5692 IntVarFilteredDecisionBuilder* savings_db =
5693 CreateIntVarFilteredDecisionBuilder<ParallelSavingsFilteredHeuristic>(
5694 savings_parameters, filter_manager);
5695 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5696 first_solution_filtered_decision_builders_
5697 [FirstSolutionStrategy::SAVINGS] = savings_db;
5700 first_solution_decision_builders_[FirstSolutionStrategy::SAVINGS] =
5701 solver_->Try(savings_db, CreateIntVarFilteredDecisionBuilder<
5702 ParallelSavingsFilteredHeuristic>(
5704 GetOrCreateLocalSearchFilterManager(
5709 IntVarFilteredDecisionBuilder* savings_db =
5710 CreateIntVarFilteredDecisionBuilder<SequentialSavingsFilteredHeuristic>(
5711 savings_parameters, filter_manager);
5712 if (!search_parameters.use_unfiltered_first_solution_strategy()) {
5713 first_solution_filtered_decision_builders_
5714 [FirstSolutionStrategy::SAVINGS] = savings_db;
5717 first_solution_decision_builders_[FirstSolutionStrategy::SAVINGS] =
5718 solver_->Try(savings_db, CreateIntVarFilteredDecisionBuilder<
5719 SequentialSavingsFilteredHeuristic>(
5721 GetOrCreateLocalSearchFilterManager(
5727 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP] =
5730 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP] =
5733 first_solution_decision_builders_[FirstSolutionStrategy::SWEEP]);
5735 first_solution_decision_builders_[FirstSolutionStrategy::CHRISTOFIDES] =
5736 CreateIntVarFilteredDecisionBuilder<ChristofidesFilteredHeuristic>(
5737 GetOrCreateLocalSearchFilterManager(
5738 search_parameters, {
false,
5740 search_parameters.christofides_use_minimum_matching());
5742 const bool has_precedences = std::any_of(
5743 dimensions_.begin(), dimensions_.end(),
5745 bool has_single_vehicle_node =
false;
5746 for (
int node = 0; node <
Size(); node++) {
5747 if (!
IsStart(node) && !
IsEnd(node) && allowed_vehicles_[node].size() == 1) {
5748 has_single_vehicle_node =
true;
5752 automatic_first_solution_strategy_ =
5754 has_precedences, has_single_vehicle_node);
5755 first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC] =
5756 first_solution_decision_builders_[automatic_first_solution_strategy_];
5757 first_solution_decision_builders_[FirstSolutionStrategy::UNSET] =
5758 first_solution_decision_builders_[FirstSolutionStrategy::AUTOMATIC];
5761 for (FirstSolutionStrategy_Value strategy =
5762 FirstSolutionStrategy_Value_Value_MIN;
5763 strategy <= FirstSolutionStrategy_Value_Value_MAX;
5764 strategy = FirstSolutionStrategy_Value(strategy + 1)) {
5765 if (first_solution_decision_builders_[strategy] ==
nullptr ||
5766 strategy == FirstSolutionStrategy::AUTOMATIC) {
5769 const std::string strategy_name =
5770 FirstSolutionStrategy_Value_Name(strategy);
5771 const std::string& log_tag = search_parameters.log_tag();
5772 if (!log_tag.empty() && log_tag != strategy_name) {
5773 first_solution_decision_builders_[strategy]->set_name(absl::StrFormat(
5774 "%s / %s", strategy_name, search_parameters.log_tag()));
5776 first_solution_decision_builders_[strategy]->set_name(strategy_name);
5781 DecisionBuilder* RoutingModel::GetFirstSolutionDecisionBuilder(
5782 const RoutingSearchParameters& search_parameters)
const {
5784 search_parameters.first_solution_strategy();
5785 if (first_solution_strategy < first_solution_decision_builders_.size()) {
5786 return first_solution_decision_builders_[first_solution_strategy];
5792 IntVarFilteredDecisionBuilder*
5793 RoutingModel::GetFilteredFirstSolutionDecisionBuilderOrNull(
5794 const RoutingSearchParameters& search_parameters)
const {
5796 search_parameters.first_solution_strategy();
5797 return first_solution_filtered_decision_builders_[first_solution_strategy];
5800 template <
typename Heuristic,
typename... Args>
5801 IntVarFilteredDecisionBuilder*
5802 RoutingModel::CreateIntVarFilteredDecisionBuilder(
const Args&... args) {
5803 return solver_->RevAlloc(
5804 new IntVarFilteredDecisionBuilder(std::make_unique<Heuristic>(
5805 this, [
this]() {
return CheckLimit(time_buffer_); }, args...)));
5808 LocalSearchPhaseParameters* RoutingModel::CreateLocalSearchParameters(
5809 const RoutingSearchParameters& search_parameters) {
5810 SearchLimit* lns_limit = GetOrCreateLargeNeighborhoodSearchLimit();
5811 return solver_->MakeLocalSearchPhaseParameters(
5812 CostVar(), GetNeighborhoodOperators(search_parameters),
5813 solver_->MakeSolveOnce(
5814 CreateSolutionFinalizer(search_parameters, lns_limit), lns_limit),
5815 GetOrCreateLocalSearchLimit(),
5816 GetOrCreateLocalSearchFilterManager(
5821 DecisionBuilder* RoutingModel::CreateLocalSearchDecisionBuilder(
5822 const RoutingSearchParameters& search_parameters) {
5823 const int size =
Size();
5824 DecisionBuilder* first_solution =
5825 GetFirstSolutionDecisionBuilder(search_parameters);
5826 LocalSearchPhaseParameters*
const parameters =
5827 CreateLocalSearchParameters(search_parameters);
5828 SearchLimit* first_solution_lns_limit =
5829 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
5830 DecisionBuilder*
const first_solution_sub_decision_builder =
5831 solver_->MakeSolveOnce(
5832 CreateSolutionFinalizer(search_parameters, first_solution_lns_limit),
5833 first_solution_lns_limit);
5835 return solver_->MakeLocalSearchPhase(nexts_, first_solution,
5836 first_solution_sub_decision_builder,
5839 const int all_size = size + size + vehicles_;
5840 std::vector<IntVar*> all_vars(all_size);
5841 for (
int i = 0; i < size; ++i) {
5842 all_vars[i] = nexts_[i];
5844 for (
int i = size; i < all_size; ++i) {
5845 all_vars[i] = vehicle_vars_[i - size];
5847 return solver_->MakeLocalSearchPhase(all_vars, first_solution,
5848 first_solution_sub_decision_builder,
5853 void RoutingModel::SetupDecisionBuilders(
5854 const RoutingSearchParameters& search_parameters) {
5855 if (search_parameters.use_depth_first_search()) {
5856 SearchLimit* first_lns_limit =
5857 GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
5858 solve_db_ = solver_->Compose(
5859 GetFirstSolutionDecisionBuilder(search_parameters),
5860 solver_->MakeSolveOnce(
5861 CreateSolutionFinalizer(search_parameters, first_lns_limit),
5864 solve_db_ = CreateLocalSearchDecisionBuilder(search_parameters);
5866 CHECK(preassignment_ !=
nullptr);
5867 DecisionBuilder* restore_preassignment =
5868 solver_->MakeRestoreAssignment(preassignment_);
5869 solve_db_ = solver_->Compose(restore_preassignment, solve_db_);
5871 solver_->Compose(restore_preassignment,
5872 solver_->MakeLocalSearchPhase(
5873 GetOrCreateAssignment(),
5874 CreateLocalSearchParameters(search_parameters)));
5875 restore_assignment_ = solver_->Compose(
5876 solver_->MakeRestoreAssignment(GetOrCreateAssignment()),
5877 CreateSolutionFinalizer(search_parameters,
5878 GetOrCreateLargeNeighborhoodSearchLimit()));
5879 restore_tmp_assignment_ = solver_->Compose(
5880 restore_preassignment,
5881 solver_->MakeRestoreAssignment(GetOrCreateTmpAssignment()),
5882 CreateSolutionFinalizer(search_parameters,
5883 GetOrCreateLargeNeighborhoodSearchLimit()));
5886 void RoutingModel::SetupMetaheuristics(
5887 const RoutingSearchParameters& search_parameters) {
5888 SearchMonitor* optimize =
nullptr;
5890 search_parameters.local_search_metaheuristic();
5893 bool limit_too_long =
5894 !search_parameters.has_time_limit() &&
5896 const int64_t optimization_step =
std::max(
5898 switch (metaheuristic) {
5899 case LocalSearchMetaheuristic::GUIDED_LOCAL_SEARCH:
5901 optimize = solver_->MakeGuidedLocalSearch(
5904 optimization_step, nexts_,
5905 search_parameters.guided_local_search_lambda_coefficient(),
5907 .guided_local_search_reset_penalties_on_new_best_solution());
5909 optimize = solver_->MakeGuidedLocalSearch(
5911 [
this](int64_t i, int64_t j, int64_t k) {
5914 optimization_step, nexts_, vehicle_vars_,
5915 search_parameters.guided_local_search_lambda_coefficient(),
5917 .guided_local_search_reset_penalties_on_new_best_solution());
5920 case LocalSearchMetaheuristic::SIMULATED_ANNEALING:
5922 solver_->MakeSimulatedAnnealing(
false, cost_, optimization_step, 100);
5924 case LocalSearchMetaheuristic::TABU_SEARCH:
5925 optimize = solver_->MakeTabuSearch(
false, cost_, optimization_step,
5926 nexts_, 10, 10, .8);
5928 case LocalSearchMetaheuristic::GENERIC_TABU_SEARCH: {
5929 std::vector<operations_research::IntVar*> tabu_vars;
5930 if (tabu_var_callback_) {
5931 tabu_vars = tabu_var_callback_(
this);
5933 tabu_vars.push_back(cost_);
5935 optimize = solver_->MakeGenericTabuSearch(
false, cost_, optimization_step,
5940 limit_too_long =
false;
5941 optimize = solver_->MakeMinimize(cost_, optimization_step);
5943 if (limit_too_long) {
5944 LOG(WARNING) << LocalSearchMetaheuristic::Value_Name(metaheuristic)
5945 <<
" specified without sane timeout: solve may run forever.";
5947 monitors_.push_back(optimize);
5951 tabu_var_callback_ = std::move(tabu_var_callback);
5954 void RoutingModel::SetupAssignmentCollector(
5955 const RoutingSearchParameters& search_parameters) {
5956 Assignment* full_assignment = solver_->MakeAssignment();
5958 full_assignment->Add(dimension->cumuls());
5960 for (IntVar*
const extra_var : extra_vars_) {
5961 full_assignment->Add(extra_var);
5963 for (IntervalVar*
const extra_interval : extra_intervals_) {
5964 full_assignment->Add(extra_interval);
5966 full_assignment->Add(nexts_);
5967 full_assignment->Add(active_);
5968 full_assignment->Add(vehicle_vars_);
5969 full_assignment->AddObjective(cost_);
5971 collect_assignments_ = solver_->MakeNBestValueSolutionCollector(
5972 full_assignment, search_parameters.number_of_solutions_to_collect(),
5974 collect_one_assignment_ =
5975 solver_->MakeFirstSolutionCollector(full_assignment);
5976 monitors_.push_back(collect_assignments_);
5979 void RoutingModel::SetupTrace(
5980 const RoutingSearchParameters& search_parameters) {
5981 if (search_parameters.log_search()) {
5982 Solver::SearchLogParameters search_log_parameters;
5983 search_log_parameters.branch_period = 10000;
5984 search_log_parameters.objective =
nullptr;
5985 search_log_parameters.variable = cost_;
5986 search_log_parameters.scaling_factor =
5987 search_parameters.log_cost_scaling_factor();
5988 search_log_parameters.offset = search_parameters.log_cost_offset();
5989 if (!search_parameters.log_tag().empty()) {
5990 const std::string& tag = search_parameters.log_tag();
5991 search_log_parameters.display_callback = [tag]() {
return tag; };
5993 search_log_parameters.display_callback =
nullptr;
5995 search_log_parameters.display_on_new_solutions_only =
false;
5996 monitors_.push_back(solver_->MakeSearchLog(search_log_parameters));
6000 void RoutingModel::SetupImprovementLimit(
6001 const RoutingSearchParameters& search_parameters) {
6002 if (search_parameters.has_improvement_limit_parameters()) {
6003 monitors_.push_back(solver_->MakeImprovementLimit(
6004 cost_,
false, search_parameters.log_cost_scaling_factor(),
6005 search_parameters.log_cost_offset(),
6006 search_parameters.improvement_limit_parameters()
6007 .improvement_rate_coefficient(),
6008 search_parameters.improvement_limit_parameters()
6009 .improvement_rate_solutions_distance()));
6015 template <
typename EndInitialPropagationCallback,
typename LocalOptimumCallback>
6016 class LocalOptimumWatcher :
public SearchMonitor {
6018 LocalOptimumWatcher(
6020 EndInitialPropagationCallback end_initial_propagation_callback,
6021 LocalOptimumCallback local_optimum_callback)
6023 end_initial_propagation_callback_(
6024 std::move(end_initial_propagation_callback)),
6025 local_optimum_callback_(std::move(local_optimum_callback)) {}
6026 void Install()
override {
6030 void EndInitialPropagation()
override { end_initial_propagation_callback_(); }
6031 bool LocalOptimum()
override {
6032 local_optimum_callback_();
6037 EndInitialPropagationCallback end_initial_propagation_callback_;
6038 LocalOptimumCallback local_optimum_callback_;
6041 template <
typename EndInitialPropagationCallback,
typename LocalOptimumCallback>
6042 SearchMonitor* MakeLocalOptimumWatcher(
6044 EndInitialPropagationCallback end_initial_propagation_callback,
6045 LocalOptimumCallback local_optimum_callback) {
6046 return solver->
RevAlloc(
new LocalOptimumWatcher<EndInitialPropagationCallback,
6047 LocalOptimumCallback>(
6048 solver, std::move(end_initial_propagation_callback),
6049 std::move(local_optimum_callback)));
6054 void RoutingModel::SetupSearchMonitors(
6055 const RoutingSearchParameters& search_parameters) {
6056 monitors_.push_back(GetOrCreateLimit());
6057 monitors_.push_back(MakeLocalOptimumWatcher(
6060 objective_lower_bound_ =
6063 [
this]() { local_optimum_reached_ =
true; }));
6064 SetupImprovementLimit(search_parameters);
6065 SetupMetaheuristics(search_parameters);
6066 SetupAssignmentCollector(search_parameters);
6067 SetupTrace(search_parameters);
6070 bool RoutingModel::UsesLightPropagation(
6071 const RoutingSearchParameters& search_parameters)
const {
6072 return !search_parameters.use_full_propagation() &&
6073 !search_parameters.use_depth_first_search() &&
6074 search_parameters.first_solution_strategy() !=
6075 FirstSolutionStrategy::FIRST_UNBOUND_MIN_VALUE;
6081 CHECK(
var !=
nullptr);
6084 weighted_finalizer_variable_targets_.size());
6085 if (
index < weighted_finalizer_variable_targets_.size()) {
6086 auto& [var_target, total_cost] =
6087 weighted_finalizer_variable_targets_[
index];
6088 DCHECK_EQ(var_target.var,
var);
6089 DCHECK_EQ(var_target.target, target);
6092 DCHECK_EQ(
index, weighted_finalizer_variable_targets_.size());
6093 weighted_finalizer_variable_targets_.emplace_back(VarTarget(
var, target),
6111 CHECK(
var !=
nullptr);
6112 if (finalizer_variable_target_set_.contains(
var))
return;
6113 finalizer_variable_target_set_.insert(
var);
6114 finalizer_variable_targets_.emplace_back(
var, target);
6125 void RoutingModel::SetupSearch(
6126 const RoutingSearchParameters& search_parameters) {
6127 SetupDecisionBuilders(search_parameters);
6128 SetupSearchMonitors(search_parameters);
6132 extra_vars_.push_back(
var);
6136 extra_intervals_.push_back(
interval);
6141 class PathSpansAndTotalSlacks :
public Constraint {
6145 std::vector<IntVar*> spans,
6146 std::vector<IntVar*> total_slacks)
6149 dimension_(dimension),
6150 spans_(std::move(spans)),
6151 total_slacks_(std::move(total_slacks)) {
6152 CHECK_EQ(spans_.size(), model_->vehicles());
6153 CHECK_EQ(total_slacks_.size(), model_->vehicles());
6154 vehicle_demons_.resize(model_->vehicles());
6157 std::string DebugString()
const override {
return "PathSpansAndTotalSlacks"; }
6159 void Post()
override {
6160 const int num_nodes = model_->VehicleVars().size();
6161 const int num_transits = model_->Nexts().size();
6162 for (
int node = 0; node < num_nodes; ++node) {
6164 model_->solver(),
this, &PathSpansAndTotalSlacks::PropagateNode,
6165 "PathSpansAndTotalSlacks::PropagateNode", node);
6166 dimension_->CumulVar(node)->WhenRange(demon);
6167 model_->VehicleVar(node)->WhenBound(demon);
6168 if (node < num_transits) {
6169 dimension_->TransitVar(node)->WhenRange(demon);
6170 dimension_->FixedTransitVar(node)->WhenBound(demon);
6171 model_->NextVar(node)->WhenBound(demon);
6174 for (
int vehicle = 0; vehicle < spans_.size(); ++vehicle) {
6175 if (!spans_[vehicle] && !total_slacks_[vehicle])
continue;
6177 solver(),
this, &PathSpansAndTotalSlacks::PropagateVehicle,
6178 "PathSpansAndTotalSlacks::PropagateVehicle", vehicle);
6179 vehicle_demons_[vehicle] = demon;
6180 if (spans_[vehicle]) spans_[vehicle]->WhenRange(demon);
6181 if (total_slacks_[vehicle]) total_slacks_[vehicle]->WhenRange(demon);
6182 if (dimension_->HasBreakConstraints()) {
6183 for (IntervalVar*
b : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
6184 b->WhenAnything(demon);
6191 void InitialPropagate()
override {
6192 for (
int vehicle = 0; vehicle < spans_.size(); ++vehicle) {
6193 if (!spans_[vehicle] && !total_slacks_[vehicle])
continue;
6194 PropagateVehicle(vehicle);
6202 void PropagateNode(
int node) {
6203 if (!model_->VehicleVar(node)->Bound())
return;
6204 const int vehicle = model_->VehicleVar(node)->Min();
6205 if (vehicle < 0 || vehicle_demons_[vehicle] ==
nullptr)
return;
6206 EnqueueDelayedDemon(vehicle_demons_[vehicle]);
6214 int64_t SpanMin(
int vehicle, int64_t sum_fixed_transits) {
6215 DCHECK_GE(sum_fixed_transits, 0);
6216 const int64_t span_min = spans_[vehicle]
6217 ? spans_[vehicle]->Min()
6219 const int64_t total_slack_min = total_slacks_[vehicle]
6220 ? total_slacks_[vehicle]->Min()
6222 return std::min(span_min,
CapAdd(total_slack_min, sum_fixed_transits));
6224 int64_t SpanMax(
int vehicle, int64_t sum_fixed_transits) {
6225 DCHECK_GE(sum_fixed_transits, 0);
6226 const int64_t span_max = spans_[vehicle]
6227 ? spans_[vehicle]->Max()
6229 const int64_t total_slack_max = total_slacks_[vehicle]
6230 ? total_slacks_[vehicle]->Max()
6232 return std::max(span_max,
CapAdd(total_slack_max, sum_fixed_transits));
6234 void SetSpanMin(
int vehicle, int64_t
min, int64_t sum_fixed_transits) {
6235 DCHECK_GE(sum_fixed_transits, 0);
6236 if (spans_[vehicle]) {
6237 spans_[vehicle]->SetMin(
min);
6239 if (total_slacks_[vehicle]) {
6240 total_slacks_[vehicle]->SetMin(
CapSub(
min, sum_fixed_transits));
6243 void SetSpanMax(
int vehicle, int64_t
max, int64_t sum_fixed_transits) {
6244 DCHECK_GE(sum_fixed_transits, 0);
6245 if (spans_[vehicle]) {
6246 spans_[vehicle]->SetMax(
max);
6248 if (total_slacks_[vehicle]) {
6249 total_slacks_[vehicle]->SetMax(
CapSub(
max, sum_fixed_transits));
6254 void SynchronizeSpanAndTotalSlack(
int vehicle, int64_t sum_fixed_transits) {
6255 DCHECK_GE(sum_fixed_transits, 0);
6256 IntVar* span = spans_[vehicle];
6257 IntVar* total_slack = total_slacks_[vehicle];
6258 if (!span || !total_slack)
return;
6259 span->SetMin(
CapAdd(total_slack->Min(), sum_fixed_transits));
6260 span->SetMax(
CapAdd(total_slack->Max(), sum_fixed_transits));
6261 total_slack->SetMin(
CapSub(span->Min(), sum_fixed_transits));
6262 total_slack->SetMax(
CapSub(span->Max(), sum_fixed_transits));
6265 void PropagateVehicle(
int vehicle) {
6266 DCHECK(spans_[vehicle] || total_slacks_[vehicle]);
6267 const int start = model_->Start(vehicle);
6268 const int end = model_->End(vehicle);
6271 if (spans_[vehicle] !=
nullptr &&
6272 dimension_->AreVehicleTransitsPositive(vehicle)) {
6273 spans_[vehicle]->SetRange(
CapSub(dimension_->CumulVar(
end)->Min(),
6274 dimension_->CumulVar(
start)->Max()),
6275 CapSub(dimension_->CumulVar(
end)->Max(),
6276 dimension_->CumulVar(
start)->Min()));
6283 int curr_node =
start;
6284 while (!model_->IsEnd(curr_node)) {
6285 const IntVar* next_var = model_->NextVar(curr_node);
6286 if (!next_var->Bound())
return;
6287 path_.push_back(curr_node);
6288 curr_node = next_var->Value();
6293 int64_t sum_fixed_transits = 0;
6294 for (
const int node : path_) {
6295 const IntVar* fixed_transit_var = dimension_->FixedTransitVar(node);
6296 if (!fixed_transit_var->Bound())
return;
6297 sum_fixed_transits =
6298 CapAdd(sum_fixed_transits, fixed_transit_var->Value());
6301 SynchronizeSpanAndTotalSlack(vehicle, sum_fixed_transits);
6308 if (dimension_->HasBreakConstraints() &&
6309 !dimension_->GetBreakIntervalsOfVehicle(vehicle).empty()) {
6310 const int64_t vehicle_start_max = dimension_->CumulVar(
start)->Max();
6311 const int64_t vehicle_end_min = dimension_->CumulVar(
end)->Min();
6313 int64_t min_break_duration = 0;
6314 for (IntervalVar* br : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
6315 if (!br->MustBePerformed())
continue;
6316 if (vehicle_start_max < br->EndMin() &&
6317 br->StartMax() < vehicle_end_min) {
6318 min_break_duration =
CapAdd(min_break_duration, br->DurationMin());
6321 SetSpanMin(vehicle,
CapAdd(min_break_duration, sum_fixed_transits),
6322 sum_fixed_transits);
6328 const int64_t slack_max =
6329 CapSub(SpanMax(vehicle, sum_fixed_transits), sum_fixed_transits);
6330 const int64_t max_additional_slack =
6331 CapSub(slack_max, min_break_duration);
6332 for (IntervalVar* br : dimension_->GetBreakIntervalsOfVehicle(vehicle)) {
6333 if (!br->MustBePerformed())
continue;
6335 if (vehicle_start_max >= br->EndMin() &&
6336 br->StartMax() < vehicle_end_min) {
6337 if (br->DurationMin() > max_additional_slack) {
6340 br->SetEndMax(vehicle_start_max);
6341 dimension_->CumulVar(
start)->SetMin(br->EndMin());
6346 if (vehicle_start_max < br->EndMin() &&
6347 br->StartMax() >= vehicle_end_min) {
6348 if (br->DurationMin() > max_additional_slack) {
6349 br->SetStartMin(vehicle_end_min);
6350 dimension_->CumulVar(
end)->SetMax(br->StartMax());
6358 IntVar* start_cumul = dimension_->CumulVar(
start);
6359 IntVar* end_cumul = dimension_->CumulVar(
end);
6360 const int64_t
start_min = start_cumul->Min();
6361 const int64_t
start_max = start_cumul->Max();
6362 const int64_t
end_min = end_cumul->Min();
6363 const int64_t
end_max = end_cumul->Max();
6366 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
6368 SetSpanMax(vehicle, span_ub, sum_fixed_transits);
6370 const int64_t span_min = SpanMin(vehicle, sum_fixed_transits);
6371 const int64_t span_max = SpanMax(vehicle, sum_fixed_transits);
6372 const int64_t slack_from_lb =
CapSub(span_max, span_lb);
6373 const int64_t slack_from_ub =
CapSub(span_ub, span_min);
6387 int64_t span_lb = 0;
6388 int64_t span_ub = 0;
6389 for (
const int node : path_) {
6390 span_lb =
CapAdd(span_lb, dimension_->TransitVar(node)->Min());
6391 span_ub =
CapAdd(span_ub, dimension_->TransitVar(node)->Max());
6393 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
6394 SetSpanMax(vehicle, span_ub, sum_fixed_transits);
6398 const int64_t span_min = SpanMin(vehicle, sum_fixed_transits);
6399 const int64_t span_max = SpanMax(vehicle, sum_fixed_transits);
6400 const int64_t slack_from_lb =
CapSub(span_max, span_lb);
6401 const int64_t slack_from_ub =
6403 ?
CapSub(span_ub, span_min)
6404 : std::numeric_limits<int64_t>::
max();
6405 for (
const int node : path_) {
6406 IntVar* transit_var = dimension_->TransitVar(node);
6407 const int64_t transit_i_min = transit_var->Min();
6408 const int64_t transit_i_max = transit_var->Max();
6412 transit_var->SetMax(
CapAdd(transit_i_min, slack_from_lb));
6413 transit_var->SetMin(
CapSub(transit_i_max, slack_from_ub));
6418 path_.push_back(
end);
6429 int64_t arrival_time = dimension_->CumulVar(
start)->Min();
6430 for (
int i = 1; i < path_.size(); ++i) {
6433 dimension_->FixedTransitVar(path_[i - 1])->Min()),
6434 dimension_->CumulVar(path_[i])->Min());
6436 int64_t departure_time = arrival_time;
6437 for (
int i = path_.size() - 2; i >= 0; --i) {
6440 dimension_->FixedTransitVar(path_[i])->Min()),
6441 dimension_->CumulVar(path_[i])->Max());
6443 const int64_t span_lb =
CapSub(arrival_time, departure_time);
6444 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
6445 const int64_t maximum_deviation =
6446 CapSub(SpanMax(vehicle, sum_fixed_transits), span_lb);
6447 const int64_t start_lb =
CapSub(departure_time, maximum_deviation);
6448 dimension_->CumulVar(
start)->SetMin(start_lb);
6452 int64_t departure_time = dimension_->CumulVar(
end)->Max();
6453 for (
int i = path_.size() - 2; i >= 0; --i) {
6454 const int curr_node = path_[i];
6457 dimension_->FixedTransitVar(curr_node)->Min()),
6458 dimension_->CumulVar(curr_node)->Max());
6460 int arrival_time = departure_time;
6461 for (
int i = 1; i < path_.size(); ++i) {
6464 dimension_->FixedTransitVar(path_[i - 1])->Min()),
6465 dimension_->CumulVar(path_[i])->Min());
6467 const int64_t span_lb =
CapSub(arrival_time, departure_time);
6468 SetSpanMin(vehicle, span_lb, sum_fixed_transits);
6469 const int64_t maximum_deviation =
6470 CapSub(SpanMax(vehicle, sum_fixed_transits), span_lb);
6471 dimension_->CumulVar(
end)->SetMax(
6472 CapAdd(arrival_time, maximum_deviation));
6478 std::vector<IntVar*> spans_;
6479 std::vector<IntVar*> total_slacks_;
6480 std::vector<int> path_;
6481 std::vector<Demon*> vehicle_demons_;
6488 std::vector<IntVar*> total_slacks) {
6489 CHECK_EQ(vehicles_, spans.size());
6490 CHECK_EQ(vehicles_, total_slacks.size());
6492 new PathSpansAndTotalSlacks(
this, dimension, spans, total_slacks));
6500 std::vector<int64_t> vehicle_capacities,
6501 const std::string&
name,
6503 : vehicle_capacities_(std::move(vehicle_capacities)),
6504 base_dimension_(base_dimension),
6505 global_span_cost_coefficient_(0),
6508 global_optimizer_offset_(0) {
6509 CHECK(
model !=
nullptr);
6510 vehicle_span_upper_bounds_.assign(
model->vehicles(),
6512 vehicle_span_cost_coefficients_.assign(
model->vehicles(), 0);
6516 std::vector<int64_t> vehicle_capacities,
6517 const std::string&
name, SelfBased)
6521 cumul_var_piecewise_linear_cost_.clear();
6524 void RoutingDimension::Initialize(
6525 const std::vector<int>& transit_evaluators,
6526 const std::vector<int>& state_dependent_transit_evaluators,
6527 int64_t slack_max) {
6529 InitializeTransits(transit_evaluators, state_dependent_transit_evaluators,
6543 class LightRangeLessOrEqual :
public Constraint {
6545 LightRangeLessOrEqual(Solver*
const s, IntExpr*
const l, IntExpr*
const r);
6546 ~LightRangeLessOrEqual()
override {}
6547 void Post()
override;
6548 void InitialPropagate()
override;
6549 std::string DebugString()
const override;
6550 IntVar* Var()
override {
6551 return solver()->MakeIsLessOrEqualVar(left_, right_);
6554 void Accept(ModelVisitor*
const visitor)
const override {
6565 IntExpr*
const left_;
6566 IntExpr*
const right_;
6570 LightRangeLessOrEqual::LightRangeLessOrEqual(Solver*
const s, IntExpr*
const l,
6572 : Constraint(s), left_(l), right_(r), demon_(nullptr) {}
6574 void LightRangeLessOrEqual::Post() {
6576 solver(),
this, &LightRangeLessOrEqual::CheckRange,
"CheckRange");
6577 left_->WhenRange(demon_);
6578 right_->WhenRange(demon_);
6581 void LightRangeLessOrEqual::InitialPropagate() {
6582 left_->SetMax(right_->Max());
6583 right_->SetMin(left_->Min());
6584 if (left_->Max() <= right_->Min()) {
6589 void LightRangeLessOrEqual::CheckRange() {
6590 if (left_->Min() > right_->Max()) {
6593 if (left_->Max() <= right_->Min()) {
6598 std::string LightRangeLessOrEqual::DebugString()
const {
6599 return left_->DebugString() +
" < " + right_->DebugString();
6604 void RoutingDimension::InitializeCumuls() {
6605 Solver*
const solver = model_->
solver();
6607 const auto capacity_range = std::minmax_element(vehicle_capacities_.begin(),
6608 vehicle_capacities_.end());
6609 const int64_t min_capacity = *capacity_range.first;
6610 CHECK_GE(min_capacity, 0);
6611 const int64_t max_capacity = *capacity_range.second;
6612 solver->MakeIntVarArray(size, 0, max_capacity, name_, &cumuls_);
6614 for (
int v = 0; v < model_->
vehicles(); v++) {
6615 const int64_t vehicle_capacity = vehicle_capacities_[v];
6616 cumuls_[model_->
Start(v)]->SetMax(vehicle_capacity);
6617 cumuls_[model_->
End(v)]->SetMax(vehicle_capacity);
6620 forbidden_intervals_.resize(size);
6621 capacity_vars_.clear();
6622 if (min_capacity != max_capacity) {
6625 for (
int i = 0; i < size; ++i) {
6626 IntVar*
const capacity_var = capacity_vars_[i];
6627 if (i < model_->Size()) {
6628 IntVar*
const capacity_active = solver->MakeBoolVar();
6629 solver->AddConstraint(
6630 solver->MakeLessOrEqual(model_->
ActiveVar(i), capacity_active));
6631 solver->AddConstraint(solver->MakeIsLessOrEqualCt(
6632 cumuls_[i], capacity_var, capacity_active));
6634 solver->AddConstraint(
6635 solver->MakeLessOrEqual(cumuls_[i], capacity_var));
6642 void ComputeTransitClasses(
const std::vector<int>& evaluator_indices,
6643 std::vector<int>* class_evaluators,
6644 std::vector<int64_t>* vehicle_to_class) {
6645 CHECK(class_evaluators !=
nullptr);
6646 CHECK(vehicle_to_class !=
nullptr);
6647 class_evaluators->clear();
6648 vehicle_to_class->resize(evaluator_indices.size(), -1);
6649 absl::flat_hash_map<int, int64_t> evaluator_to_class;
6650 for (
int i = 0; i < evaluator_indices.size(); ++i) {
6651 const int evaluator_index = evaluator_indices[i];
6652 int evaluator_class = -1;
6653 if (!
gtl::FindCopy(evaluator_to_class, evaluator_index, &evaluator_class)) {
6654 evaluator_class = class_evaluators->size();
6655 evaluator_to_class[evaluator_index] = evaluator_class;
6656 class_evaluators->push_back(evaluator_index);
6658 (*vehicle_to_class)[i] = evaluator_class;
6663 void RoutingDimension::InitializeTransitVariables(int64_t slack_max) {
6664 CHECK(!class_evaluators_.empty());
6665 CHECK(base_dimension_ ==
nullptr ||
6666 !state_dependent_class_evaluators_.empty());
6668 Solver*
const solver = model_->
solver();
6669 const int size = model_->
Size();
6672 return (0 <=
index &&
index < state_dependent_vehicle_to_class_.size())
6673 ? state_dependent_vehicle_to_class_[
index]
6674 : state_dependent_class_evaluators_.size();
6676 const std::string slack_name = name_ +
" slack";
6677 const std::string transit_name = name_ +
" fixed transit";
6679 bool are_all_evaluators_positive =
true;
6680 for (
int class_evaluator : class_evaluators_) {
6681 if (!
model()->is_transit_evaluator_positive_[class_evaluator]) {
6682 are_all_evaluators_positive =
false;
6686 for (int64_t i = 0; i < size; ++i) {
6687 fixed_transits_[i] = solver->MakeIntVar(
6688 are_all_evaluators_positive ? int64_t{0}
6692 if (base_dimension_ !=
nullptr) {
6693 if (state_dependent_class_evaluators_.size() == 1) {
6694 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6695 for (int64_t j = 0; j < cumuls_.size(); ++j) {
6696 transition_variables[j] =
6697 MakeRangeMakeElementExpr(
6699 ->StateDependentTransitCallback(
6700 state_dependent_class_evaluators_[0])(i, j)
6702 base_dimension_->
CumulVar(i), solver)
6705 dependent_transits_[i] =
6706 solver->MakeElement(transition_variables, model_->
NextVar(i))
6709 IntVar*
const vehicle_class_var =
6711 ->MakeElement(dependent_vehicle_class_function,
6714 std::vector<IntVar*> transit_for_vehicle;
6715 transit_for_vehicle.reserve(state_dependent_class_evaluators_.size() +
6717 for (
int evaluator : state_dependent_class_evaluators_) {
6718 std::vector<IntVar*> transition_variables(cumuls_.size(),
nullptr);
6719 for (int64_t j = 0; j < cumuls_.size(); ++j) {
6720 transition_variables[j] =
6721 MakeRangeMakeElementExpr(
6724 base_dimension_->
CumulVar(i), solver)
6727 transit_for_vehicle.push_back(
6728 solver->MakeElement(transition_variables, model_->
NextVar(i))
6731 transit_for_vehicle.push_back(solver->MakeIntConst(0));
6732 dependent_transits_[i] =
6733 solver->MakeElement(transit_for_vehicle, vehicle_class_var)->Var();
6736 dependent_transits_[i] = solver->MakeIntConst(0);
6740 IntExpr* transit_expr = fixed_transits_[i];
6741 if (dependent_transits_[i]->Min() != 0 ||
6742 dependent_transits_[i]->Max() != 0) {
6743 transit_expr = solver->MakeSum(transit_expr, dependent_transits_[i]);
6746 if (slack_max == 0) {
6747 slacks_[i] = solver->MakeIntConst(0);
6750 solver->MakeIntVar(0, slack_max, absl::StrCat(slack_name, i));
6751 transit_expr = solver->MakeSum(slacks_[i], transit_expr);
6753 transits_[i] = transit_expr->Var();
6757 void RoutingDimension::InitializeTransits(
6758 const std::vector<int>& transit_evaluators,
6759 const std::vector<int>& state_dependent_transit_evaluators,
6760 int64_t slack_max) {
6761 CHECK_EQ(model_->
vehicles(), transit_evaluators.size());
6762 CHECK(base_dimension_ ==
nullptr ||
6763 model_->
vehicles() == state_dependent_transit_evaluators.size());
6764 const int size = model_->
Size();
6765 transits_.resize(size,
nullptr);
6766 fixed_transits_.resize(size,
nullptr);
6767 slacks_.resize(size,
nullptr);
6768 dependent_transits_.resize(size,
nullptr);
6769 ComputeTransitClasses(transit_evaluators, &class_evaluators_,
6770 &vehicle_to_class_);
6771 if (base_dimension_ !=
nullptr) {
6772 ComputeTransitClasses(state_dependent_transit_evaluators,
6773 &state_dependent_class_evaluators_,
6774 &state_dependent_vehicle_to_class_);
6777 InitializeTransitVariables(slack_max);
6783 std::vector<int64_t>* values) {
6784 const int num_nodes = path.size();
6785 values->resize(num_nodes - 1);
6786 for (
int i = 0; i < num_nodes - 1; ++i) {
6787 (*values)[i] = evaluator(path[i], path[i + 1]);
6792 : model_(
model), occurrences_of_type_(
model.GetNumberOfVisitTypes()) {}
6795 int vehicle,
const std::function<int64_t(int64_t)>& next_accessor) {
6802 for (
int pos = 0; pos < current_route_visits_.size(); pos++) {
6803 const int64_t current_visit = current_route_visits_[pos];
6810 DCHECK_LT(type, occurrences_of_type_.size());
6811 int& num_type_added = occurrences_of_type_[type].num_type_added_to_vehicle;
6812 int& num_type_removed =
6813 occurrences_of_type_[type].num_type_removed_from_vehicle;
6814 DCHECK_LE(num_type_removed, num_type_added);
6816 num_type_removed == num_type_added) {
6826 if (policy == VisitTypePolicy::TYPE_ADDED_TO_VEHICLE ||
6827 policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED) {
6830 if (policy == VisitTypePolicy::TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED ||
6831 policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
6839 int vehicle,
const std::function<int64_t(int64_t)>& next_accessor) {
6842 std::fill(occurrences_of_type_.begin(), occurrences_of_type_.end(),
6843 TypeRegulationsChecker::TypePolicyOccurrence());
6848 current_route_visits_.clear();
6850 current = next_accessor(current)) {
6853 VisitTypePolicy::TYPE_ON_VEHICLE_UP_TO_VISIT) {
6854 occurrences_of_type_[type].position_of_last_type_on_vehicle_up_to_visit =
6855 current_route_visits_.size();
6857 current_route_visits_.push_back(current);
6879 check_hard_incompatibilities_(check_hard_incompatibilities) {}
6881 bool TypeIncompatibilityChecker::HasRegulationsToCheck()
const {
6883 (check_hard_incompatibilities_ &&
6892 bool TypeIncompatibilityChecker::CheckTypeRegulations(
int type,
6893 VisitTypePolicy policy,
6895 if (policy == VisitTypePolicy::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
6900 for (
int incompatible_type :
6906 if (check_hard_incompatibilities_) {
6907 for (
int incompatible_type :
6917 bool TypeRequirementChecker::HasRegulationsToCheck()
const {
6922 bool TypeRequirementChecker::CheckRequiredTypesCurrentlyOnRoute(
6923 const std::vector<absl::flat_hash_set<int>>& required_type_alternatives,
6925 for (
const absl::flat_hash_set<int>& requirement_alternatives :
6926 required_type_alternatives) {
6927 bool has_one_of_alternatives =
false;
6928 for (
int type_alternative : requirement_alternatives) {
6930 has_one_of_alternatives =
true;
6934 if (!has_one_of_alternatives) {
6941 bool TypeRequirementChecker::CheckTypeRegulations(
int type,
6942 VisitTypePolicy policy,
6946 if (!CheckRequiredTypesCurrentlyOnRoute(
6952 if (!CheckRequiredTypesCurrentlyOnRoute(
6959 types_with_same_vehicle_requirements_on_route_.insert(type);
6964 bool TypeRequirementChecker::FinalizeCheck()
const {
6965 for (
int type : types_with_same_vehicle_requirements_on_route_) {
6966 for (
const absl::flat_hash_set<int>& requirement_alternatives :
6968 bool has_one_of_alternatives =
false;
6969 for (
const int type_alternative : requirement_alternatives) {
6971 has_one_of_alternatives =
true;
6975 if (!has_one_of_alternatives) {
6984 : Constraint(
model.solver()),
6986 incompatibility_checker_(
model, true),
6987 requirement_checker_(
model),
6988 vehicle_demons_(
model.vehicles()) {}
6990 void TypeRegulationsConstraint::PropagateNodeRegulations(
int node) {
6991 DCHECK_LT(node, model_.
Size());
6997 if (vehicle < 0)
return;
6998 DCHECK(vehicle_demons_[vehicle] !=
nullptr);
7002 void TypeRegulationsConstraint::CheckRegulationsOnVehicle(
int vehicle) {
7003 const auto next_accessor = [
this, vehicle](int64_t node) {
7008 return model_.
End(vehicle);
7010 if (!incompatibility_checker_.
CheckVehicle(vehicle, next_accessor) ||
7011 !requirement_checker_.
CheckVehicle(vehicle, next_accessor)) {
7017 for (
int vehicle = 0; vehicle < model_.
vehicles(); vehicle++) {
7019 solver(),
this, &TypeRegulationsConstraint::CheckRegulationsOnVehicle,
7020 "CheckRegulationsOnVehicle", vehicle);
7022 for (
int node = 0; node < model_.
Size(); node++) {
7024 solver(),
this, &TypeRegulationsConstraint::PropagateNodeRegulations,
7025 "PropagateNodeRegulations", node);
7032 for (
int vehicle = 0; vehicle < model_.
vehicles(); vehicle++) {
7033 CheckRegulationsOnVehicle(vehicle);
7037 void RoutingDimension::CloseModel(
bool use_light_propagation) {
7038 Solver*
const solver = model_->
solver();
7039 const auto capacity_lambda = [
this](int64_t vehicle) {
7040 return vehicle >= 0 ? vehicle_capacities_[vehicle]
7043 for (
int i = 0; i < capacity_vars_.size(); ++i) {
7044 IntVar*
const vehicle_var = model_->
VehicleVar(i);
7045 IntVar*
const capacity_var = capacity_vars_[i];
7046 if (use_light_propagation) {
7047 solver->AddConstraint(solver->MakeLightElement(
7048 capacity_lambda, capacity_var, vehicle_var,
7049 [
this]() { return model_->enable_deep_serialization_; }));
7051 solver->AddConstraint(solver->MakeEquality(
7053 solver->MakeElement(capacity_lambda, vehicle_var)->Var()));
7056 for (
int i = 0; i < fixed_transits_.size(); ++i) {
7057 IntVar*
const next_var = model_->
NextVar(i);
7058 IntVar*
const fixed_transit = fixed_transits_[i];
7059 const auto transit_vehicle_evaluator = [
this, i](int64_t to,
7060 int64_t eval_index) {
7063 if (use_light_propagation) {
7064 if (class_evaluators_.size() == 1) {
7065 const int class_evaluator_index = class_evaluators_[0];
7066 const auto& unary_callback =
7068 if (unary_callback ==
nullptr) {
7069 solver->AddConstraint(solver->MakeLightElement(
7070 [
this, i](int64_t to) {
7071 return model_->TransitCallback(class_evaluators_[0])(i, to);
7073 fixed_transit, next_var,
7074 [
this]() { return model_->enable_deep_serialization_; }));
7076 fixed_transit->SetValue(unary_callback(i));
7079 solver->AddConstraint(solver->MakeLightElement(
7080 transit_vehicle_evaluator, fixed_transit, next_var,
7082 [
this]() { return model_->enable_deep_serialization_; }));
7085 if (class_evaluators_.size() == 1) {
7086 const int class_evaluator_index = class_evaluators_[0];
7087 const auto& unary_callback =
7089 if (unary_callback ==
nullptr) {
7090 solver->AddConstraint(solver->MakeEquality(
7091 fixed_transit, solver
7093 [
this, i](int64_t to) {
7094 return model_->TransitCallback(
7095 class_evaluators_[0])(i, to);
7100 fixed_transit->SetValue(unary_callback(i));
7103 solver->AddConstraint(solver->MakeEquality(
7104 fixed_transit, solver
7105 ->MakeElement(transit_vehicle_evaluator,
7114 solver->AddConstraint(constraint);
7119 int64_t vehicle)
const {
7125 int64_t
index, int64_t min_value, int64_t max_value)
const {
7131 int64_t next_start =
min;
7135 if (next_start >
max)
break;
7136 if (next_start < interval->
start) {
7141 if (next_start <=
max) {
7149 CHECK_GE(vehicle, 0);
7150 CHECK_LT(vehicle, vehicle_span_upper_bounds_.size());
7152 vehicle_span_upper_bounds_[vehicle] =
upper_bound;
7157 CHECK_GE(vehicle, 0);
7158 CHECK_LT(vehicle, vehicle_span_cost_coefficients_.size());
7160 vehicle_span_cost_coefficients_[vehicle] =
coefficient;
7175 int64_t
index,
const PiecewiseLinearFunction&
cost) {
7176 if (!
cost.IsNonDecreasing()) {
7177 LOG(WARNING) <<
"Only non-decreasing cost functions are supported.";
7180 if (
cost.Value(0) < 0) {
7181 LOG(WARNING) <<
"Only positive cost functions are supported.";
7184 if (
index >= cumul_var_piecewise_linear_cost_.size()) {
7185 cumul_var_piecewise_linear_cost_.resize(
index + 1);
7187 PiecewiseLinearCost& piecewise_linear_cost =
7188 cumul_var_piecewise_linear_cost_[
index];
7189 piecewise_linear_cost.var = cumuls_[
index];
7190 piecewise_linear_cost.cost = std::make_unique<PiecewiseLinearFunction>(
cost);
7194 return (
index < cumul_var_piecewise_linear_cost_.size() &&
7195 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr);
7199 int64_t
index)
const {
7200 if (
index < cumul_var_piecewise_linear_cost_.size() &&
7201 cumul_var_piecewise_linear_cost_[
index].var !=
nullptr) {
7202 return cumul_var_piecewise_linear_cost_[
index].cost.get();
7208 IntVar* BuildVarFromExprAndIndexActiveState(
const RoutingModel*
model,
7209 IntExpr* expr,
int index) {
7210 Solver*
const solver =
model->solver();
7212 const int vehicle =
model->VehicleIndex(
index);
7213 DCHECK_GE(vehicle, 0);
7214 return solver->MakeProd(expr,
model->VehicleRouteConsideredVar(vehicle))
7217 return solver->MakeProd(expr,
model->ActiveVar(
index))->Var();
7221 void RoutingDimension::SetupCumulVarPiecewiseLinearCosts(
7222 std::vector<IntVar*>* cost_elements)
const {
7223 CHECK(cost_elements !=
nullptr);
7224 Solver*
const solver = model_->
solver();
7225 for (
int i = 0; i < cumul_var_piecewise_linear_cost_.size(); ++i) {
7226 const PiecewiseLinearCost& piecewise_linear_cost =
7227 cumul_var_piecewise_linear_cost_[i];
7228 if (piecewise_linear_cost.var !=
nullptr) {
7229 IntExpr*
const expr = solver->MakePiecewiseLinearExpr(
7230 piecewise_linear_cost.var, *piecewise_linear_cost.cost);
7231 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7232 cost_elements->push_back(cost_var);
7243 if (
index >= cumul_var_soft_upper_bound_.size()) {
7244 cumul_var_soft_upper_bound_.resize(
index + 1, {
nullptr, 0, 0});
7251 return (
index < cumul_var_soft_upper_bound_.size() &&
7252 cumul_var_soft_upper_bound_[
index].var !=
nullptr);
7256 if (
index < cumul_var_soft_upper_bound_.size() &&
7257 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
7258 return cumul_var_soft_upper_bound_[
index].bound;
7260 return cumuls_[
index]->Max();
7264 int64_t
index)
const {
7265 if (
index < cumul_var_soft_upper_bound_.size() &&
7266 cumul_var_soft_upper_bound_[
index].var !=
nullptr) {
7267 return cumul_var_soft_upper_bound_[
index].coefficient;
7272 void RoutingDimension::SetupCumulVarSoftUpperBoundCosts(
7273 std::vector<IntVar*>* cost_elements)
const {
7274 CHECK(cost_elements !=
nullptr);
7275 Solver*
const solver = model_->
solver();
7276 for (
int i = 0; i < cumul_var_soft_upper_bound_.size(); ++i) {
7277 const SoftBound& soft_bound = cumul_var_soft_upper_bound_[i];
7278 if (soft_bound.var !=
nullptr) {
7279 IntExpr*
const expr = solver->MakeSemiContinuousExpr(
7280 solver->MakeSum(soft_bound.var, -soft_bound.bound), 0,
7281 soft_bound.coefficient);
7282 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7283 cost_elements->push_back(cost_var);
7287 soft_bound.coefficient);
7295 if (
index >= cumul_var_soft_lower_bound_.size()) {
7296 cumul_var_soft_lower_bound_.resize(
index + 1, {
nullptr, 0, 0});
7303 return (
index < cumul_var_soft_lower_bound_.size() &&
7304 cumul_var_soft_lower_bound_[
index].var !=
nullptr);
7308 if (
index < cumul_var_soft_lower_bound_.size() &&
7309 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
7310 return cumul_var_soft_lower_bound_[
index].bound;
7312 return cumuls_[
index]->Min();
7316 int64_t
index)
const {
7317 if (
index < cumul_var_soft_lower_bound_.size() &&
7318 cumul_var_soft_lower_bound_[
index].var !=
nullptr) {
7319 return cumul_var_soft_lower_bound_[
index].coefficient;
7324 void RoutingDimension::SetupCumulVarSoftLowerBoundCosts(
7325 std::vector<IntVar*>* cost_elements)
const {
7326 CHECK(cost_elements !=
nullptr);
7327 Solver*
const solver = model_->
solver();
7328 for (
int i = 0; i < cumul_var_soft_lower_bound_.size(); ++i) {
7329 const SoftBound& soft_bound = cumul_var_soft_lower_bound_[i];
7330 if (soft_bound.var !=
nullptr) {
7331 IntExpr*
const expr = solver->MakeSemiContinuousExpr(
7332 solver->MakeDifference(soft_bound.bound, soft_bound.var), 0,
7333 soft_bound.coefficient);
7334 IntVar* cost_var = BuildVarFromExprAndIndexActiveState(model_, expr, i);
7335 cost_elements->push_back(cost_var);
7339 soft_bound.coefficient);
7344 void RoutingDimension::SetupGlobalSpanCost(
7345 std::vector<IntVar*>* cost_elements)
const {
7346 CHECK(cost_elements !=
nullptr);
7347 Solver*
const solver = model_->
solver();
7348 if (global_span_cost_coefficient_ != 0) {
7349 std::vector<IntVar*> end_cumuls;
7350 for (
int i = 0; i < model_->
vehicles(); ++i) {
7351 end_cumuls.push_back(solver
7352 ->MakeProd(model_->vehicle_route_considered_[i],
7353 cumuls_[model_->
End(i)])
7356 IntVar*
const max_end_cumul = solver->
MakeMax(end_cumuls)->
Var();
7358 max_end_cumul, global_span_cost_coefficient_);
7359 std::vector<IntVar*> start_cumuls;
7360 for (
int i = 0; i < model_->
vehicles(); ++i) {
7361 IntVar* global_span_cost_start_cumul =
7363 solver->AddConstraint(solver->MakeIfThenElseCt(
7364 model_->vehicle_route_considered_[i], cumuls_[model_->
Start(i)],
7365 max_end_cumul, global_span_cost_start_cumul));
7366 start_cumuls.push_back(global_span_cost_start_cumul);
7368 IntVar*
const min_start_cumul = solver->MakeMin(start_cumuls)->Var();
7370 min_start_cumul, global_span_cost_coefficient_);
7375 for (
int var_index = 0; var_index < model_->
Size(); ++var_index) {
7377 slacks_[var_index], global_span_cost_coefficient_);
7378 cost_elements->push_back(
7381 model_->vehicle_route_considered_[0],
7384 solver->MakeSum(transits_[var_index],
7385 dependent_transits_[var_index]),
7386 global_span_cost_coefficient_),
7391 IntVar*
const end_range =
7392 solver->MakeDifference(max_end_cumul, min_start_cumul)->Var();
7393 end_range->SetMin(0);
7394 cost_elements->push_back(
7395 solver->MakeProd(end_range, global_span_cost_coefficient_)->Var());
7401 std::vector<IntervalVar*> breaks,
int vehicle,
7402 std::vector<int64_t> node_visit_transits) {
7403 if (breaks.empty())
return;
7405 [node_visit_transits](int64_t from, int64_t ) {
7406 return node_visit_transits[from];
7412 std::vector<IntervalVar*> breaks,
int vehicle,
7413 std::vector<int64_t> node_visit_transits,
7414 std::function<int64_t(int64_t, int64_t)> delays) {
7415 if (breaks.empty())
return;
7417 [node_visit_transits](int64_t from, int64_t ) {
7418 return node_visit_transits[from];
7420 const int delay_evaluator =
7427 std::vector<IntervalVar*> breaks,
int vehicle,
int pre_travel_evaluator,
7428 int post_travel_evaluator) {
7429 DCHECK_LE(0, vehicle);
7430 DCHECK_LT(vehicle, model_->
vehicles());
7431 if (breaks.empty())
return;
7433 vehicle_break_intervals_[vehicle] = std::move(breaks);
7434 vehicle_pre_travel_evaluators_[vehicle] = pre_travel_evaluator;
7435 vehicle_post_travel_evaluators_[vehicle] = post_travel_evaluator;
7437 for (IntervalVar*
const interval : vehicle_break_intervals_[vehicle]) {
7456 DCHECK(!break_constraints_are_initialized_);
7457 const int num_vehicles = model_->
vehicles();
7458 vehicle_break_intervals_.resize(num_vehicles);
7459 vehicle_pre_travel_evaluators_.resize(num_vehicles, -1);
7460 vehicle_post_travel_evaluators_.resize(num_vehicles, -1);
7461 vehicle_break_distance_duration_.resize(num_vehicles);
7462 break_constraints_are_initialized_ =
true;
7466 return break_constraints_are_initialized_;
7470 int vehicle)
const {
7471 DCHECK_LE(0, vehicle);
7472 DCHECK_LT(vehicle, vehicle_break_intervals_.size());
7473 return vehicle_break_intervals_[vehicle];
7477 DCHECK_LE(0, vehicle);
7478 DCHECK_LT(vehicle, vehicle_pre_travel_evaluators_.size());
7479 return vehicle_pre_travel_evaluators_[vehicle];
7483 DCHECK_LE(0, vehicle);
7484 DCHECK_LT(vehicle, vehicle_post_travel_evaluators_.size());
7485 return vehicle_post_travel_evaluators_[vehicle];
7491 DCHECK_LE(0, vehicle);
7492 DCHECK_LT(vehicle, model_->
vehicles());
7494 vehicle_break_distance_duration_[vehicle].emplace_back(
distance, duration);
7503 const std::vector<std::pair<int64_t, int64_t>>&
7505 DCHECK_LE(0, vehicle);
7506 DCHECK_LT(vehicle, vehicle_break_distance_duration_.size());
7507 return vehicle_break_distance_duration_[vehicle];
7511 PickupToDeliveryLimitFunction limit_function,
int pair_index) {
7512 CHECK_GE(pair_index, 0);
7513 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
7514 pickup_to_delivery_limits_per_pair_index_.resize(pair_index + 1);
7516 pickup_to_delivery_limits_per_pair_index_[pair_index] =
7517 std::move(limit_function);
7521 return !pickup_to_delivery_limits_per_pair_index_.empty();
7526 int delivery)
const {
7527 DCHECK_GE(pair_index, 0);
7529 if (pair_index >= pickup_to_delivery_limits_per_pair_index_.size()) {
7533 pickup_to_delivery_limits_per_pair_index_[pair_index];
7534 if (!pickup_to_delivery_limit_function) {
7538 DCHECK_GE(pickup, 0);
7539 DCHECK_GE(delivery, 0);
7540 return pickup_to_delivery_limit_function(pickup, delivery);
7543 void RoutingDimension::SetupSlackAndDependentTransitCosts()
const {
7544 if (model_->
vehicles() == 0)
return;
7546 bool all_vehicle_span_costs_are_equal =
true;
7547 for (
int i = 1; i < model_->
vehicles(); ++i) {
7548 all_vehicle_span_costs_are_equal &= vehicle_span_cost_coefficients_[i] ==
7549 vehicle_span_cost_coefficients_[0];
7552 if (all_vehicle_span_costs_are_equal &&
7553 vehicle_span_cost_coefficients_[0] == 0) {
7565 std::vector<const RoutingDimension*> dimensions_with_relevant_slacks = {
this};
7567 const RoutingDimension*
next =
7568 dimensions_with_relevant_slacks.back()->base_dimension_;
7569 if (
next ==
nullptr ||
next == dimensions_with_relevant_slacks.back()) {
7572 dimensions_with_relevant_slacks.push_back(
next);
7575 for (
auto it = dimensions_with_relevant_slacks.rbegin();
7576 it != dimensions_with_relevant_slacks.rend(); ++it) {
7577 for (
int i = 0; i < model_->
vehicles(); ++i) {
7583 for (IntVar*
const slack : (*it)->slacks_) {
std::vector< int > dimensions
An Assignment is a variable -> domains mapping, used to report solutions to the user.
bool Contains(const IntVar *const var) const
int64_t Max(const IntVar *const var) const
int64_t Value(const IntVar *const var) const
bool Bound(const IntVar *const var) const
int64_t Min(const IntVar *const var) const
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.
void inhibit(Solver *const s)
This method inhibits the demon in the search tree below the current position.
We call domain any subset of Int64 = [kint64min, kint64max].
ArcIndexType AddArc(NodeIndexType tail, NodeIndexType head)
GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimensio...
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_t Min() const =0
virtual int64_t Max() const =0
Decision builder building a solution using heuristics with local search filters to evaluate its feasi...
int64_t number_of_decisions() const
Returns statistics from its underlying heuristic.
int64_t number_of_rejects() const
The class IntVar is a subset of IntExpr.
virtual bool Contains(int64_t v) const =0
This method returns whether the value 'v' is in the domain of the variable.
virtual void WhenBound(Demon *d)=0
This method attaches a demon that will be awakened when the variable is bound.
virtual int64_t Value() const =0
This method returns the value of the variable.
virtual uint64_t Size() const =0
This method returns the number of values in the domain of the variable.
CostValue GetCost() const
void SetArcCost(ArcIndex arc, CostValue cost)
The base class for all local search operators.
static int64_t FastInt64Round(double x)
static const char kLessOrEqual[]
static const char kLeftArgument[]
static const char kVarsArgument[]
static const char kRightArgument[]
static const char kValuesArgument[]
void EnqueueDelayedDemon(Demon *const d)
This method pushes the demon onto the propagation queue.
Reversible array of POD types.
This class adds reversibility to a POD type.
Dimensions represent quantities accumulated at nodes along the routes.
void SetSpanCostCoefficientForAllVehicles(int64_t coefficient)
void SetCumulVarPiecewiseLinearCost(int64_t 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...
bool HasCumulVarPiecewiseLinearCost(int64_t index) const
Returns true if a piecewise linear cost has been set for a given variable index.
int64_t GetCumulVarSoftUpperBoundCoefficient(int64_t index) const
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
RoutingModel * model() const
Returns the model on which the dimension was created.
bool HasPickupToDeliveryLimits() const
int64_t GetPickupToDeliveryLimitForPair(int pair_index, int pickup, int delivery) const
bool HasCumulVarSoftLowerBound(int64_t index) const
Returns true if a soft lower bound has been set for a given variable index.
void SetBreakDistanceDurationOfVehicle(int64_t distance, int64_t 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.
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64_t index, int64_t min_value, int64_t max_value) const
Returns allowed intervals for a given node in a given interval.
void InitializeBreaks()
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_tr...
std::function< int64_t(int, int)> PickupToDeliveryLimitFunction
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery a...
const std::vector< int64_t > & vehicle_span_cost_coefficients() const
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
bool HasCumulVarSoftUpperBound(int64_t index) const
Returns true if a soft upper bound has been set for a given variable index.
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
void SetPickupToDeliveryLimitFunctionForPair(PickupToDeliveryLimitFunction limit_function, int pair_index)
int vehicle_to_class(int vehicle) const
const PiecewiseLinearFunction * GetCumulVarPiecewiseLinearCost(int64_t index) const
Returns the piecewise linear cost of a cumul variable for a given variable index.
int64_t GetTransitValue(int64_t from_index, int64_t to_index, int64_t vehicle) const
Returns the transition value for a given pair of nodes (as var index); this value is the one taken by...
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
const std::vector< int64_t > & vehicle_capacities() const
Returns the capacities for all vehicles.
void SetCumulVarSoftUpperBound(int64_t index, int64_t upper_bound, int64_t coefficient)
Sets a soft upper bound to the cumul variable of a given variable index.
const std::string & name() const
Returns the name of the dimension.
IntVar * CumulVar(int64_t index) const
Get the cumul, transit and slack variables for the given node (given as int64_t var index).
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator)
Sets the breaks for a given vehicle.
int64_t GetCumulVarSoftUpperBound(int64_t index) const
Returns the soft upper bound of a cumul variable for a given variable index.
const std::vector< std::pair< int64_t, int64_t > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
void SetSpanUpperBoundForVehicle(int64_t upper_bound, int vehicle)
!defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON)
void SetGlobalSpanCostCoefficient(int64_t coefficient)
Sets a cost proportional to the global dimension span, that is the difference between the largest val...
int64_t GetCumulVarSoftLowerBoundCoefficient(int64_t index) const
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
void SetSpanCostCoefficientForVehicle(int64_t coefficient, int vehicle)
Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once.
void SetCumulVarSoftLowerBound(int64_t index, int64_t lower_bound, int64_t coefficient)
Sets a soft lower bound to the cumul variable of a given variable index.
int64_t GetCumulVarSoftLowerBound(int64_t index) const
Returns the soft lower bound of a cumul variable for a given variable index.
Manager for any NodeIndex <-> variable index conversion.
std::vector< NodeIndex > GetIndexToNodeMap() const
int num_unique_depots() const
complete.
NodeIndex IndexToNode(int64_t index) const
void ComputeNeighbors(const RoutingModel &routing_model, int num_neighbors)
Computes num_neighbors neighbors of all nodes for every cost class in routing_model.
Attributes for a dimension.
const ResourceGroup::Attributes & GetDimensionAttributes(const RoutingDimension *dimension) const
A ResourceGroup defines a set of available Resources with attributes on one or multiple dimensions.
bool VehicleRequiresAResource(int vehicle) const
int AddResource(Attributes attributes, const RoutingDimension *dimension)
Adds a Resource with the given attributes for the corresponding dimension.
ResourceGroup(const RoutingModel *model)
void NotifyVehicleRequiresAResource(int vehicle)
Notifies that the given vehicle index requires a resource from this group if the vehicle is used (i....
friend class RoutingModelInspector
Assignment * ReadAssignmentFromRoutes(const std::vector< std::vector< int64_t >> &routes, bool ignore_inactive_indices)
Restores the routes as the current solution.
int64_t ComputeLowerBound()
Computes a lower bound to the routing problem solving a linear assignment problem.
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.
const Assignment * SolveFromAssignmentsWithParameters(const std::vector< const Assignment * > &assignments, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
Same as above but will try all assignments in order as first solutions until one succeeds.
Assignment * RestoreAssignment(const Assignment &solution)
Restores an assignment as a solution in the routing model and returns the new solution.
bool RoutesToAssignment(const std::vector< std::vector< int64_t >> &routes, bool ignore_inactive_indices, bool close_routes, Assignment *const assignment) const
Fills an assignment from a specification of the routes of the vehicles.
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.
ResourceGroup * GetResourceGroup(int rg_index) const
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension with transits depending on the cumuls of another dimension.
std::vector< const RoutingDimension * > GetDimensionsWithGlobalCumulOptimizers() const
Returns the dimensions which have [global|local]_dimension_optimizers_.
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64_t vehicle) const
void AddLocalSearchOperator(LocalSearchOperator *ls_operator)
Adds a local search operator to the set of operators used to solve the vehicle routing problem.
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulLPOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
std::pair< int, bool > AddMatrixDimension(std::vector< std::vector< int64_t > > values, int64_t 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...
const Assignment * PackCumulsOfOptimizerDimensionsFromAssignment(const Assignment *original_assignment, absl::Duration duration_limit, bool *time_limit_was_reached=nullptr)
For every dimension in the model with an optimizer in local/global_dimension_optimizers_,...
const std::vector< int > & GetPairIndicesOfType(int type) const
RoutingTransitCallback1 TransitCallback1
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType(int type) const
const std::vector< int > & GetDimensionResourceGroupIndices(const RoutingDimension *dimension) const
Returns the indices of resource groups for this dimension.
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.
bool HasMandatoryDisjunctions() const
Returns true if the model contains mandatory disjunctions (ones with kNoPenalty as penalty).
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
int64_t GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
std::pair< int, bool > AddVectorDimension(std::vector< int64_t > values, int64_t 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; ...
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(int vehicle) const
bool IsStart(int64_t index) const
Returns true if 'index' represents the first node of a route.
void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy)
Sets the Pickup and delivery policy of all vehicles.
void AddSoftSameVehicleConstraint(const std::vector< int64_t > &indices, int64_t cost)
Adds a soft constraint to force a set of variable indices to be on the same vehicle.
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 ...
IntVar * ActiveVar(int64_t index) const
Returns the active variable of the node corresponding to index.
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64_t index) const
Returns the indices of the disjunctions to which an index belongs.
IntVar * NextVar(int64_t index) const
!defined(SWIGPYTHON)
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
int GetDimensionResourceGroupIndex(const RoutingDimension *dimension) const
Returns the index of the resource group attached to the dimension.
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64_t node_index) const
Same as above for deliveries.
const std::vector< int64_t > & GetDisjunctionNodeIndices(DisjunctionIndex index) const
Returns the variable indices of the nodes in the disjunction of index 'index'.
void AddToAssignment(IntVar *const var)
Adds an extra variable to the vehicle routing assignment.
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
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...
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulMPOptimizer(const RoutingDimension &dimension) const
void AddWeightedVariableTargetToFinalizer(IntVar *var, int64_t target, int64_t cost)
Same as above with a weighted priority: the higher the cost, the more priority it has to be set close...
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_t GetHomogeneousCost(int64_t from_index, int64_t to_index) const
Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns t...
IntVar * VehicleVar(int64_t index) const
Returns the vehicle variable of the node corresponding to index.
int RegisterUnaryTransitVector(std::vector< int64_t > values)
Registers 'callback' and returns its index.
bool HasLocalCumulOptimizer(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.
int64_t Size() const
Returns the number of next variables in the model.
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
int GetVisitType(int64_t index) const
bool HasTemporalTypeRequirements() const
Solver * solver() const
Returns the underlying constraint solver.
static const int64_t kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
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
bool ApplyLocksToAllVehicles(const std::vector< std::vector< int64_t >> &locks, bool close_routes)
Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for rout...
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
std::pair< int, bool > AddConstantDimensionWithSlack(int64_t value, int64_t capacity, int64_t 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...
const Assignment * SolveFromAssignmentWithParameters(const Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
Same as above, except that if assignment is not null, it will be used as the initial solution.
LocalDimensionCumulOptimizer * GetMutableLocalCumulLPOptimizer(const RoutingDimension &dimension) const
@ ROUTING_INFEASIBLE
Problem proven to be infeasible.
@ ROUTING_SUCCESS
Problem solved successfully after calling RoutingModel::Solve().
@ ROUTING_FAIL
No solution found to the problem after calling RoutingModel::Solve().
@ ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED
Problem solved successfully after calling RoutingModel::Solve(), except that a local optimum has not ...
@ ROUTING_INVALID
Model, model parameters or flags are not valid.
@ ROUTING_FAIL_TIMEOUT
Time limit reached before finding a solution with RoutingModel::Solve().
bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const
Returns true iff the model contains a vehicle with the given cost_class_index.
void SetVisitType(int64_t index, int type, VisitTypePolicy type_policy)
int64_t GetDepot() const
Returns the variable index of the first starting or ending node of all routes.
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
std::vector< const RoutingDimension * > GetDimensionsWithLocalCumulOptimizers() const
void AddWeightedVariableMaximizedByFinalizer(IntVar *var, int64_t cost)
Adds a variable to maximize in the solution finalizer, with a weighted priority: the higher the more ...
void SetSweepArranger(SweepArranger *sweep_arranger)
void AddTemporalTypeIncompatibility(int type1, int type2)
const std::vector< int > & GetSingleNodesOfType(int type) const
void SetFixedCostOfVehicle(int64_t cost, int vehicle)
Sets the fixed cost of one vehicle route.
std::vector< std::vector< std::pair< int64_t, int64_t > > > 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...
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType(int type) const
Returns the set of requirement alternatives when adding the given type.
bool ArcIsMoreConstrainedThanArc(int64_t from, int64_t to1, int64_t to2)
Returns whether the arc from->to1 is more constrained than from->to2, taking into account,...
void AddHardTypeIncompatibility(int type1, int type2)
Incompatibilities: Two nodes with "hard" incompatible types cannot share the same route at all,...
void AddPickupAndDelivery(int64_t pickup, int64_t delivery)
Notifies that index1 and index2 form a pair of nodes which should belong to the same route.
bool CheckLimit(absl::Duration offset=absl::ZeroDuration())
Returns true if the search limit has been crossed with the given time offset.
int64_t GetArcCostForFirstSolution(int64_t from_index, int64_t to_index) const
Returns the cost of the arc in the context of the first solution strategy.
bool IsVehicleAllowedForIndex(int vehicle, int64_t index)
Returns true if a vehicle is allowed to visit a given node.
int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback)
void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback)
IntVar * ApplyLocks(const std::vector< int64_t > &locks)
Applies a lock chain to the next search.
bool AreRoutesInterdependent(const RoutingSearchParameters ¶meters) const
Returns true if routes are interdependent.
int64_t GetArcCostForVehicle(int64_t from_index, int64_t to_index, int64_t vehicle) const
Returns the cost of the transit arc between two nodes for a given vehicle.
void CloseVisitTypes()
This function should be called once all node visit types have been set and prior to adding any incomp...
DisjunctionIndex AddDisjunction(const std::vector< int64_t > &indices, int64_t penalty=kNoPenalty, int64_t max_cardinality=1)
Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active.
bool HasGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns whether the given dimension has global/local cumul optimizers.
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)
void AddVariableTargetToFinalizer(IntVar *var, int64_t target)
Add a variable to set the closest possible to the target value in the solution finalizer.
int64_t UnperformedPenaltyOrValue(int64_t default_value, int64_t var_index) const
Same as above except that it returns default_value instead of 0 when penalty is not well defined (def...
int AddResourceGroup()
Adds a resource group to the routing model.
RoutingDimensionIndex DimensionIndex
Assignment * CompactAndCheckAssignment(const Assignment &assignment) const
Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not ...
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< int64_t > > GetRoutesFromAssignment(const Assignment &assignment)
Converts the solution in the given assignment to routes for all vehicles.
int64_t Next(const Assignment &assignment, int64_t index) const
Assignment inspection Returns the variable index of the node directly after the node corresponding to...
void SetAmortizedCostFactorsOfAllVehicles(int64_t linear_cost_factor, int64_t quadratic_cost_factor)
The following methods set the linear and quadratic cost factors of vehicles (must be positive values)...
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.
int64_t Start(int vehicle) const
Model inspection.
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 SetAllowedVehiclesForIndex(const std::vector< int > &vehicles, int64_t index)
Sets the vehicles which can visit a given node.
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...
int64_t UnperformedPenalty(int64_t var_index) const
Get the "unperformed" penalty of a node.
void SetAmortizedCostFactorsOfVehicle(int64_t linear_cost_factor, int64_t quadratic_cost_factor, int vehicle)
Sets the linear and quadratic cost factor of the given vehicle.
int64_t GetNumberOfDecisionsInFirstSolution(const RoutingSearchParameters &search_parameters) const
Returns statistics on first solution search, number of decisions sent to filters, number of decisions...
bool HasTypeRegulations() const
Returns true iff the model has any incompatibilities or requirements set on node types.
RoutingVehicleClassIndex VehicleClassIndex
void AddWeightedVariableMinimizedByFinalizer(IntVar *var, int64_t cost)
Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more ...
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...
std::vector< std::pair< int64_t, int64_t > > GetPerfectBinaryDisjunctions() const
Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "...
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
bool HasSameVehicleTypeRequirements() const
Returns true iff any same-route (resp.
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
int64_t GetArcCostForClass(int64_t from_index, int64_t to_index, int64_t cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
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.
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64_t node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
Creates a cached StateDependentTransit from an std::function.
int RegisterUnaryTransitCallback(TransitCallback1 callback)
int64_t GetNumberOfRejectsInFirstSolution(const RoutingSearchParameters &search_parameters) const
bool IsEnd(int64_t index) const
Returns true if 'index' represents the last node of a route.
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
bool WriteAssignment(const std::string &file_name) const
Writes the current solution to a file containing an AssignmentProto.
RoutingCostClassIndex CostClassIndex
bool HasTemporalTypeIncompatibilities() const
bool HasMaxCardinalityConstrainedDisjunctions() const
Returns true if the model contains at least one disjunction which is constrained by its max_cardinali...
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
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 AssignmentToRoutes(const Assignment &assignment, std::vector< std::vector< int64_t >> *const routes) const
Converts the solution in the given assignment to routes for all vehicles.
Status status() const
Returns the current status of the routing model.
int RegisterTransitMatrix(std::vector< std::vector< int64_t > > values)
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.
CostClassIndex GetCostClassIndexOfVehicle(int64_t vehicle) const
Get the cost class index of the given vehicle.
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 SetFixedCostOfAllVehicles(int64_t cost)
Sets the fixed cost of all vehicle routes.
void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle)
Sets the cost function for a given vehicle route.
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
VisitTypePolicy GetVisitTypePolicy(int64_t index) const
int VehicleIndex(int64_t index) const
Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/en...
bool IsVehicleUsed(const Assignment &assignment, int vehicle) const
Returns true if the route of 'vehicle' is non empty in 'assignment'.
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
bool AddDimensionWithVehicleTransitAndCapacity(const std::vector< int > &evaluator_indices, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
RoutingDisjunctionIndex DisjunctionIndex
int64_t End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
const NodeNeighborsByCostClass * GetOrCreateNodeNeighborsByCostClass(int num_neighbors)
Returns num_neighbors neighbors of all nodes for every cost class.
bool AddDimension(int evaluator_index, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
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.
virtual bool LocalOptimum()
When a local optimum is reached.
int solution_count() const
Returns how many solutions were stored during the search.
Assignment * solution(int n) const
Returns the nth solution.
Decision * MakeAssignVariableValueOrDoNothing(IntVar *const var, int64_t value)
IntExpr * RegisterIntExpr(IntExpr *const expr)
Registers a new IntExpr and wraps it inside a TraceIntExpr if necessary.
bool SolveAndCommit(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
SolveAndCommit using a decision builder and up to three search monitors, usually one for the objectiv...
@ ASSIGN_MIN_VALUE
Selects the min value of the selected variable.
IntVar * MakeIntVar(int64_t min, int64_t max, const std::string &name)
MakeIntVar will create the best range based int var for the bounds given.
void TopPeriodicCheck()
Performs PeriodicCheck on the top-level search; for instance, can be called from a nested solve to ch...
std::function< int64_t(int64_t, int64_t)> IndexEvaluator2
Decision * MakeAssignVariableValue(IntVar *const var, int64_t val)
Decisions.
@ 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)
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_t(int64_t)> IndexEvaluator1
Callback typedefs.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
std::function< bool(int64_t, int64_t, int64_t)> VariableValueComparator
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_t start, int64_t end)
Adds the interval [start..end] to the list, and merges overlapping or immediately adjacent intervals ...
ConstIterator end() const
Iterator FirstIntervalGreaterOrEqual(int64_t value) const
Returns an iterator to either:
IntervalSet::iterator Iterator
Class to arrange indices by their distance and their angle from the depot.
TypeIncompatibilityChecker(const RoutingModel &model, bool check_hard_incompatibilities)
virtual bool HasRegulationsToCheck() const =0
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
virtual void OnInitializeCheck()
bool CheckVehicle(int vehicle, const std::function< int64_t(int64_t)> &next_accessor)
TypeRegulationsChecker(const RoutingModel &model)
virtual bool FinalizeCheck() const
void InitializeCheck(int vehicle, const std::function< int64_t(int64_t)> &next_accessor)
RoutingModel::VisitTypePolicy VisitTypePolicy
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_
bool TypeOccursOnRoute(int type) const
Returns true iff any occurrence of the given type was seen on the route, i.e.
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)
static const int64_t kint64max
static const int64_t kint64min
const Collection::value_type::second_type FindPtrOrNull(const Collection &collection, const typename Collection::value_type::first_type &key)
void STLDeleteElements(T *container)
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)
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)
void swap(IdMap< K, V > &a, IdMap< K, V > &b)
std::function< int64_t(const Model &)> Value(IntegerVariable v)
Collection of objects used to extend the Constraint Solver library.
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.
int64_t CapAdd(int64_t x, int64_t y)
Demon * MakeDelayedConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
RangeIntToIntFunction * MakeCachedIntToIntFunction(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
std::function< int64_t(int64_t, int64_t)> RoutingTransitCallback2
DecisionBuilder * MakeAllUnperformed(RoutingModel *model)
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)
int64_t ComputeBestVehicleToResourceAssignment(std::vector< int > vehicles, int num_resources, std::function< const std::vector< int64_t > *(int)> vehicle_to_resource_assignment_costs, std::vector< int > *resource_indices)
std::string FindErrorInRoutingSearchParameters(const RoutingSearchParameters &search_parameters)
Returns an empty std::string if the routing search parameters are valid, and a non-empty,...
int64_t CapSub(int64_t x, int64_t y)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
Returns a filter computing vehicle amortized costs.
Demon * MakeConstraintDemon1(Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
void SetAssignmentFromAssignment(Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
NOLINT.
RangeMinMaxIndexFunction * MakeCachedRangeMinMaxIndexFunction(const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
Returns a filter checking the current solution using CP propagation.
DecisionBuilder * MakeRestoreDimensionValuesForUnchangedRoutes(RoutingModel *model)
DecisionBuilder * MakeSetValuesFromTargets(Solver *solver, std::vector< IntVar * > variables, std::vector< int64_t > targets)
A decision builder which tries to assign values to variables as close as possible to target values fi...
FirstSolutionStrategy::Value AutomaticFirstSolutionStrategy(bool has_pickup_deliveries, bool has_node_precedences, bool has_single_vehicle_node)
Returns the best value for the automatic first solution strategy, based on the given model parameters...
int64_t One()
This method returns 1.
DimensionSchedulingStatus
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
Returns a filter ensuring that max active vehicles constraints are enforced.
int64_t CapProd(int64_t x, int64_t y)
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, bool use_chain_cumul_filter, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
std::function< int64_t(int64_t)> RoutingTransitCallback1
void FillPathEvaluation(const std::vector< int64_t > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64_t > *values)
RoutingSearchParameters DefaultRoutingSearchParameters()
DecisionBuilder * MakeSweepDecisionBuilder(RoutingModel *model, bool check_assignment)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
Returns a filter checking that vehicle variable domains are respected.
std::string MemoryUsage()
std::vector< int64_t > ComputeVehicleEndChainStarts(const RoutingModel &model)
Computes and returns the first node in the end chain of each vehicle in the model,...
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
Returns a filter enforcing pickup and delivery constraints for the given pair of nodes and given poli...
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
Returns a filter ensuring type regulation constraints are enforced.
static const int kUnassigned
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)
Appends dimension-based filters to the given list of filters using a path state.
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model, bool filter_cost)
Returns a filter ensuring that node disjunction constraints are enforced.
bool ComputeVehicleToResourcesAssignmentCosts(int v, const RoutingModel::ResourceGroup &resource_group, const std::function< int64_t(int64_t)> &next_accessor, const std::function< int64_t(int64_t, int64_t)> &transit_accessor, bool optimize_vehicle_costs, LocalDimensionCumulOptimizer *lp_optimizer, LocalDimensionCumulOptimizer *mp_optimizer, std::vector< int64_t > *assignment_costs, std::vector< std::vector< int64_t >> *cumul_values, std::vector< std::vector< int64_t >> *break_values)
uint64_t MurmurHash64(const char *buf, const size_t len)
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
static int input(yyscan_t yyscanner)
#define CP_ROUTING_PUSH_OPERATOR(operator_type, operator_method, operators)
std::vector< int > var_indices
std::optional< int64_t > end
static bool LessThan(const CostClass &a, const CostClass &b)
Comparator for STL containers and algorithms.
std::string DebugString(std::string line_prefix="") const
std::string DebugString(std::string line_prefix="") const
std::vector< TransitionInfo > transition_info
For each node #i on the route, transition_info[i] contains the relevant information for the travel be...
std::string DebugString(std::string line_prefix="") const
int64_t travel_cost_coefficient
The cost per unit of travel for this vehicle.
What follows is relevant for models with time/state dependent transits.
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
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...
#define VLOG(verboselevel)