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