14#ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
24#include <initializer_list>
37#include "absl/container/flat_hash_set.h"
38#include "absl/container/inlined_vector.h"
39#include "absl/log/check.h"
40#include "absl/types/span.h"
77 RoutingModel* primary_model,
78 const std::vector<RoutingModel*>& alternative_models,
80 int max_non_improving_iterations);
83 const Assignment* assignment, RoutingModel* primary_model,
84 const std::vector<RoutingModel*>& alternative_models,
86 int max_non_improving_iterations);
89 const Assignment* assignment, RoutingModel* primary_model,
91 const std::vector<RoutingModel*>& alternative_models,
92 const std::vector<RoutingSearchParameters>& alternative_parameters,
93 int max_non_improving_iterations);
103 const RoutingModel::VehicleTypeContainer& vehicle_type_container)
104 : vehicle_type_container_(&vehicle_type_container) {}
106 int NumTypes()
const {
return vehicle_type_container_->NumTypes(); }
108 int Type(
int vehicle)
const {
return vehicle_type_container_->Type(vehicle); }
112 void Reset(
const std::function<
bool(
int)>& store_vehicle);
116 void Update(
const std::function<
bool(
int)>& remove_vehicle);
120 const std::set<VehicleClassEntry>& vehicle_classes =
121 sorted_vehicle_classes_per_type_[type];
122 if (vehicle_classes.empty()) {
125 const int vehicle_class = (vehicle_classes.begin())->vehicle_class;
126 DCHECK(!vehicles_per_vehicle_class_[vehicle_class].empty());
127 return vehicles_per_vehicle_class_[vehicle_class][0];
131 int64_t fixed_cost) {
132 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
133 if (vehicles.empty()) {
136 std::set<VehicleClassEntry>& vehicle_classes =
137 sorted_vehicle_classes_per_type_[
Type(vehicle)];
138 const auto& insertion =
139 vehicle_classes.insert({vehicle_class, fixed_cost});
140 DCHECK(insertion.second);
142 vehicles.push_back(vehicle);
148 int type,
const std::function<
bool(
int)>& vehicle_is_compatible)
const;
158 int type,
const std::function<
bool(
int)>& vehicle_is_compatible,
159 const std::function<
bool(
int)>& stop_and_return_vehicle);
162 using VehicleClassEntry =
163 RoutingModel::VehicleTypeContainer::VehicleClassEntry;
164 const RoutingModel::VehicleTypeContainer*
const vehicle_type_container_;
166 std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;
167 std::vector<std::vector<int> > vehicles_per_vehicle_class_;
175 bool has_node_precedences,
176 bool has_single_vehicle_node);
201 std::unique_ptr<IntVarFilteredHeuristic> heuristic);
214 const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;
221 const std::vector<IntVar*>& secondary_vars,
235 virtual std::string
DebugString()
const {
return "IntVarFilteredHeuristic"; }
253 std::optional<int64_t>
Evaluate(
bool commit,
bool ignore_upper_bound =
false,
254 bool update_upper_bound =
true);
260 DCHECK_LT(index, is_in_delta_.size());
261 if (!is_in_delta_[index]) {
262 delta_->FastAdd(vars_[index])->SetValue(value);
263 delta_indices_.push_back(index);
264 is_in_delta_[index] =
true;
266 delta_->SetValue(vars_[index], value);
273 int64_t
Value(int64_t index)
const {
274 return assignment_->IntVarContainer().Element(index).Value();
278 return assignment_->IntVarContainer().Element(index).Var() !=
nullptr;
281 IntVar*
Var(int64_t index)
const {
return vars_[index]; }
285 return index + base_vars_size_;
299 bool FilterAccept(
bool ignore_upper_bound);
302 std::vector<IntVar*> vars_;
303 const int base_vars_size_;
305 std::vector<int> delta_indices_;
306 std::vector<bool> is_in_delta_;
309 int64_t objective_upper_bound_;
311 int64_t number_of_decisions_;
312 int64_t number_of_rejects_;
319 std::function<
bool()> stop_search,
324 const std::function<int64_t(int64_t)>& next_accessor);
325 RoutingModel*
model()
const {
return model_; }
350 void SetNext(int64_t node, int64_t next,
int vehicle) {
359 RoutingModel*
const model_;
360 std::function<bool()> stop_search_;
361 std::vector<int64_t> start_chain_ends_;
362 std::vector<int64_t> end_chain_starts_;
369 RoutingModel*
model, std::function<
bool()> stop_search,
370 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
371 std::function<int64_t(int64_t)> penalty_evaluator,
399 for (
size_t i = 0; i <
properties.size(); ++i) {
414 std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed> >
426 std::vector<std::vector<StartEndValue> >
433 std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
440 std::vector<StartEndValue>* start_end_distances,
448 void InsertBetween(int64_t node, int64_t predecessor, int64_t successor,
457 int64_t insert_after,
458 int64_t insert_before,
464 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
465 int vehicle,
int hint_weight = 0);
469 int64_t pickup_to_insert, int64_t pickup_insert_after,
470 int64_t delivery_to_insert, int64_t delivery_insert_after,
int vehicle,
471 int hint_weight = 0);
484 bool IsHint(
int node, int64_t next)
const {
488 std::function<int64_t(int64_t, int64_t, int64_t)>
evaluator_;
532 RoutingModel*
model, std::function<
bool()> stop_search,
533 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
534 std::function<int64_t(int64_t)> penalty_evaluator,
540 return "GlobalCheapestInsertionFilteredHeuristic";
545 class NodeEntryQueue;
550 PairEntry(
int pickup_to_insert,
int pickup_insert_after,
551 int delivery_to_insert,
int delivery_insert_after,
int vehicle,
553 : value_(
std::numeric_limits<int64_t>::max()),
555 pickup_to_insert_(pickup_to_insert),
556 pickup_insert_after_(pickup_insert_after),
557 delivery_to_insert_(delivery_to_insert),
558 delivery_insert_after_(delivery_insert_after),
563 bool operator<(
const PairEntry& other)
const {
565 if (bucket_ != other.bucket_) {
566 return bucket_ > other.bucket_;
570 if (value_ != other.value_) {
571 return value_ > other.value_;
573 if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
574 return vehicle_ == -1;
576 return std::tie(pickup_insert_after_, pickup_to_insert_,
577 delivery_insert_after_, delivery_to_insert_, vehicle_) >
578 std::tie(other.pickup_insert_after_, other.pickup_to_insert_,
579 other.delivery_insert_after_, other.delivery_to_insert_,
582 void SetHeapIndex(
int h) { heap_index_ = h; }
583 int GetHeapIndex()
const {
return heap_index_; }
584 void set_value(int64_t value) { value_ = value; }
585 int pickup_to_insert()
const {
return pickup_to_insert_; }
586 int pickup_insert_after()
const {
return pickup_insert_after_; }
587 void set_pickup_insert_after(
int pickup_insert_after) {
588 pickup_insert_after_ = pickup_insert_after;
590 int delivery_to_insert()
const {
return delivery_to_insert_; }
591 int delivery_insert_after()
const {
return delivery_insert_after_; }
592 int vehicle()
const {
return vehicle_; }
593 void set_vehicle(
int vehicle) { vehicle_ = vehicle; }
598 int pickup_to_insert_;
599 int pickup_insert_after_;
600 int delivery_to_insert_;
601 int delivery_insert_after_;
606 typedef absl::flat_hash_set<PairEntry*> PairEntries;
609 template <
typename T>
610 class EntryAllocator {
612 EntryAllocator() =
default;
615 free_entries_.clear();
617 template <
typename... Args>
618 T* NewEntry(
const Args&... args) {
619 if (!free_entries_.empty()) {
620 auto* entry = free_entries_.back();
621 free_entries_.pop_back();
625 entries_.emplace_back(args...);
626 return &entries_.back();
629 void FreeEntry(T* entry) { free_entries_.push_back(entry); }
633 std::deque<T> entries_;
634 std::vector<T*> free_entries_;
643 bool InsertPairsAndNodesByRequirementTopologicalOrder();
652 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket);
657 bool UseEmptyVehicleTypeCuratorForVehicle(
int vehicle,
658 bool all_vehicles =
true)
const {
672 bool InsertPairEntryUsingEmptyVehicleTypeCurator(
673 const absl::flat_hash_set<int>& pair_indices, PairEntry* pair_entry,
674 AdjustablePriorityQueue<PairEntry>* priority_queue,
675 std::vector<PairEntries>* pickup_to_entries,
676 std::vector<PairEntries>* delivery_to_entries);
685 bool InsertNodesOnRoutes(
686 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,
687 const absl::flat_hash_set<int>& vehicles);
696 bool InsertNodeEntryUsingEmptyVehicleTypeCurator(
697 const SparseBitset<int>& nodes,
bool all_vehicles,
NodeEntryQueue* queue);
704 bool SequentialInsertNodes(
705 const std::map<int64_t, std::vector<int>>& nodes_by_bucket);
710 void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,
711 std::vector<int>* unused_vehicles,
712 absl::flat_hash_set<int>* used_vehicles);
716 bool IsCheapestClassRepresentative(
int vehicle)
const;
721 void InsertFarthestNodesAsSeeds();
732 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
733 SeedQueue* sq, std::vector<bool>* is_vehicle_used);
738 bool InitializePairPositions(
739 const absl::flat_hash_set<int>& pair_indices,
740 AdjustablePriorityQueue<PairEntry>* priority_queue,
741 std::vector<PairEntries>* pickup_to_entries,
742 std::vector<PairEntries>* delivery_to_entries);
748 void InitializeInsertionEntriesPerformingPair(
749 int64_t pickup, int64_t delivery,
750 AdjustablePriorityQueue<PairEntry>* priority_queue,
751 std::vector<PairEntries>* pickup_to_entries,
752 std::vector<PairEntries>* delivery_to_entries);
756 bool UpdateAfterPairInsertion(
757 const absl::flat_hash_set<int>& pair_indices,
int vehicle, int64_t pickup,
758 int64_t pickup_position, int64_t delivery, int64_t delivery_position,
759 AdjustablePriorityQueue<PairEntry>* priority_queue,
760 std::vector<PairEntries>* pickup_to_entries,
761 std::vector<PairEntries>* delivery_to_entries);
765 bool UpdateExistingPairEntriesOnChain(
766 int64_t insert_after_start, int64_t insert_after_end,
767 AdjustablePriorityQueue<PairEntry>* priority_queue,
768 std::vector<PairEntries>* pickup_to_entries,
769 std::vector<PairEntries>* delivery_to_entries);
775 bool AddPairEntriesAfter(
const absl::flat_hash_set<int>& pair_indices,
776 int vehicle, int64_t insert_after,
777 int64_t skip_entries_inserting_delivery_after,
778 AdjustablePriorityQueue<PairEntry>* priority_queue,
779 std::vector<PairEntries>* pickup_to_entries,
780 std::vector<PairEntries>* delivery_to_entries) {
781 return AddPairEntriesWithDeliveryAfter(pair_indices, vehicle, insert_after,
782 priority_queue, pickup_to_entries,
783 delivery_to_entries) &&
784 AddPairEntriesWithPickupAfter(pair_indices, vehicle, insert_after,
785 skip_entries_inserting_delivery_after,
786 priority_queue, pickup_to_entries,
787 delivery_to_entries);
795 bool AddPairEntriesWithPickupAfter(
796 const absl::flat_hash_set<int>& pair_indices,
int vehicle,
797 int64_t insert_after, int64_t skip_entries_inserting_delivery_after,
798 AdjustablePriorityQueue<PairEntry>* priority_queue,
799 std::vector<PairEntries>* pickup_to_entries,
800 std::vector<PairEntries>* delivery_to_entries);
804 bool AddPairEntriesWithDeliveryAfter(
805 const absl::flat_hash_set<int>& pair_indices,
int vehicle,
806 int64_t insert_after, AdjustablePriorityQueue<PairEntry>* priority_queue,
807 std::vector<PairEntries>* pickup_to_entries,
808 std::vector<PairEntries>* delivery_to_entries);
811 void DeletePairEntry(PairEntry* entry,
812 AdjustablePriorityQueue<PairEntry>* priority_queue,
813 std::vector<PairEntries>* pickup_to_entries,
814 std::vector<PairEntries>* delivery_to_entries);
819 void AddPairEntry(int64_t pickup, int64_t pickup_insert_after,
820 int64_t delivery, int64_t delivery_insert_after,
822 AdjustablePriorityQueue<PairEntry>* priority_queue,
823 std::vector<PairEntries>* pickup_entries,
824 std::vector<PairEntries>* delivery_entries);
830 bool UpdatePairEntry(PairEntry* pair_entry,
831 AdjustablePriorityQueue<PairEntry>* priority_queue);
835 bool InitializePositions(
const SparseBitset<int>& nodes,
836 const absl::flat_hash_set<int>& vehicles,
843 void InitializeInsertionEntriesPerformingNode(
844 int64_t node,
const absl::flat_hash_set<int>& vehicles,
848 bool UpdateAfterNodeInsertion(
const SparseBitset<int>& nodes,
int vehicle,
849 int64_t node, int64_t insert_after,
854 bool UpdateExistingNodeEntriesOnChain(
const SparseBitset<int>& nodes,
855 int vehicle, int64_t insert_after_start,
856 int64_t insert_after_end,
861 bool AddNodeEntriesAfter(
const SparseBitset<int>& nodes,
int vehicle,
862 int64_t insert_after,
bool all_vehicles,
868 void AddNodeEntry(int64_t node, int64_t insert_after,
int vehicle,
872 node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);
875 void SetVehicleIndex(int64_t node,
int vehicle)
override {
876 DCHECK_LT(node, node_index_to_vehicle_.size());
877 node_index_to_vehicle_[node] = vehicle;
882 bool CheckVehicleIndices()
const;
885 int64_t GetBucketOfNode(
int node)
const {
886 return model()->VehicleVar(node)->Size();
890 int64_t GetBucketOfPair(
const PickupDeliveryPair& pair)
const {
891 int64_t max_pickup_bucket = 0;
892 for (int64_t pickup : pair.pickup_alternatives) {
893 max_pickup_bucket = std::max(max_pickup_bucket, GetBucketOfNode(pickup));
895 int64_t max_delivery_bucket = 0;
896 for (int64_t delivery : pair.delivery_alternatives) {
897 max_delivery_bucket =
898 std::max(max_delivery_bucket, GetBucketOfNode(delivery));
900 return std::min(max_pickup_bucket, max_delivery_bucket);
905 template <
typename T>
906 bool StopSearchAndCleanup(AdjustablePriorityQueue<T>* priority_queue) {
908 if constexpr (std::is_same_v<T, PairEntry>) {
909 pair_entry_allocator_.Clear();
911 priority_queue->
Clear();
917 std::vector<int> node_index_to_vehicle_;
919 const RoutingModel::NodeNeighborsByCostClass*
920 node_index_to_neighbors_by_cost_class_;
922 std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;
924 mutable EntryAllocator<PairEntry> pair_entry_allocator_;
941 struct InsertionBounds {
947 bool operator<(
const InsertionBounds& other)
const {
948 return std::tie(neg_hint_weight, cost, vehicle,
begin) <
949 std::tie(other.neg_hint_weight, other.cost, other.vehicle,
969 : data_(data), bounds_(bounds) {}
972 DCHECK_NE(data_, other.data_);
973 return bounds_ != other.bounds_;
978 size_t Size()
const {
return bounds_->Size(); }
979 int Vehicle()
const {
return bounds_->vehicle; }
980 int64_t
Cost()
const {
return bounds_->cost; }
981 int64_t&
Cost() {
return bounds_->cost; }
983 bounds_->neg_hint_weight = -hint_weight;
989 InsertionBounds*
const bounds_;
994 : data_(data), bounds_(bounds) {}
996 DCHECK_EQ(data_, other.data_);
997 return bounds_ != other.bounds_;
1007 InsertionBounds* bounds_;
1012 return {insertions_.data(), insertion_bounds_.data()};
1015 return {insertions_.data(),
1016 insertion_bounds_.data() + insertion_bounds_.size()};
1019 size_t Size()
const {
return insertion_bounds_.size(); }
1025 int vehicle, std::initializer_list<Insertion> insertion_sequence) {
1026 insertion_bounds_.push_back(
1027 {.begin = insertions_.size(),
1028 .end = insertions_.size() + insertion_sequence.size(),
1031 insertions_.insert(insertions_.end(), insertion_sequence.begin(),
1032 insertion_sequence.end());
1037 absl::Span<const Insertion> insertion_sequence) {
1038 insertion_bounds_.push_back(
1039 {.begin = insertions_.size(),
1040 .end = insertions_.size() + insertion_sequence.size(),
1043 insertions_.insert(insertions_.end(), insertion_sequence.begin(),
1044 insertion_sequence.end());
1054 if (!p(sequence)) insertion_bounds_[
to++] = insertion_bounds_[from];
1057 insertion_bounds_.resize(
to);
1064 void Sort() { std::sort(insertion_bounds_.begin(), insertion_bounds_.end()); }
1068 insertions_.clear();
1069 insertion_bounds_.clear();
1073 std::vector<Insertion> insertions_;
1074 std::vector<InsertionBounds> insertion_bounds_;
1100 int pickup,
int delivery,
int vehicle,
const std::vector<int>& path,
1101 const std::vector<bool>& path_node_is_pickup,
1102 const std::vector<bool>& path_node_is_delivery,
1107 std::vector<int> next_decrease_;
1108 std::vector<int> next_increase_;
1109 std::vector<int> prev_decrease_;
1110 std::vector<int> prev_increase_;
1139 RoutingModel*
model, std::function<
bool()> stop_search,
1140 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
1142 std::vector<RoutingSearchParameters::InsertionSortingProperty>
1143 insertion_sorting_properties,
1146 std::function<
bool(
const std::vector<RoutingModel::VariableValuePair>&,
1147 std::vector<RoutingModel::VariableValuePair>*)>
1148 optimize_on_insertion =
nullptr);
1152 return "LocalCheapestInsertionFilteredHeuristic";
1159 struct NodeInsertion {
1160 int64_t insert_after;
1162 int neg_hint_weight;
1165 bool operator<(
const NodeInsertion& other)
const {
1166 return std::tie(neg_hint_weight, value, insert_after, vehicle) <
1167 std::tie(other.neg_hint_weight, other.value, other.insert_after,
1174 void ComputeInsertionOrder();
1179 void AppendInsertionPositionsAfter(
1180 int64_t node_to_insert, int64_t start, int64_t next_after_start,
1181 int vehicle, std::vector<NodeInsertion>* node_insertions);
1185 std::vector<NodeInsertion> ComputeEvaluatorSortedPositions(int64_t node);
1190 std::vector<NodeInsertion> ComputeEvaluatorSortedPositionsOnRouteAfter(
1191 int64_t node, int64_t start, int64_t next_after_start,
int vehicle);
1196 std::vector<PickupDeliveryInsertion> ComputeEvaluatorSortedPairPositions(
1197 int pickup,
int delivery);
1201 void InsertBestPickupThenDelivery(
const PickupDeliveryPair& pair);
1204 void InsertBestPair(
const PickupDeliveryPair& pair);
1208 void InsertBestPairMultitour(
const PickupDeliveryPair& pair);
1210 bool InsertPair(int64_t pickup, int64_t insert_pickup_after, int64_t delivery,
1211 int64_t insert_delivery_after,
int vehicle);
1219 bool MustUpdateBinCapacities()
const {
1220 return bin_capacities_ !=
nullptr && optimize_on_insertion_ ==
nullptr;
1223 std::vector<Seed> insertion_order_;
1225 std::vector<RoutingSearchParameters::InsertionSortingProperty>
1226 insertion_sorting_properties_;
1227 InsertionSequenceContainer insertion_container_;
1228 InsertionSequenceGenerator insertion_generator_;
1230 const bool use_first_solution_hint_;
1232 BinCapacities*
const bin_capacities_;
1234 std::function<bool(
const std::vector<RoutingModel::VariableValuePair>&,
1235 std::vector<RoutingModel::VariableValuePair>*)>
1236 optimize_on_insertion_;
1237 bool synchronize_insertion_optimizer_ =
true;
1239 const bool use_random_insertion_order_;
1248 std::function<
bool()> stop_search,
1254 class PartialRoutesAndLargeVehicleIndicesFirst {
1256 explicit PartialRoutesAndLargeVehicleIndicesFirst(
1258 : builder_(builder) {}
1259 bool operator()(
int vehicle1,
int vehicle2)
const;
1265 template <
typename Iterator>
1266 std::vector<int64_t> GetPossibleNextsFromIterator(int64_t node,
1268 Iterator
end)
const {
1269 const int size =
model()->Size();
1270 std::vector<int64_t> nexts;
1271 for (Iterator it = start; it !=
end; ++it) {
1272 const int64_t next = *it;
1273 if (next != node && (next >= size || !
Contains(next))) {
1274 nexts.push_back(next);
1280 virtual void SortSuccessors(int64_t node,
1281 std::vector<int64_t>* successors) = 0;
1282 virtual int64_t FindTopSuccessor(int64_t node,
1283 const std::vector<int64_t>& successors) = 0;
1293 RoutingModel*
model, std::function<
bool()> stop_search,
1294 std::function<int64_t(int64_t, int64_t)> evaluator,
1298 return "EvaluatorCheapestAdditionFilteredHeuristic";
1303 void SortSuccessors(int64_t node, std::vector<int64_t>* successors)
override;
1304 int64_t FindTopSuccessor(int64_t node,
1305 const std::vector<int64_t>& successors)
override;
1307 std::function<int64_t(int64_t, int64_t)> evaluator_;
1317 RoutingModel*
model, std::function<
bool()> stop_search,
1322 return "ComparatorCheapestAdditionFilteredHeuristic";
1327 void SortSuccessors(int64_t node, std::vector<int64_t>* successors)
override;
1328 int64_t FindTopSuccessor(int64_t node,
1329 const std::vector<int64_t>& successors)
override;
1360 std::function<
bool()> stop_search,
1379 template <
typename S>
1380 class SavingsContainer;
1396 int64_t after_node);
1409 void AddSymmetricArcsToAdjacencyLists(
1410 std::vector<std::vector<int64_t> >* adjacency_lists);
1421 bool ComputeSavings();
1423 Saving BuildSaving(int64_t saving,
int vehicle_type,
int before_node,
1424 int after_node)
const {
1425 return {saving,
static_cast<unsigned int>(vehicle_type),
1426 static_cast<unsigned int>(before_node),
1427 static_cast<unsigned int>(after_node)};
1433 int64_t MaxNumNeighborsPerNode(
int num_vehicle_types)
const;
1435 const SavingsParameters savings_params_;
1443 std::function<
bool()> stop_search,
1450 return "SequentialSavingsFilteredHeuristic";
1465 std::function<
bool()> stop_search,
1472 return "ParallelSavingsFilteredHeuristic";
1494 void MergeRoutes(
int first_vehicle,
int second_vehicle, int64_t before_node,
1495 int64_t after_node);
1498 std::vector<int64_t> first_node_on_route_;
1499 std::vector<int64_t> last_node_on_route_;
1503 std::vector<int> vehicle_of_first_or_last_node_;
1513 std::function<
bool()> stop_search,
1515 bool use_minimum_matching);
1519 return "ChristofidesFilteredHeuristic";
1523 const bool use_minimum_matching_;
1530 explicit SweepArranger(absl::Span<
const std::pair<int64_t, int64_t>> points);
1541 std::vector<int> coordinates_;
1549 bool check_assignment);
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
CheapestAdditionFilteredHeuristic.
~CheapestAdditionFilteredHeuristic() override=default
std::function< int64_t(int64_t, int64_t, int64_t)> evaluator_
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(absl::Span< const int > vehicles)
int64_t GetEvaluatorInsertionCostForNodeAtPosition(int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle) const
bool HasHintedNext(int node) const
std::optional< int64_t > GetInsertionCostForPairAtPositions(int64_t pickup_to_insert, int64_t pickup_insert_after, int64_t delivery_to_insert, int64_t delivery_insert_after, int vehicle, int hint_weight=0)
std::vector< int > hint_prev_values_
~CheapestInsertionFilteredHeuristic() override=default
bool IsHint(int node, int64_t next) const
std::vector< int > hint_next_values_
void InitializeSeedQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, SeedQueue *sq)
std::vector< EvaluatorCache > evaluator_cache_
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, std::function< int64_t(int64_t)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
int64_t GetUnperformedValue(int64_t node_to_insert) const
std::optional< int64_t > GetInsertionCostForNodeAtPosition(int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle, int hint_weight=0)
void InsertBetween(int64_t node, int64_t predecessor, int64_t successor, int vehicle=-1)
bool HasHintedPrev(int node) const
std::function< int64_t(int64_t)> penalty_evaluator_
void AddSeedNodeToQueue(int node, std::vector< StartEndValue > *start_end_distances, SeedQueue *sq)
clang-format on
ChristofidesFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
ChristofidesFilteredHeuristic.
bool BuildSolutionInternal() override
~ChristofidesFilteredHeuristic() override=default
std::string DebugString() const override
std::string DebugString() const override
~ComparatorCheapestAdditionFilteredHeuristic() override=default
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
~EvaluatorCheapestAdditionFilteredHeuristic() override=default
std::string DebugString() const override
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
FirstSolutionStrategy_Value Value
nested types -------------------------------------------------—
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, std::function< int64_t(int64_t)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
~GlobalCheapestInsertionFilteredHeuristic() override=default
std::string DebugString() const override
InsertionSequenceIterator(Insertion *data, InsertionBounds *bounds)
InsertionSequence operator*() const
bool operator!=(const InsertionSequenceIterator &other) const
InsertionSequenceIterator & operator++()
void SetHintWeight(int hint_weight)
const Insertion * end() const
const Insertion * begin() const
bool operator!=(const InsertionSequence &other) const
int NegHintWeight() const
InsertionSequence(Insertion *data, InsertionBounds *bounds)
void RemoveIf(const std::function< bool(const InsertionSequence &)> &p)
void AddInsertionSequence(int vehicle, std::initializer_list< Insertion > insertion_sequence)
InsertionSequenceIterator begin()
InsertionSequenceContainer is a range over insertion sequences.
void Clear()
Removes all sequences.
size_t Size() const
Returns the number of sequences of this container.
InsertionSequenceIterator end()
void AddInsertionSequence(int vehicle, absl::Span< const Insertion > insertion_sequence)
Adds an insertion sequence to the container.
void AppendPickupDeliveryMultitourInsertions(int pickup, int delivery, int vehicle, const std::vector< int > &path, const std::vector< bool > &path_node_is_pickup, const std::vector< bool > &path_node_is_delivery, InsertionSequenceContainer &insertions)
InsertionSequenceGenerator()=default
int64_t number_of_rejects() const
int64_t number_of_decisions() const
Returns statistics from its underlying heuristic.
std::string DebugString() const override
-------— Decision Builder -------—
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
— First solution decision builder —
~IntVarFilteredDecisionBuilder() override=default
Generic filter-based heuristic applied to IntVars.
bool HasSecondaryVars() const
Returns true if there are secondary variables.
Assignment *const assignment_
virtual std::string DebugString() const
void ResetSolution()
Resets the data members for a new solution.
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, LocalSearchFilterManager *filter_manager)
— First solution heuristics —
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
int64_t number_of_rejects() const
virtual ~IntVarFilteredHeuristic()=default
int64_t number_of_decisions() const
bool Contains(int64_t index) const
Returns true if the variable of index 'index' is in the current solution.
virtual bool StopSearch()
Returns true if the search must be stopped.
virtual void Initialize()
Initialize the heuristic; called before starting to build a new solution.
Assignment * BuildSolution()
int64_t SecondaryVarIndex(int64_t index) const
Returns the index of a secondary var.
int64_t Value(int64_t index) const
void SetValue(int64_t index, int64_t value)
virtual bool InitializeSolution()
Virtual method to initialize the solution.
const std::vector< int > & delta_indices() const
Returns the indices of the nodes currently in the insertion delta.
IntVar * Var(int64_t index) const
Returns the variable of index 'index'.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
std::optional< int64_t > Evaluate(bool commit, bool ignore_upper_bound=false, bool update_upper_bound=true)
bool IsSecondaryVar(int64_t index) const
Returns true if 'index' is a secondary variable index.
void Initialize() override
Initialize the heuristic; called before starting to build a new solution.
~LocalCheapestInsertionFilteredHeuristic() override=default
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy, std::vector< RoutingSearchParameters::InsertionSortingProperty > insertion_sorting_properties, LocalSearchFilterManager *filter_manager, bool use_first_solution_hint, BinCapacities *bin_capacities=nullptr, std::function< bool(const std::vector< RoutingModel::VariableValuePair > &, std::vector< RoutingModel::VariableValuePair > *)> optimize_on_insertion=nullptr)
Takes ownership of evaluator.
std::string DebugString() const override
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
~ParallelSavingsFilteredHeuristic() override=default
std::string DebugString() const override
ParallelSavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
virtual void ResetVehicleIndices()
virtual void SetVehicleIndex(int64_t, int)
Assignment * BuildSolutionFromRoutes(const std::function< int64_t(int64_t)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
~RoutingFilteredHeuristic() override=default
void SetNext(int64_t node, int64_t next, int vehicle)
bool VehicleIsEmpty(int vehicle) const
void MakeDisjunctionNodesUnperformed(int64_t node)
bool MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed, always returns true.
RoutingFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
RoutingFilteredHeuristic.
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
RoutingModel * model() const
bool StopSearch() override
Returns true if the search must be stopped.
void AddUnassignedNodesToEmptyVehicles()
Adds all unassigned nodes to empty vehicles.
void MakePartiallyPerformedPairsUnperformed()
RoutingSearchParameters_PairInsertionStrategy PairInsertionStrategy
virtual void BuildRoutesFromSavings()=0
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
SavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
SavingsFilteredHeuristic.
~SavingsFilteredHeuristic() override
friend class SavingsFilteredHeuristicTestPeer
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node, int64_t after_node)
std::unique_ptr< SavingsContainer< Saving > > savings_container_
clang-format off
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
clang-format on
std::string DebugString() const override
SequentialSavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
~SequentialSavingsFilteredHeuristic() override=default
For the time being, Solver is neither MT_SAFE nor MT_HOT.
std::function< bool(int64_t, int64_t, int64_t)> VariableValueComparator
SweepArranger(absl::Span< const std::pair< int64_t, int64_t > > points)
SweepArranger(const SweepArranger &)=delete
This type is neither copyable nor movable.
void ArrangeIndices(std::vector< int64_t > *indices)
void SetSectors(int sectors)
virtual ~SweepArranger()=default
SweepArranger & operator=(const SweepArranger &)=delete
void Update(const std::function< bool(int)> &remove_vehicle)
bool HasCompatibleVehicleOfType(int type, const std::function< bool(int)> &vehicle_is_compatible) const
VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)
void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64_t fixed_cost)
int GetLowestFixedCostVehicleOfType(int type) const
std::pair< int, int > GetCompatibleVehicleOfType(int type, const std::function< bool(int)> &vehicle_is_compatible, const std::function< bool(int)> &stop_and_return_vehicle)
void Reset(const std::function< bool(int)> &store_vehicle)
— VehicleTypeCurator —
int Type(int vehicle) const
dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp
In SWIG mode, we don't want anything besides these top-level includes.
const Assignment * SolveFromAssignmentWithAlternativeSolversAndParameters(const Assignment *assignment, RoutingModel *primary_model, const RoutingSearchParameters &primary_parameters, const std::vector< RoutingModel * > &alternative_models, const std::vector< RoutingSearchParameters > &alternative_parameters, int max_non_improving_iterations)
Same as above but taking alternative parameters for each alternative model.
DecisionBuilder * MakeAllUnperformed(RoutingModel *model)
Returns a DecisionBuilder making all nodes unperformed.
FirstSolutionStrategy::Value AutomaticFirstSolutionStrategy(bool has_pickup_deliveries, bool has_node_precedences, bool has_single_vehicle_node)
std::vector< int64_t > ComputeVehicleEndChainStarts(const RoutingModel &model)
ClosedInterval::Iterator end(ClosedInterval interval)
const Assignment * SolveFromAssignmentWithAlternativeSolvers(const Assignment *assignment, RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters ¶meters, int max_non_improving_iterations)
Same as above, but taking an initial solution.
DecisionBuilder * MakeSweepDecisionBuilder(RoutingModel *model, bool check_assignment)
const Assignment * SolveWithAlternativeSolvers(RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters ¶meters, int max_non_improving_iterations)
trees with all degrees equal to
const bool prioritize_farthest_nodes
std::priority_queue< Seed, std::vector< Seed >, std::greater< Seed > > priority_queue
SeedQueue(bool prioritize_farthest_nodes)
bool operator>(const Seed &other) const
absl::InlinedVector< int64_t, 8 > properties
bool operator<(const StartEndValue &other) const
bool add_unperformed_entries
bool use_neighbors_ratio_for_initialization
double farthest_seeds_ratio
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
bool operator==(const Insertion &other) const
bool operator<(const PickupDeliveryInsertion &other) const
int64_t insert_pickup_after
int64_t insert_delivery_after
unsigned int vehicle_type
bool operator<(const Saving &other) const
double max_memory_usage_bytes