Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
routing_search.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14#ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
16
17#include <sys/types.h>
18
19#include <algorithm>
20#include <cstddef>
21#include <cstdint>
22#include <deque>
23#include <functional>
24#include <initializer_list>
25#include <limits>
26#include <map>
27#include <memory>
28#include <optional>
29#include <queue>
30#include <set>
31#include <string>
32#include <tuple>
33#include <type_traits>
34#include <utility>
35#include <vector>
36
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"
49#include "ortools/util/bitset.h"
50
51namespace operations_research {
52
53// Solves a routing model using alternative models. This assumes that the models
54// are equivalent in the sense that a solution to one model is also a solution
55// to the other models. This is true for models that differ only by their arc
56// costs or objective for instance.
57// The primary model is the main model, to which the returned solution will
58// correspond.
59// The method solves the primary model and alternative models alternatively.
60// It works as follows (all solves use 'parameters'):
61// 1) solve the primary model with a greedy descent,
62// 2) let 'alt' be the first alternative model,
63// 3) solve 'alt' starting from the solution to the primary model with a greedy
64// descent,
65// 4) solve the primary model from the solution to 'alt' with a greedy descent,
66// 5) if the new solution improves the best solution found so far, update it,
67// otherwise increase the iteration counter,
68// 6) if the iteration counter is less than 'max_non_improving_iterations', let
69// 'alt' be the next "round-robin" alternative model, and go to step 3,
70// 7) if 'parameters' specified a metaheuristic, solve the primary model using
71// that metaheuristic starting from the best solution found so far,
72// 8) return the best solution found.
73// Note that if the time limit is reached at any stage, the search is
74// interrupted and the best solution found will be returned immediately.
75// TODO(user): Add a version taking search parameters for alternative models.
77 RoutingModel* primary_model,
78 const std::vector<RoutingModel*>& alternative_models,
79 const RoutingSearchParameters& parameters,
80 int max_non_improving_iterations);
81// Same as above, but taking an initial solution.
83 const Assignment* assignment, RoutingModel* primary_model,
84 const std::vector<RoutingModel*>& alternative_models,
85 const RoutingSearchParameters& parameters,
86 int max_non_improving_iterations);
87// Same as above but taking alternative parameters for each alternative model.
89 const Assignment* assignment, RoutingModel* primary_model,
90 const RoutingSearchParameters& parameters,
91 const std::vector<RoutingModel*>& alternative_models,
92 const std::vector<RoutingSearchParameters>& alternative_parameters,
93 int max_non_improving_iterations);
94
96#ifndef SWIG
101 public:
103 const RoutingModel::VehicleTypeContainer& vehicle_type_container)
104 : vehicle_type_container_(&vehicle_type_container) {}
105
106 int NumTypes() const { return vehicle_type_container_->NumTypes(); }
107
108 int Type(int vehicle) const { return vehicle_type_container_->Type(vehicle); }
109
112 void Reset(const std::function<bool(int)>& store_vehicle);
113
116 void Update(const std::function<bool(int)>& remove_vehicle);
117
119 DCHECK_LT(type, NumTypes());
120 const std::set<VehicleClassEntry>& vehicle_classes =
121 sorted_vehicle_classes_per_type_[type];
122 if (vehicle_classes.empty()) {
123 return -1;
124 }
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];
128 }
129
130 void ReinjectVehicleOfClass(int vehicle, int vehicle_class,
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);
141 }
142 vehicles.push_back(vehicle);
143 }
144
148 int type, const std::function<bool(int)>& vehicle_is_compatible) const;
157 std::pair<int, int> GetCompatibleVehicleOfType(
158 int type, const std::function<bool(int)>& vehicle_is_compatible,
159 const std::function<bool(int)>& stop_and_return_vehicle);
160
161 private:
162 using VehicleClassEntry =
163 RoutingModel::VehicleTypeContainer::VehicleClassEntry;
164 const RoutingModel::VehicleTypeContainer* const vehicle_type_container_;
165 // clang-format off
166 std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;
167 std::vector<std::vector<int> > vehicles_per_vehicle_class_;
168 // clang-format on
169};
170
174AutomaticFirstSolutionStrategy(bool has_pickup_deliveries,
175 bool has_node_precedences,
176 bool has_single_vehicle_node);
177
180std::vector<int64_t> ComputeVehicleEndChainStarts(const RoutingModel& model);
181
194
196// TODO(user): Eventually move this to the core CP solver library
199 public:
201 std::unique_ptr<IntVarFilteredHeuristic> heuristic);
202
203 ~IntVarFilteredDecisionBuilder() override = default;
204
205 Decision* Next(Solver* solver) override;
206
207 std::string DebugString() const override;
208
210 int64_t number_of_decisions() const;
211 int64_t number_of_rejects() const;
212
213 private:
214 const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;
215};
216
219 public:
220 IntVarFilteredHeuristic(Solver* solver, const std::vector<IntVar*>& vars,
221 const std::vector<IntVar*>& secondary_vars,
222 LocalSearchFilterManager* filter_manager);
223
224 virtual ~IntVarFilteredHeuristic() = default;
225
229
232 int64_t number_of_decisions() const { return number_of_decisions_; }
233 int64_t number_of_rejects() const { return number_of_rejects_; }
234
235 virtual std::string DebugString() const { return "IntVarFilteredHeuristic"; }
236
237 protected:
239 void ResetSolution();
241 virtual void Initialize() {}
243 virtual bool InitializeSolution() { return true; }
245 virtual bool BuildSolutionInternal() = 0;
253 std::optional<int64_t> Evaluate(bool commit, bool ignore_upper_bound = false,
254 bool update_upper_bound = true);
256 virtual bool StopSearch() { return false; }
259 void SetValue(int64_t index, int64_t value) {
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;
265 } else {
266 delta_->SetValue(vars_[index], value);
267 }
268 }
269
270 const std::vector<int>& delta_indices() const { return delta_indices_; }
273 int64_t Value(int64_t index) const {
274 return assignment_->IntVarContainer().Element(index).Value();
275 }
276
277 bool Contains(int64_t index) const {
278 return assignment_->IntVarContainer().Element(index).Var() != nullptr;
279 }
280
281 IntVar* Var(int64_t index) const { return vars_[index]; }
283 int64_t SecondaryVarIndex(int64_t index) const {
284 DCHECK(HasSecondaryVars());
285 return index + base_vars_size_;
286 }
287
288 bool HasSecondaryVars() const { return base_vars_size_ != vars_.size(); }
290 bool IsSecondaryVar(int64_t index) const { return index >= base_vars_size_; }
292 void SynchronizeFilters();
293
295
296 private:
299 bool FilterAccept(bool ignore_upper_bound);
300
301 Solver* solver_;
302 std::vector<IntVar*> vars_;
303 const int base_vars_size_;
304 Assignment* const delta_;
305 std::vector<int> delta_indices_;
306 std::vector<bool> is_in_delta_;
307 Assignment* const empty_;
308 LocalSearchFilterManager* filter_manager_;
309 int64_t objective_upper_bound_;
311 int64_t number_of_decisions_;
312 int64_t number_of_rejects_;
313};
314
317 public:
318 RoutingFilteredHeuristic(RoutingModel* model,
319 std::function<bool()> stop_search,
320 LocalSearchFilterManager* filter_manager);
321 ~RoutingFilteredHeuristic() override = default;
324 const std::function<int64_t(int64_t)>& next_accessor);
325 RoutingModel* model() const { return model_; }
327 int GetStartChainEnd(int vehicle) const { return start_chain_ends_[vehicle]; }
329 int GetEndChainStart(int vehicle) const { return end_chain_starts_[vehicle]; }
332 void MakeDisjunctionNodesUnperformed(int64_t node);
342
343 protected:
344 bool StopSearch() override { return stop_search_(); }
345 virtual void SetVehicleIndex(int64_t /*node*/, int /*vehicle*/) {}
346 virtual void ResetVehicleIndices() {}
347 bool VehicleIsEmpty(int vehicle) const {
348 return Value(model()->Start(vehicle)) == model()->End(vehicle);
349 }
350 void SetNext(int64_t node, int64_t next, int vehicle) {
351 SetValue(node, next);
352 if (HasSecondaryVars()) SetValue(SecondaryVarIndex(node), vehicle);
353 }
354
355 private:
357 bool InitializeSolution() override;
358
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_;
363};
364
366 public:
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,
372 LocalSearchFilterManager* filter_manager);
374
375 protected:
377 int64_t distance;
379
380 bool operator<(const StartEndValue& other) const {
381 return std::tie(distance, vehicle) <
382 std::tie(other.distance, other.vehicle);
383 }
384 };
386 int64_t value = 0;
387 int64_t node = -1;
388 int vehicle = -1;
389 };
390 struct Seed {
391 absl::InlinedVector<int64_t, 8> properties;
395 bool is_node_index = true;
396 int index;
397
398 bool operator>(const Seed& other) const {
399 for (size_t i = 0; i < properties.size(); ++i) {
400 if (properties[i] == other.properties[i]) continue;
401 return properties[i] > other.properties[i];
402 }
403 return std::tie(vehicle, is_node_index, index) >
404 std::tie(other.vehicle, other.is_node_index, other.index);
405 }
406 };
407 // clang-format off
408 struct SeedQueue {
411
414 std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed> >
419 };
420
426 std::vector<std::vector<StartEndValue> >
427 ComputeStartEndDistanceForVehicles(absl::Span<const int> vehicles);
428
433 std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
434 SeedQueue* sq);
435 // clang-format on
436
439 void AddSeedNodeToQueue(int node,
440 std::vector<StartEndValue>* start_end_distances,
441 SeedQueue* sq);
442
448 void InsertBetween(int64_t node, int64_t predecessor, int64_t successor,
449 int vehicle = -1);
454 // TODO(user): Replace 'insert_before' and 'insert_after' by 'predecessor'
455 // and 'successor' in the code.
456 int64_t GetEvaluatorInsertionCostForNodeAtPosition(int64_t node_to_insert,
457 int64_t insert_after,
458 int64_t insert_before,
459 int vehicle) const;
463 std::optional<int64_t> GetInsertionCostForNodeAtPosition(
464 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
465 int vehicle, int hint_weight = 0);
468 std::optional<int64_t> GetInsertionCostForPairAtPositions(
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);
474 int64_t GetUnperformedValue(int64_t node_to_insert) const;
475
476 bool HasHintedNext(int node) const {
477 CHECK_LT(node, hint_next_values_.size());
478 return hint_next_values_[node] != -1;
479 }
480 bool HasHintedPrev(int node) const {
481 CHECK_LT(node, hint_prev_values_.size());
482 return hint_prev_values_[node] != -1;
483 }
484 bool IsHint(int node, int64_t next) const {
485 return node < hint_next_values_.size() && hint_next_values_[node] == next;
486 }
487
488 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator_;
489 // TODO(user): Remove mutable if possible.
490 mutable std::vector<EvaluatorCache> evaluator_cache_;
491 std::function<int64_t(int64_t)> penalty_evaluator_;
492 std::vector<int> hint_next_values_;
493 std::vector<int> hint_prev_values_;
494};
495
505 public:
529
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,
535 LocalSearchFilterManager* filter_manager,
538 bool BuildSolutionInternal() override;
539 std::string DebugString() const override {
540 return "GlobalCheapestInsertionFilteredHeuristic";
541 }
542
543 private:
545 class NodeEntryQueue;
546
548 class PairEntry {
549 public:
550 PairEntry(int pickup_to_insert, int pickup_insert_after,
551 int delivery_to_insert, int delivery_insert_after, int vehicle,
552 int64_t bucket)
553 : value_(std::numeric_limits<int64_t>::max()),
554 heap_index_(-1),
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),
559 vehicle_(vehicle),
560 bucket_(bucket) {}
561 // Note: for compatibility reasons, comparator follows tie-breaking rules
562 // used in the first version of GlobalCheapestInsertion.
563 bool operator<(const PairEntry& other) const {
564 // We give higher priority to insertions from lower buckets.
565 if (bucket_ != other.bucket_) {
566 return bucket_ > other.bucket_;
567 }
568 // We then compare by value, then we favor insertions (vehicle != -1).
569 // The rest of the tie-breaking is done with std::tie.
570 if (value_ != other.value_) {
571 return value_ > other.value_;
572 }
573 if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
574 return vehicle_ == -1;
575 }
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_,
580 other.vehicle_);
581 }
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;
589 }
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; }
594
595 private:
596 int64_t value_;
597 int heap_index_;
598 int pickup_to_insert_;
599 int pickup_insert_after_;
600 int delivery_to_insert_;
601 int delivery_insert_after_;
602 int vehicle_;
603 int64_t bucket_;
604 };
605
606 typedef absl::flat_hash_set<PairEntry*> PairEntries;
607
609 template <typename T>
610 class EntryAllocator {
611 public:
612 EntryAllocator() = default;
613 void Clear() {
614 entries_.clear();
615 free_entries_.clear();
616 }
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();
622 *entry = T(args...);
623 return entry;
624 } else {
625 entries_.emplace_back(args...);
626 return &entries_.back();
627 }
628 }
629 void FreeEntry(T* entry) { free_entries_.push_back(entry); }
630
631 private:
633 std::deque<T> entries_;
634 std::vector<T*> free_entries_;
635 };
636
643 bool InsertPairsAndNodesByRequirementTopologicalOrder();
644
651 bool InsertPairs(
652 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket);
653
657 bool UseEmptyVehicleTypeCuratorForVehicle(int vehicle,
658 bool all_vehicles = true) const {
659 // NOTE: When the evaluator_ is null, filters are used to evaluate the cost
660 // and feasibility of inserting on each vehicle, so all vehicles are
661 // considered for insertion instead of just one per class.
662 return vehicle >= 0 && VehicleIsEmpty(vehicle) && all_vehicles &&
663 evaluator_ != nullptr;
664 }
665
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);
677
685 bool InsertNodesOnRoutes(
686 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,
687 const absl::flat_hash_set<int>& vehicles);
688
696 bool InsertNodeEntryUsingEmptyVehicleTypeCurator(
697 const SparseBitset<int>& nodes, bool all_vehicles, NodeEntryQueue* queue);
698
704 bool SequentialInsertNodes(
705 const std::map<int64_t, std::vector<int>>& nodes_by_bucket);
706
710 void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,
711 std::vector<int>* unused_vehicles,
712 absl::flat_hash_set<int>* used_vehicles);
713
716 bool IsCheapestClassRepresentative(int vehicle) const;
717
721 void InsertFarthestNodesAsSeeds();
722
731 int InsertSeedNode(
732 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
733 SeedQueue* sq, std::vector<bool>* is_vehicle_used);
734 // clang-format on
735
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);
788 }
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,
821 int vehicle,
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);
832
835 bool InitializePositions(const SparseBitset<int>& nodes,
836 const absl::flat_hash_set<int>& vehicles,
837 NodeEntryQueue* queue);
843 void InitializeInsertionEntriesPerformingNode(
844 int64_t node, const absl::flat_hash_set<int>& vehicles,
845 NodeEntryQueue* queue);
848 bool UpdateAfterNodeInsertion(const SparseBitset<int>& nodes, int vehicle,
849 int64_t node, int64_t insert_after,
850 bool all_vehicles, NodeEntryQueue* queue);
854 bool UpdateExistingNodeEntriesOnChain(const SparseBitset<int>& nodes,
855 int vehicle, int64_t insert_after_start,
856 int64_t insert_after_end,
857 bool all_vehicles,
858 NodeEntryQueue* queue);
861 bool AddNodeEntriesAfter(const SparseBitset<int>& nodes, int vehicle,
862 int64_t insert_after, bool all_vehicles,
863 NodeEntryQueue* queue);
864
868 void AddNodeEntry(int64_t node, int64_t insert_after, int vehicle,
869 bool all_vehicles, NodeEntryQueue* queue);
870
871 void ResetVehicleIndices() override {
872 node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);
873 }
874
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;
878 }
879
882 bool CheckVehicleIndices() const;
883
885 int64_t GetBucketOfNode(int node) const {
886 return model()->VehicleVar(node)->Size();
887 }
888
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));
894 }
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));
899 }
900 return std::min(max_pickup_bucket, max_delivery_bucket);
901 }
902
905 template <typename T>
906 bool StopSearchAndCleanup(AdjustablePriorityQueue<T>* priority_queue) {
907 if (!StopSearch()) return false;
908 if constexpr (std::is_same_v<T, PairEntry>) {
909 pair_entry_allocator_.Clear();
910 }
911 priority_queue->Clear();
912 return true;
913 }
914
917 std::vector<int> node_index_to_vehicle_;
918
919 const RoutingModel::NodeNeighborsByCostClass*
920 node_index_to_neighbors_by_cost_class_;
921
922 std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;
923
924 mutable EntryAllocator<PairEntry> pair_entry_allocator_;
925};
926
927// Holds sequences of insertions.
928// A sequence of insertions must be in the same path, each insertion must
929// take place either after the previously inserted node or further down the
930// path, never before.
932 private:
933 // InsertionSequenceContainer holds all insertion sequences in the same vector
934 // contiguously, each insertion sequence is defined by a pair of bounds.
935 // Using Insertion* directly to delimit bounds would cause out-of-memory reads
936 // when the underlying vector<Insertion> is extended and reallocated,
937 // so this stores integer bounds in InsertionBounds to delimit sequences,
938 // and InsertionSequenceIterator translates those bounds to
939 // Insertion*-based ranges (InsertionSequence) on-the-fly when iterating over
940 // all sequences.
941 struct InsertionBounds {
942 size_t begin;
943 size_t end;
944 int vehicle;
945 int neg_hint_weight;
946 int64_t cost;
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,
950 other.begin);
951 }
952 size_t Size() const { return end - begin; }
953 };
954
955 public:
956 struct Insertion {
957 int pred;
958 int node;
959 bool operator==(const Insertion& other) const {
960 return pred == other.pred && node == other.node;
961 }
962 };
963
964 // Represents an insertion sequence as passed to AddInsertionSequence.
965 // This only allows to modify the cost, as a means to reorder sequences.
967 public:
968 InsertionSequence(Insertion* data, InsertionBounds* bounds)
969 : data_(data), bounds_(bounds) {}
970
971 bool operator!=(const InsertionSequence& other) const {
972 DCHECK_NE(data_, other.data_);
973 return bounds_ != other.bounds_;
974 }
975
976 const Insertion* begin() const { return data_ + bounds_->begin; }
977 const Insertion* end() const { return data_ + bounds_->end; }
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; }
982 void SetHintWeight(int hint_weight) {
983 bounds_->neg_hint_weight = -hint_weight;
984 }
985 int NegHintWeight() const { return bounds_->neg_hint_weight; }
986
987 private:
988 const Insertion* const data_;
989 InsertionBounds* const bounds_;
990 };
992 public:
993 InsertionSequenceIterator(Insertion* data, InsertionBounds* bounds)
994 : data_(data), bounds_(bounds) {}
995 bool operator!=(const InsertionSequenceIterator& other) const {
996 DCHECK_EQ(data_, other.data_);
997 return bounds_ != other.bounds_;
998 }
1000 ++bounds_;
1001 return *this;
1002 }
1003 InsertionSequence operator*() const { return {data_, bounds_}; }
1004
1005 private:
1006 Insertion* data_;
1007 InsertionBounds* bounds_;
1008 };
1009
1010 // InsertionSequenceContainer is a range over insertion sequences.
1012 return {insertions_.data(), insertion_bounds_.data()};
1013 }
1015 return {insertions_.data(),
1016 insertion_bounds_.data() + insertion_bounds_.size()};
1017 }
1018 // Returns the number of sequences of this container.
1019 size_t Size() const { return insertion_bounds_.size(); }
1020
1021 // Adds an insertion sequence to the container.
1022 // Passing an initializer_list allows deeper optimizations by the compiler
1023 // for cases where the sequence has a compile-time fixed 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(),
1029 .vehicle = vehicle,
1030 .cost = 0});
1031 insertions_.insert(insertions_.end(), insertion_sequence.begin(),
1032 insertion_sequence.end());
1033 }
1034
1035 // Adds an insertion sequence to the container.
1036 void AddInsertionSequence(int vehicle,
1037 absl::Span<const Insertion> insertion_sequence) {
1038 insertion_bounds_.push_back(
1039 {.begin = insertions_.size(),
1040 .end = insertions_.size() + insertion_sequence.size(),
1041 .vehicle = vehicle,
1042 .cost = 0});
1043 insertions_.insert(insertions_.end(), insertion_sequence.begin(),
1044 insertion_sequence.end());
1045 }
1046
1047 // Similar to std::remove_if(), removes all sequences that match a predicate.
1048 // This keeps original order, and removes selected sequences.
1049 void RemoveIf(const std::function<bool(const InsertionSequence&)>& p) {
1050 size_t from = 0;
1051 size_t to = 0;
1052 for (const InsertionSequence& sequence : *this) {
1053 // TODO(user): Benchmark this against std::swap().
1054 if (!p(sequence)) insertion_bounds_[to++] = insertion_bounds_[from];
1055 ++from;
1056 }
1057 insertion_bounds_.resize(to);
1058 }
1059
1060 // Sorts sequences according to (cost, vehicle).
1061 // TODO(user): benchmark this against other ways to get insertion
1062 // sequence in order, for instance sorting by index, separating {cost, index},
1063 // making a heap.
1064 void Sort() { std::sort(insertion_bounds_.begin(), insertion_bounds_.end()); }
1065
1066 // Removes all sequences.
1067 void Clear() {
1068 insertions_.clear();
1069 insertion_bounds_.clear();
1070 }
1071
1072 private:
1073 std::vector<Insertion> insertions_;
1074 std::vector<InsertionBounds> insertion_bounds_;
1075};
1076
1077// Generates insertion positions respecting structural constraints.
1079 public:
1081
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,
1103 InsertionSequenceContainer& insertions);
1104
1105 private:
1106 // Information[i] describes the insertion between path[i] and path[i+1].
1107 std::vector<int> next_decrease_; // next position after a delivery.
1108 std::vector<int> next_increase_; // next position after a pickup.
1109 std::vector<int> prev_decrease_; // previous position after delivery.
1110 std::vector<int> prev_increase_; // previous position after pickup.
1111};
1112
1117 int64_t value;
1119
1120 bool operator<(const PickupDeliveryInsertion& other) const {
1121 return std::tie(neg_hint_weight, value, insert_pickup_after,
1123 std::tie(other.neg_hint_weight, other.value,
1125 other.vehicle);
1126 }
1127};
1128
1136 public:
1139 RoutingModel* model, std::function<bool()> stop_search,
1140 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
1141 RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy,
1142 std::vector<RoutingSearchParameters::InsertionSortingProperty>
1143 insertion_sorting_properties,
1144 LocalSearchFilterManager* filter_manager, bool use_first_solution_hint,
1145 BinCapacities* bin_capacities = nullptr,
1146 std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,
1147 std::vector<RoutingModel::VariableValuePair>*)>
1148 optimize_on_insertion = nullptr);
1150 bool BuildSolutionInternal() override;
1151 std::string DebugString() const override {
1152 return "LocalCheapestInsertionFilteredHeuristic";
1153 }
1154
1155 protected:
1156 void Initialize() override;
1157
1158 private:
1159 struct NodeInsertion {
1160 int64_t insert_after;
1161 int vehicle;
1162 int neg_hint_weight;
1163 int64_t value;
1164
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,
1168 other.vehicle);
1169 }
1170 };
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);
1192
1196 std::vector<PickupDeliveryInsertion> ComputeEvaluatorSortedPairPositions(
1197 int pickup, int delivery);
1198
1199 // Tries to insert any alternative of the given pair,
1200 // ordered by cost of pickup insertion, then by cost of delivery insertion.
1201 void InsertBestPickupThenDelivery(const PickupDeliveryPair& pair);
1202 // Tries to insert any alternative of the given pair,
1203 // ordered by the sum of pickup and delivery insertion.
1204 void InsertBestPair(const PickupDeliveryPair& pair);
1205 // Tries to insert any alternative of the given pair,
1206 // at a position that preserves the multitour property,
1207 // ordered by the sum of pickup and delivery insertion.
1208 void InsertBestPairMultitour(const PickupDeliveryPair& pair);
1209 // Tries to insert a pair at the given location. Returns true iff inserted.
1210 bool InsertPair(int64_t pickup, int64_t insert_pickup_after, int64_t delivery,
1211 int64_t insert_delivery_after, int vehicle);
1212
1213 // Runs an internal optimization. Returns true if the solution was changed.
1214 bool OptimizeOnInsertion(std::vector<int> delta_indices);
1215
1216 // Returns true if bin capacities should be updated.
1217 // TODO(user): Allow updating bin capacities when we do internal
1218 // optimizations.
1219 bool MustUpdateBinCapacities() const {
1220 return bin_capacities_ != nullptr && optimize_on_insertion_ == nullptr;
1221 }
1222
1223 std::vector<Seed> insertion_order_;
1224 const RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy_;
1225 std::vector<RoutingSearchParameters::InsertionSortingProperty>
1226 insertion_sorting_properties_;
1227 InsertionSequenceContainer insertion_container_;
1228 InsertionSequenceGenerator insertion_generator_;
1229
1230 const bool use_first_solution_hint_;
1231
1232 BinCapacities* const bin_capacities_;
1233
1234 std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,
1235 std::vector<RoutingModel::VariableValuePair>*)>
1236 optimize_on_insertion_;
1237 bool synchronize_insertion_optimizer_ = true;
1238
1239 const bool use_random_insertion_order_;
1240 std::mt19937 rnd_;
1241};
1242
1246 public:
1248 std::function<bool()> stop_search,
1249 LocalSearchFilterManager* filter_manager);
1251 bool BuildSolutionInternal() override;
1252
1253 private:
1254 class PartialRoutesAndLargeVehicleIndicesFirst {
1255 public:
1256 explicit PartialRoutesAndLargeVehicleIndicesFirst(
1257 const CheapestAdditionFilteredHeuristic& builder)
1258 : builder_(builder) {}
1259 bool operator()(int vehicle1, int vehicle2) const;
1260
1261 private:
1262 const CheapestAdditionFilteredHeuristic& builder_;
1263 };
1265 template <typename Iterator>
1266 std::vector<int64_t> GetPossibleNextsFromIterator(int64_t node,
1267 Iterator start,
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);
1275 }
1276 }
1277 return nexts;
1278 }
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;
1284};
1285
1290 public:
1293 RoutingModel* model, std::function<bool()> stop_search,
1294 std::function<int64_t(int64_t, int64_t)> evaluator,
1295 LocalSearchFilterManager* filter_manager);
1297 std::string DebugString() const override {
1298 return "EvaluatorCheapestAdditionFilteredHeuristic";
1299 }
1300
1301 private:
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;
1306
1307 std::function<int64_t(int64_t, int64_t)> evaluator_;
1308};
1309
1314 public:
1317 RoutingModel* model, std::function<bool()> stop_search,
1319 LocalSearchFilterManager* filter_manager);
1321 std::string DebugString() const override {
1322 return "ComparatorCheapestAdditionFilteredHeuristic";
1323 }
1324
1325 private:
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;
1330
1332};
1333
1343 public:
1347 double neighbors_ratio = 1.0;
1353 bool add_reverse_arcs = false;
1356 double arc_coefficient = 1.0;
1357 };
1358
1359 SavingsFilteredHeuristic(RoutingModel* model,
1360 std::function<bool()> stop_search,
1361 SavingsParameters parameters,
1362 LocalSearchFilterManager* filter_manager);
1364 bool BuildSolutionInternal() override;
1365
1366 protected:
1367 struct Saving {
1368 int64_t saving;
1369 unsigned int vehicle_type : 20;
1370 unsigned int before_node : 22;
1371 unsigned int after_node : 22;
1372 bool operator<(const Saving& other) const {
1373 return std::tie(saving, vehicle_type, before_node, after_node) <
1374 std::tie(other.saving, other.vehicle_type, other.before_node,
1375 other.after_node);
1376 }
1377 };
1378
1379 template <typename S>
1380 class SavingsContainer;
1381
1382 virtual double ExtraSavingsMemoryMultiplicativeFactor() const = 0;
1383
1384 virtual void BuildRoutesFromSavings() = 0;
1385
1395 int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node,
1396 int64_t after_node);
1397
1398 // clang-format off
1399 std::unique_ptr<SavingsContainer<Saving> > savings_container_;
1400 // clang-format on
1401 std::unique_ptr<VehicleTypeCurator> vehicle_type_curator_;
1402
1403 private:
1408 // clang-format off
1409 void AddSymmetricArcsToAdjacencyLists(
1410 std::vector<std::vector<int64_t> >* adjacency_lists);
1411 // clang-format on
1412
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)};
1428 }
1429
1433 int64_t MaxNumNeighborsPerNode(int num_vehicle_types) const;
1434
1435 const SavingsParameters savings_params_;
1436
1438};
1439
1441 public:
1443 std::function<bool()> stop_search,
1444 SavingsParameters parameters,
1445 LocalSearchFilterManager* filter_manager)
1446 : SavingsFilteredHeuristic(model, std::move(stop_search), parameters,
1447 filter_manager) {}
1449 std::string DebugString() const override {
1450 return "SequentialSavingsFilteredHeuristic";
1451 }
1452
1453 private:
1458 void BuildRoutesFromSavings() override;
1459 double ExtraSavingsMemoryMultiplicativeFactor() const override { return 1.0; }
1460};
1461
1463 public:
1465 std::function<bool()> stop_search,
1466 SavingsParameters parameters,
1467 LocalSearchFilterManager* filter_manager)
1468 : SavingsFilteredHeuristic(model, std::move(stop_search), parameters,
1469 filter_manager) {}
1471 std::string DebugString() const override {
1472 return "ParallelSavingsFilteredHeuristic";
1473 }
1474
1475 private:
1486 void BuildRoutesFromSavings() override;
1487
1488 double ExtraSavingsMemoryMultiplicativeFactor() const override { return 2.0; }
1489
1494 void MergeRoutes(int first_vehicle, int second_vehicle, int64_t before_node,
1495 int64_t after_node);
1496
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_;
1504};
1505
1509
1511 public:
1513 std::function<bool()> stop_search,
1514 LocalSearchFilterManager* filter_manager,
1515 bool use_minimum_matching);
1517 bool BuildSolutionInternal() override;
1518 std::string DebugString() const override {
1519 return "ChristofidesFilteredHeuristic";
1520 }
1521
1522 private:
1523 const bool use_minimum_matching_;
1524};
1525
1529 public:
1530 explicit SweepArranger(absl::Span<const std::pair<int64_t, int64_t>> points);
1531
1532 // This type is neither copyable nor movable.
1535
1536 virtual ~SweepArranger() = default;
1537 void ArrangeIndices(std::vector<int64_t>* indices);
1538 void SetSectors(int sectors) { sectors_ = sectors; }
1539
1540 private:
1541 std::vector<int> coordinates_;
1542 int sectors_;
1543};
1544#endif // SWIG
1545
1546// Returns a DecisionBuilder building a first solution based on the Sweep
1547// heuristic. Mostly suitable when cost is proportional to distance.
1548DecisionBuilder* MakeSweepDecisionBuilder(RoutingModel* model,
1549 bool check_assignment);
1550
1551// Returns a DecisionBuilder making all nodes unperformed.
1552DecisionBuilder* MakeAllUnperformed(RoutingModel* model);
1553
1554} // namespace operations_research
1555
1556#endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
CheapestAdditionFilteredHeuristic.
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
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)
void InitializeSeedQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, SeedQueue *sq)
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)
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.
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
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.
bool operator!=(const InsertionSequenceIterator &other) 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.
size_t Size() const
Returns the number of sequences of this container.
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)
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 —
Generic filter-based heuristic applied to IntVars.
bool HasSecondaryVars() const
Returns true if there are secondary variables.
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.
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.
int64_t SecondaryVarIndex(int64_t index) const
Returns the index of a secondary var.
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(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.
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
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,.
Assignment * BuildSolutionFromRoutes(const std::function< int64_t(int64_t)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
void SetNext(int64_t node, int64_t next, int vehicle)
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,.
bool StopSearch() override
Returns true if the search must be stopped.
void AddUnassignedNodesToEmptyVehicles()
Adds all unassigned nodes to empty vehicles.
RoutingSearchParameters_PairInsertionStrategy PairInsertionStrategy
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.
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
SequentialSavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
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)
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 —
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 &parameters, 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 &parameters, int max_non_improving_iterations)
STL namespace.
bool Next()
trees with all degrees equal to
std::priority_queue< Seed, std::vector< Seed >, std::greater< Seed > > priority_queue
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
bool operator<(const PickupDeliveryInsertion &other) const