26 #include "absl/container/flat_hash_map.h"
27 #include "absl/container/flat_hash_set.h"
44 "Run stronger checks in debug; these stronger tests might change "
45 "the complexity of the code in particular.");
46 ABSL_FLAG(
bool, routing_shift_insertion_cost_by_penalty,
true,
47 "Shift insertion costs by the penalty of the inserted node(s).");
55 class MaxActiveVehiclesFilter :
public IntVarLocalSearchFilter {
57 explicit MaxActiveVehiclesFilter(
const RoutingModel& routing_model)
58 : IntVarLocalSearchFilter(routing_model.Nexts()),
59 routing_model_(routing_model),
60 is_active_(routing_model.vehicles(), false),
61 active_vehicles_(0) {}
62 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
63 int64 objective_min,
int64 objective_max)
override {
66 const int delta_size = container.Size();
67 int current_active_vehicles = active_vehicles_;
68 for (
int i = 0; i < delta_size; ++i) {
69 const IntVarElement& new_element = container.Element(i);
70 IntVar*
const var = new_element.Var();
72 if (FindIndex(
var, &
index) && routing_model_.IsStart(
index)) {
73 if (new_element.Min() != new_element.Max()) {
77 const int vehicle = routing_model_.VehicleIndex(
index);
78 const bool is_active =
79 (new_element.Min() != routing_model_.End(vehicle));
80 if (is_active && !is_active_[vehicle]) {
81 ++current_active_vehicles;
82 }
else if (!is_active && is_active_[vehicle]) {
83 --current_active_vehicles;
87 return current_active_vehicles <=
88 routing_model_.GetMaximumNumberOfActiveVehicles();
92 void OnSynchronize(
const Assignment*
delta)
override {
94 for (
int i = 0; i < routing_model_.vehicles(); ++i) {
95 const int index = routing_model_.Start(i);
100 is_active_[i] =
false;
105 const RoutingModel& routing_model_;
106 std::vector<bool> is_active_;
107 int active_vehicles_;
114 new MaxActiveVehiclesFilter(routing_model));
121 class NodeDisjunctionFilter :
public IntVarLocalSearchFilter {
123 explicit NodeDisjunctionFilter(
const RoutingModel& routing_model)
124 : IntVarLocalSearchFilter(routing_model.Nexts()),
125 routing_model_(routing_model),
126 active_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
127 inactive_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
128 synchronized_objective_value_(
kint64min),
131 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
132 int64 objective_min,
int64 objective_max)
override {
135 const int delta_size = container.Size();
137 disjunction_active_deltas;
139 disjunction_inactive_deltas;
140 bool lns_detected =
false;
142 for (
int i = 0; i < delta_size; ++i) {
143 const IntVarElement& new_element = container.Element(i);
144 IntVar*
const var = new_element.Var();
147 const bool is_inactive =
148 (new_element.Min() <=
index && new_element.Max() >=
index);
149 if (new_element.Min() != new_element.Max()) {
153 routing_model_.GetDisjunctionIndices(
index)) {
154 const bool active_state_changed =
156 if (active_state_changed) {
159 disjunction_index, 0);
160 if (IsVarSynced(
index)) {
162 disjunction_index, 0);
166 disjunction_index, 0);
167 if (IsVarSynced(
index)) {
169 disjunction_index, 0);
177 for (
const std::pair<RoutingModel::DisjunctionIndex, int>
178 disjunction_active_delta : disjunction_active_deltas) {
179 const int current_active_nodes =
180 active_per_disjunction_[disjunction_active_delta.first];
181 const int active_nodes =
182 current_active_nodes + disjunction_active_delta.second;
183 const int max_cardinality = routing_model_.GetDisjunctionMaxCardinality(
184 disjunction_active_delta.first);
186 if (active_nodes > max_cardinality) {
191 accepted_objective_value_ = synchronized_objective_value_;
192 for (
const std::pair<RoutingModel::DisjunctionIndex, int>
193 disjunction_inactive_delta : disjunction_inactive_deltas) {
194 const int64 penalty = routing_model_.GetDisjunctionPenalty(
195 disjunction_inactive_delta.first);
196 if (penalty != 0 && !lns_detected) {
198 disjunction_inactive_delta.first;
199 const int current_inactive_nodes =
200 inactive_per_disjunction_[disjunction_index];
201 const int inactive_nodes =
202 current_inactive_nodes + disjunction_inactive_delta.second;
203 const int max_inactive_cardinality =
204 routing_model_.GetDisjunctionIndices(disjunction_index).size() -
205 routing_model_.GetDisjunctionMaxCardinality(disjunction_index);
207 if (inactive_nodes > max_inactive_cardinality) {
212 }
else if (current_inactive_nodes <= max_inactive_cardinality) {
215 accepted_objective_value_ =
216 CapAdd(accepted_objective_value_, penalty);
218 }
else if (current_inactive_nodes > max_inactive_cardinality) {
221 accepted_objective_value_ =
222 CapSub(accepted_objective_value_, penalty);
227 accepted_objective_value_ = 0;
231 return accepted_objective_value_ <= objective_max;
234 std::string DebugString()
const override {
return "NodeDisjunctionFilter"; }
235 int64 GetSynchronizedObjectiveValue()
const override {
236 return synchronized_objective_value_;
238 int64 GetAcceptedObjectiveValue()
const override {
239 return accepted_objective_value_;
243 void OnSynchronize(
const Assignment*
delta)
override {
244 synchronized_objective_value_ = 0;
246 i < active_per_disjunction_.size(); ++i) {
247 active_per_disjunction_[i] = 0;
248 inactive_per_disjunction_[i] = 0;
249 const std::vector<int64>& disjunction_indices =
250 routing_model_.GetDisjunctionIndices(i);
251 for (
const int64 index : disjunction_indices) {
252 const bool index_synced = IsVarSynced(
index);
255 ++active_per_disjunction_[i];
257 ++inactive_per_disjunction_[i];
261 const int64 penalty = routing_model_.GetDisjunctionPenalty(i);
262 const int max_cardinality =
263 routing_model_.GetDisjunctionMaxCardinality(i);
264 if (inactive_per_disjunction_[i] >
265 disjunction_indices.size() - max_cardinality &&
267 synchronized_objective_value_ =
268 CapAdd(synchronized_objective_value_, penalty);
273 const RoutingModel& routing_model_;
276 active_per_disjunction_;
278 inactive_per_disjunction_;
279 int64 synchronized_objective_value_;
280 int64 accepted_objective_value_;
287 new NodeDisjunctionFilter(routing_model));
293 int next_domain_size)
296 paths_(nexts.size(), -1),
297 new_synchronized_unperformed_nodes_(nexts.size()),
299 touched_paths_(nexts.size()),
301 ranks_(next_domain_size, -1),
302 status_(BasePathFilter::UNKNOWN) {}
306 int64 objective_max) {
308 for (
const int touched : delta_touched_) {
311 delta_touched_.clear();
313 const int delta_size = container.
Size();
314 delta_touched_.reserve(delta_size);
326 const auto update_touched_path_chain_start_end = [
this](
int64 index) {
329 touched_paths_.
Set(start);
331 int64& chain_start = touched_path_chain_start_ends_[start].first;
336 int64& chain_end = touched_path_chain_start_ends_[start].second;
342 for (
int i = 0; i < delta_size; ++i) {
347 if (!new_element.
Bound()) {
352 delta_touched_.push_back(
index);
353 update_touched_path_chain_start_end(
index);
354 update_touched_path_chain_start_end(new_nexts_[
index]);
358 InitializeAcceptPath();
361 const std::pair<int64, int64> start_end =
362 touched_path_chain_start_ends_[touched_start];
363 if (!AcceptPath(touched_start, start_end.first, start_end.second)) {
369 return accept && FinalizeAcceptPath(
delta, objective_min, objective_max);
372 void BasePathFilter::ComputePathStarts(std::vector<int64>* path_starts,
373 std::vector<int>* index_to_path) {
374 path_starts->clear();
375 const int nexts_size =
Size();
378 for (
int i = 0; i < nexts_size; ++i) {
383 if (
next < nexts_size) {
388 for (
int i = 0; i < nexts_size; ++i) {
390 (*index_to_path)[i] = path_starts->size();
391 path_starts->push_back(i);
396 bool BasePathFilter::HavePathsChanged() {
397 std::vector<int64> path_starts;
399 ComputePathStarts(&path_starts, &index_to_path);
400 if (path_starts.size() != starts_.size()) {
403 for (
int i = 0; i < path_starts.size(); ++i) {
404 if (path_starts[i] != starts_[i]) {
408 for (
int i = 0; i <
Size(); ++i) {
409 if (index_to_path[i] != paths_[i]) {
416 void BasePathFilter::SynchronizeFullAssignment() {
420 ComputePathStarts(&starts_, &paths_);
425 new_synchronized_unperformed_nodes_.
Set(
index);
429 node_path_starts_.assign(node_path_starts_.size(),
kUnassigned);
431 const int nexts_size =
Size();
432 for (
const int64 start : starts_) {
434 node_path_starts_[node] = start;
437 while (
next < nexts_size) {
439 node_path_starts_[node] = start;
443 node_path_starts_[
next] = start;
445 OnBeforeSynchronizePaths();
447 OnAfterSynchronizePaths();
451 if (status_ == BasePathFilter::UNKNOWN) {
453 DisableFiltering() ? BasePathFilter::DISABLED : BasePathFilter::ENABLED;
456 new_synchronized_unperformed_nodes_.
ClearAll();
457 if (
delta ==
nullptr ||
delta->Empty() || starts_.empty()) {
458 SynchronizeFullAssignment();
465 DCHECK(!absl::GetFlag(FLAGS_routing_strong_debug_checks) ||
466 !HavePathsChanged());
469 for (
int i = 0; i < container.
Size(); ++i) {
475 touched_paths_.
Set(start);
479 new_synchronized_unperformed_nodes_.
Set(
index);
485 OnBeforeSynchronizePaths();
487 int64 node = touched_start;
488 while (node <
Size()) {
489 node_path_starts_[node] = touched_start;
492 node_path_starts_[node] = touched_start;
493 UpdatePathRanksFromStart(touched_start);
494 OnSynchronizePathFromStart(touched_start);
496 OnAfterSynchronizePaths();
499 void BasePathFilter::UpdateAllRanks() {
500 for (
int i = 0; i < ranks_.size(); ++i) {
503 for (
int r = 0; r <
NumPaths(); ++r) {
504 UpdatePathRanksFromStart(
Start(r));
505 OnSynchronizePathFromStart(
Start(r));
509 void BasePathFilter::UpdatePathRanksFromStart(
int start) {
512 while (node <
Size()) {
522 class VehicleAmortizedCostFilter :
public BasePathFilter {
524 explicit VehicleAmortizedCostFilter(
const RoutingModel& routing_model);
525 ~VehicleAmortizedCostFilter()
override {}
526 std::string DebugString()
const override {
527 return "VehicleAmortizedCostFilter";
529 int64 GetSynchronizedObjectiveValue()
const override {
530 return current_vehicle_cost_;
532 int64 GetAcceptedObjectiveValue()
const override {
533 return delta_vehicle_cost_;
537 void OnSynchronizePathFromStart(
int64 start)
override;
538 void OnAfterSynchronizePaths()
override;
539 void InitializeAcceptPath()
override;
540 bool AcceptPath(
int64 path_start,
int64 chain_start,
541 int64 chain_end)
override;
542 bool FinalizeAcceptPath(
const Assignment*
delta,
int64 objective_min,
543 int64 objective_max)
override;
545 int64 current_vehicle_cost_;
546 int64 delta_vehicle_cost_;
547 std::vector<int> current_route_lengths_;
548 std::vector<int64> start_to_end_;
549 std::vector<int> start_to_vehicle_;
550 std::vector<int64> vehicle_to_start_;
551 const std::vector<int64>& linear_cost_factor_of_vehicle_;
552 const std::vector<int64>& quadratic_cost_factor_of_vehicle_;
555 VehicleAmortizedCostFilter::VehicleAmortizedCostFilter(
556 const RoutingModel& routing_model)
557 : BasePathFilter(routing_model.Nexts(),
558 routing_model.Size() + routing_model.vehicles()),
559 current_vehicle_cost_(0),
560 delta_vehicle_cost_(0),
561 current_route_lengths_(Size(), -1),
562 linear_cost_factor_of_vehicle_(
563 routing_model.GetAmortizedLinearCostFactorOfVehicles()),
564 quadratic_cost_factor_of_vehicle_(
565 routing_model.GetAmortizedQuadraticCostFactorOfVehicles()) {
566 start_to_end_.resize(
Size(), -1);
567 start_to_vehicle_.resize(
Size(), -1);
568 vehicle_to_start_.resize(routing_model.vehicles());
569 for (
int v = 0; v < routing_model.vehicles(); v++) {
570 const int64 start = routing_model.Start(v);
571 start_to_vehicle_[start] = v;
572 start_to_end_[start] = routing_model.End(v);
573 vehicle_to_start_[v] = start;
577 void VehicleAmortizedCostFilter::OnSynchronizePathFromStart(
int64 start) {
578 const int64 end = start_to_end_[start];
580 const int route_length = Rank(end) - 1;
582 current_route_lengths_[start] = route_length;
585 void VehicleAmortizedCostFilter::OnAfterSynchronizePaths() {
586 current_vehicle_cost_ = 0;
587 for (
int vehicle = 0; vehicle < vehicle_to_start_.size(); vehicle++) {
588 const int64 start = vehicle_to_start_[vehicle];
589 DCHECK_EQ(vehicle, start_to_vehicle_[start]);
591 const int route_length = current_route_lengths_[start];
594 if (route_length == 0) {
599 const int64 linear_cost_factor = linear_cost_factor_of_vehicle_[vehicle];
600 const int64 route_length_cost =
601 CapProd(quadratic_cost_factor_of_vehicle_[vehicle],
602 route_length * route_length);
604 current_vehicle_cost_ =
CapAdd(
605 current_vehicle_cost_,
CapSub(linear_cost_factor, route_length_cost));
609 void VehicleAmortizedCostFilter::InitializeAcceptPath() {
610 delta_vehicle_cost_ = current_vehicle_cost_;
613 bool VehicleAmortizedCostFilter::AcceptPath(
int64 path_start,
int64 chain_start,
616 const int previous_chain_nodes = Rank(chain_end) - 1 - Rank(chain_start);
618 int new_chain_nodes = 0;
619 int64 node = GetNext(chain_start);
620 while (node != chain_end) {
622 node = GetNext(node);
625 const int previous_route_length = current_route_lengths_[path_start];
627 const int new_route_length =
628 previous_route_length - previous_chain_nodes + new_chain_nodes;
630 const int vehicle = start_to_vehicle_[path_start];
632 DCHECK_EQ(path_start, vehicle_to_start_[vehicle]);
636 if (previous_route_length == 0) {
639 delta_vehicle_cost_ =
640 CapAdd(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
641 }
else if (new_route_length == 0) {
643 delta_vehicle_cost_ =
644 CapSub(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
648 const int64 quadratic_cost_factor =
649 quadratic_cost_factor_of_vehicle_[vehicle];
650 delta_vehicle_cost_ =
651 CapAdd(delta_vehicle_cost_,
653 previous_route_length * previous_route_length));
654 delta_vehicle_cost_ =
CapSub(
656 CapProd(quadratic_cost_factor, new_route_length * new_route_length));
661 bool VehicleAmortizedCostFilter::FinalizeAcceptPath(
const Assignment*
delta,
663 int64 objective_max) {
664 return delta_vehicle_cost_ <= objective_max;
672 new VehicleAmortizedCostFilter(routing_model));
677 class TypeRegulationsFilter :
public BasePathFilter {
679 explicit TypeRegulationsFilter(
const RoutingModel&
model);
680 ~TypeRegulationsFilter()
override {}
681 std::string DebugString()
const override {
return "TypeRegulationsFilter"; }
684 void OnSynchronizePathFromStart(
int64 start)
override;
685 bool AcceptPath(
int64 path_start,
int64 chain_start,
686 int64 chain_end)
override;
688 bool HardIncompatibilitiesRespected(
int vehicle,
int64 chain_start,
691 const RoutingModel& routing_model_;
692 std::vector<int> start_to_vehicle_;
695 std::vector<std::vector<int>> hard_incompatibility_type_counts_per_vehicle_;
697 TypeIncompatibilityChecker temporal_incompatibility_checker_;
698 TypeRequirementChecker requirement_checker_;
701 TypeRegulationsFilter::TypeRegulationsFilter(
const RoutingModel&
model)
703 routing_model_(
model),
704 start_to_vehicle_(
model.Size(), -1),
705 temporal_incompatibility_checker_(
model,
707 requirement_checker_(
model) {
708 const int num_vehicles =
model.vehicles();
709 const bool has_hard_type_incompatibilities =
710 model.HasHardTypeIncompatibilities();
711 if (has_hard_type_incompatibilities) {
712 hard_incompatibility_type_counts_per_vehicle_.resize(num_vehicles);
714 const int num_visit_types =
model.GetNumberOfVisitTypes();
715 for (
int vehicle = 0; vehicle < num_vehicles; vehicle++) {
717 start_to_vehicle_[start] = vehicle;
718 if (has_hard_type_incompatibilities) {
719 hard_incompatibility_type_counts_per_vehicle_[vehicle].resize(
725 void TypeRegulationsFilter::OnSynchronizePathFromStart(
int64 start) {
726 if (!routing_model_.HasHardTypeIncompatibilities())
return;
728 const int vehicle = start_to_vehicle_[start];
730 std::vector<int>& type_counts =
731 hard_incompatibility_type_counts_per_vehicle_[vehicle];
732 std::fill(type_counts.begin(), type_counts.end(), 0);
733 const int num_types = type_counts.size();
736 while (node < Size()) {
737 DCHECK(IsVarSynced(node));
738 const int type = routing_model_.GetVisitType(node);
739 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
740 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
748 bool TypeRegulationsFilter::HardIncompatibilitiesRespected(
int vehicle,
751 if (!routing_model_.HasHardTypeIncompatibilities())
return true;
753 const std::vector<int>& previous_type_counts =
754 hard_incompatibility_type_counts_per_vehicle_[vehicle];
756 absl::flat_hash_map< int,
int> new_type_counts;
757 absl::flat_hash_set<int> types_to_check;
760 int64 node = GetNext(chain_start);
761 while (node != chain_end) {
762 const int type = routing_model_.GetVisitType(node);
763 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
764 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
765 DCHECK_LT(type, previous_type_counts.size());
767 previous_type_counts[type]);
768 if (type_count++ == 0) {
770 types_to_check.insert(type);
773 node = GetNext(node);
778 node =
Value(chain_start);
779 while (node != chain_end) {
780 const int type = routing_model_.GetVisitType(node);
781 if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
782 RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
783 DCHECK_LT(type, previous_type_counts.size());
785 previous_type_counts[type]);
793 for (
int type : types_to_check) {
794 for (
int incompatible_type :
795 routing_model_.GetHardTypeIncompatibilitiesOfType(type)) {
797 previous_type_counts[incompatible_type]) > 0) {
805 bool TypeRegulationsFilter::AcceptPath(
int64 path_start,
int64 chain_start,
807 const int vehicle = start_to_vehicle_[path_start];
809 const auto next_accessor = [
this](
int64 node) {
return GetNext(node); };
810 return HardIncompatibilitiesRespected(vehicle, chain_start, chain_end) &&
811 temporal_incompatibility_checker_.CheckVehicle(vehicle,
813 requirement_checker_.CheckVehicle(vehicle, next_accessor);
821 new TypeRegulationsFilter(routing_model));
831 class ChainCumulFilter :
public BasePathFilter {
833 ChainCumulFilter(
const RoutingModel& routing_model,
834 const RoutingDimension& dimension);
835 ~ChainCumulFilter()
override {}
836 std::string DebugString()
const override {
837 return "ChainCumulFilter(" + name_ +
")";
841 void OnSynchronizePathFromStart(
int64 start)
override;
842 bool AcceptPath(
int64 path_start,
int64 chain_start,
843 int64 chain_end)
override;
845 const std::vector<IntVar*>
cumuls_;
846 std::vector<int64> start_to_vehicle_;
847 std::vector<int64> start_to_end_;
848 std::vector<const RoutingModel::TransitCallback2*> evaluators_;
849 const std::vector<int64> vehicle_capacities_;
850 std::vector<int64> current_path_cumul_mins_;
851 std::vector<int64> current_max_of_path_end_cumul_mins_;
852 std::vector<int64> old_nexts_;
853 std::vector<int> old_vehicles_;
854 std::vector<int64> current_transits_;
855 const std::string name_;
858 ChainCumulFilter::ChainCumulFilter(
const RoutingModel& routing_model,
859 const RoutingDimension& dimension)
860 : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
862 evaluators_(routing_model.vehicles(), nullptr),
863 vehicle_capacities_(dimension.vehicle_capacities()),
864 current_path_cumul_mins_(dimension.cumuls().size(), 0),
865 current_max_of_path_end_cumul_mins_(dimension.cumuls().size(), 0),
868 current_transits_(routing_model.Size(), 0),
869 name_(dimension.
name()) {
870 start_to_vehicle_.resize(Size(), -1);
871 start_to_end_.resize(Size(), -1);
872 for (
int i = 0; i < routing_model.vehicles(); ++i) {
873 start_to_vehicle_[routing_model.Start(i)] = i;
874 start_to_end_[routing_model.Start(i)] = routing_model.End(i);
875 evaluators_[i] = &dimension.transit_evaluator(i);
882 void ChainCumulFilter::OnSynchronizePathFromStart(
int64 start) {
883 const int vehicle = start_to_vehicle_[start];
884 std::vector<int64> path_nodes;
887 while (node < Size()) {
888 path_nodes.push_back(node);
889 current_path_cumul_mins_[node] = cumul;
891 if (
next != old_nexts_[node] || vehicle != old_vehicles_[node]) {
892 old_nexts_[node] =
next;
893 old_vehicles_[node] = vehicle;
894 current_transits_[node] = (*evaluators_[vehicle])(node,
next);
896 cumul =
CapAdd(cumul, current_transits_[node]);
900 path_nodes.push_back(node);
901 current_path_cumul_mins_[node] = cumul;
902 int64 max_cumuls = cumul;
903 for (
int i = path_nodes.size() - 1; i >= 0; --i) {
904 const int64 node = path_nodes[i];
905 max_cumuls =
std::max(max_cumuls, current_path_cumul_mins_[node]);
906 current_max_of_path_end_cumul_mins_[node] = max_cumuls;
911 bool ChainCumulFilter::AcceptPath(
int64 path_start,
int64 chain_start,
913 const int vehicle = start_to_vehicle_[path_start];
915 int64 node = chain_start;
916 int64 cumul = current_path_cumul_mins_[node];
917 while (node != chain_end) {
919 if (IsVarSynced(node) &&
next ==
Value(node) &&
920 vehicle == old_vehicles_[node]) {
921 cumul =
CapAdd(cumul, current_transits_[node]);
923 cumul =
CapAdd(cumul, (*evaluators_[vehicle])(node,
next));
929 const int64 end = start_to_end_[path_start];
930 const int64 end_cumul_delta =
931 CapSub(current_path_cumul_mins_[end], current_path_cumul_mins_[node]);
932 const int64 after_chain_cumul_delta =
933 CapSub(current_max_of_path_end_cumul_mins_[node],
934 current_path_cumul_mins_[node]);
941 class PathCumulFilter :
public BasePathFilter {
943 PathCumulFilter(
const RoutingModel& routing_model,
944 const RoutingDimension& dimension,
946 bool propagate_own_objective_value,
947 bool filter_objective_cost,
bool can_use_lp);
948 ~PathCumulFilter()
override {}
949 std::string DebugString()
const override {
950 return "PathCumulFilter(" + name_ +
")";
952 int64 GetSynchronizedObjectiveValue()
const override {
953 return propagate_own_objective_value_ ? synchronized_objective_value_ : 0;
955 int64 GetAcceptedObjectiveValue()
const override {
956 return propagate_own_objective_value_ ? accepted_objective_value_ : 0;
963 struct SupportedPathCumul {
984 void ClearPath(
int path) {
985 paths_[path].clear();
986 transits_[path].clear();
988 int AddPaths(
int num_paths) {
989 const int first_path = paths_.size();
990 paths_.resize(first_path + num_paths);
991 transits_.resize(first_path + num_paths);
994 void ReserveTransits(
int path,
int number_of_route_arcs) {
995 transits_[path].reserve(number_of_route_arcs);
996 paths_[path].reserve(number_of_route_arcs + 1);
1000 void PushTransit(
int path,
int node,
int next,
int64 transit) {
1001 transits_[path].push_back(transit);
1002 if (paths_[path].empty()) {
1003 paths_[path].push_back(node);
1006 paths_[path].push_back(
next);
1008 int NumPaths()
const {
return paths_.size(); }
1009 int PathSize(
int path)
const {
return paths_[path].size(); }
1010 int Node(
int path,
int position)
const {
return paths_[path][position]; }
1011 int64 Transit(
int path,
int position)
const {
1012 return transits_[path][position];
1017 std::vector<std::vector<int64>> paths_;
1020 std::vector<std::vector<int64>> transits_;
1023 void InitializeAcceptPath()
override {
1024 cumul_cost_delta_ = total_current_cumul_cost_value_;
1025 node_with_precedence_to_delta_min_max_cumuls_.clear();
1028 delta_paths_.clear();
1029 delta_path_transits_.Clear();
1030 lns_detected_ =
false;
1031 delta_nodes_with_precedences_and_changed_cumul_.
ClearAll();
1033 bool AcceptPath(
int64 path_start,
int64 chain_start,
1034 int64 chain_end)
override;
1035 bool FinalizeAcceptPath(
const Assignment*
delta,
int64 objective_min,
1036 int64 objective_max)
override;
1037 void OnBeforeSynchronizePaths()
override;
1039 bool FilterSpanCost()
const {
return global_span_cost_coefficient_ != 0; }
1041 bool FilterSlackCost()
const {
1042 return has_nonzero_vehicle_span_cost_coefficients_ ||
1043 has_vehicle_span_upper_bounds_;
1046 bool FilterBreakCost(
int vehicle)
const {
1047 return dimension_.HasBreakConstraints() &&
1048 !dimension_.GetBreakIntervalsOfVehicle(vehicle).empty();
1051 bool FilterCumulSoftBounds()
const {
return !cumul_soft_bounds_.empty(); }
1055 bool FilterCumulPiecewiseLinearCosts()
const {
1056 return !cumul_piecewise_linear_costs_.empty();
1059 bool FilterWithDimensionCumulOptimizerForVehicle(
int vehicle)
const {
1060 if (!can_use_lp_ || FilterCumulPiecewiseLinearCosts()) {
1064 int num_linear_constraints = 0;
1065 if (dimension_.GetSpanCostCoefficientForVehicle(vehicle) > 0)
1066 ++num_linear_constraints;
1067 if (FilterSoftSpanCost(vehicle)) ++num_linear_constraints;
1068 if (FilterCumulSoftLowerBounds()) ++num_linear_constraints;
1069 if (FilterCumulSoftBounds()) ++num_linear_constraints;
1070 if (vehicle_span_upper_bounds_[vehicle] <
kint64max)
1071 ++num_linear_constraints;
1072 const bool has_breaks = FilterBreakCost(vehicle);
1073 if (has_breaks) ++num_linear_constraints;
1083 return num_linear_constraints >= 2 &&
1084 (has_breaks || filter_objective_cost_);
1087 bool FilterDimensionForbiddenIntervals()
const {
1088 for (
const SortedDisjointIntervalList& intervals :
1089 dimension_.forbidden_intervals()) {
1092 if (intervals.NumIntervals() > 0) {
1101 bool FilterCumulSoftLowerBounds()
const {
1102 return !cumul_soft_lower_bounds_.empty();
1105 bool FilterPrecedences()
const {
return !node_index_to_precedences_.empty(); }
1107 bool FilterSoftSpanCost()
const {
1108 return dimension_.HasSoftSpanUpperBounds();
1110 bool FilterSoftSpanCost(
int vehicle)
const {
1111 return dimension_.HasSoftSpanUpperBounds() &&
1112 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle).cost > 0;
1114 bool FilterSoftSpanQuadraticCost()
const {
1115 return dimension_.HasQuadraticCostSoftSpanUpperBounds();
1117 bool FilterSoftSpanQuadraticCost(
int vehicle)
const {
1118 return dimension_.HasQuadraticCostSoftSpanUpperBounds() &&
1119 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle)
1125 int64 GetPathCumulSoftLowerBoundCost(
const PathTransits& path_transits,
1128 void InitializeSupportedPathCumul(SupportedPathCumul* supported_cumul,
1129 int64 default_value);
1139 bool PickupToDeliveryLimitsRespected(
1140 const PathTransits& path_transits,
int path,
1141 const std::vector<int64>& min_path_cumuls)
const;
1151 void StoreMinMaxCumulOfNodesOnPath(
int path,
1152 const std::vector<int64>& min_path_cumuls,
1162 int64 ComputePathMaxStartFromEndCumul(
const PathTransits& path_transits,
1163 int path,
int64 path_start,
1164 int64 min_end_cumul)
const;
1166 const RoutingModel& routing_model_;
1167 const RoutingDimension& dimension_;
1168 const std::vector<IntVar*>
cumuls_;
1169 const std::vector<IntVar*> slacks_;
1170 std::vector<int64> start_to_vehicle_;
1171 std::vector<const RoutingModel::TransitCallback2*> evaluators_;
1172 std::vector<int64> vehicle_span_upper_bounds_;
1173 bool has_vehicle_span_upper_bounds_;
1174 int64 total_current_cumul_cost_value_;
1175 int64 synchronized_objective_value_;
1176 int64 accepted_objective_value_;
1179 absl::flat_hash_map<int64, int64> current_cumul_cost_values_;
1180 int64 cumul_cost_delta_;
1182 std::vector<int64> delta_path_cumul_cost_values_;
1183 const int64 global_span_cost_coefficient_;
1184 std::vector<SoftBound> cumul_soft_bounds_;
1185 std::vector<SoftBound> cumul_soft_lower_bounds_;
1186 std::vector<const PiecewiseLinearFunction*> cumul_piecewise_linear_costs_;
1187 std::vector<int64> vehicle_span_cost_coefficients_;
1188 bool has_nonzero_vehicle_span_cost_coefficients_;
1189 const std::vector<int64> vehicle_capacities_;
1193 std::vector<std::vector<RoutingDimension::NodePrecedence>>
1194 node_index_to_precedences_;
1197 SupportedPathCumul current_min_start_;
1198 SupportedPathCumul current_max_end_;
1199 PathTransits current_path_transits_;
1201 std::vector<std::pair<int64, int64>> current_min_max_node_cumuls_;
1204 PathTransits delta_path_transits_;
1205 int64 delta_max_end_cumul_;
1206 SparseBitset<int64> delta_nodes_with_precedences_and_changed_cumul_;
1207 absl::flat_hash_map<int64, std::pair<int64, int64>>
1208 node_with_precedence_to_delta_min_max_cumuls_;
1211 const std::string name_;
1213 LocalDimensionCumulOptimizer* optimizer_;
1214 std::unique_ptr<LocalDimensionCumulOptimizer> internal_optimizer_;
1215 LocalDimensionCumulOptimizer* mp_optimizer_;
1216 std::unique_ptr<LocalDimensionCumulOptimizer> internal_mp_optimizer_;
1217 const bool filter_objective_cost_;
1220 const bool can_use_lp_;
1221 const bool propagate_own_objective_value_;
1224 DisjunctivePropagator disjunctive_propagator_;
1225 DisjunctivePropagator::Tasks tasks_;
1226 TravelBounds travel_bounds_;
1227 std::vector<int64> current_path_;
1232 PathCumulFilter::PathCumulFilter(
const RoutingModel& routing_model,
1233 const RoutingDimension& dimension,
1235 bool propagate_own_objective_value,
1236 bool filter_objective_cost,
bool can_use_lp)
1237 : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
1238 routing_model_(routing_model),
1239 dimension_(dimension),
1241 slacks_(dimension.slacks()),
1242 evaluators_(routing_model.vehicles(), nullptr),
1243 vehicle_span_upper_bounds_(dimension.vehicle_span_upper_bounds()),
1244 has_vehicle_span_upper_bounds_(false),
1245 total_current_cumul_cost_value_(0),
1246 synchronized_objective_value_(0),
1247 accepted_objective_value_(0),
1248 current_cumul_cost_values_(),
1249 cumul_cost_delta_(0),
1250 delta_path_cumul_cost_values_(routing_model.vehicles(),
kint64min),
1251 global_span_cost_coefficient_(dimension.global_span_cost_coefficient()),
1252 vehicle_span_cost_coefficients_(
1253 dimension.vehicle_span_cost_coefficients()),
1254 has_nonzero_vehicle_span_cost_coefficients_(false),
1255 vehicle_capacities_(dimension.vehicle_capacities()),
1256 delta_max_end_cumul_(0),
1257 delta_nodes_with_precedences_and_changed_cumul_(routing_model.Size()),
1258 name_(dimension.
name()),
1259 optimizer_(routing_model.GetMutableLocalCumulOptimizer(dimension)),
1260 mp_optimizer_(routing_model.GetMutableLocalCumulMPOptimizer(dimension)),
1261 filter_objective_cost_(filter_objective_cost),
1262 can_use_lp_(can_use_lp),
1263 propagate_own_objective_value_(propagate_own_objective_value),
1264 lns_detected_(false) {
1265 for (
const int64 upper_bound : vehicle_span_upper_bounds_) {
1267 has_vehicle_span_upper_bounds_ =
true;
1273 has_nonzero_vehicle_span_cost_coefficients_ =
true;
1277 cumul_soft_bounds_.resize(
cumuls_.size());
1278 cumul_soft_lower_bounds_.resize(
cumuls_.size());
1279 cumul_piecewise_linear_costs_.resize(
cumuls_.size());
1280 bool has_cumul_soft_bounds =
false;
1281 bool has_cumul_soft_lower_bounds =
false;
1282 bool has_cumul_piecewise_linear_costs =
false;
1283 bool has_cumul_hard_bounds =
false;
1284 for (
const IntVar*
const slack : slacks_) {
1285 if (slack->Min() > 0) {
1286 has_cumul_hard_bounds =
true;
1290 for (
int i = 0; i <
cumuls_.size(); ++i) {
1291 if (dimension.HasCumulVarSoftUpperBound(i)) {
1292 has_cumul_soft_bounds =
true;
1293 cumul_soft_bounds_[i].bound = dimension.GetCumulVarSoftUpperBound(i);
1294 cumul_soft_bounds_[i].coefficient =
1295 dimension.GetCumulVarSoftUpperBoundCoefficient(i);
1297 if (dimension.HasCumulVarSoftLowerBound(i)) {
1298 has_cumul_soft_lower_bounds =
true;
1299 cumul_soft_lower_bounds_[i].bound =
1300 dimension.GetCumulVarSoftLowerBound(i);
1301 cumul_soft_lower_bounds_[i].coefficient =
1302 dimension.GetCumulVarSoftLowerBoundCoefficient(i);
1304 if (dimension.HasCumulVarPiecewiseLinearCost(i)) {
1305 has_cumul_piecewise_linear_costs =
true;
1306 cumul_piecewise_linear_costs_[i] =
1307 dimension.GetCumulVarPiecewiseLinearCost(i);
1309 IntVar*
const cumul_var =
cumuls_[i];
1310 if (cumul_var->Min() > 0 || cumul_var->Max() <
kint64max) {
1311 has_cumul_hard_bounds =
true;
1314 if (!has_cumul_soft_bounds) {
1315 cumul_soft_bounds_.clear();
1317 if (!has_cumul_soft_lower_bounds) {
1318 cumul_soft_lower_bounds_.clear();
1320 if (!has_cumul_piecewise_linear_costs) {
1321 cumul_piecewise_linear_costs_.clear();
1323 if (!has_cumul_hard_bounds) {
1328 vehicle_span_cost_coefficients_.assign(routing_model.vehicles(), 0);
1329 has_nonzero_vehicle_span_cost_coefficients_ =
false;
1331 start_to_vehicle_.resize(Size(), -1);
1332 for (
int i = 0; i < routing_model.vehicles(); ++i) {
1333 start_to_vehicle_[routing_model.Start(i)] = i;
1334 evaluators_[i] = &dimension.transit_evaluator(i);
1337 const std::vector<RoutingDimension::NodePrecedence>& node_precedences =
1338 dimension.GetNodePrecedences();
1339 if (!node_precedences.empty()) {
1340 current_min_max_node_cumuls_.resize(
cumuls_.size(), {-1, -1});
1341 node_index_to_precedences_.resize(
cumuls_.size());
1342 for (
const auto& node_precedence : node_precedences) {
1343 node_index_to_precedences_[node_precedence.first_node].push_back(
1345 node_index_to_precedences_[node_precedence.second_node].push_back(
1352 if (can_use_lp_ && optimizer_ ==
nullptr) {
1353 DCHECK(mp_optimizer_ ==
nullptr);
1354 for (
int vehicle = 0; vehicle < routing_model.vehicles(); vehicle++) {
1355 if (!FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1358 if (optimizer_ ==
nullptr) {
1362 internal_optimizer_ = absl::make_unique<LocalDimensionCumulOptimizer>(
1363 &dimension,
parameters.continuous_scheduling_solver());
1364 optimizer_ = internal_optimizer_.get();
1366 if (FilterBreakCost(vehicle) || FilterDimensionForbiddenIntervals()) {
1367 internal_mp_optimizer_ =
1368 absl::make_unique<LocalDimensionCumulOptimizer>(
1369 &dimension,
parameters.mixed_integer_scheduling_solver());
1370 mp_optimizer_ = internal_mp_optimizer_.get();
1378 if (node < cumul_soft_bounds_.size()) {
1379 const int64 bound = cumul_soft_bounds_[node].bound;
1388 int64 PathCumulFilter::GetCumulPiecewiseLinearCost(
int64 node,
1390 if (node < cumul_piecewise_linear_costs_.size()) {
1391 const PiecewiseLinearFunction*
cost = cumul_piecewise_linear_costs_[node];
1392 if (
cost !=
nullptr) {
1399 int64 PathCumulFilter::GetCumulSoftLowerBoundCost(
int64 node,
1401 if (node < cumul_soft_lower_bounds_.size()) {
1402 const int64 bound = cumul_soft_lower_bounds_[node].bound;
1411 int64 PathCumulFilter::GetPathCumulSoftLowerBoundCost(
1412 const PathTransits& path_transits,
int path)
const {
1413 int64 node = path_transits.Node(path, path_transits.PathSize(path) - 1);
1415 int64 current_cumul_cost_value = GetCumulSoftLowerBoundCost(node, cumul);
1416 for (
int i = path_transits.PathSize(path) - 2; i >= 0; --i) {
1417 node = path_transits.Node(path, i);
1418 cumul =
CapSub(cumul, path_transits.Transit(path, i));
1420 current_cumul_cost_value =
CapAdd(current_cumul_cost_value,
1421 GetCumulSoftLowerBoundCost(node, cumul));
1423 return current_cumul_cost_value;
1426 void PathCumulFilter::OnBeforeSynchronizePaths() {
1427 total_current_cumul_cost_value_ = 0;
1428 cumul_cost_delta_ = 0;
1429 current_cumul_cost_values_.clear();
1430 if (NumPaths() > 0 &&
1431 (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1432 FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1433 FilterPrecedences() || FilterSoftSpanCost() ||
1434 FilterSoftSpanQuadraticCost())) {
1435 InitializeSupportedPathCumul(¤t_min_start_,
kint64max);
1436 InitializeSupportedPathCumul(¤t_max_end_,
kint64min);
1437 current_path_transits_.Clear();
1438 current_path_transits_.AddPaths(NumPaths());
1440 for (
int r = 0; r < NumPaths(); ++r) {
1441 int64 node = Start(r);
1442 const int vehicle = start_to_vehicle_[Start(r)];
1445 int number_of_route_arcs = 0;
1446 while (node < Size()) {
1447 ++number_of_route_arcs;
1450 current_path_transits_.ReserveTransits(r, number_of_route_arcs);
1454 std::vector<int64> min_path_cumuls;
1455 min_path_cumuls.reserve(number_of_route_arcs + 1);
1456 min_path_cumuls.push_back(cumul);
1458 int64 current_cumul_cost_value = GetCumulSoftCost(node, cumul);
1459 current_cumul_cost_value =
CapAdd(
1460 current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1462 int64 total_transit = 0;
1463 while (node < Size()) {
1465 const int64 transit = (*evaluators_[vehicle])(node,
next);
1466 total_transit =
CapAdd(total_transit, transit);
1467 const int64 transit_slack =
CapAdd(transit, slacks_[node]->Min());
1468 current_path_transits_.PushTransit(r, node,
next, transit_slack);
1469 cumul =
CapAdd(cumul, transit_slack);
1471 dimension_.GetFirstPossibleGreaterOrEqualValueForNode(
next, cumul);
1473 min_path_cumuls.push_back(cumul);
1475 current_cumul_cost_value =
1476 CapAdd(current_cumul_cost_value, GetCumulSoftCost(node, cumul));
1477 current_cumul_cost_value =
CapAdd(
1478 current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1480 if (FilterPrecedences()) {
1481 StoreMinMaxCumulOfNodesOnPath(r, min_path_cumuls,
1484 if (number_of_route_arcs == 1 &&
1485 !routing_model_.AreEmptyRouteCostsConsideredForVehicle(vehicle)) {
1488 current_cumul_cost_values_[Start(r)] = 0;
1489 current_path_transits_.ClearPath(r);
1492 if (FilterSlackCost() || FilterSoftSpanCost() ||
1493 FilterSoftSpanQuadraticCost()) {
1494 const int64 start = ComputePathMaxStartFromEndCumul(
1495 current_path_transits_, r, Start(r), cumul);
1496 const int64 span_lower_bound =
CapSub(cumul, start);
1497 if (FilterSlackCost()) {
1498 current_cumul_cost_value =
1499 CapAdd(current_cumul_cost_value,
1500 CapProd(vehicle_span_cost_coefficients_[vehicle],
1501 CapSub(span_lower_bound, total_transit)));
1503 if (FilterSoftSpanCost()) {
1504 const SimpleBoundCosts::BoundCost bound_cost =
1505 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1506 if (bound_cost.bound < span_lower_bound) {
1507 const int64 violation =
CapSub(span_lower_bound, bound_cost.bound);
1508 current_cumul_cost_value =
CapAdd(
1509 current_cumul_cost_value,
CapProd(bound_cost.cost, violation));
1512 if (FilterSoftSpanQuadraticCost()) {
1513 const SimpleBoundCosts::BoundCost bound_cost =
1514 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1515 if (bound_cost.bound < span_lower_bound) {
1516 const int64 violation =
CapSub(span_lower_bound, bound_cost.bound);
1517 current_cumul_cost_value =
1518 CapAdd(current_cumul_cost_value,
1523 if (FilterCumulSoftLowerBounds()) {
1524 current_cumul_cost_value =
1525 CapAdd(current_cumul_cost_value,
1526 GetPathCumulSoftLowerBoundCost(current_path_transits_, r));
1528 if (FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1531 int64 lp_cumul_cost_value = 0;
1532 LocalDimensionCumulOptimizer*
const optimizer =
1533 FilterBreakCost(vehicle) ? mp_optimizer_ : optimizer_;
1534 DCHECK(optimizer !=
nullptr);
1536 optimizer->ComputeRouteCumulCostWithoutFixedTransits(
1537 vehicle, [
this](
int64 node) {
return Value(node); },
1538 &lp_cumul_cost_value);
1540 case DimensionSchedulingStatus::INFEASIBLE:
1541 lp_cumul_cost_value = 0;
1543 case DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY:
1544 DCHECK(mp_optimizer_ !=
nullptr);
1545 if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1546 vehicle, [
this](
int64 node) { return Value(node); },
1547 &lp_cumul_cost_value) ==
1548 DimensionSchedulingStatus::INFEASIBLE) {
1549 lp_cumul_cost_value = 0;
1553 DCHECK(status == DimensionSchedulingStatus::OPTIMAL);
1555 current_cumul_cost_value =
1556 std::max(current_cumul_cost_value, lp_cumul_cost_value);
1558 current_cumul_cost_values_[Start(r)] = current_cumul_cost_value;
1559 current_max_end_.path_values[r] = cumul;
1560 if (current_max_end_.cumul_value < cumul) {
1561 current_max_end_.cumul_value = cumul;
1562 current_max_end_.cumul_value_support = r;
1564 total_current_cumul_cost_value_ =
1565 CapAdd(total_current_cumul_cost_value_, current_cumul_cost_value);
1567 if (FilterPrecedences()) {
1569 for (
int64 node : GetNewSynchronizedUnperformedNodes()) {
1570 current_min_max_node_cumuls_[node] = {-1, -1};
1575 for (
int r = 0; r < NumPaths(); ++r) {
1576 const int64 start = ComputePathMaxStartFromEndCumul(
1577 current_path_transits_, r, Start(r), current_max_end_.cumul_value);
1578 current_min_start_.path_values[r] = start;
1579 if (current_min_start_.cumul_value > start) {
1580 current_min_start_.cumul_value = start;
1581 current_min_start_.cumul_value_support = r;
1587 lns_detected_ =
false;
1589 DCHECK_GE(current_max_end_.cumul_value, current_min_start_.cumul_value);
1590 synchronized_objective_value_ =
1591 CapAdd(total_current_cumul_cost_value_,
1592 CapProd(global_span_cost_coefficient_,
1593 CapSub(current_max_end_.cumul_value,
1594 current_min_start_.cumul_value)));
1597 bool PathCumulFilter::AcceptPath(
int64 path_start,
int64 chain_start,
1599 int64 node = path_start;
1601 int64 cumul_cost_delta = 0;
1602 int64 total_transit = 0;
1603 const int path = delta_path_transits_.AddPaths(1);
1604 const int vehicle = start_to_vehicle_[path_start];
1606 const bool filter_vehicle_costs =
1607 !routing_model_.IsEnd(GetNext(node)) ||
1608 routing_model_.AreEmptyRouteCostsConsideredForVehicle(vehicle);
1609 if (filter_vehicle_costs) {
1610 cumul_cost_delta =
CapAdd(GetCumulSoftCost(node, cumul),
1611 GetCumulPiecewiseLinearCost(node, cumul));
1614 int number_of_route_arcs = 0;
1615 while (node < Size()) {
1621 lns_detected_ =
true;
1624 ++number_of_route_arcs;
1627 delta_path_transits_.ReserveTransits(path, number_of_route_arcs);
1628 std::vector<int64> min_path_cumuls;
1629 min_path_cumuls.reserve(number_of_route_arcs + 1);
1630 min_path_cumuls.push_back(cumul);
1635 while (node < Size()) {
1637 const int64 transit = (*evaluators_[vehicle])(node,
next);
1638 total_transit =
CapAdd(total_transit, transit);
1639 const int64 transit_slack =
CapAdd(transit, slacks_[node]->Min());
1640 delta_path_transits_.PushTransit(path, node,
next, transit_slack);
1641 cumul =
CapAdd(cumul, transit_slack);
1642 cumul = dimension_.GetFirstPossibleGreaterOrEqualValueForNode(
next, cumul);
1647 min_path_cumuls.push_back(cumul);
1649 if (filter_vehicle_costs) {
1651 CapAdd(cumul_cost_delta, GetCumulSoftCost(node, cumul));
1653 CapAdd(cumul_cost_delta, GetCumulPiecewiseLinearCost(node, cumul));
1656 const int64 min_end = cumul;
1658 if (!PickupToDeliveryLimitsRespected(delta_path_transits_, path,
1662 if (FilterSlackCost() || FilterBreakCost(vehicle) ||
1663 FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1665 if (vehicle_span_upper_bounds_[vehicle] <
kint64max) {
1666 const int64 span_max = vehicle_span_upper_bounds_[vehicle];
1667 slack_max =
std::min(slack_max,
CapSub(span_max, total_transit));
1669 const int64 max_start_from_min_end = ComputePathMaxStartFromEndCumul(
1670 delta_path_transits_, path, path_start, min_end);
1671 const int64 span_lb =
CapSub(min_end, max_start_from_min_end);
1672 int64 min_total_slack =
CapSub(span_lb, total_transit);
1673 if (min_total_slack > slack_max)
return false;
1675 if (dimension_.HasBreakConstraints()) {
1676 for (
const auto [limit, min_break_duration] :
1677 dimension_.GetBreakDistanceDurationOfVehicle(vehicle)) {
1682 if (limit == 0 || total_transit == 0)
continue;
1683 const int num_breaks_lb = (total_transit - 1) / limit;
1684 const int64 slack_lb =
CapProd(num_breaks_lb, min_break_duration);
1685 if (slack_lb > slack_max)
return false;
1686 min_total_slack =
std::max(min_total_slack, slack_lb);
1692 int64 min_total_break = 0;
1693 int64 max_path_end =
cumuls_[routing_model_.End(vehicle)]->Max();
1694 const int64 max_start = ComputePathMaxStartFromEndCumul(
1695 delta_path_transits_, path, path_start, max_path_end);
1696 for (
const IntervalVar* br :
1697 dimension_.GetBreakIntervalsOfVehicle(vehicle)) {
1698 if (!br->MustBePerformed())
continue;
1699 if (max_start < br->EndMin() && br->StartMax() < min_end) {
1700 min_total_break =
CapAdd(min_total_break, br->DurationMin());
1703 if (min_total_break > slack_max)
return false;
1704 min_total_slack =
std::max(min_total_slack, min_total_break);
1706 if (filter_vehicle_costs) {
1707 cumul_cost_delta =
CapAdd(
1709 CapProd(vehicle_span_cost_coefficients_[vehicle], min_total_slack));
1710 const int64 span_lower_bound =
CapAdd(total_transit, min_total_slack);
1711 if (FilterSoftSpanCost()) {
1712 const SimpleBoundCosts::BoundCost bound_cost =
1713 dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1714 if (bound_cost.bound < span_lower_bound) {
1715 const int64 violation =
CapSub(span_lower_bound, bound_cost.bound);
1717 CapAdd(cumul_cost_delta,
CapProd(bound_cost.cost, violation));
1720 if (FilterSoftSpanQuadraticCost()) {
1721 const SimpleBoundCosts::BoundCost bound_cost =
1722 dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1723 if (bound_cost.bound < span_lower_bound) {
1724 const int64 violation =
CapSub(span_lower_bound, bound_cost.bound);
1731 if (
CapAdd(total_transit, min_total_slack) >
1732 vehicle_span_upper_bounds_[vehicle]) {
1736 if (FilterCumulSoftLowerBounds() && filter_vehicle_costs) {
1739 GetPathCumulSoftLowerBoundCost(delta_path_transits_, path));
1741 if (FilterPrecedences()) {
1742 StoreMinMaxCumulOfNodesOnPath(path, min_path_cumuls,
true);
1744 if (!filter_vehicle_costs) {
1747 cumul_cost_delta = 0;
1748 delta_path_transits_.ClearPath(path);
1750 if (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1751 FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1752 FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1753 delta_paths_.insert(GetPath(path_start));
1754 delta_path_cumul_cost_values_[vehicle] = cumul_cost_delta;
1756 CapSub(cumul_cost_delta, current_cumul_cost_values_[path_start]);
1757 if (filter_vehicle_costs) {
1758 delta_max_end_cumul_ =
std::max(delta_max_end_cumul_, min_end);
1761 cumul_cost_delta_ =
CapAdd(cumul_cost_delta_, cumul_cost_delta);
1765 bool PathCumulFilter::FinalizeAcceptPath(
const Assignment*
delta,
1766 int64 objective_min,
1767 int64 objective_max) {
1768 if ((!FilterSpanCost() && !FilterCumulSoftBounds() && !FilterSlackCost() &&
1769 !FilterCumulSoftLowerBounds() && !FilterCumulPiecewiseLinearCosts() &&
1770 !FilterPrecedences() && !FilterSoftSpanCost() &&
1771 !FilterSoftSpanQuadraticCost()) ||
1775 if (FilterPrecedences()) {
1776 for (
int64 node : delta_nodes_with_precedences_and_changed_cumul_
1777 .PositionsSetAtLeastOnce()) {
1778 const std::pair<int64, int64> node_min_max_cumul_in_delta =
1783 DCHECK(node_min_max_cumul_in_delta.first >= 0 &&
1784 node_min_max_cumul_in_delta.second >= 0);
1785 for (
const RoutingDimension::NodePrecedence& precedence :
1786 node_index_to_precedences_[node]) {
1787 const bool node_is_first = (precedence.first_node == node);
1788 const int64 other_node =
1789 node_is_first ? precedence.second_node : precedence.first_node;
1791 GetNext(other_node) == other_node) {
1798 const std::pair<int64, int64>& other_min_max_cumul_in_delta =
1801 current_min_max_node_cumuls_[other_node]);
1803 const int64 first_min_cumul = node_is_first
1804 ? node_min_max_cumul_in_delta.first
1805 : other_min_max_cumul_in_delta.first;
1806 const int64 second_max_cumul = node_is_first
1807 ? other_min_max_cumul_in_delta.second
1808 : node_min_max_cumul_in_delta.second;
1810 if (second_max_cumul < first_min_cumul + precedence.offset) {
1816 int64 new_max_end = delta_max_end_cumul_;
1818 if (FilterSpanCost()) {
1819 if (new_max_end < current_max_end_.cumul_value) {
1824 current_max_end_.cumul_value_support)) {
1825 new_max_end = current_max_end_.cumul_value;
1827 for (
int i = 0; i < current_max_end_.path_values.size(); ++i) {
1828 if (current_max_end_.path_values[i] > new_max_end &&
1830 new_max_end = current_max_end_.path_values[i];
1838 for (
int r = 0; r < delta_path_transits_.NumPaths(); ++r) {
1840 std::min(ComputePathMaxStartFromEndCumul(delta_path_transits_, r,
1841 Start(r), new_max_end),
1844 if (new_max_end != current_max_end_.cumul_value) {
1845 for (
int r = 0; r < NumPaths(); ++r) {
1849 new_min_start =
std::min(new_min_start, ComputePathMaxStartFromEndCumul(
1850 current_path_transits_, r,
1851 Start(r), new_max_end));
1853 }
else if (new_min_start > current_min_start_.cumul_value) {
1858 current_min_start_.cumul_value_support)) {
1859 new_min_start = current_min_start_.cumul_value;
1861 for (
int i = 0; i < current_min_start_.path_values.size(); ++i) {
1862 if (current_min_start_.path_values[i] < new_min_start &&
1864 new_min_start = current_min_start_.path_values[i];
1872 accepted_objective_value_ =
1873 CapAdd(cumul_cost_delta_,
CapProd(global_span_cost_coefficient_,
1874 CapSub(new_max_end, new_min_start)));
1876 if (can_use_lp_ && optimizer_ !=
nullptr &&
1877 accepted_objective_value_ <= objective_max) {
1878 const size_t num_touched_paths = GetTouchedPathStarts().size();
1879 std::vector<int64> path_delta_cost_values(num_touched_paths, 0);
1880 std::vector<bool> requires_mp(num_touched_paths,
false);
1881 for (
int i = 0; i < num_touched_paths; ++i) {
1882 const int64 start = GetTouchedPathStarts()[i];
1883 const int vehicle = start_to_vehicle_[start];
1884 if (!FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1887 int64 path_delta_cost_with_lp = 0;
1889 optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1890 vehicle, [
this](
int64 node) {
return GetNext(node); },
1891 &path_delta_cost_with_lp);
1892 if (status == DimensionSchedulingStatus::INFEASIBLE) {
1897 path_delta_cost_with_lp, delta_path_cumul_cost_values_[vehicle]);
1898 if (path_cost_diff_with_lp > 0) {
1899 path_delta_cost_values[i] = path_delta_cost_with_lp;
1900 accepted_objective_value_ =
1901 CapAdd(accepted_objective_value_, path_cost_diff_with_lp);
1902 if (accepted_objective_value_ > objective_max) {
1906 path_delta_cost_values[i] = delta_path_cumul_cost_values_[vehicle];
1908 if (mp_optimizer_ !=
nullptr) {
1910 FilterBreakCost(vehicle) ||
1911 (status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY);
1914 if (mp_optimizer_ ==
nullptr) {
1915 return accepted_objective_value_ <= objective_max;
1917 for (
int i = 0; i < num_touched_paths; ++i) {
1918 if (!requires_mp[i]) {
1921 const int64 start = GetTouchedPathStarts()[i];
1922 const int vehicle = start_to_vehicle_[start];
1923 int64 path_delta_cost_with_mp = 0;
1924 if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1925 vehicle, [
this](
int64 node) { return GetNext(node); },
1926 &path_delta_cost_with_mp) ==
1927 DimensionSchedulingStatus::INFEASIBLE) {
1931 const int64 path_cost_diff_with_mp =
1932 CapSub(path_delta_cost_with_mp, path_delta_cost_values[i]);
1933 if (path_cost_diff_with_mp > 0) {
1934 accepted_objective_value_ =
1935 CapAdd(accepted_objective_value_, path_cost_diff_with_mp);
1936 if (accepted_objective_value_ > objective_max) {
1943 return accepted_objective_value_ <= objective_max;
1946 void PathCumulFilter::InitializeSupportedPathCumul(
1947 SupportedPathCumul* supported_cumul,
int64 default_value) {
1948 supported_cumul->cumul_value = default_value;
1949 supported_cumul->cumul_value_support = -1;
1950 supported_cumul->path_values.resize(NumPaths(), default_value);
1953 bool PathCumulFilter::PickupToDeliveryLimitsRespected(
1954 const PathTransits& path_transits,
int path,
1955 const std::vector<int64>& min_path_cumuls)
const {
1956 if (!dimension_.HasPickupToDeliveryLimits()) {
1959 const int num_pairs = routing_model_.GetPickupAndDeliveryPairs().size();
1961 std::vector<std::pair<int, int64>> visited_delivery_and_min_cumul_per_pair(
1962 num_pairs, {-1, -1});
1964 const int path_size = path_transits.PathSize(path);
1965 CHECK_EQ(min_path_cumuls.size(), path_size);
1967 int64 max_cumul = min_path_cumuls.back();
1968 for (
int i = path_transits.PathSize(path) - 2; i >= 0; i--) {
1969 const int node_index = path_transits.Node(path, i);
1970 max_cumul =
CapSub(max_cumul, path_transits.Transit(path, i));
1973 const std::vector<std::pair<int, int>>& pickup_index_pairs =
1974 routing_model_.GetPickupIndexPairs(node_index);
1975 const std::vector<std::pair<int, int>>& delivery_index_pairs =
1976 routing_model_.GetDeliveryIndexPairs(node_index);
1977 if (!pickup_index_pairs.empty()) {
1981 DCHECK(delivery_index_pairs.empty());
1982 DCHECK_EQ(pickup_index_pairs.size(), 1);
1983 const int pair_index = pickup_index_pairs[0].first;
1985 const int delivery_index =
1986 visited_delivery_and_min_cumul_per_pair[pair_index].first;
1987 if (delivery_index < 0) {
1991 const int64 cumul_diff_limit = dimension_.GetPickupToDeliveryLimitForPair(
1992 pair_index, pickup_index_pairs[0].second, delivery_index);
1993 if (
CapSub(visited_delivery_and_min_cumul_per_pair[pair_index].second,
1994 max_cumul) > cumul_diff_limit) {
1998 if (!delivery_index_pairs.empty()) {
2001 DCHECK(pickup_index_pairs.empty());
2002 DCHECK_EQ(delivery_index_pairs.size(), 1);
2003 const int pair_index = delivery_index_pairs[0].first;
2004 std::pair<int, int64>& delivery_index_and_cumul =
2005 visited_delivery_and_min_cumul_per_pair[pair_index];
2006 int& delivery_index = delivery_index_and_cumul.first;
2008 delivery_index = delivery_index_pairs[0].second;
2009 delivery_index_and_cumul.second = min_path_cumuls[i];
2015 void PathCumulFilter::StoreMinMaxCumulOfNodesOnPath(
2016 int path,
const std::vector<int64>& min_path_cumuls,
bool is_delta) {
2017 const PathTransits& path_transits =
2018 is_delta ? delta_path_transits_ : current_path_transits_;
2020 const int path_size = path_transits.PathSize(path);
2021 DCHECK_EQ(min_path_cumuls.size(), path_size);
2023 int64 max_cumul =
cumuls_[path_transits.Node(path, path_size - 1)]->Max();
2024 for (
int i = path_size - 1; i >= 0; i--) {
2025 const int node_index = path_transits.Node(path, i);
2027 if (i < path_size - 1) {
2028 max_cumul =
CapSub(max_cumul, path_transits.Transit(path, i));
2032 if (is_delta && node_index_to_precedences_[node_index].empty()) {
2037 std::pair<int64, int64>& min_max_cumuls =
2038 is_delta ? node_with_precedence_to_delta_min_max_cumuls_[node_index]
2039 : current_min_max_node_cumuls_[node_index];
2040 min_max_cumuls.first = min_path_cumuls[i];
2041 min_max_cumuls.second = max_cumul;
2043 if (is_delta && !routing_model_.IsEnd(node_index) &&
2044 (min_max_cumuls.first !=
2045 current_min_max_node_cumuls_[node_index].first ||
2046 max_cumul != current_min_max_node_cumuls_[node_index].second)) {
2047 delta_nodes_with_precedences_and_changed_cumul_.
Set(node_index);
2052 int64 PathCumulFilter::ComputePathMaxStartFromEndCumul(
2053 const PathTransits& path_transits,
int path,
int64 path_start,
2054 int64 min_end_cumul)
const {
2055 int64 cumul_from_min_end = min_end_cumul;
2056 int64 cumul_from_max_end =
2057 cumuls_[routing_model_.End(start_to_vehicle_[path_start])]->Max();
2058 for (
int i = path_transits.PathSize(path) - 2; i >= 0; --i) {
2059 const int64 transit = path_transits.Transit(path, i);
2060 const int64 node = path_transits.Node(path, i);
2061 cumul_from_min_end =
2063 cumul_from_max_end = dimension_.GetLastPossibleLessOrEqualValueForNode(
2064 node,
CapSub(cumul_from_max_end, transit));
2066 return std::min(cumul_from_min_end, cumul_from_max_end);
2074 bool propagate_own_objective_value,
bool filter_objective_cost,
2077 return model.solver()->RevAlloc(
new PathCumulFilter(
2079 filter_objective_cost, can_use_lp));
2084 bool DimensionHasCumulCost(
const RoutingDimension& dimension) {
2085 if (dimension.global_span_cost_coefficient() != 0)
return true;
2086 if (dimension.HasSoftSpanUpperBounds())
return true;
2087 if (dimension.HasQuadraticCostSoftSpanUpperBounds())
return true;
2088 for (
const int64 coefficient : dimension.vehicle_span_cost_coefficients()) {
2091 for (
int i = 0; i < dimension.cumuls().size(); ++i) {
2092 if (dimension.HasCumulVarSoftUpperBound(i))
return true;
2093 if (dimension.HasCumulVarSoftLowerBound(i))
return true;
2094 if (dimension.HasCumulVarPiecewiseLinearCost(i))
return true;
2099 bool DimensionHasCumulConstraint(
const RoutingDimension& dimension) {
2100 if (dimension.HasBreakConstraints())
return true;
2101 if (dimension.HasPickupToDeliveryLimits())
return true;
2102 if (!dimension.GetNodePrecedences().empty())
return true;
2103 for (
const int64 upper_bound : dimension.vehicle_span_upper_bounds()) {
2104 if (upper_bound !=
kint64max)
return true;
2106 for (
const IntVar*
const slack : dimension.slacks()) {
2107 if (slack->Min() > 0)
return true;
2109 const std::vector<IntVar*>& cumuls = dimension.cumuls();
2110 for (
int i = 0; i < cumuls.size(); ++i) {
2111 IntVar*
const cumul_var = cumuls[i];
2112 if (cumul_var->Min() > 0 && cumul_var->Max() <
kint64max &&
2113 !dimension.model()->IsEnd(i)) {
2116 if (dimension.forbidden_intervals()[i].NumIntervals() > 0)
return true;
2125 const std::vector<RoutingDimension*>& dimensions,
2126 std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2130 if (dimension->GetUnaryTransitEvaluator(0) ==
nullptr)
continue;
2132 using Intervals = std::vector<UnaryDimensionChecker::Interval>;
2134 const int num_vehicles = dimension->model()->vehicles();
2135 Intervals path_capacity(num_vehicles);
2136 std::vector<int> path_class(num_vehicles);
2137 for (
int v = 0; v < num_vehicles; ++v) {
2138 const auto& vehicle_capacities = dimension->vehicle_capacities();
2139 path_capacity[v] = {0, vehicle_capacities[v]};
2140 path_class[v] = dimension->vehicle_to_class(v);
2147 const int num_vehicle_classes =
2148 1 + *std::max_element(path_class.begin(), path_class.end());
2149 std::vector<Intervals> demands(num_vehicle_classes);
2150 const int num_cumuls = dimension->cumuls().size();
2151 const int num_slacks = dimension->slacks().size();
2152 for (
int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
2153 const int vehicle_class = path_class[vehicle];
2154 if (!demands[vehicle_class].empty())
continue;
2155 const auto& evaluator = dimension->GetUnaryTransitEvaluator(vehicle);
2156 Intervals class_demands(num_cumuls);
2157 for (
int node = 0; node < num_cumuls; ++node) {
2158 if (node < num_slacks) {
2159 const int64 demand_min = evaluator(node);
2160 const int64 slack_max = dimension->SlackVar(node)->Max();
2161 class_demands[node] = {demand_min,
CapAdd(demand_min, slack_max)};
2163 class_demands[node] = {0, 0};
2166 demands[vehicle_class] = std::move(class_demands);
2169 Intervals node_capacity(num_cumuls);
2170 for (
int node = 0; node < num_cumuls; ++node) {
2171 const IntVar* cumul = dimension->CumulVar(node);
2172 node_capacity[node] = {cumul->
Min(), cumul->
Max()};
2175 auto checker = absl::make_unique<UnaryDimensionChecker>(
2176 path_state, std::move(path_capacity), std::move(path_class),
2177 std::move(demands), std::move(node_capacity));
2178 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2180 dimension->model()->solver(), std::move(checker));
2181 filters->push_back({filter, kAccept});
2186 const std::vector<RoutingDimension*>& dimensions,
2187 const RoutingSearchParameters&
parameters,
bool filter_objective_cost,
2188 std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2189 const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2197 const int num_dimensions = dimensions.size();
2199 std::vector<bool> use_path_cumul_filter(num_dimensions);
2200 std::vector<bool> use_cumul_bounds_propagator_filter(num_dimensions);
2201 std::vector<bool> use_global_lp_filter(num_dimensions);
2202 std::vector<int> filtering_difficulty(num_dimensions);
2203 for (
int d = 0; d < num_dimensions; d++) {
2205 const bool has_cumul_cost = DimensionHasCumulCost(dimension);
2206 use_path_cumul_filter[d] =
2207 has_cumul_cost || DimensionHasCumulConstraint(dimension);
2209 const bool can_use_cumul_bounds_propagator_filter =
2211 (!filter_objective_cost || !has_cumul_cost);
2213 use_global_lp_filter[d] =
2214 (has_precedences && !can_use_cumul_bounds_propagator_filter) ||
2217 use_cumul_bounds_propagator_filter[d] =
2218 has_precedences && !use_global_lp_filter[d];
2220 filtering_difficulty[d] = 4 * use_global_lp_filter[d] +
2221 2 * use_cumul_bounds_propagator_filter[d] +
2222 use_path_cumul_filter[d];
2225 std::vector<int> sorted_dimension_indices(num_dimensions);
2226 std::iota(sorted_dimension_indices.begin(), sorted_dimension_indices.end(),
2228 std::sort(sorted_dimension_indices.begin(), sorted_dimension_indices.end(),
2229 [&filtering_difficulty](
int d1,
int d2) {
2230 return filtering_difficulty[d1] < filtering_difficulty[d2];
2233 for (
const int d : sorted_dimension_indices) {
2240 const bool use_global_lp = use_global_lp_filter[d];
2241 if (use_path_cumul_filter[d]) {
2244 filter_objective_cost),
2248 {
model.solver()->RevAlloc(
new ChainCumulFilter(
model, dimension)),
2252 if (use_global_lp) {
2253 DCHECK(
model.GetMutableGlobalCumulOptimizer(dimension) !=
nullptr);
2255 model.GetMutableGlobalCumulOptimizer(dimension),
2256 filter_objective_cost),
2258 }
else if (use_cumul_bounds_propagator_filter[d]) {
2269 PickupDeliveryFilter(
const std::vector<IntVar*>& nexts,
int next_domain_size,
2271 const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2273 ~PickupDeliveryFilter()
override {}
2274 bool AcceptPath(
int64 path_start,
int64 chain_start,
2275 int64 chain_end)
override;
2276 std::string
DebugString()
const override {
return "PickupDeliveryFilter"; }
2279 bool AcceptPathDefault(
int64 path_start);
2280 template <
bool lifo>
2281 bool AcceptPathOrdered(
int64 path_start);
2283 std::vector<int> pair_firsts_;
2284 std::vector<int> pair_seconds_;
2285 const RoutingModel::IndexPairs pairs_;
2286 SparseBitset<> visited_;
2287 std::deque<int> visited_deque_;
2288 const std::vector<RoutingModel::PickupAndDeliveryPolicy> vehicle_policies_;
2291 PickupDeliveryFilter::PickupDeliveryFilter(
2292 const std::vector<IntVar*>& nexts,
int next_domain_size,
2293 const RoutingModel::IndexPairs& pairs,
2294 const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies)
2295 : BasePathFilter(nexts, next_domain_size),
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.first) {
2304 pair_firsts_[first] = i;
2306 for (
int second : index_pair.second) {
2307 pair_seconds_[second] = i;
2312 bool PickupDeliveryFilter::AcceptPath(
int64 path_start,
int64 chain_start,
2314 switch (vehicle_policies_[GetPath(path_start)]) {
2316 return AcceptPathDefault(path_start);
2318 return AcceptPathOrdered<true>(path_start);
2320 return AcceptPathOrdered<false>(path_start);
2326 bool PickupDeliveryFilter::AcceptPathDefault(
int64 path_start) {
2328 int64 node = path_start;
2329 int64 path_length = 1;
2330 while (node < Size()) {
2332 if (path_length > Size()) {
2339 for (
int second : pairs_[pair_firsts_[node]].second) {
2340 if (visited_[second]) {
2346 bool found_first =
false;
2347 bool some_synced =
false;
2348 for (
int first : pairs_[pair_seconds_[node]].first) {
2349 if (visited_[first]) {
2353 if (IsVarSynced(first)) {
2357 if (!found_first && some_synced) {
2372 bool found_second =
false;
2373 bool some_synced =
false;
2374 for (
int second : pairs_[pair_firsts_[node]].second) {
2375 if (visited_[second]) {
2376 found_second =
true;
2379 if (IsVarSynced(second)) {
2383 if (!found_second && some_synced) {
2391 template <
bool lifo>
2392 bool PickupDeliveryFilter::AcceptPathOrdered(
int64 path_start) {
2393 visited_deque_.clear();
2394 int64 node = path_start;
2395 int64 path_length = 1;
2396 while (node < Size()) {
2398 if (path_length > Size()) {
2403 visited_deque_.push_back(node);
2405 visited_deque_.push_front(node);
2409 bool found_first =
false;
2410 bool some_synced =
false;
2411 for (
int first : pairs_[pair_seconds_[node]].first) {
2412 if (!visited_deque_.empty() && visited_deque_.back() == first) {
2416 if (IsVarSynced(first)) {
2420 if (!found_first && some_synced) {
2422 }
else if (!visited_deque_.empty()) {
2423 visited_deque_.pop_back();
2434 while (!visited_deque_.empty()) {
2435 for (
int second : pairs_[pair_firsts_[visited_deque_.back()]].second) {
2436 if (IsVarSynced(second)) {
2440 visited_deque_.pop_back();
2449 const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2451 return routing_model.
solver()->
RevAlloc(
new PickupDeliveryFilter(
2453 pairs, vehicle_policies));
2459 class VehicleVarFilter :
public BasePathFilter {
2461 explicit VehicleVarFilter(
const RoutingModel& routing_model);
2462 ~VehicleVarFilter()
override {}
2463 bool AcceptPath(
int64 path_start,
int64 chain_start,
2464 int64 chain_end)
override;
2465 std::string DebugString()
const override {
return "VehicleVariableFilter"; }
2468 bool DisableFiltering()
const override;
2469 bool IsVehicleVariableConstrained(
int index)
const;
2471 std::vector<int64> start_to_vehicle_;
2472 std::vector<IntVar*> vehicle_vars_;
2473 const int64 unconstrained_vehicle_var_domain_size_;
2476 VehicleVarFilter::VehicleVarFilter(
const RoutingModel& routing_model)
2477 : BasePathFilter(routing_model.Nexts(),
2478 routing_model.Size() + routing_model.vehicles()),
2479 vehicle_vars_(routing_model.VehicleVars()),
2480 unconstrained_vehicle_var_domain_size_(routing_model.vehicles()) {
2481 start_to_vehicle_.resize(Size(), -1);
2482 for (
int i = 0; i < routing_model.vehicles(); ++i) {
2483 start_to_vehicle_[routing_model.Start(i)] = i;
2487 bool VehicleVarFilter::AcceptPath(
int64 path_start,
int64 chain_start,
2489 const int64 vehicle = start_to_vehicle_[path_start];
2490 int64 node = chain_start;
2491 while (node != chain_end) {
2492 if (!vehicle_vars_[node]->Contains(vehicle)) {
2495 node = GetNext(node);
2497 return vehicle_vars_[node]->Contains(vehicle);
2500 bool VehicleVarFilter::DisableFiltering()
const {
2501 for (
int i = 0; i < vehicle_vars_.size(); ++i) {
2502 if (IsVehicleVariableConstrained(i))
return false;
2507 bool VehicleVarFilter::IsVehicleVariableConstrained(
int index)
const {
2508 const IntVar*
const vehicle_var = vehicle_vars_[
index];
2512 const int adjusted_unconstrained_vehicle_var_domain_size =
2513 vehicle_var->Min() >= 0 ? unconstrained_vehicle_var_domain_size_
2514 : unconstrained_vehicle_var_domain_size_ + 1;
2515 return vehicle_var->Size() != adjusted_unconstrained_vehicle_var_domain_size;
2522 return routing_model.
solver()->
RevAlloc(
new VehicleVarFilter(routing_model));
2527 class CumulBoundsPropagatorFilter :
public IntVarLocalSearchFilter {
2529 explicit CumulBoundsPropagatorFilter(
const RoutingDimension& dimension);
2530 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2531 int64 objective_min,
int64 objective_max)
override;
2532 std::string DebugString()
const override {
2533 return "CumulBoundsPropagatorFilter(" + propagator_.dimension().name() +
2538 CumulBoundsPropagator propagator_;
2539 const int64 cumul_offset_;
2540 SparseBitset<int64> delta_touched_;
2541 std::vector<int64> delta_nexts_;
2544 CumulBoundsPropagatorFilter::CumulBoundsPropagatorFilter(
2545 const RoutingDimension& dimension)
2546 : IntVarLocalSearchFilter(dimension.
model()->Nexts()),
2547 propagator_(&dimension),
2548 cumul_offset_(dimension.GetGlobalOptimizerOffset()),
2549 delta_touched_(Size()),
2550 delta_nexts_(Size()) {}
2552 bool CumulBoundsPropagatorFilter::Accept(
const Assignment*
delta,
2553 const Assignment* deltadelta,
2554 int64 objective_min,
2555 int64 objective_max) {
2557 for (
const IntVarElement& delta_element :
2558 delta->IntVarContainer().elements()) {
2560 if (FindIndex(delta_element.Var(), &
index)) {
2561 if (!delta_element.Bound()) {
2566 delta_nexts_[
index] = delta_element.Value();
2569 const auto& next_accessor = [
this](
int64 index) {
2573 return propagator_.PropagateCumulBounds(next_accessor, cumul_offset_);
2581 new CumulBoundsPropagatorFilter(dimension));
2586 class LPCumulFilter :
public IntVarLocalSearchFilter {
2588 LPCumulFilter(
const std::vector<IntVar*>& nexts,
2589 GlobalDimensionCumulOptimizer* optimizer,
2590 bool filter_objective_cost);
2591 bool Accept(
const Assignment*
delta,
const Assignment* deltadelta,
2592 int64 objective_min,
int64 objective_max)
override;
2593 int64 GetAcceptedObjectiveValue()
const override;
2594 void OnSynchronize(
const Assignment*
delta)
override;
2595 int64 GetSynchronizedObjectiveValue()
const override;
2596 std::string DebugString()
const override {
2597 return "LPCumulFilter(" + optimizer_.dimension()->name() +
")";
2601 GlobalDimensionCumulOptimizer& optimizer_;
2602 const bool filter_objective_cost_;
2603 int64 synchronized_cost_without_transit_;
2604 int64 delta_cost_without_transit_;
2605 SparseBitset<int64> delta_touched_;
2606 std::vector<int64> delta_nexts_;
2609 LPCumulFilter::LPCumulFilter(
const std::vector<IntVar*>& nexts,
2610 GlobalDimensionCumulOptimizer* optimizer,
2611 bool filter_objective_cost)
2612 : IntVarLocalSearchFilter(nexts),
2613 optimizer_(*optimizer),
2614 filter_objective_cost_(filter_objective_cost),
2615 synchronized_cost_without_transit_(-1),
2616 delta_cost_without_transit_(-1),
2617 delta_touched_(Size()),
2618 delta_nexts_(Size()) {}
2620 bool LPCumulFilter::Accept(
const Assignment*
delta,
2621 const Assignment* deltadelta,
int64 objective_min,
2622 int64 objective_max) {
2624 for (
const IntVarElement& delta_element :
2625 delta->IntVarContainer().elements()) {
2627 if (FindIndex(delta_element.Var(), &
index)) {
2628 if (!delta_element.Bound()) {
2633 delta_nexts_[
index] = delta_element.Value();
2636 const auto& next_accessor = [
this](
int64 index) {
2640 if (!filter_objective_cost_) {
2642 delta_cost_without_transit_ = 0;
2643 return optimizer_.IsFeasible(next_accessor);
2646 if (!optimizer_.ComputeCumulCostWithoutFixedTransits(
2647 next_accessor, &delta_cost_without_transit_)) {
2649 delta_cost_without_transit_ =
kint64max;
2652 return delta_cost_without_transit_ <= objective_max;
2655 int64 LPCumulFilter::GetAcceptedObjectiveValue()
const {
2656 return delta_cost_without_transit_;
2659 void LPCumulFilter::OnSynchronize(
const Assignment*
delta) {
2662 const RoutingModel&
model = *optimizer_.dimension()->model();
2663 if (!optimizer_.ComputeCumulCostWithoutFixedTransits(
2665 return IsVarSynced(index) ? Value(index)
2666 : model.IsStart(index) ? model.End(model.VehicleIndex(index))
2669 &synchronized_cost_without_transit_)) {
2672 synchronized_cost_without_transit_ = 0;
2676 int64 LPCumulFilter::GetSynchronizedObjectiveValue()
const {
2677 return synchronized_cost_without_transit_;
2685 return model.solver()->RevAlloc(
2686 new LPCumulFilter(
model.Nexts(), optimizer, filter_objective_cost));
2693 model_(routing_model),
2694 solver_(routing_model->solver()),
2695 assignment_(solver_->MakeAssignment()),
2696 temp_assignment_(solver_->MakeAssignment()),
2697 restore_(solver_->MakeRestoreAssignment(temp_assignment_)),
2698 limit_(solver_->MakeCustomLimit(
2699 [routing_model]() {
return routing_model->
CheckLimit(); })) {
2700 assignment_->
Add(routing_model->Nexts());
2706 temp_assignment_->
Copy(assignment_);
2707 AddDeltaToAssignment(
delta, temp_assignment_);
2709 return solver_->
Solve(restore_, limit_);
2713 AddDeltaToAssignment(
delta, assignment_);
2716 void CPFeasibilityFilter::AddDeltaToAssignment(
const Assignment*
delta,
2718 if (
delta ==
nullptr) {
2724 const int delta_size = delta_container.Size();
2726 for (
int i = 0; i < delta_size; i++) {
2727 const IntVarElement& delta_element = delta_container.Element(i);
2728 IntVar*
const var = delta_element.Var();
2738 container->MutableElement(
index)->Deactivate();
2741 container->MutableElement(
index)->Activate();
2758 const std::vector<std::set<VehicleClassEntry>>& all_vehicle_classes_per_type =
2760 sorted_vehicle_classes_per_type_.resize(all_vehicle_classes_per_type.size());
2761 const std::vector<std::deque<int>>& all_vehicles_per_class =
2763 vehicles_per_vehicle_class_.resize(all_vehicles_per_class.size());
2765 for (
int type = 0; type < all_vehicle_classes_per_type.size(); type++) {
2766 std::set<VehicleClassEntry>& stored_class_entries =
2767 sorted_vehicle_classes_per_type_[type];
2768 stored_class_entries.clear();
2770 const int vehicle_class = class_entry.vehicle_class;
2771 std::vector<int>& stored_vehicles =
2772 vehicles_per_vehicle_class_[vehicle_class];
2773 stored_vehicles.clear();
2774 for (
int vehicle : all_vehicles_per_class[vehicle_class]) {
2775 if (store_vehicle(vehicle)) {
2776 stored_vehicles.push_back(vehicle);
2779 if (!stored_vehicles.empty()) {
2780 stored_class_entries.insert(class_entry);
2787 const std::function<
bool(
int)>& remove_vehicle) {
2788 for (std::set<VehicleClassEntry>& class_entries :
2789 sorted_vehicle_classes_per_type_) {
2790 auto class_entry_it = class_entries.begin();
2791 while (class_entry_it != class_entries.end()) {
2792 const int vehicle_class = class_entry_it->vehicle_class;
2793 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
2794 vehicles.erase(std::remove_if(vehicles.begin(), vehicles.end(),
2795 [&remove_vehicle](
int vehicle) {
2796 return remove_vehicle(vehicle);
2799 if (vehicles.empty()) {
2800 class_entry_it = class_entries.erase(class_entry_it);
2809 int type, std::function<
bool(
int)> vehicle_is_compatible,
2810 std::function<
bool(
int)> stop_and_return_vehicle) {
2811 std::set<VehicleTypeCurator::VehicleClassEntry>& sorted_classes =
2812 sorted_vehicle_classes_per_type_[type];
2813 auto vehicle_class_it = sorted_classes.begin();
2815 while (vehicle_class_it != sorted_classes.end()) {
2816 const int vehicle_class = vehicle_class_it->vehicle_class;
2817 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
2818 DCHECK(!vehicles.empty());
2820 for (
auto vehicle_it = vehicles.begin(); vehicle_it != vehicles.end();
2822 const int vehicle = *vehicle_it;
2823 if (vehicle_is_compatible(vehicle)) {
2824 vehicles.erase(vehicle_it);
2825 if (vehicles.empty()) {
2826 sorted_classes.erase(vehicle_class_it);
2828 return {vehicle, -1};
2830 if (stop_and_return_vehicle(vehicle)) {
2831 return {-1, vehicle};
2848 std::unique_ptr<IntVarFilteredHeuristic> heuristic)
2849 : heuristic_(std::move(heuristic)) {}
2852 Assignment*
const assignment = heuristic_->BuildSolution();
2853 if (assignment !=
nullptr) {
2854 VLOG(2) <<
"Number of decisions: " << heuristic_->number_of_decisions();
2855 VLOG(2) <<
"Number of rejected decisions: "
2856 << heuristic_->number_of_rejects();
2865 return heuristic_->number_of_decisions();
2869 return heuristic_->number_of_rejects();
2873 return absl::StrCat(
"IntVarFilteredDecisionBuilder(",
2874 heuristic_->DebugString(),
")");
2882 Solver* solver,
const std::vector<IntVar*>& vars,
2884 : assignment_(solver->MakeAssignment()),
2887 delta_(solver->MakeAssignment()),
2888 is_in_delta_(
vars_.size(), false),
2889 empty_(solver->MakeAssignment()),
2890 filter_manager_(filter_manager),
2891 number_of_decisions_(0),
2892 number_of_rejects_(0) {
2894 delta_indices_.reserve(vars_.size());
2898 number_of_decisions_ = 0;
2899 number_of_rejects_ = 0;
2920 const std::function<
int64(
int64)>& next_accessor) {
2925 start_chain_ends_.resize(
model()->vehicles());
2926 end_chain_starts_.resize(
model()->vehicles());
2928 for (
int v = 0; v < model_->
vehicles(); v++) {
2930 while (!model_->
IsEnd(node)) {
2940 end_chain_starts_[v] =
model()->
End(v);
2953 ++number_of_decisions_;
2954 const bool accept = FilterAccept();
2957 const int delta_size = delta_container.
Size();
2960 for (
int i = 0; i < delta_size; ++i) {
2969 ++number_of_rejects_;
2972 for (
const int delta_index : delta_indices_) {
2973 is_in_delta_[delta_index] =
false;
2976 delta_indices_.clear();
2984 bool IntVarFilteredHeuristic::FilterAccept() {
2985 if (!filter_manager_)
return true;
2997 bool RoutingFilteredHeuristic::InitializeSolution() {
3007 start_chain_ends_.clear();
3008 start_chain_ends_.resize(
model()->vehicles(), -1);
3009 end_chain_starts_.clear();
3010 end_chain_starts_.resize(
model()->vehicles(), -1);
3013 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
3015 while (!
model()->IsEnd(node) &&
Var(node)->Bound()) {
3021 start_chain_ends_[vehicle] = node;
3024 std::vector<int64> starts(
Size() +
model()->vehicles(), -1);
3025 std::vector<int64> ends(
Size() +
model()->vehicles(), -1);
3028 starts[node] = node;
3031 std::vector<bool> touched(
Size(),
false);
3032 for (
int node = 0; node <
Size(); ++node) {
3034 while (!
model()->
IsEnd(current) && !touched[current]) {
3035 touched[current] =
true;
3036 IntVar*
const next_var =
Var(current);
3037 if (next_var->Bound()) {
3038 current = next_var->Value();
3043 starts[ends[current]] = starts[node];
3044 ends[starts[node]] = ends[current];
3049 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
3050 end_chain_starts_[vehicle] = starts[
model()->
End(vehicle)];
3051 int64 node = start_chain_ends_[vehicle];
3052 if (!
model()->IsEnd(node)) {
3057 while (!
model()->IsEnd(node)) {
3075 node, 1, [
this, node](
int alternate) {
3076 if (node != alternate && !
Contains(alternate)) {
3091 std::vector<bool> to_make_unperformed(
Size(),
false);
3092 for (
const auto& [pickups, deliveries] :
3093 model()->GetPickupAndDeliveryPairs()) {
3094 int64 performed_pickup = -1;
3095 for (
int64 pickup : pickups) {
3097 performed_pickup = pickup;
3101 int64 performed_delivery = -1;
3102 for (
int64 delivery : deliveries) {
3104 performed_delivery = delivery;
3108 if ((performed_pickup == -1) != (performed_delivery == -1)) {
3109 if (performed_pickup != -1) {
3110 to_make_unperformed[performed_pickup] =
true;
3112 if (performed_delivery != -1) {
3113 to_make_unperformed[performed_delivery] =
true;
3124 next = next_of_next;
3133 std::function<
int64(
int64)> penalty_evaluator,
3137 penalty_evaluator_(std::move(penalty_evaluator)) {}
3139 std::vector<std::vector<CheapestInsertionFilteredHeuristic::StartEndValue>>
3141 const std::vector<int>& vehicles) {
3142 std::vector<std::vector<StartEndValue>> start_end_distances_per_node(
3145 for (
int node = 0; node <
model()->
Size(); node++) {
3147 std::vector<StartEndValue>& start_end_distances =
3148 start_end_distances_per_node[node];
3150 for (
const int vehicle : vehicles) {
3155 const int64 distance =
3156 CapAdd(
model()->GetArcCostForVehicle(start, node, vehicle),
3157 model()->GetArcCostForVehicle(node, end, vehicle));
3158 start_end_distances.push_back({distance, vehicle});
3162 std::sort(start_end_distances.begin(), start_end_distances.end(),
3164 return second < first;
3167 return start_end_distances_per_node;
3170 template <
class Queue>
3172 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3173 Queue* priority_queue) {
3175 DCHECK_EQ(start_end_distances_per_node->size(), num_nodes);
3177 for (
int node = 0; node < num_nodes; node++) {
3179 std::vector<StartEndValue>& start_end_distances =
3180 (*start_end_distances_per_node)[node];
3181 if (start_end_distances.empty()) {
3185 const StartEndValue& start_end_value = start_end_distances.back();
3186 priority_queue->push(std::make_pair(start_end_value, node));
3187 start_end_distances.pop_back();
3201 std::vector<ValuedPosition>* valued_positions) {
3202 CHECK(valued_positions !=
nullptr);
3203 int64 insert_after = start;
3204 while (!
model()->IsEnd(insert_after)) {
3205 const int64 insert_before =
3206 (insert_after == start) ? next_after_start :
Value(insert_after);
3207 valued_positions->push_back(std::make_pair(
3209 insert_before, vehicle),
3211 insert_after = insert_before;
3217 int vehicle)
const {
3219 evaluator_(node_to_insert, insert_before, vehicle)),
3220 evaluator_(insert_after, insert_before, vehicle));
3224 int64 node_to_insert)
const {
3233 void SortAndExtractPairSeconds(std::vector<std::pair<int64, T>>* pairs,
3234 std::vector<T>* sorted_seconds) {
3235 CHECK(pairs !=
nullptr);
3236 CHECK(sorted_seconds !=
nullptr);
3237 std::sort(pairs->begin(), pairs->end());
3238 sorted_seconds->reserve(pairs->size());
3239 for (
const std::pair<int64, T>& p : *pairs) {
3240 sorted_seconds->push_back(p.second);
3264 if (value_ != other.value_) {
3265 return value_ > other.value_;
3267 if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
3268 return vehicle_ == -1;
3270 return std::tie(pickup_insert_after_, pickup_to_insert_,
3271 delivery_insert_after_, delivery_to_insert_, vehicle_) >
3272 std::tie(other.pickup_insert_after_, other.pickup_to_insert_,
3273 other.delivery_insert_after_, other.delivery_to_insert_,
3293 const int pickup_to_insert_;
3294 int pickup_insert_after_;
3295 const int delivery_to_insert_;
3296 const int delivery_insert_after_;
3311 if (value_ != other.value_) {
3312 return value_ > other.value_;
3314 if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
3315 return vehicle_ == -1;
3317 return std::tie(insert_after_, node_to_insert_, vehicle_) >
3318 std::tie(other.insert_after_, other.node_to_insert_, other.vehicle_);
3333 const int node_to_insert_;
3344 std::function<
int64(
int64)> penalty_evaluator,
3348 std::move(penalty_evaluator),
3351 node_index_to_vehicle_(
model->Size(), -1),
3352 empty_vehicle_type_curator_(nullptr) {
3357 if (NumNeighbors() >= NumNonStartEndNodes() - 1) {
3366 std::iota(all_nodes_.begin(), all_nodes_.end(), 0);
3370 void GlobalCheapestInsertionFilteredHeuristic::ComputeNeighborhoods() {
3372 !node_index_to_neighbors_by_cost_class_.empty()) {
3378 const int64 num_neighbors = NumNeighbors();
3381 DCHECK_LT(num_neighbors, NumNonStartEndNodes() - 1);
3383 const RoutingModel& routing_model = *
model();
3384 const int64 size = routing_model.Size();
3385 node_index_to_neighbors_by_cost_class_.resize(size);
3386 const int num_cost_classes = routing_model.GetCostClassesCount();
3387 for (
int64 node_index = 0; node_index < size; node_index++) {
3388 node_index_to_neighbors_by_cost_class_[node_index].resize(num_cost_classes);
3389 for (
int cc = 0; cc < num_cost_classes; cc++) {
3390 node_index_to_neighbors_by_cost_class_[node_index][cc] =
3391 absl::make_unique<SparseBitset<int64>>(size);
3395 for (
int64 node_index = 0; node_index < size; ++node_index) {
3396 DCHECK(!routing_model.IsEnd(node_index));
3397 if (routing_model.IsStart(node_index)) {
3404 for (
int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
3405 if (!routing_model.HasVehicleWithCostClassIndex(
3406 RoutingCostClassIndex(cost_class))) {
3410 std::vector<std::pair<
int64,
int64>> costed_after_nodes;
3411 costed_after_nodes.reserve(size);
3412 for (
int after_node = 0; after_node < size; ++after_node) {
3413 if (after_node != node_index && !routing_model.IsStart(after_node)) {
3414 costed_after_nodes.push_back(
3415 std::make_pair(routing_model.GetArcCostForClass(
3416 node_index, after_node, cost_class),
3420 std::nth_element(costed_after_nodes.begin(),
3421 costed_after_nodes.begin() + num_neighbors - 1,
3422 costed_after_nodes.end());
3423 costed_after_nodes.resize(num_neighbors);
3425 for (
auto [
cost, neighbor] : costed_after_nodes) {
3426 node_index_to_neighbors_by_cost_class_[node_index][cost_class]->Set(
3430 DCHECK(!routing_model.IsEnd(neighbor) &&
3431 !routing_model.IsStart(neighbor));
3432 node_index_to_neighbors_by_cost_class_[neighbor][cost_class]->Set(
3436 for (
int vehicle = 0; vehicle < routing_model.vehicles(); vehicle++) {
3437 const int64 vehicle_start = routing_model.Start(vehicle);
3438 node_index_to_neighbors_by_cost_class_[node_index][cost_class]->Set(
3440 node_index_to_neighbors_by_cost_class_[vehicle_start][cost_class]->Set(
3447 bool GlobalCheapestInsertionFilteredHeuristic::IsNeighborForCostClass(
3448 int cost_class,
int64 node_index,
int64 neighbor_index)
const {
3450 (*node_index_to_neighbors_by_cost_class_[node_index]
3451 [cost_class])[neighbor_index];
3454 bool GlobalCheapestInsertionFilteredHeuristic::CheckVehicleIndices()
const {
3455 std::vector<bool> node_is_visited(
model()->
Size(), -1);
3458 node =
Value(node)) {
3459 if (node_index_to_vehicle_[node] != v) {
3462 node_is_visited[node] =
true;
3466 for (
int node = 0; node <
model()->
Size(); node++) {
3467 if (!node_is_visited[node] && node_index_to_vehicle_[node] != -1) {
3476 ComputeNeighborhoods();
3477 if (empty_vehicle_type_curator_ ==
nullptr) {
3478 empty_vehicle_type_curator_ = absl::make_unique<VehicleTypeCurator>(
3479 model()->GetVehicleTypeContainer());
3482 empty_vehicle_type_curator_->Reset(
3487 std::vector<int> pairs_to_insert;
3488 absl::flat_hash_map<int, std::vector<int>> vehicle_to_pair_nodes;
3491 int pickup_vehicle = -1;
3492 for (
int64 pickup : index_pair.first) {
3494 pickup_vehicle = node_index_to_vehicle_[pickup];
3498 int delivery_vehicle = -1;
3499 for (
int64 delivery : index_pair.second) {
3501 delivery_vehicle = node_index_to_vehicle_[delivery];
3505 if (pickup_vehicle < 0 && delivery_vehicle < 0) {
3506 pairs_to_insert.push_back(
index);
3508 if (pickup_vehicle >= 0 && delivery_vehicle < 0) {
3509 std::vector<int>& pair_nodes = vehicle_to_pair_nodes[pickup_vehicle];
3510 for (
int64 delivery : index_pair.second) {
3511 pair_nodes.push_back(delivery);
3514 if (pickup_vehicle < 0 && delivery_vehicle >= 0) {
3515 std::vector<int>& pair_nodes = vehicle_to_pair_nodes[delivery_vehicle];
3516 for (
int64 pickup : index_pair.first) {
3517 pair_nodes.push_back(pickup);
3521 for (
const auto& vehicle_and_nodes : vehicle_to_pair_nodes) {
3522 InsertNodesOnRoutes(vehicle_and_nodes.second, {vehicle_and_nodes.first});
3525 InsertPairsAndNodesByRequirementTopologicalOrder();
3529 InsertPairs(pairs_to_insert);
3530 std::vector<int> nodes;
3531 for (
int node = 0; node <
model()->
Size(); ++node) {
3534 nodes.push_back(node);
3537 InsertFarthestNodesAsSeeds();
3539 SequentialInsertNodes(nodes);
3541 InsertNodesOnRoutes(nodes, {});
3544 DCHECK(CheckVehicleIndices());
3548 void GlobalCheapestInsertionFilteredHeuristic::
3549 InsertPairsAndNodesByRequirementTopologicalOrder() {
3550 for (
const std::vector<int>& types :
3551 model()->GetTopologicallySortedVisitTypes()) {
3552 for (
int type : types) {
3553 InsertPairs(
model()->GetPairIndicesOfType(type));
3554 InsertNodesOnRoutes(
model()->GetSingleNodesOfType(type), {});
3559 void GlobalCheapestInsertionFilteredHeuristic::InsertPairs(
3560 const std::vector<int>& pair_indices) {
3562 std::vector<PairEntries> pickup_to_entries;
3563 std::vector<PairEntries> delivery_to_entries;
3564 InitializePairPositions(pair_indices, &priority_queue, &pickup_to_entries,
3565 &delivery_to_entries);
3566 while (!priority_queue.
IsEmpty()) {
3568 for (PairEntry*
const entry : *priority_queue.
Raw()) {
3573 PairEntry*
const entry = priority_queue.
Top();
3574 const int64 pickup = entry->pickup_to_insert();
3575 const int64 delivery = entry->delivery_to_insert();
3577 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3578 &delivery_to_entries);
3582 const int entry_vehicle = entry->vehicle();
3583 if (entry_vehicle == -1) {
3588 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3589 &delivery_to_entries);
3595 if (InsertPairEntryUsingEmptyVehicleTypeCurator(
3596 pair_indices, entry, &priority_queue, &pickup_to_entries,
3597 &delivery_to_entries)) {
3603 const int64 pickup_insert_after = entry->pickup_insert_after();
3604 const int64 pickup_insert_before =
Value(pickup_insert_after);
3605 InsertBetween(pickup, pickup_insert_after, pickup_insert_before);
3607 const int64 delivery_insert_after = entry->delivery_insert_after();
3608 const int64 delivery_insert_before = (delivery_insert_after == pickup)
3609 ? pickup_insert_before
3610 :
Value(delivery_insert_after);
3611 InsertBetween(delivery, delivery_insert_after, delivery_insert_before);
3613 UpdateAfterPairInsertion(pair_indices, entry_vehicle, pickup,
3614 pickup_insert_after, delivery,
3615 delivery_insert_after, &priority_queue,
3616 &pickup_to_entries, &delivery_to_entries);
3618 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3619 &delivery_to_entries);
3624 bool GlobalCheapestInsertionFilteredHeuristic::
3625 InsertPairEntryUsingEmptyVehicleTypeCurator(
3626 const std::vector<int>& pair_indices,
3627 GlobalCheapestInsertionFilteredHeuristic::PairEntry*
const pair_entry,
3629 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
3631 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
3633 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
3634 delivery_to_entries) {
3635 const int entry_vehicle = pair_entry->vehicle();
3644 const int64 pickup = pair_entry->pickup_to_insert();
3645 const int64 delivery = pair_entry->delivery_to_insert();
3647 auto vehicle_is_compatible = [
this, entry_fixed_cost, pickup,
3648 delivery](
int vehicle) {
3663 auto stop_and_return_vehicle = [
this, entry_fixed_cost](
int vehicle) {
3666 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
3667 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
3668 empty_vehicle_type_curator_->Type(entry_vehicle),
3669 vehicle_is_compatible, stop_and_return_vehicle);
3670 if (compatible_vehicle >= 0) {
3673 const int num_previous_vehicle_entries =
3674 pickup_to_entries->at(vehicle_start).size() +
3675 delivery_to_entries->at(vehicle_start).size();
3676 UpdateAfterPairInsertion(pair_indices, compatible_vehicle, pickup,
3677 vehicle_start, delivery, pickup, priority_queue,
3678 pickup_to_entries, delivery_to_entries);
3679 if (compatible_vehicle != entry_vehicle) {
3685 DCHECK_EQ(num_previous_vehicle_entries, 0);
3691 const int new_empty_vehicle =
3692 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
3693 empty_vehicle_type_curator_->Type(compatible_vehicle));
3695 if (new_empty_vehicle >= 0) {
3699 UpdatePairPositions(pair_indices, new_empty_vehicle,
3700 model()->Start(new_empty_vehicle), priority_queue,
3701 pickup_to_entries, delivery_to_entries);
3703 }
else if (next_fixed_cost_empty_vehicle >= 0) {
3710 pair_entry->set_vehicle(next_fixed_cost_empty_vehicle);
3711 pickup_to_entries->at(pair_entry->pickup_insert_after()).erase(pair_entry);
3712 pair_entry->set_pickup_insert_after(
3713 model()->Start(next_fixed_cost_empty_vehicle));
3714 pickup_to_entries->at(pair_entry->pickup_insert_after()).insert(pair_entry);
3715 DCHECK_EQ(pair_entry->delivery_insert_after(), pickup);
3716 UpdatePairEntry(pair_entry, priority_queue);
3718 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
3719 delivery_to_entries);
3725 void GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(
3726 const std::vector<int>& nodes,
const absl::flat_hash_set<int>& vehicles) {
3728 std::vector<NodeEntries> position_to_node_entries;
3729 InitializePositions(nodes, vehicles, &priority_queue,
3730 &position_to_node_entries);
3736 const bool all_vehicles =
3739 while (!priority_queue.
IsEmpty()) {
3740 NodeEntry*
const node_entry = priority_queue.
Top();
3742 for (NodeEntry*
const entry : *priority_queue.
Raw()) {
3747 const int64 node_to_insert = node_entry->node_to_insert();
3749 DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3753 const int entry_vehicle = node_entry->vehicle();
3754 if (entry_vehicle == -1) {
3757 SetValue(node_to_insert, node_to_insert);
3759 DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3765 if (InsertNodeEntryUsingEmptyVehicleTypeCurator(
3766 nodes, all_vehicles, node_entry, &priority_queue,
3767 &position_to_node_entries)) {
3772 const int64 insert_after = node_entry->insert_after();
3775 UpdatePositions(nodes, entry_vehicle, node_to_insert, all_vehicles,
3776 &priority_queue, &position_to_node_entries);
3777 UpdatePositions(nodes, entry_vehicle, insert_after, all_vehicles,
3778 &priority_queue, &position_to_node_entries);
3779 SetVehicleIndex(node_to_insert, entry_vehicle);
3781 DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3786 bool GlobalCheapestInsertionFilteredHeuristic::
3787 InsertNodeEntryUsingEmptyVehicleTypeCurator(
3788 const std::vector<int>& nodes,
bool all_vehicles,
3789 GlobalCheapestInsertionFilteredHeuristic::NodeEntry*
const node_entry,
3791 GlobalCheapestInsertionFilteredHeuristic::NodeEntry>*
3793 std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
3794 position_to_node_entries) {
3795 const int entry_vehicle = node_entry->vehicle();
3796 if (entry_vehicle == -1 || !all_vehicles || !
VehicleIsEmpty(entry_vehicle)) {
3805 const int64 node_to_insert = node_entry->node_to_insert();
3807 auto vehicle_is_compatible = [
this, entry_fixed_cost,
3808 node_to_insert](
int vehicle) {
3815 model()->End(vehicle));
3822 auto stop_and_return_vehicle = [
this, entry_fixed_cost](
int vehicle) {
3825 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
3826 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
3827 empty_vehicle_type_curator_->Type(entry_vehicle),
3828 vehicle_is_compatible, stop_and_return_vehicle);
3829 if (compatible_vehicle >= 0) {
3831 UpdatePositions(nodes, compatible_vehicle, node_to_insert, all_vehicles,
3832 priority_queue, position_to_node_entries);
3834 const bool no_prior_entries_for_this_vehicle =
3835 position_to_node_entries->at(compatible_start).empty();
3836 UpdatePositions(nodes, compatible_vehicle, compatible_start, all_vehicles,
3837 priority_queue, position_to_node_entries);
3838 SetVehicleIndex(node_to_insert, compatible_vehicle);
3839 if (compatible_vehicle != entry_vehicle) {
3845 DCHECK(no_prior_entries_for_this_vehicle);
3851 const int new_empty_vehicle =
3852 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
3853 empty_vehicle_type_curator_->Type(compatible_vehicle));
3855 if (new_empty_vehicle >= 0) {
3859 UpdatePositions(nodes, new_empty_vehicle,
3860 model()->Start(new_empty_vehicle), all_vehicles,
3861 priority_queue, position_to_node_entries);
3863 }
else if (next_fixed_cost_empty_vehicle >= 0) {
3870 position_to_node_entries->at(node_entry->insert_after()).erase(node_entry);
3871 node_entry->set_insert_after(
model()->Start(next_fixed_cost_empty_vehicle));
3872 position_to_node_entries->at(node_entry->insert_after()).insert(node_entry);
3873 node_entry->set_vehicle(next_fixed_cost_empty_vehicle);
3874 UpdateNodeEntry(node_entry, priority_queue);
3876 DeleteNodeEntry(node_entry, priority_queue, position_to_node_entries);
3882 void GlobalCheapestInsertionFilteredHeuristic::SequentialInsertNodes(
3883 const std::vector<int>& nodes) {
3884 std::vector<bool> is_vehicle_used;
3885 absl::flat_hash_set<int> used_vehicles;
3886 std::vector<int> unused_vehicles;
3888 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
3889 if (!used_vehicles.empty()) {
3890 InsertNodesOnRoutes(nodes, used_vehicles);
3893 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
3895 std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed>>
3899 int vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
3902 while (vehicle >= 0) {
3903 InsertNodesOnRoutes(nodes, {vehicle});
3904 vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
3909 void GlobalCheapestInsertionFilteredHeuristic::DetectUsedVehicles(
3910 std::vector<bool>* is_vehicle_used, std::vector<int>* unused_vehicles,
3911 absl::flat_hash_set<int>* used_vehicles) {
3912 is_vehicle_used->clear();
3913 is_vehicle_used->resize(
model()->vehicles());
3915 used_vehicles->clear();
3916 used_vehicles->reserve(
model()->vehicles());
3918 unused_vehicles->clear();
3919 unused_vehicles->reserve(
model()->vehicles());
3921 for (
int vehicle = 0; vehicle <
model()->
vehicles(); vehicle++) {
3923 (*is_vehicle_used)[vehicle] =
true;
3924 used_vehicles->insert(vehicle);
3926 (*is_vehicle_used)[vehicle] =
false;
3927 unused_vehicles->push_back(vehicle);
3932 void GlobalCheapestInsertionFilteredHeuristic::InsertFarthestNodesAsSeeds() {
3935 const int num_seeds =
static_cast<int>(
3938 std::vector<bool> is_vehicle_used;
3939 absl::flat_hash_set<int> used_vehicles;
3940 std::vector<int> unused_vehicles;
3941 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
3942 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
3947 std::priority_queue<Seed> farthest_node_queue;
3950 int inserted_seeds = 0;
3951 while (!farthest_node_queue.empty() && inserted_seeds < num_seeds) {
3952 InsertSeedNode(&start_end_distances_per_node, &farthest_node_queue,
3961 DCHECK(empty_vehicle_type_curator_ !=
nullptr);
3962 empty_vehicle_type_curator_->Update(
3966 template <
class Queue>
3967 int GlobalCheapestInsertionFilteredHeuristic::InsertSeedNode(
3968 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3969 Queue* priority_queue, std::vector<bool>* is_vehicle_used) {
3970 while (!priority_queue->empty()) {
3972 const Seed& seed = priority_queue->top();
3974 const int seed_node = seed.second;
3975 const int seed_vehicle = seed.first.vehicle;
3977 std::vector<StartEndValue>& other_start_end_values =
3978 (*start_end_distances_per_node)[seed_node];
3983 priority_queue->pop();
3984 other_start_end_values.clear();
3987 if (!(*is_vehicle_used)[seed_vehicle]) {
3994 priority_queue->pop();
3995 (*is_vehicle_used)[seed_vehicle] =
true;
3996 other_start_end_values.clear();
3997 SetVehicleIndex(seed_node, seed_vehicle);
3998 return seed_vehicle;
4005 priority_queue->pop();
4006 if (!other_start_end_values.empty()) {
4007 const StartEndValue& next_seed_value = other_start_end_values.back();
4008 priority_queue->push(std::make_pair(next_seed_value, seed_node));
4009 other_start_end_values.pop_back();
4016 void GlobalCheapestInsertionFilteredHeuristic::InitializePairPositions(
4017 const std::vector<int>& pair_indices,
4019 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4020 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4022 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4023 delivery_to_entries) {
4024 priority_queue->Clear();
4025 pickup_to_entries->clear();
4026 pickup_to_entries->resize(
model()->
Size());
4027 delivery_to_entries->clear();
4028 delivery_to_entries->resize(
model()->
Size());
4031 for (
int index : pair_indices) {
4033 for (
int64 pickup : index_pair.first) {
4035 for (
int64 delivery : index_pair.second) {
4042 index_pair.first.size() == 1 && index_pair.second.size() == 1 &&
4045 AddPairEntry(pickup, -1, delivery, -1, -1, priority_queue,
nullptr,
4049 InitializeInsertionEntriesPerformingPair(
4050 pickup, delivery, priority_queue, pickup_to_entries,
4051 delivery_to_entries);
4057 void GlobalCheapestInsertionFilteredHeuristic::
4058 InitializeInsertionEntriesPerformingPair(
4061 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
4063 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4065 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4066 delivery_to_entries) {
4068 std::vector<std::pair<std::pair<int64, int>, std::pair<int64, int64>>>
4070 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
4072 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4073 empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4079 std::vector<ValuedPosition> valued_pickup_positions;
4081 &valued_pickup_positions);
4083 valued_pickup_positions) {
4084 const int64 pickup_position = valued_pickup_position.second;
4086 std::vector<ValuedPosition> valued_delivery_positions;
4088 vehicle, &valued_delivery_positions);
4090 valued_delivery_positions) {
4091 valued_positions.push_back(std::make_pair(
4092 std::make_pair(
CapAdd(valued_pickup_position.first,
4093 valued_delivery_position.first),
4095 std::make_pair(pickup_position,
4096 valued_delivery_position.second)));
4100 for (
const auto& [cost_for_vehicle, pair_positions] : valued_positions) {
4101 DCHECK_NE(pair_positions.first, pair_positions.second);
4102 AddPairEntry(pickup, pair_positions.first, delivery,
4103 pair_positions.second, cost_for_vehicle.second,
4104 priority_queue, pickup_to_entries, delivery_to_entries);
4113 absl::flat_hash_set<std::pair<int64, int64>> existing_insertion_positions;
4115 for (
const int64 pickup_insert_after :
4116 GetNeighborsOfNodeForCostClass(cost_class, pickup)) {
4117 if (!
Contains(pickup_insert_after)) {
4120 const int vehicle = node_index_to_vehicle_[pickup_insert_after];
4126 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4127 empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4133 int64 delivery_insert_after = pickup;
4134 while (!
model()->
IsEnd(delivery_insert_after)) {
4135 const std::pair<int64, int64> insertion_position = {
4136 pickup_insert_after, delivery_insert_after};
4138 insertion_position));
4139 existing_insertion_positions.insert(insertion_position);
4141 AddPairEntry(pickup, pickup_insert_after, delivery,
4142 delivery_insert_after, vehicle, priority_queue,
4143 pickup_to_entries, delivery_to_entries);
4144 delivery_insert_after = (delivery_insert_after == pickup)
4145 ?
Value(pickup_insert_after)
4146 :
Value(delivery_insert_after);
4151 for (
const int64 delivery_insert_after :
4152 GetNeighborsOfNodeForCostClass(cost_class, delivery)) {
4153 if (!
Contains(delivery_insert_after)) {
4156 const int vehicle = node_index_to_vehicle_[delivery_insert_after];
4157 if (
model()->GetCostClassIndexOfVehicle(vehicle).
value() != cost_class) {
4167 while (pickup_insert_after != delivery_insert_after) {
4169 existing_insertion_positions,
4170 std::make_pair(pickup_insert_after, delivery_insert_after))) {
4171 AddPairEntry(pickup, pickup_insert_after, delivery,
4172 delivery_insert_after, vehicle, priority_queue,
4173 pickup_to_entries, delivery_to_entries);
4175 pickup_insert_after =
Value(pickup_insert_after);
4181 void GlobalCheapestInsertionFilteredHeuristic::UpdateAfterPairInsertion(
4182 const std::vector<int>& pair_indices,
int vehicle,
int64 pickup,
4185 std::vector<PairEntries>* pickup_to_entries,
4186 std::vector<PairEntries>* delivery_to_entries) {
4187 UpdatePairPositions(pair_indices, vehicle, pickup_position, priority_queue,
4188 pickup_to_entries, delivery_to_entries);
4189 UpdatePairPositions(pair_indices, vehicle, pickup, priority_queue,
4190 pickup_to_entries, delivery_to_entries);
4191 UpdatePairPositions(pair_indices, vehicle, delivery, priority_queue,
4192 pickup_to_entries, delivery_to_entries);
4193 if (delivery_position != pickup) {
4194 UpdatePairPositions(pair_indices, vehicle, delivery_position,
4195 priority_queue, pickup_to_entries, delivery_to_entries);
4197 SetVehicleIndex(pickup, vehicle);
4198 SetVehicleIndex(delivery, vehicle);
4201 void GlobalCheapestInsertionFilteredHeuristic::UpdatePickupPositions(
4202 const std::vector<int>& pair_indices,
int vehicle,
4203 int64 pickup_insert_after,
4205 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4206 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4208 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4209 delivery_to_entries) {
4212 using Pair = std::pair<int64, int64>;
4213 using Insertion = std::pair<Pair,
int64>;
4214 absl::flat_hash_set<Insertion> existing_insertions;
4215 std::vector<PairEntry*> to_remove;
4216 for (PairEntry*
const pair_entry :
4217 pickup_to_entries->at(pickup_insert_after)) {
4219 DCHECK_EQ(pair_entry->pickup_insert_after(), pickup_insert_after);
4220 if (
Contains(pair_entry->pickup_to_insert()) ||
4221 Contains(pair_entry->delivery_to_insert())) {
4222 to_remove.push_back(pair_entry);
4224 DCHECK(delivery_to_entries->at(pair_entry->delivery_insert_after())
4225 .contains(pair_entry));
4226 UpdatePairEntry(pair_entry, priority_queue);
4227 existing_insertions.insert(
4228 {{pair_entry->pickup_to_insert(), pair_entry->delivery_to_insert()},
4229 pair_entry->delivery_insert_after()});
4232 for (PairEntry*
const pair_entry : to_remove) {
4233 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
4234 delivery_to_entries);
4239 const int64 pickup_insert_before =
Value(pickup_insert_after);
4242 for (
int pair_index : pair_indices) {
4244 pickup_delivery_pairs[pair_index];
4245 for (
int64 pickup : index_pair.first) {
4247 !IsNeighborForCostClass(cost_class, pickup_insert_after, pickup)) {
4250 for (
int64 delivery : index_pair.second) {
4254 int64 delivery_insert_after = pickup;
4255 while (!
model()->IsEnd(delivery_insert_after)) {
4256 const Insertion insertion = {{pickup, delivery},
4257 delivery_insert_after};
4259 AddPairEntry(pickup, pickup_insert_after, delivery,
4260 delivery_insert_after, vehicle, priority_queue,
4261 pickup_to_entries, delivery_to_entries);
4263 if (delivery_insert_after == pickup) {
4264 delivery_insert_after = pickup_insert_before;
4266 delivery_insert_after =
Value(delivery_insert_after);
4274 void GlobalCheapestInsertionFilteredHeuristic::UpdateDeliveryPositions(
4275 const std::vector<int>& pair_indices,
int vehicle,
4276 int64 delivery_insert_after,
4278 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4279 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4281 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4282 delivery_to_entries) {
4285 using Pair = std::pair<int64, int64>;
4286 using Insertion = std::pair<Pair,
int64>;
4287 absl::flat_hash_set<Insertion> existing_insertions;
4288 std::vector<PairEntry*> to_remove;
4289 for (PairEntry*
const pair_entry :
4290 delivery_to_entries->at(delivery_insert_after)) {
4292 DCHECK_EQ(pair_entry->delivery_insert_after(), delivery_insert_after);
4293 if (
Contains(pair_entry->pickup_to_insert()) ||
4294 Contains(pair_entry->delivery_to_insert())) {
4295 to_remove.push_back(pair_entry);
4297 DCHECK(pickup_to_entries->at(pair_entry->pickup_insert_after())
4298 .contains(pair_entry));
4299 existing_insertions.insert(
4300 {{pair_entry->pickup_to_insert(), pair_entry->delivery_to_insert()},
4301 pair_entry->pickup_insert_after()});
4302 UpdatePairEntry(pair_entry, priority_queue);
4305 for (PairEntry*
const pair_entry : to_remove) {
4306 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
4307 delivery_to_entries);
4314 for (
int pair_index : pair_indices) {
4316 pickup_delivery_pairs[pair_index];
4317 for (
int64 delivery : index_pair.second) {
4319 !IsNeighborForCostClass(cost_class, delivery_insert_after,
4323 for (
int64 pickup : index_pair.first) {
4328 while (pickup_insert_after != delivery_insert_after) {
4329 const Insertion insertion = {{pickup, delivery}, pickup_insert_after};
4331 AddPairEntry(pickup, pickup_insert_after, delivery,
4332 delivery_insert_after, vehicle, priority_queue,
4333 pickup_to_entries, delivery_to_entries);
4335 pickup_insert_after =
Value(pickup_insert_after);
4342 void GlobalCheapestInsertionFilteredHeuristic::DeletePairEntry(
4343 GlobalCheapestInsertionFilteredHeuristic::PairEntry* entry,
4345 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4346 std::vector<PairEntries>* pickup_to_entries,
4347 std::vector<PairEntries>* delivery_to_entries) {
4348 priority_queue->
Remove(entry);
4349 if (entry->pickup_insert_after() != -1) {
4350 pickup_to_entries->at(entry->pickup_insert_after()).erase(entry);
4352 if (entry->delivery_insert_after() != -1) {
4353 delivery_to_entries->at(entry->delivery_insert_after()).erase(entry);
4358 void GlobalCheapestInsertionFilteredHeuristic::AddPairEntry(
4360 int64 delivery_insert_after,
int vehicle,
4362 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4363 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4365 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4366 delivery_entries)
const {
4367 if (pickup_insert_after == -1) {
4370 PairEntry* pair_entry =
new PairEntry(pickup, -1, delivery, -1, -1);
4371 pair_entry->set_value(
4372 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4376 priority_queue->
Add(pair_entry);
4380 PairEntry*
const pair_entry =
new PairEntry(
4381 pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle);
4382 pair_entry->set_value(GetInsertionValueForPairAtPositions(
4383 pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle));
4387 pickup_entries->at(pickup_insert_after).insert(pair_entry);
4388 delivery_entries->at(delivery_insert_after).insert(pair_entry);
4389 priority_queue->
Add(pair_entry);
4392 void GlobalCheapestInsertionFilteredHeuristic::UpdatePairEntry(
4393 GlobalCheapestInsertionFilteredHeuristic::PairEntry*
const pair_entry,
4395 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue)
4397 pair_entry->set_value(GetInsertionValueForPairAtPositions(
4398 pair_entry->pickup_to_insert(), pair_entry->pickup_insert_after(),
4399 pair_entry->delivery_to_insert(), pair_entry->delivery_insert_after(),
4400 pair_entry->vehicle()));
4407 int64 GlobalCheapestInsertionFilteredHeuristic::
4408 GetInsertionValueForPairAtPositions(
int64 pickup,
int64 pickup_insert_after,
4410 int64 delivery_insert_after,
4411 int vehicle)
const {
4413 const int64 pickup_insert_before =
Value(pickup_insert_after);
4415 pickup, pickup_insert_after, pickup_insert_before, vehicle);
4418 const int64 delivery_insert_before = (delivery_insert_after == pickup)
4419 ? pickup_insert_before
4420 :
Value(delivery_insert_after);
4422 delivery, delivery_insert_after, delivery_insert_before, vehicle);
4424 const int64 penalty_shift =
4425 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4428 return CapSub(
CapAdd(pickup_value, delivery_value), penalty_shift);
4431 void GlobalCheapestInsertionFilteredHeuristic::InitializePositions(
4432 const std::vector<int>& nodes,
const absl::flat_hash_set<int>& vehicles,
4434 GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4435 std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4436 position_to_node_entries) {
4437 priority_queue->
Clear();
4438 position_to_node_entries->clear();
4439 position_to_node_entries->resize(
model()->
Size());
4441 const int num_vehicles =
4443 const bool all_vehicles = (num_vehicles ==
model()->
vehicles());
4445 for (
int node : nodes) {
4452 AddNodeEntry(node, -1, -1, all_vehicles, priority_queue,
nullptr);
4455 InitializeInsertionEntriesPerformingNode(node, vehicles, priority_queue,
4456 position_to_node_entries);
4460 void GlobalCheapestInsertionFilteredHeuristic::
4461 InitializeInsertionEntriesPerformingNode(
4462 int64 node,
const absl::flat_hash_set<int>& vehicles,
4464 GlobalCheapestInsertionFilteredHeuristic::NodeEntry>*
4466 std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4467 position_to_node_entries) {
4468 const int num_vehicles =
4470 const bool all_vehicles = (num_vehicles ==
model()->
vehicles());
4473 auto vehicles_it = vehicles.begin();
4474 for (
int v = 0; v < num_vehicles; v++) {
4475 const int vehicle = vehicles.empty() ? v : *vehicles_it++;
4479 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4480 empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4485 std::vector<ValuedPosition> valued_positions;
4488 for (
const std::pair<int64, int64>& valued_position : valued_positions) {
4489 AddNodeEntry(node, valued_position.second, vehicle, all_vehicles,
4490 priority_queue, position_to_node_entries);
4498 const auto insert_on_vehicle_for_cost_class = [
this, &vehicles, all_vehicles](
4499 int v,
int cost_class) {
4501 (all_vehicles || vehicles.contains(v));
4505 for (
const int64 insert_after :
4506 GetNeighborsOfNodeForCostClass(cost_class, node)) {
4510 const int vehicle = node_index_to_vehicle_[insert_after];
4511 if (vehicle == -1 ||
4512 !insert_on_vehicle_for_cost_class(vehicle, cost_class)) {
4516 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4517 empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4522 AddNodeEntry(node, insert_after, vehicle, all_vehicles, priority_queue,
4523 position_to_node_entries);
4528 void GlobalCheapestInsertionFilteredHeuristic::UpdatePositions(
4529 const std::vector<int>& nodes,
int vehicle,
int64 insert_after,
4532 GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4533 std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4537 std::vector<NodeEntry*> to_remove;
4538 absl::flat_hash_set<int> existing_insertions;
4539 for (NodeEntry*
const node_entry : node_entries->at(insert_after)) {
4540 DCHECK_EQ(node_entry->insert_after(), insert_after);
4541 const int64 node_to_insert = node_entry->node_to_insert();
4543 to_remove.push_back(node_entry);
4545 UpdateNodeEntry(node_entry, priority_queue);
4546 existing_insertions.insert(node_to_insert);
4549 for (NodeEntry*
const node_entry : to_remove) {
4550 DeleteNodeEntry(node_entry, priority_queue, node_entries);
4553 for (
int node_to_insert : nodes) {
4555 !existing_insertions.contains(node_to_insert) &&
4556 IsNeighborForCostClass(cost_class, insert_after, node_to_insert)) {
4557 AddNodeEntry(node_to_insert, insert_after, vehicle, all_vehicles,
4558 priority_queue, node_entries);
4563 void GlobalCheapestInsertionFilteredHeuristic::DeleteNodeEntry(
4564 GlobalCheapestInsertionFilteredHeuristic::NodeEntry* entry,
4566 GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4567 std::vector<NodeEntries>* node_entries) {
4568 priority_queue->
Remove(entry);
4569 if (entry->insert_after() != -1) {
4570 node_entries->at(entry->insert_after()).erase(entry);
4575 void GlobalCheapestInsertionFilteredHeuristic::AddNodeEntry(
4576 int64 node,
int64 insert_after,
int vehicle,
bool all_vehicles,
4578 std::vector<NodeEntries>* node_entries)
const {
4580 const int64 penalty_shift =
4581 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4584 if (insert_after == -1) {
4586 if (!all_vehicles) {
4592 NodeEntry*
const node_entry =
new NodeEntry(node, -1, -1);
4593 node_entry->set_value(
CapSub(node_penalty, penalty_shift));
4594 priority_queue->
Add(node_entry);
4599 node, insert_after,
Value(insert_after), vehicle);
4600 if (!all_vehicles && insertion_cost > node_penalty) {
4607 NodeEntry*
const node_entry =
new NodeEntry(node, insert_after, vehicle);
4608 node_entry->set_value(
CapSub(insertion_cost, penalty_shift));
4611 node_entries->at(insert_after).insert(node_entry);
4612 priority_queue->
Add(node_entry);
4615 void GlobalCheapestInsertionFilteredHeuristic::UpdateNodeEntry(
4616 NodeEntry*
const node_entry,
4618 const int64 node = node_entry->node_to_insert();
4619 const int64 insert_after = node_entry->insert_after();
4622 node, insert_after,
Value(insert_after), node_entry->vehicle());
4623 const int64 penalty_shift =
4624 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4628 node_entry->set_value(
CapSub(insertion_cost, penalty_shift));
4644 std::iota(std::begin(all_vehicles), std::end(all_vehicles), 0);
4646 start_end_distances_per_node_ =
4652 std::vector<bool> visited(
model()->
Size(),
false);
4654 std::vector<int64> insertion_positions;
4657 std::vector<int64> delivery_insertion_positions;
4661 for (
const auto& index_pair : index_pairs) {
4662 for (
int64 pickup : index_pair.first) {
4666 for (
int64 delivery : index_pair.second) {
4673 visited[pickup] =
true;
4674 visited[delivery] =
true;
4675 ComputeEvaluatorSortedPositions(pickup, &insertion_positions);
4676 for (
const int64 pickup_insertion : insertion_positions) {
4677 const int pickup_insertion_next =
Value(pickup_insertion);
4678 ComputeEvaluatorSortedPositionsOnRouteAfter(
4679 delivery, pickup, pickup_insertion_next,
4680 &delivery_insertion_positions);
4682 for (
const int64 delivery_insertion : delivery_insertion_positions) {
4683 InsertBetween(pickup, pickup_insertion, pickup_insertion_next);
4684 const int64 delivery_insertion_next =
4685 (delivery_insertion == pickup_insertion) ? pickup
4686 : (delivery_insertion == pickup) ? pickup_insertion_next
4687 :
Value(delivery_insertion);
4689 delivery_insertion_next);
4703 std::priority_queue<Seed> node_queue;
4706 while (!node_queue.empty()) {
4707 const int node = node_queue.top().second;
4709 if (
Contains(node) || visited[node])
continue;
4710 ComputeEvaluatorSortedPositions(node, &insertion_positions);
4711 for (
const int64 insertion : insertion_positions) {
4723 void LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPositions(
4724 int64 node, std::vector<int64>* sorted_positions) {
4725 CHECK(sorted_positions !=
nullptr);
4727 sorted_positions->clear();
4730 std::vector<std::pair<int64, int64>> valued_positions;
4731 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
4736 SortAndExtractPairSeconds(&valued_positions, sorted_positions);
4740 void LocalCheapestInsertionFilteredHeuristic::
4741 ComputeEvaluatorSortedPositionsOnRouteAfter(
4743 std::vector<int64>* sorted_positions) {
4744 CHECK(sorted_positions !=
nullptr);
4746 sorted_positions->clear();
4750 std::vector<std::pair<int64, int64>> valued_positions;
4753 SortAndExtractPairSeconds(&valued_positions, sorted_positions);
4766 std::vector<std::vector<int64>> deliveries(
Size());
4767 std::vector<std::vector<int64>> pickups(
Size());
4769 for (
int first : pair.first) {
4770 for (
int second : pair.second) {
4771 deliveries[first].push_back(second);
4772 pickups[second].push_back(first);
4779 std::vector<int> sorted_vehicles(
model()->vehicles(), 0);
4780 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
4781 sorted_vehicles[vehicle] = vehicle;
4783 std::sort(sorted_vehicles.begin(), sorted_vehicles.end(),
4784 PartialRoutesAndLargeVehicleIndicesFirst(*
this));
4786 for (
const int vehicle : sorted_vehicles) {
4788 bool extend_route =
true;
4793 while (extend_route) {
4794 extend_route =
false;
4805 std::vector<int64> neighbors;
4807 std::unique_ptr<IntVarIterator> it(
4808 model()->Nexts()[
index]->MakeDomainIterator(
false));
4810 neighbors = GetPossibleNextsFromIterator(
index, next_values.begin(),
4813 for (
int i = 0; !found && i < neighbors.size(); ++i) {
4817 next = FindTopSuccessor(
index, neighbors);
4820 SortSuccessors(
index, &neighbors);
4821 ABSL_FALLTHROUGH_INTENDED;
4823 next = neighbors[i];
4830 bool contains_pickups =
false;
4833 contains_pickups =
true;
4837 if (!contains_pickups) {
4841 std::vector<int64> next_deliveries;
4842 if (
next < deliveries.size()) {
4843 next_deliveries = GetPossibleNextsFromIterator(
4844 next, deliveries[
next].begin(), deliveries[
next].end());
4846 if (next_deliveries.empty()) next_deliveries = {
kUnassigned};
4847 for (
int j = 0; !found && j < next_deliveries.size(); ++j) {
4852 delivery = FindTopSuccessor(
next, next_deliveries);
4855 SortSuccessors(
next, &next_deliveries);
4856 ABSL_FALLTHROUGH_INTENDED;
4858 delivery = next_deliveries[j];
4876 if (
model()->IsEnd(end) && last_node != delivery) {
4877 last_node = delivery;
4878 extend_route =
true;
4893 bool CheapestAdditionFilteredHeuristic::
4894 PartialRoutesAndLargeVehicleIndicesFirst::operator()(
int vehicle1,
4895 int vehicle2)
const {
4896 const bool has_partial_route1 = (builder_.model()->Start(vehicle1) !=
4897 builder_.GetStartChainEnd(vehicle1));
4898 const bool has_partial_route2 = (builder_.model()->Start(vehicle2) !=
4899 builder_.GetStartChainEnd(vehicle2));
4900 if (has_partial_route1 == has_partial_route2) {
4901 return vehicle2 < vehicle1;
4903 return has_partial_route2 < has_partial_route1;
4916 int64 EvaluatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
4917 int64 node,
const std::vector<int64>& successors) {
4919 int64 best_successor = -1;
4920 for (
int64 successor : successors) {
4921 const int64 evaluation =
4922 (successor >= 0) ? evaluator_(node, successor) :
kint64max;
4923 if (evaluation < best_evaluation ||
4924 (evaluation == best_evaluation && successor > best_successor)) {
4925 best_evaluation = evaluation;
4926 best_successor = successor;
4929 return best_successor;
4932 void EvaluatorCheapestAdditionFilteredHeuristic::SortSuccessors(
4933 int64 node, std::vector<int64>* successors) {
4934 std::vector<std::pair<int64, int64>> values;
4935 values.reserve(successors->size());
4936 for (
int64 successor : *successors) {
4939 values.push_back({evaluator_(node, successor), -successor});
4941 std::sort(values.begin(), values.end());
4942 successors->clear();
4943 for (
auto value : values) {
4944 successors->push_back(-
value.second);
4955 comparator_(std::move(comparator)) {}
4957 int64 ComparatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
4958 int64 node,
const std::vector<int64>& successors) {
4959 return *std::min_element(successors.begin(), successors.end(),
4960 [
this, node](
int successor1,
int successor2) {
4961 return comparator_(node, successor1, successor2);
4965 void ComparatorCheapestAdditionFilteredHeuristic::SortSuccessors(
4966 int64 node, std::vector<int64>* successors) {
4967 std::sort(successors->begin(), successors->end(),
4968 [
this, node](
int successor1,
int successor2) {
4969 return comparator_(node, successor1, successor2);
5021 template <
typename Saving>
5026 : savings_db_(savings_db),
5027 vehicle_types_(vehicle_types),
5028 index_in_sorted_savings_(0),
5029 single_vehicle_type_(vehicle_types == 1),
5030 using_incoming_reinjected_saving_(false),
5035 sorted_savings_per_vehicle_type_.clear();
5036 sorted_savings_per_vehicle_type_.resize(vehicle_types_);
5037 for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
5038 savings.reserve(size * saving_neighbors);
5041 sorted_savings_.clear();
5042 costs_and_savings_per_arc_.clear();
5043 arc_indices_per_before_node_.clear();
5045 if (!single_vehicle_type_) {
5046 costs_and_savings_per_arc_.reserve(size * saving_neighbors);
5047 arc_indices_per_before_node_.resize(size);
5048 for (
int before_node = 0; before_node < size; before_node++) {
5049 arc_indices_per_before_node_[before_node].reserve(saving_neighbors);
5052 skipped_savings_starting_at_.clear();
5053 skipped_savings_starting_at_.resize(size);
5054 skipped_savings_ending_at_.clear();
5055 skipped_savings_ending_at_.resize(size);
5056 incoming_reinjected_savings_ =
nullptr;
5057 outgoing_reinjected_savings_ =
nullptr;
5058 incoming_new_reinjected_savings_ =
nullptr;
5059 outgoing_new_reinjected_savings_ =
nullptr;
5063 int64 after_node,
int vehicle_type) {
5064 CHECK(!sorted_savings_per_vehicle_type_.empty())
5065 <<
"Container not initialized!";
5066 sorted_savings_per_vehicle_type_[vehicle_type].push_back(saving);
5067 UpdateArcIndicesCostsAndSavings(before_node, after_node,
5068 {total_cost, saving});
5072 CHECK(!sorted_) <<
"Container already sorted!";
5074 for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
5075 std::sort(savings.begin(), savings.end());
5078 if (single_vehicle_type_) {
5079 const auto& savings = sorted_savings_per_vehicle_type_[0];
5080 sorted_savings_.resize(savings.size());
5081 std::transform(savings.begin(), savings.end(), sorted_savings_.begin(),
5082 [](
const Saving& saving) {
5083 return SavingAndArc({saving, -1});
5089 sorted_savings_.reserve(vehicle_types_ *
5090 costs_and_savings_per_arc_.size());
5092 for (
int arc_index = 0; arc_index < costs_and_savings_per_arc_.size();
5094 std::vector<std::pair<int64, Saving>>& costs_and_savings =
5095 costs_and_savings_per_arc_[arc_index];
5096 DCHECK(!costs_and_savings.empty());
5099 costs_and_savings.begin(), costs_and_savings.end(),
5100 [](
const std::pair<int64, Saving>& cs1,
5101 const std::pair<int64, Saving>& cs2) { return cs1 > cs2; });
5106 const int64 cost = costs_and_savings.back().first;
5107 while (!costs_and_savings.empty() &&
5108 costs_and_savings.back().first ==
cost) {
5109 sorted_savings_.push_back(
5110 {costs_and_savings.back().second, arc_index});
5111 costs_and_savings.pop_back();
5114 std::sort(sorted_savings_.begin(), sorted_savings_.end());
5115 next_saving_type_and_index_for_arc_.clear();
5116 next_saving_type_and_index_for_arc_.resize(
5117 costs_and_savings_per_arc_.size(), {-1, -1});
5120 index_in_sorted_savings_ = 0;
5125 return index_in_sorted_savings_ < sorted_savings_.size() ||
5126 HasReinjectedSavings();
5130 CHECK(sorted_) <<
"Calling GetSaving() before Sort() !";
5132 <<
"Update() should be called between two calls to GetSaving() !";
5136 if (HasReinjectedSavings()) {
5137 if (incoming_reinjected_savings_ !=
nullptr &&
5138 outgoing_reinjected_savings_ !=
nullptr) {
5140 SavingAndArc& incoming_saving = incoming_reinjected_savings_->front();
5141 SavingAndArc& outgoing_saving = outgoing_reinjected_savings_->front();
5142 if (incoming_saving < outgoing_saving) {
5143 current_saving_ = incoming_saving;
5144 using_incoming_reinjected_saving_ =
true;
5146 current_saving_ = outgoing_saving;
5147 using_incoming_reinjected_saving_ =
false;
5150 if (incoming_reinjected_savings_ !=
nullptr) {
5151 current_saving_ = incoming_reinjected_savings_->front();
5152 using_incoming_reinjected_saving_ =
true;
5154 if (outgoing_reinjected_savings_ !=
nullptr) {
5155 current_saving_ = outgoing_reinjected_savings_->front();
5156 using_incoming_reinjected_saving_ =
false;
5160 current_saving_ = sorted_savings_[index_in_sorted_savings_];
5162 return current_saving_.saving;
5165 void Update(
bool update_best_saving,
int type = -1) {
5166 CHECK(to_update_) <<
"Container already up to date!";
5167 if (update_best_saving) {
5168 const int64 arc_index = current_saving_.arc_index;
5169 UpdateNextAndSkippedSavingsForArcWithType(arc_index, type);
5171 if (!HasReinjectedSavings()) {
5172 index_in_sorted_savings_++;
5174 if (index_in_sorted_savings_ == sorted_savings_.size()) {
5175 sorted_savings_.swap(next_savings_);
5177 index_in_sorted_savings_ = 0;
5179 std::sort(sorted_savings_.begin(), sorted_savings_.end());
5180 next_saving_type_and_index_for_arc_.clear();
5181 next_saving_type_and_index_for_arc_.resize(
5182 costs_and_savings_per_arc_.size(), {-1, -1});
5185 UpdateReinjectedSavings();
5190 CHECK(!single_vehicle_type_);
5191 Update(
true, type);
5195 CHECK(sorted_) <<
"Savings not sorted yet!";
5197 return sorted_savings_per_vehicle_type_[type];
5201 CHECK(outgoing_new_reinjected_savings_ ==
nullptr);
5202 outgoing_new_reinjected_savings_ = &(skipped_savings_starting_at_[node]);
5206 CHECK(incoming_new_reinjected_savings_ ==
nullptr);
5207 incoming_new_reinjected_savings_ = &(skipped_savings_ending_at_[node]);
5211 struct SavingAndArc {
5215 bool operator<(
const SavingAndArc& other)
const {
5216 return std::tie(saving, arc_index) <
5217 std::tie(other.saving, other.arc_index);
5223 void SkipSavingForArc(
const SavingAndArc& saving_and_arc) {
5224 const Saving& saving = saving_and_arc.saving;
5225 const int64 before_node = savings_db_->GetBeforeNodeFromSaving(saving);
5226 const int64 after_node = savings_db_->GetAfterNodeFromSaving(saving);
5227 if (!savings_db_->Contains(before_node)) {
5228 skipped_savings_starting_at_[before_node].push_back(saving_and_arc);
5230 if (!savings_db_->Contains(after_node)) {
5231 skipped_savings_ending_at_[after_node].push_back(saving_and_arc);
5245 void UpdateNextAndSkippedSavingsForArcWithType(
int64 arc_index,
int type) {
5246 if (single_vehicle_type_) {
5249 SkipSavingForArc(current_saving_);
5253 auto& type_and_index = next_saving_type_and_index_for_arc_[arc_index];
5254 const int previous_index = type_and_index.second;
5255 const int previous_type = type_and_index.first;
5256 bool next_saving_added =
false;
5259 if (previous_index >= 0) {
5262 if (type == -1 || previous_type == type) {
5265 next_saving_added =
true;
5266 next_saving = next_savings_[previous_index].saving;
5270 if (!next_saving_added &&
5271 GetNextSavingForArcWithType(arc_index, type, &next_saving)) {
5272 type_and_index.first = savings_db_->GetVehicleTypeFromSaving(next_saving);
5273 if (previous_index >= 0) {
5275 next_savings_[previous_index] = {next_saving, arc_index};
5278 type_and_index.second = next_savings_.size();
5279 next_savings_.push_back({next_saving, arc_index});
5281 next_saving_added =
true;
5287 SkipSavingForArc(current_saving_);
5291 if (next_saving_added) {
5292 SkipSavingForArc({next_saving, arc_index});
5297 void UpdateReinjectedSavings() {
5298 UpdateGivenReinjectedSavings(incoming_new_reinjected_savings_,
5299 &incoming_reinjected_savings_,
5300 using_incoming_reinjected_saving_);
5301 UpdateGivenReinjectedSavings(outgoing_new_reinjected_savings_,
5302 &outgoing_reinjected_savings_,
5303 !using_incoming_reinjected_saving_);
5304 incoming_new_reinjected_savings_ =
nullptr;
5305 outgoing_new_reinjected_savings_ =
nullptr;
5308 void UpdateGivenReinjectedSavings(
5309 std::deque<SavingAndArc>* new_reinjected_savings,
5310 std::deque<SavingAndArc>** reinjected_savings,
5311 bool using_reinjected_savings) {
5312 if (new_reinjected_savings ==
nullptr) {
5314 if (*reinjected_savings !=
nullptr && using_reinjected_savings) {
5315 CHECK(!(*reinjected_savings)->empty());
5316 (*reinjected_savings)->pop_front();
5317 if ((*reinjected_savings)->empty()) {
5318 *reinjected_savings =
nullptr;
5327 if (*reinjected_savings !=
nullptr) {
5328 (*reinjected_savings)->clear();
5330 *reinjected_savings =
nullptr;
5331 if (!new_reinjected_savings->empty()) {
5332 *reinjected_savings = new_reinjected_savings;
5336 bool HasReinjectedSavings() {
5337 return outgoing_reinjected_savings_ !=
nullptr ||
5338 incoming_reinjected_savings_ !=
nullptr;
5341 void UpdateArcIndicesCostsAndSavings(
5343 const std::pair<int64, Saving>& cost_and_saving) {
5344 if (single_vehicle_type_) {
5347 absl::flat_hash_map<int, int>& arc_indices =
5348 arc_indices_per_before_node_[before_node];
5349 const auto& arc_inserted = arc_indices.insert(
5350 std::make_pair(after_node, costs_and_savings_per_arc_.size()));
5351 const int index = arc_inserted.first->second;
5352 if (arc_inserted.second) {
5353 costs_and_savings_per_arc_.push_back({cost_and_saving});
5356 costs_and_savings_per_arc_[
index].push_back(cost_and_saving);
5360 bool GetNextSavingForArcWithType(
int64 arc_index,
int type,
5361 Saving* next_saving) {
5362 std::vector<std::pair<int64, Saving>>& costs_and_savings =
5363 costs_and_savings_per_arc_[arc_index];
5365 bool found_saving =
false;
5366 while (!costs_and_savings.empty() && !found_saving) {
5367 const Saving& saving = costs_and_savings.back().second;
5368 if (type == -1 || savings_db_->GetVehicleTypeFromSaving(saving) == type) {
5369 *next_saving = saving;
5370 found_saving =
true;
5372 costs_and_savings.pop_back();
5374 return found_saving;
5377 const SavingsFilteredHeuristic*
const savings_db_;
5378 const int vehicle_types_;
5379 int64 index_in_sorted_savings_;
5380 std::vector<std::vector<Saving>> sorted_savings_per_vehicle_type_;
5381 std::vector<SavingAndArc> sorted_savings_;
5382 std::vector<SavingAndArc> next_savings_;
5383 std::vector<std::pair< int,
int>>
5384 next_saving_type_and_index_for_arc_;
5385 SavingAndArc current_saving_;
5386 const bool single_vehicle_type_;
5387 std::vector<std::vector<std::pair<
int64, Saving>>>
5388 costs_and_savings_per_arc_;
5389 std::vector<absl::flat_hash_map< int,
int>>
5390 arc_indices_per_before_node_;
5391 std::vector<std::deque<SavingAndArc>> skipped_savings_starting_at_;
5392 std::vector<std::deque<SavingAndArc>> skipped_savings_ending_at_;
5393 std::deque<SavingAndArc>* outgoing_reinjected_savings_;
5394 std::deque<SavingAndArc>* incoming_reinjected_savings_;
5395 bool using_incoming_reinjected_saving_;
5396 std::deque<SavingAndArc>* outgoing_new_reinjected_savings_;
5397 std::deque<SavingAndArc>* incoming_new_reinjected_savings_;
5404 SavingsFilteredHeuristic::SavingsFilteredHeuristic(
5408 vehicle_type_curator_(nullptr),
5416 size_squared_ = size * size;
5424 model()->GetVehicleTypeContainer());
5434 if (!
Commit())
return false;
5440 int type,
int64 before_node,
int64 after_node) {
5441 auto vehicle_is_compatible = [
this, before_node, after_node](
int vehicle) {
5457 ->GetCompatibleVehicleOfType(
5458 type, vehicle_is_compatible,
5459 [](
int) {
return false; })
5463 void SavingsFilteredHeuristic::AddSymmetricArcsToAdjacencyLists(
5464 std::vector<std::vector<int64>>* adjacency_lists) {
5465 for (
int64 node = 0; node < adjacency_lists->size(); node++) {
5466 for (
int64 neighbor : (*adjacency_lists)[node]) {
5467 if (
model()->IsStart(neighbor) ||
model()->IsEnd(neighbor)) {
5470 (*adjacency_lists)[neighbor].push_back(node);
5473 std::transform(adjacency_lists->begin(), adjacency_lists->end(),
5474 adjacency_lists->begin(), [](std::vector<int64> vec) {
5475 std::sort(vec.begin(), vec.end());
5476 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
5492 void SavingsFilteredHeuristic::ComputeSavings() {
5496 std::vector<int64> uncontained_non_start_end_nodes;
5497 uncontained_non_start_end_nodes.reserve(size);
5498 for (
int node = 0; node < size; node++) {
5500 uncontained_non_start_end_nodes.push_back(node);
5504 const int64 saving_neighbors =
5505 std::min(MaxNumNeighborsPerNode(num_vehicle_types),
5506 static_cast<int64>(uncontained_non_start_end_nodes.size()));
5509 absl::make_unique<SavingsContainer<Saving>>(
this, num_vehicle_types);
5512 std::vector<std::vector<int64>> adjacency_lists(size);
5514 for (
int type = 0; type < num_vehicle_types; ++type) {
5521 const int64 cost_class =
5529 for (
int before_node : uncontained_non_start_end_nodes) {
5530 std::vector<std::pair<
int64,
int64>> costed_after_nodes;
5531 costed_after_nodes.reserve(uncontained_non_start_end_nodes.size());
5532 for (
int after_node : uncontained_non_start_end_nodes) {
5533 if (after_node != before_node) {
5534 costed_after_nodes.push_back(std::make_pair(
5535 model()->GetArcCostForClass(before_node, after_node, cost_class),
5539 if (saving_neighbors < costed_after_nodes.size()) {
5540 std::nth_element(costed_after_nodes.begin(),
5541 costed_after_nodes.begin() + saving_neighbors,
5542 costed_after_nodes.end());
5543 costed_after_nodes.resize(saving_neighbors);
5545 adjacency_lists[before_node].resize(costed_after_nodes.size());
5546 std::transform(costed_after_nodes.begin(), costed_after_nodes.end(),
5547 adjacency_lists[before_node].begin(),
5548 [](std::pair<int64, int64> cost_and_node) {
5549 return cost_and_node.second;
5553 AddSymmetricArcsToAdjacencyLists(&adjacency_lists);
5557 for (
int before_node : uncontained_non_start_end_nodes) {
5558 const int64 before_to_end_cost =
5560 const int64 start_to_before_cost =
5561 CapSub(
model()->GetArcCostForClass(start, before_node, cost_class),
5563 for (
int64 after_node : adjacency_lists[before_node]) {
5564 if (
model()->IsStart(after_node) ||
model()->IsEnd(after_node) ||
5565 before_node == after_node ||
Contains(after_node)) {
5568 const int64 arc_cost =
5570 const int64 start_to_after_cost =
5571 CapSub(
model()->GetArcCostForClass(start, after_node, cost_class),
5573 const int64 after_to_end_cost =
5576 const double weighted_arc_cost_fp =
5578 const int64 weighted_arc_cost =
5580 ?
static_cast<int64>(weighted_arc_cost_fp)
5583 CapAdd(before_to_end_cost, start_to_after_cost), weighted_arc_cost);
5586 BuildSaving(-saving_value, type, before_node, after_node);
5588 const int64 total_cost =
5589 CapAdd(
CapAdd(start_to_before_cost, arc_cost), after_to_end_cost);
5599 int64 SavingsFilteredHeuristic::MaxNumNeighborsPerNode(
5600 int num_vehicle_types)
const {
5603 const int64 num_neighbors_with_ratio =
5610 const double max_memory_usage_in_savings_unit =
5628 if (num_vehicle_types > 1) {
5629 multiplicative_factor += 1.5;
5631 const double num_savings =
5632 max_memory_usage_in_savings_unit / multiplicative_factor;
5633 const int64 num_neighbors_with_memory_restriction =
5634 std::max(1.0, num_savings / (num_vehicle_types * size));
5636 return std::min(num_neighbors_with_ratio,
5637 num_neighbors_with_memory_restriction);
5642 void SequentialSavingsFilteredHeuristic::BuildRoutesFromSavings() {
5648 std::vector<std::vector<const Saving*>> in_savings_ptr(size * vehicle_types);
5649 std::vector<std::vector<const Saving*>> out_savings_ptr(size * vehicle_types);
5650 for (
int type = 0; type < vehicle_types; type++) {
5651 const int vehicle_type_offset = type * size;
5652 const std::vector<Saving>& sorted_savings_for_type =
5654 for (
const Saving& saving : sorted_savings_for_type) {
5657 in_savings_ptr[vehicle_type_offset + before_node].push_back(&saving);
5659 out_savings_ptr[vehicle_type_offset + after_node].push_back(&saving);
5669 const bool nodes_not_contained =
5672 bool committed =
false;
5674 if (nodes_not_contained) {
5687 const int saving_offset = type * size;
5689 while (in_index < in_savings_ptr[saving_offset + after_node].size() ||
5691 out_savings_ptr[saving_offset + before_node].size()) {
5694 int before_before_node = -1;
5695 int after_after_node = -1;
5696 if (in_index < in_savings_ptr[saving_offset + after_node].size()) {
5697 const Saving& in_saving =
5698 *(in_savings_ptr[saving_offset + after_node][in_index]);
5700 out_savings_ptr[saving_offset + before_node].size()) {
5701 const Saving& out_saving =
5702 *(out_savings_ptr[saving_offset + before_node][out_index]);
5717 *(out_savings_ptr[saving_offset + before_node][out_index]));
5720 if (after_after_node != -1) {
5724 SetValue(after_node, after_after_node);
5728 after_node = after_after_node;
5738 if (!
Contains(before_before_node)) {
5739 SetValue(start, before_before_node);
5740 SetValue(before_before_node, before_node);
5743 before_node = before_before_node;
5760 void ParallelSavingsFilteredHeuristic::BuildRoutesFromSavings() {
5766 first_node_on_route_.resize(vehicles, -1);
5767 last_node_on_route_.resize(vehicles, -1);
5768 vehicle_of_first_or_last_node_.resize(size, -1);
5770 for (
int vehicle = 0; vehicle < vehicles; vehicle++) {
5778 vehicle_of_first_or_last_node_[node] = vehicle;
5779 first_node_on_route_[vehicle] = node;
5782 while (
next != end) {
5786 vehicle_of_first_or_last_node_[node] = vehicle;
5787 last_node_on_route_[vehicle] = node;
5800 bool committed =
false;
5808 vehicle_of_first_or_last_node_[before_node] = vehicle;
5809 vehicle_of_first_or_last_node_[after_node] = vehicle;
5810 first_node_on_route_[vehicle] = before_node;
5811 last_node_on_route_[vehicle] = after_node;
5823 const int v1 = vehicle_of_first_or_last_node_[before_node];
5824 const int64 last_node = v1 == -1 ? -1 : last_node_on_route_[v1];
5826 const int v2 = vehicle_of_first_or_last_node_[after_node];
5827 const int64 first_node = v2 == -1 ? -1 : first_node_on_route_[v2];
5829 if (before_node == last_node && after_node == first_node && v1 != v2 &&
5838 MergeRoutes(v1, v2, before_node, after_node);
5843 const int vehicle = vehicle_of_first_or_last_node_[before_node];
5844 const int64 last_node = vehicle == -1 ? -1 : last_node_on_route_[vehicle];
5846 if (before_node == last_node) {
5851 if (type != route_type) {
5862 if (first_node_on_route_[vehicle] != before_node) {
5865 vehicle_of_first_or_last_node_[before_node] = -1;
5867 vehicle_of_first_or_last_node_[after_node] = vehicle;
5868 last_node_on_route_[vehicle] = after_node;
5875 const int vehicle = vehicle_of_first_or_last_node_[after_node];
5876 const int64 first_node =
5877 vehicle == -1 ? -1 : first_node_on_route_[vehicle];
5879 if (after_node == first_node) {
5884 if (type != route_type) {
5895 if (last_node_on_route_[vehicle] != after_node) {
5898 vehicle_of_first_or_last_node_[after_node] = -1;
5900 vehicle_of_first_or_last_node_[before_node] = vehicle;
5901 first_node_on_route_[vehicle] = before_node;
5910 void ParallelSavingsFilteredHeuristic::MergeRoutes(
int first_vehicle,
5915 const int64 new_first_node = first_node_on_route_[first_vehicle];
5916 DCHECK_EQ(vehicle_of_first_or_last_node_[new_first_node], first_vehicle);
5918 const int64 new_last_node = last_node_on_route_[second_vehicle];
5919 DCHECK_EQ(vehicle_of_first_or_last_node_[new_last_node], second_vehicle);
5923 int used_vehicle = first_vehicle;
5924 int unused_vehicle = second_vehicle;
5925 if (
model()->GetFixedCostOfVehicle(first_vehicle) >
5926 model()->GetFixedCostOfVehicle(second_vehicle)) {
5927 used_vehicle = second_vehicle;
5928 unused_vehicle = first_vehicle;
5933 if (used_vehicle == first_vehicle) {
5938 bool committed =
Commit();
5940 model()->GetVehicleClassIndexOfVehicle(first_vehicle).
value() !=
5941 model()->GetVehicleClassIndexOfVehicle(second_vehicle).
value()) {
5943 std::swap(used_vehicle, unused_vehicle);
5946 if (used_vehicle == first_vehicle) {
5957 model()->GetVehicleClassIndexOfVehicle(unused_vehicle).
value(),
5958 model()->GetFixedCostOfVehicle(unused_vehicle));
5961 first_node_on_route_[unused_vehicle] = -1;
5962 last_node_on_route_[unused_vehicle] = -1;
5963 vehicle_of_first_or_last_node_[before_node] = -1;
5964 vehicle_of_first_or_last_node_[after_node] = -1;
5965 first_node_on_route_[used_vehicle] = new_first_node;
5966 last_node_on_route_[used_vehicle] = new_last_node;
5967 vehicle_of_first_or_last_node_[new_last_node] = used_vehicle;
5968 vehicle_of_first_or_last_node_[new_first_node] = used_vehicle;
5975 bool use_minimum_matching)
5977 use_minimum_matching_(use_minimum_matching) {}
5987 std::vector<int> indices(1, 0);
5988 for (
int i = 1; i < size; ++i) {
5989 if (!
model()->IsStart(i) && !
model()->IsEnd(i)) {
5990 indices.push_back(i);
5994 std::vector<std::vector<int>> path_per_cost_class(num_cost_classes);
5995 std::vector<bool> class_covered(num_cost_classes,
false);
5996 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
5997 const int64 cost_class =
5999 if (!class_covered[cost_class]) {
6000 class_covered[cost_class] =
true;
6003 auto cost = [
this, &indices, start, end, cost_class](
int from,
int to) {
6006 const int from_index = (from == 0) ? start : indices[from];
6007 const int to_index = (to == 0) ? end : indices[to];
6016 using Cost = decltype(
cost);
6018 indices.size(),
cost);
6019 if (use_minimum_matching_) {
6022 MINIMUM_WEIGHT_MATCHING);
6024 if (christofides_solver.
Solve()) {
6025 path_per_cost_class[cost_class] =
6031 for (
int vehicle = 0; vehicle <
model()->
vehicles(); ++vehicle) {
6032 const int64 cost_class =
6034 const std::vector<int>& path = path_per_cost_class[cost_class];
6035 if (path.empty())
continue;
6040 const int end =
model()->
End(vehicle);
6041 for (
int i = 1; i < path.size() - 1 && prev != end; ++i) {
6043 int next = indices[path[i]];
6067 int64 ChooseVariable();
6071 const std::function<
int64(
int64)> initializer_;
6073 std::vector<int64> initial_values_;
6081 GuidedSlackFinalizer::GuidedSlackFinalizer(
6082 const RoutingDimension* dimension, RoutingModel*
model,
6086 initializer_(std::move(initializer)),
6087 is_initialized_(dimension->slacks().size(), false),
6088 initial_values_(dimension->slacks().size(),
kint64min),
6089 current_index_(model_->Start(0)),
6091 last_delta_used_(dimension->slacks().size(), 0) {}
6093 Decision* GuidedSlackFinalizer::Next(Solver* solver) {
6095 const int node_idx = ChooseVariable();
6096 CHECK(node_idx == -1 ||
6097 (node_idx >= 0 && node_idx < dimension_->slacks().size()));
6098 if (node_idx != -1) {
6099 if (!is_initialized_[node_idx]) {
6100 initial_values_[node_idx] = initializer_(node_idx);
6101 is_initialized_.SetValue(solver, node_idx,
true);
6104 IntVar*
const slack_variable = dimension_->
SlackVar(node_idx);
6105 return solver->MakeAssignVariableValue(slack_variable,
value);
6111 const IntVar*
const slack_variable = dimension_->
SlackVar(
index);
6113 const int64 max_delta =
6114 std::max(center - slack_variable->Min(), slack_variable->Max() - center) +
6120 while (std::abs(
delta) < max_delta &&
6121 !slack_variable->Contains(center +
delta)) {
6129 return center +
delta;
6132 int64 GuidedSlackFinalizer::ChooseVariable() {
6133 int64 int_current_node = current_index_.Value();
6134 int64 int_current_route = current_route_.Value();
6136 while (int_current_route < model_->vehicles()) {
6137 while (!model_->
IsEnd(int_current_node) &&
6139 int_current_node = model_->
NextVar(int_current_node)->
Value();
6141 if (!model_->
IsEnd(int_current_node)) {
6144 int_current_route += 1;
6145 if (int_current_route < model_->vehicles()) {
6146 int_current_node = model_->
Start(int_current_route);
6152 current_index_.SetValue(model_->
solver(), int_current_node);
6153 current_route_.SetValue(model_->
solver(), int_current_route);
6154 if (int_current_route < model_->vehicles()) {
6155 return int_current_node;
6165 return solver_->RevAlloc(
6166 new GuidedSlackFinalizer(dimension,
this, std::move(initializer)));
6184 state_dependent_class_evaluators_
6185 [state_dependent_vehicle_to_class_[serving_vehicle]])(
next,
6190 const int64 optimal_next_cumul =
6192 next_cumul_min, next_cumul_max + 1);
6194 DCHECK_LE(next_cumul_min, optimal_next_cumul);
6195 DCHECK_LE(optimal_next_cumul, next_cumul_max);
6202 class_evaluators_[vehicle_to_class_[serving_vehicle]])(node,
next);
6203 const int64 current_state_dependent_transit =
6206 state_dependent_class_evaluators_
6207 [state_dependent_vehicle_to_class_[serving_vehicle]])(node,
6209 .transit->Query(current_cumul);
6210 const int64 optimal_slack = optimal_next_cumul - current_cumul -
6211 current_state_independent_transit -
6212 current_state_dependent_transit;
6215 return optimal_slack;
6221 explicit GreedyDescentLSOperator(std::vector<IntVar*> variables);
6224 void Start(
const Assignment* assignment)
override;
6229 const std::vector<IntVar*> variables_;
6231 int64 current_step_;
6238 int64 current_direction_;
6243 GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)
6244 : variables_(std::move(variables)),
6247 current_direction_(0) {}
6249 bool GreedyDescentLSOperator::MakeNextNeighbor(Assignment*
delta,
6251 static const int64 sings[] = {1, -1};
6252 for (; 1 <= current_step_; current_step_ /= 2) {
6253 for (; current_direction_ < 2 * variables_.size();) {
6254 const int64 variable_idx = current_direction_ / 2;
6255 IntVar*
const variable = variables_[variable_idx];
6256 const int64 sign_index = current_direction_ % 2;
6257 const int64 sign = sings[sign_index];
6258 const int64 offset = sign * current_step_;
6259 const int64 new_value = center_->
Value(variable) + offset;
6260 ++current_direction_;
6261 if (variable->Contains(new_value)) {
6262 delta->Add(variable);
6263 delta->SetValue(variable, new_value);
6267 current_direction_ = 0;
6272 void GreedyDescentLSOperator::Start(
const Assignment* assignment) {
6273 CHECK(assignment !=
nullptr);
6274 current_step_ = FindMaxDistanceToDomain(assignment);
6275 center_ = assignment;
6278 int64 GreedyDescentLSOperator::FindMaxDistanceToDomain(
6279 const Assignment* assignment) {
6281 for (
const IntVar*
const var : variables_) {
6290 std::vector<IntVar*> variables) {
6291 return std::unique_ptr<LocalSearchOperator>(
6292 new GreedyDescentLSOperator(std::move(variables)));
6297 CHECK(dimension !=
nullptr);
6305 solver_->MakeSolveOnce(guided_finalizer);
6306 std::vector<IntVar*> start_cumuls(vehicles_,
nullptr);
6307 for (
int64 vehicle_idx = 0; vehicle_idx < vehicles_; ++vehicle_idx) {
6308 start_cumuls[vehicle_idx] = dimension->
CumulVar(starts_[vehicle_idx]);
6311 solver_->RevAlloc(
new GreedyDescentLSOperator(start_cumuls));
6313 solver_->MakeLocalSearchPhaseParameters(
CostVar(), hill_climber,
6315 Assignment*
const first_solution = solver_->MakeAssignment();
6316 first_solution->
Add(start_cumuls);
6317 for (
IntVar*
const cumul : start_cumuls) {
6318 first_solution->
SetValue(cumul, cumul->Min());
6321 solver_->MakeLocalSearchPhase(first_solution,
parameters);
const std::vector< IntVar * > vars_
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_LT(val1, val2)
#define CHECK_EQ(val1, val2)
#define CHECK_GE(val1, val2)
#define CHECK_GT(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_GT(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define CHECK_LE(val1, val2)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
const std::vector< T * > * Raw() const
void NoteChangedPriority(T *val)
bool Contains(const T *val) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
const E & Element(const V *const var) const
void Resize(size_t size)
Advanced usage: Resizes the container, potentially adding elements with null variables.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
int64 Value(const IntVar *const var) const
IntContainer * MutableIntVarContainer()
const IntContainer & IntVarContainer() const
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
AssignmentContainer< IntVar, IntVarElement > IntContainer
IntVarElement * Add(IntVar *const var)
virtual std::string DebugString() const
Generic path-based filter class.
static const int64 kUnassigned
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size)
void OnSynchronize(const Assignment *delta) override
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
void OnSynchronize(const Assignment *delta) override
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
std::function< int64(int64)> penalty_evaluator_
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(const std::vector< int > &vehicles)
Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::ve...
std::function< int64(int64, int64, int64)> evaluator_
void InsertBetween(int64 node, int64 predecessor, int64 successor)
Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subs...
void InitializePriorityQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, Queue *priority_queue)
Initializes the priority_queue by inserting the best entry corresponding to each node,...
std::pair< int64, int64 > ValuedPosition
void AppendEvaluatedPositionsAfter(int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle, std::vector< ValuedPosition > *valued_positions)
Helper method to the ComputeEvaluatorSortedPositions* methods.
int64 GetUnperformedValue(int64 node_to_insert) const
Returns the cost of unperforming node 'node_to_insert'.
std::pair< StartEndValue, int > Seed
int64 GetInsertionCostForNodeAtPosition(int64 node_to_insert, int64 insert_after, int64 insert_before, int vehicle) const
Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'veh...
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
ChristofidesFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
std::vector< NodeIndex > TravelingSalesmanPath()
void SetMatchingAlgorithm(MatchingAlgorithm matching)
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
bool operator<(const NodeEntry &other) const
void set_vehicle(int vehicle)
void set_insert_after(int insert_after)
NodeEntry(int node_to_insert, int insert_after, int vehicle)
void set_value(int64 value)
int node_to_insert() const
bool operator<(const PairEntry &other) const
void set_vehicle(int vehicle)
PairEntry(int pickup_to_insert, int pickup_insert_after, int delivery_to_insert, int delivery_insert_after, int vehicle)
int pickup_insert_after() const
void set_pickup_insert_after(int pickup_insert_after)
int delivery_insert_after() const
void set_value(int64 value)
int delivery_to_insert() const
int pickup_to_insert() const
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
const RoutingDimension * dimension() const
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64 Max() const =0
virtual int64 Min() const =0
Decision * Next(Solver *solver) override
This is the main method of the decision builder class.
int64 number_of_rejects() const
int64 number_of_decisions() const
Returns statistics from its underlying heuristic.
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
std::string DebugString() const override
Generic filter-based heuristic applied to IntVars.
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
int Size() const
Returns the number of variables the decision builder is trying to instantiate.
bool Contains(int64 index) const
Returns true if the variable of index 'index' is in the current solution.
int64 Value(int64 index) const
Returns the value of the variable of index 'index' in the last committed solution.
bool Commit()
Commits the modifications to the current solution if these modifications are "filter-feasible",...
IntVar * Var(int64 index) const
Returns the variable of index 'index'.
Assignment *const assignment_
void ResetSolution()
Resets the data members for a new solution.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
virtual bool InitializeSolution()
Virtual method to initialize the solution.
void SetValue(int64 index, int64 value)
Modifies the current solution by setting the variable of index 'index' to value 'value'.
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, LocalSearchFilterManager *filter_manager)
Assignment *const BuildSolution()
Builds a solution.
The class IntVar is a subset of IntExpr.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
bool FindIndex(IntVar *const var, int64 *index) const
IntVar * Var(int index) const
int64 Value(int index) const
bool IsVarSynced(int index) const
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
bool Accept(LocalSearchMonitor *const monitor, const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)
Returns true iff all filters return true, and the sum of their accepted objectives is between objecti...
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
The base class for all local search operators.
virtual int64 RangeMinArgument(int64 from, int64 to) const =0
Reversible array of POD types.
This class adds reversibility to a POD type.
Dimensions represent quantities accumulated at nodes along the routes.
int64 global_span_cost_coefficient() const
RoutingModel * model() const
Returns the model on which the dimension was created.
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
int64 ShortestTransitionSlack(int64 node) const
It makes sense to use the function only for self-dependent dimension.
IntVar * SlackVar(int64 index) const
const std::vector< NodePrecedence > & GetNodePrecedences() const
Filter-based heuristic dedicated to routing.
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
RoutingModel * model() const
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
const Assignment * BuildSolutionFromRoutes(const std::function< int64(int64)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
virtual void SetVehicleIndex(int64 node, int vehicle)
bool StopSearch() override
Returns true if the search must be stopped.
void MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed.
void MakeDisjunctionNodesUnperformed(int64 node)
Make nodes in the same disjunction as 'node' unperformed.
virtual void ResetVehicleIndices()
void MakePartiallyPerformedPairsUnperformed()
Make all partially performed pickup and delivery pairs unperformed.
bool VehicleIsEmpty(int vehicle) const
RoutingFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
Manager for any NodeIndex <-> variable index conversion.
RoutingIndexPair IndexPair
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(int64 index, int64 max_cardinality, F f) const
Calls f for each variable index of indices in the same disjunctions as the node corresponding to the ...
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
int64 Size() const
Returns the number of next variables in the model.
bool CheckLimit()
Returns true if the search limit has been crossed.
static std::unique_ptr< LocalSearchOperator > MakeGreedyDescentLSOperator(std::vector< IntVar * > variables)
Perhaps move it to constraint_solver.h.
int64 GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
Solver * solver() const
Returns the underlying constraint solver.
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
RoutingIndexPairs IndexPairs
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
int vehicles() const
Returns the number of vehicle routes in the model.
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
DecisionBuilder * MakeSelfDependentDimensionFinalizer(const RoutingDimension *dimension)
SWIG
int64 Start(int vehicle) const
Model inspection.
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
DecisionBuilder * MakeGuidedSlackFinalizer(const RoutingDimension *dimension, std::function< int64(int64)> initializer)
The next few members are in the public section only for testing purposes.
const TransitCallback2 & TransitCallback(int callback_index) const
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
RoutingDisjunctionIndex DisjunctionIndex
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
void AddNewSaving(const Saving &saving, int64 total_cost, int64 before_node, int64 after_node, int vehicle_type)
void ReinjectSkippedSavingsStartingAt(int64 node)
void ReinjectSkippedSavingsEndingAt(int64 node)
void InitializeContainer(int64 size, int64 saving_neighbors)
SavingsContainer(const SavingsFilteredHeuristic *savings_db, int vehicle_types)
void UpdateWithType(int type)
void Update(bool update_best_saving, int type=-1)
const std::vector< Saving > & GetSortedSavingsForVehicleType(int type)
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
int StartNewRouteWithBestVehicleOfType(int type, int64 before_node, int64 after_node)
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->a...
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
std::pair< int64, int64 > Saving
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
int64 GetVehicleTypeFromSaving(const Saving &saving) const
Returns the cost class from a saving.
std::unique_ptr< SavingsContainer< Saving > > savings_container_
~SavingsFilteredHeuristic() override
int64 GetSavingValue(const Saving &saving) const
Returns the saving value from a saving.
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int64 GetBeforeNodeFromSaving(const Saving &saving) const
Returns the "before node" from a saving.
int64 GetAfterNodeFromSaving(const Saving &saving) const
Returns the "after node" from a saving.
virtual void BuildRoutesFromSavings()=0
std::function< bool(int64, int64, int64)> VariableValueComparator
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
T * RevAlloc(T *object)
Registers the given object as being reversible.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void Set(IntegerType index)
void Update(const std::function< bool(int)> &remove_vehicle)
Goes through all the currently stored vehicles and removes vehicles for which remove_vehicle() return...
std::pair< int, int > GetCompatibleVehicleOfType(int type, std::function< bool(int)> vehicle_is_compatible, std::function< bool(int)> stop_and_return_vehicle)
Searches for the best compatible vehicle of the given type, i.e.
void Reset(const std::function< bool(int)> &store_vehicle)
Resets the vehicles stored, storing only vehicles from the vehicle_type_container_ for which store_ve...
const std::vector< IntVar * > cumuls_
static const int64 kint64max
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
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)
void STLClearObject(T *obj)
bool ContainsKey(const Collection &collection, const Key &key)
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
std::function< int64(const Model &)> Value(IntegerVariable v)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters ¶meters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
int64 CapSub(int64 x, int64 y)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
int64 CapAdd(int64 x, int64 y)
DimensionSchedulingStatus
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
int64 CapProd(int64 x, int64 y)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
static const int kUnassigned
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
std::vector< int64 > path_values
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.")
std::function< int64(int64, int64)> evaluator_
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
double farthest_seeds_ratio
The ratio of routes on which to insert farthest nodes as seeds before starting the cheapest insertion...
bool use_neighbors_ratio_for_initialization
If true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion p...
bool add_unperformed_entries
If true, entries are created for making the nodes/pairs unperformed, and when the cost of making a no...
What follows is relevant for models with time/state dependent transits.
RangeMinMaxIndexFunction * transit_plus_identity
f(x)
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
std::vector< std::deque< int > > vehicles_per_vehicle_class
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
double arc_coefficient
arc_coefficient is a strictly positive parameter indicating the coefficient of the arc being consider...
double max_memory_usage_bytes
The number of neighbors considered for each node is also adapted so that the stored Savings don't use...
bool add_reverse_arcs
If add_reverse_arcs is true, the neighborhood relationships are considered symmetrically.