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 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
15 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
16
17 #include <cstdint>
18 #include <functional>
19 #include <memory>
20 #include <string>
21 #include <utility>
22 #include <vector>
23
24 #include "absl/strings/str_cat.h"
25 #include "ortools/base/logging.h"
26 #include "ortools/constraint_solver/constraint_solver.h"
27 #include "ortools/constraint_solver/constraint_solveri.h"
28 #include "ortools/constraint_solver/routing.h"
29 #include "ortools/constraint_solver/routing_search.h"
30 #include "ortools/constraint_solver/routing_types.h"
31 #include "ortools/util/bitset.h"
32
33 namespace operations_research {
34
35 /// Relocate neighborhood which moves chains of neighbors.
36 /// The operator starts by relocating a node n after a node m, then continues
37 /// moving nodes which were after n as long as the "cost" added is less than
38 /// the "cost" of the arc (m, n). If the new chain doesn't respect the domain of
39 /// next variables, it will try reordering the nodes.
40 /// Possible neighbors for path 1 -> A -> B -> C -> D -> E -> 2 (where (1, 2)
41 /// are first and last nodes of the path and can therefore not be moved, A must
42 /// be performed before B, and A, D and E are located at the same place):
43 /// 1 -> A -> C -> [B] -> D -> E -> 2
44 /// 1 -> A -> C -> D -> [B] -> E -> 2
45 /// 1 -> A -> C -> D -> E -> [B] -> 2
46 /// 1 -> A -> B -> D -> [C] -> E -> 2
47 /// 1 -> A -> B -> D -> E -> [C] -> 2
48 /// 1 -> A -> [D] -> [E] -> B -> C -> 2
49 /// 1 -> A -> B -> [D] -> [E] -> C -> 2
50 /// 1 -> A -> [E] -> B -> C -> D -> 2
51 /// 1 -> A -> B -> [E] -> C -> D -> 2
52 /// 1 -> A -> B -> C -> [E] -> D -> 2
53 /// This operator is extremely useful to move chains of nodes which are located
54 /// at the same place (for instance nodes part of a same stop).
55 // TODO(user): Consider merging with standard Relocate in local_search.cc.
56 class MakeRelocateNeighborsOperator : public PathOperator {
57 public:
58 MakeRelocateNeighborsOperator(
59 const std::vector<IntVar*>& vars,
60 const std::vector<IntVar*>& secondary_vars,
61 std::function<int(int64_t)> start_empty_path_class,
62 RoutingTransitCallback2 arc_evaluator);
~MakeRelocateNeighborsOperator()63 ~MakeRelocateNeighborsOperator() override {}
64
65 bool MakeNeighbor() override;
DebugString()66 std::string DebugString() const override { return "RelocateNeighbors"; }
67
68 private:
69 /// Moves a chain starting after 'before_chain' and ending at 'chain_end'
70 /// after node 'destination'. Tries to repair the resulting solution by
71 /// checking if the new arc created after 'destination' is compatible with
72 /// NextVar domains, and moves the 'destination' down the path if the solution
73 /// is inconsistent. Iterates the process on the new arcs created before
74 /// the node 'destination' (if destination was moved).
75 bool MoveChainAndRepair(int64_t before_chain, int64_t chain_end,
76 int64_t destination);
77
78 /// Moves node after 'before_to_move' down the path until a position is found
79 /// where NextVar domains are not violated, if it exists. Stops when reaching
80 /// position after 'up_to'.
81 /// If the node was not moved (either because the current position does not
82 /// violate any domains or because not such position could be found), returns
83 /// -1. If the node was moved to a new position before up_to, returns up_to;
84 /// if it was moved just after up_to returns the node which was after up_to.
85 int64_t Reposition(int64_t before_to_move, int64_t up_to);
86
87 RoutingTransitCallback2 arc_evaluator_;
88 };
89
90 /// Pair-based neighborhood operators, designed to move nodes by pairs (pairs
91 /// are static and given). These neighborhoods are very useful for Pickup and
92 /// Delivery problems where pickup and delivery nodes must remain on the same
93 /// route.
94 // TODO(user): Add option to prune neighbords where the order of node pairs
95 // is violated (ie precedence between pickup and delivery nodes).
96 // TODO(user): Move this to local_search.cc if it's generic enough.
97 // TODO(user): Detect pairs automatically by parsing the constraint model;
98 // we could then get rid of the pair API in the RoutingModel
99 // class.
100
101 /// Operator which inserts pairs of inactive nodes into a path.
102 /// Possible neighbors for the path 1 -> 2 -> 3 with pair (A, B) inactive
103 /// (where 1 and 3 are first and last nodes of the path) are:
104 /// 1 -> [A] -> [B] -> 2 -> 3
105 /// 1 -> [B] -> 2 -> [A] -> 3
106 /// 1 -> [A] -> 2 -> [B] -> 3
107 /// 1 -> 2 -> [A] -> [B] -> 3
108 /// Note that this operator does not expicitely insert the nodes of a pair one
109 /// after the other which forbids the following solutions:
110 /// 1 -> [B] -> [A] -> 2 -> 3
111 /// 1 -> 2 -> [B] -> [A] -> 3
112 /// which can only be obtained by inserting A after B.
113 class MakePairActiveOperator : public PathOperator {
114 public:
115 MakePairActiveOperator(const std::vector<IntVar*>& vars,
116 const std::vector<IntVar*>& secondary_vars,
117 std::function<int(int64_t)> start_empty_path_class,
118 const RoutingIndexPairs& pairs);
~MakePairActiveOperator()119 ~MakePairActiveOperator() override {}
120 bool MakeNeighbor() override;
DebugString()121 std::string DebugString() const override { return "MakePairActive"; }
122
123 protected:
124 bool MakeOneNeighbor() override;
OnSamePathAsPreviousBase(int64_t base_index)125 bool OnSamePathAsPreviousBase(int64_t base_index) override {
126 /// Both base nodes have to be on the same path since they represent the
127 /// nodes after which unactive node pairs will be moved.
128 return true;
129 }
130
131 int64_t GetBaseNodeRestartPosition(int base_index) override;
132
133 /// Required to ensure that after synchronization the operator is in a state
134 /// compatible with GetBaseNodeRestartPosition.
RestartAtPathStartOnSynchronize()135 bool RestartAtPathStartOnSynchronize() override { return true; }
136
137 private:
138 void OnNodeInitialization() override;
139 int FindNextInactivePair(int pair_index) const;
140 bool ContainsActiveNodes(const std::vector<int64_t>& nodes) const;
141
142 int inactive_pair_;
143 int inactive_pair_first_index_;
144 int inactive_pair_second_index_;
145 const RoutingIndexPairs pairs_;
146 };
147
148 /// Operator which makes pairs of active nodes inactive.
149 class MakePairInactiveOperator : public PathOperator {
150 public:
151 MakePairInactiveOperator(const std::vector<IntVar*>& vars,
152 const std::vector<IntVar*>& secondary_vars,
153 std::function<int(int64_t)> start_empty_path_class,
154 const RoutingIndexPairs& index_pairs);
155
156 bool MakeNeighbor() override;
DebugString()157 std::string DebugString() const override { return "MakePairInActive"; }
158 };
159
160 /// Operator which moves a pair of nodes to another position where the first
161 /// node of the pair must be before the second node on the same path.
162 /// Possible neighbors for the path 1 -> A -> B -> 2 -> 3 (where (1, 3) are
163 /// first and last nodes of the path and can therefore not be moved, and (A, B)
164 /// is a pair of nodes):
165 /// 1 -> [A] -> 2 -> [B] -> 3
166 /// 1 -> 2 -> [A] -> [B] -> 3
167 /// The pair can be moved to another path.
168 class PairRelocateOperator : public PathOperator {
169 public:
170 PairRelocateOperator(const std::vector<IntVar*>& vars,
171 const std::vector<IntVar*>& secondary_vars,
172 std::function<int(int64_t)> start_empty_path_class,
173 const RoutingIndexPairs& index_pairs);
~PairRelocateOperator()174 ~PairRelocateOperator() override {}
175
176 bool MakeNeighbor() override;
DebugString()177 std::string DebugString() const override { return "PairRelocateOperator"; }
178
179 protected:
OnSamePathAsPreviousBase(int64_t base_index)180 bool OnSamePathAsPreviousBase(int64_t base_index) override {
181 /// Both destination nodes must be on the same path.
182 return base_index == kPairSecondNodeDestination;
183 }
184 int64_t GetBaseNodeRestartPosition(int base_index) override;
185
ConsiderAlternatives(int64_t base_index)186 bool ConsiderAlternatives(int64_t base_index) const override {
187 return base_index == kPairFirstNode;
188 }
189
190 private:
RestartAtPathStartOnSynchronize()191 bool RestartAtPathStartOnSynchronize() override { return true; }
192
193 static constexpr int kPairFirstNode = 0;
194 static constexpr int kPairFirstNodeDestination = 1;
195 static constexpr int kPairSecondNodeDestination = 2;
196 };
197
198 class LightPairRelocateOperator : public PathOperator {
199 public:
200 LightPairRelocateOperator(const std::vector<IntVar*>& vars,
201 const std::vector<IntVar*>& secondary_vars,
202 std::function<int(int64_t)> start_empty_path_class,
203 const RoutingIndexPairs& index_pairs);
~LightPairRelocateOperator()204 ~LightPairRelocateOperator() override {}
205
206 bool MakeNeighbor() override;
DebugString()207 std::string DebugString() const override {
208 return "LightPairRelocateOperator";
209 }
210 };
211
212 /// Operator which exchanges the position of two pairs; for both pairs the first
213 /// node of the pair must be before the second node on the same path.
214 /// Possible neighbors for the paths 1 -> A -> B -> 2 -> 3 and 4 -> C -> D -> 5
215 /// (where (1, 3) and (4, 5) are first and last nodes of the paths and can
216 /// therefore not be moved, and (A, B) and (C,D) are pairs of nodes):
217 /// 1 -> [C] -> [D] -> 2 -> 3, 4 -> [A] -> [B] -> 5
218 class PairExchangeOperator : public PathOperator {
219 public:
220 PairExchangeOperator(const std::vector<IntVar*>& vars,
221 const std::vector<IntVar*>& secondary_vars,
222 std::function<int(int64_t)> start_empty_path_class,
223 const RoutingIndexPairs& index_pairs);
~PairExchangeOperator()224 ~PairExchangeOperator() override {}
225
226 bool MakeNeighbor() override;
DebugString()227 std::string DebugString() const override { return "PairExchangeOperator"; }
228
229 private:
RestartAtPathStartOnSynchronize()230 bool RestartAtPathStartOnSynchronize() override { return true; }
ConsiderAlternatives(int64_t base_index)231 bool ConsiderAlternatives(int64_t base_index) const override { return true; }
232 bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,
233 int64_t* sibling_previous) const;
234 };
235
236 /// Operator which exchanges the paths of two pairs (path have to be different).
237 /// Pairs are inserted in all possible positions in their new path with the
238 /// constraint that the second node must be placed after the first.
239 /// Possible neighbors for the path 1 -> A -> B -> 2 -> 3, 4 -> C -> 5 -> D -> 6
240 /// 1 -> C -> D -> 2 -> 3 4 -> A -> B -> 5 -> 6
241 /// 1 -> C -> 2 -> D -> 3 4 -> A -> 5 -> B -> 6
242 /// 1 -> 2 -> C -> D -> 3 4 -> 5 -> A -> B -> 6
243 /// 1 -> C -> D -> 2 -> 3 4 -> A -> B -> 5 -> 6
244 /// 1 -> C -> 2 -> D -> 3 4 -> A -> 5 -> B -> 6
245 /// 1 -> 2 -> C -> D -> 3 4 -> 5 -> A -> B -> 6
246 /// 1 -> C -> D -> 2 -> 3 4 -> A -> B -> 5 -> 6
247 /// 1 -> C -> 2 -> D -> 3 4 -> A -> 5 -> B -> 6
248 /// 1 -> 2 -> C -> D -> 3 4 -> 5 -> A -> B -> 6
249 class PairExchangeRelocateOperator : public PathOperator {
250 public:
251 PairExchangeRelocateOperator(
252 const std::vector<IntVar*>& vars,
253 const std::vector<IntVar*>& secondary_vars,
254 std::function<int(int64_t)> start_empty_path_class,
255 const RoutingIndexPairs& index_pairs);
~PairExchangeRelocateOperator()256 ~PairExchangeRelocateOperator() override {}
257
258 bool MakeNeighbor() override;
DebugString()259 std::string DebugString() const override {
260 return "PairExchangeRelocateOperator";
261 }
262
263 protected:
264 bool OnSamePathAsPreviousBase(int64_t base_index) override;
265 int64_t GetBaseNodeRestartPosition(int base_index) override;
266
267 private:
RestartAtPathStartOnSynchronize()268 bool RestartAtPathStartOnSynchronize() override { return true; }
269 bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,
270 int64_t* sibling_previous) const;
271 bool MoveNode(int pair, int node, int64_t nodes[2][2], int64_t dest[2][2],
272 int64_t prev[2][2]);
273 bool LoadAndCheckDest(int pair, int node, int64_t base_node,
274 int64_t nodes[2][2], int64_t dest[2][2]) const;
275
276 static constexpr int kFirstPairFirstNode = 0;
277 static constexpr int kSecondPairFirstNode = 1;
278 static constexpr int kFirstPairFirstNodeDestination = 2;
279 static constexpr int kFirstPairSecondNodeDestination = 3;
280 static constexpr int kSecondPairFirstNodeDestination = 4;
281 static constexpr int kSecondPairSecondNodeDestination = 5;
282 };
283
284 /// Operator which iterates through each alternative of a set of pairs. If a
285 /// pair has n and m alternatives, n.m alternatives will be explored.
286 /// Possible neighbors for the path 1 -> A -> a -> 2 (where (1, 2) are first and
287 /// last nodes of a path and A has B, C as alternatives and a has b as
288 /// alternative):
289 /// 1 -> A -> [b] -> 2
290 /// 1 -> [B] -> a -> 2
291 /// 1 -> [B] -> [b] -> 2
292 /// 1 -> [C] -> a -> 2
293 /// 1 -> [C] -> [b] -> 2
294 class SwapIndexPairOperator : public IntVarLocalSearchOperator {
295 public:
296 SwapIndexPairOperator(const std::vector<IntVar*>& vars,
297 const std::vector<IntVar*>& path_vars,
298 std::function<int(int64_t)> start_empty_path_class,
299 const RoutingIndexPairs& index_pairs);
~SwapIndexPairOperator()300 ~SwapIndexPairOperator() override {}
301
302 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
303 void OnStart() override;
DebugString()304 std::string DebugString() const override { return "SwapIndexPairOperator"; }
305
306 private:
307 /// Updates first_active_ and second_active_ to make them correspond to the
308 /// active nodes of the node pair of index pair_index_.
309 bool UpdateActiveNodes();
310 /// Sets the to to be the node after from
SetNext(int64_t from,int64_t to,int64_t path)311 void SetNext(int64_t from, int64_t to, int64_t path) {
312 DCHECK_LT(from, number_of_nexts_);
313 SetValue(from, to);
314 if (!ignore_path_vars_) {
315 DCHECK_LT(from + number_of_nexts_, Size());
316 SetValue(from + number_of_nexts_, path);
317 }
318 }
319
320 const RoutingIndexPairs index_pairs_;
321 int pair_index_;
322 int first_index_;
323 int second_index_;
324 int64_t first_active_;
325 int64_t second_active_;
326 std::vector<int64_t> prevs_;
327 const int number_of_nexts_;
328 const bool ignore_path_vars_;
329 };
330
331 /// Operator which inserts inactive nodes into a path and makes a pair of
332 /// active nodes inactive.
333 class IndexPairSwapActiveOperator : public PathOperator {
334 public:
335 IndexPairSwapActiveOperator(
336 const std::vector<IntVar*>& vars,
337 const std::vector<IntVar*>& secondary_vars,
338 std::function<int(int64_t)> start_empty_path_class,
339 const RoutingIndexPairs& index_pairs);
~IndexPairSwapActiveOperator()340 ~IndexPairSwapActiveOperator() override {}
341
342 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
343 bool MakeNeighbor() override;
DebugString()344 std::string DebugString() const override {
345 return "IndexPairSwapActiveOperator";
346 }
347
348 private:
349 void OnNodeInitialization() override;
350
351 int inactive_node_;
352 };
353
354 /// Class of operators using a RoutingFilteredHeuristic to insert unperformed
355 /// nodes after changes have been made to the current solution.
356 // TODO(user): Put these methods in an object with helper methods instead
357 // of adding a layer to the class hierarchy.
358 class FilteredHeuristicLocalSearchOperator : public IntVarLocalSearchOperator {
359 public:
360 explicit FilteredHeuristicLocalSearchOperator(
361 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
362 bool keep_inverse_values = false);
~FilteredHeuristicLocalSearchOperator()363 ~FilteredHeuristicLocalSearchOperator() override {}
364
365 protected:
366 virtual bool IncrementPosition() = 0;
367 /// Virtual method to return the next_accessor to be passed to the heuristic
368 /// to build a new solution. This method should also correctly set the
369 /// nodes being removed (if any) in removed_nodes_.
370 virtual std::function<int64_t(int64_t)> SetupNextAccessorForNeighbor() = 0;
371
HeuristicName()372 std::string HeuristicName() const {
373 std::string heuristic_name = heuristic_->DebugString();
374 const int erase_pos = heuristic_name.find("FilteredHeuristic");
375 if (erase_pos != std::string::npos) {
376 const int expected_name_size = heuristic_name.size() - 17;
377 heuristic_name.erase(erase_pos);
378 // NOTE: Verify that the "FilteredHeuristic" string was at the end of the
379 // heuristic name.
380 DCHECK_EQ(heuristic_name.size(), expected_name_size);
381 }
382 return heuristic_name;
383 }
384
385 // TODO(user): Remove the dependency from RoutingModel by storing an
386 // IntVarFilteredHeuristic here instead and storing information on path
387 // start/ends like PathOperator does (instead of relying on the model).
388 RoutingModel* const model_;
389 /// Keeps track of removed nodes when making a neighbor.
390 SparseBitset<> removed_nodes_;
391
392 private:
393 bool MakeOneNeighbor() override;
394 bool MakeChangesAndInsertNodes();
395
VehicleVarIndex(int64_t node)396 int64_t VehicleVarIndex(int64_t node) const { return model_->Size() + node; }
397
398 const std::unique_ptr<RoutingFilteredHeuristic> heuristic_;
399 const bool consider_vehicle_vars_;
400 };
401
402 /// LNS-like operator based on a filtered first solution heuristic to rebuild
403 /// the solution, after the destruction phase consisting of removing one route.
404 class FilteredHeuristicPathLNSOperator
405 : public FilteredHeuristicLocalSearchOperator {
406 public:
407 explicit FilteredHeuristicPathLNSOperator(
408 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
~FilteredHeuristicPathLNSOperator()409 ~FilteredHeuristicPathLNSOperator() override {}
410
DebugString()411 std::string DebugString() const override {
412 return absl::StrCat("HeuristicPathLNS(", HeuristicName(), ")");
413 }
414
415 private:
416 void OnStart() override;
417
418 bool IncrementPosition() override;
419 bool CurrentRouteIsEmpty() const;
420 void IncrementCurrentRouteToNextNonEmpty();
421
422 std::function<int64_t(int64_t)> SetupNextAccessorForNeighbor() override;
423
424 int current_route_;
425 int last_route_;
426 bool just_started_;
427 };
428
429 /// Heuristic-based local search operator which relocates an entire route to
430 /// an empty vehicle of different vehicle class and then tries to insert
431 /// unperformed nodes using the heuristic.
432 class RelocatePathAndHeuristicInsertUnperformedOperator
433 : public FilteredHeuristicLocalSearchOperator {
434 public:
435 explicit RelocatePathAndHeuristicInsertUnperformedOperator(
436 std::unique_ptr<RoutingFilteredHeuristic> heuristic);
~RelocatePathAndHeuristicInsertUnperformedOperator()437 ~RelocatePathAndHeuristicInsertUnperformedOperator() override {}
438
DebugString()439 std::string DebugString() const override {
440 return absl::StrCat("RelocatePathAndHeuristicInsertUnperformed(",
441 HeuristicName(), ")");
442 }
443
444 private:
445 void OnStart() override;
446
447 bool IncrementPosition() override;
448 bool IncrementRoutes();
449
450 std::function<int64_t(int64_t)> SetupNextAccessorForNeighbor() override;
451
452 int route_to_relocate_index_;
453 int last_route_to_relocate_index_;
454 int empty_route_index_;
455 int last_empty_route_index_;
456 std::vector<int> routes_to_relocate_;
457 std::vector<int> empty_routes_;
458 std::vector<int64_t> last_node_on_route_;
459 bool has_unperformed_nodes_;
460 bool just_started_;
461 };
462
463 /// Similar to the heuristic path LNS above, but instead of removing one route
464 /// entirely, the destruction phase consists of removing all nodes on an
465 /// "expensive" chain from a route.
466 class FilteredHeuristicExpensiveChainLNSOperator
467 : public FilteredHeuristicLocalSearchOperator {
468 public:
469 FilteredHeuristicExpensiveChainLNSOperator(
470 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
471 int num_arcs_to_consider,
472 std::function<int64_t(int64_t, int64_t, int64_t)>
473 arc_cost_for_route_start);
~FilteredHeuristicExpensiveChainLNSOperator()474 ~FilteredHeuristicExpensiveChainLNSOperator() override {}
475
DebugString()476 std::string DebugString() const override {
477 return absl::StrCat("HeuristicExpensiveChainLNS(", HeuristicName(), ")");
478 }
479
480 private:
481 void OnStart() override;
482
483 bool IncrementPosition() override;
484 bool IncrementRoute();
485 bool IncrementCurrentArcIndices();
486 bool FindMostExpensiveChainsOnRemainingRoutes();
487
488 std::function<int64_t(int64_t)> SetupNextAccessorForNeighbor() override;
489
490 int current_route_;
491 int last_route_;
492
493 const int num_arcs_to_consider_;
494 std::vector<std::pair<int64_t, int>> most_expensive_arc_starts_and_ranks_;
495 /// Indices in most_expensive_arc_starts_and_ranks_ corresponding to the first
496 /// and second arcs currently being considered for removal.
497 std::pair</*first_arc_index*/ int, /*second_arc_index*/ int>
498 current_expensive_arc_indices_;
499 std::function<int64_t(/*before_node*/ int64_t, /*after_node*/ int64_t,
500 /*path_start*/ int64_t)>
501 arc_cost_for_route_start_;
502
503 bool just_started_;
504 };
505
506 /// Filtered heuristic LNS operator, where the destruction phase consists of
507 /// removing a node and the 'num_close_nodes' nodes closest to it, along with
508 /// each of their corresponding sibling pickup/deliveries that are performed.
509 class FilteredHeuristicCloseNodesLNSOperator
510 : public FilteredHeuristicLocalSearchOperator {
511 public:
512 FilteredHeuristicCloseNodesLNSOperator(
513 std::unique_ptr<RoutingFilteredHeuristic> heuristic, int num_close_nodes);
~FilteredHeuristicCloseNodesLNSOperator()514 ~FilteredHeuristicCloseNodesLNSOperator() override {}
515
DebugString()516 std::string DebugString() const override {
517 return absl::StrCat("HeuristicCloseNodesLNS(", HeuristicName(), ")");
518 }
519
520 private:
521 void OnStart() override;
522
523 bool IncrementPosition() override;
524
525 std::function<int64_t(int64_t)> SetupNextAccessorForNeighbor() override;
526
527 void RemoveNode(int64_t node);
528 void RemoveNodeAndActiveSibling(int64_t node);
529
IsActive(int64_t node)530 bool IsActive(int64_t node) const {
531 DCHECK_LT(node, model_->Size());
532 return Value(node) != node && !removed_nodes_[node];
533 }
534
Prev(int64_t node)535 int64_t Prev(int64_t node) const {
536 DCHECK_EQ(Value(InverseValue(node)), node);
537 DCHECK_LT(node, new_prevs_.size());
538 return changed_prevs_[node] ? new_prevs_[node] : InverseValue(node);
539 }
Next(int64_t node)540 int64_t Next(int64_t node) const {
541 DCHECK(!model_->IsEnd(node));
542 return changed_nexts_[node] ? new_nexts_[node] : Value(node);
543 }
544
545 std::vector<int64_t> GetActiveSiblings(int64_t node) const;
546
547 const std::vector<std::pair<std::vector<int64_t>, std::vector<int64_t>>>&
548 pickup_delivery_pairs_;
549
550 int current_node_;
551 int last_node_;
552 bool just_started_;
553
554 std::vector<std::vector<int64_t>> close_nodes_;
555 /// Keep track of changes when making a neighbor.
556 std::vector<int64_t> new_nexts_;
557 SparseBitset<> changed_nexts_;
558 std::vector<int64_t> new_prevs_;
559 SparseBitset<> changed_prevs_;
560 };
561
562 /// RelocateExpensiveChain
563 ///
564 /// Operator which relocates the most expensive subchains (given a cost
565 /// callback) in a path to a different position.
566 ///
567 /// The most expensive chain on a path is the one resulting from cutting the 2
568 /// most expensive arcs on this path.
569 class RelocateExpensiveChain : public PathOperator {
570 public:
571 RelocateExpensiveChain(const std::vector<IntVar*>& vars,
572 const std::vector<IntVar*>& secondary_vars,
573 std::function<int(int64_t)> start_empty_path_class,
574 int num_arcs_to_consider,
575 std::function<int64_t(int64_t, int64_t, int64_t)>
576 arc_cost_for_path_start);
~RelocateExpensiveChain()577 ~RelocateExpensiveChain() override {}
578 bool MakeNeighbor() override;
579 bool MakeOneNeighbor() override;
580
DebugString()581 std::string DebugString() const override { return "RelocateExpensiveChain"; }
582
583 private:
584 void OnNodeInitialization() override;
585 void IncrementCurrentPath();
586 bool IncrementCurrentArcIndices();
587 /// Tries to find most expensive chains on remaining paths, starting with the
588 /// current one, until succeeding on one of them.
589 /// Returns false iff all remaining paths are empty.
590 bool FindMostExpensiveChainsOnRemainingPaths();
591
592 int num_arcs_to_consider_;
593 int current_path_;
594 std::vector<std::pair<int64_t, int>> most_expensive_arc_starts_and_ranks_;
595 /// Indices in most_expensive_arc_starts_and_ranks_ corresponding to the first
596 /// and second arcs currently being considered for removal.
597 std::pair</*first_arc_index*/ int, /*second_arc_index*/ int>
598 current_expensive_arc_indices_;
599 std::function<int64_t(/*before_node*/ int64_t, /*after_node*/ int64_t,
600 /*path_start*/ int64_t)>
601 arc_cost_for_path_start_;
602 int end_path_;
603 /// The following boolean indicates if there are any non-empty paths left to
604 /// explore by the operator.
605 bool has_non_empty_paths_to_explore_;
606 };
607
608 /// Operator which inserts pairs of inactive nodes into a path and makes an
609 /// active node inactive.
610 /// There are two versions:
611 /// - one which makes inactive the node being replaced by the first node of the
612 /// pair (with swap_first true);
613 /// - one which makes inactive the node being replaced by the second node of the
614 /// pair (with swap_first false).
615 template <bool swap_first>
616 class PairNodeSwapActiveOperator : public PathOperator {
617 public:
618 PairNodeSwapActiveOperator(const std::vector<IntVar*>& vars,
619 const std::vector<IntVar*>& secondary_vars,
620 std::function<int(int64_t)> start_empty_path_class,
621 const RoutingIndexPairs& index_pairs);
~PairNodeSwapActiveOperator()622 ~PairNodeSwapActiveOperator() override {}
623
624 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
625 bool MakeNeighbor() override;
DebugString()626 std::string DebugString() const override {
627 return "PairNodeSwapActiveOperator";
628 }
629
630 protected:
OnSamePathAsPreviousBase(int64_t base_index)631 bool OnSamePathAsPreviousBase(int64_t base_index) override {
632 /// Both base nodes have to be on the same path since they represent the
633 /// nodes after which unactive node pairs will be moved.
634 return true;
635 }
636
637 int64_t GetBaseNodeRestartPosition(int base_index) override;
638
639 /// Required to ensure that after synchronization the operator is in a state
640 /// compatible with GetBaseNodeRestartPosition.
RestartAtPathStartOnSynchronize()641 bool RestartAtPathStartOnSynchronize() override { return true; }
642
643 private:
644 void OnNodeInitialization() override;
645
646 int inactive_pair_;
647 RoutingIndexPairs pairs_;
648 };
649
650 // ==========================================================================
651 // Section: Implementations of the template classes declared above.
652
653 template <bool swap_first>
PairNodeSwapActiveOperator(const std::vector<IntVar * > & vars,const std::vector<IntVar * > & secondary_vars,std::function<int (int64_t)> start_empty_path_class,const RoutingIndexPairs & index_pairs)654 PairNodeSwapActiveOperator<swap_first>::PairNodeSwapActiveOperator(
655 const std::vector<IntVar*>& vars,
656 const std::vector<IntVar*>& secondary_vars,
657 std::function<int(int64_t)> start_empty_path_class,
658 const RoutingIndexPairs& index_pairs)
659 : PathOperator(vars, secondary_vars, 2, false, false,
660 std::move(start_empty_path_class)),
661 inactive_pair_(0),
662 pairs_(index_pairs) {}
663
664 template <bool swap_first>
GetBaseNodeRestartPosition(int base_index)665 int64_t PairNodeSwapActiveOperator<swap_first>::GetBaseNodeRestartPosition(
666 int base_index) {
667 // Base node 1 must be after base node 0 if they are both on the same path.
668 if (base_index == 0 || StartNode(base_index) != StartNode(base_index - 1)) {
669 return StartNode(base_index);
670 } else {
671 return BaseNode(base_index - 1);
672 }
673 }
674
675 template <bool swap_first>
OnNodeInitialization()676 void PairNodeSwapActiveOperator<swap_first>::OnNodeInitialization() {
677 for (int i = 0; i < pairs_.size(); ++i) {
678 if (IsInactive(pairs_[i].first[0]) && IsInactive(pairs_[i].second[0])) {
679 inactive_pair_ = i;
680 return;
681 }
682 }
683 inactive_pair_ = pairs_.size();
684 }
685
686 template <bool swap_first>
MakeNextNeighbor(Assignment * delta,Assignment * deltadelta)687 bool PairNodeSwapActiveOperator<swap_first>::MakeNextNeighbor(
688 Assignment* delta, Assignment* deltadelta) {
689 while (inactive_pair_ < pairs_.size()) {
690 if (!IsInactive(pairs_[inactive_pair_].first[0]) ||
691 !IsInactive(pairs_[inactive_pair_].second[0]) ||
692 !PathOperator::MakeNextNeighbor(delta, deltadelta)) {
693 ResetPosition();
694 ++inactive_pair_;
695 } else {
696 return true;
697 }
698 }
699 return false;
700 }
701
702 template <bool swap_first>
MakeNeighbor()703 bool PairNodeSwapActiveOperator<swap_first>::MakeNeighbor() {
704 const int64_t base = BaseNode(0);
705 if (IsPathEnd(base)) {
706 return false;
707 }
708 const int64_t pair_first = pairs_[inactive_pair_].first[0];
709 const int64_t pair_second = pairs_[inactive_pair_].second[0];
710 if (swap_first) {
711 return MakeActive(pair_second, BaseNode(1)) &&
712 MakeActive(pair_first, base) &&
713 MakeChainInactive(pair_first, Next(pair_first));
714 } else {
715 return MakeActive(pair_second, BaseNode(1)) &&
716 MakeActive(pair_first, base) &&
717 MakeChainInactive(pair_second, Next(pair_second));
718 }
719 }
720
721 /// Tries to move subtrips after an insertion node.
722 /// A subtrip is a subsequence that contains only matched pickup and delivery
723 /// nodes, or pickup-only nodes, i.e. it cannot contain a pickup without a
724 /// corresponding delivery or vice-versa.
725 ///
726 /// For a given subtrip given by path indices i_1 ... i_k, we call 'rejected'
727 /// the nodes with indices i_1 < j < i_k that are not in the subtrip. If the
728 /// base_node is a pickup, this operator selects the smallest subtrip starting
729 /// at base_node such that rejected nodes are only deliveries. If the base_node
730 /// is a delivery, it selects the smallest subtrip ending at base_node such that
731 /// rejected nodes are only pickups.
732 class RelocateSubtrip : public PathOperator {
733 public:
734 RelocateSubtrip(const std::vector<IntVar*>& vars,
735 const std::vector<IntVar*>& secondary_vars,
736 std::function<int(int64_t)> start_empty_path_class,
737 const RoutingIndexPairs& pairs);
738
DebugString()739 std::string DebugString() const override { return "RelocateSubtrip"; }
740 bool MakeNeighbor() override;
741
742 private:
743 // Relocates the subtrip starting at chain_first_node. It must be a pickup.
744 bool RelocateSubTripFromPickup(int64_t chain_first_node,
745 int64_t insertion_node);
746 /// Relocates the subtrip ending at chain_first_node. It must be a delivery.
747 bool RelocateSubTripFromDelivery(int64_t chain_last_node,
748 int64_t insertion_node);
749 std::vector<bool> is_pickup_node_;
750 std::vector<bool> is_delivery_node_;
751 std::vector<int> pair_of_node_;
752 // Represents the set of pairs that have been opened during a call to
753 // MakeNeighbor(). This vector must be all false before and after calling
754 // RelocateSubTripFromPickup() and RelocateSubTripFromDelivery().
755 std::vector<bool> opened_pairs_bitset_;
756
757 std::vector<int64_t> rejected_nodes_;
758 std::vector<int64_t> subtrip_nodes_;
759 };
760
761 class ExchangeSubtrip : public PathOperator {
762 public:
763 ExchangeSubtrip(const std::vector<IntVar*>& vars,
764 const std::vector<IntVar*>& secondary_vars,
765 std::function<int(int64_t)> start_empty_path_class,
766 const RoutingIndexPairs& pairs);
767
DebugString()768 std::string DebugString() const override { return "ExchangeSubtrip"; }
769 bool MakeNeighbor() override;
770
771 private:
772 // Try to extract a subtrip from base_node (see below) and check that the move
773 // will be canonical.
774 // Given a pickup/delivery pair, this operator could generate the same move
775 // twice, the first time with base_node == pickup, the second time with
776 // base_node == delivery. This happens only when no nodes in the subtrip
777 // remain in the original path, i.e. when rejects is empty after
778 // chain extraction. In that case, we keep only a canonical move out of the
779 // two possibilities, the move where base_node is a pickup.
780 bool ExtractChainsAndCheckCanonical(int64_t base_node,
781 std::vector<int64_t>* rejects,
782 std::vector<int64_t>* subtrip);
783 // Reads the path from base_node forward, collecting subtrip nodes in
784 // subtrip and non-subtrip nodes in rejects.
785 // Non-subtrip nodes will be unmatched delivery nodes.
786 // base_node must be a pickup, and remaining/extracted_nodes must be empty.
787 // Returns true if such chains could be extracted.
788 bool ExtractChainsFromPickup(int64_t base_node, std::vector<int64_t>* rejects,
789 std::vector<int64_t>* subtrip);
790 // Reads the path from base_node backward, collecting subtrip nodes in
791 // subtrip and non-subtrip nodes in rejects.
792 // Non-subtrip nodes will be unmatched pickup nodes.
793 // base_node must be a delivery, and remaining/extracted_nodes must be empty.
794 // Returns true if such chains could be extracted.
795 bool ExtractChainsFromDelivery(int64_t base_node,
796 std::vector<int64_t>* rejects,
797 std::vector<int64_t>* subtrip);
798 void SetPath(const std::vector<int64_t>& path, int path_id);
799
800 // Precompute some information about nodes.
801 std::vector<bool> is_pickup_node_;
802 std::vector<bool> is_delivery_node_;
803 std::vector<int> pair_of_node_;
804 // Represents the set of opened pairs during ExtractChainsFromXXX().
805 std::vector<bool> opened_pairs_set_;
806 // Keep internal structures under hand to avoid reallocation.
807 std::vector<int64_t> rejects0_;
808 std::vector<int64_t> subtrip0_;
809 std::vector<int64_t> rejects1_;
810 std::vector<int64_t> subtrip1_;
811 std::vector<int64_t> path0_;
812 std::vector<int64_t> path1_;
813 };
814
815 } // namespace operations_research
816
817 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
818