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 
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).
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_
#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
int64 delta
Definition: resource.cc:1684