Google OR-Tools: ortools/constraint_solver/routing

Google OR-Tools: ortools/constraint_solver/routing_search.h Source File

14#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_

15#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_

17#include <algorithm>

18#include <cstddef>

19#include <cstdint>

20#include <deque>

21#include <functional>

22#include <initializer_list>

23#include <limits>

24#include <map>

25#include <memory>

26#include <optional>

27#include <queue>

28#include <random>

29#include <set>

30#include <string>

31#include <tuple>

32#include <type_traits>

33#include <utility>

34#include <vector>

36#include "absl/container/flat_hash_set.h"

37#include "absl/container/inlined_vector.h"

38#include "absl/log/check.h"

39#include "absl/types/span.h"

78 const std::vector<RoutingModel*>& alternative_models,

80 int max_non_improving_iterations);

84 const std::vector<RoutingModel*>& alternative_models,

86 int max_non_improving_iterations);

91 const std::vector<RoutingModel*>& alternative_models,

92 const std::vector<RoutingSearchParameters>& alternative_parameters,

93 int max_non_improving_iterations);

96#ifndef SWIG

101 public:

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

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

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;

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 =

165

166 std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;

167 std::vector<std::vector<int> > vehicles_per_vehicle_class_;

168

169};

170

175 bool has_node_precedences,

176 bool has_single_vehicle_node);

177

181

194

196

199 public:

201 std::unique_ptr<IntVarFilteredHeuristic> heuristic);

202

204

206

207 std::string DebugString() const override;

208

212

213 private:

214 const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;

215};

216

219 public:

221 const std::vector<IntVar*>& secondary_vars,

223

225

229

234

235 virtual std::string DebugString() const { return "IntVarFilteredHeuristic"; }

236

237 protected:

253 std::optional<int64_t> Evaluate(bool commit, bool ignore_upper_bound = false,

254 bool update_upper_bound = true);

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

278 return assignment_->IntVarContainer().Element(index).Var() != nullptr;

279 }

280

281 IntVar* Var(int64_t index) const { return vars_[index]; }

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_; }

293

295

296 private:

299 bool FilterAccept(bool ignore_upper_bound);

300

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_;

313};

314

317 public:

319 std::function<bool()> stop_search,

324 const std::function<int64_t(int64_t)>& next_accessor);

327 int GetStartChainEnd(int vehicle) const { return start_chain_ends_[vehicle]; }

329 int GetEndChainStart(int vehicle) const { return end_chain_starts_[vehicle]; }

342

343 protected:

344 bool StopSearch() override { return stop_search_(); }

350 void SetNext(int64_t node, int64_t next, int vehicle) {

353 }

354

355 private:

358

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:

370 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,

371 std::function<int64_t(int64_t)> penalty_evaluator,

374

375 protected:

397

399 for (size_t i = 0; i < properties.size(); ++i) {

402 }

405 }

406 };

407

411

414 std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed> >

419 };

420

426 std::vector<std::vector<StartEndValue> >

428

433 std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,

435

436

440 std::vector<StartEndValue>* start_end_distances,

442

448 void InsertBetween(int64_t node, int64_t predecessor, int64_t successor,

449 int vehicle = -1);

454

455

457 int64_t insert_after,

458 int64_t insert_before,

459 int vehicle) const;

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);

475

484 bool IsHint(int node, int64_t next) const {

486 }

487

488 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator_;

489

494};

495

505 public:

509 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,

510 std::function<int64_t(int64_t)> penalty_evaluator,

516 return "GlobalCheapestInsertionFilteredHeuristic";

517 }

518

519 private:

521 class NodeEntryQueue;

522

524 class PairEntry {

525 public:

526 PairEntry(int pickup_to_insert, int pickup_insert_after,

527 int delivery_to_insert, int delivery_insert_after, int vehicle,

528 int64_t bucket)

529 : value_(std::numeric_limits<int64_t>::max()),

530 heap_index_(-1),

531 pickup_to_insert_(pickup_to_insert),

532 pickup_insert_after_(pickup_insert_after),

533 delivery_to_insert_(delivery_to_insert),

534 delivery_insert_after_(delivery_insert_after),

535 vehicle_(vehicle),

536 bucket_(bucket) {}

537

538

539 bool operator<(const PairEntry& other) const {

540

541 if (bucket_ != other.bucket_) {

542 return bucket_ > other.bucket_;

543 }

544

545

546 if (value_ != other.value_) {

547 return value_ > other.value_;

548 }

549 if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {

550 return vehicle_ == -1;

551 }

552 return std::tie(pickup_insert_after_, pickup_to_insert_,

553 delivery_insert_after_, delivery_to_insert_, vehicle_) >

554 std::tie(other.pickup_insert_after_, other.pickup_to_insert_,

555 other.delivery_insert_after_, other.delivery_to_insert_,

556 other.vehicle_);

557 }

558 void SetHeapIndex(int h) { heap_index_ = h; }

559 int GetHeapIndex() const { return heap_index_; }

560 void set_value(int64_t value) { value_ = value; }

561 int pickup_to_insert() const { return pickup_to_insert_; }

562 int pickup_insert_after() const { return pickup_insert_after_; }

563 void set_pickup_insert_after(int pickup_insert_after) {

564 pickup_insert_after_ = pickup_insert_after;

565 }

566 int delivery_to_insert() const { return delivery_to_insert_; }

567 int delivery_insert_after() const { return delivery_insert_after_; }

568 int vehicle() const { return vehicle_; }

569 void set_vehicle(int vehicle) { vehicle_ = vehicle; }

570

571 private:

572 int64_t value_;

573 int heap_index_;

574 int pickup_to_insert_;

575 int pickup_insert_after_;

576 int delivery_to_insert_;

577 int delivery_insert_after_;

578 int vehicle_;

579 int64_t bucket_;

580 };

581

582 typedef absl::flat_hash_set<PairEntry*> PairEntries;

583

585 template <typename T>

586 class EntryAllocator {

587 public:

588 EntryAllocator() = default;

589 void Clear() {

590 entries_.clear();

591 free_entries_.clear();

592 }

593 template <typename... Args>

594 T* NewEntry(const Args&... args) {

595 if (!free_entries_.empty()) {

596 auto* entry = free_entries_.back();

597 free_entries_.pop_back();

598 *entry = T(args...);

599 return entry;

600 } else {

601 entries_.emplace_back(args...);

602 return &entries_.back();

603 }

604 }

605 void FreeEntry(T* entry) { free_entries_.push_back(entry); }

606

607 private:

609 std::deque<T> entries_;

610 std::vector<T*> free_entries_;

611 };

612

619 bool InsertPairsAndNodesByRequirementTopologicalOrder();

626 bool InsertPairsAndNodesByPrecedenceTopologicalOrder();

627

634 bool InsertPairs(

635 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket);

636

640 bool UseEmptyVehicleTypeCuratorForVehicle(int vehicle,

641 bool all_vehicles = true) const {

642

643

644

645 return vehicle >= 0 && VehicleIsEmpty(vehicle) && all_vehicles &&

647 }

648

655 bool InsertPairEntryUsingEmptyVehicleTypeCurator(

656 const absl::flat_hash_set<int>& pair_indices, PairEntry* pair_entry,

657 AdjustablePriorityQueue<PairEntry>* priority_queue,

658 std::vector<PairEntries>* pickup_to_entries,

659 std::vector<PairEntries>* delivery_to_entries);

660

668 bool InsertNodesOnRoutes(

669 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,

670 const absl::flat_hash_set<int>& vehicles);

671

679 bool InsertNodeEntryUsingEmptyVehicleTypeCurator(

680 const SparseBitset<int>& nodes, bool all_vehicles, NodeEntryQueue* queue);

681

687 bool SequentialInsertNodes(

688 const std::map<int64_t, std::vector<int>>& nodes_by_bucket);

689

693 void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,

694 std::vector<int>* unused_vehicles,

695 absl::flat_hash_set<int>* used_vehicles);

696

699 bool IsCheapestClassRepresentative(int vehicle) const;

700

704 void InsertFarthestNodesAsSeeds();

705

714 int InsertSeedNode(

715 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,

716 SeedQueue* sq, std::vector<bool>* is_vehicle_used);

717

718

721 bool InitializePairPositions(

722 const absl::flat_hash_set<int>& pair_indices,

723 AdjustablePriorityQueue<PairEntry>* priority_queue,

724 std::vector<PairEntries>* pickup_to_entries,

725 std::vector<PairEntries>* delivery_to_entries);

731 void InitializeInsertionEntriesPerformingPair(

732 int64_t pickup, int64_t delivery,

733 AdjustablePriorityQueue<PairEntry>* priority_queue,

734 std::vector<PairEntries>* pickup_to_entries,

735 std::vector<PairEntries>* delivery_to_entries);

739 bool UpdateAfterPairInsertion(

740 const absl::flat_hash_set<int>& pair_indices, int vehicle, int64_t pickup,

741 int64_t pickup_position, int64_t delivery, int64_t delivery_position,

742 AdjustablePriorityQueue<PairEntry>* priority_queue,

743 std::vector<PairEntries>* pickup_to_entries,

744 std::vector<PairEntries>* delivery_to_entries);

747 bool UpdateExistingPairEntriesAfter(

748 int64_t insert_after, AdjustablePriorityQueue<PairEntry>* priority_queue,

749 std::vector<PairEntries>* pickup_to_entries,

750 std::vector<PairEntries>* delivery_to_entries);

756 bool AddPairEntriesAfter(const absl::flat_hash_set<int>& pair_indices,

757 int vehicle, int64_t insert_after,

758 int64_t skip_entries_inserting_delivery_after,

759 AdjustablePriorityQueue<PairEntry>* priority_queue,

760 std::vector<PairEntries>* pickup_to_entries,

761 std::vector<PairEntries>* delivery_to_entries) {

762 return AddPairEntriesWithDeliveryAfter(pair_indices, vehicle, insert_after,

763 priority_queue, pickup_to_entries,

764 delivery_to_entries) &&

765 AddPairEntriesWithPickupAfter(pair_indices, vehicle, insert_after,

766 skip_entries_inserting_delivery_after,

767 priority_queue, pickup_to_entries,

768 delivery_to_entries);

769 }

776 bool AddPairEntriesWithPickupAfter(

777 const absl::flat_hash_set<int>& pair_indices, int vehicle,

778 int64_t insert_after, int64_t skip_entries_inserting_delivery_after,

779 AdjustablePriorityQueue<PairEntry>* priority_queue,

780 std::vector<PairEntries>* pickup_to_entries,

781 std::vector<PairEntries>* delivery_to_entries);

785 bool AddPairEntriesWithDeliveryAfter(

786 const absl::flat_hash_set<int>& pair_indices, int vehicle,

787 int64_t insert_after, AdjustablePriorityQueue<PairEntry>* priority_queue,

788 std::vector<PairEntries>* pickup_to_entries,

789 std::vector<PairEntries>* delivery_to_entries);

792 void DeletePairEntry(PairEntry* entry,

793 AdjustablePriorityQueue<PairEntry>* priority_queue,

794 std::vector<PairEntries>* pickup_to_entries,

795 std::vector<PairEntries>* delivery_to_entries);

800 void AddPairEntry(int64_t pickup, int64_t pickup_insert_after,

801 int64_t delivery, int64_t delivery_insert_after,

802 int vehicle,

803 AdjustablePriorityQueue<PairEntry>* priority_queue,

804 std::vector<PairEntries>* pickup_entries,

805 std::vector<PairEntries>* delivery_entries);

811 bool UpdatePairEntry(PairEntry* pair_entry,

812 AdjustablePriorityQueue<PairEntry>* priority_queue);

813

816 bool InitializePositions(const SparseBitset<int>& nodes,

817 const absl::flat_hash_set<int>& vehicles,

824 void InitializeInsertionEntriesPerformingNode(

825 int64_t node, const absl::flat_hash_set<int>& vehicles,

829 bool UpdateAfterNodeInsertion(const SparseBitset<int>& nodes, int vehicle,

830 int64_t node, int64_t insert_after,

834 bool AddNodeEntriesAfter(const SparseBitset<int>& nodes, int vehicle,

835 int64_t insert_after, bool all_vehicles,

837

841 void AddNodeEntry(int64_t node, int64_t insert_after, int vehicle,

843

845 node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);

846 }

847

848 void SetVehicleIndex(int64_t node, int vehicle) override {

849 DCHECK_LT(node, node_index_to_vehicle_.size());

850 node_index_to_vehicle_[node] = vehicle;

851 }

852

855 bool CheckVehicleIndices() const;

856

858 int64_t GetBucketOfNode(int node) const {

860 }

861

863 int64_t GetBucketOfPair(const PickupDeliveryPair& pair) const {

864 int64_t max_pickup_bucket = 0;

865 for (int64_t pickup : pair.pickup_alternatives) {

866 max_pickup_bucket = std::max(max_pickup_bucket, GetBucketOfNode(pickup));

867 }

868 int64_t max_delivery_bucket = 0;

869 for (int64_t delivery : pair.delivery_alternatives) {

870 max_delivery_bucket =

871 std::max(max_delivery_bucket, GetBucketOfNode(delivery));

872 }

873 return std::min(max_pickup_bucket, max_delivery_bucket);

874 }

875

878 template <typename T>

879 bool StopSearchAndCleanup(AdjustablePriorityQueue<T>* priority_queue) {

881 if constexpr (std::is_same_v<T, PairEntry>) {

882 pair_entry_allocator_.Clear();

883 }

884 priority_queue->Clear();

885 return true;

886 }

887

888 GlobalCheapestInsertionParameters gci_params_;

890 bool is_sequential_;

892 std::vector<int> node_index_to_vehicle_;

893

894 const RoutingModel::NodeNeighborsByCostClass*

895 node_index_to_neighbors_by_cost_class_;

896

897 std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;

898

899

900 SparseBitset<int> temp_inserted_nodes_;

901

902 mutable EntryAllocator<PairEntry> pair_entry_allocator_;

903};

904

905

906

907

908

910 private:

911

912

913

914

915

916

917

918

919 struct InsertionBounds {

921 size_t end;

922 int vehicle;

923 int neg_hint_weight;

924 int64_t cost;

925 bool operator<(const InsertionBounds& other) const {

926 return std::tie(neg_hint_weight, cost, vehicle, begin) <

927 std::tie(other.neg_hint_weight, other.cost, other.vehicle,

928 other.begin);

929 }

931 };

932

933 public:

941

942

943

945 public:

947 : data_(data), bounds_(bounds) {}

948

950 DCHECK_NE(data_, other.data_);

951 return bounds_ != other.bounds_;

952 }

953

954 const Insertion* begin() const { return data_ + bounds_->begin; }

955 const Insertion* end() const { return data_ + bounds_->end; }

956 size_t Size() const { return bounds_->Size(); }

957 int Vehicle() const { return bounds_->vehicle; }

958 int64_t Cost() const { return bounds_->cost; }

959 int64_t& Cost() { return bounds_->cost; }

961 bounds_->neg_hint_weight = -hint_weight;

962 }

963 int NegHintWeight() const { return bounds_->neg_hint_weight; }

964

965 private:

967 InsertionBounds* const bounds_;

968 };

970 public:

972 : data_(data), bounds_(bounds) {}

974 DCHECK_EQ(data_, other.data_);

975 return bounds_ != other.bounds_;

976 }

978 ++bounds_;

979 return *this;

980 }

982

983 private:

985 InsertionBounds* bounds_;

986 };

987

988

990 return {insertions_.data(), insertion_bounds_.data()};

991 }

993 return {insertions_.data(),

994 insertion_bounds_.data() + insertion_bounds_.size()};

995 }

996

997 size_t Size() const { return insertion_bounds_.size(); }

998

999

1000

1001

1003 int vehicle, std::initializer_list<Insertion> insertion_sequence) {

1004 insertion_bounds_.push_back(

1005 {.begin = insertions_.size(),

1006 .end = insertions_.size() + insertion_sequence.size(),

1007 .vehicle = vehicle,

1008 .cost = 0});

1009 insertions_.insert(insertions_.end(), insertion_sequence.begin(),

1010 insertion_sequence.end());

1011 }

1012

1013

1015 absl::Span<const Insertion> insertion_sequence) {

1016 insertion_bounds_.push_back(

1017 {.begin = insertions_.size(),

1018 .end = insertions_.size() + insertion_sequence.size(),

1019 .vehicle = vehicle,

1020 .cost = 0});

1021 insertions_.insert(insertions_.end(), insertion_sequence.begin(),

1022 insertion_sequence.end());

1023 }

1024

1025

1026

1028 size_t from = 0;

1029 size_t to = 0;

1031

1032 if (!p(sequence)) insertion_bounds_[to++] = insertion_bounds_[from];

1033 ++from;

1034 }

1035 insertion_bounds_.resize(to);

1036 }

1037

1038

1039

1040

1041

1042 void Sort() { std::sort(insertion_bounds_.begin(), insertion_bounds_.end()); }

1043

1044

1046 insertions_.clear();

1047 insertion_bounds_.clear();

1048 }

1049

1050 private:

1051 std::vector<Insertion> insertions_;

1052 std::vector<InsertionBounds> insertion_bounds_;

1053};

1054

1055

1057 public:

1059

1078 int pickup, int delivery, int vehicle, absl::Span<const int> path,

1079 const std::vector<bool>& path_node_is_pickup,

1080 const std::vector<bool>& path_node_is_delivery,

1082

1083 private:

1084

1085 std::vector<int> next_decrease_;

1086 std::vector<int> next_increase_;

1087 std::vector<int> prev_decrease_;

1088 std::vector<int> prev_increase_;

1089};

1090

1106

1114 public:

1118 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,

1122 std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,

1123 std::vector<RoutingModel::VariableValuePair>*)>

1124 optimize_on_insertion = nullptr);

1128 return "LocalCheapestInsertionFilteredHeuristic";

1129 }

1130

1131 protected:

1133

1134 private:

1135 struct NodeInsertion {

1136 int64_t insert_after;

1137 int vehicle;

1138 int neg_hint_weight;

1139 int64_t value;

1140

1141 bool operator<(const NodeInsertion& other) const {

1142 return std::tie(neg_hint_weight, value, insert_after, vehicle) <

1143 std::tie(other.neg_hint_weight, other.value, other.insert_after,

1144 other.vehicle);

1145 }

1146 };

1150 void ComputeInsertionOrder();

1155 void AppendInsertionPositionsAfter(

1156 int64_t node_to_insert, int64_t start, int64_t next_after_start,

1157 int vehicle, std::vector<NodeInsertion>* node_insertions);

1161 std::vector<NodeInsertion> ComputeEvaluatorSortedPositions(int64_t node);

1166 std::vector<NodeInsertion> ComputeEvaluatorSortedPositionsOnRouteAfter(

1167 int64_t node, int64_t start, int64_t next_after_start, int vehicle);

1168

1172 std::vector<PickupDeliveryInsertion> ComputeEvaluatorSortedPairPositions(

1173 int pickup, int delivery);

1174

1175

1176

1177 void InsertBestPickupThenDelivery(const PickupDeliveryPair& pair);

1178

1179

1180 void InsertBestPair(const PickupDeliveryPair& pair);

1181

1182

1183

1184 void InsertBestPairMultitour(const PickupDeliveryPair& pair);

1185

1186 bool InsertPair(int64_t pickup, int64_t insert_pickup_after, int64_t delivery,

1187 int64_t insert_delivery_after, int vehicle);

1188

1189

1190 bool OptimizeOnInsertion(std::vector<int> delta_indices);

1191

1192

1193

1194

1195 bool MustUpdateBinCapacities() const {

1196 return bin_capacities_ != nullptr && optimize_on_insertion_ == nullptr;

1197 }

1198

1199 std::vector<Seed> insertion_order_;

1201 pair_insertion_strategy_;

1202 std::vector<LocalCheapestInsertionParameters::InsertionSortingProperty>

1203 insertion_sorting_properties_;

1204 InsertionSequenceContainer insertion_container_;

1205 InsertionSequenceGenerator insertion_generator_;

1206

1207 const bool use_first_solution_hint_;

1208

1209 BinCapacities* const bin_capacities_;

1210

1211 std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,

1212 std::vector<RoutingModel::VariableValuePair>*)>

1213 optimize_on_insertion_;

1214 bool synchronize_insertion_optimizer_ = true;

1215

1216 const bool use_random_insertion_order_;

1217 std::mt19937 rnd_;

1218};

1219

1223 public:

1225 std::function<bool()> stop_search,

1229

1230 private:

1231 class PartialRoutesAndLargeVehicleIndicesFirst {

1232 public:

1233 explicit PartialRoutesAndLargeVehicleIndicesFirst(

1235 : builder_(builder) {}

1236 bool operator()(int vehicle1, int vehicle2) const;

1237

1238 private:

1240 };

1242 template <typename Iterator>

1243 std::vector<int64_t> GetPossibleNextsFromIterator(int64_t node,

1244 Iterator start,

1245 Iterator end) const {

1246 const int size = model()->Size();

1247 std::vector<int64_t> nexts;

1248 for (Iterator it = start; it != end; ++it) {

1249 const int64_t next = *it;

1250 if (next != node && (next >= size || !Contains(next))) {

1251 nexts.push_back(next);

1252 }

1253 }

1254 return nexts;

1255 }

1257 virtual void SortSuccessors(int64_t node,

1258 std::vector<int64_t>* successors) = 0;

1259 virtual int64_t FindTopSuccessor(int64_t node,

1260 const std::vector<int64_t>& successors) = 0;

1261};

1262

1267 public:

1271 std::function<int64_t(int64_t, int64_t)> evaluator,

1275 return "EvaluatorCheapestAdditionFilteredHeuristic";

1276 }

1277

1278 private:

1280 void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override;

1281 int64_t FindTopSuccessor(int64_t node,

1282 const std::vector<int64_t>& successors) override;

1283

1284 std::function<int64_t(int64_t, int64_t)> evaluator_;

1285};

1286

1291 public:

1299 return "ComparatorCheapestAdditionFilteredHeuristic";

1300 }

1301

1302 private:

1304 void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override;

1305 int64_t FindTopSuccessor(int64_t node,

1306 const std::vector<int64_t>& successors) override;

1307

1309};

1310

1320 public:

1322 std::function<bool()> stop_search,

1327

1328 protected:

1340

1341 template <typename S>

1342 class SavingsContainer;

1343

1345

1347

1358 int64_t after_node);

1359

1360

1362

1364

1365 private:

1370

1371 void AddSymmetricArcsToAdjacencyLists(

1372 std::vector<std::vector<int64_t> >* adjacency_lists);

1373

1374

1383 bool ComputeSavings();

1385 Saving BuildSaving(int64_t saving, int vehicle_type, int before_node,

1386 int after_node) const {

1387 return {saving, static_cast<unsigned int>(vehicle_type),

1388 static_cast<unsigned int>(before_node),

1389 static_cast<unsigned int>(after_node)};

1390 }

1391

1395 int64_t MaxNumNeighborsPerNode(int num_vehicle_types) const;

1396

1397 const SavingsParameters savings_params_;

1398

1400};

1401

1403 public:

1405 std::function<bool()> stop_search,

1409 filter_manager) {}

1412 return "SequentialSavingsFilteredHeuristic";

1413 }

1414

1415 private:

1422};

1423

1425 public:

1427 std::function<bool()> stop_search,

1431 filter_manager) {}

1434 return "ParallelSavingsFilteredHeuristic";

1435 }

1436

1437 private:

1449

1451

1456 void MergeRoutes(int first_vehicle, int second_vehicle, int64_t before_node,

1457 int64_t after_node);

1458

1460 std::vector<int64_t> first_node_on_route_;

1461 std::vector<int64_t> last_node_on_route_;

1465 std::vector<int> vehicle_of_first_or_last_node_;

1466};

1467

1471

1473 public:

1475 std::function<bool()> stop_search,

1477 bool use_minimum_matching);

1481 return "ChristofidesFilteredHeuristic";

1482 }

1483

1484 private:

1485 const bool use_minimum_matching_;

1486};

1487

1491 public:

1492 explicit SweepArranger(absl::Span<const std::pair<int64_t, int64_t>> points);

1493

1494

1497

1500 void SetSectors(int sectors) { sectors_ = sectors; }

1501

1502 private:

1503 std::vector<int> coordinates_;

1504 int sectors_;

1505};

1506#endif

1507

1508

1509

1511 bool check_assignment);

1512

1513

1515

1516}

1517

1518#endif

Definition routing_search.h:1222

bool BuildSolutionInternal() override

Virtual method to redefine how to build a solution.

CheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)

~CheapestAdditionFilteredHeuristic() override=default

std::function< int64_t(int64_t, int64_t, int64_t)> evaluator_

Definition routing_search.h:488

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

Definition routing_search.h:476

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_

Definition routing_search.h:493

~CheapestInsertionFilteredHeuristic() override=default

bool IsHint(int node, int64_t next) const

Definition routing_search.h:484

std::vector< int > hint_next_values_

Definition routing_search.h:492

void InitializeSeedQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, SeedQueue *sq)

std::vector< EvaluatorCache > evaluator_cache_

Definition routing_search.h:490

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

Definition routing_search.h:480

std::function< int64_t(int64_t)> penalty_evaluator_

Definition routing_search.h:491

void AddSeedNodeToQueue(int node, std::vector< StartEndValue > *start_end_distances, SeedQueue *sq)

ChristofidesFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)

bool BuildSolutionInternal() override

Virtual method to redefine how to build a solution.

~ChristofidesFilteredHeuristic() override=default

std::string DebugString() const override

Definition routing_search.h:1480

std::string DebugString() const override

Definition routing_search.h:1298

~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

Definition routing_search.h:1274

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

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, bool is_sequential)

Takes ownership of evaluators.

bool BuildSolutionInternal() override

Virtual method to redefine how to build a solution.

~GlobalCheapestInsertionFilteredHeuristic() override=default

std::string DebugString() const override

Definition routing_search.h:515

Definition routing_search.h:969

InsertionSequenceIterator(Insertion *data, InsertionBounds *bounds)

Definition routing_search.h:971

InsertionSequence operator*() const

Definition routing_search.h:981

bool operator!=(const InsertionSequenceIterator &other) const

Definition routing_search.h:973

InsertionSequenceIterator & operator++()

Definition routing_search.h:977

Definition routing_search.h:944

void SetHintWeight(int hint_weight)

Definition routing_search.h:960

size_t Size() const

Definition routing_search.h:956

int Vehicle() const

Definition routing_search.h:957

const Insertion * end() const

Definition routing_search.h:955

const Insertion * begin() const

Definition routing_search.h:954

int64_t Cost() const

Definition routing_search.h:958

bool operator!=(const InsertionSequence &other) const

Definition routing_search.h:949

int NegHintWeight() const

Definition routing_search.h:963

int64_t & Cost()

Definition routing_search.h:959

InsertionSequence(Insertion *data, InsertionBounds *bounds)

Definition routing_search.h:946

Definition routing_search.h:909

void RemoveIf(const std::function< bool(const InsertionSequence &)> &p)

Definition routing_search.h:1027

void AddInsertionSequence(int vehicle, std::initializer_list< Insertion > insertion_sequence)

Definition routing_search.h:1002

InsertionSequenceIterator begin()

Definition routing_search.h:989

void Sort()

Definition routing_search.h:1042

void Clear()

Definition routing_search.h:1045

size_t Size() const

Definition routing_search.h:997

InsertionSequenceIterator end()

Definition routing_search.h:992

void AddInsertionSequence(int vehicle, absl::Span< const Insertion > insertion_sequence)

Definition routing_search.h:1014

void AppendPickupDeliveryMultitourInsertions(int pickup, int delivery, int vehicle, absl::Span< const 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

IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)

~IntVarFilteredDecisionBuilder() override=default

Generic filter-based heuristic applied to IntVars.

Definition routing_search.h:218

bool HasSecondaryVars() const

Returns true if there are secondary variables.

Definition routing_search.h:288

Assignment *const assignment_

Definition routing_search.h:294

virtual std::string DebugString() const

Definition routing_search.h:235

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)

virtual bool BuildSolutionInternal()=0

Virtual method to redefine how to build a solution.

int64_t number_of_rejects() const

Definition routing_search.h:233

virtual ~IntVarFilteredHeuristic()=default

int64_t number_of_decisions() const

Definition routing_search.h:232

bool Contains(int64_t index) const

Returns true if the variable of index 'index' is in the current solution.

Definition routing_search.h:277

virtual bool StopSearch()

Returns true if the search must be stopped.

Definition routing_search.h:256

virtual void Initialize()

Initialize the heuristic; called before starting to build a new solution.

Definition routing_search.h:241

Assignment * BuildSolution()

int64_t SecondaryVarIndex(int64_t index) const

Returns the index of a secondary var.

Definition routing_search.h:283

int64_t Value(int64_t index) const

Definition routing_search.h:273

void SetValue(int64_t index, int64_t value)

Definition routing_search.h:259

virtual bool InitializeSolution()

Virtual method to initialize the solution.

Definition routing_search.h:243

const std::vector< int > & delta_indices() const

Returns the indices of the nodes currently in the insertion delta.

Definition routing_search.h:270

IntVar * Var(int64_t index) const

Returns the variable of index 'index'.

Definition routing_search.h:281

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.

Definition routing_search.h:290

virtual uint64_t Size() const =0

This method returns the number of values in the domain of the variable.

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, LocalCheapestInsertionParameters lci_params, 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

Definition routing_search.h:1127

bool BuildSolutionInternal() override

Virtual method to redefine how to build a solution.

LocalCheapestInsertionParameters_PairInsertionStrategy PairInsertionStrategy

~ParallelSavingsFilteredHeuristic() override=default

std::string DebugString() const override

Definition routing_search.h:1433

ParallelSavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)

Definition routing_search.h:1426

int GetEndChainStart(int vehicle) const

Returns the start of the end chain of vehicle,.

Definition routing_search.h:329

virtual void ResetVehicleIndices()

Definition routing_search.h:346

virtual void SetVehicleIndex(int64_t, int)

Definition routing_search.h:345

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)

Definition routing_search.h:350

bool VehicleIsEmpty(int vehicle) const

Definition routing_search.h:347

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)

int GetStartChainEnd(int vehicle) const

Returns the end of the start chain of vehicle,.

Definition routing_search.h:327

RoutingModel * model() const

Definition routing_search.h:325

bool StopSearch() override

Returns true if the search must be stopped.

Definition routing_search.h:344

void AddUnassignedNodesToEmptyVehicles()

Adds all unassigned nodes to empty vehicles.

void MakePartiallyPerformedPairsUnperformed()

int64_t Size() const

Returns the number of next variables in the model.

int64_t End(int vehicle) const

Returns the variable index of the ending node of a vehicle route.

operations_research::IntVar * VehicleVar(int64_t index) const

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() override

friend class SavingsFilteredHeuristicTestPeer

Definition routing_search.h:1399

virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0

int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node, int64_t after_node)

std::unique_ptr< SavingsContainer< Saving > > savings_container_

Definition routing_search.h:1361

std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_

Definition routing_search.h:1363

std::string DebugString() const override

Definition routing_search.h:1411

SequentialSavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)

Definition routing_search.h:1404

~SequentialSavingsFilteredHeuristic() override=default

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

void ArrangeIndices(std::vector< int64_t > *indices)

void SetSectors(int sectors)

Definition routing_search.h:1500

virtual ~SweepArranger()=default

SweepArranger & operator=(const SweepArranger &)=delete

void Update(const std::function< bool(int)> &remove_vehicle)

int NumTypes() const

Definition routing_search.h:106

bool HasCompatibleVehicleOfType(int type, const std::function< bool(int)> &vehicle_is_compatible) const

VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)

Definition routing_search.h:102

void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64_t fixed_cost)

Definition routing_search.h:130

int GetLowestFixedCostVehicleOfType(int type) const

Definition routing_search.h:118

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)

int Type(int vehicle) const

Definition routing_search.h:108

dual_gradient T(y - `dual_solution`) class DiagonalTrustRegionProblemFromQp

DecisionBuilder * MakeAllUnperformed(RoutingModel *model)

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)

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)

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)

trees with all degrees equal to

The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...

Definition routing_search.h:385

int64_t node

Definition routing_search.h:387

int64_t value

Definition routing_search.h:386

int vehicle

Definition routing_search.h:388

Definition routing_search.h:408

const bool prioritize_farthest_nodes

Definition routing_search.h:418