OR-Tools  8.2
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).
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]) ||
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_
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
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.
Definition: local_search.cc:74
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.
int64_t int64
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
STL namespace.
int64 delta
Definition: resource.cc:1684