OR-Tools  8.2
routing_neighborhoods.cc
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 
15 
16 #include <algorithm>
17 #include <functional>
18 
19 #include "absl/container/flat_hash_set.h"
21 
22 namespace operations_research {
23 
25  const std::vector<IntVar*>& vars,
26  const std::vector<IntVar*>& secondary_vars,
27  std::function<int(int64)> start_empty_path_class,
28  RoutingTransitCallback2 arc_evaluator)
29  : PathOperator(vars, secondary_vars, 2, true, false,
30  std::move(start_empty_path_class)),
31  arc_evaluator_(std::move(arc_evaluator)) {}
32 
34  const int64 before_chain = BaseNode(0);
35  int64 chain_end = Next(before_chain);
36  if (IsPathEnd(chain_end)) return false;
37  const int64 destination = BaseNode(1);
38  if (chain_end == destination) return false;
39  const int64 max_arc_value = arc_evaluator_(destination, chain_end);
40  int64 next = Next(chain_end);
41  while (!IsPathEnd(next) && arc_evaluator_(chain_end, next) <= max_arc_value) {
42  if (next == destination) return false;
43  chain_end = next;
44  next = Next(chain_end);
45  }
46  return MoveChainAndRepair(before_chain, chain_end, destination);
47 }
48 
49 bool MakeRelocateNeighborsOperator::MoveChainAndRepair(int64 before_chain,
50  int64 chain_end,
51  int64 destination) {
52  if (MoveChain(before_chain, chain_end, destination)) {
53  if (!IsPathStart(destination)) {
54  int64 current = Prev(destination);
55  int64 last = chain_end;
56  if (current == last) { // chain was just before destination
57  current = before_chain;
58  }
59  while (last >= 0 && !IsPathStart(current) && current != last) {
60  last = Reposition(current, last);
61  current = Prev(current);
62  }
63  }
64  return true;
65  }
66  return false;
67 }
68 
69 int64 MakeRelocateNeighborsOperator::Reposition(int64 before_to_move,
70  int64 up_to) {
71  const int64 kNoChange = -1;
72  const int64 to_move = Next(before_to_move);
73  int64 next = Next(to_move);
74  if (Var(to_move)->Contains(next)) {
75  return kNoChange;
76  }
77  int64 prev = next;
78  next = Next(next);
79  while (prev != up_to) {
80  if (Var(prev)->Contains(to_move) && Var(to_move)->Contains(next)) {
81  MoveChain(before_to_move, to_move, prev);
82  return up_to;
83  }
84  prev = next;
85  next = Next(next);
86  }
87  if (Var(prev)->Contains(to_move)) {
88  MoveChain(before_to_move, to_move, prev);
89  return to_move;
90  }
91  return kNoChange;
92 }
93 
95  const std::vector<IntVar*>& vars,
96  const std::vector<IntVar*>& secondary_vars,
97  std::function<int(int64)> start_empty_path_class,
98  const RoutingIndexPairs& pairs)
99  : PathOperator(vars, secondary_vars, 2, false, true,
100  std::move(start_empty_path_class)),
101  inactive_pair_(0),
102  inactive_pair_first_index_(0),
103  inactive_pair_second_index_(0),
104  pairs_(pairs) {}
105 
107  while (inactive_pair_ < pairs_.size()) {
108  if (PathOperator::MakeOneNeighbor()) return true;
109  ResetPosition();
110  if (inactive_pair_first_index_ < pairs_[inactive_pair_].first.size() - 1) {
111  ++inactive_pair_first_index_;
112  } else if (inactive_pair_second_index_ <
113  pairs_[inactive_pair_].second.size() - 1) {
114  inactive_pair_first_index_ = 0;
115  ++inactive_pair_second_index_;
116  } else {
117  inactive_pair_ = FindNextInactivePair(inactive_pair_ + 1);
118  inactive_pair_first_index_ = 0;
119  inactive_pair_second_index_ = 0;
120  }
121  }
122  return false;
123 }
124 
126  DCHECK_EQ(StartNode(0), StartNode(1));
127  // Inserting the second node of the pair before the first one which ensures
128  // that the only solutions where both nodes are next to each other have the
129  // first node before the second (the move is not symmetric and doing it this
130  // way ensures that a potential precedence constraint between the nodes of the
131  // pair is not violated).
132  return MakeActive(pairs_[inactive_pair_].second[inactive_pair_second_index_],
133  BaseNode(1)) &&
134  MakeActive(pairs_[inactive_pair_].first[inactive_pair_first_index_],
135  BaseNode(0));
136 }
137 
139  // Base node 1 must be after base node 0 if they are both on the same path.
140  if (base_index == 0 || StartNode(base_index) != StartNode(base_index - 1)) {
141  return StartNode(base_index);
142  } else {
143  return BaseNode(base_index - 1);
144  }
145 }
146 
147 void MakePairActiveOperator::OnNodeInitialization() {
148  inactive_pair_ = FindNextInactivePair(0);
149  inactive_pair_first_index_ = 0;
150  inactive_pair_second_index_ = 0;
151 }
152 
153 int MakePairActiveOperator::FindNextInactivePair(int pair_index) const {
154  for (int index = pair_index; index < pairs_.size(); ++index) {
155  if (!ContainsActiveNodes(pairs_[index].first) &&
156  !ContainsActiveNodes(pairs_[index].second)) {
157  return index;
158  }
159  }
160  return pairs_.size();
161 }
162 
163 bool MakePairActiveOperator::ContainsActiveNodes(
164  const std::vector<int64>& nodes) const {
165  for (int64 node : nodes) {
166  if (!IsInactive(node)) return true;
167  }
168  return false;
169 }
170 
172  const std::vector<IntVar*>& vars,
173  const std::vector<IntVar*>& secondary_vars,
174  std::function<int(int64)> start_empty_path_class,
175  const RoutingIndexPairs& index_pairs)
176  : PathOperator(vars, secondary_vars, 1, true, false,
177  std::move(start_empty_path_class)) {
178  AddPairAlternativeSets(index_pairs);
179 }
180 
182  const int64 base = BaseNode(0);
183  const int64 first_index = Next(base);
184  const int64 second_index = GetActiveAlternativeSibling(first_index);
185  if (second_index < 0) {
186  return false;
187  }
188  return MakeChainInactive(base, first_index) &&
189  MakeChainInactive(Prev(second_index), second_index);
190 }
191 
193  const std::vector<IntVar*>& vars,
194  const std::vector<IntVar*>& secondary_vars,
195  std::function<int(int64)> start_empty_path_class,
196  const RoutingIndexPairs& index_pairs)
197  : PathOperator(vars, secondary_vars, 3, true, false,
198  std::move(start_empty_path_class)) {
199  AddPairAlternativeSets(index_pairs);
200 }
201 
203  DCHECK_EQ(StartNode(1), StartNode(2));
204  const int64 first_pair_node = BaseNode(kPairFirstNode);
205  if (IsPathStart(first_pair_node)) {
206  return false;
207  }
208  int64 first_prev = Prev(first_pair_node);
209  const int second_pair_node = GetActiveAlternativeSibling(first_pair_node);
210  if (second_pair_node < 0 || IsPathEnd(second_pair_node) ||
211  IsPathStart(second_pair_node)) {
212  return false;
213  }
214  const int64 second_prev = Prev(second_pair_node);
215 
216  const int64 first_node_destination = BaseNode(kPairFirstNodeDestination);
217  if (first_node_destination == second_pair_node) {
218  // The second_pair_node -> first_pair_node link is forbidden.
219  return false;
220  }
221 
222  const int64 second_node_destination = BaseNode(kPairSecondNodeDestination);
223  if (second_prev == first_pair_node && first_node_destination == first_prev &&
224  second_node_destination == first_prev) {
225  // If the current sequence is first_prev -> first_pair_node ->
226  // second_pair_node, and both 1st and 2nd are moved both to prev, the result
227  // of the move will be first_prev -> first_pair_node -> second_pair_node,
228  // which is no move.
229  return false;
230  }
231 
232  // Relocation is successful if both moves are feasible and at least one of the
233  // nodes moves.
234  if (second_pair_node == second_node_destination ||
235  first_pair_node == first_node_destination) {
236  return false;
237  }
238  const bool moved_second_pair_node =
239  MoveChain(second_prev, second_pair_node, second_node_destination);
240  // Explictly calling Prev as second_pair_node might have been moved before
241  // first_pair_node.
242  const bool moved_first_pair_node =
243  MoveChain(Prev(first_pair_node), first_pair_node, first_node_destination);
244  // Swapping alternatives in.
245  SwapActiveAndInactive(second_pair_node,
246  BaseSiblingAlternativeNode(kPairFirstNode));
247  SwapActiveAndInactive(first_pair_node, BaseAlternativeNode(kPairFirstNode));
248  return moved_first_pair_node || moved_second_pair_node;
249 }
250 
252  // Destination node of the second node of a pair must be after the
253  // destination node of the first node of a pair.
254  if (base_index == kPairSecondNodeDestination) {
255  return BaseNode(kPairFirstNodeDestination);
256  } else {
257  return StartNode(base_index);
258  }
259 }
260 
262  const std::vector<IntVar*>& vars,
263  const std::vector<IntVar*>& secondary_vars,
264  std::function<int(int64)> start_empty_path_class,
265  const RoutingIndexPairs& index_pairs)
266  : PathOperator(vars, secondary_vars, 2, true, false,
267  std::move(start_empty_path_class)) {
268  AddPairAlternativeSets(index_pairs);
269 }
270 
272  const int64 prev1 = BaseNode(0);
273  const int64 node1 = Next(prev1);
274  if (IsPathEnd(node1)) return false;
275  const int64 sibling1 = GetActiveAlternativeSibling(node1);
276  if (sibling1 == -1) return false;
277  const int64 node2 = BaseNode(1);
278  if (node2 == sibling1) return false;
279  const int64 sibling2 = GetActiveAlternativeSibling(node2);
280  if (sibling2 == -1) return false;
281  // Note: MoveChain will return false if it is a no-op (moving the chain to its
282  // current position). However we want to accept the move if at least node1 or
283  // sibling1 gets moved to a new position. Therefore we want to be sure both
284  // MoveChains are called and at least one succeeds.
285  const bool ok = MoveChain(prev1, node1, node2);
286  return MoveChain(Prev(sibling1), sibling1, sibling2) || ok;
287 }
288 
290  const std::vector<IntVar*>& vars,
291  const std::vector<IntVar*>& secondary_vars,
292  std::function<int(int64)> start_empty_path_class,
293  const RoutingIndexPairs& index_pairs)
294  : PathOperator(vars, secondary_vars, 2, true, true,
295  std::move(start_empty_path_class)) {
296  AddPairAlternativeSets(index_pairs);
297 }
298 
300  const int64 node1 = BaseNode(0);
301  int64 prev1, sibling1, sibling_prev1 = -1;
302  if (!GetPreviousAndSibling(node1, &prev1, &sibling1, &sibling_prev1)) {
303  return false;
304  }
305  const int64 node2 = BaseNode(1);
306  int64 prev2, sibling2, sibling_prev2 = -1;
307  if (!GetPreviousAndSibling(node2, &prev2, &sibling2, &sibling_prev2)) {
308  return false;
309  }
310  bool status = true;
311  // Exchanging node1 and node2.
312  if (node1 == prev2) {
313  status = MoveChain(prev2, node2, prev1);
314  if (sibling_prev1 == node2) sibling_prev1 = node1;
315  if (sibling_prev2 == node2) sibling_prev2 = node1;
316  } else if (node2 == prev1) {
317  status = MoveChain(prev1, node1, prev2);
318  if (sibling_prev1 == node1) sibling_prev1 = node2;
319  if (sibling_prev2 == node1) sibling_prev2 = node2;
320  } else {
321  status = MoveChain(prev1, node1, node2) && MoveChain(prev2, node2, prev1);
322  if (sibling_prev1 == node1) {
323  sibling_prev1 = node2;
324  } else if (sibling_prev1 == node2) {
325  sibling_prev1 = node1;
326  }
327  if (sibling_prev2 == node1) {
328  sibling_prev2 = node2;
329  } else if (sibling_prev2 == node2) {
330  sibling_prev2 = node1;
331  }
332  }
333  if (!status) return false;
334  // Exchanging sibling1 and sibling2.
335  if (sibling1 == sibling_prev2) {
336  status = MoveChain(sibling_prev2, sibling2, sibling_prev1);
337  } else if (sibling2 == sibling_prev1) {
338  status = MoveChain(sibling_prev1, sibling1, sibling_prev2);
339  } else {
340  status = MoveChain(sibling_prev1, sibling1, sibling2) &&
341  MoveChain(sibling_prev2, sibling2, sibling_prev1);
342  }
343  // Swapping alternatives in.
348  return status;
349 }
350 
351 bool PairExchangeOperator::GetPreviousAndSibling(
352  int64 node, int64* previous, int64* sibling,
353  int64* sibling_previous) const {
354  if (IsPathStart(node)) return false;
355  *previous = Prev(node);
356  *sibling = GetActiveAlternativeSibling(node);
357  *sibling_previous = *sibling >= 0 ? Prev(*sibling) : -1;
358  return *sibling_previous >= 0;
359 }
360 
362  const std::vector<IntVar*>& vars,
363  const std::vector<IntVar*>& secondary_vars,
364  std::function<int(int64)> start_empty_path_class,
365  const RoutingIndexPairs& index_pairs)
366  : PathOperator(vars, secondary_vars, 6, true, false,
367  std::move(start_empty_path_class)) {
368  AddPairAlternativeSets(index_pairs);
369 }
370 
372  DCHECK_EQ(StartNode(kSecondPairFirstNodeDestination),
373  StartNode(kSecondPairSecondNodeDestination));
374  DCHECK_EQ(StartNode(kSecondPairFirstNode),
375  StartNode(kFirstPairFirstNodeDestination));
376  DCHECK_EQ(StartNode(kSecondPairFirstNode),
377  StartNode(kFirstPairSecondNodeDestination));
378 
379  if (StartNode(kFirstPairFirstNode) == StartNode(kSecondPairFirstNode)) {
380  SetNextBaseToIncrement(kSecondPairFirstNode);
381  return false;
382  }
383  // Through this method, <base>[X][Y] represent the <base> variable for the
384  // node Y of pair X. <base> is in node, prev, dest.
385  int64 nodes[2][2];
386  int64 prev[2][2];
387  int64 dest[2][2];
388  nodes[0][0] = BaseNode(kFirstPairFirstNode);
389  nodes[1][0] = BaseNode(kSecondPairFirstNode);
390  if (nodes[1][0] <= nodes[0][0]) {
391  // Exchange is symetric.
392  SetNextBaseToIncrement(kSecondPairFirstNode);
393  return false;
394  }
395  if (!GetPreviousAndSibling(nodes[0][0], &prev[0][0], &nodes[0][1],
396  &prev[0][1])) {
397  SetNextBaseToIncrement(kFirstPairFirstNode);
398  return false;
399  }
400  if (!GetPreviousAndSibling(nodes[1][0], &prev[1][0], &nodes[1][1],
401  &prev[1][1])) {
402  SetNextBaseToIncrement(kSecondPairFirstNode);
403  return false;
404  }
405 
406  if (!LoadAndCheckDest(0, 0, kFirstPairFirstNodeDestination, nodes, dest)) {
407  SetNextBaseToIncrement(kFirstPairFirstNodeDestination);
408  return false;
409  }
410  if (!LoadAndCheckDest(0, 1, kFirstPairSecondNodeDestination, nodes, dest)) {
411  SetNextBaseToIncrement(kFirstPairSecondNodeDestination);
412  return false;
413  }
414  if (StartNode(kSecondPairFirstNodeDestination) !=
415  StartNode(kFirstPairFirstNode) ||
416  !LoadAndCheckDest(1, 0, kSecondPairFirstNodeDestination, nodes, dest)) {
417  SetNextBaseToIncrement(kSecondPairFirstNodeDestination);
418  return false;
419  }
420  if (!LoadAndCheckDest(1, 1, kSecondPairSecondNodeDestination, nodes, dest)) {
421  SetNextBaseToIncrement(kSecondPairSecondNodeDestination);
422  return false;
423  }
424 
425  if (!MoveNode(0, 1, nodes, dest, prev)) {
426  SetNextBaseToIncrement(kFirstPairSecondNodeDestination);
427  return false;
428  }
429  if (!MoveNode(0, 0, nodes, dest, prev)) {
430  SetNextBaseToIncrement(kFirstPairSecondNodeDestination);
431  return false;
432  }
433  if (!MoveNode(1, 1, nodes, dest, prev)) {
434  return false;
435  }
436  if (!MoveNode(1, 0, nodes, dest, prev)) {
437  return false;
438  }
439  return true;
440 }
441 
442 bool PairExchangeRelocateOperator::MoveNode(int pair, int node,
443  int64 nodes[2][2], int64 dest[2][2],
444  int64 prev[2][2]) {
445  if (!MoveChain(prev[pair][node], nodes[pair][node], dest[pair][node])) {
446  return false;
447  }
448  // Update the other pair if needed.
449  if (prev[1 - pair][0] == dest[pair][node]) {
450  prev[1 - pair][0] = nodes[pair][node];
451  }
452  if (prev[1 - pair][1] == dest[pair][node]) {
453  prev[1 - pair][1] = nodes[pair][node];
454  }
455  return true;
456 }
457 
458 bool PairExchangeRelocateOperator::LoadAndCheckDest(int pair, int node,
459  int64 base_node,
460  int64 nodes[2][2],
461  int64 dest[2][2]) const {
462  dest[pair][node] = BaseNode(base_node);
463  // A destination cannot be a node that will be moved.
464  return !(nodes[0][0] == dest[pair][node] || nodes[0][1] == dest[pair][node] ||
465  nodes[1][0] == dest[pair][node] || nodes[1][1] == dest[pair][node]);
466 }
467 
469  // Ensuring the destination of the first pair is on the route of the second.
470  // pair.
471  // Ensuring that destination of both nodes of a pair are on the same route.
472  return base_index == kFirstPairFirstNodeDestination ||
473  base_index == kFirstPairSecondNodeDestination ||
474  base_index == kSecondPairSecondNodeDestination;
475 }
476 
478  if (base_index == kFirstPairSecondNodeDestination ||
479  base_index == kSecondPairSecondNodeDestination) {
480  return BaseNode(base_index - 1);
481  } else {
482  return StartNode(base_index);
483  }
484 }
485 
486 bool PairExchangeRelocateOperator::GetPreviousAndSibling(
487  int64 node, int64* previous, int64* sibling,
488  int64* sibling_previous) const {
489  if (IsPathStart(node)) return false;
490  *previous = Prev(node);
491  *sibling = GetActiveAlternativeSibling(node);
492  *sibling_previous = *sibling >= 0 ? Prev(*sibling) : -1;
493  return *sibling_previous >= 0;
494 }
495 
497  const std::vector<IntVar*>& vars, const std::vector<IntVar*>& path_vars,
498  std::function<int(int64)> start_empty_path_class,
499  const RoutingIndexPairs& index_pairs)
501  index_pairs_(index_pairs),
502  pair_index_(0),
503  first_index_(0),
504  second_index_(0),
505  number_of_nexts_(vars.size()),
506  ignore_path_vars_(path_vars.empty()) {
507  if (!ignore_path_vars_) {
508  AddVars(path_vars);
509  }
510 }
511 
513  Assignment* deltadelta) {
514  const int64 kNoPath = -1;
515  CHECK(delta != nullptr);
516  while (true) {
517  RevertChanges(true);
518 
519  if (pair_index_ < index_pairs_.size()) {
520  const int64 path =
521  ignore_path_vars_ ? 0LL : Value(first_active_ + number_of_nexts_);
522  const int64 prev_first = prevs_[first_active_];
523  const int64 next_first = Value(first_active_);
524  // Making current active "pickup" unperformed.
525  SetNext(first_active_, first_active_, kNoPath);
526  // Inserting "pickup" alternative at the same position.
527  const int64 insert_first = index_pairs_[pair_index_].first[first_index_];
528  SetNext(prev_first, insert_first, path);
529  SetNext(insert_first, next_first, path);
530  int64 prev_second = prevs_[second_active_];
531  if (prev_second == first_active_) {
532  prev_second = insert_first;
533  }
534  DCHECK_EQ(path, ignore_path_vars_
535  ? int64{0}
536  : Value(second_active_ + number_of_nexts_));
537  const int64 next_second = Value(second_active_);
538  // Making current active "delivery" unperformed.
539  SetNext(second_active_, second_active_, kNoPath);
540  // Inserting "delivery" alternative at the same position.
541  const int64 insert_second =
542  index_pairs_[pair_index_].second[second_index_];
543  SetNext(prev_second, insert_second, path);
544  SetNext(insert_second, next_second, path);
545  // Move to next "pickup/delivery" alternative.
546  ++second_index_;
547  if (second_index_ >= index_pairs_[pair_index_].second.size()) {
548  second_index_ = 0;
549  ++first_index_;
550  if (first_index_ >= index_pairs_[pair_index_].first.size()) {
551  first_index_ = 0;
552  ++pair_index_;
553  UpdateActiveNodes();
554  }
555  }
556  } else {
557  return false;
558  }
559 
560  if (ApplyChanges(delta, deltadelta)) {
561  VLOG(2) << "Delta (" << DebugString() << ") = " << delta->DebugString();
562  return true;
563  }
564  }
565  return false;
566 }
567 
569  prevs_.resize(number_of_nexts_, -1);
570  for (int index = 0; index < number_of_nexts_; ++index) {
571  const int64 next = Value(index);
572  if (next >= prevs_.size()) prevs_.resize(next + 1, -1);
573  prevs_[next] = index;
574  }
575  pair_index_ = 0;
576  first_index_ = 0;
577  second_index_ = 0;
578  first_active_ = -1;
579  second_active_ = -1;
580  while (true) {
581  if (!UpdateActiveNodes()) break;
582  if (first_active_ != -1 && second_active_ != -1) {
583  break;
584  }
585  ++pair_index_;
586  }
587 }
588 
589 bool SwapIndexPairOperator::UpdateActiveNodes() {
590  if (pair_index_ < index_pairs_.size()) {
591  for (const int64 first : index_pairs_[pair_index_].first) {
592  if (Value(first) != first) {
593  first_active_ = first;
594  break;
595  }
596  }
597  for (const int64 second : index_pairs_[pair_index_].second) {
598  if (Value(second) != second) {
599  second_active_ = second;
600  break;
601  }
602  }
603  return true;
604  }
605  return false;
606 }
607 
609  const std::vector<IntVar*>& vars,
610  const std::vector<IntVar*>& secondary_vars,
611  std::function<int(int64)> start_empty_path_class,
612  const RoutingIndexPairs& index_pairs)
613  : PathOperator(vars, secondary_vars, 1, true, false,
614  std::move(start_empty_path_class)),
615  inactive_node_(0) {
616  AddPairAlternativeSets(index_pairs);
617 }
618 
620  Assignment* deltadelta) {
621  while (inactive_node_ < Size()) {
622  if (!IsInactive(inactive_node_) ||
623  !PathOperator::MakeNextNeighbor(delta, deltadelta)) {
624  ResetPosition();
625  ++inactive_node_;
626  } else {
627  return true;
628  }
629  }
630  return false;
631 }
632 
634  const int64 base = BaseNode(0);
635  const int64 next = Next(base);
636  const int64 other = GetActiveAlternativeSibling(next);
637  if (other != -1) {
638  return MakeChainInactive(Prev(other), other) &&
639  MakeChainInactive(base, next) && MakeActive(inactive_node_, base);
640  }
641  return false;
642 }
643 
644 void IndexPairSwapActiveOperator::OnNodeInitialization() {
646  for (int i = 0; i < Size(); ++i) {
647  if (IsInactive(i)) {
648  inactive_node_ = i;
649  return;
650  }
651  }
652  inactive_node_ = Size();
653 }
654 
655 // FilteredHeuristicLocalSearchOperator
656 
658  std::unique_ptr<RoutingFilteredHeuristic> heuristic,
659  bool keep_inverse_values)
660  : IntVarLocalSearchOperator(heuristic->model()->Nexts(),
661  keep_inverse_values),
662  model_(*heuristic->model()),
663  removed_nodes_(model_.Size()),
664  heuristic_(std::move(heuristic)),
665  consider_vehicle_vars_(!model_.CostsAreHomogeneousAcrossVehicles()) {
666  if (consider_vehicle_vars_) {
668  }
669 }
670 
671 bool FilteredHeuristicLocalSearchOperator::MakeOneNeighbor() {
672  while (IncrementPosition()) {
673  // NOTE: No need to call RevertChanges() here as MakeChangeAndInsertNodes()
674  // will always return true if any change was made.
675  if (MakeChangesAndInsertNodes()) {
676  return true;
677  }
678  }
679  return false;
680 }
681 
682 bool FilteredHeuristicLocalSearchOperator::MakeChangesAndInsertNodes() {
684 
685  const std::function<int64(int64)> next_accessor =
687  if (next_accessor == nullptr) {
688  return false;
689  }
690  const Assignment* const result_assignment =
691  heuristic_->BuildSolutionFromRoutes(next_accessor);
692 
693  if (result_assignment == nullptr) {
694  return false;
695  }
696 
697  bool has_change = false;
698  const std::vector<IntVarElement>& elements =
699  result_assignment->IntVarContainer().elements();
700  for (int vehicle = 0; vehicle < model_.vehicles(); vehicle++) {
701  int64 node_index = model_.Start(vehicle);
702  while (!model_.IsEnd(node_index)) {
703  // NOTE: When building the solution in the heuristic, Next vars are added
704  // to the assignment at the position corresponding to their index.
705  const IntVarElement& node_element = elements[node_index];
706  DCHECK_EQ(node_element.Var(), model_.NextVar(node_index));
707 
708  const int64 new_node_value = node_element.Value();
709  DCHECK_NE(new_node_value, node_index);
710 
711  const int64 vehicle_var_index = VehicleVarIndex(node_index);
712  if (OldValue(node_index) != new_node_value ||
713  (consider_vehicle_vars_ && OldValue(vehicle_var_index) != vehicle)) {
714  has_change = true;
715  SetValue(node_index, new_node_value);
716  if (consider_vehicle_vars_) {
717  SetValue(vehicle_var_index, vehicle);
718  }
719  }
720  node_index = new_node_value;
721  }
722  }
723  // Check for newly unperformed nodes among the ones removed for insertion by
724  // the heuristic.
726  const IntVarElement& node_element = elements[node];
727  DCHECK_EQ(node_element.Var(), model_.NextVar(node));
728  if (node_element.Value() == node) {
729  DCHECK_NE(OldValue(node), node);
730  has_change = true;
731  SetValue(node, node);
732  if (consider_vehicle_vars_) {
733  const int64 vehicle_var_index = VehicleVarIndex(node);
734  DCHECK_NE(OldValue(vehicle_var_index), -1);
735  SetValue(vehicle_var_index, -1);
736  }
737  }
738  }
739  return has_change;
740 }
741 
742 // FilteredHeuristicPathLNSOperator
743 
745  std::unique_ptr<RoutingFilteredHeuristic> heuristic)
746  : FilteredHeuristicLocalSearchOperator(std::move(heuristic)),
747  current_route_(0),
748  last_route_(0),
749  just_started_(false) {}
750 
751 void FilteredHeuristicPathLNSOperator::OnStart() {
752  // NOTE: We set last_route_ to current_route_ here to make sure all routes
753  // are scanned in IncrementCurrentRouteToNextNonEmpty().
754  last_route_ = current_route_;
755  if (CurrentRouteIsEmpty()) {
756  IncrementCurrentRouteToNextNonEmpty();
757  }
758  just_started_ = true;
759 }
760 
761 bool FilteredHeuristicPathLNSOperator::IncrementPosition() {
762  if (just_started_) {
763  just_started_ = false;
764  return !CurrentRouteIsEmpty();
765  }
766  IncrementCurrentRouteToNextNonEmpty();
767  return current_route_ != last_route_;
768 }
769 
770 bool FilteredHeuristicPathLNSOperator::CurrentRouteIsEmpty() const {
771  return model_.IsEnd(OldValue(model_.Start(current_route_)));
772 }
773 
774 void FilteredHeuristicPathLNSOperator::IncrementCurrentRouteToNextNonEmpty() {
775  const int num_routes = model_.vehicles();
776  do {
777  ++current_route_ %= num_routes;
778  if (current_route_ == last_route_) {
779  // All routes have been scanned.
780  return;
781  }
782  } while (CurrentRouteIsEmpty());
783 }
784 
785 std::function<int64(int64)>
786 FilteredHeuristicPathLNSOperator::SetupNextAccessorForNeighbor() {
787  const int64 start_node = model_.Start(current_route_);
788  const int64 end_node = model_.End(current_route_);
789 
790  int64 node = Value(start_node);
791  while (node != end_node) {
792  removed_nodes_.Set(node);
793  node = Value(node);
794  }
795 
796  return [this, start_node, end_node](int64 node) {
797  if (node == start_node) return end_node;
798  return Value(node);
799  };
800 }
801 
802 // RelocatePathAndHeuristicInsertUnperformedOperator
803 
806  std::unique_ptr<RoutingFilteredHeuristic> heuristic)
807  : FilteredHeuristicLocalSearchOperator(std::move(heuristic)),
808  route_to_relocate_index_(0),
809  empty_route_index_(0),
810  just_started_(false) {}
811 
812 void RelocatePathAndHeuristicInsertUnperformedOperator::OnStart() {
813  has_unperformed_nodes_ = false;
814  last_node_on_route_.resize(model_.vehicles());
815  routes_to_relocate_.clear();
816  empty_routes_.clear();
817  std::vector<bool> empty_vehicle_of_vehicle_class_added(
818  model_.GetVehicleClassesCount(), false);
819  for (int64 node = 0; node < model_.Size(); node++) {
820  const int64 next = OldValue(node);
821  if (next == node) {
822  has_unperformed_nodes_ = true;
823  continue;
824  }
825  if (model_.IsEnd(next)) {
826  last_node_on_route_[model_.VehicleIndex(next)] = node;
827  }
828  }
829 
830  for (int vehicle = 0; vehicle < model_.vehicles(); vehicle++) {
831  const int64 next = OldValue(model_.Start(vehicle));
832  if (!model_.IsEnd(next)) {
833  routes_to_relocate_.push_back(vehicle);
834  continue;
835  }
836  const int vehicle_class =
837  model_.GetVehicleClassIndexOfVehicle(vehicle).value();
838  if (!empty_vehicle_of_vehicle_class_added[vehicle_class]) {
839  empty_routes_.push_back(vehicle);
840  empty_vehicle_of_vehicle_class_added[vehicle_class] = true;
841  }
842  }
843 
844  if (empty_route_index_ >= empty_routes_.size()) {
845  empty_route_index_ = 0;
846  }
847  if (route_to_relocate_index_ >= routes_to_relocate_.size()) {
848  route_to_relocate_index_ = 0;
849  }
850  last_empty_route_index_ = empty_route_index_;
851  last_route_to_relocate_index_ = route_to_relocate_index_;
852 
853  just_started_ = true;
854 }
855 
856 bool RelocatePathAndHeuristicInsertUnperformedOperator::IncrementPosition() {
857  if (!has_unperformed_nodes_ || empty_routes_.empty() ||
858  routes_to_relocate_.empty()) {
859  return false;
860  }
861  if (just_started_) {
862  just_started_ = false;
863  return true;
864  }
865  return IncrementRoutes();
866 }
867 
868 bool RelocatePathAndHeuristicInsertUnperformedOperator::IncrementRoutes() {
869  ++empty_route_index_ %= empty_routes_.size();
870  if (empty_route_index_ != last_empty_route_index_) {
871  return true;
872  }
873  ++route_to_relocate_index_ %= routes_to_relocate_.size();
874  return route_to_relocate_index_ != last_route_to_relocate_index_;
875 }
876 
877 std::function<int64(int64)> RelocatePathAndHeuristicInsertUnperformedOperator::
878  SetupNextAccessorForNeighbor() {
879  const int empty_route = empty_routes_[empty_route_index_];
880  const int relocated_route = routes_to_relocate_[route_to_relocate_index_];
881  if (model_.GetVehicleClassIndexOfVehicle(empty_route) ==
882  model_.GetVehicleClassIndexOfVehicle(relocated_route)) {
883  // Don't try to relocate the route to an empty vehicle of the same class.
884  return nullptr;
885  }
886 
887  const int64 empty_start_node = model_.Start(empty_route);
888  const int64 empty_end_node = model_.End(empty_route);
889 
890  const int64 relocated_route_start = model_.Start(relocated_route);
891  const int64 first_relocated_node = OldValue(relocated_route_start);
892  const int64 last_relocated_node = last_node_on_route_[relocated_route];
893  const int64 relocated_route_end = model_.End(relocated_route);
894 
895  return [this, empty_start_node, empty_end_node, first_relocated_node,
896  last_relocated_node, relocated_route_start,
897  relocated_route_end](int64 node) {
898  if (node == relocated_route_start) return relocated_route_end;
899  if (node == empty_start_node) return first_relocated_node;
900  if (node == last_relocated_node) return empty_end_node;
901  return Value(node);
902  };
903 }
904 
905 // FilteredHeuristicCloseNodesLNSOperator
906 
908  std::unique_ptr<RoutingFilteredHeuristic> heuristic, int num_close_nodes)
909  : FilteredHeuristicLocalSearchOperator(std::move(heuristic),
910  /*keep_inverse_values*/ true),
911  pickup_delivery_pairs_(model_.GetPickupAndDeliveryPairs()),
912  current_node_(0),
913  last_node_(0),
914  close_nodes_(model_.Size()),
915  new_nexts_(model_.Size()),
916  changed_nexts_(model_.Size()),
917  new_prevs_(model_.Size()),
918  changed_prevs_(model_.Size()) {
919  const int64 size = model_.Size();
920  const int64 max_num_neighbors =
921  std::max<int64>(0, size - 1 - model_.vehicles());
922  const int64 num_closest_neighbors =
923  std::min<int64>(num_close_nodes, max_num_neighbors);
924  DCHECK_GE(num_closest_neighbors, 0);
925 
926  if (num_closest_neighbors == 0) return;
927 
928  const int64 num_cost_classes = model_.GetCostClassesCount();
929 
930  for (int64 node = 0; node < size; node++) {
931  if (model_.IsStart(node) || model_.IsEnd(node)) continue;
932 
933  std::vector<std::pair</*cost*/ double, /*node*/ int64>> costed_after_nodes;
934  costed_after_nodes.reserve(size);
935  for (int64 after_node = 0; after_node < size; after_node++) {
936  if (model_.IsStart(after_node) || model_.IsEnd(after_node) ||
937  after_node == node) {
938  continue;
939  }
940  double total_cost = 0.0;
941  // NOTE: We don't consider the 'always-zero' cost class when searching for
942  // closest neighbors.
943  for (int cost_class = 1; cost_class < num_cost_classes; cost_class++) {
944  total_cost += model_.GetArcCostForClass(node, after_node, cost_class);
945  }
946  costed_after_nodes.emplace_back(total_cost, after_node);
947  }
948 
949  std::nth_element(costed_after_nodes.begin(),
950  costed_after_nodes.begin() + num_closest_neighbors - 1,
951  costed_after_nodes.end());
952  std::vector<int64>& neighbors = close_nodes_[node];
953  neighbors.reserve(num_closest_neighbors);
954  for (int index = 0; index < num_closest_neighbors; index++) {
955  neighbors.push_back(costed_after_nodes[index].second);
956  }
957  }
958 }
959 
960 void FilteredHeuristicCloseNodesLNSOperator::OnStart() {
961  last_node_ = current_node_;
962  just_started_ = true;
963 }
964 
965 bool FilteredHeuristicCloseNodesLNSOperator::IncrementPosition() {
966  if (just_started_) {
967  just_started_ = false;
968  return true;
969  }
970  ++current_node_ %= model_.Size();
971  return current_node_ != last_node_;
972 }
973 
974 void FilteredHeuristicCloseNodesLNSOperator::RemoveNode(int64 node) {
975  DCHECK(!model_.IsEnd(node) && !model_.IsStart(node));
976  DCHECK_NE(Value(node), node);
977  DCHECK(IsActive(node));
978 
979  removed_nodes_.Set(node);
980  const int64 prev = Prev(node);
981  const int64 next = Next(node);
982  changed_nexts_.Set(prev);
983  new_nexts_[prev] = next;
984  if (next < model_.Size()) {
985  changed_prevs_.Set(next);
986  new_prevs_[next] = prev;
987  }
988 }
989 
990 void FilteredHeuristicCloseNodesLNSOperator::RemoveNodeAndActiveSibling(
991  int64 node) {
992  if (!IsActive(node)) return;
993  RemoveNode(node);
994 
995  for (int64 sibling_node : GetActiveSiblings(node)) {
996  if (!model_.IsStart(sibling_node) && !model_.IsEnd(sibling_node)) {
997  RemoveNode(sibling_node);
998  }
999  }
1000 }
1001 
1002 std::vector<int64> FilteredHeuristicCloseNodesLNSOperator::GetActiveSiblings(
1003  int64 node) const {
1004  // NOTE: In most use-cases, where each node is a pickup or delivery in a
1005  // single index pair, this function is in O(k) where k is the number of
1006  // alternative deliveries or pickups for this index pair.
1007  std::vector<int64> active_siblings;
1008  for (std::pair<int64, int64> index_pair : model_.GetPickupIndexPairs(node)) {
1009  for (int64 sibling_delivery :
1010  pickup_delivery_pairs_[index_pair.first].second) {
1011  if (IsActive(sibling_delivery)) {
1012  active_siblings.push_back(sibling_delivery);
1013  break;
1014  }
1015  }
1016  }
1017  for (std::pair<int64, int64> index_pair :
1018  model_.GetDeliveryIndexPairs(node)) {
1019  for (int64 sibling_pickup :
1020  pickup_delivery_pairs_[index_pair.first].first) {
1021  if (IsActive(sibling_pickup)) {
1022  active_siblings.push_back(sibling_pickup);
1023  break;
1024  }
1025  }
1026  }
1027  return active_siblings;
1028 }
1029 
1030 std::function<int64(int64)>
1031 FilteredHeuristicCloseNodesLNSOperator::SetupNextAccessorForNeighbor() {
1032  if (model_.IsStart(current_node_)) {
1033  return nullptr;
1034  }
1035  DCHECK(!model_.IsEnd(current_node_));
1036 
1037  changed_nexts_.SparseClearAll();
1038  changed_prevs_.SparseClearAll();
1039 
1040  RemoveNodeAndActiveSibling(current_node_);
1041 
1042  for (int64 neighbor : close_nodes_[current_node_]) {
1043  RemoveNodeAndActiveSibling(neighbor);
1044  }
1045 
1046  return [this](int64 node) { return Next(node); };
1047 }
1048 
1049 // FilteredHeuristicExpensiveChainLNSOperator
1050 
1053  std::unique_ptr<RoutingFilteredHeuristic> heuristic,
1054  int num_arcs_to_consider,
1055  std::function<int64(int64, int64, int64)> arc_cost_for_route_start)
1056  : FilteredHeuristicLocalSearchOperator(std::move(heuristic)),
1057  current_route_(0),
1058  last_route_(0),
1059  num_arcs_to_consider_(num_arcs_to_consider),
1060  current_expensive_arc_indices_({-1, -1}),
1061  arc_cost_for_route_start_(std::move(arc_cost_for_route_start)),
1062  just_started_(false) {
1063  DCHECK_GE(num_arcs_to_consider_, 2);
1064 }
1065 
1066 void FilteredHeuristicExpensiveChainLNSOperator::OnStart() {
1067  last_route_ = current_route_;
1068  just_started_ = true;
1069 }
1070 
1071 bool FilteredHeuristicExpensiveChainLNSOperator::IncrementPosition() {
1072  if (just_started_) {
1073  just_started_ = false;
1074  return FindMostExpensiveChainsOnRemainingRoutes();
1075  }
1076 
1077  if (IncrementCurrentArcIndices()) return true;
1078 
1079  return IncrementRoute() && FindMostExpensiveChainsOnRemainingRoutes();
1080 }
1081 
1082 std::function<int64(int64)>
1083 FilteredHeuristicExpensiveChainLNSOperator::SetupNextAccessorForNeighbor() {
1084  const int first_arc_index = current_expensive_arc_indices_.first;
1085  const int second_arc_index = current_expensive_arc_indices_.second;
1086  DCHECK_LE(0, first_arc_index);
1087  DCHECK_LT(first_arc_index, second_arc_index);
1088  DCHECK_LT(second_arc_index, most_expensive_arc_starts_and_ranks_.size());
1089 
1090  const std::pair<int, int>& first_start_and_rank =
1091  most_expensive_arc_starts_and_ranks_[first_arc_index];
1092  const std::pair<int, int>& second_start_and_rank =
1093  most_expensive_arc_starts_and_ranks_[second_arc_index];
1094  int64 before_chain, after_chain;
1095  if (first_start_and_rank.second < second_start_and_rank.second) {
1096  before_chain = first_start_and_rank.first;
1097  after_chain = OldValue(second_start_and_rank.first);
1098  } else {
1099  before_chain = second_start_and_rank.first;
1100  after_chain = OldValue(first_start_and_rank.first);
1101  }
1102 
1103  int node = Value(before_chain);
1104  while (node != after_chain) {
1105  removed_nodes_.Set(node);
1106  node = Value(node);
1107  }
1108 
1109  return [this, before_chain, after_chain](int64 node) {
1110  if (node == before_chain) return after_chain;
1111  return OldValue(node);
1112  };
1113 }
1114 
1115 bool FilteredHeuristicExpensiveChainLNSOperator::IncrementRoute() {
1116  ++current_route_ %= model_.vehicles();
1117  return current_route_ != last_route_;
1118 }
1119 
1120 bool FilteredHeuristicExpensiveChainLNSOperator::IncrementCurrentArcIndices() {
1121  int& second_index = current_expensive_arc_indices_.second;
1122  if (++second_index < most_expensive_arc_starts_and_ranks_.size()) {
1123  return true;
1124  }
1125  int& first_index = current_expensive_arc_indices_.first;
1126  if (first_index + 2 < most_expensive_arc_starts_and_ranks_.size()) {
1127  first_index++;
1128  second_index = first_index + 1;
1129  return true;
1130  }
1131  return false;
1132 }
1133 
1134 namespace {
1135 
1136 // Returns false if the route starting with 'start' is empty. Otherwise sets
1137 // most_expensive_arc_starts_and_ranks and first_expensive_arc_indices according
1138 // to the most expensive chains on the route, and returns true.
1139 bool FindMostExpensiveArcsOnRoute(
1140  int num_arcs, int64 start, const std::function<int64(int64)>& next_accessor,
1141  const std::function<bool(int64)>& is_end,
1142  const std::function<int64(int64, int64, int64)>& arc_cost_for_route_start,
1143  std::vector<std::pair<int64, int>>* most_expensive_arc_starts_and_ranks,
1144  std::pair<int, int>* first_expensive_arc_indices) {
1145  if (is_end(next_accessor(start))) {
1146  // Empty route.
1147  *first_expensive_arc_indices = {-1, -1};
1148  return false;
1149  }
1150 
1151  // NOTE: The negative ranks are so that for a given cost, lower ranks are
1152  // given higher priority.
1153  using ArcCostNegativeRankStart = std::tuple<int64, int, int64>;
1154  std::priority_queue<ArcCostNegativeRankStart,
1155  std::vector<ArcCostNegativeRankStart>,
1156  std::greater<ArcCostNegativeRankStart>>
1157  arc_info_pq;
1158 
1159  int64 before_node = start;
1160  int rank = 0;
1161  while (!is_end(before_node)) {
1162  const int64 after_node = next_accessor(before_node);
1163  const int64 arc_cost =
1164  arc_cost_for_route_start(before_node, after_node, start);
1165  arc_info_pq.emplace(arc_cost, -rank, before_node);
1166 
1167  before_node = after_node;
1168  rank++;
1169 
1170  if (rank > num_arcs) {
1171  arc_info_pq.pop();
1172  }
1173  }
1174 
1175  DCHECK_GE(rank, 2);
1176  DCHECK_EQ(arc_info_pq.size(), std::min(rank, num_arcs));
1177 
1178  most_expensive_arc_starts_and_ranks->resize(arc_info_pq.size());
1179  int arc_index = arc_info_pq.size() - 1;
1180  while (!arc_info_pq.empty()) {
1181  const ArcCostNegativeRankStart& arc_info = arc_info_pq.top();
1182  (*most_expensive_arc_starts_and_ranks)[arc_index] = {
1183  std::get<2>(arc_info), -std::get<1>(arc_info)};
1184  arc_index--;
1185  arc_info_pq.pop();
1186  }
1187 
1188  *first_expensive_arc_indices = {0, 1};
1189  return true;
1190 }
1191 
1192 } // namespace
1193 
1194 bool FilteredHeuristicExpensiveChainLNSOperator::
1195  FindMostExpensiveChainsOnRemainingRoutes() {
1196  do {
1197  if (FindMostExpensiveArcsOnRoute(
1198  num_arcs_to_consider_, model_.Start(current_route_),
1199  [this](int64 i) { return OldValue(i); },
1200  [this](int64 node) { return model_.IsEnd(node); },
1201  arc_cost_for_route_start_, &most_expensive_arc_starts_and_ranks_,
1202  &current_expensive_arc_indices_)) {
1203  return true;
1204  }
1205  } while (IncrementRoute());
1206 
1207  return false;
1208 }
1209 
1211  const std::vector<IntVar*>& vars,
1212  const std::vector<IntVar*>& secondary_vars,
1213  std::function<int(int64)> start_empty_path_class, int num_arcs_to_consider,
1214  std::function<int64(int64, int64, int64)> arc_cost_for_path_start)
1215  : PathOperator(vars, secondary_vars, 1, false, false,
1216  std::move(start_empty_path_class)),
1217  num_arcs_to_consider_(num_arcs_to_consider),
1218  current_path_(0),
1219  current_expensive_arc_indices_({-1, -1}),
1220  arc_cost_for_path_start_(std::move(arc_cost_for_path_start)),
1221  end_path_(0),
1222  has_non_empty_paths_to_explore_(false) {
1223  DCHECK_GE(num_arcs_to_consider_, 2);
1224 }
1225 
1227  const int first_arc_index = current_expensive_arc_indices_.first;
1228  const int second_arc_index = current_expensive_arc_indices_.second;
1229  DCHECK_LE(0, first_arc_index);
1230  DCHECK_LT(first_arc_index, second_arc_index);
1231  DCHECK_LT(second_arc_index, most_expensive_arc_starts_and_ranks_.size());
1232 
1233  const std::pair<int, int>& first_start_and_rank =
1234  most_expensive_arc_starts_and_ranks_[first_arc_index];
1235  const std::pair<int, int>& second_start_and_rank =
1236  most_expensive_arc_starts_and_ranks_[second_arc_index];
1237  if (first_start_and_rank.second < second_start_and_rank.second) {
1238  return CheckChainValidity(first_start_and_rank.first,
1239  second_start_and_rank.first, BaseNode(0)) &&
1240  MoveChain(first_start_and_rank.first, second_start_and_rank.first,
1241  BaseNode(0));
1242  }
1243  return CheckChainValidity(second_start_and_rank.first,
1244  first_start_and_rank.first, BaseNode(0)) &&
1245  MoveChain(second_start_and_rank.first, first_start_and_rank.first,
1246  BaseNode(0));
1247 }
1248 
1250  while (has_non_empty_paths_to_explore_) {
1252  ResetPosition();
1253  // Move on to the next expensive arcs on the same path.
1254  if (IncrementCurrentArcIndices()) {
1255  continue;
1256  }
1257  // Move on to the next non_empty path.
1258  IncrementCurrentPath();
1259  has_non_empty_paths_to_explore_ =
1260  current_path_ != end_path_ &&
1261  FindMostExpensiveChainsOnRemainingPaths();
1262  } else {
1263  return true;
1264  }
1265  }
1266  return false;
1267 }
1268 
1269 void RelocateExpensiveChain::OnNodeInitialization() {
1270  if (current_path_ >= path_starts().size()) {
1271  // current_path_ was made empty by last move (and it was the last non-empty
1272  // path), restart from 0.
1273  current_path_ = 0;
1274  }
1275  end_path_ = current_path_;
1276  has_non_empty_paths_to_explore_ = FindMostExpensiveChainsOnRemainingPaths();
1277 }
1278 
1279 void RelocateExpensiveChain::IncrementCurrentPath() {
1280  const int num_paths = path_starts().size();
1281  if (++current_path_ == num_paths) {
1282  current_path_ = 0;
1283  }
1284 }
1285 
1286 bool RelocateExpensiveChain::IncrementCurrentArcIndices() {
1287  int& second_index = current_expensive_arc_indices_.second;
1288  if (++second_index < most_expensive_arc_starts_and_ranks_.size()) {
1289  return true;
1290  }
1291  int& first_index = current_expensive_arc_indices_.first;
1292  if (first_index + 2 < most_expensive_arc_starts_and_ranks_.size()) {
1293  first_index++;
1294  second_index = first_index + 1;
1295  return true;
1296  }
1297  return false;
1298 }
1299 
1300 bool RelocateExpensiveChain::FindMostExpensiveChainsOnRemainingPaths() {
1301  do {
1302  if (FindMostExpensiveArcsOnRoute(
1303  num_arcs_to_consider_, path_starts()[current_path_],
1304  [this](int64 i) { return OldNext(i); },
1305  [this](int64 node) { return IsPathEnd(node); },
1306  arc_cost_for_path_start_, &most_expensive_arc_starts_and_ranks_,
1307  &current_expensive_arc_indices_)) {
1308  return true;
1309  }
1310  IncrementCurrentPath();
1311  } while (current_path_ != end_path_);
1312  return false;
1313 }
1314 
1316  const std::vector<IntVar*>& vars,
1317  const std::vector<IntVar*>& secondary_vars,
1318  std::function<int(int64)> start_empty_path_class,
1319  const RoutingIndexPairs& pairs)
1320  : PathOperator(vars, secondary_vars,
1321  /*number_of_base_nodes*/ 2, true, false,
1322  std::move(start_empty_path_class)) {
1323  is_pickup_node_.resize(number_of_nexts_, false);
1324  is_delivery_node_.resize(number_of_nexts_, false);
1325  pair_of_node_.resize(number_of_nexts_, -1);
1326  for (int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
1327  for (const int node : pairs[pair_index].first) {
1328  is_pickup_node_[node] = true;
1329  pair_of_node_[node] = pair_index;
1330  }
1331  for (const int node : pairs[pair_index].second) {
1332  is_delivery_node_[node] = true;
1333  pair_of_node_[node] = pair_index;
1334  }
1335  }
1336  opened_pairs_bitset_.resize(pairs.size(), false);
1337 }
1338 
1339 bool RelocateSubtrip::RelocateSubTripFromPickup(const int64 chain_first_node,
1340  const int64 insertion_node) {
1341  if (IsPathEnd(insertion_node)) return false;
1342  if (Prev(chain_first_node) == insertion_node)
1343  return false; // Skip null move.
1344 
1345  int num_opened_pairs = 0;
1346  // Split chain into subtrip and rejected nodes.
1347  rejected_nodes_ = {Prev(chain_first_node)};
1348  subtrip_nodes_ = {insertion_node};
1349  int current = chain_first_node;
1350  do {
1351  if (current == insertion_node) {
1352  // opened_pairs_bitset_ must be all false when we leave this function.
1353  opened_pairs_bitset_.assign(opened_pairs_bitset_.size(), false);
1354  return false;
1355  }
1356  const int pair = pair_of_node_[current];
1357  if (is_delivery_node_[current] && !opened_pairs_bitset_[pair]) {
1358  rejected_nodes_.push_back(current);
1359  } else {
1360  subtrip_nodes_.push_back(current);
1361  if (is_pickup_node_[current]) {
1362  ++num_opened_pairs;
1363  opened_pairs_bitset_[pair] = true;
1364  } else if (is_delivery_node_[current]) {
1365  --num_opened_pairs;
1366  opened_pairs_bitset_[pair] = false;
1367  }
1368  }
1369  current = Next(current);
1370  } while (num_opened_pairs != 0 && !IsPathEnd(current));
1371  DCHECK_EQ(num_opened_pairs, 0);
1372  rejected_nodes_.push_back(current);
1373  subtrip_nodes_.push_back(Next(insertion_node));
1374 
1375  // Set new paths.
1376  const int64 rejected_path = Path(chain_first_node);
1377  for (int i = 1; i < rejected_nodes_.size(); ++i) {
1378  SetNext(rejected_nodes_[i - 1], rejected_nodes_[i], rejected_path);
1379  }
1380  const int64 insertion_path = Path(insertion_node);
1381  for (int i = 1; i < subtrip_nodes_.size(); ++i) {
1382  SetNext(subtrip_nodes_[i - 1], subtrip_nodes_[i], insertion_path);
1383  }
1384  return true;
1385 }
1386 
1387 bool RelocateSubtrip::RelocateSubTripFromDelivery(const int64 chain_last_node,
1388  const int64 insertion_node) {
1389  if (IsPathEnd(insertion_node)) return false;
1390 
1391  // opened_pairs_bitset_ should be all false.
1392  DCHECK(std::none_of(opened_pairs_bitset_.begin(), opened_pairs_bitset_.end(),
1393  [](bool value) { return value; }));
1394  int num_opened_pairs = 0;
1395  // Split chain into subtrip and rejected nodes. Store nodes in reverse order.
1396  rejected_nodes_ = {Next(chain_last_node)};
1397  subtrip_nodes_ = {Next(insertion_node)};
1398  int current = chain_last_node;
1399  do {
1400  if (current == insertion_node) {
1401  opened_pairs_bitset_.assign(opened_pairs_bitset_.size(), false);
1402  return false;
1403  }
1404  const int pair = pair_of_node_[current];
1405  if (is_pickup_node_[current] && !opened_pairs_bitset_[pair]) {
1406  rejected_nodes_.push_back(current);
1407  } else {
1408  subtrip_nodes_.push_back(current);
1409  if (is_delivery_node_[current]) {
1410  ++num_opened_pairs;
1411  opened_pairs_bitset_[pair] = true;
1412  } else if (is_pickup_node_[current]) {
1413  --num_opened_pairs;
1414  opened_pairs_bitset_[pair] = false;
1415  }
1416  }
1417  current = Prev(current);
1418  } while (num_opened_pairs != 0 && !IsPathStart(current));
1419  DCHECK_EQ(num_opened_pairs, 0);
1420  if (current == insertion_node) return false; // Skip null move.
1421  rejected_nodes_.push_back(current);
1422  subtrip_nodes_.push_back(insertion_node);
1423 
1424  // TODO(user): either remove those std::reverse() and adapt the loops
1425  // below, or refactor the loops into a function that also DCHECKs the path.
1426  std::reverse(rejected_nodes_.begin(), rejected_nodes_.end());
1427  std::reverse(subtrip_nodes_.begin(), subtrip_nodes_.end());
1428 
1429  // Set new paths.
1430  const int64 rejected_path = Path(chain_last_node);
1431  for (int i = 1; i < rejected_nodes_.size(); ++i) {
1432  SetNext(rejected_nodes_[i - 1], rejected_nodes_[i], rejected_path);
1433  }
1434  const int64 insertion_path = Path(insertion_node);
1435  for (int i = 1; i < subtrip_nodes_.size(); ++i) {
1436  SetNext(subtrip_nodes_[i - 1], subtrip_nodes_[i], insertion_path);
1437  }
1438  return true;
1439 }
1440 
1442  if (is_pickup_node_[BaseNode(0)]) {
1443  return RelocateSubTripFromPickup(BaseNode(0), BaseNode(1));
1444  } else if (is_delivery_node_[BaseNode(0)]) {
1445  return RelocateSubTripFromDelivery(BaseNode(0), BaseNode(1));
1446  } else {
1447  return false;
1448  }
1449 }
1450 
1452  const std::vector<IntVar*>& vars,
1453  const std::vector<IntVar*>& secondary_vars,
1454  std::function<int(int64)> start_empty_path_class,
1455  const RoutingIndexPairs& pairs)
1456  : PathOperator(vars, secondary_vars, 2, true, false,
1457  std::move(start_empty_path_class)) {
1458  is_pickup_node_.resize(number_of_nexts_, false);
1459  is_delivery_node_.resize(number_of_nexts_, false);
1460  pair_of_node_.resize(number_of_nexts_, -1);
1461  for (int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
1462  for (const int node : pairs[pair_index].first) {
1463  is_pickup_node_[node] = true;
1464  pair_of_node_[node] = pair_index;
1465  }
1466  for (const int node : pairs[pair_index].second) {
1467  is_delivery_node_[node] = true;
1468  pair_of_node_[node] = pair_index;
1469  }
1470  }
1471  opened_pairs_set_.resize(pairs.size(), false);
1472 }
1473 
1474 void ExchangeSubtrip::SetPath(const std::vector<int64>& path, int path_id) {
1475  for (int i = 1; i < path.size(); ++i) {
1476  SetNext(path[i - 1], path[i], path_id);
1477  }
1478 }
1479 
1480 namespace {
1481 bool VectorContains(const std::vector<int64>& values, int64 target) {
1482  return std::find(values.begin(), values.end(), target) != values.end();
1483 }
1484 } // namespace
1485 
1487  if (pair_of_node_[BaseNode(0)] == -1) return false;
1488  if (pair_of_node_[BaseNode(1)] == -1) return false;
1489  // Break symmetry: a move generated from (BaseNode(0), BaseNode(1)) is the
1490  // same as from (BaseNode(1), BaseNode(1)): no need to do it twice.
1491  if (BaseNode(0) >= BaseNode(1)) return false;
1492  rejects0_.clear();
1493  subtrip0_.clear();
1494  if (!ExtractChainsAndCheckCanonical(BaseNode(0), &rejects0_, &subtrip0_)) {
1495  return false;
1496  }
1497  rejects1_.clear();
1498  subtrip1_.clear();
1499  if (!ExtractChainsAndCheckCanonical(BaseNode(1), &rejects1_, &subtrip1_)) {
1500  return false;
1501  }
1502 
1503  // If paths intersect, skip the move.
1504  if (Path(BaseNode(0)) == Path(BaseNode(1))) {
1505  if (VectorContains(rejects0_, subtrip1_.front())) return false;
1506  if (VectorContains(rejects1_, subtrip0_.front())) return false;
1507  if (VectorContains(subtrip0_, subtrip1_.front())) return false;
1508  if (VectorContains(subtrip1_, subtrip0_.front())) return false;
1509  }
1510 
1511  // Assemble the new paths.
1512  path0_ = {Prev(subtrip0_.front())};
1513  path1_ = {Prev(subtrip1_.front())};
1514  const int64 last0 = Next(subtrip0_.back());
1515  const int64 last1 = Next(subtrip1_.back());
1516  const bool concatenated01 = last0 == subtrip1_.front();
1517  const bool concatenated10 = last1 == subtrip0_.front();
1518 
1519  if (is_delivery_node_[BaseNode(0)]) std::swap(subtrip1_, rejects0_);
1520  path0_.insert(path0_.end(), subtrip1_.begin(), subtrip1_.end());
1521  path0_.insert(path0_.end(), rejects0_.begin(), rejects0_.end());
1522  path0_.push_back(last0);
1523 
1524  if (is_delivery_node_[BaseNode(1)]) std::swap(subtrip0_, rejects1_);
1525  path1_.insert(path1_.end(), subtrip0_.begin(), subtrip0_.end());
1526  path1_.insert(path1_.end(), rejects1_.begin(), rejects1_.end());
1527  path1_.push_back(last1);
1528 
1529  // When the trips are concatenated, bypass the regular extremities.
1530  if (concatenated01) {
1531  path0_.pop_back();
1532  path1_.front() = path0_.back();
1533  } else if (concatenated10) {
1534  path1_.pop_back();
1535  path0_.front() = path1_.back();
1536  }
1537 
1538  // Change the paths. Since SetNext() modifies Path() values,
1539  // record path_id0 and path_id11 before calling SetPath();
1540  const int64 path0_id = Path(BaseNode(0));
1541  const int64 path1_id = Path(BaseNode(1));
1542  SetPath(path0_, path0_id);
1543  SetPath(path1_, path1_id);
1544  return true;
1545 }
1546 
1547 bool ExchangeSubtrip::ExtractChainsAndCheckCanonical(
1548  int64 base_node, std::vector<int64>* rejects, std::vector<int64>* subtrip) {
1549  const bool extracted =
1550  is_pickup_node_[base_node]
1551  ? ExtractChainsFromPickup(base_node, rejects, subtrip)
1552  : ExtractChainsFromDelivery(base_node, rejects, subtrip);
1553  if (!extracted) return false;
1554  // Check canonicality.
1555  return !is_delivery_node_[base_node] ||
1556  pair_of_node_[subtrip->front()] != pair_of_node_[subtrip->back()] ||
1557  !rejects->empty();
1558 }
1559 
1560 bool ExchangeSubtrip::ExtractChainsFromPickup(int64 base_node,
1561  std::vector<int64>* rejects,
1562  std::vector<int64>* subtrip) {
1563  DCHECK(is_pickup_node_[base_node]);
1564  DCHECK(rejects->empty());
1565  DCHECK(subtrip->empty());
1566  // Iterate from base_node forwards while maintaining the set of opened pairs.
1567  // A pair is opened by a pickup, closed with the corresponding delivery.
1568  opened_pairs_set_.assign(opened_pairs_set_.size(), false);
1569  int num_opened_pairs = 0;
1570  int current = base_node;
1571  do {
1572  const int pair = pair_of_node_[current];
1573  if (is_delivery_node_[current] && !opened_pairs_set_[pair]) {
1574  rejects->push_back(current);
1575  } else {
1576  subtrip->push_back(current);
1577  if (is_pickup_node_[current]) {
1578  ++num_opened_pairs;
1579  opened_pairs_set_[pair] = true;
1580  } else if (is_delivery_node_[current]) {
1581  --num_opened_pairs;
1582  opened_pairs_set_[pair] = false;
1583  }
1584  }
1585  current = Next(current);
1586  } while (num_opened_pairs != 0 && !IsPathEnd(current));
1587  return num_opened_pairs == 0;
1588 }
1589 
1590 bool ExchangeSubtrip::ExtractChainsFromDelivery(int64 base_node,
1591  std::vector<int64>* rejects,
1592  std::vector<int64>* subtrip) {
1593  DCHECK(is_delivery_node_[base_node]);
1594  DCHECK(rejects->empty());
1595  DCHECK(subtrip->empty());
1596  // Iterate from base_node backwards while maintaining the set of opened pairs.
1597  // A pair is opened by a delivery, closed with the corresponding pickup.
1598  opened_pairs_set_.assign(opened_pairs_set_.size(), false);
1599  int num_opened_pairs = 0;
1600  int current = base_node;
1601  do {
1602  const int pair = pair_of_node_[current];
1603  if (is_pickup_node_[current] && !opened_pairs_set_[pair]) {
1604  rejects->push_back(current);
1605  } else {
1606  subtrip->push_back(current);
1607  if (is_delivery_node_[current]) {
1608  ++num_opened_pairs;
1609  opened_pairs_set_[pair] = true;
1610  } else if (is_pickup_node_[current]) {
1611  --num_opened_pairs;
1612  opened_pairs_set_[pair] = false;
1613  }
1614  }
1615  current = Prev(current);
1616  } while (num_opened_pairs != 0 && !IsPathStart(current));
1617  if (num_opened_pairs != 0) return false;
1618  std::reverse(rejects->begin(), rejects->end());
1619  std::reverse(subtrip->begin(), subtrip->end());
1620  return true;
1621 }
1622 
1623 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#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
#define VLOG(verboselevel)
Definition: base/logging.h:978
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)
FilteredHeuristicCloseNodesLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_close_nodes)
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.
FilteredHeuristicPathLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
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)
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...
MakePairInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
MakeRelocateNeighborsOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, RoutingTransitCallback2 arc_evaluator)
PairExchangeOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
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)
PairRelocateOperator(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...
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
int64 BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual void SetNextBaseToIncrement(int64 base_index)
Set the next base to increment on next iteration.
const std::vector< int64 > & path_starts() const
Returns the vector of path start nodes.
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
void AddPairAlternativeSets(const std::vector< std::pair< std::vector< int64 >, std::vector< int64 >>> &pair_alternative_sets)
Adds all sets of node alternatives of a vector of alternative pairs.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 StartNode(int i) const
Returns the start node of the ith base node.
int64 Next(int64 node) const
Returns the node after node in the current delta.
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
bool IsPathStart(int64 node) const
Returns true if node is the first node on the path.
int64 BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
bool CheckChainValidity(int64 before_chain, int64 chain_end, int64 exclude) const
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not ...
int64 GetActiveAlternativeSibling(int node) const
Returns the active node in the alternative set of the sibling of the given node.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
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.
RelocatePathAndHeuristicInsertUnperformedOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
RelocateSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
Definition: routing.h:1278
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1347
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
Definition: routing.h:1273
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
Definition: routing.h:1203
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
Definition: routing.cc:3928
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1345
int VehicleIndex(int64 index) const
Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/en...
Definition: routing.h:1189
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
Definition: routing.h:1268
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
Definition: routing.cc:3896
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
Definition: routing.cc:1707
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
Definition: routing.cc:1713
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
void Set(IntegerType index)
Definition: bitset.h:803
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)
IntVar * Var(int64 index) const
Returns the variable of given index.
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
Block * next
int64 value
GRBmodel * model
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
int index
Definition: pack.cc:508
int64 delta
Definition: resource.cc:1684