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 
24 namespace 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);
165  ~PairRelocateOperator() override {}
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);
215  ~PairExchangeOperator() override {}
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 
603 template <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 
641 template <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 
652 template <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 
663 template <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 
674 template <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 
690 template <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