C++ Reference

C++ Reference: Routing

routing_neighborhoods.h
Go to the documentation of this file.
1// Copyright 2010-2018 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_NEIGHBORHOODS_H_
15#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
16
17#include "absl/container/flat_hash_set.h"
22#include "ortools/util/bitset.h"
23
24namespace operations_research {
25
46// TODO(user): Consider merging with standard Relocate in local_search.cc.
48 public:
50 const std::vector<IntVar*>& vars,
51 const std::vector<IntVar*>& secondary_vars,
52 std::function<int(int64)> start_empty_path_class,
53 RoutingTransitCallback2 arc_evaluator);
55
56 bool MakeNeighbor() override;
57 std::string DebugString() const override { return "RelocateNeighbors"; }
58
59 private:
66 bool MoveChainAndRepair(int64 before_chain, int64 chain_end,
67 int64 destination);
68
76 int64 Reposition(int64 before_to_move, int64 up_to);
77
78 RoutingTransitCallback2 arc_evaluator_;
79};
80
85// TODO(user): Add option to prune neighbords where the order of node pairs
86// is violated (ie precedence between pickup and delivery nodes).
87// TODO(user): Move this to local_search.cc if it's generic enough.
88// TODO(user): Detect pairs automatically by parsing the constraint model;
89// we could then get rid of the pair API in the RoutingModel
90// class.
91
105 public:
106 MakePairActiveOperator(const std::vector<IntVar*>& vars,
107 const std::vector<IntVar*>& secondary_vars,
108 std::function<int(int64)> start_empty_path_class,
109 const RoutingIndexPairs& pairs);
111 bool MakeNeighbor() override;
112 std::string DebugString() const override { return "MakePairActive"; }
113
114 protected:
115 bool MakeOneNeighbor() override;
116 bool OnSamePathAsPreviousBase(int64 base_index) override {
119 return true;
120 }
121
122 int64 GetBaseNodeRestartPosition(int base_index) override;
123
126 bool RestartAtPathStartOnSynchronize() override { return true; }
127
128 private:
129 void OnNodeInitialization() override;
130 int FindNextInactivePair(int pair_index) const;
131 bool ContainsActiveNodes(const std::vector<int64>& nodes) const;
132
133 int inactive_pair_;
134 int inactive_pair_first_index_;
135 int inactive_pair_second_index_;
136 const RoutingIndexPairs pairs_;
137};
138
141 public:
142 MakePairInactiveOperator(const std::vector<IntVar*>& vars,
143 const std::vector<IntVar*>& secondary_vars,
144 std::function<int(int64)> start_empty_path_class,
145 const RoutingIndexPairs& index_pairs);
146
147 bool MakeNeighbor() override;
148 std::string DebugString() const override { return "MakePairInActive"; }
149};
150
160 public:
161 PairRelocateOperator(const std::vector<IntVar*>& vars,
162 const std::vector<IntVar*>& secondary_vars,
163 std::function<int(int64)> start_empty_path_class,
164 const RoutingIndexPairs& index_pairs);
166
167 bool MakeNeighbor() override;
168 std::string DebugString() const override { return "PairRelocateOperator"; }
169
170 protected:
171 bool OnSamePathAsPreviousBase(int64 base_index) override {
173 return base_index == kPairSecondNodeDestination;
174 }
175 int64 GetBaseNodeRestartPosition(int base_index) override;
176
177 bool ConsiderAlternatives(int64 base_index) const override {
178 return base_index == kPairFirstNode;
179 }
180
181 private:
182 bool RestartAtPathStartOnSynchronize() override { return true; }
183
184 static constexpr int kPairFirstNode = 0;
185 static constexpr int kPairFirstNodeDestination = 1;
186 static constexpr int kPairSecondNodeDestination = 2;
187};
188
190 public:
191 LightPairRelocateOperator(const std::vector<IntVar*>& vars,
192 const std::vector<IntVar*>& secondary_vars,
193 std::function<int(int64)> start_empty_path_class,
194 const RoutingIndexPairs& index_pairs);
196
197 bool MakeNeighbor() override;
198 std::string DebugString() const override {
199 return "LightPairRelocateOperator";
200 }
201};
202
210 public:
211 PairExchangeOperator(const std::vector<IntVar*>& vars,
212 const std::vector<IntVar*>& secondary_vars,
213 std::function<int(int64)> start_empty_path_class,
214 const RoutingIndexPairs& index_pairs);
216
217 bool MakeNeighbor() override;
218 std::string DebugString() const override { return "PairExchangeOperator"; }
219
220 private:
221 bool RestartAtPathStartOnSynchronize() override { return true; }
222 bool ConsiderAlternatives(int64 base_index) const override { return true; }
223 bool GetPreviousAndSibling(int64 node, int64* previous, int64* sibling,
224 int64* sibling_previous) const;
225};
226
241 public:
242 PairExchangeRelocateOperator(const std::vector<IntVar*>& vars,
243 const std::vector<IntVar*>& secondary_vars,
244 std::function<int(int64)> start_empty_path_class,
245 const RoutingIndexPairs& index_pairs);
247
248 bool MakeNeighbor() override;
249 std::string DebugString() const override {
250 return "PairExchangeRelocateOperator";
251 }
252
253 protected:
254 bool OnSamePathAsPreviousBase(int64 base_index) override;
255 int64 GetBaseNodeRestartPosition(int base_index) override;
256
257 private:
258 bool RestartAtPathStartOnSynchronize() override { return true; }
259 bool GetPreviousAndSibling(int64 node, int64* previous, int64* sibling,
260 int64* sibling_previous) const;
261 bool MoveNode(int pair, int node, int64 nodes[2][2], int64 dest[2][2],
262 int64 prev[2][2]);
263 bool LoadAndCheckDest(int pair, int node, int64 base_node, int64 nodes[2][2],
264 int64 dest[2][2]) const;
265
266 static constexpr int kFirstPairFirstNode = 0;
267 static constexpr int kSecondPairFirstNode = 1;
268 static constexpr int kFirstPairFirstNodeDestination = 2;
269 static constexpr int kFirstPairSecondNodeDestination = 3;
270 static constexpr int kSecondPairFirstNodeDestination = 4;
271 static constexpr int kSecondPairSecondNodeDestination = 5;
272};
273
285 public:
286 SwapIndexPairOperator(const std::vector<IntVar*>& vars,
287 const std::vector<IntVar*>& path_vars,
288 std::function<int(int64)> start_empty_path_class,
289 const RoutingIndexPairs& index_pairs);
291
292 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
293 void OnStart() override;
294 std::string DebugString() const override { return "SwapIndexPairOperator"; }
295
296 private:
299 bool UpdateActiveNodes();
301 void SetNext(int64 from, int64 to, int64 path) {
302 DCHECK_LT(from, number_of_nexts_);
303 SetValue(from, to);
304 if (!ignore_path_vars_) {
305 DCHECK_LT(from + number_of_nexts_, Size());
306 SetValue(from + number_of_nexts_, path);
307 }
308 }
309
310 const RoutingIndexPairs index_pairs_;
311 int pair_index_;
312 int first_index_;
313 int second_index_;
314 int64 first_active_;
315 int64 second_active_;
316 std::vector<int64> prevs_;
317 const int number_of_nexts_;
318 const bool ignore_path_vars_;
319};
320
324 public:
325 IndexPairSwapActiveOperator(const std::vector<IntVar*>& vars,
326 const std::vector<IntVar*>& secondary_vars,
327 std::function<int(int64)> start_empty_path_class,
328 const RoutingIndexPairs& index_pairs);
330
331 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
332 bool MakeNeighbor() override;
333 std::string DebugString() const override {
334 return "IndexPairSwapActiveOperator";
335 }
336
337 private:
338 void OnNodeInitialization() override;
339
340 int inactive_node_;
341};
342
345// TODO(user): Put these methods in an object with helper methods instead
346// of adding a layer to the class hierarchy.
348 public:
350 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
351 bool keep_inverse_values = false);
353
354 protected:
355 virtual bool IncrementPosition() = 0;
359 virtual std::function<int64(int64)> SetupNextAccessorForNeighbor() = 0;
360
361 std::string HeuristicName() const {
362 std::string heuristic_name = heuristic_->DebugString();
363 const int erase_pos = heuristic_name.find("FilteredHeuristic");
364 if (erase_pos != std::string::npos) {
365 const int expected_name_size = heuristic_name.size() - 17;
366 heuristic_name.erase(erase_pos);
367 // NOTE: Verify that the "FilteredHeuristic" string was at the end of the
368 // heuristic name.
369 DCHECK_EQ(heuristic_name.size(), expected_name_size);
370 }
371 return heuristic_name;
372 }
373
374 // TODO(user): Remove the dependency from RoutingModel by storing an
375 // IntVarFilteredHeuristic here instead and storing information on path
376 // start/ends like PathOperator does (instead of relying on the model).
379 SparseBitset<> removed_nodes_;
380
381 private:
382 bool MakeOneNeighbor() override;
383 bool MakeChangesAndInsertNodes();
384
385 int64 VehicleVarIndex(int64 node) const { return model_.Size() + node; }
386
387 const std::unique_ptr<RoutingFilteredHeuristic> heuristic_;
388 const bool consider_vehicle_vars_;
389};
390
395 public:
397 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
399
400 std::string DebugString() const override {
401 return absl::StrCat("HeuristicPathLNS(", HeuristicName(), ")");
402 }
403
404 private:
405 void OnStart() override;
406
407 bool IncrementPosition() override;
408 bool CurrentRouteIsEmpty() const;
409 void IncrementCurrentRouteToNextNonEmpty();
410
411 std::function<int64(int64)> SetupNextAccessorForNeighbor() override;
412
413 int current_route_;
414 int last_route_;
415 bool just_started_;
416};
417
423 public:
425 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
427
428 std::string DebugString() const override {
429 return absl::StrCat("RelocatePathAndHeuristicInsertUnperformed(",
430 HeuristicName(), ")");
431 }
432
433 private:
434 void OnStart() override;
435
436 bool IncrementPosition() override;
437 bool IncrementRoutes();
438
439 std::function<int64(int64)> SetupNextAccessorForNeighbor() override;
440
441 int route_to_relocate_index_;
442 int last_route_to_relocate_index_;
443 int empty_route_index_;
444 int last_empty_route_index_;
445 std::vector<int> routes_to_relocate_;
446 std::vector<int> empty_routes_;
447 std::vector<int64> last_node_on_route_;
448 bool has_unperformed_nodes_;
449 bool just_started_;
450};
451
457 public:
459 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
460 int num_arcs_to_consider,
461 std::function<int64(int64, int64, int64)> arc_cost_for_route_start);
463
464 std::string DebugString() const override {
465 return absl::StrCat("HeuristicExpensiveChainLNS(", HeuristicName(), ")");
466 }
467
468 private:
469 void OnStart() override;
470
471 bool IncrementPosition() override;
472 bool IncrementRoute();
473 bool IncrementCurrentArcIndices();
474 bool FindMostExpensiveChainsOnRemainingRoutes();
475
476 std::function<int64(int64)> SetupNextAccessorForNeighbor() override;
477
478 int current_route_;
479 int last_route_;
480
481 const int num_arcs_to_consider_;
482 std::vector<std::pair<int64, int>> most_expensive_arc_starts_and_ranks_;
485 std::pair</*first_arc_index*/ int, /*second_arc_index*/ int>
486 current_expensive_arc_indices_;
487 std::function<int64(/*before_node*/ int64, /*after_node*/ int64,
488 /*path_start*/ int64)>
489 arc_cost_for_route_start_;
490
491 bool just_started_;
492};
493
499 public:
501 std::unique_ptr<RoutingFilteredHeuristic> heuristic, int num_close_nodes);
503
504 std::string DebugString() const override {
505 return absl::StrCat("HeuristicCloseNodesLNS(", HeuristicName(), ")");
506 }
507
508 private:
509 void OnStart() override;
510
511 bool IncrementPosition() override;
512
513 std::function<int64(int64)> SetupNextAccessorForNeighbor() override;
514
515 void RemoveNode(int64 node);
516 void RemoveNodeAndActiveSibling(int64 node);
517
518 bool IsActive(int64 node) const {
519 DCHECK_LT(node, model_.Size());
520 return Value(node) != node && !removed_nodes_[node];
521 }
522
523 int64 Prev(int64 node) const {
524 DCHECK_EQ(Value(InverseValue(node)), node);
525 DCHECK_LT(node, new_prevs_.size());
526 return changed_prevs_[node] ? new_prevs_[node] : InverseValue(node);
527 }
528 int64 Next(int64 node) const {
529 DCHECK(!model_.IsEnd(node));
530 return changed_nexts_[node] ? new_nexts_[node] : Value(node);
531 }
532
533 std::vector<int64> GetActiveSiblings(int64 node) const;
534
535 const std::vector<std::pair<std::vector<int64>, std::vector<int64>>>&
536 pickup_delivery_pairs_;
537
538 int current_node_;
539 int last_node_;
540 bool just_started_;
541
542 std::vector<std::vector<int64>> close_nodes_;
544 std::vector<int64> new_nexts_;
545 SparseBitset<> changed_nexts_;
546 std::vector<int64> new_prevs_;
547 SparseBitset<> changed_prevs_;
548};
549
558 public:
560 const std::vector<IntVar*>& vars,
561 const std::vector<IntVar*>& secondary_vars,
562 std::function<int(int64)> start_empty_path_class,
563 int num_arcs_to_consider,
564 std::function<int64(int64, int64, int64)> arc_cost_for_path_start);
566 bool MakeNeighbor() override;
567 bool MakeOneNeighbor() override;
568
569 std::string DebugString() const override { return "RelocateExpensiveChain"; }
570
571 private:
572 void OnNodeInitialization() override;
573 void IncrementCurrentPath();
574 bool IncrementCurrentArcIndices();
578 bool FindMostExpensiveChainsOnRemainingPaths();
579
580 int num_arcs_to_consider_;
581 int current_path_;
582 std::vector<std::pair<int64, int>> most_expensive_arc_starts_and_ranks_;
585 std::pair</*first_arc_index*/ int, /*second_arc_index*/ int>
586 current_expensive_arc_indices_;
587 std::function<int64(/*before_node*/ int64, /*after_node*/ int64,
588 /*path_start*/ int64)>
589 arc_cost_for_path_start_;
590 int end_path_;
593 bool has_non_empty_paths_to_explore_;
594};
595
603template <bool swap_first>
605 public:
606 PairNodeSwapActiveOperator(const std::vector<IntVar*>& vars,
607 const std::vector<IntVar*>& secondary_vars,
608 std::function<int(int64)> start_empty_path_class,
609 const RoutingIndexPairs& index_pairs);
611
612 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
613 bool MakeNeighbor() override;
614 std::string DebugString() const override {
615 return "PairNodeSwapActiveOperator";
616 }
617
618 protected:
619 bool OnSamePathAsPreviousBase(int64 base_index) override {
622 return true;
623 }
624
625 int64 GetBaseNodeRestartPosition(int base_index) override;
626
629 bool RestartAtPathStartOnSynchronize() override { return true; }
630
631 private:
632 void OnNodeInitialization() override;
633
634 int inactive_pair_;
635 RoutingIndexPairs pairs_;
636};
637
638// ==========================================================================
639// Section: Implementations of the template classes declared above.
640
641template <bool swap_first>
643 const std::vector<IntVar*>& vars,
644 const std::vector<IntVar*>& secondary_vars,
645 std::function<int(int64)> start_empty_path_class,
646 const RoutingIndexPairs& index_pairs)
647 : PathOperator(vars, secondary_vars, 2, false, false,
648 std::move(start_empty_path_class)),
649 inactive_pair_(0),
650 pairs_(index_pairs) {}
651
652template <bool swap_first>
654 int base_index) {
655 // Base node 1 must be after base node 0 if they are both on the same path.
656 if (base_index == 0 || StartNode(base_index) != StartNode(base_index - 1)) {
657 return StartNode(base_index);
658 } else {
659 return BaseNode(base_index - 1);
660 }
661}
662
663template <bool swap_first>
665 for (int i = 0; i < pairs_.size(); ++i) {
666 if (IsInactive(pairs_[i].first[0]) && IsInactive(pairs_[i].second[0])) {
667 inactive_pair_ = i;
668 return;
669 }
670 }
671 inactive_pair_ = pairs_.size();
672}
673
674template <bool swap_first>
676 Assignment* delta, Assignment* deltadelta) {
677 while (inactive_pair_ < pairs_.size()) {
678 if (!IsInactive(pairs_[inactive_pair_].first[0]) ||
679 !IsInactive(pairs_[inactive_pair_].second[0]) ||
680 !PathOperator::MakeNextNeighbor(delta, deltadelta)) {
681 ResetPosition();
682 ++inactive_pair_;
683 } else {
684 return true;
685 }
686 }
687 return false;
688}
689
690template <bool swap_first>
692 const int64 base = BaseNode(0);
693 if (IsPathEnd(base)) {
694 return false;
695 }
696 const int64 pair_first = pairs_[inactive_pair_].first[0];
697 const int64 pair_second = pairs_[inactive_pair_].second[0];
698 if (swap_first) {
699 return MakeActive(pair_second, BaseNode(1)) &&
700 MakeActive(pair_first, base) &&
701 MakeChainInactive(pair_first, Next(pair_first));
702 } else {
703 return MakeActive(pair_second, BaseNode(1)) &&
704 MakeActive(pair_first, base) &&
705 MakeChainInactive(pair_second, Next(pair_second));
706 }
707}
708
721 public:
722 RelocateSubtrip(const std::vector<IntVar*>& vars,
723 const std::vector<IntVar*>& secondary_vars,
724 std::function<int(int64)> start_empty_path_class,
725 const RoutingIndexPairs& pairs);
726
727 std::string DebugString() const override { return "RelocateSubtrip"; }
728 bool MakeNeighbor() override;
729
730 private:
731 // Relocates the subtrip starting at chain_first_node. It must be a pickup.
732 bool RelocateSubTripFromPickup(int64 chain_first_node, int64 insertion_node);
734 bool RelocateSubTripFromDelivery(int64 chain_last_node, int64 insertion_node);
735 std::vector<bool> is_pickup_node_;
736 std::vector<bool> is_delivery_node_;
737 std::vector<int> pair_of_node_;
738 // Represents the set of pairs that have been opened during a call to
739 // MakeNeighbor(). This vector must be all false before and after calling
740 // RelocateSubTripFromPickup() and RelocateSubTripFromDelivery().
741 std::vector<bool> opened_pairs_bitset_;
742
743 std::vector<int64> rejected_nodes_;
744 std::vector<int64> subtrip_nodes_;
745};
746
748 public:
749 ExchangeSubtrip(const std::vector<IntVar*>& vars,
750 const std::vector<IntVar*>& secondary_vars,
751 std::function<int(int64)> start_empty_path_class,
752 const RoutingIndexPairs& pairs);
753
754 std::string DebugString() const override { return "ExchangeSubtrip"; }
755 bool MakeNeighbor() override;
756
757 private:
758 // Try to extract a subtrip from base_node (see below) and check that the move
759 // will be canonical.
760 // Given a pickup/delivery pair, this operator could generate the same move
761 // twice, the first time with base_node == pickup, the second time with
762 // base_node == delivery. This happens only when no nodes in the subtrip
763 // remain in the original path, i.e. when rejects is empty after
764 // chain extraction. In that case, we keep only a canonical move out of the
765 // two possibilities, the move where base_node is a pickup.
766 bool ExtractChainsAndCheckCanonical(int64 base_node,
767 std::vector<int64>* rejects,
768 std::vector<int64>* subtrip);
769 // Reads the path from base_node forward, collecting subtrip nodes in
770 // subtrip and non-subtrip nodes in rejects.
771 // Non-subtrip nodes will be unmatched delivery nodes.
772 // base_node must be a pickup, and remaining/extracted_nodes must be empty.
773 // Returns true if such chains could be extracted.
774 bool ExtractChainsFromPickup(int64 base_node, std::vector<int64>* rejects,
775 std::vector<int64>* subtrip);
776 // Reads the path from base_node backward, collecting subtrip nodes in
777 // subtrip and non-subtrip nodes in rejects.
778 // Non-subtrip nodes will be unmatched pickup nodes.
779 // base_node must be a delivery, and remaining/extracted_nodes must be empty.
780 // Returns true if such chains could be extracted.
781 bool ExtractChainsFromDelivery(int64 base_node, std::vector<int64>* rejects,
782 std::vector<int64>* subtrip);
783 void SetPath(const std::vector<int64>& path, int path_id);
784
785 // Precompute some information about nodes.
786 std::vector<bool> is_pickup_node_;
787 std::vector<bool> is_delivery_node_;
788 std::vector<int> pair_of_node_;
789 // Represents the set of opened pairs during ExtractChainsFromXXX().
790 std::vector<bool> opened_pairs_set_;
791 // Keep internal structures under hand to avoid reallocation.
792 std::vector<int64> rejects0_;
793 std::vector<int64> subtrip0_;
794 std::vector<int64> rejects1_;
795 std::vector<int64> subtrip1_;
796 std::vector<int64> path0_;
797 std::vector<int64> path1_;
798};
799
800} // namespace operations_research
801
802#endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
An Assignment is a variable -> domains mapping, used to report solutions to the user.
ExchangeSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
std::string DebugString() const override
Filtered heuristic LNS operator, where the destruction phase consists of removing a node and the 'num...
FilteredHeuristicCloseNodesLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_close_nodes)
Similar to the heuristic path LNS above, but instead of removing one route entirely,...
FilteredHeuristicExpensiveChainLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_route_start)
Class of operators using a RoutingFilteredHeuristic to insert unperformed nodes after changes have be...
FilteredHeuristicLocalSearchOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, bool keep_inverse_values=false)
virtual std::function< int64(int64)> SetupNextAccessorForNeighbor()=0
Virtual method to return the next_accessor to be passed to the heuristic to build a new solution.
SparseBitset removed_nodes_
Keeps track of removed nodes when making a neighbor.
LNS-like operator based on a filtered first solution heuristic to rebuild the solution,...
FilteredHeuristicPathLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
Operator which inserts inactive nodes into a path and makes a pair of active nodes inactive.
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
IndexPairSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
LightPairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Pair-based neighborhood operators, designed to move nodes by pairs (pairs are static and given).
bool RestartAtPathStartOnSynchronize() override
Required to ensure that after synchronization the operator is in a state compatible with GetBaseNodeR...
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
MakePairActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
Operator which makes pairs of active nodes inactive.
MakePairInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Relocate neighborhood which moves chains of neighbors.
MakeRelocateNeighborsOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, RoutingTransitCallback2 arc_evaluator)
Operator which exchanges the position of two pairs; for both pairs the first node of the pair must be...
PairExchangeOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Operator which exchanges the paths of two pairs (path have to be different).
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
PairExchangeRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Operator which inserts pairs of inactive nodes into a path and makes an active node inactive.
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
bool RestartAtPathStartOnSynchronize() override
Required to ensure that after synchronization the operator is in a state compatible with GetBaseNodeR...
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
PairNodeSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
Operator which moves a pair of nodes to another position where the first node of the pair must be bef...
PairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool ConsiderAlternatives(int64 base_index) const override
Indicates if alternatives should be considered when iterating over base nodes.
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
RelocateExpensiveChain(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_path_start)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
Heuristic-based local search operator which relocates an entire route to an empty vehicle of differen...
RelocatePathAndHeuristicInsertUnperformedOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
Tries to move subtrips after an insertion node.
RelocateSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
std::string DebugString() const override
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1347
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
Operator which iterates through each alternative of a set of pairs.
void OnStart() override
Called by Start() after synchronizing the operator with the current assignment.
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
SwapIndexPairOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &path_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::function< int64(int64, int64)> RoutingTransitCallback2
Definition: routing_types.h:42
std::vector< RoutingIndexPair > RoutingIndexPairs
Definition: routing_types.h:45