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
22namespace 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
49bool 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
69int64 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;
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
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
147void MakePairActiveOperator::OnNodeInitialization() {
148 inactive_pair_ = FindNextInactivePair(0);
149 inactive_pair_first_index_ = 0;
150 inactive_pair_second_index_ = 0;
151}
152
153int 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
163bool 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
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
351bool 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
442bool 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
458bool 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
486bool 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
589bool 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_) ||
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);
637 if (other != -1) {
638 return MakeChainInactive(Prev(other), other) &&
639 MakeChainInactive(base, next) && MakeActive(inactive_node_, base);
640 }
641 return false;
642}
643
644void 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
671bool 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
682bool 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
751void 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
761bool FilteredHeuristicPathLNSOperator::IncrementPosition() {
762 if (just_started_) {
763 just_started_ = false;
764 return !CurrentRouteIsEmpty();
765 }
766 IncrementCurrentRouteToNextNonEmpty();
767 return current_route_ != last_route_;
768}
769
770bool FilteredHeuristicPathLNSOperator::CurrentRouteIsEmpty() const {
771 return model_.IsEnd(OldValue(model_.Start(current_route_)));
772}
773
774void 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
785std::function<int64(int64)>
786FilteredHeuristicPathLNSOperator::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
812void 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(
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
856bool 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
868bool 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
877std::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
960void FilteredHeuristicCloseNodesLNSOperator::OnStart() {
961 last_node_ = current_node_;
962 just_started_ = true;
963}
964
965bool 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
974void 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
990void 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
1002std::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 :
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
1030std::function<int64(int64)>
1031FilteredHeuristicCloseNodesLNSOperator::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
1066void FilteredHeuristicExpensiveChainLNSOperator::OnStart() {
1067 last_route_ = current_route_;
1068 just_started_ = true;
1069}
1070
1071bool 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
1082std::function<int64(int64)>
1083FilteredHeuristicExpensiveChainLNSOperator::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
1115bool FilteredHeuristicExpensiveChainLNSOperator::IncrementRoute() {
1116 ++current_route_ %= model_.vehicles();
1117 return current_route_ != last_route_;
1118}
1119
1120bool 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
1134namespace {
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.
1139bool 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
1194bool 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
1269void 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
1279void RelocateExpensiveChain::IncrementCurrentPath() {
1280 const int num_paths = path_starts().size();
1281 if (++current_path_ == num_paths) {
1282 current_path_ = 0;
1283 }
1284}
1285
1286bool 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
1300bool 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
1339bool 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
1387bool 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
1474void 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
1480namespace {
1481bool 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
1547bool 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
1560bool 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
1590bool 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.
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 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.
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
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
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
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
void Set(IntegerType index)
Definition: bitset.h:803
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
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
STL namespace.
int index
Definition: pack.cc:508
int64 delta
Definition: resource.cc:1684