31#include "absl/algorithm/container.h"
32#include "absl/container/btree_set.h"
33#include "absl/container/flat_hash_map.h"
34#include "absl/container/flat_hash_set.h"
35#include "absl/flags/flag.h"
36#include "absl/log/check.h"
37#include "absl/strings/str_cat.h"
38#include "absl/strings/string_view.h"
39#include "absl/types/span.h"
48#include "ortools/constraint_solver/routing_parameters.pb.h"
55 "Run stronger checks in debug; these stronger tests might change "
56 "the complexity of the code in particular.");
64class MaxActiveVehiclesFilter :
public IntVarLocalSearchFilter {
66 explicit MaxActiveVehiclesFilter(
const RoutingModel& routing_model)
67 : IntVarLocalSearchFilter(routing_model.Nexts()),
68 routing_model_(routing_model),
69 is_active_(routing_model.vehicles(), false),
70 active_vehicles_(0) {}
71 bool Accept(
const Assignment*
delta,
const Assignment* ,
72 int64_t , int64_t )
override {
75 int current_active_vehicles = active_vehicles_;
76 for (
const IntVarElement& new_element : container.elements()) {
77 IntVar*
const var = new_element.Var();
79 if (FindIndex(
var, &
index) && routing_model_.IsStart(
index)) {
80 if (new_element.Min() != new_element.Max()) {
84 const int vehicle = routing_model_.VehicleIndex(
index);
85 const bool is_active =
86 (new_element.Min() != routing_model_.End(vehicle));
87 if (is_active && !is_active_[vehicle]) {
88 ++current_active_vehicles;
89 }
else if (!is_active && is_active_[vehicle]) {
90 --current_active_vehicles;
94 return current_active_vehicles <=
95 routing_model_.GetMaximumNumberOfActiveVehicles();
99 void OnSynchronize(
const Assignment* )
override {
100 active_vehicles_ = 0;
101 for (
int i = 0;
i < routing_model_.vehicles(); ++
i) {
102 const int index = routing_model_.Start(i);
104 is_active_[
i] =
true;
107 is_active_[
i] =
false;
112 const RoutingModel& routing_model_;
113 std::vector<bool> is_active_;
114 int active_vehicles_;
119 const RoutingModel& routing_model) {
120 return routing_model.solver()->RevAlloc(
121 new MaxActiveVehiclesFilter(routing_model));
127class NodeDisjunctionFilter :
public IntVarLocalSearchFilter {
129 explicit NodeDisjunctionFilter(
const RoutingModel& routing_model,
131 : IntVarLocalSearchFilter(routing_model.Nexts()),
132 routing_model_(routing_model),
133 active_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
134 inactive_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
135 synchronized_objective_value_(
std::numeric_limits<int64_t>::
min()),
136 accepted_objective_value_(
std::numeric_limits<int64_t>::
min()),
137 filter_cost_(filter_cost),
138 has_mandatory_disjunctions_(routing_model.HasMandatoryDisjunctions()) {}
140 bool Accept(
const Assignment*
delta,
const Assignment* ,
141 int64_t , int64_t objective_max)
override {
145 disjunction_active_deltas;
147 disjunction_inactive_deltas;
148 bool lns_detected =
false;
150 for (
const IntVarElement& new_element : container.elements()) {
151 IntVar*
const var = new_element.Var();
154 const bool is_inactive =
155 (new_element.Min() <=
index && new_element.Max() >=
index);
156 if (new_element.Min() != new_element.Max()) {
159 for (
const RoutingModel::DisjunctionIndex disjunction_index :
160 routing_model_.GetDisjunctionIndices(
index)) {
161 const bool is_var_synced = IsVarSynced(
index);
164 : &disjunction_active_deltas,
165 disjunction_index, 0);
168 : &disjunction_inactive_deltas,
169 disjunction_index, 0);
176 for (
const auto [disjunction_index, active_nodes] :
177 disjunction_active_deltas) {
179 if (active_per_disjunction_[disjunction_index] + active_nodes >
180 routing_model_.GetDisjunctionMaxCardinality(disjunction_index)) {
184 if (lns_detected || (!filter_cost_ && !has_mandatory_disjunctions_)) {
185 accepted_objective_value_ = 0;
189 accepted_objective_value_ = synchronized_objective_value_;
190 for (
const auto [disjunction_index, inactive_nodes] :
191 disjunction_inactive_deltas) {
192 const int64_t penalty =
193 routing_model_.GetDisjunctionPenalty(disjunction_index);
194 if (penalty == 0)
continue;
195 const int current_inactive_nodes =
196 inactive_per_disjunction_[disjunction_index];
197 const int max_inactive_cardinality =
198 routing_model_.GetDisjunctionNodeIndices(disjunction_index).size() -
199 routing_model_.GetDisjunctionMaxCardinality(disjunction_index);
201 if (current_inactive_nodes + inactive_nodes > max_inactive_cardinality) {
206 }
else if (current_inactive_nodes <= max_inactive_cardinality) {
209 accepted_objective_value_ =
210 CapAdd(accepted_objective_value_, penalty);
212 }
else if (current_inactive_nodes > max_inactive_cardinality) {
215 accepted_objective_value_ =
CapSub(accepted_objective_value_, penalty);
219 return accepted_objective_value_ <= objective_max;
221 std::string DebugString()
const override {
return "NodeDisjunctionFilter"; }
222 int64_t GetSynchronizedObjectiveValue()
const override {
223 return synchronized_objective_value_;
225 int64_t GetAcceptedObjectiveValue()
const override {
226 return accepted_objective_value_;
230 void OnSynchronize(
const Assignment* )
override {
231 synchronized_objective_value_ = 0;
232 for (RoutingModel::DisjunctionIndex
i(0);
233 i < active_per_disjunction_.size(); ++
i) {
234 active_per_disjunction_[
i] = 0;
235 inactive_per_disjunction_[
i] = 0;
236 const std::vector<int64_t>& disjunction_indices =
237 routing_model_.GetDisjunctionNodeIndices(i);
238 for (
const int64_t
index : disjunction_indices) {
239 if (IsVarSynced(
index)) {
241 ++active_per_disjunction_[
i];
243 ++inactive_per_disjunction_[
i];
247 if (!filter_cost_)
continue;
248 const int64_t penalty = routing_model_.GetDisjunctionPenalty(i);
249 const int max_cardinality =
250 routing_model_.GetDisjunctionMaxCardinality(i);
251 if (inactive_per_disjunction_[i] >
252 disjunction_indices.size() - max_cardinality &&
254 synchronized_objective_value_ =
255 CapAdd(synchronized_objective_value_, penalty);
260 const RoutingModel& routing_model_;
263 active_per_disjunction_;
265 inactive_per_disjunction_;
266 int64_t synchronized_objective_value_;
267 int64_t accepted_objective_value_;
268 const bool filter_cost_;
269 const bool has_mandatory_disjunctions_;
274 const RoutingModel& routing_model,
bool filter_cost) {
275 return routing_model.solver()->RevAlloc(
276 new NodeDisjunctionFilter(routing_model, filter_cost));
282 int next_domain_size)
285 paths_(nexts.size(), -1),
286 new_synchronized_unperformed_nodes_(nexts.size()),
288 touched_paths_(nexts.size()),
290 ranks_(next_domain_size, -1),
291 status_(BasePathFilter::UNKNOWN),
292 lns_detected_(
false) {}
296 int64_t objective_min, int64_t objective_max) {
298 lns_detected_ =
false;
299 for (
const int touched : delta_touched_) {
302 delta_touched_.clear();
304 delta_touched_.reserve(container.
Size());
316 const auto update_touched_path_chain_start_end = [
this](int64_t
index) {
317 const int64_t
start = node_path_starts_[
index];
321 int64_t& chain_start = touched_path_chain_start_ends_[
start].first;
326 int64_t& chain_end = touched_path_chain_start_ends_[
start].second;
336 if (!new_element.Bound()) {
338 lns_detected_ =
true;
341 new_nexts_[
index] = new_element.Value();
342 delta_touched_.push_back(
index);
343 update_touched_path_chain_start_end(
index);
344 update_touched_path_chain_start_end(new_nexts_[
index]);
348 if (!InitializeAcceptPath())
return false;
350 const std::pair<int64_t, int64_t> start_end =
351 touched_path_chain_start_ends_[touched_start];
352 if (!AcceptPath(touched_start, start_end.first, start_end.second)) {
358 return FinalizeAcceptPath(objective_min, objective_max);
361void BasePathFilter::ComputePathStarts(std::vector<int64_t>* path_starts,
362 std::vector<int>* index_to_path) {
363 path_starts->clear();
364 const int nexts_size =
Size();
367 for (
int i = 0; i < nexts_size; ++i) {
372 if (
next < nexts_size) {
377 for (
int i = 0;
i < nexts_size; ++
i) {
379 (*index_to_path)[
i] = path_starts->size();
380 path_starts->push_back(i);
385bool BasePathFilter::HavePathsChanged() {
386 std::vector<int64_t> path_starts;
388 ComputePathStarts(&path_starts, &index_to_path);
389 if (path_starts.size() != starts_.size()) {
392 for (
int i = 0;
i < path_starts.size(); ++
i) {
393 if (path_starts[i] != starts_[i]) {
397 for (
int i = 0;
i <
Size(); ++
i) {
398 if (index_to_path[i] != paths_[i]) {
405void BasePathFilter::SynchronizeFullAssignment() {
409 ComputePathStarts(&starts_, &paths_);
414 new_synchronized_unperformed_nodes_.
Set(
index);
418 node_path_starts_.assign(node_path_starts_.size(),
kUnassigned);
420 const int nexts_size =
Size();
421 for (
const int64_t
start : starts_) {
423 node_path_starts_[node] =
start;
426 while (
next < nexts_size) {
428 node_path_starts_[node] =
start;
434 for (
const int touched : delta_touched_) {
437 delta_touched_.clear();
438 OnBeforeSynchronizePaths();
440 OnAfterSynchronizePaths();
444 if (status_ == BasePathFilter::UNKNOWN) {
446 DisableFiltering() ? BasePathFilter::DISABLED : BasePathFilter::ENABLED;
449 new_synchronized_unperformed_nodes_.
ClearAll();
450 if (
delta ==
nullptr ||
delta->Empty() || starts_.empty()) {
451 SynchronizeFullAssignment();
458 DCHECK(!absl::GetFlag(FLAGS_routing_strong_debug_checks) ||
459 !HavePathsChanged());
465 const int64_t
start = node_path_starts_[
index];
470 DCHECK_LT(
index, new_nexts_.size());
471 new_synchronized_unperformed_nodes_.
Set(
index);
477 for (
const int touched : delta_touched_) {
480 delta_touched_.clear();
481 OnBeforeSynchronizePaths();
483 int64_t node = touched_start;
484 while (node <
Size()) {
485 node_path_starts_[node] = touched_start;
488 node_path_starts_[node] = touched_start;
489 UpdatePathRanksFromStart(touched_start);
490 OnSynchronizePathFromStart(touched_start);
492 OnAfterSynchronizePaths();
495void BasePathFilter::UpdateAllRanks() {
497 for (
int r = 0; r <
NumPaths(); ++r) {
498 UpdatePathRanksFromStart(
Start(r));
499 OnSynchronizePathFromStart(
Start(r));
503void BasePathFilter::UpdatePathRanksFromStart(
int start) {
505 int64_t node =
start;
506 while (node <
Size()) {
516class VehicleAmortizedCostFilter :
public BasePathFilter {
518 explicit VehicleAmortizedCostFilter(
const RoutingModel& routing_model);
519 ~VehicleAmortizedCostFilter()
override {}
520 std::string DebugString()
const override {
521 return "VehicleAmortizedCostFilter";
523 int64_t GetSynchronizedObjectiveValue()
const override {
524 return current_vehicle_cost_;
526 int64_t GetAcceptedObjectiveValue()
const override {
527 return lns_detected() ? 0 : delta_vehicle_cost_;
531 void OnSynchronizePathFromStart(int64_t
start)
override;
532 void OnAfterSynchronizePaths()
override;
533 bool InitializeAcceptPath()
override;
534 bool AcceptPath(int64_t path_start, int64_t chain_start,
535 int64_t chain_end)
override;
536 bool FinalizeAcceptPath(int64_t objective_min,
537 int64_t objective_max)
override;
539 int64_t current_vehicle_cost_;
540 int64_t delta_vehicle_cost_;
541 std::vector<int> current_route_lengths_;
542 std::vector<int64_t> start_to_end_;
543 std::vector<int> start_to_vehicle_;
544 std::vector<int64_t> vehicle_to_start_;
545 const std::vector<int64_t>& linear_cost_factor_of_vehicle_;
546 const std::vector<int64_t>& quadratic_cost_factor_of_vehicle_;
549VehicleAmortizedCostFilter::VehicleAmortizedCostFilter(
550 const RoutingModel& routing_model)
551 : BasePathFilter(routing_model.Nexts(),
552 routing_model.Size() + routing_model.vehicles()),
553 current_vehicle_cost_(0),
554 delta_vehicle_cost_(0),
555 current_route_lengths_(Size(), -1),
556 linear_cost_factor_of_vehicle_(
557 routing_model.GetAmortizedLinearCostFactorOfVehicles()),
558 quadratic_cost_factor_of_vehicle_(
559 routing_model.GetAmortizedQuadraticCostFactorOfVehicles()) {
560 start_to_end_.resize(
Size(), -1);
561 start_to_vehicle_.resize(
Size(), -1);
562 vehicle_to_start_.resize(routing_model.vehicles());
563 for (
int v = 0; v < routing_model.vehicles(); v++) {
564 const int64_t
start = routing_model.Start(v);
565 start_to_vehicle_[
start] = v;
566 start_to_end_[
start] = routing_model.End(v);
567 vehicle_to_start_[v] =
start;
571void VehicleAmortizedCostFilter::OnSynchronizePathFromStart(int64_t
start) {
572 const int64_t
end = start_to_end_[
start];
574 const int route_length = Rank(
end) - 1;
575 CHECK_GE(route_length, 0);
576 current_route_lengths_[
start] = route_length;
579void VehicleAmortizedCostFilter::OnAfterSynchronizePaths() {
580 current_vehicle_cost_ = 0;
581 for (
int vehicle = 0; vehicle < vehicle_to_start_.size(); vehicle++) {
582 const int64_t
start = vehicle_to_start_[vehicle];
583 DCHECK_EQ(vehicle, start_to_vehicle_[
start]);
585 const int route_length = current_route_lengths_[
start];
586 DCHECK_GE(route_length, 0);
588 if (route_length == 0) {
593 const int64_t linear_cost_factor = linear_cost_factor_of_vehicle_[vehicle];
594 const int64_t route_length_cost =
595 CapProd(quadratic_cost_factor_of_vehicle_[vehicle],
596 route_length * route_length);
598 current_vehicle_cost_ =
CapAdd(
599 current_vehicle_cost_,
CapSub(linear_cost_factor, route_length_cost));
603bool VehicleAmortizedCostFilter::InitializeAcceptPath() {
604 delta_vehicle_cost_ = current_vehicle_cost_;
608bool VehicleAmortizedCostFilter::AcceptPath(int64_t path_start,
612 const int previous_chain_nodes = Rank(chain_end) - 1 - Rank(chain_start);
613 CHECK_GE(previous_chain_nodes, 0);
614 int new_chain_nodes = 0;
615 int64_t node = GetNext(chain_start);
616 while (node != chain_end) {
618 node = GetNext(node);
621 const int previous_route_length = current_route_lengths_[path_start];
622 CHECK_GE(previous_route_length, 0);
623 const int new_route_length =
624 previous_route_length - previous_chain_nodes + new_chain_nodes;
626 const int vehicle = start_to_vehicle_[path_start];
627 CHECK_GE(vehicle, 0);
628 DCHECK_EQ(path_start, vehicle_to_start_[vehicle]);
632 if (previous_route_length == 0) {
634 CHECK_GT(new_route_length, 0);
635 delta_vehicle_cost_ =
636 CapAdd(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
637 }
else if (new_route_length == 0) {
639 delta_vehicle_cost_ =
640 CapSub(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
644 const int64_t quadratic_cost_factor =
645 quadratic_cost_factor_of_vehicle_[vehicle];
646 delta_vehicle_cost_ =
647 CapAdd(delta_vehicle_cost_,
649 previous_route_length * previous_route_length));
650 delta_vehicle_cost_ =
CapSub(
652 CapProd(quadratic_cost_factor, new_route_length * new_route_length));
657bool VehicleAmortizedCostFilter::FinalizeAcceptPath(int64_t ,
658 int64_t objective_max) {
659 return delta_vehicle_cost_ <= objective_max;
665 const RoutingModel& routing_model) {
666 return routing_model.solver()->RevAlloc(
667 new VehicleAmortizedCostFilter(routing_model));
672class TypeRegulationsFilter :
public BasePathFilter {
674 explicit TypeRegulationsFilter(
const RoutingModel&
model);
675 ~TypeRegulationsFilter()
override {}
676 std::string DebugString()
const override {
return "TypeRegulationsFilter"; }
679 void OnSynchronizePathFromStart(int64_t
start)
override;
680 bool AcceptPath(int64_t path_start, int64_t chain_start,
681 int64_t chain_end)
override;
683 bool HardIncompatibilitiesRespected(
int vehicle, int64_t chain_start,
686 const RoutingModel& routing_model_;
687 std::vector<int> start_to_vehicle_;
690 std::vector<std::vector<int>> hard_incompatibility_type_counts_per_vehicle_;
692 TypeIncompatibilityChecker temporal_incompatibility_checker_;
693 TypeRequirementChecker requirement_checker_;
696TypeRegulationsFilter::TypeRegulationsFilter(
const RoutingModel&
model)
698 routing_model_(
model),
699 start_to_vehicle_(
model.Size(), -1),
700 temporal_incompatibility_checker_(
model,
702 requirement_checker_(
model) {
703 const int num_vehicles =
model.vehicles();
704 const bool has_hard_type_incompatibilities =
705 model.HasHardTypeIncompatibilities();
706 if (has_hard_type_incompatibilities) {
707 hard_incompatibility_type_counts_per_vehicle_.resize(num_vehicles);
709 const int num_visit_types =
model.GetNumberOfVisitTypes();
710 for (
int vehicle = 0; vehicle < num_vehicles; vehicle++) {
712 start_to_vehicle_[
start] = vehicle;
713 if (has_hard_type_incompatibilities) {
714 hard_incompatibility_type_counts_per_vehicle_[vehicle].resize(
720void TypeRegulationsFilter::OnSynchronizePathFromStart(int64_t
start) {
721 if (!routing_model_.HasHardTypeIncompatibilities())
return;
723 const int vehicle = start_to_vehicle_[
start];
724 CHECK_GE(vehicle, 0);
725 std::vector<int>& type_counts =
726 hard_incompatibility_type_counts_per_vehicle_[vehicle];
727 std::fill(type_counts.begin(), type_counts.end(), 0);
728 const int num_types = type_counts.size();
730 int64_t node =
start;
731 while (node < Size()) {
732 DCHECK(IsVarSynced(node));
733 const int type = routing_model_.GetVisitType(node);
734 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
735 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
736 CHECK_LT(type, num_types);
743bool TypeRegulationsFilter::HardIncompatibilitiesRespected(
int vehicle,
746 if (!routing_model_.HasHardTypeIncompatibilities())
return true;
748 const std::vector<int>& previous_type_counts =
749 hard_incompatibility_type_counts_per_vehicle_[vehicle];
751 absl::flat_hash_map< int,
int> new_type_counts;
752 absl::flat_hash_set<int> types_to_check;
755 int64_t node = GetNext(chain_start);
756 while (node != chain_end) {
757 const int type = routing_model_.GetVisitType(node);
758 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
759 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
760 DCHECK_LT(type, previous_type_counts.size());
762 previous_type_counts[type]);
763 if (type_count++ == 0) {
765 types_to_check.insert(type);
768 node = GetNext(node);
773 node =
Value(chain_start);
774 while (node != chain_end) {
775 const int type = routing_model_.GetVisitType(node);
776 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
777 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
778 DCHECK_LT(type, previous_type_counts.size());
780 previous_type_counts[type]);
781 CHECK_GE(type_count, 1);
788 for (
int type : types_to_check) {
789 for (
int incompatible_type :
790 routing_model_.GetHardTypeIncompatibilitiesOfType(type)) {
792 previous_type_counts[incompatible_type]) > 0) {
800bool TypeRegulationsFilter::AcceptPath(int64_t path_start, int64_t chain_start,
802 const int vehicle = start_to_vehicle_[path_start];
803 CHECK_GE(vehicle, 0);
804 const auto next_accessor = [
this](int64_t node) {
return GetNext(node); };
805 return HardIncompatibilitiesRespected(vehicle, chain_start, chain_end) &&
806 temporal_incompatibility_checker_.CheckVehicle(vehicle,
808 requirement_checker_.CheckVehicle(vehicle, next_accessor);
814 const RoutingModel& routing_model) {
815 return routing_model.solver()->RevAlloc(
816 new TypeRegulationsFilter(routing_model));
826class ChainCumulFilter :
public BasePathFilter {
828 ChainCumulFilter(
const RoutingModel& routing_model,
829 const RoutingDimension& dimension);
830 ~ChainCumulFilter()
override {}
831 std::string DebugString()
const override {
832 return "ChainCumulFilter(" + name_ +
")";
836 void OnSynchronizePathFromStart(int64_t
start)
override;
837 bool AcceptPath(int64_t path_start, int64_t chain_start,
838 int64_t chain_end)
override;
840 const std::vector<IntVar*>
cumuls_;
841 std::vector<int64_t> start_to_vehicle_;
842 std::vector<int64_t> start_to_end_;
843 std::vector<const RoutingModel::TransitCallback2*> evaluators_;
844 const std::vector<int64_t> vehicle_capacities_;
845 std::vector<int64_t> current_path_cumul_mins_;
846 std::vector<int64_t> current_max_of_path_end_cumul_mins_;
847 std::vector<int64_t> old_nexts_;
848 std::vector<int> old_vehicles_;
849 std::vector<int64_t> current_transits_;
850 const std::string name_;
853ChainCumulFilter::ChainCumulFilter(
const RoutingModel& routing_model,
854 const RoutingDimension& dimension)
855 : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
857 evaluators_(routing_model.vehicles(), nullptr),
858 vehicle_capacities_(dimension.vehicle_capacities()),
859 current_path_cumul_mins_(dimension.cumuls().size(), 0),
860 current_max_of_path_end_cumul_mins_(dimension.cumuls().size(), 0),
861 old_nexts_(routing_model.Size(), kUnassigned),
862 old_vehicles_(routing_model.Size(), kUnassigned),
863 current_transits_(routing_model.Size(), 0),
864 name_(dimension.
name()) {
865 start_to_vehicle_.resize(Size(), -1);
866 start_to_end_.resize(Size(), -1);
867 for (
int i = 0;
i < routing_model.vehicles(); ++
i) {
868 start_to_vehicle_[routing_model.Start(i)] =
i;
869 start_to_end_[routing_model.Start(i)] = routing_model.End(i);
870 evaluators_[
i] = &dimension.transit_evaluator(i);
877void ChainCumulFilter::OnSynchronizePathFromStart(int64_t
start) {
878 const int vehicle = start_to_vehicle_[
start];
879 std::vector<int64_t> path_nodes;
880 int64_t node =
start;
881 int64_t cumul =
cumuls_[node]->Min();
882 while (node < Size()) {
883 path_nodes.push_back(node);
884 current_path_cumul_mins_[node] = cumul;
886 if (
next != old_nexts_[node] || vehicle != old_vehicles_[node]) {
887 old_nexts_[node] =
next;
888 old_vehicles_[node] = vehicle;
889 current_transits_[node] = (*evaluators_[vehicle])(node,
next);
891 cumul =
CapAdd(cumul, current_transits_[node]);
892 cumul = std::max(cumuls_[
next]->Min(), cumul);
895 path_nodes.push_back(node);
896 current_path_cumul_mins_[node] = cumul;
897 int64_t max_cumuls = cumul;
898 for (
int i = path_nodes.size() - 1;
i >= 0; --
i) {
899 const int64_t node = path_nodes[
i];
900 max_cumuls = std::max(max_cumuls, current_path_cumul_mins_[node]);
901 current_max_of_path_end_cumul_mins_[node] = max_cumuls;
906bool ChainCumulFilter::AcceptPath(int64_t path_start, int64_t chain_start,
908 const int vehicle = start_to_vehicle_[path_start];
909 const int64_t capacity = vehicle_capacities_[vehicle];
910 int64_t node = chain_start;
911 int64_t cumul = current_path_cumul_mins_[node];
912 while (node != chain_end) {
913 const int64_t
next = GetNext(node);
914 if (IsVarSynced(node) &&
next ==
Value(node) &&
915 vehicle == old_vehicles_[node]) {
916 cumul =
CapAdd(cumul, current_transits_[node]);
918 cumul =
CapAdd(cumul, (*evaluators_[vehicle])(node,
next));
920 cumul = std::max(cumuls_[
next]->Min(), cumul);
921 if (cumul > capacity)
return false;
924 const int64_t
end = start_to_end_[path_start];
925 const int64_t end_cumul_delta =
926 CapSub(current_path_cumul_mins_[
end], current_path_cumul_mins_[node]);
927 const int64_t after_chain_cumul_delta =
928 CapSub(current_max_of_path_end_cumul_mins_[node],
929 current_path_cumul_mins_[node]);
930 return CapAdd(cumul, after_chain_cumul_delta) <= capacity &&
936class PathCumulFilter :
public BasePathFilter {
938 PathCumulFilter(
const RoutingModel& routing_model,
939 const RoutingDimension& dimension,
940 bool propagate_own_objective_value,
941 bool filter_objective_cost,
bool can_use_lp);
942 ~PathCumulFilter()
override {}
943 std::string DebugString()
const override {
944 return "PathCumulFilter(" + name_ +
")";
946 int64_t GetSynchronizedObjectiveValue()
const override {
947 return propagate_own_objective_value_ ? synchronized_objective_value_ : 0;
949 int64_t GetAcceptedObjectiveValue()
const override {
950 return lns_detected() || !propagate_own_objective_value_
952 : accepted_objective_value_;
959 struct SupportedPathCumul {
980 void ClearPath(
int path) {
981 paths_[path].clear();
982 transits_[path].clear();
984 int AddPaths(
int num_paths) {
985 const int first_path = paths_.size();
986 paths_.resize(first_path + num_paths);
987 transits_.resize(first_path + num_paths);
990 void ReserveTransits(
int path,
int number_of_route_arcs) {
991 transits_[path].reserve(number_of_route_arcs);
992 paths_[path].reserve(number_of_route_arcs + 1);
996 void PushTransit(
int path,
int node,
int next, int64_t transit) {
997 transits_[path].push_back(transit);
998 if (paths_[path].empty()) {
999 paths_[path].push_back(node);
1001 DCHECK_EQ(paths_[path].back(), node);
1002 paths_[path].push_back(
next);
1004 int NumPaths()
const {
return paths_.size(); }
1005 int PathSize(
int path)
const {
return paths_[path].size(); }
1006 int Node(
int path,
int position)
const {
return paths_[path][position]; }
1007 int64_t Transit(
int path,
int position)
const {
1008 return transits_[path][position];
1013 std::vector<std::vector<int64_t>> paths_;
1016 std::vector<std::vector<int64_t>> transits_;
1019 bool InitializeAcceptPath()
override {
1020 cumul_cost_delta_ = total_current_cumul_cost_value_;
1021 node_with_precedence_to_delta_min_max_cumuls_.clear();
1023 delta_max_end_cumul_ = std::numeric_limits<int64_t>::min();
1024 delta_paths_.clear();
1025 delta_path_transits_.Clear();
1026 delta_nodes_with_precedences_and_changed_cumul_.
ClearAll();
1029 bool AcceptPath(int64_t path_start, int64_t chain_start,
1030 int64_t chain_end)
override;
1031 bool FinalizeAcceptPath(int64_t objective_min,
1032 int64_t objective_max)
override;
1033 void OnBeforeSynchronizePaths()
override;
1035 bool FilterSpanCost()
const {
return global_span_cost_coefficient_ != 0; }
1037 bool FilterSlackCost()
const {
1038 return has_nonzero_vehicle_total_slack_cost_coefficients_ ||
1039 has_vehicle_span_upper_bounds_;
1042 bool FilterBreakCost(
int vehicle)
const {
1043 return dimension_.HasBreakConstraints() &&
1044 !dimension_.GetBreakIntervalsOfVehicle(vehicle).empty();
1047 bool FilterCumulSoftBounds()
const {
return !cumul_soft_bounds_.empty(); }
1049 int64_t GetCumulSoftCost(int64_t node, int64_t
cumul_value)
const;
1051 bool FilterCumulPiecewiseLinearCosts()
const {
1052 return !cumul_piecewise_linear_costs_.empty();
1055 bool FilterWithDimensionCumulOptimizerForVehicle(
int vehicle)
const {
1056 if (!can_use_lp_ || FilterCumulPiecewiseLinearCosts()) {
1060 int num_linear_constraints = 0;
1061 if (dimension_.GetSpanCostCoefficientForVehicle(vehicle) > 0 ||
1062 dimension_.GetSlackCostCoefficientForVehicle(vehicle) > 0) {
1063 ++num_linear_constraints;
1065 if (FilterSoftSpanCost(vehicle)) ++num_linear_constraints;
1066 if (FilterCumulSoftLowerBounds()) ++num_linear_constraints;
1067 if (FilterCumulSoftBounds()) ++num_linear_constraints;
1068 if (vehicle_span_upper_bounds_[vehicle] <
1069 std::numeric_limits<int64_t>::max()) {
1070 ++num_linear_constraints;
1072 const bool has_breaks = FilterBreakCost(vehicle);
1073 if (has_breaks) ++num_linear_constraints;
1082 return num_linear_constraints >= 2 &&
1083 (has_breaks || filter_objective_cost_);
1086 int64_t GetCumulPiecewiseLinearCost(int64_t node, int64_t
cumul_value)
const;
1088 bool FilterCumulSoftLowerBounds()
const {
1089 return !cumul_soft_lower_bounds_.empty();
1092 bool FilterPrecedences()
const {
return !node_index_to_precedences_.empty(); }
1094 bool FilterSoftSpanCost()
const {
1095 return dimension_.HasSoftSpanUpperBounds();
1097 bool FilterSoftSpanCost(
int vehicle)
const {
1098 return dimension_.HasSoftSpanUpperBounds() &&
1099 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle).cost > 0;
1101 bool FilterSoftSpanQuadraticCost()
const {
1102 return dimension_.HasQuadraticCostSoftSpanUpperBounds();
1104 bool FilterSoftSpanQuadraticCost(
int vehicle)
const {
1105 return dimension_.HasQuadraticCostSoftSpanUpperBounds() &&
1106 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle)
1110 int64_t GetCumulSoftLowerBoundCost(int64_t node, int64_t
cumul_value)
const;
1112 int64_t GetPathCumulSoftLowerBoundCost(
const PathTransits& path_transits,
1115 void InitializeSupportedPathCumul(SupportedPathCumul* supported_cumul,
1116 int64_t default_value);
1126 bool PickupToDeliveryLimitsRespected(
1127 const PathTransits& path_transits,
int path,
1128 absl::Span<const int64_t> min_path_cumuls)
const;
1138 void StoreMinMaxCumulOfNodesOnPath(
int path,
1139 absl::Span<const int64_t> min_path_cumuls,
1149 int64_t ComputePathMaxStartFromEndCumul(
const PathTransits& path_transits,
1150 int path, int64_t path_start,
1151 int64_t min_end_cumul)
const;
1153 const RoutingModel& routing_model_;
1154 const RoutingDimension& dimension_;
1155 const std::vector<IntVar*>
cumuls_;
1156 const std::vector<IntVar*> slacks_;
1157 std::vector<int64_t> start_to_vehicle_;
1158 std::vector<const RoutingModel::TransitCallback2*> evaluators_;
1159 std::vector<int64_t> vehicle_span_upper_bounds_;
1160 const bool has_vehicle_span_upper_bounds_;
1161 int64_t total_current_cumul_cost_value_;
1162 int64_t synchronized_objective_value_;
1163 int64_t accepted_objective_value_;
1166 absl::flat_hash_map<int64_t, int64_t> current_cumul_cost_values_;
1167 int64_t cumul_cost_delta_;
1169 std::vector<int64_t> delta_path_cumul_cost_values_;
1170 const int64_t global_span_cost_coefficient_;
1171 std::vector<SoftBound> cumul_soft_bounds_;
1172 std::vector<SoftBound> cumul_soft_lower_bounds_;
1173 std::vector<const PiecewiseLinearFunction*> cumul_piecewise_linear_costs_;
1174 std::vector<int64_t> vehicle_total_slack_cost_coefficients_;
1175 bool has_nonzero_vehicle_total_slack_cost_coefficients_;
1176 const std::vector<int64_t> vehicle_capacities_;
1180 std::vector<std::vector<RoutingDimension::NodePrecedence>>
1181 node_index_to_precedences_;
1184 SupportedPathCumul current_min_start_;
1185 SupportedPathCumul current_max_end_;
1186 PathTransits current_path_transits_;
1188 std::vector<std::pair<int64_t, int64_t>> current_min_max_node_cumuls_;
1191 PathTransits delta_path_transits_;
1192 int64_t delta_max_end_cumul_;
1193 SparseBitset<int64_t> delta_nodes_with_precedences_and_changed_cumul_;
1194 absl::flat_hash_map<int64_t, std::pair<int64_t, int64_t>>
1195 node_with_precedence_to_delta_min_max_cumuls_;
1196 absl::btree_set<int> delta_paths_;
1197 const std::string name_;
1199 LocalDimensionCumulOptimizer* optimizer_;
1200 LocalDimensionCumulOptimizer* mp_optimizer_;
1201 const std::function<int64_t(int64_t)> path_accessor_;
1202 const bool filter_objective_cost_;
1205 const bool can_use_lp_;
1206 const bool propagate_own_objective_value_;
1208 std::vector<int64_t> min_path_cumuls_;
1212template <
typename T>
1213std::vector<T> SumOfVectors(
const std::vector<T>& v1,
1214 const std::vector<T>& v2) {
1215 DCHECK_EQ(v1.size(), v2.size());
1216 std::vector<T> sum(v1.size());
1217 absl::c_transform(v1, v2, sum.begin(), [](T
a, T
b) { return CapAdd(a, b); });
1222PathCumulFilter::PathCumulFilter(
const RoutingModel& routing_model,
1223 const RoutingDimension& dimension,
1224 bool propagate_own_objective_value,
1225 bool filter_objective_cost,
bool can_use_lp)
1226 : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
1227 routing_model_(routing_model),
1228 dimension_(dimension),
1230 slacks_(dimension.slacks()),
1231 evaluators_(routing_model.vehicles(), nullptr),
1232 vehicle_span_upper_bounds_(dimension.vehicle_span_upper_bounds()),
1233 has_vehicle_span_upper_bounds_(
absl::c_any_of(
1234 vehicle_span_upper_bounds_,
1236 return upper_bound != std::numeric_limits<int64_t>::max();
1238 total_current_cumul_cost_value_(0),
1239 synchronized_objective_value_(0),
1240 accepted_objective_value_(0),
1241 current_cumul_cost_values_(),
1242 cumul_cost_delta_(0),
1243 delta_path_cumul_cost_values_(routing_model.vehicles(),
1244 std::numeric_limits<int64_t>::min()),
1245 global_span_cost_coefficient_(dimension.global_span_cost_coefficient()),
1246 vehicle_total_slack_cost_coefficients_(
1247 SumOfVectors(dimension.vehicle_span_cost_coefficients(),
1248 dimension.vehicle_slack_cost_coefficients())),
1249 has_nonzero_vehicle_total_slack_cost_coefficients_(
1250 absl::c_any_of(vehicle_total_slack_cost_coefficients_,
1252 vehicle_capacities_(dimension.vehicle_capacities()),
1253 delta_max_end_cumul_(0),
1254 delta_nodes_with_precedences_and_changed_cumul_(routing_model.Size()),
1255 name_(dimension.name()),
1256 optimizer_(routing_model.GetMutableLocalCumulLPOptimizer(dimension)),
1257 mp_optimizer_(routing_model.GetMutableLocalCumulMPOptimizer(dimension)),
1258 path_accessor_([
this](int64_t node) {
return GetNext(node); }),
1259 filter_objective_cost_(filter_objective_cost),
1260 can_use_lp_(can_use_lp),
1261 propagate_own_objective_value_(propagate_own_objective_value) {
1262 cumul_soft_bounds_.resize(
cumuls_.size());
1263 cumul_soft_lower_bounds_.resize(
cumuls_.size());
1264 cumul_piecewise_linear_costs_.resize(
cumuls_.size());
1265 bool has_cumul_soft_bounds =
false;
1266 bool has_cumul_soft_lower_bounds =
false;
1267 bool has_cumul_piecewise_linear_costs =
false;
1268 bool has_cumul_hard_bounds =
false;
1269 for (
const IntVar*
const slack : slacks_) {
1270 if (slack->Min() > 0) {
1271 has_cumul_hard_bounds =
true;
1275 for (
int i = 0;
i <
cumuls_.size(); ++
i) {
1276 if (dimension.HasCumulVarSoftUpperBound(i)) {
1277 has_cumul_soft_bounds =
true;
1278 cumul_soft_bounds_[
i].bound = dimension.GetCumulVarSoftUpperBound(i);
1279 cumul_soft_bounds_[
i].coefficient =
1280 dimension.GetCumulVarSoftUpperBoundCoefficient(i);
1282 if (dimension.HasCumulVarSoftLowerBound(i)) {
1283 has_cumul_soft_lower_bounds =
true;
1284 cumul_soft_lower_bounds_[
i].bound =
1285 dimension.GetCumulVarSoftLowerBound(i);
1286 cumul_soft_lower_bounds_[
i].coefficient =
1287 dimension.GetCumulVarSoftLowerBoundCoefficient(i);
1289 if (dimension.HasCumulVarPiecewiseLinearCost(i)) {
1290 has_cumul_piecewise_linear_costs =
true;
1291 cumul_piecewise_linear_costs_[
i] =
1292 dimension.GetCumulVarPiecewiseLinearCost(i);
1294 IntVar*
const cumul_var =
cumuls_[
i];
1295 if (cumul_var->Min() > 0 ||
1296 cumul_var->Max() < std::numeric_limits<int64_t>::max()) {
1297 has_cumul_hard_bounds =
true;
1300 if (!has_cumul_soft_bounds) {
1301 cumul_soft_bounds_.clear();
1303 if (!has_cumul_soft_lower_bounds) {
1304 cumul_soft_lower_bounds_.clear();
1306 if (!has_cumul_piecewise_linear_costs) {
1307 cumul_piecewise_linear_costs_.clear();
1309 if (!has_cumul_hard_bounds) {
1314 vehicle_total_slack_cost_coefficients_.assign(routing_model.vehicles(), 0);
1315 has_nonzero_vehicle_total_slack_cost_coefficients_ =
false;
1317 start_to_vehicle_.resize(Size(), -1);
1318 for (
int i = 0;
i < routing_model.vehicles(); ++
i) {
1319 start_to_vehicle_[routing_model.Start(i)] =
i;
1320 evaluators_[
i] = &dimension.transit_evaluator(i);
1323 const std::vector<RoutingDimension::NodePrecedence>& node_precedences =
1324 dimension.GetNodePrecedences();
1325 if (!node_precedences.empty()) {
1326 current_min_max_node_cumuls_.resize(
cumuls_.size(), {-1, -1});
1327 node_index_to_precedences_.resize(
cumuls_.size());
1328 for (
const auto& node_precedence : node_precedences) {
1329 node_index_to_precedences_[node_precedence.first_node].push_back(
1331 node_index_to_precedences_[node_precedence.second_node].push_back(
1337 for (
int vehicle = 0; vehicle < routing_model.vehicles(); vehicle++) {
1338 if (FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1339 DCHECK_NE(optimizer_,
nullptr);
1340 DCHECK_NE(mp_optimizer_,
nullptr);
1346int64_t PathCumulFilter::GetCumulSoftCost(int64_t node,
1348 if (node < cumul_soft_bounds_.size()) {
1349 const int64_t
bound = cumul_soft_bounds_[node].bound;
1350 const int64_t
coefficient = cumul_soft_bounds_[node].coefficient;
1358int64_t PathCumulFilter::GetCumulPiecewiseLinearCost(
1360 if (node < cumul_piecewise_linear_costs_.size()) {
1361 const PiecewiseLinearFunction* cost = cumul_piecewise_linear_costs_[node];
1362 if (cost !=
nullptr) {
1369int64_t PathCumulFilter::GetCumulSoftLowerBoundCost(int64_t node,
1371 if (node < cumul_soft_lower_bounds_.size()) {
1372 const int64_t
bound = cumul_soft_lower_bounds_[node].bound;
1373 const int64_t
coefficient = cumul_soft_lower_bounds_[node].coefficient;
1381int64_t PathCumulFilter::GetPathCumulSoftLowerBoundCost(
1382 const PathTransits& path_transits,
int path)
const {
1383 int64_t node = path_transits.Node(path, path_transits.PathSize(path) - 1);
1384 int64_t cumul =
cumuls_[node]->Max();
1385 int64_t current_cumul_cost_value = GetCumulSoftLowerBoundCost(node, cumul);
1386 for (
int i = path_transits.PathSize(path) - 2;
i >= 0; --
i) {
1387 node = path_transits.Node(path, i);
1388 cumul =
CapSub(cumul, path_transits.Transit(path, i));
1389 cumul = std::min(cumuls_[node]->Max(), cumul);
1390 current_cumul_cost_value =
CapAdd(current_cumul_cost_value,
1391 GetCumulSoftLowerBoundCost(node, cumul));
1393 return current_cumul_cost_value;
1396void PathCumulFilter::OnBeforeSynchronizePaths() {
1397 total_current_cumul_cost_value_ = 0;
1398 cumul_cost_delta_ = 0;
1399 current_cumul_cost_values_.clear();
1400 if (NumPaths() > 0 &&
1401 (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1402 FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1403 FilterPrecedences() || FilterSoftSpanCost() ||
1404 FilterSoftSpanQuadraticCost())) {
1405 InitializeSupportedPathCumul(¤t_min_start_,
1406 std::numeric_limits<int64_t>::max());
1407 InitializeSupportedPathCumul(¤t_max_end_,
1408 std::numeric_limits<int64_t>::min());
1409 current_path_transits_.Clear();
1410 current_path_transits_.AddPaths(NumPaths());
1412 for (
int r = 0; r < NumPaths(); ++r) {
1413 int64_t node = Start(r);
1414 const int vehicle = start_to_vehicle_[Start(r)];
1417 int number_of_route_arcs = 0;
1418 while (node < Size()) {
1419 ++number_of_route_arcs;
1422 current_path_transits_.ReserveTransits(r, number_of_route_arcs);
1425 int64_t cumul =
cumuls_[node]->Min();
1426 min_path_cumuls_.clear();
1427 min_path_cumuls_.push_back(cumul);
1429 int64_t current_cumul_cost_value = GetCumulSoftCost(node, cumul);
1430 current_cumul_cost_value =
CapAdd(
1431 current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1433 int64_t total_transit = 0;
1434 while (node < Size()) {
1436 const int64_t transit = (*evaluators_[vehicle])(node,
next);
1437 total_transit =
CapAdd(total_transit, transit);
1438 const int64_t transit_slack =
CapAdd(transit, slacks_[node]->Min());
1439 current_path_transits_.PushTransit(r, node,
next, transit_slack);
1440 cumul =
CapAdd(cumul, transit_slack);
1442 dimension_.GetFirstPossibleGreaterOrEqualValueForNode(
next, cumul);
1443 cumul = std::max(cumuls_[
next]->Min(), cumul);
1444 min_path_cumuls_.push_back(cumul);
1446 current_cumul_cost_value =
1447 CapAdd(current_cumul_cost_value, GetCumulSoftCost(node, cumul));
1448 current_cumul_cost_value =
CapAdd(
1449 current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1451 if (FilterPrecedences()) {
1452 StoreMinMaxCumulOfNodesOnPath(r, min_path_cumuls_,
1455 if (number_of_route_arcs == 1 &&
1456 !routing_model_.IsVehicleUsedWhenEmpty(vehicle)) {
1459 current_cumul_cost_values_[Start(r)] = 0;
1460 current_path_transits_.ClearPath(r);
1463 if (FilterSlackCost() || FilterSoftSpanCost() ||
1464 FilterSoftSpanQuadraticCost()) {
1465 const int64_t
start = ComputePathMaxStartFromEndCumul(
1466 current_path_transits_, r, Start(r), cumul);
1467 const int64_t span_lower_bound =
CapSub(cumul,
start);
1468 if (FilterSlackCost()) {
1469 current_cumul_cost_value =
1470 CapAdd(current_cumul_cost_value,
1471 CapProd(vehicle_total_slack_cost_coefficients_[vehicle],
1472 CapSub(span_lower_bound, total_transit)));
1474 if (FilterSoftSpanCost()) {
1475 const BoundCost bound_cost =
1476 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1477 if (bound_cost.bound < span_lower_bound) {
1478 const int64_t violation =
1479 CapSub(span_lower_bound, bound_cost.bound);
1480 current_cumul_cost_value =
CapAdd(
1481 current_cumul_cost_value,
CapProd(bound_cost.cost, violation));
1484 if (FilterSoftSpanQuadraticCost()) {
1485 const BoundCost bound_cost =
1486 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1487 if (bound_cost.bound < span_lower_bound) {
1488 const int64_t violation =
1489 CapSub(span_lower_bound, bound_cost.bound);
1490 current_cumul_cost_value =
1491 CapAdd(current_cumul_cost_value,
1496 if (FilterCumulSoftLowerBounds()) {
1497 current_cumul_cost_value =
1498 CapAdd(current_cumul_cost_value,
1499 GetPathCumulSoftLowerBoundCost(current_path_transits_, r));
1501 if (FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1504 int64_t lp_cumul_cost_value = 0;
1505 LocalDimensionCumulOptimizer*
const optimizer =
1506 FilterBreakCost(vehicle) ? mp_optimizer_ : optimizer_;
1507 DCHECK(optimizer !=
nullptr);
1509 optimizer->ComputeRouteCumulCostWithoutFixedTransits(
1510 vehicle, path_accessor_,
1511 filter_objective_cost_ ? &lp_cumul_cost_value : nullptr);
1513 case DimensionSchedulingStatus::INFEASIBLE:
1514 lp_cumul_cost_value = 0;
1516 case DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY:
1517 DCHECK(mp_optimizer_ !=
nullptr);
1518 if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1519 vehicle, path_accessor_,
1520 filter_objective_cost_ ? &lp_cumul_cost_value : nullptr) ==
1522 lp_cumul_cost_value = 0;
1526 DCHECK(
status == DimensionSchedulingStatus::OPTIMAL);
1528 current_cumul_cost_value =
1529 std::max(current_cumul_cost_value, lp_cumul_cost_value);
1531 current_cumul_cost_values_[Start(r)] = current_cumul_cost_value;
1532 current_max_end_.path_values[r] = cumul;
1533 if (current_max_end_.cumul_value < cumul) {
1534 current_max_end_.cumul_value = cumul;
1535 current_max_end_.cumul_value_support = r;
1537 total_current_cumul_cost_value_ =
1538 CapAdd(total_current_cumul_cost_value_, current_cumul_cost_value);
1540 if (FilterPrecedences()) {
1542 for (int64_t node : GetNewSynchronizedUnperformedNodes()) {
1543 current_min_max_node_cumuls_[node] = {-1, -1};
1548 for (
int r = 0; r < NumPaths(); ++r) {
1549 const int64_t
start = ComputePathMaxStartFromEndCumul(
1550 current_path_transits_, r, Start(r), current_max_end_.cumul_value);
1551 current_min_start_.path_values[r] =
start;
1552 if (current_min_start_.cumul_value >
start) {
1553 current_min_start_.cumul_value =
start;
1554 current_min_start_.cumul_value_support = r;
1559 delta_max_end_cumul_ = std::numeric_limits<int64_t>::min();
1561 DCHECK(global_span_cost_coefficient_ == 0 ||
1562 current_min_start_.cumul_value <= current_max_end_.cumul_value);
1563 synchronized_objective_value_ =
1564 CapAdd(total_current_cumul_cost_value_,
1565 CapProd(global_span_cost_coefficient_,
1566 CapSub(current_max_end_.cumul_value,
1567 current_min_start_.cumul_value)));
1570bool PathCumulFilter::AcceptPath(int64_t path_start, int64_t ,
1572 int64_t node = path_start;
1573 int64_t cumul =
cumuls_[node]->Min();
1574 int64_t cumul_cost_delta = 0;
1575 int64_t total_transit = 0;
1576 const int path = delta_path_transits_.AddPaths(1);
1577 const int vehicle = start_to_vehicle_[path_start];
1578 const int64_t capacity = vehicle_capacities_[vehicle];
1579 const bool filter_vehicle_costs =
1580 !routing_model_.IsEnd(GetNext(node)) ||
1581 routing_model_.IsVehicleUsedWhenEmpty(vehicle);
1582 if (filter_vehicle_costs) {
1583 cumul_cost_delta =
CapAdd(GetCumulSoftCost(node, cumul),
1584 GetCumulPiecewiseLinearCost(node, cumul));
1587 int number_of_route_arcs = 0;
1588 while (node < Size()) {
1589 ++number_of_route_arcs;
1590 node = GetNext(node);
1591 DCHECK_NE(node, kUnassigned);
1593 delta_path_transits_.ReserveTransits(path, number_of_route_arcs);
1594 min_path_cumuls_.clear();
1595 min_path_cumuls_.push_back(cumul);
1600 while (node < Size()) {
1601 const int64_t
next = GetNext(node);
1602 const int64_t transit = (*evaluators_[vehicle])(node,
next);
1603 total_transit =
CapAdd(total_transit, transit);
1604 const int64_t transit_slack =
CapAdd(transit, slacks_[node]->Min());
1605 delta_path_transits_.PushTransit(path, node,
next, transit_slack);
1606 cumul =
CapAdd(cumul, transit_slack);
1607 cumul = dimension_.GetFirstPossibleGreaterOrEqualValueForNode(
next, cumul);
1608 if (cumul > std::min(capacity, cumuls_[
next]->Max())) {
1611 cumul = std::max(cumuls_[
next]->Min(), cumul);
1612 min_path_cumuls_.push_back(cumul);
1614 if (filter_vehicle_costs) {
1616 CapAdd(cumul_cost_delta, GetCumulSoftCost(node, cumul));
1618 CapAdd(cumul_cost_delta, GetCumulPiecewiseLinearCost(node, cumul));
1621 const int64_t min_end = cumul;
1623 if (!PickupToDeliveryLimitsRespected(delta_path_transits_, path,
1624 min_path_cumuls_)) {
1627 if (FilterSlackCost() || FilterBreakCost(vehicle) ||
1628 FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1629 int64_t slack_max = std::numeric_limits<int64_t>::max();
1630 if (vehicle_span_upper_bounds_[vehicle] <
1631 std::numeric_limits<int64_t>::max()) {
1632 const int64_t span_max = vehicle_span_upper_bounds_[vehicle];
1633 slack_max = std::min(slack_max,
CapSub(span_max, total_transit));
1635 const int64_t max_start_from_min_end = ComputePathMaxStartFromEndCumul(
1636 delta_path_transits_, path, path_start, min_end);
1637 const int64_t span_lb =
CapSub(min_end, max_start_from_min_end);
1638 int64_t min_total_slack =
CapSub(span_lb, total_transit);
1639 if (min_total_slack > slack_max)
return false;
1641 if (dimension_.HasBreakConstraints()) {
1642 for (
const auto [limit, min_break_duration] :
1643 dimension_.GetBreakDistanceDurationOfVehicle(vehicle)) {
1648 if (limit == 0 || total_transit == 0)
continue;
1649 const int num_breaks_lb = (total_transit - 1) / limit;
1650 const int64_t slack_lb =
CapProd(num_breaks_lb, min_break_duration);
1651 if (slack_lb > slack_max)
return false;
1652 min_total_slack = std::max(min_total_slack, slack_lb);
1658 int64_t min_total_break = 0;
1659 int64_t max_path_end =
cumuls_[routing_model_.End(vehicle)]->Max();
1660 const int64_t max_start = ComputePathMaxStartFromEndCumul(
1661 delta_path_transits_, path, path_start, max_path_end);
1662 for (
const IntervalVar* br :
1663 dimension_.GetBreakIntervalsOfVehicle(vehicle)) {
1664 if (!br->MustBePerformed())
continue;
1665 if (max_start < br->EndMin() && br->StartMax() < min_end) {
1666 min_total_break =
CapAdd(min_total_break, br->DurationMin());
1669 if (min_total_break > slack_max)
return false;
1670 min_total_slack = std::max(min_total_slack, min_total_break);
1672 if (filter_vehicle_costs) {
1675 CapProd(vehicle_total_slack_cost_coefficients_[vehicle],
1677 const int64_t span_lower_bound =
CapAdd(total_transit, min_total_slack);
1678 if (FilterSoftSpanCost()) {
1679 const BoundCost bound_cost =
1680 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1681 if (bound_cost.bound < span_lower_bound) {
1682 const int64_t violation =
CapSub(span_lower_bound, bound_cost.bound);
1684 CapAdd(cumul_cost_delta,
CapProd(bound_cost.cost, violation));
1687 if (FilterSoftSpanQuadraticCost()) {
1688 const BoundCost bound_cost =
1689 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1690 if (bound_cost.bound < span_lower_bound) {
1691 const int64_t violation =
CapSub(span_lower_bound, bound_cost.bound);
1698 if (
CapAdd(total_transit, min_total_slack) >
1699 vehicle_span_upper_bounds_[vehicle]) {
1703 if (FilterCumulSoftLowerBounds() && filter_vehicle_costs) {
1706 GetPathCumulSoftLowerBoundCost(delta_path_transits_, path));
1708 if (FilterPrecedences()) {
1709 StoreMinMaxCumulOfNodesOnPath(path, min_path_cumuls_,
true);
1711 if (!filter_vehicle_costs) {
1714 cumul_cost_delta = 0;
1715 delta_path_transits_.ClearPath(path);
1717 if (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1718 FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1719 FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1720 delta_paths_.insert(GetPath(path_start));
1721 delta_path_cumul_cost_values_[vehicle] = cumul_cost_delta;
1723 CapSub(cumul_cost_delta, current_cumul_cost_values_[path_start]);
1724 if (filter_vehicle_costs) {
1725 delta_max_end_cumul_ = std::max(delta_max_end_cumul_, min_end);
1728 cumul_cost_delta_ =
CapAdd(cumul_cost_delta_, cumul_cost_delta);
1732bool PathCumulFilter::FinalizeAcceptPath(int64_t ,
1733 int64_t objective_max) {
1734 DCHECK(!lns_detected());
1735 if (!FilterSpanCost() && !FilterCumulSoftBounds() && !FilterSlackCost() &&
1736 !FilterCumulSoftLowerBounds() && !FilterCumulPiecewiseLinearCosts() &&
1737 !FilterPrecedences() && !FilterSoftSpanCost() &&
1738 !FilterSoftSpanQuadraticCost()) {
1741 if (FilterPrecedences()) {
1742 for (int64_t node : delta_nodes_with_precedences_and_changed_cumul_
1743 .PositionsSetAtLeastOnce()) {
1744 const std::pair<int64_t, int64_t> node_min_max_cumul_in_delta =
1749 DCHECK(node_min_max_cumul_in_delta.first >= 0 &&
1750 node_min_max_cumul_in_delta.second >= 0);
1751 for (
const RoutingDimension::NodePrecedence& precedence :
1752 node_index_to_precedences_[node]) {
1753 const bool node_is_first = (precedence.first_node == node);
1754 const int64_t other_node =
1755 node_is_first ? precedence.second_node : precedence.first_node;
1756 if (GetNext(other_node) == kUnassigned ||
1757 GetNext(other_node) == other_node) {
1764 const std::pair<int64_t, int64_t>& other_min_max_cumul_in_delta =
1767 current_min_max_node_cumuls_[other_node]);
1769 const int64_t first_min_cumul =
1770 node_is_first ? node_min_max_cumul_in_delta.first
1771 : other_min_max_cumul_in_delta.first;
1772 const int64_t second_max_cumul =
1773 node_is_first ? other_min_max_cumul_in_delta.second
1774 : node_min_max_cumul_in_delta.second;
1776 if (second_max_cumul < first_min_cumul + precedence.offset) {
1782 int64_t new_max_end = delta_max_end_cumul_;
1783 int64_t new_min_start = std::numeric_limits<int64_t>::max();
1784 if (FilterSpanCost()) {
1785 if (new_max_end < current_max_end_.cumul_value) {
1789 if (!delta_paths_.contains(current_max_end_.cumul_value_support)) {
1790 new_max_end = current_max_end_.cumul_value;
1792 for (
int i = 0;
i < current_max_end_.path_values.size(); ++
i) {
1793 if (current_max_end_.path_values[i] > new_max_end &&
1794 !delta_paths_.contains(i)) {
1795 new_max_end = current_max_end_.path_values[
i];
1803 for (
int r = 0; r < delta_path_transits_.NumPaths(); ++r) {
1805 std::min(ComputePathMaxStartFromEndCumul(delta_path_transits_, r,
1806 Start(r), new_max_end),
1809 if (new_max_end != current_max_end_.cumul_value) {
1810 for (
int r = 0; r < NumPaths(); ++r) {
1811 if (delta_paths_.contains(r)) {
1814 new_min_start = std::min(new_min_start, ComputePathMaxStartFromEndCumul(
1815 current_path_transits_, r,
1816 Start(r), new_max_end));
1818 }
else if (new_min_start > current_min_start_.cumul_value) {
1822 if (!delta_paths_.contains(current_min_start_.cumul_value_support)) {
1823 new_min_start = current_min_start_.cumul_value;
1825 for (
int i = 0;
i < current_min_start_.path_values.size(); ++
i) {
1826 if (current_min_start_.path_values[i] < new_min_start &&
1827 !delta_paths_.contains(i)) {
1828 new_min_start = current_min_start_.path_values[
i];
1836 accepted_objective_value_ =
1837 CapAdd(cumul_cost_delta_,
CapProd(global_span_cost_coefficient_,
1838 CapSub(new_max_end, new_min_start)));
1840 if (can_use_lp_ && optimizer_ !=
nullptr &&
1841 accepted_objective_value_ <= objective_max) {
1842 const size_t num_touched_paths = GetTouchedPathStarts().size();
1843 std::vector<int64_t> path_delta_cost_values(num_touched_paths, 0);
1844 std::vector<bool> requires_mp(num_touched_paths,
false);
1845 for (
int i = 0;
i < num_touched_paths; ++
i) {
1846 const int64_t
start = GetTouchedPathStarts()[
i];
1847 const int vehicle = start_to_vehicle_[
start];
1848 if (!FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1851 int64_t path_delta_cost_with_lp = 0;
1853 optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1854 vehicle, path_accessor_,
1855 filter_objective_cost_ ? &path_delta_cost_with_lp : nullptr);
1856 if (
status == DimensionSchedulingStatus::INFEASIBLE) {
1859 DCHECK(delta_paths_.contains(GetPath(
start)));
1860 const int64_t path_cost_diff_with_lp =
CapSub(
1861 path_delta_cost_with_lp, delta_path_cumul_cost_values_[vehicle]);
1862 if (path_cost_diff_with_lp > 0) {
1863 path_delta_cost_values[
i] = path_delta_cost_with_lp;
1864 accepted_objective_value_ =
1865 CapAdd(accepted_objective_value_, path_cost_diff_with_lp);
1866 if (accepted_objective_value_ > objective_max) {
1870 path_delta_cost_values[
i] = delta_path_cumul_cost_values_[vehicle];
1872 DCHECK_NE(mp_optimizer_,
nullptr);
1874 FilterBreakCost(vehicle) ||
1875 (
status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY);
1878 DCHECK_LE(accepted_objective_value_, objective_max);
1880 for (
int i = 0;
i < num_touched_paths; ++
i) {
1881 if (!requires_mp[i]) {
1884 const int64_t
start = GetTouchedPathStarts()[
i];
1885 const int vehicle = start_to_vehicle_[
start];
1886 int64_t path_delta_cost_with_mp = 0;
1887 if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1888 vehicle, path_accessor_,
1889 filter_objective_cost_ ? &path_delta_cost_with_mp : nullptr) ==
1893 DCHECK(delta_paths_.contains(GetPath(
start)));
1894 const int64_t path_cost_diff_with_mp =
1895 CapSub(path_delta_cost_with_mp, path_delta_cost_values[i]);
1896 if (path_cost_diff_with_mp > 0) {
1897 accepted_objective_value_ =
1898 CapAdd(accepted_objective_value_, path_cost_diff_with_mp);
1899 if (accepted_objective_value_ > objective_max) {
1906 return accepted_objective_value_ <= objective_max;
1909void PathCumulFilter::InitializeSupportedPathCumul(
1910 SupportedPathCumul* supported_cumul, int64_t default_value) {
1911 supported_cumul->cumul_value = default_value;
1912 supported_cumul->cumul_value_support = -1;
1913 supported_cumul->path_values.resize(NumPaths(), default_value);
1916bool PathCumulFilter::PickupToDeliveryLimitsRespected(
1917 const PathTransits& path_transits,
int path,
1918 absl::Span<const int64_t> min_path_cumuls)
const {
1919 if (!dimension_.HasPickupToDeliveryLimits()) {
1922 const int num_pairs = routing_model_.GetPickupAndDeliveryPairs().size();
1923 DCHECK_GT(num_pairs, 0);
1924 std::vector<std::pair<int, int64_t>> visited_delivery_and_min_cumul_per_pair(
1925 num_pairs, {-1, -1});
1927 const int path_size = path_transits.PathSize(path);
1928 CHECK_EQ(min_path_cumuls.size(), path_size);
1930 int64_t max_cumul = min_path_cumuls.back();
1931 for (
int i = path_transits.PathSize(path) - 2;
i >= 0;
i--) {
1932 const int node_index = path_transits.Node(path, i);
1933 max_cumul =
CapSub(max_cumul, path_transits.Transit(path, i));
1934 max_cumul = std::min(cumuls_[node_index]->Max(), max_cumul);
1936 const std::vector<RoutingModel::PickupDeliveryPosition>& pickup_positions =
1937 routing_model_.GetPickupPositions(node_index);
1938 const std::vector<RoutingModel::PickupDeliveryPosition>&
1939 delivery_positions = routing_model_.GetDeliveryPositions(node_index);
1940 if (!pickup_positions.empty()) {
1944 DCHECK(delivery_positions.empty());
1945 DCHECK_EQ(pickup_positions.size(), 1);
1946 const auto [pair_index, pickup_alternative_index] = pickup_positions[0];
1948 const int delivery_alternative_index =
1949 visited_delivery_and_min_cumul_per_pair[pair_index].first;
1950 if (delivery_alternative_index < 0) {
1954 const int64_t cumul_diff_limit =
1955 dimension_.GetPickupToDeliveryLimitForPair(
1956 pair_index, pickup_alternative_index, delivery_alternative_index);
1957 if (
CapSub(visited_delivery_and_min_cumul_per_pair[pair_index].second,
1958 max_cumul) > cumul_diff_limit) {
1962 if (!delivery_positions.empty()) {
1965 DCHECK(pickup_positions.empty());
1966 DCHECK_EQ(delivery_positions.size(), 1);
1967 const auto [pair_index, delivery_alternative_index] =
1968 delivery_positions[0];
1969 std::pair<int, int64_t>& delivery_index_and_cumul =
1970 visited_delivery_and_min_cumul_per_pair[pair_index];
1971 int& delivery_index = delivery_index_and_cumul.first;
1972 DCHECK_EQ(delivery_index, -1);
1973 delivery_index = delivery_alternative_index;
1974 delivery_index_and_cumul.second = min_path_cumuls[
i];
1980void PathCumulFilter::StoreMinMaxCumulOfNodesOnPath(
1981 int path, absl::Span<const int64_t> min_path_cumuls,
bool is_delta) {
1982 const PathTransits& path_transits =
1983 is_delta ? delta_path_transits_ : current_path_transits_;
1985 const int path_size = path_transits.PathSize(path);
1986 DCHECK_EQ(min_path_cumuls.size(), path_size);
1988 int64_t max_cumul =
cumuls_[path_transits.Node(path, path_size - 1)]->Max();
1989 for (
int i = path_size - 1;
i >= 0;
i--) {
1990 const int node_index = path_transits.Node(path, i);
1992 if (i < path_size - 1) {
1993 max_cumul =
CapSub(max_cumul, path_transits.Transit(path, i));
1994 max_cumul = std::min(cumuls_[node_index]->Max(), max_cumul);
1997 if (is_delta && node_index_to_precedences_[node_index].empty()) {
2002 std::pair<int64_t, int64_t>& min_max_cumuls =
2003 is_delta ? node_with_precedence_to_delta_min_max_cumuls_[node_index]
2004 : current_min_max_node_cumuls_[node_index];
2005 min_max_cumuls.first = min_path_cumuls[
i];
2006 min_max_cumuls.second = max_cumul;
2008 if (is_delta && !routing_model_.IsEnd(node_index) &&
2009 (min_max_cumuls.first !=
2010 current_min_max_node_cumuls_[node_index].first ||
2011 max_cumul != current_min_max_node_cumuls_[node_index].second)) {
2012 delta_nodes_with_precedences_and_changed_cumul_.
Set(node_index);
2017int64_t PathCumulFilter::ComputePathMaxStartFromEndCumul(
2018 const PathTransits& path_transits,
int path, int64_t path_start,
2019 int64_t min_end_cumul)
const {
2020 int64_t cumul_from_min_end = min_end_cumul;
2021 int64_t cumul_from_max_end =
2022 cumuls_[routing_model_.End(start_to_vehicle_[path_start])]->Max();
2023 for (
int i = path_transits.PathSize(path) - 2;
i >= 0; --
i) {
2024 const int64_t transit = path_transits.Transit(path, i);
2025 const int64_t node = path_transits.Node(path, i);
2026 cumul_from_min_end =
2027 std::min(cumuls_[node]->Max(),
CapSub(cumul_from_min_end, transit));
2028 cumul_from_max_end = dimension_.GetLastPossibleLessOrEqualValueForNode(
2029 node,
CapSub(cumul_from_max_end, transit));
2031 return std::min(cumul_from_min_end, cumul_from_max_end);
2037 bool propagate_own_objective_value,
2038 bool filter_objective_cost,
2040 RoutingModel&
model = *dimension.model();
2041 return model.solver()->RevAlloc(
2042 new PathCumulFilter(
model, dimension, propagate_own_objective_value,
2043 filter_objective_cost, can_use_lp));
2048bool DimensionHasCumulCost(
const RoutingDimension& dimension) {
2049 if (dimension.global_span_cost_coefficient() != 0)
return true;
2050 if (dimension.HasSoftSpanUpperBounds())
return true;
2051 if (dimension.HasQuadraticCostSoftSpanUpperBounds())
return true;
2052 if (absl::c_any_of(dimension.vehicle_span_cost_coefficients(),
2053 [](int64_t
coefficient) { return coefficient != 0; })) {
2056 if (absl::c_any_of(dimension.vehicle_slack_cost_coefficients(),
2057 [](int64_t
coefficient) { return coefficient != 0; })) {
2060 for (
int i = 0;
i < dimension.cumuls().size(); ++
i) {
2061 if (dimension.HasCumulVarSoftUpperBound(i))
return true;
2062 if (dimension.HasCumulVarSoftLowerBound(i))
return true;
2063 if (dimension.HasCumulVarPiecewiseLinearCost(i))
return true;
2068bool DimensionHasPathCumulConstraint(
const RoutingDimension& dimension) {
2069 if (dimension.HasBreakConstraints())
return true;
2070 if (dimension.HasPickupToDeliveryLimits())
return true;
2072 dimension.vehicle_span_upper_bounds(), [](int64_t
upper_bound) {
2073 return upper_bound != std::numeric_limits<int64_t>::max();
2077 if (absl::c_any_of(dimension.slacks(),
2078 [](IntVar* slack) { return slack->Min() > 0; })) {
2081 const std::vector<IntVar*>& cumuls = dimension.cumuls();
2082 for (
int i = 0;
i < cumuls.size(); ++
i) {
2083 IntVar*
const cumul_var = cumuls[
i];
2084 if (cumul_var->Min() > 0 &&
2085 cumul_var->Max() < std::numeric_limits<int64_t>::max() &&
2086 !dimension.model()->IsEnd(i)) {
2089 if (dimension.forbidden_intervals()[i].NumIntervals() > 0)
return true;
2098 const std::vector<RoutingDimension*>&
dimensions,
2099 std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2103 for (
const RoutingDimension* dimension :
dimensions) {
2105 const int num_vehicles = dimension->model()->vehicles();
2106 std::vector<Interval> path_capacity(num_vehicles);
2107 std::vector<int> path_class(num_vehicles);
2108 for (
int v = 0; v < num_vehicles; ++v) {
2109 const auto& vehicle_capacities = dimension->vehicle_capacities();
2110 path_capacity[v] = {0, vehicle_capacities[v]};
2111 path_class[v] = dimension->vehicle_to_class(v);
2118 const int num_vehicle_classes =
2119 1 + *std::max_element(path_class.begin(), path_class.end());
2120 const int num_cumuls = dimension->cumuls().size();
2121 const int num_slacks = dimension->slacks().size();
2122 std::vector<std::function<Interval(int64_t, int64_t)>> transits(
2123 num_vehicle_classes,
nullptr);
2124 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
2127 const auto& unary_evaluator =
2128 dimension->GetUnaryTransitEvaluator(vehicle);
2129 if (unary_evaluator !=
nullptr) {
2130 transits[
vehicle_class] = [&unary_evaluator, dimension, num_slacks](
2131 int64_t node, int64_t) -> Interval {
2132 if (node >= num_slacks)
return {0, 0};
2133 const int64_t min_transit = unary_evaluator(node);
2134 const int64_t max_transit =
2135 CapAdd(min_transit, dimension->SlackVar(node)->Max());
2136 return {min_transit, max_transit};
2139 const auto& binary_evaluator =
2140 dimension->GetBinaryTransitEvaluator(vehicle);
2142 transits[
vehicle_class] = [&binary_evaluator, dimension, num_slacks](
2143 int64_t node, int64_t
next) -> Interval {
2144 if (node >= num_slacks)
return {0, 0};
2145 const int64_t min_transit = binary_evaluator(node,
next);
2146 const int64_t max_transit =
2147 CapAdd(min_transit, dimension->SlackVar(node)->Max());
2148 return {min_transit, max_transit};
2153 std::vector<Interval> node_capacity(num_cumuls);
2154 for (
int node = 0; node < num_cumuls; ++node) {
2155 const IntVar* cumul = dimension->CumulVar(node);
2156 node_capacity[node] = {cumul->
Min(), cumul->
Max()};
2159 auto checker = std::make_unique<DimensionChecker>(
2160 path_state, std::move(path_capacity), std::move(path_class),
2161 std::move(transits), std::move(node_capacity));
2162 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2164 dimension->model()->solver(), std::move(checker), dimension->name());
2165 filters->push_back({filter, kAccept});
2170 const std::vector<RoutingDimension*>&
dimensions,
2171 const RoutingSearchParameters&
parameters,
bool filter_objective_cost,
2172 bool use_chain_cumul_filter,
2173 std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2174 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2182 const int num_dimensions =
dimensions.size();
2184 const bool has_dimension_optimizers =
2185 !
parameters.disable_scheduling_beware_this_may_degrade_performance();
2186 std::vector<bool> use_path_cumul_filter(num_dimensions);
2187 std::vector<bool> use_cumul_bounds_propagator_filter(num_dimensions);
2188 std::vector<bool> use_global_lp_filter(num_dimensions);
2189 std::vector<bool> use_resource_assignment_filter(num_dimensions);
2190 for (
int d = 0; d < num_dimensions; d++) {
2191 const RoutingDimension& dimension = *
dimensions[d];
2192 const bool has_cumul_cost = DimensionHasCumulCost(dimension);
2193 use_path_cumul_filter[d] =
2194 has_cumul_cost || DimensionHasPathCumulConstraint(dimension);
2196 const int num_dimension_resource_groups =
2197 dimension.model()->GetDimensionResourceGroupIndices(&dimension).size();
2198 const bool can_use_cumul_bounds_propagator_filter =
2199 !dimension.HasBreakConstraints() &&
2200 num_dimension_resource_groups == 0 &&
2201 (!filter_objective_cost || !has_cumul_cost);
2202 const bool has_precedences = !dimension.GetNodePrecedences().empty();
2203 use_global_lp_filter[d] =
2204 has_dimension_optimizers &&
2205 ((has_precedences && !can_use_cumul_bounds_propagator_filter) ||
2206 (filter_objective_cost &&
2207 dimension.global_span_cost_coefficient() > 0) ||
2208 num_dimension_resource_groups > 1);
2210 use_cumul_bounds_propagator_filter[d] =
2211 has_precedences && !use_global_lp_filter[d];
2213 use_resource_assignment_filter[d] =
2214 has_dimension_optimizers && num_dimension_resource_groups > 0;
2217 for (
int d = 0; d < num_dimensions; d++) {
2218 const RoutingDimension& dimension = *
dimensions[d];
2219 const RoutingModel&
model = *dimension.model();
2224 const bool use_global_lp = use_global_lp_filter[d];
2225 const bool filter_resource_assignment = use_resource_assignment_filter[d];
2226 if (use_path_cumul_filter[d]) {
2229 !use_global_lp && !filter_resource_assignment,
2230 filter_objective_cost, has_dimension_optimizers),
2232 }
else if (use_chain_cumul_filter) {
2234 {
model.solver()->RevAlloc(
new ChainCumulFilter(
model, dimension)),
2238 if (use_cumul_bounds_propagator_filter[d]) {
2239 DCHECK(!use_global_lp);
2240 DCHECK(!filter_resource_assignment);
2245 if (filter_resource_assignment) {
2247 model.GetMutableLocalCumulLPOptimizer(dimension),
2248 model.GetMutableLocalCumulMPOptimizer(dimension),
2250 filter_objective_cost),
2254 if (use_global_lp) {
2256 model.GetMutableGlobalCumulLPOptimizer(dimension),
2257 model.GetMutableGlobalCumulMPOptimizer(dimension),
2258 filter_objective_cost),
2267class PickupDeliveryFilter :
public BasePathFilter {
2269 PickupDeliveryFilter(
const std::vector<IntVar*>& nexts,
int next_domain_size,
2270 const std::vector<PickupDeliveryPair>& pairs,
2271 const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2273 ~PickupDeliveryFilter()
override {}
2274 bool AcceptPath(int64_t path_start, int64_t chain_start,
2275 int64_t chain_end)
override;
2276 std::string DebugString()
const override {
return "PickupDeliveryFilter"; }
2279 bool AcceptPathDefault(int64_t path_start);
2280 template <
bool lifo>
2281 bool AcceptPathOrdered(int64_t path_start);
2283 std::vector<int> pair_firsts_;
2284 std::vector<int> pair_seconds_;
2285 const std::vector<PickupDeliveryPair> pairs_;
2286 SparseBitset<> visited_;
2287 std::deque<int> visited_deque_;
2288 const std::vector<RoutingModel::PickupAndDeliveryPolicy> vehicle_policies_;
2291PickupDeliveryFilter::PickupDeliveryFilter(
2292 const std::vector<IntVar*>& nexts,
int next_domain_size,
2293 const std::vector<PickupDeliveryPair>& pairs,
2294 const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies)
2295 : BasePathFilter(nexts, next_domain_size),
2296 pair_firsts_(next_domain_size, kUnassigned),
2297 pair_seconds_(next_domain_size, kUnassigned),
2300 vehicle_policies_(vehicle_policies) {
2301 for (
int i = 0;
i < pairs.size(); ++
i) {
2302 const auto& index_pair = pairs[
i];
2303 for (
int first : index_pair.pickup_alternatives) {
2304 pair_firsts_[first] =
i;
2306 for (
int second : index_pair.delivery_alternatives) {
2307 pair_seconds_[second] =
i;
2312bool PickupDeliveryFilter::AcceptPath(int64_t path_start,
2315 switch (vehicle_policies_[GetPath(path_start)]) {
2316 case RoutingModel::PICKUP_AND_DELIVERY_NO_ORDER:
2317 return AcceptPathDefault(path_start);
2318 case RoutingModel::PICKUP_AND_DELIVERY_LIFO:
2319 return AcceptPathOrdered<true>(path_start);
2320 case RoutingModel::PICKUP_AND_DELIVERY_FIFO:
2321 return AcceptPathOrdered<false>(path_start);
2327bool PickupDeliveryFilter::AcceptPathDefault(int64_t path_start) {
2328 visited_.ClearAll();
2329 int64_t node = path_start;
2330 int64_t path_length = 1;
2331 while (node < Size()) {
2333 if (path_length > Size()) {
2336 if (pair_firsts_[node] != kUnassigned) {
2340 for (
int second : pairs_[pair_firsts_[node]].delivery_alternatives) {
2341 if (visited_[second]) {
2346 if (pair_seconds_[node] != kUnassigned) {
2347 bool found_first =
false;
2348 bool some_synced =
false;
2349 for (
int first : pairs_[pair_seconds_[node]].pickup_alternatives) {
2350 if (visited_[first]) {
2354 if (IsVarSynced(first)) {
2358 if (!found_first && some_synced) {
2363 const int64_t
next = GetNext(node);
2364 if (
next == kUnassigned) {
2371 for (
const int64_t node : visited_.PositionsSetAtLeastOnce()) {
2372 if (pair_firsts_[node] != kUnassigned) {
2373 bool found_second =
false;
2374 bool some_synced =
false;
2375 for (
int second : pairs_[pair_firsts_[node]].delivery_alternatives) {
2376 if (visited_[second]) {
2377 found_second =
true;
2380 if (IsVarSynced(second)) {
2384 if (!found_second && some_synced) {
2393bool PickupDeliveryFilter::AcceptPathOrdered(int64_t path_start) {
2394 visited_deque_.clear();
2395 int64_t node = path_start;
2396 int64_t path_length = 1;
2397 while (node < Size()) {
2399 if (path_length > Size()) {
2402 if (pair_firsts_[node] != kUnassigned) {
2404 visited_deque_.push_back(node);
2406 visited_deque_.push_front(node);
2409 if (pair_seconds_[node] != kUnassigned) {
2410 bool found_first =
false;
2411 bool some_synced =
false;
2412 for (
int first : pairs_[pair_seconds_[node]].pickup_alternatives) {
2413 if (!visited_deque_.empty() && visited_deque_.back() == first) {
2417 if (IsVarSynced(first)) {
2421 if (!found_first && some_synced) {
2423 }
else if (!visited_deque_.empty()) {
2424 visited_deque_.pop_back();
2427 const int64_t
next = GetNext(node);
2428 if (
next == kUnassigned) {
2435 while (!visited_deque_.empty()) {
2437 pairs_[pair_firsts_[visited_deque_.back()]].delivery_alternatives) {
2438 if (IsVarSynced(second)) {
2442 visited_deque_.pop_back();
2450 const RoutingModel& routing_model,
2451 const std::vector<PickupDeliveryPair>& pairs,
2452 const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2454 return routing_model.solver()->RevAlloc(
new PickupDeliveryFilter(
2455 routing_model.Nexts(), routing_model.Size() + routing_model.vehicles(),
2456 pairs, vehicle_policies));
2462class VehicleVarFilter :
public BasePathFilter {
2464 explicit VehicleVarFilter(
const RoutingModel& routing_model);
2465 ~VehicleVarFilter()
override {}
2466 bool AcceptPath(int64_t path_start, int64_t chain_start,
2467 int64_t chain_end)
override;
2468 std::string DebugString()
const override {
return "VehicleVariableFilter"; }
2471 bool DisableFiltering()
const override;
2472 bool IsVehicleVariableConstrained(
int index)
const;
2474 std::vector<int64_t> start_to_vehicle_;
2475 std::vector<IntVar*> vehicle_vars_;
2476 const int64_t unconstrained_vehicle_var_domain_size_;
2477 SparseBitset<int> touched_;
2480VehicleVarFilter::VehicleVarFilter(
const RoutingModel& routing_model)
2481 : BasePathFilter(routing_model.Nexts(),
2482 routing_model.Size() + routing_model.vehicles()),
2483 vehicle_vars_(routing_model.VehicleVars()),
2484 unconstrained_vehicle_var_domain_size_(routing_model.vehicles()),
2485 touched_(routing_model.Nexts().size()) {
2486 start_to_vehicle_.resize(Size(), -1);
2487 for (
int i = 0;
i < routing_model.vehicles(); ++
i) {
2488 start_to_vehicle_[routing_model.Start(i)] =
i;
2492bool VehicleVarFilter::AcceptPath(int64_t path_start, int64_t chain_start,
2493 int64_t chain_end) {
2494 touched_.SparseClearAll();
2495 const int64_t vehicle = start_to_vehicle_[path_start];
2496 int64_t node = chain_start;
2497 while (node != chain_end) {
2498 if (touched_[node] || !vehicle_vars_[node]->Contains(vehicle)) {
2502 node = GetNext(node);
2504 return vehicle_vars_[node]->Contains(vehicle);
2507bool VehicleVarFilter::DisableFiltering()
const {
2508 for (
int i = 0;
i < vehicle_vars_.size(); ++
i) {
2509 if (IsVehicleVariableConstrained(i))
return false;
2514bool VehicleVarFilter::IsVehicleVariableConstrained(
int index)
const {
2515 const IntVar*
const vehicle_var = vehicle_vars_[
index];
2519 const int adjusted_unconstrained_vehicle_var_domain_size =
2520 vehicle_var->Min() >= 0 ? unconstrained_vehicle_var_domain_size_
2521 : unconstrained_vehicle_var_domain_size_ + 1;
2522 return vehicle_var->Size() != adjusted_unconstrained_vehicle_var_domain_size;
2528 const RoutingModel& routing_model) {
2529 return routing_model.solver()->RevAlloc(
new VehicleVarFilter(routing_model));
2534class CumulBoundsPropagatorFilter :
public IntVarLocalSearchFilter {
2536 explicit CumulBoundsPropagatorFilter(
const RoutingDimension& dimension);
2537 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2538 int64_t objective_min, int64_t objective_max)
override;
2539 std::string DebugString()
const override {
2540 return "CumulBoundsPropagatorFilter(" + propagator_.dimension().name() +
2545 CumulBoundsPropagator propagator_;
2546 const int64_t cumul_offset_;
2547 SparseBitset<int64_t> delta_touched_;
2548 std::vector<int64_t> delta_nexts_;
2551CumulBoundsPropagatorFilter::CumulBoundsPropagatorFilter(
2552 const RoutingDimension& dimension)
2553 : IntVarLocalSearchFilter(dimension.
model()->Nexts()),
2554 propagator_(&dimension),
2555 cumul_offset_(dimension.GetGlobalOptimizerOffset()),
2556 delta_touched_(Size()),
2557 delta_nexts_(Size()) {}
2559bool CumulBoundsPropagatorFilter::Accept(
const Assignment*
delta,
2564 for (
const IntVarElement& delta_element :
2565 delta->IntVarContainer().elements()) {
2567 if (FindIndex(delta_element.Var(), &
index)) {
2568 if (!delta_element.Bound()) {
2573 delta_nexts_[
index] = delta_element.Value();
2576 const auto& next_accessor = [
this](int64_t
index) {
2580 return propagator_.PropagateCumulBounds(next_accessor, cumul_offset_);
2586 const RoutingDimension& dimension) {
2587 return dimension.model()->solver()->RevAlloc(
2588 new CumulBoundsPropagatorFilter(dimension));
2593class LPCumulFilter :
public IntVarLocalSearchFilter {
2595 LPCumulFilter(
const std::vector<IntVar*>& nexts,
2596 GlobalDimensionCumulOptimizer* optimizer,
2597 GlobalDimensionCumulOptimizer* mp_optimizer,
2598 bool filter_objective_cost);
2599 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2600 int64_t objective_min, int64_t objective_max)
override;
2601 int64_t GetAcceptedObjectiveValue()
const override;
2602 void OnSynchronize(
const Assignment*
delta)
override;
2603 int64_t GetSynchronizedObjectiveValue()
const override;
2604 std::string DebugString()
const override {
2605 return "LPCumulFilter(" + optimizer_.dimension()->name() +
")";
2609 GlobalDimensionCumulOptimizer& optimizer_;
2610 GlobalDimensionCumulOptimizer& mp_optimizer_;
2611 const bool filter_objective_cost_;
2612 int64_t synchronized_cost_without_transit_;
2613 int64_t delta_cost_without_transit_;
2614 SparseBitset<int64_t> delta_touched_;
2615 std::vector<int64_t> delta_nexts_;
2618LPCumulFilter::LPCumulFilter(
const std::vector<IntVar*>& nexts,
2619 GlobalDimensionCumulOptimizer* optimizer,
2620 GlobalDimensionCumulOptimizer* mp_optimizer,
2621 bool filter_objective_cost)
2622 : IntVarLocalSearchFilter(nexts),
2623 optimizer_(*optimizer),
2624 mp_optimizer_(*mp_optimizer),
2625 filter_objective_cost_(filter_objective_cost),
2626 synchronized_cost_without_transit_(-1),
2627 delta_cost_without_transit_(-1),
2628 delta_touched_(Size()),
2629 delta_nexts_(Size()) {}
2631bool LPCumulFilter::Accept(
const Assignment*
delta,
2633 int64_t , int64_t objective_max) {
2635 for (
const IntVarElement& delta_element :
2636 delta->IntVarContainer().elements()) {
2638 if (FindIndex(delta_element.Var(), &
index)) {
2639 if (!delta_element.Bound()) {
2644 delta_nexts_[
index] = delta_element.Value();
2647 const auto& next_accessor = [
this](int64_t
index) {
2651 if (!filter_objective_cost_) {
2653 delta_cost_without_transit_ = 0;
2655 optimizer_.ComputeCumuls(next_accessor, {},
nullptr,
nullptr,
nullptr);
2656 if (
status == DimensionSchedulingStatus::OPTIMAL)
return true;
2657 if (
status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY &&
2658 mp_optimizer_.ComputeCumuls(next_accessor, {},
nullptr,
nullptr,
2660 DimensionSchedulingStatus::OPTIMAL) {
2667 optimizer_.ComputeCumulCostWithoutFixedTransits(
2668 next_accessor, &delta_cost_without_transit_);
2669 if (
status == DimensionSchedulingStatus::INFEASIBLE) {
2670 delta_cost_without_transit_ = std::numeric_limits<int64_t>::max();
2673 if (delta_cost_without_transit_ > objective_max)
return false;
2675 if (
status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY &&
2676 mp_optimizer_.ComputeCumulCostWithoutFixedTransits(
2677 next_accessor, &delta_cost_without_transit_) !=
2678 DimensionSchedulingStatus::OPTIMAL) {
2679 delta_cost_without_transit_ = std::numeric_limits<int64_t>::max();
2682 return delta_cost_without_transit_ <= objective_max;
2685int64_t LPCumulFilter::GetAcceptedObjectiveValue()
const {
2686 return delta_cost_without_transit_;
2689void LPCumulFilter::OnSynchronize(
const Assignment* ) {
2692 const RoutingModel&
model = *optimizer_.dimension()->model();
2693 const auto& next_accessor = [
this, &
model](int64_t
index) {
2700 optimizer_.ComputeCumulCostWithoutFixedTransits(
2701 next_accessor, &synchronized_cost_without_transit_);
2702 if (
status == DimensionSchedulingStatus::INFEASIBLE) {
2705 synchronized_cost_without_transit_ = 0;
2707 if (
status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY &&
2708 mp_optimizer_.ComputeCumulCostWithoutFixedTransits(
2709 next_accessor, &synchronized_cost_without_transit_) !=
2710 DimensionSchedulingStatus::OPTIMAL) {
2713 synchronized_cost_without_transit_ = 0;
2717int64_t LPCumulFilter::GetSynchronizedObjectiveValue()
const {
2718 return synchronized_cost_without_transit_;
2726 DCHECK_NE(optimizer,
nullptr);
2727 DCHECK_NE(mp_optimizer,
nullptr);
2729 return model.solver()->RevAlloc(
new LPCumulFilter(
2730 model.Nexts(), optimizer, mp_optimizer, filter_objective_cost));
2735using ResourceGroup = RoutingModel::ResourceGroup;
2737class ResourceGroupAssignmentFilter :
public BasePathFilter {
2739 ResourceGroupAssignmentFilter(
const std::vector<IntVar*>& nexts,
2740 const ResourceGroup* resource_group,
2741 LocalDimensionCumulOptimizer* lp_optimizer,
2742 LocalDimensionCumulOptimizer* mp_optimizer,
2743 bool filter_objective_cost);
2744 bool InitializeAcceptPath()
override;
2745 bool AcceptPath(int64_t path_start, int64_t chain_start,
2746 int64_t chain_end)
override;
2747 bool FinalizeAcceptPath(int64_t objective_min,
2748 int64_t objective_max)
override;
2749 void OnBeforeSynchronizePaths()
override;
2750 void OnSynchronizePathFromStart(int64_t
start)
override;
2751 void OnAfterSynchronizePaths()
override;
2753 int64_t GetAcceptedObjectiveValue()
const override {
2754 return lns_detected() ? 0 : delta_cost_without_transit_;
2756 int64_t GetSynchronizedObjectiveValue()
const override {
2757 return synchronized_cost_without_transit_;
2759 std::string DebugString()
const override {
2760 return "ResourceGroupAssignmentFilter(" + dimension_.name() +
")";
2764 const RoutingModel& model_;
2765 const RoutingDimension& dimension_;
2766 const ResourceGroup& resource_group_;
2767 LocalDimensionCumulOptimizer* lp_optimizer_;
2768 LocalDimensionCumulOptimizer* mp_optimizer_;
2769 const bool filter_objective_cost_;
2770 bool current_synch_failed_;
2771 int64_t synchronized_cost_without_transit_;
2772 int64_t delta_cost_without_transit_;
2773 std::vector<std::vector<int64_t>> vehicle_to_resource_class_assignment_costs_;
2774 std::vector<std::vector<int64_t>>
2775 delta_vehicle_to_resource_class_assignment_costs_;
2778ResourceGroupAssignmentFilter::ResourceGroupAssignmentFilter(
2779 const std::vector<IntVar*>& nexts,
const ResourceGroup* resource_group,
2780 LocalDimensionCumulOptimizer* lp_optimizer,
2781 LocalDimensionCumulOptimizer* mp_optimizer,
bool filter_objective_cost)
2782 : BasePathFilter(nexts, lp_optimizer->dimension()->cumuls().size()),
2783 model_(*lp_optimizer->dimension()->
model()),
2784 dimension_(*lp_optimizer->dimension()),
2785 resource_group_(*resource_group),
2786 lp_optimizer_(lp_optimizer),
2787 mp_optimizer_(mp_optimizer),
2788 filter_objective_cost_(filter_objective_cost),
2789 current_synch_failed_(
false),
2790 synchronized_cost_without_transit_(-1),
2791 delta_cost_without_transit_(-1) {
2792 vehicle_to_resource_class_assignment_costs_.resize(model_.vehicles());
2793 delta_vehicle_to_resource_class_assignment_costs_.resize(model_.vehicles());
2796bool ResourceGroupAssignmentFilter::InitializeAcceptPath() {
2797 delta_vehicle_to_resource_class_assignment_costs_.assign(model_.vehicles(),
2801 int num_used_vehicles = 0;
2802 const int num_resources = resource_group_.Size();
2803 for (
int v : resource_group_.GetVehiclesRequiringAResource()) {
2804 if (GetNext(model_.Start(v)) != model_.End(v) ||
2805 model_.IsVehicleUsedWhenEmpty(v)) {
2806 if (++num_used_vehicles > num_resources) {
2814bool ResourceGroupAssignmentFilter::AcceptPath(int64_t path_start,
2817 const int vehicle = model_.VehicleIndex(path_start);
2822 using RCIndex = RoutingModel::ResourceClassIndex;
2824 ignored_resources_per_class(resource_group_.GetResourceClassesCount());
2826 vehicle, resource_group_, ignored_resources_per_class,
2827 [
this](int64_t
index) {
return GetNext(
index); },
2828 dimension_.transit_evaluator(vehicle), filter_objective_cost_,
2829 lp_optimizer_, mp_optimizer_,
2830 &delta_vehicle_to_resource_class_assignment_costs_[vehicle],
nullptr,
2834bool ResourceGroupAssignmentFilter::FinalizeAcceptPath(
2835 int64_t , int64_t objective_max) {
2836 using RCIndex = RoutingModel::ResourceClassIndex;
2838 ignored_resources_per_class(resource_group_.GetResourceClassesCount());
2840 resource_group_.GetVehiclesRequiringAResource(),
2841 resource_group_.GetResourceIndicesPerClass(), ignored_resources_per_class,
2844 return PathStartTouched(model_.Start(v))
2845 ? &delta_vehicle_to_resource_class_assignment_costs_[v]
2846 : &vehicle_to_resource_class_assignment_costs_[v];
2849 return delta_cost_without_transit_ >= 0 &&
2850 delta_cost_without_transit_ <= objective_max;
2853void ResourceGroupAssignmentFilter::OnBeforeSynchronizePaths() {
2854 current_synch_failed_ =
false;
2857void ResourceGroupAssignmentFilter::OnSynchronizePathFromStart(int64_t
start) {
2863 const auto& next_accessor = [
this](int64_t
index) {
2865 : model_.IsStart(
index) ? model_.End(model_.VehicleIndex(
index))
2868 const int v = model_.VehicleIndex(
start);
2873 using RCIndex = RoutingModel::ResourceClassIndex;
2875 ignored_resources_per_class(resource_group_.GetResourceClassesCount());
2877 v, resource_group_, ignored_resources_per_class, next_accessor,
2878 dimension_.transit_evaluator(v), filter_objective_cost_,
2879 lp_optimizer_, mp_optimizer_,
2880 &vehicle_to_resource_class_assignment_costs_[v],
nullptr,
nullptr)) {
2881 vehicle_to_resource_class_assignment_costs_[v].assign(
2882 resource_group_.GetResourceClassesCount(), -1);
2883 current_synch_failed_ =
true;
2887void ResourceGroupAssignmentFilter::OnAfterSynchronizePaths() {
2888 using RCIndex = RoutingModel::ResourceClassIndex;
2890 ignored_resources_per_class(resource_group_.GetResourceClassesCount());
2891 synchronized_cost_without_transit_ =
2892 (current_synch_failed_ || !filter_objective_cost_)
2895 resource_group_.GetVehiclesRequiringAResource(),
2896 resource_group_.GetResourceIndicesPerClass(),
2897 ignored_resources_per_class,
2899 return &vehicle_to_resource_class_assignment_costs_[v];
2902 synchronized_cost_without_transit_ =
2903 std::max<int64_t>(synchronized_cost_without_transit_, 0);
2907class ResourceAssignmentFilter :
public LocalSearchFilter {
2909 ResourceAssignmentFilter(
const std::vector<IntVar*>& nexts,
2910 LocalDimensionCumulOptimizer* optimizer,
2911 LocalDimensionCumulOptimizer* mp_optimizer,
2912 bool propagate_own_objective_value,
2913 bool filter_objective_cost);
2914 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2915 int64_t objective_min, int64_t objective_max)
override;
2916 void Synchronize(
const Assignment* assignment,
2917 const Assignment*
delta)
override;
2919 int64_t GetAcceptedObjectiveValue()
const override {
2920 return propagate_own_objective_value_ ? delta_cost_ : 0;
2922 int64_t GetSynchronizedObjectiveValue()
const override {
2923 return propagate_own_objective_value_ ? synchronized_cost_ : 0;
2925 std::string DebugString()
const override {
2926 return "ResourceAssignmentFilter(" + dimension_name_ +
")";
2930 std::vector<IntVarLocalSearchFilter*> resource_group_assignment_filters_;
2931 int64_t synchronized_cost_;
2932 int64_t delta_cost_;
2933 const bool propagate_own_objective_value_;
2934 const std::string dimension_name_;
2937ResourceAssignmentFilter::ResourceAssignmentFilter(
2938 const std::vector<IntVar*>& nexts, LocalDimensionCumulOptimizer* optimizer,
2939 LocalDimensionCumulOptimizer* mp_optimizer,
2940 bool propagate_own_objective_value,
bool filter_objective_cost)
2941 : propagate_own_objective_value_(propagate_own_objective_value),
2942 dimension_name_(optimizer->dimension()->
name()) {
2943 const RoutingModel&
model = *optimizer->dimension()->model();
2944 for (
const auto& resource_group :
model.GetResourceGroups()) {
2945 resource_group_assignment_filters_.push_back(
2946 model.solver()->RevAlloc(
new ResourceGroupAssignmentFilter(
2947 nexts, resource_group.get(), optimizer, mp_optimizer,
2948 filter_objective_cost)));
2952bool ResourceAssignmentFilter::Accept(
const Assignment*
delta,
2953 const Assignment* deltadelta,
2954 int64_t objective_min,
2955 int64_t objective_max) {
2957 for (LocalSearchFilter* group_filter : resource_group_assignment_filters_) {
2958 if (!group_filter->Accept(
delta, deltadelta, objective_min,
2963 std::max(delta_cost_, group_filter->GetAcceptedObjectiveValue());
2964 DCHECK_LE(delta_cost_, objective_max)
2965 <<
"ResourceGroupAssignmentFilter should return false when the "
2966 "objective_max is exceeded.";
2971void ResourceAssignmentFilter::Synchronize(
const Assignment* assignment,
2972 const Assignment*
delta) {
2973 synchronized_cost_ = 0;
2974 for (LocalSearchFilter* group_filter : resource_group_assignment_filters_) {
2975 group_filter->Synchronize(assignment,
delta);
2976 synchronized_cost_ = std::max(
2977 synchronized_cost_, group_filter->GetSynchronizedObjectiveValue());
2986 bool propagate_own_objective_value,
bool filter_objective_cost) {
2988 DCHECK_NE(optimizer,
nullptr);
2989 DCHECK_NE(mp_optimizer,
nullptr);
2990 return model.solver()->RevAlloc(
new ResourceAssignmentFilter(
2991 model.Nexts(), optimizer, mp_optimizer, propagate_own_objective_value,
2992 filter_objective_cost));
3009class CPFeasibilityFilter :
public IntVarLocalSearchFilter {
3011 explicit CPFeasibilityFilter(RoutingModel* routing_model);
3012 ~CPFeasibilityFilter()
override {}
3013 std::string DebugString()
const override {
return "CPFeasibilityFilter"; }
3014 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
3015 int64_t objective_min, int64_t objective_max)
override;
3016 void OnSynchronize(
const Assignment*
delta)
override;
3019 void AddDeltaToAssignment(
const Assignment*
delta, Assignment* assignment);
3021 static const int64_t kUnassigned;
3022 const RoutingModel*
const model_;
3023 Solver*
const solver_;
3024 Assignment*
const assignment_;
3025 Assignment*
const temp_assignment_;
3026 DecisionBuilder*
const restore_;
3027 SearchLimit*
const limit_;
3030const int64_t CPFeasibilityFilter::kUnassigned = -1;
3032CPFeasibilityFilter::CPFeasibilityFilter(RoutingModel* routing_model)
3033 : IntVarLocalSearchFilter(routing_model->Nexts()),
3034 model_(routing_model),
3035 solver_(routing_model->solver()),
3036 assignment_(solver_->MakeAssignment()),
3037 temp_assignment_(solver_->MakeAssignment()),
3038 restore_(solver_->MakeRestoreAssignment(temp_assignment_)),
3039 limit_(solver_->MakeCustomLimit(
3040 [routing_model]() {
return routing_model->CheckLimit(); })) {
3041 assignment_->Add(routing_model->Nexts());
3044bool CPFeasibilityFilter::Accept(
const Assignment*
delta,
3048 temp_assignment_->Copy(assignment_);
3049 AddDeltaToAssignment(
delta, temp_assignment_);
3051 return solver_->Solve(restore_, limit_);
3054void CPFeasibilityFilter::OnSynchronize(
const Assignment*
delta) {
3055 AddDeltaToAssignment(
delta, assignment_);
3058void CPFeasibilityFilter::AddDeltaToAssignment(
const Assignment*
delta,
3059 Assignment* assignment) {
3060 if (
delta ==
nullptr) {
3063 Assignment::IntContainer*
const container =
3064 assignment->MutableIntVarContainer();
3065 for (
const IntVarElement& delta_element :
3066 delta->IntVarContainer().elements()) {
3067 IntVar*
const var = delta_element.Var();
3068 int64_t
index = kUnassigned;
3071 if (!FindIndex(
var, &
index))
continue;
3073 const int64_t
value = delta_element.Value();
3076 if (model_->IsStart(
index)) {
3077 if (model_->IsEnd(
value)) {
3079 container->MutableElement(
index)->Deactivate();
3082 container->MutableElement(
index)->Activate();
3091 return routing_model->solver()->RevAlloc(
3092 new CPFeasibilityFilter(routing_model));
3095PathEnergyCostChecker::PathEnergyCostChecker(
3096 const PathState* path_state, std::vector<int> force_class,
3097 std::vector<
const std::function<int64_t(int64_t)>*> force_per_class,
3098 std::vector<int> distance_class,
3099 std::vector<
const std::function<int64_t(int64_t, int64_t)>*>
3101 std::vector<int64_t> path_unit_costs,
3102 std::vector<bool> path_has_cost_when_empty)
3103 : path_state_(path_state),
3104 force_class_(
std::move(force_class)),
3105 distance_class_(
std::move(distance_class)),
3106 force_per_class_(
std::move(force_per_class)),
3107 distance_per_class_(
std::move(distance_per_class)),
3108 path_unit_costs_(
std::move(path_unit_costs)),
3109 path_has_cost_when_empty_(
std::move(path_has_cost_when_empty)) {
3110 committed_total_cost_ = 0;
3111 committed_path_cost_.assign(path_state_->
NumPaths(), 0);
3112 const int num_paths = path_state_->
NumPaths();
3113 for (
int path = 0; path < num_paths; ++path) {
3114 committed_path_cost_[path] = ComputePathCost(path);
3115 committed_total_cost_ =
3116 CapAdd(committed_total_cost_, committed_path_cost_[path]);
3118 accepted_total_cost_ = committed_total_cost_;
3122 if (path_state_->
IsInvalid())
return true;
3123 accepted_total_cost_ = committed_total_cost_;
3125 accepted_total_cost_ =
3126 CapSub(accepted_total_cost_, committed_path_cost_[path]);
3127 accepted_total_cost_ =
CapAdd(accepted_total_cost_, ComputePathCost(path));
3128 if (accepted_total_cost_ ==
kint64max)
return false;
3135 committed_total_cost_ =
3136 CapSub(committed_total_cost_, committed_path_cost_[path]);
3137 committed_path_cost_[path] = ComputePathCost(path);
3138 committed_total_cost_ =
3139 CapAdd(committed_total_cost_, committed_path_cost_[path]);
3143int64_t PathEnergyCostChecker::ComputePathCost(int64_t path)
const {
3144 const int force_class = force_class_[path];
3145 const auto& force_evaluator = *force_per_class_[force_class];
3146 const int distance_class = distance_class_[path];
3147 const auto& distance_evaluator = *distance_per_class_[distance_class];
3149 int64_t total_energy = 0;
3150 int64_t total_force = 0;
3152 int64_t total_distance = 0;
3153 int num_path_nodes = 0;
3154 int prev_node = path_state_->
Start(path);
3155 for (
const auto chain : path_state_->Chains(path)) {
3156 num_path_nodes += chain.NumNodes();
3157 const int first = chain.First();
3160 for (
const int node :
3161 (first == prev_node ? chain.WithoutFirstNode() : chain)) {
3162 const int64_t force = force_evaluator(prev_node);
3163 const int64_t
distance = distance_evaluator(prev_node, node);
3164 total_force =
CapAdd(total_force, force);
3167 min_total_force = std::min(min_total_force, total_force);
3172 if (min_total_force < 0) {
3173 const int64_t offset =
CapProd(total_distance,
CapOpp(min_total_force));
3174 total_energy =
CapAdd(total_energy, offset);
3176 return (num_path_nodes == 2 && !path_has_cost_when_empty_[path])
3178 :
CapProd(total_energy, path_unit_costs_[path]);
3183class PathEnergyCostFilter :
public LocalSearchFilter {
3185 std::string DebugString()
const override {
return name_; }
3186 PathEnergyCostFilter(std::unique_ptr<PathEnergyCostChecker> checker,
3187 absl::string_view energy_name)
3188 : checker_(
std::move(checker)),
3189 name_(
absl::StrCat(
"PathEnergyCostFilter(", energy_name,
")")) {}
3191 bool Accept(
const Assignment*,
const Assignment*, int64_t objective_min,
3192 int64_t objective_max)
override {
3193 if (objective_max >
kint64max / 2)
return true;
3194 if (!checker_->Check())
return false;
3195 const int64_t cost = checker_->AcceptedCost();
3196 return objective_min <= cost && cost <= objective_max;
3199 void Synchronize(
const Assignment*,
const Assignment*)
override {
3203 int64_t GetSynchronizedObjectiveValue()
const override {
3204 return checker_->CommittedCost();
3206 int64_t GetAcceptedObjectiveValue()
const override {
3207 return checker_->AcceptedCost();
3211 std::unique_ptr<PathEnergyCostChecker> checker_;
3212 const std::string name_;
3218 Solver* solver, std::unique_ptr<PathEnergyCostChecker> checker,
3219 absl::string_view dimension_name) {
3220 PathEnergyCostFilter* filter =
3221 new PathEnergyCostFilter(std::move(checker), dimension_name);
std::vector< int > dimensions
STL vector ---------------------------------------------------------------—.
const std::vector< E > & elements() const
AssignmentContainer< IntVar, IntVarElement > IntContainer
static const int64_t kUnassigned
BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size)
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max) override
void OnSynchronize(const Assignment *delta) override
int64_t Start(int i) const
const RoutingDimension * dimension() const
virtual int64_t Min() const =0
virtual int64_t Max() const =0
bool FindIndex(IntVar *const var, int64_t *index) const
int64_t Value(int index) const
bool IsVarSynced(int index) const
IntVar * Var() override
Creates a variable from the expression.
const RoutingDimension * dimension() const
const std::vector< int > & ChangedPaths() const
int NumPaths() const
Returns the number of paths (empty paths included).
int Start(int path) const
Returns the start of a path.
For the time being, Solver is neither MT_SAFE nor MT_HOT.
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Set(IntegerType index)
const std::string name
A name for logging purposes.
const std::vector< IntVar * > cumuls_
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 & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false
problem is infeasible or unbounded (default).
std::function< int64_t(const Model &) Value)(IntegerVariable v)
This checks that the variable is fixed.
In SWIG mode, we don't want anything besides these top-level includes.
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
Returns a filter computing vehicle amortized costs.
int64_t CapAdd(int64_t x, int64_t y)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
Returns a filter ensuring that max active vehicles constraints are enforced.
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
DimensionSchedulingStatus
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model, bool filter_cost)
Returns a filter ensuring that node disjunction constraints are enforced.
int64_t CapSub(int64_t x, int64_t y)
LocalSearchFilter * MakePathEnergyCostFilter(Solver *solver, std::unique_ptr< PathEnergyCostChecker > checker, absl::string_view dimension_name)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
Returns a filter handling dimension cumul bounds.
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, GlobalDimensionCumulOptimizer *mp_optimizer, bool filter_objective_cost)
Returns a filter checking global linear constraints and costs.
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
Returns a filter checking the current solution using CP propagation.
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp)
Returns a filter handling dimension costs and constraints.
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const std::vector< PickupDeliveryPair > &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
int64_t CapProd(int64_t x, int64_t y)
static const int kUnassigned
--— Routing model --—
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, bool use_chain_cumul_filter, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
LocalSearchFilter * MakeResourceAssignmentFilter(LocalDimensionCumulOptimizer *optimizer, LocalDimensionCumulOptimizer *mp_optimizer, bool propagate_own_objective_value, bool filter_objective_cost)
int64_t ComputeBestVehicleToResourceAssignment(const std::vector< int > &vehicles, const absl::StrongVector< RoutingModel::ResourceClassIndex, std::vector< int > > &resource_indices_per_class, const absl::StrongVector< RoutingModel::ResourceClassIndex, absl::flat_hash_set< int > > &ignored_resources_per_class, std::function< const std::vector< int64_t > *(int)> vehicle_to_resource_class_assignment_costs, std::vector< int > *resource_indices)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
Returns a filter checking that vehicle variable domains are respected.
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
Returns a filter ensuring type regulation constraints are enforced.
bool ComputeVehicleToResourceClassAssignmentCosts(int v, const RoutingModel::ResourceGroup &resource_group, const absl::StrongVector< RoutingModel::ResourceClassIndex, absl::flat_hash_set< int > > &ignored_resources_per_class, 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)
LocalSearchFilter * MakeDimensionFilter(Solver *solver, std::unique_ptr< DimensionChecker > checker, const std::string &dimension_name)
int64_t CapOpp(int64_t v)
Note(user): -kint64min != kint64max, but kint64max == ~kint64min.
ABSL_FLAG(bool, routing_strong_debug_checks, false, "Run stronger checks in debug; these stronger tests might change " "the complexity of the code in particular.")
Implementation of local search filters for routing models.
std::vector< int64_t > path_values
std::optional< int64_t > end
static const int64_t kint64max