OR-Tools  8.2
routing_search.cc
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 // Implementation of all classes related to routing and search.
15 // This includes decision builders, local search neighborhood operators
16 // and local search filters.
17 // TODO(user): Move all existing routing search code here.
18 
19 #include <algorithm>
20 #include <cstdlib>
21 #include <map>
22 #include <numeric>
23 #include <set>
24 #include <utility>
25 
26 #include "absl/container/flat_hash_map.h"
27 #include "absl/container/flat_hash_set.h"
30 #include "ortools/base/map_util.h"
31 #include "ortools/base/small_map.h"
33 #include "ortools/base/stl_util.h"
40 #include "ortools/util/bitset.h"
42 
43 ABSL_FLAG(bool, routing_strong_debug_checks, false,
44  "Run stronger checks in debug; these stronger tests might change "
45  "the complexity of the code in particular.");
46 ABSL_FLAG(bool, routing_shift_insertion_cost_by_penalty, true,
47  "Shift insertion costs by the penalty of the inserted node(s).");
48 
49 namespace operations_research {
50 
51 namespace {
52 
53 // Max active vehicles filter.
54 
55 class MaxActiveVehiclesFilter : public IntVarLocalSearchFilter {
56  public:
57  explicit MaxActiveVehiclesFilter(const RoutingModel& routing_model)
58  : IntVarLocalSearchFilter(routing_model.Nexts()),
59  routing_model_(routing_model),
60  is_active_(routing_model.vehicles(), false),
61  active_vehicles_(0) {}
62  bool Accept(const Assignment* delta, const Assignment* deltadelta,
63  int64 objective_min, int64 objective_max) override {
64  const int64 kUnassigned = -1;
65  const Assignment::IntContainer& container = delta->IntVarContainer();
66  const int delta_size = container.Size();
67  int current_active_vehicles = active_vehicles_;
68  for (int i = 0; i < delta_size; ++i) {
69  const IntVarElement& new_element = container.Element(i);
70  IntVar* const var = new_element.Var();
72  if (FindIndex(var, &index) && routing_model_.IsStart(index)) {
73  if (new_element.Min() != new_element.Max()) {
74  // LNS detected.
75  return true;
76  }
77  const int vehicle = routing_model_.VehicleIndex(index);
78  const bool is_active =
79  (new_element.Min() != routing_model_.End(vehicle));
80  if (is_active && !is_active_[vehicle]) {
81  ++current_active_vehicles;
82  } else if (!is_active && is_active_[vehicle]) {
83  --current_active_vehicles;
84  }
85  }
86  }
87  return current_active_vehicles <=
88  routing_model_.GetMaximumNumberOfActiveVehicles();
89  }
90 
91  private:
92  void OnSynchronize(const Assignment* delta) override {
93  active_vehicles_ = 0;
94  for (int i = 0; i < routing_model_.vehicles(); ++i) {
95  const int index = routing_model_.Start(i);
96  if (IsVarSynced(index) && Value(index) != routing_model_.End(i)) {
97  is_active_[i] = true;
98  ++active_vehicles_;
99  } else {
100  is_active_[i] = false;
101  }
102  }
103  }
104 
105  const RoutingModel& routing_model_;
106  std::vector<bool> is_active_;
107  int active_vehicles_;
108 };
109 } // namespace
110 
112  const RoutingModel& routing_model) {
113  return routing_model.solver()->RevAlloc(
114  new MaxActiveVehiclesFilter(routing_model));
115 }
116 
117 namespace {
118 
119 // Node disjunction filter class.
120 
121 class NodeDisjunctionFilter : public IntVarLocalSearchFilter {
122  public:
123  explicit NodeDisjunctionFilter(const RoutingModel& routing_model)
124  : IntVarLocalSearchFilter(routing_model.Nexts()),
125  routing_model_(routing_model),
126  active_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
127  inactive_per_disjunction_(routing_model.GetNumberOfDisjunctions(), 0),
128  synchronized_objective_value_(kint64min),
129  accepted_objective_value_(kint64min) {}
130 
131  bool Accept(const Assignment* delta, const Assignment* deltadelta,
132  int64 objective_min, int64 objective_max) override {
133  const int64 kUnassigned = -1;
134  const Assignment::IntContainer& container = delta->IntVarContainer();
135  const int delta_size = container.Size();
137  disjunction_active_deltas;
139  disjunction_inactive_deltas;
140  bool lns_detected = false;
141  // Update active/inactive count per disjunction for each element of delta.
142  for (int i = 0; i < delta_size; ++i) {
143  const IntVarElement& new_element = container.Element(i);
144  IntVar* const var = new_element.Var();
146  if (FindIndex(var, &index)) {
147  const bool is_inactive =
148  (new_element.Min() <= index && new_element.Max() >= index);
149  if (new_element.Min() != new_element.Max()) {
150  lns_detected = true;
151  }
152  for (const RoutingModel::DisjunctionIndex disjunction_index :
153  routing_model_.GetDisjunctionIndices(index)) {
154  const bool active_state_changed =
155  !IsVarSynced(index) || (Value(index) == index) != is_inactive;
156  if (active_state_changed) {
157  if (!is_inactive) {
158  ++gtl::LookupOrInsert(&disjunction_active_deltas,
159  disjunction_index, 0);
160  if (IsVarSynced(index)) {
161  --gtl::LookupOrInsert(&disjunction_inactive_deltas,
162  disjunction_index, 0);
163  }
164  } else {
165  ++gtl::LookupOrInsert(&disjunction_inactive_deltas,
166  disjunction_index, 0);
167  if (IsVarSynced(index)) {
168  --gtl::LookupOrInsert(&disjunction_active_deltas,
169  disjunction_index, 0);
170  }
171  }
172  }
173  }
174  }
175  }
176  // Check if any disjunction has too many active nodes.
177  for (const std::pair<RoutingModel::DisjunctionIndex, int>
178  disjunction_active_delta : disjunction_active_deltas) {
179  const int current_active_nodes =
180  active_per_disjunction_[disjunction_active_delta.first];
181  const int active_nodes =
182  current_active_nodes + disjunction_active_delta.second;
183  const int max_cardinality = routing_model_.GetDisjunctionMaxCardinality(
184  disjunction_active_delta.first);
185  // Too many active nodes.
186  if (active_nodes > max_cardinality) {
187  return false;
188  }
189  }
190  // Update penalty costs for disjunctions.
191  accepted_objective_value_ = synchronized_objective_value_;
192  for (const std::pair<RoutingModel::DisjunctionIndex, int>
193  disjunction_inactive_delta : disjunction_inactive_deltas) {
194  const int64 penalty = routing_model_.GetDisjunctionPenalty(
195  disjunction_inactive_delta.first);
196  if (penalty != 0 && !lns_detected) {
197  const RoutingModel::DisjunctionIndex disjunction_index =
198  disjunction_inactive_delta.first;
199  const int current_inactive_nodes =
200  inactive_per_disjunction_[disjunction_index];
201  const int inactive_nodes =
202  current_inactive_nodes + disjunction_inactive_delta.second;
203  const int max_inactive_cardinality =
204  routing_model_.GetDisjunctionIndices(disjunction_index).size() -
205  routing_model_.GetDisjunctionMaxCardinality(disjunction_index);
206  // Too many inactive nodes.
207  if (inactive_nodes > max_inactive_cardinality) {
208  if (penalty < 0) {
209  // Nodes are mandatory, i.e. exactly max_cardinality nodes must be
210  // performed, so the move is not acceptable.
211  return false;
212  } else if (current_inactive_nodes <= max_inactive_cardinality) {
213  // Add penalty if there were not too many inactive nodes before the
214  // move.
215  accepted_objective_value_ =
216  CapAdd(accepted_objective_value_, penalty);
217  }
218  } else if (current_inactive_nodes > max_inactive_cardinality) {
219  // Remove penalty if there were too many inactive nodes before the
220  // move and there are not too many after the move.
221  accepted_objective_value_ =
222  CapSub(accepted_objective_value_, penalty);
223  }
224  }
225  }
226  if (lns_detected) {
227  accepted_objective_value_ = 0;
228  return true;
229  } else {
230  // Only compare to max as a cost lower bound is computed.
231  return accepted_objective_value_ <= objective_max;
232  }
233  }
234  std::string DebugString() const override { return "NodeDisjunctionFilter"; }
235  int64 GetSynchronizedObjectiveValue() const override {
236  return synchronized_objective_value_;
237  }
238  int64 GetAcceptedObjectiveValue() const override {
239  return accepted_objective_value_;
240  }
241 
242  private:
243  void OnSynchronize(const Assignment* delta) override {
244  synchronized_objective_value_ = 0;
246  i < active_per_disjunction_.size(); ++i) {
247  active_per_disjunction_[i] = 0;
248  inactive_per_disjunction_[i] = 0;
249  const std::vector<int64>& disjunction_indices =
250  routing_model_.GetDisjunctionIndices(i);
251  for (const int64 index : disjunction_indices) {
252  const bool index_synced = IsVarSynced(index);
253  if (index_synced) {
254  if (Value(index) != index) {
255  ++active_per_disjunction_[i];
256  } else {
257  ++inactive_per_disjunction_[i];
258  }
259  }
260  }
261  const int64 penalty = routing_model_.GetDisjunctionPenalty(i);
262  const int max_cardinality =
263  routing_model_.GetDisjunctionMaxCardinality(i);
264  if (inactive_per_disjunction_[i] >
265  disjunction_indices.size() - max_cardinality &&
266  penalty > 0) {
267  synchronized_objective_value_ =
268  CapAdd(synchronized_objective_value_, penalty);
269  }
270  }
271  }
272 
273  const RoutingModel& routing_model_;
274 
276  active_per_disjunction_;
278  inactive_per_disjunction_;
279  int64 synchronized_objective_value_;
280  int64 accepted_objective_value_;
281 };
282 } // namespace
283 
285  const RoutingModel& routing_model) {
286  return routing_model.solver()->RevAlloc(
287  new NodeDisjunctionFilter(routing_model));
288 }
289 
291 
292 BasePathFilter::BasePathFilter(const std::vector<IntVar*>& nexts,
293  int next_domain_size)
294  : IntVarLocalSearchFilter(nexts),
295  node_path_starts_(next_domain_size, kUnassigned),
296  paths_(nexts.size(), -1),
297  new_synchronized_unperformed_nodes_(nexts.size()),
298  new_nexts_(nexts.size(), kUnassigned),
299  touched_paths_(nexts.size()),
300  touched_path_chain_start_ends_(nexts.size(), {kUnassigned, kUnassigned}),
301  ranks_(next_domain_size, -1),
302  status_(BasePathFilter::UNKNOWN) {}
303 
305  const Assignment* deltadelta, int64 objective_min,
306  int64 objective_max) {
307  if (IsDisabled()) return true;
308  for (const int touched : delta_touched_) {
309  new_nexts_[touched] = kUnassigned;
310  }
311  delta_touched_.clear();
312  const Assignment::IntContainer& container = delta->IntVarContainer();
313  const int delta_size = container.Size();
314  delta_touched_.reserve(delta_size);
315  // Determining touched paths and their touched chain start and ends (a node is
316  // touched if it corresponds to an element of delta or that an element of
317  // delta points to it).
318  // The start and end of a touched path subchain will have remained on the same
319  // path and will correspond to the min and max ranks of touched nodes in the
320  // current assignment.
321  for (int64 touched_path : touched_paths_.PositionsSetAtLeastOnce()) {
322  touched_path_chain_start_ends_[touched_path] = {kUnassigned, kUnassigned};
323  }
324  touched_paths_.SparseClearAll();
325 
326  const auto update_touched_path_chain_start_end = [this](int64 index) {
327  const int64 start = node_path_starts_[index];
328  if (start == kUnassigned) return;
329  touched_paths_.Set(start);
330 
331  int64& chain_start = touched_path_chain_start_ends_[start].first;
332  if (chain_start == kUnassigned || ranks_[index] < ranks_[chain_start]) {
333  chain_start = index;
334  }
335 
336  int64& chain_end = touched_path_chain_start_ends_[start].second;
337  if (chain_end == kUnassigned || ranks_[index] > ranks_[chain_end]) {
338  chain_end = index;
339  }
340  };
341 
342  for (int i = 0; i < delta_size; ++i) {
343  const IntVarElement& new_element = container.Element(i);
344  IntVar* const var = new_element.Var();
346  if (FindIndex(var, &index)) {
347  if (!new_element.Bound()) {
348  // LNS detected
349  return true;
350  }
351  new_nexts_[index] = new_element.Value();
352  delta_touched_.push_back(index);
353  update_touched_path_chain_start_end(index);
354  update_touched_path_chain_start_end(new_nexts_[index]);
355  }
356  }
357  // Checking feasibility of touched paths.
358  InitializeAcceptPath();
359  bool accept = true;
360  for (const int64 touched_start : touched_paths_.PositionsSetAtLeastOnce()) {
361  const std::pair<int64, int64> start_end =
362  touched_path_chain_start_ends_[touched_start];
363  if (!AcceptPath(touched_start, start_end.first, start_end.second)) {
364  accept = false;
365  break;
366  }
367  }
368  // NOTE: FinalizeAcceptPath() is only called if all paths are accepted.
369  return accept && FinalizeAcceptPath(delta, objective_min, objective_max);
370 }
371 
372 void BasePathFilter::ComputePathStarts(std::vector<int64>* path_starts,
373  std::vector<int>* index_to_path) {
374  path_starts->clear();
375  const int nexts_size = Size();
376  index_to_path->assign(nexts_size, kUnassigned);
377  Bitset64<> has_prevs(nexts_size);
378  for (int i = 0; i < nexts_size; ++i) {
379  if (!IsVarSynced(i)) {
380  has_prevs.Set(i);
381  } else {
382  const int next = Value(i);
383  if (next < nexts_size) {
384  has_prevs.Set(next);
385  }
386  }
387  }
388  for (int i = 0; i < nexts_size; ++i) {
389  if (!has_prevs[i]) {
390  (*index_to_path)[i] = path_starts->size();
391  path_starts->push_back(i);
392  }
393  }
394 }
395 
396 bool BasePathFilter::HavePathsChanged() {
397  std::vector<int64> path_starts;
398  std::vector<int> index_to_path(Size(), kUnassigned);
399  ComputePathStarts(&path_starts, &index_to_path);
400  if (path_starts.size() != starts_.size()) {
401  return true;
402  }
403  for (int i = 0; i < path_starts.size(); ++i) {
404  if (path_starts[i] != starts_[i]) {
405  return true;
406  }
407  }
408  for (int i = 0; i < Size(); ++i) {
409  if (index_to_path[i] != paths_[i]) {
410  return true;
411  }
412  }
413  return false;
414 }
415 
416 void BasePathFilter::SynchronizeFullAssignment() {
417  // Subclasses of BasePathFilter might not propagate injected objective values
418  // so making sure it is done here (can be done again by the subclass if
419  // needed).
420  ComputePathStarts(&starts_, &paths_);
421  for (int64 index = 0; index < Size(); index++) {
422  if (IsVarSynced(index) && Value(index) == index &&
423  node_path_starts_[index] != kUnassigned) {
424  // index was performed before and is now unperformed.
425  new_synchronized_unperformed_nodes_.Set(index);
426  }
427  }
428  // Marking unactive nodes (which are not on a path).
429  node_path_starts_.assign(node_path_starts_.size(), kUnassigned);
430  // Marking nodes on a path and storing next values.
431  const int nexts_size = Size();
432  for (const int64 start : starts_) {
433  int node = start;
434  node_path_starts_[node] = start;
435  DCHECK(IsVarSynced(node));
436  int next = Value(node);
437  while (next < nexts_size) {
438  node = next;
439  node_path_starts_[node] = start;
440  DCHECK(IsVarSynced(node));
441  next = Value(node);
442  }
443  node_path_starts_[next] = start;
444  }
445  OnBeforeSynchronizePaths();
446  UpdateAllRanks();
447  OnAfterSynchronizePaths();
448 }
449 
451  if (status_ == BasePathFilter::UNKNOWN) {
452  status_ =
453  DisableFiltering() ? BasePathFilter::DISABLED : BasePathFilter::ENABLED;
454  }
455  if (IsDisabled()) return;
456  new_synchronized_unperformed_nodes_.ClearAll();
457  if (delta == nullptr || delta->Empty() || starts_.empty()) {
458  SynchronizeFullAssignment();
459  return;
460  }
461  // Subclasses of BasePathFilter might not propagate injected objective values
462  // so making sure it is done here (can be done again by the subclass if
463  // needed).
464  // This code supposes that path starts didn't change.
465  DCHECK(!absl::GetFlag(FLAGS_routing_strong_debug_checks) ||
466  !HavePathsChanged());
467  const Assignment::IntContainer& container = delta->IntVarContainer();
468  touched_paths_.SparseClearAll();
469  for (int i = 0; i < container.Size(); ++i) {
470  const IntVarElement& new_element = container.Element(i);
472  if (FindIndex(new_element.Var(), &index)) {
473  const int64 start = node_path_starts_[index];
474  if (start != kUnassigned) {
475  touched_paths_.Set(start);
476  if (Value(index) == index) {
477  // New unperformed node (its previous start isn't unassigned).
478  DCHECK_LT(index, new_nexts_.size());
479  new_synchronized_unperformed_nodes_.Set(index);
480  node_path_starts_[index] = kUnassigned;
481  }
482  }
483  }
484  }
485  OnBeforeSynchronizePaths();
486  for (const int64 touched_start : touched_paths_.PositionsSetAtLeastOnce()) {
487  int64 node = touched_start;
488  while (node < Size()) {
489  node_path_starts_[node] = touched_start;
490  node = Value(node);
491  }
492  node_path_starts_[node] = touched_start;
493  UpdatePathRanksFromStart(touched_start);
494  OnSynchronizePathFromStart(touched_start);
495  }
496  OnAfterSynchronizePaths();
497 }
498 
499 void BasePathFilter::UpdateAllRanks() {
500  for (int i = 0; i < ranks_.size(); ++i) {
501  ranks_[i] = kUnassigned;
502  }
503  for (int r = 0; r < NumPaths(); ++r) {
504  UpdatePathRanksFromStart(Start(r));
505  OnSynchronizePathFromStart(Start(r));
506  }
507 }
508 
509 void BasePathFilter::UpdatePathRanksFromStart(int start) {
510  int rank = 0;
511  int64 node = start;
512  while (node < Size()) {
513  ranks_[node] = rank;
514  rank++;
515  node = Value(node);
516  }
517  ranks_[node] = rank;
518 }
519 
520 namespace {
521 
522 class VehicleAmortizedCostFilter : public BasePathFilter {
523  public:
524  explicit VehicleAmortizedCostFilter(const RoutingModel& routing_model);
525  ~VehicleAmortizedCostFilter() override {}
526  std::string DebugString() const override {
527  return "VehicleAmortizedCostFilter";
528  }
529  int64 GetSynchronizedObjectiveValue() const override {
530  return current_vehicle_cost_;
531  }
532  int64 GetAcceptedObjectiveValue() const override {
533  return delta_vehicle_cost_;
534  }
535 
536  private:
537  void OnSynchronizePathFromStart(int64 start) override;
538  void OnAfterSynchronizePaths() override;
539  void InitializeAcceptPath() override;
540  bool AcceptPath(int64 path_start, int64 chain_start,
541  int64 chain_end) override;
542  bool FinalizeAcceptPath(const Assignment* delta, int64 objective_min,
543  int64 objective_max) override;
544 
545  int64 current_vehicle_cost_;
546  int64 delta_vehicle_cost_;
547  std::vector<int> current_route_lengths_;
548  std::vector<int64> start_to_end_;
549  std::vector<int> start_to_vehicle_;
550  std::vector<int64> vehicle_to_start_;
551  const std::vector<int64>& linear_cost_factor_of_vehicle_;
552  const std::vector<int64>& quadratic_cost_factor_of_vehicle_;
553 };
554 
555 VehicleAmortizedCostFilter::VehicleAmortizedCostFilter(
556  const RoutingModel& routing_model)
557  : BasePathFilter(routing_model.Nexts(),
558  routing_model.Size() + routing_model.vehicles()),
559  current_vehicle_cost_(0),
560  delta_vehicle_cost_(0),
561  current_route_lengths_(Size(), -1),
562  linear_cost_factor_of_vehicle_(
563  routing_model.GetAmortizedLinearCostFactorOfVehicles()),
564  quadratic_cost_factor_of_vehicle_(
565  routing_model.GetAmortizedQuadraticCostFactorOfVehicles()) {
566  start_to_end_.resize(Size(), -1);
567  start_to_vehicle_.resize(Size(), -1);
568  vehicle_to_start_.resize(routing_model.vehicles());
569  for (int v = 0; v < routing_model.vehicles(); v++) {
570  const int64 start = routing_model.Start(v);
571  start_to_vehicle_[start] = v;
572  start_to_end_[start] = routing_model.End(v);
573  vehicle_to_start_[v] = start;
574  }
575 }
576 
577 void VehicleAmortizedCostFilter::OnSynchronizePathFromStart(int64 start) {
578  const int64 end = start_to_end_[start];
579  CHECK_GE(end, 0);
580  const int route_length = Rank(end) - 1;
581  CHECK_GE(route_length, 0);
582  current_route_lengths_[start] = route_length;
583 }
584 
585 void VehicleAmortizedCostFilter::OnAfterSynchronizePaths() {
586  current_vehicle_cost_ = 0;
587  for (int vehicle = 0; vehicle < vehicle_to_start_.size(); vehicle++) {
588  const int64 start = vehicle_to_start_[vehicle];
589  DCHECK_EQ(vehicle, start_to_vehicle_[start]);
590 
591  const int route_length = current_route_lengths_[start];
592  DCHECK_GE(route_length, 0);
593 
594  if (route_length == 0) {
595  // The path is empty.
596  continue;
597  }
598 
599  const int64 linear_cost_factor = linear_cost_factor_of_vehicle_[vehicle];
600  const int64 route_length_cost =
601  CapProd(quadratic_cost_factor_of_vehicle_[vehicle],
602  route_length * route_length);
603 
604  current_vehicle_cost_ = CapAdd(
605  current_vehicle_cost_, CapSub(linear_cost_factor, route_length_cost));
606  }
607 }
608 
609 void VehicleAmortizedCostFilter::InitializeAcceptPath() {
610  delta_vehicle_cost_ = current_vehicle_cost_;
611 }
612 
613 bool VehicleAmortizedCostFilter::AcceptPath(int64 path_start, int64 chain_start,
614  int64 chain_end) {
615  // Number of nodes previously between chain_start and chain_end
616  const int previous_chain_nodes = Rank(chain_end) - 1 - Rank(chain_start);
617  CHECK_GE(previous_chain_nodes, 0);
618  int new_chain_nodes = 0;
619  int64 node = GetNext(chain_start);
620  while (node != chain_end) {
621  new_chain_nodes++;
622  node = GetNext(node);
623  }
624 
625  const int previous_route_length = current_route_lengths_[path_start];
626  CHECK_GE(previous_route_length, 0);
627  const int new_route_length =
628  previous_route_length - previous_chain_nodes + new_chain_nodes;
629 
630  const int vehicle = start_to_vehicle_[path_start];
631  CHECK_GE(vehicle, 0);
632  DCHECK_EQ(path_start, vehicle_to_start_[vehicle]);
633 
634  // Update the cost related to used vehicles.
635  // TODO(user): Handle possible overflows.
636  if (previous_route_length == 0) {
637  // The route was empty before, it is no longer the case (changed path).
638  CHECK_GT(new_route_length, 0);
639  delta_vehicle_cost_ =
640  CapAdd(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
641  } else if (new_route_length == 0) {
642  // The route is now empty.
643  delta_vehicle_cost_ =
644  CapSub(delta_vehicle_cost_, linear_cost_factor_of_vehicle_[vehicle]);
645  }
646 
647  // Update the cost related to the sum of the squares of the route lengths.
648  const int64 quadratic_cost_factor =
649  quadratic_cost_factor_of_vehicle_[vehicle];
650  delta_vehicle_cost_ =
651  CapAdd(delta_vehicle_cost_,
652  CapProd(quadratic_cost_factor,
653  previous_route_length * previous_route_length));
654  delta_vehicle_cost_ = CapSub(
655  delta_vehicle_cost_,
656  CapProd(quadratic_cost_factor, new_route_length * new_route_length));
657 
658  return true;
659 }
660 
661 bool VehicleAmortizedCostFilter::FinalizeAcceptPath(const Assignment* delta,
662  int64 objective_min,
663  int64 objective_max) {
664  return delta_vehicle_cost_ <= objective_max;
665 }
666 
667 } // namespace
668 
670  const RoutingModel& routing_model) {
671  return routing_model.solver()->RevAlloc(
672  new VehicleAmortizedCostFilter(routing_model));
673 }
674 
675 namespace {
676 
677 class TypeRegulationsFilter : public BasePathFilter {
678  public:
679  explicit TypeRegulationsFilter(const RoutingModel& model);
680  ~TypeRegulationsFilter() override {}
681  std::string DebugString() const override { return "TypeRegulationsFilter"; }
682 
683  private:
684  void OnSynchronizePathFromStart(int64 start) override;
685  bool AcceptPath(int64 path_start, int64 chain_start,
686  int64 chain_end) override;
687 
688  bool HardIncompatibilitiesRespected(int vehicle, int64 chain_start,
689  int64 chain_end);
690 
691  const RoutingModel& routing_model_;
692  std::vector<int> start_to_vehicle_;
693  // The following vector is used to keep track of the type counts for hard
694  // incompatibilities.
695  std::vector<std::vector<int>> hard_incompatibility_type_counts_per_vehicle_;
696  // Used to verify the temporal incompatibilities and requirements.
697  TypeIncompatibilityChecker temporal_incompatibility_checker_;
698  TypeRequirementChecker requirement_checker_;
699 };
700 
701 TypeRegulationsFilter::TypeRegulationsFilter(const RoutingModel& model)
702  : BasePathFilter(model.Nexts(), model.Size() + model.vehicles()),
703  routing_model_(model),
704  start_to_vehicle_(model.Size(), -1),
705  temporal_incompatibility_checker_(model,
706  /*check_hard_incompatibilities*/ false),
707  requirement_checker_(model) {
708  const int num_vehicles = model.vehicles();
709  const bool has_hard_type_incompatibilities =
710  model.HasHardTypeIncompatibilities();
711  if (has_hard_type_incompatibilities) {
712  hard_incompatibility_type_counts_per_vehicle_.resize(num_vehicles);
713  }
714  const int num_visit_types = model.GetNumberOfVisitTypes();
715  for (int vehicle = 0; vehicle < num_vehicles; vehicle++) {
716  const int64 start = model.Start(vehicle);
717  start_to_vehicle_[start] = vehicle;
718  if (has_hard_type_incompatibilities) {
719  hard_incompatibility_type_counts_per_vehicle_[vehicle].resize(
720  num_visit_types, 0);
721  }
722  }
723 }
724 
725 void TypeRegulationsFilter::OnSynchronizePathFromStart(int64 start) {
726  if (!routing_model_.HasHardTypeIncompatibilities()) return;
727 
728  const int vehicle = start_to_vehicle_[start];
729  CHECK_GE(vehicle, 0);
730  std::vector<int>& type_counts =
731  hard_incompatibility_type_counts_per_vehicle_[vehicle];
732  std::fill(type_counts.begin(), type_counts.end(), 0);
733  const int num_types = type_counts.size();
734 
735  int64 node = start;
736  while (node < Size()) {
737  DCHECK(IsVarSynced(node));
738  const int type = routing_model_.GetVisitType(node);
739  if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
740  RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
741  CHECK_LT(type, num_types);
742  type_counts[type]++;
743  }
744  node = Value(node);
745  }
746 }
747 
748 bool TypeRegulationsFilter::HardIncompatibilitiesRespected(int vehicle,
749  int64 chain_start,
750  int64 chain_end) {
751  if (!routing_model_.HasHardTypeIncompatibilities()) return true;
752 
753  const std::vector<int>& previous_type_counts =
754  hard_incompatibility_type_counts_per_vehicle_[vehicle];
755 
756  absl::flat_hash_map</*type*/ int, /*new_count*/ int> new_type_counts;
757  absl::flat_hash_set<int> types_to_check;
758 
759  // Go through the new nodes on the path and increment their type counts.
760  int64 node = GetNext(chain_start);
761  while (node != chain_end) {
762  const int type = routing_model_.GetVisitType(node);
763  if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
764  RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
765  DCHECK_LT(type, previous_type_counts.size());
766  int& type_count = gtl::LookupOrInsert(&new_type_counts, type,
767  previous_type_counts[type]);
768  if (type_count++ == 0) {
769  // New type on the route, mark to check its incompatibilities.
770  types_to_check.insert(type);
771  }
772  }
773  node = GetNext(node);
774  }
775 
776  // Update new_type_counts by decrementing the occurrence of the types of the
777  // nodes no longer on the route.
778  node = Value(chain_start);
779  while (node != chain_end) {
780  const int type = routing_model_.GetVisitType(node);
781  if (type >= 0 && routing_model_.GetVisitTypePolicy(node) !=
782  RoutingModel::ADDED_TYPE_REMOVED_FROM_VEHICLE) {
783  DCHECK_LT(type, previous_type_counts.size());
784  int& type_count = gtl::LookupOrInsert(&new_type_counts, type,
785  previous_type_counts[type]);
786  CHECK_GE(type_count, 1);
787  type_count--;
788  }
789  node = Value(node);
790  }
791 
792  // Check the incompatibilities for types in types_to_check.
793  for (int type : types_to_check) {
794  for (int incompatible_type :
795  routing_model_.GetHardTypeIncompatibilitiesOfType(type)) {
796  if (gtl::FindWithDefault(new_type_counts, incompatible_type,
797  previous_type_counts[incompatible_type]) > 0) {
798  return false;
799  }
800  }
801  }
802  return true;
803 }
804 
805 bool TypeRegulationsFilter::AcceptPath(int64 path_start, int64 chain_start,
806  int64 chain_end) {
807  const int vehicle = start_to_vehicle_[path_start];
808  CHECK_GE(vehicle, 0);
809  const auto next_accessor = [this](int64 node) { return GetNext(node); };
810  return HardIncompatibilitiesRespected(vehicle, chain_start, chain_end) &&
811  temporal_incompatibility_checker_.CheckVehicle(vehicle,
812  next_accessor) &&
813  requirement_checker_.CheckVehicle(vehicle, next_accessor);
814 }
815 
816 } // namespace
817 
819  const RoutingModel& routing_model) {
820  return routing_model.solver()->RevAlloc(
821  new TypeRegulationsFilter(routing_model));
822 }
823 
824 namespace {
825 
826 // ChainCumul filter. Version of dimension path filter which is O(delta) rather
827 // than O(length of touched paths). Currently only supports dimensions without
828 // costs (global and local span cost, soft bounds) and with unconstrained
829 // cumul variables except overall capacity and cumul variables of path ends.
830 
831 class ChainCumulFilter : public BasePathFilter {
832  public:
833  ChainCumulFilter(const RoutingModel& routing_model,
834  const RoutingDimension& dimension);
835  ~ChainCumulFilter() override {}
836  std::string DebugString() const override {
837  return "ChainCumulFilter(" + name_ + ")";
838  }
839 
840  private:
841  void OnSynchronizePathFromStart(int64 start) override;
842  bool AcceptPath(int64 path_start, int64 chain_start,
843  int64 chain_end) override;
844 
845  const std::vector<IntVar*> cumuls_;
846  std::vector<int64> start_to_vehicle_;
847  std::vector<int64> start_to_end_;
848  std::vector<const RoutingModel::TransitCallback2*> evaluators_;
849  const std::vector<int64> vehicle_capacities_;
850  std::vector<int64> current_path_cumul_mins_;
851  std::vector<int64> current_max_of_path_end_cumul_mins_;
852  std::vector<int64> old_nexts_;
853  std::vector<int> old_vehicles_;
854  std::vector<int64> current_transits_;
855  const std::string name_;
856 };
857 
858 ChainCumulFilter::ChainCumulFilter(const RoutingModel& routing_model,
859  const RoutingDimension& dimension)
860  : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
861  cumuls_(dimension.cumuls()),
862  evaluators_(routing_model.vehicles(), nullptr),
863  vehicle_capacities_(dimension.vehicle_capacities()),
864  current_path_cumul_mins_(dimension.cumuls().size(), 0),
865  current_max_of_path_end_cumul_mins_(dimension.cumuls().size(), 0),
866  old_nexts_(routing_model.Size(), kUnassigned),
867  old_vehicles_(routing_model.Size(), kUnassigned),
868  current_transits_(routing_model.Size(), 0),
869  name_(dimension.name()) {
870  start_to_vehicle_.resize(Size(), -1);
871  start_to_end_.resize(Size(), -1);
872  for (int i = 0; i < routing_model.vehicles(); ++i) {
873  start_to_vehicle_[routing_model.Start(i)] = i;
874  start_to_end_[routing_model.Start(i)] = routing_model.End(i);
875  evaluators_[i] = &dimension.transit_evaluator(i);
876  }
877 }
878 
879 // On synchronization, maintain "propagated" cumul mins and max level of cumul
880 // from each node to the end of the path; to be used by AcceptPath to
881 // incrementally check feasibility.
882 void ChainCumulFilter::OnSynchronizePathFromStart(int64 start) {
883  const int vehicle = start_to_vehicle_[start];
884  std::vector<int64> path_nodes;
885  int64 node = start;
886  int64 cumul = cumuls_[node]->Min();
887  while (node < Size()) {
888  path_nodes.push_back(node);
889  current_path_cumul_mins_[node] = cumul;
890  const int64 next = Value(node);
891  if (next != old_nexts_[node] || vehicle != old_vehicles_[node]) {
892  old_nexts_[node] = next;
893  old_vehicles_[node] = vehicle;
894  current_transits_[node] = (*evaluators_[vehicle])(node, next);
895  }
896  cumul = CapAdd(cumul, current_transits_[node]);
897  cumul = std::max(cumuls_[next]->Min(), cumul);
898  node = next;
899  }
900  path_nodes.push_back(node);
901  current_path_cumul_mins_[node] = cumul;
902  int64 max_cumuls = cumul;
903  for (int i = path_nodes.size() - 1; i >= 0; --i) {
904  const int64 node = path_nodes[i];
905  max_cumuls = std::max(max_cumuls, current_path_cumul_mins_[node]);
906  current_max_of_path_end_cumul_mins_[node] = max_cumuls;
907  }
908 }
909 
910 // The complexity of the method is O(size of chain (chain_start...chain_end).
911 bool ChainCumulFilter::AcceptPath(int64 path_start, int64 chain_start,
912  int64 chain_end) {
913  const int vehicle = start_to_vehicle_[path_start];
914  const int64 capacity = vehicle_capacities_[vehicle];
915  int64 node = chain_start;
916  int64 cumul = current_path_cumul_mins_[node];
917  while (node != chain_end) {
918  const int64 next = GetNext(node);
919  if (IsVarSynced(node) && next == Value(node) &&
920  vehicle == old_vehicles_[node]) {
921  cumul = CapAdd(cumul, current_transits_[node]);
922  } else {
923  cumul = CapAdd(cumul, (*evaluators_[vehicle])(node, next));
924  }
925  cumul = std::max(cumuls_[next]->Min(), cumul);
926  if (cumul > capacity) return false;
927  node = next;
928  }
929  const int64 end = start_to_end_[path_start];
930  const int64 end_cumul_delta =
931  CapSub(current_path_cumul_mins_[end], current_path_cumul_mins_[node]);
932  const int64 after_chain_cumul_delta =
933  CapSub(current_max_of_path_end_cumul_mins_[node],
934  current_path_cumul_mins_[node]);
935  return CapAdd(cumul, after_chain_cumul_delta) <= capacity &&
936  CapAdd(cumul, end_cumul_delta) <= cumuls_[end]->Max();
937 }
938 
939 // PathCumul filter.
940 
941 class PathCumulFilter : public BasePathFilter {
942  public:
943  PathCumulFilter(const RoutingModel& routing_model,
944  const RoutingDimension& dimension,
945  const RoutingSearchParameters& parameters,
946  bool propagate_own_objective_value,
947  bool filter_objective_cost, bool can_use_lp);
948  ~PathCumulFilter() override {}
949  std::string DebugString() const override {
950  return "PathCumulFilter(" + name_ + ")";
951  }
952  int64 GetSynchronizedObjectiveValue() const override {
953  return propagate_own_objective_value_ ? synchronized_objective_value_ : 0;
954  }
955  int64 GetAcceptedObjectiveValue() const override {
956  return propagate_own_objective_value_ ? accepted_objective_value_ : 0;
957  }
958 
959  private:
960  // This structure stores the "best" path cumul value for a solution, the path
961  // supporting this value, and the corresponding path cumul values for all
962  // paths.
963  struct SupportedPathCumul {
964  SupportedPathCumul() : cumul_value(0), cumul_value_support(0) {}
967  std::vector<int64> path_values;
968  };
969 
970  struct SoftBound {
971  SoftBound() : bound(-1), coefficient(0) {}
974  };
975 
976  // This class caches transit values between nodes of paths. Transit and path
977  // nodes are to be added in the order in which they appear on a path.
978  class PathTransits {
979  public:
980  void Clear() {
981  paths_.clear();
982  transits_.clear();
983  }
984  void ClearPath(int path) {
985  paths_[path].clear();
986  transits_[path].clear();
987  }
988  int AddPaths(int num_paths) {
989  const int first_path = paths_.size();
990  paths_.resize(first_path + num_paths);
991  transits_.resize(first_path + num_paths);
992  return first_path;
993  }
994  void ReserveTransits(int path, int number_of_route_arcs) {
995  transits_[path].reserve(number_of_route_arcs);
996  paths_[path].reserve(number_of_route_arcs + 1);
997  }
998  // Stores the transit between node and next on path. For a given non-empty
999  // path, node must correspond to next in the previous call to PushTransit.
1000  void PushTransit(int path, int node, int next, int64 transit) {
1001  transits_[path].push_back(transit);
1002  if (paths_[path].empty()) {
1003  paths_[path].push_back(node);
1004  }
1005  DCHECK_EQ(paths_[path].back(), node);
1006  paths_[path].push_back(next);
1007  }
1008  int NumPaths() const { return paths_.size(); }
1009  int PathSize(int path) const { return paths_[path].size(); }
1010  int Node(int path, int position) const { return paths_[path][position]; }
1011  int64 Transit(int path, int position) const {
1012  return transits_[path][position];
1013  }
1014 
1015  private:
1016  // paths_[r][i] is the ith node on path r.
1017  std::vector<std::vector<int64>> paths_;
1018  // transits_[r][i] is the transit value between nodes path_[i] and
1019  // path_[i+1] on path r.
1020  std::vector<std::vector<int64>> transits_;
1021  };
1022 
1023  void InitializeAcceptPath() override {
1024  cumul_cost_delta_ = total_current_cumul_cost_value_;
1025  node_with_precedence_to_delta_min_max_cumuls_.clear();
1026  // Cleaning up for the new delta.
1027  delta_max_end_cumul_ = kint64min;
1028  delta_paths_.clear();
1029  delta_path_transits_.Clear();
1030  lns_detected_ = false;
1031  delta_nodes_with_precedences_and_changed_cumul_.ClearAll();
1032  }
1033  bool AcceptPath(int64 path_start, int64 chain_start,
1034  int64 chain_end) override;
1035  bool FinalizeAcceptPath(const Assignment* delta, int64 objective_min,
1036  int64 objective_max) override;
1037  void OnBeforeSynchronizePaths() override;
1038 
1039  bool FilterSpanCost() const { return global_span_cost_coefficient_ != 0; }
1040 
1041  bool FilterSlackCost() const {
1042  return has_nonzero_vehicle_span_cost_coefficients_ ||
1043  has_vehicle_span_upper_bounds_;
1044  }
1045 
1046  bool FilterBreakCost(int vehicle) const {
1047  return dimension_.HasBreakConstraints() &&
1048  !dimension_.GetBreakIntervalsOfVehicle(vehicle).empty();
1049  }
1050 
1051  bool FilterCumulSoftBounds() const { return !cumul_soft_bounds_.empty(); }
1052 
1053  int64 GetCumulSoftCost(int64 node, int64 cumul_value) const;
1054 
1055  bool FilterCumulPiecewiseLinearCosts() const {
1056  return !cumul_piecewise_linear_costs_.empty();
1057  }
1058 
1059  bool FilterWithDimensionCumulOptimizerForVehicle(int vehicle) const {
1060  if (!can_use_lp_ || FilterCumulPiecewiseLinearCosts()) {
1061  return false;
1062  }
1063 
1064  int num_linear_constraints = 0;
1065  if (dimension_.GetSpanCostCoefficientForVehicle(vehicle) > 0)
1066  ++num_linear_constraints;
1067  if (FilterSoftSpanCost(vehicle)) ++num_linear_constraints;
1068  if (FilterCumulSoftLowerBounds()) ++num_linear_constraints;
1069  if (FilterCumulSoftBounds()) ++num_linear_constraints;
1070  if (vehicle_span_upper_bounds_[vehicle] < kint64max)
1071  ++num_linear_constraints;
1072  const bool has_breaks = FilterBreakCost(vehicle);
1073  if (has_breaks) ++num_linear_constraints;
1074 
1075  // The DimensionCumulOptimizer is used to compute a more precise value of
1076  // the cost related to the cumul values (soft bounds and span costs).
1077  // It is also used to garantee feasibility with complex mixes of constraints
1078  // and in particular in the presence of break requests along other
1079  // constraints.
1080  // Therefore, without breaks, we only use the optimizer when the costs are
1081  // actually used to filter the solutions, i.e. when filter_objective_cost_
1082  // is true.
1083  return num_linear_constraints >= 2 &&
1084  (has_breaks || filter_objective_cost_);
1085  }
1086 
1087  bool FilterDimensionForbiddenIntervals() const {
1088  for (const SortedDisjointIntervalList& intervals :
1089  dimension_.forbidden_intervals()) {
1090  // TODO(user): Change the following test to check intervals within
1091  // the domain of the corresponding variables.
1092  if (intervals.NumIntervals() > 0) {
1093  return true;
1094  }
1095  }
1096  return false;
1097  }
1098 
1099  int64 GetCumulPiecewiseLinearCost(int64 node, int64 cumul_value) const;
1100 
1101  bool FilterCumulSoftLowerBounds() const {
1102  return !cumul_soft_lower_bounds_.empty();
1103  }
1104 
1105  bool FilterPrecedences() const { return !node_index_to_precedences_.empty(); }
1106 
1107  bool FilterSoftSpanCost() const {
1108  return dimension_.HasSoftSpanUpperBounds();
1109  }
1110  bool FilterSoftSpanCost(int vehicle) const {
1111  return dimension_.HasSoftSpanUpperBounds() &&
1112  dimension_.GetSoftSpanUpperBoundForVehicle(vehicle).cost > 0;
1113  }
1114  bool FilterSoftSpanQuadraticCost() const {
1115  return dimension_.HasQuadraticCostSoftSpanUpperBounds();
1116  }
1117  bool FilterSoftSpanQuadraticCost(int vehicle) const {
1118  return dimension_.HasQuadraticCostSoftSpanUpperBounds() &&
1119  dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle)
1120  .cost > 0;
1121  }
1122 
1123  int64 GetCumulSoftLowerBoundCost(int64 node, int64 cumul_value) const;
1124 
1125  int64 GetPathCumulSoftLowerBoundCost(const PathTransits& path_transits,
1126  int path) const;
1127 
1128  void InitializeSupportedPathCumul(SupportedPathCumul* supported_cumul,
1129  int64 default_value);
1130 
1131  // Given the vector of minimum cumuls on the path, determines if the pickup to
1132  // delivery limits for this dimension (if there are any) can be respected by
1133  // this path.
1134  // Returns true if for every pickup/delivery nodes visited on this path,
1135  // min_cumul_value(delivery) - max_cumul_value(pickup) is less than the limit
1136  // set for this pickup to delivery.
1137  // TODO(user): Verify if we should filter the pickup/delivery limits using
1138  // the LP, for a perfect filtering.
1139  bool PickupToDeliveryLimitsRespected(
1140  const PathTransits& path_transits, int path,
1141  const std::vector<int64>& min_path_cumuls) const;
1142 
1143  // Computes the maximum cumul value of nodes along the path using
1144  // [current|delta]_path_transits_, and stores the min/max cumul
1145  // related to each node in the corresponding vector
1146  // [current|delta]_[min|max]_node_cumuls_.
1147  // The boolean is_delta indicates if the computations should take place on the
1148  // "delta" or "current" members. When true, the nodes for which the min/max
1149  // cumul has changed from the current value are marked in
1150  // delta_nodes_with_precedences_and_changed_cumul_.
1151  void StoreMinMaxCumulOfNodesOnPath(int path,
1152  const std::vector<int64>& min_path_cumuls,
1153  bool is_delta);
1154 
1155  // Compute the max start cumul value for a given path and a given minimal end
1156  // cumul value.
1157  // NOTE: Since this function is used to compute a lower bound on the span of
1158  // the routes, we don't "jump" over the forbidden intervals with this min end
1159  // cumul value. We do however concurrently compute the max possible start
1160  // given the max end cumul, for which we can "jump" over forbidden intervals,
1161  // and return the minimum of the two.
1162  int64 ComputePathMaxStartFromEndCumul(const PathTransits& path_transits,
1163  int path, int64 path_start,
1164  int64 min_end_cumul) const;
1165 
1166  const RoutingModel& routing_model_;
1167  const RoutingDimension& dimension_;
1168  const std::vector<IntVar*> cumuls_;
1169  const std::vector<IntVar*> slacks_;
1170  std::vector<int64> start_to_vehicle_;
1171  std::vector<const RoutingModel::TransitCallback2*> evaluators_;
1172  std::vector<int64> vehicle_span_upper_bounds_;
1173  bool has_vehicle_span_upper_bounds_;
1174  int64 total_current_cumul_cost_value_;
1175  int64 synchronized_objective_value_;
1176  int64 accepted_objective_value_;
1177  // Map between paths and path soft cumul bound costs. The paths are indexed
1178  // by the index of the start node of the path.
1179  absl::flat_hash_map<int64, int64> current_cumul_cost_values_;
1180  int64 cumul_cost_delta_;
1181  // Cumul cost values for paths in delta, indexed by vehicle.
1182  std::vector<int64> delta_path_cumul_cost_values_;
1183  const int64 global_span_cost_coefficient_;
1184  std::vector<SoftBound> cumul_soft_bounds_;
1185  std::vector<SoftBound> cumul_soft_lower_bounds_;
1186  std::vector<const PiecewiseLinearFunction*> cumul_piecewise_linear_costs_;
1187  std::vector<int64> vehicle_span_cost_coefficients_;
1188  bool has_nonzero_vehicle_span_cost_coefficients_;
1189  const std::vector<int64> vehicle_capacities_;
1190  // node_index_to_precedences_[node_index] contains all NodePrecedence elements
1191  // with node_index as either "first_node" or "second_node".
1192  // This vector is empty if there are no precedences on the dimension_.
1193  std::vector<std::vector<RoutingDimension::NodePrecedence>>
1194  node_index_to_precedences_;
1195  // Data reflecting information on paths and cumul variables for the solution
1196  // to which the filter was synchronized.
1197  SupportedPathCumul current_min_start_;
1198  SupportedPathCumul current_max_end_;
1199  PathTransits current_path_transits_;
1200  // Current min/max cumul values, indexed by node.
1201  std::vector<std::pair<int64, int64>> current_min_max_node_cumuls_;
1202  // Data reflecting information on paths and cumul variables for the "delta"
1203  // solution (aka neighbor solution) being examined.
1204  PathTransits delta_path_transits_;
1205  int64 delta_max_end_cumul_;
1206  SparseBitset<int64> delta_nodes_with_precedences_and_changed_cumul_;
1207  absl::flat_hash_map<int64, std::pair<int64, int64>>
1208  node_with_precedence_to_delta_min_max_cumuls_;
1209  // Note: small_ordered_set only support non-hash sets.
1211  const std::string name_;
1212 
1213  LocalDimensionCumulOptimizer* optimizer_;
1214  std::unique_ptr<LocalDimensionCumulOptimizer> internal_optimizer_;
1215  LocalDimensionCumulOptimizer* mp_optimizer_;
1216  std::unique_ptr<LocalDimensionCumulOptimizer> internal_mp_optimizer_;
1217  const bool filter_objective_cost_;
1218  // This boolean indicates if the LP optimizer can be used if necessary to
1219  // optimize the dimension cumuls, and is only used for testing purposes.
1220  const bool can_use_lp_;
1221  const bool propagate_own_objective_value_;
1222 
1223  // Used to do span lower bounding in presence of vehicle breaks.
1224  DisjunctivePropagator disjunctive_propagator_;
1225  DisjunctivePropagator::Tasks tasks_;
1226  TravelBounds travel_bounds_;
1227  std::vector<int64> current_path_;
1228 
1229  bool lns_detected_;
1230 };
1231 
1232 PathCumulFilter::PathCumulFilter(const RoutingModel& routing_model,
1233  const RoutingDimension& dimension,
1234  const RoutingSearchParameters& parameters,
1235  bool propagate_own_objective_value,
1236  bool filter_objective_cost, bool can_use_lp)
1237  : BasePathFilter(routing_model.Nexts(), dimension.cumuls().size()),
1238  routing_model_(routing_model),
1239  dimension_(dimension),
1240  cumuls_(dimension.cumuls()),
1241  slacks_(dimension.slacks()),
1242  evaluators_(routing_model.vehicles(), nullptr),
1243  vehicle_span_upper_bounds_(dimension.vehicle_span_upper_bounds()),
1244  has_vehicle_span_upper_bounds_(false),
1245  total_current_cumul_cost_value_(0),
1246  synchronized_objective_value_(0),
1247  accepted_objective_value_(0),
1248  current_cumul_cost_values_(),
1249  cumul_cost_delta_(0),
1250  delta_path_cumul_cost_values_(routing_model.vehicles(), kint64min),
1251  global_span_cost_coefficient_(dimension.global_span_cost_coefficient()),
1252  vehicle_span_cost_coefficients_(
1253  dimension.vehicle_span_cost_coefficients()),
1254  has_nonzero_vehicle_span_cost_coefficients_(false),
1255  vehicle_capacities_(dimension.vehicle_capacities()),
1256  delta_max_end_cumul_(0),
1257  delta_nodes_with_precedences_and_changed_cumul_(routing_model.Size()),
1258  name_(dimension.name()),
1259  optimizer_(routing_model.GetMutableLocalCumulOptimizer(dimension)),
1260  mp_optimizer_(routing_model.GetMutableLocalCumulMPOptimizer(dimension)),
1261  filter_objective_cost_(filter_objective_cost),
1262  can_use_lp_(can_use_lp),
1263  propagate_own_objective_value_(propagate_own_objective_value),
1264  lns_detected_(false) {
1265  for (const int64 upper_bound : vehicle_span_upper_bounds_) {
1266  if (upper_bound != kint64max) {
1267  has_vehicle_span_upper_bounds_ = true;
1268  break;
1269  }
1270  }
1271  for (const int64 coefficient : vehicle_span_cost_coefficients_) {
1272  if (coefficient != 0) {
1273  has_nonzero_vehicle_span_cost_coefficients_ = true;
1274  break;
1275  }
1276  }
1277  cumul_soft_bounds_.resize(cumuls_.size());
1278  cumul_soft_lower_bounds_.resize(cumuls_.size());
1279  cumul_piecewise_linear_costs_.resize(cumuls_.size());
1280  bool has_cumul_soft_bounds = false;
1281  bool has_cumul_soft_lower_bounds = false;
1282  bool has_cumul_piecewise_linear_costs = false;
1283  bool has_cumul_hard_bounds = false;
1284  for (const IntVar* const slack : slacks_) {
1285  if (slack->Min() > 0) {
1286  has_cumul_hard_bounds = true;
1287  break;
1288  }
1289  }
1290  for (int i = 0; i < cumuls_.size(); ++i) {
1291  if (dimension.HasCumulVarSoftUpperBound(i)) {
1292  has_cumul_soft_bounds = true;
1293  cumul_soft_bounds_[i].bound = dimension.GetCumulVarSoftUpperBound(i);
1294  cumul_soft_bounds_[i].coefficient =
1295  dimension.GetCumulVarSoftUpperBoundCoefficient(i);
1296  }
1297  if (dimension.HasCumulVarSoftLowerBound(i)) {
1298  has_cumul_soft_lower_bounds = true;
1299  cumul_soft_lower_bounds_[i].bound =
1300  dimension.GetCumulVarSoftLowerBound(i);
1301  cumul_soft_lower_bounds_[i].coefficient =
1302  dimension.GetCumulVarSoftLowerBoundCoefficient(i);
1303  }
1304  if (dimension.HasCumulVarPiecewiseLinearCost(i)) {
1305  has_cumul_piecewise_linear_costs = true;
1306  cumul_piecewise_linear_costs_[i] =
1307  dimension.GetCumulVarPiecewiseLinearCost(i);
1308  }
1309  IntVar* const cumul_var = cumuls_[i];
1310  if (cumul_var->Min() > 0 || cumul_var->Max() < kint64max) {
1311  has_cumul_hard_bounds = true;
1312  }
1313  }
1314  if (!has_cumul_soft_bounds) {
1315  cumul_soft_bounds_.clear();
1316  }
1317  if (!has_cumul_soft_lower_bounds) {
1318  cumul_soft_lower_bounds_.clear();
1319  }
1320  if (!has_cumul_piecewise_linear_costs) {
1321  cumul_piecewise_linear_costs_.clear();
1322  }
1323  if (!has_cumul_hard_bounds) {
1324  // Slacks don't need to be constrained if the cumuls don't have hard bounds;
1325  // therefore we can ignore the vehicle span cost coefficient (note that the
1326  // transit part is already handled by the arc cost filters).
1327  // This doesn't concern the global span filter though.
1328  vehicle_span_cost_coefficients_.assign(routing_model.vehicles(), 0);
1329  has_nonzero_vehicle_span_cost_coefficients_ = false;
1330  }
1331  start_to_vehicle_.resize(Size(), -1);
1332  for (int i = 0; i < routing_model.vehicles(); ++i) {
1333  start_to_vehicle_[routing_model.Start(i)] = i;
1334  evaluators_[i] = &dimension.transit_evaluator(i);
1335  }
1336 
1337  const std::vector<RoutingDimension::NodePrecedence>& node_precedences =
1338  dimension.GetNodePrecedences();
1339  if (!node_precedences.empty()) {
1340  current_min_max_node_cumuls_.resize(cumuls_.size(), {-1, -1});
1341  node_index_to_precedences_.resize(cumuls_.size());
1342  for (const auto& node_precedence : node_precedences) {
1343  node_index_to_precedences_[node_precedence.first_node].push_back(
1344  node_precedence);
1345  node_index_to_precedences_[node_precedence.second_node].push_back(
1346  node_precedence);
1347  }
1348  }
1349  // NOTE(user): The model's local optimizer for this dimension could be
1350  // null because the finalizer is using a global optimizer, so we create a
1351  // separate optimizer for the PathCumulFilter if we need it.
1352  if (can_use_lp_ && optimizer_ == nullptr) {
1353  DCHECK(mp_optimizer_ == nullptr);
1354  for (int vehicle = 0; vehicle < routing_model.vehicles(); vehicle++) {
1355  if (!FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1356  continue;
1357  }
1358  if (optimizer_ == nullptr) {
1359  // NOTE: The optimizer_ might have already been set in the for loop,
1360  // since we continue scanning vehicles in case one of them needs the
1361  // the mp_optimizer_ for break constraints.
1362  internal_optimizer_ = absl::make_unique<LocalDimensionCumulOptimizer>(
1363  &dimension, parameters.continuous_scheduling_solver());
1364  optimizer_ = internal_optimizer_.get();
1365  }
1366  if (FilterBreakCost(vehicle) || FilterDimensionForbiddenIntervals()) {
1367  internal_mp_optimizer_ =
1368  absl::make_unique<LocalDimensionCumulOptimizer>(
1369  &dimension, parameters.mixed_integer_scheduling_solver());
1370  mp_optimizer_ = internal_mp_optimizer_.get();
1371  break;
1372  }
1373  }
1374  }
1375 }
1376 
1377 int64 PathCumulFilter::GetCumulSoftCost(int64 node, int64 cumul_value) const {
1378  if (node < cumul_soft_bounds_.size()) {
1379  const int64 bound = cumul_soft_bounds_[node].bound;
1380  const int64 coefficient = cumul_soft_bounds_[node].coefficient;
1381  if (coefficient > 0 && bound < cumul_value) {
1383  }
1384  }
1385  return 0;
1386 }
1387 
1388 int64 PathCumulFilter::GetCumulPiecewiseLinearCost(int64 node,
1389  int64 cumul_value) const {
1390  if (node < cumul_piecewise_linear_costs_.size()) {
1391  const PiecewiseLinearFunction* cost = cumul_piecewise_linear_costs_[node];
1392  if (cost != nullptr) {
1393  return cost->Value(cumul_value);
1394  }
1395  }
1396  return 0;
1397 }
1398 
1399 int64 PathCumulFilter::GetCumulSoftLowerBoundCost(int64 node,
1400  int64 cumul_value) const {
1401  if (node < cumul_soft_lower_bounds_.size()) {
1402  const int64 bound = cumul_soft_lower_bounds_[node].bound;
1403  const int64 coefficient = cumul_soft_lower_bounds_[node].coefficient;
1404  if (coefficient > 0 && bound > cumul_value) {
1406  }
1407  }
1408  return 0;
1409 }
1410 
1411 int64 PathCumulFilter::GetPathCumulSoftLowerBoundCost(
1412  const PathTransits& path_transits, int path) const {
1413  int64 node = path_transits.Node(path, path_transits.PathSize(path) - 1);
1414  int64 cumul = cumuls_[node]->Max();
1415  int64 current_cumul_cost_value = GetCumulSoftLowerBoundCost(node, cumul);
1416  for (int i = path_transits.PathSize(path) - 2; i >= 0; --i) {
1417  node = path_transits.Node(path, i);
1418  cumul = CapSub(cumul, path_transits.Transit(path, i));
1419  cumul = std::min(cumuls_[node]->Max(), cumul);
1420  current_cumul_cost_value = CapAdd(current_cumul_cost_value,
1421  GetCumulSoftLowerBoundCost(node, cumul));
1422  }
1423  return current_cumul_cost_value;
1424 }
1425 
1426 void PathCumulFilter::OnBeforeSynchronizePaths() {
1427  total_current_cumul_cost_value_ = 0;
1428  cumul_cost_delta_ = 0;
1429  current_cumul_cost_values_.clear();
1430  if (NumPaths() > 0 &&
1431  (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1432  FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1433  FilterPrecedences() || FilterSoftSpanCost() ||
1434  FilterSoftSpanQuadraticCost())) {
1435  InitializeSupportedPathCumul(&current_min_start_, kint64max);
1436  InitializeSupportedPathCumul(&current_max_end_, kint64min);
1437  current_path_transits_.Clear();
1438  current_path_transits_.AddPaths(NumPaths());
1439  // For each path, compute the minimum end cumul and store the max of these.
1440  for (int r = 0; r < NumPaths(); ++r) {
1441  int64 node = Start(r);
1442  const int vehicle = start_to_vehicle_[Start(r)];
1443  // First pass: evaluating route length to reserve memory to store route
1444  // information.
1445  int number_of_route_arcs = 0;
1446  while (node < Size()) {
1447  ++number_of_route_arcs;
1448  node = Value(node);
1449  }
1450  current_path_transits_.ReserveTransits(r, number_of_route_arcs);
1451  // Second pass: update cumul, transit and cost values.
1452  node = Start(r);
1453  int64 cumul = cumuls_[node]->Min();
1454  std::vector<int64> min_path_cumuls;
1455  min_path_cumuls.reserve(number_of_route_arcs + 1);
1456  min_path_cumuls.push_back(cumul);
1457 
1458  int64 current_cumul_cost_value = GetCumulSoftCost(node, cumul);
1459  current_cumul_cost_value = CapAdd(
1460  current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1461 
1462  int64 total_transit = 0;
1463  while (node < Size()) {
1464  const int64 next = Value(node);
1465  const int64 transit = (*evaluators_[vehicle])(node, next);
1466  total_transit = CapAdd(total_transit, transit);
1467  const int64 transit_slack = CapAdd(transit, slacks_[node]->Min());
1468  current_path_transits_.PushTransit(r, node, next, transit_slack);
1469  cumul = CapAdd(cumul, transit_slack);
1470  cumul =
1471  dimension_.GetFirstPossibleGreaterOrEqualValueForNode(next, cumul);
1472  cumul = std::max(cumuls_[next]->Min(), cumul);
1473  min_path_cumuls.push_back(cumul);
1474  node = next;
1475  current_cumul_cost_value =
1476  CapAdd(current_cumul_cost_value, GetCumulSoftCost(node, cumul));
1477  current_cumul_cost_value = CapAdd(
1478  current_cumul_cost_value, GetCumulPiecewiseLinearCost(node, cumul));
1479  }
1480  if (FilterPrecedences()) {
1481  StoreMinMaxCumulOfNodesOnPath(/*path=*/r, min_path_cumuls,
1482  /*is_delta=*/false);
1483  }
1484  if (number_of_route_arcs == 1 &&
1485  !routing_model_.AreEmptyRouteCostsConsideredForVehicle(vehicle)) {
1486  // This is an empty route (single start->end arc) which we don't take
1487  // into account for costs.
1488  current_cumul_cost_values_[Start(r)] = 0;
1489  current_path_transits_.ClearPath(r);
1490  continue;
1491  }
1492  if (FilterSlackCost() || FilterSoftSpanCost() ||
1493  FilterSoftSpanQuadraticCost()) {
1494  const int64 start = ComputePathMaxStartFromEndCumul(
1495  current_path_transits_, r, Start(r), cumul);
1496  const int64 span_lower_bound = CapSub(cumul, start);
1497  if (FilterSlackCost()) {
1498  current_cumul_cost_value =
1499  CapAdd(current_cumul_cost_value,
1500  CapProd(vehicle_span_cost_coefficients_[vehicle],
1501  CapSub(span_lower_bound, total_transit)));
1502  }
1503  if (FilterSoftSpanCost()) {
1504  const SimpleBoundCosts::BoundCost bound_cost =
1505  dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1506  if (bound_cost.bound < span_lower_bound) {
1507  const int64 violation = CapSub(span_lower_bound, bound_cost.bound);
1508  current_cumul_cost_value = CapAdd(
1509  current_cumul_cost_value, CapProd(bound_cost.cost, violation));
1510  }
1511  }
1512  if (FilterSoftSpanQuadraticCost()) {
1513  const SimpleBoundCosts::BoundCost bound_cost =
1514  dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1515  if (bound_cost.bound < span_lower_bound) {
1516  const int64 violation = CapSub(span_lower_bound, bound_cost.bound);
1517  current_cumul_cost_value =
1518  CapAdd(current_cumul_cost_value,
1519  CapProd(bound_cost.cost, CapProd(violation, violation)));
1520  }
1521  }
1522  }
1523  if (FilterCumulSoftLowerBounds()) {
1524  current_cumul_cost_value =
1525  CapAdd(current_cumul_cost_value,
1526  GetPathCumulSoftLowerBoundCost(current_path_transits_, r));
1527  }
1528  if (FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1529  // TODO(user): Return a status from the optimizer to detect failures
1530  // The only admissible failures here are because of LP timeout.
1531  int64 lp_cumul_cost_value = 0;
1532  LocalDimensionCumulOptimizer* const optimizer =
1533  FilterBreakCost(vehicle) ? mp_optimizer_ : optimizer_;
1534  DCHECK(optimizer != nullptr);
1535  const DimensionSchedulingStatus status =
1536  optimizer->ComputeRouteCumulCostWithoutFixedTransits(
1537  vehicle, [this](int64 node) { return Value(node); },
1538  &lp_cumul_cost_value);
1539  switch (status) {
1540  case DimensionSchedulingStatus::INFEASIBLE:
1541  lp_cumul_cost_value = 0;
1542  break;
1543  case DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY:
1544  DCHECK(mp_optimizer_ != nullptr);
1545  if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1546  vehicle, [this](int64 node) { return Value(node); },
1547  &lp_cumul_cost_value) ==
1548  DimensionSchedulingStatus::INFEASIBLE) {
1549  lp_cumul_cost_value = 0;
1550  }
1551  break;
1552  default:
1553  DCHECK(status == DimensionSchedulingStatus::OPTIMAL);
1554  }
1555  current_cumul_cost_value =
1556  std::max(current_cumul_cost_value, lp_cumul_cost_value);
1557  }
1558  current_cumul_cost_values_[Start(r)] = current_cumul_cost_value;
1559  current_max_end_.path_values[r] = cumul;
1560  if (current_max_end_.cumul_value < cumul) {
1561  current_max_end_.cumul_value = cumul;
1562  current_max_end_.cumul_value_support = r;
1563  }
1564  total_current_cumul_cost_value_ =
1565  CapAdd(total_current_cumul_cost_value_, current_cumul_cost_value);
1566  }
1567  if (FilterPrecedences()) {
1568  // Update the min/max node cumuls of new unperformed nodes.
1569  for (int64 node : GetNewSynchronizedUnperformedNodes()) {
1570  current_min_max_node_cumuls_[node] = {-1, -1};
1571  }
1572  }
1573  // Use the max of the path end cumul mins to compute the corresponding
1574  // maximum start cumul of each path; store the minimum of these.
1575  for (int r = 0; r < NumPaths(); ++r) {
1576  const int64 start = ComputePathMaxStartFromEndCumul(
1577  current_path_transits_, r, Start(r), current_max_end_.cumul_value);
1578  current_min_start_.path_values[r] = start;
1579  if (current_min_start_.cumul_value > start) {
1580  current_min_start_.cumul_value = start;
1581  current_min_start_.cumul_value_support = r;
1582  }
1583  }
1584  }
1585  // Initialize this before considering any deltas (neighbor).
1586  delta_max_end_cumul_ = kint64min;
1587  lns_detected_ = false;
1588 
1589  DCHECK_GE(current_max_end_.cumul_value, current_min_start_.cumul_value);
1590  synchronized_objective_value_ =
1591  CapAdd(total_current_cumul_cost_value_,
1592  CapProd(global_span_cost_coefficient_,
1593  CapSub(current_max_end_.cumul_value,
1594  current_min_start_.cumul_value)));
1595 }
1596 
1597 bool PathCumulFilter::AcceptPath(int64 path_start, int64 chain_start,
1598  int64 chain_end) {
1599  int64 node = path_start;
1600  int64 cumul = cumuls_[node]->Min();
1601  int64 cumul_cost_delta = 0;
1602  int64 total_transit = 0;
1603  const int path = delta_path_transits_.AddPaths(1);
1604  const int vehicle = start_to_vehicle_[path_start];
1605  const int64 capacity = vehicle_capacities_[vehicle];
1606  const bool filter_vehicle_costs =
1607  !routing_model_.IsEnd(GetNext(node)) ||
1608  routing_model_.AreEmptyRouteCostsConsideredForVehicle(vehicle);
1609  if (filter_vehicle_costs) {
1610  cumul_cost_delta = CapAdd(GetCumulSoftCost(node, cumul),
1611  GetCumulPiecewiseLinearCost(node, cumul));
1612  }
1613  // Evaluating route length to reserve memory to store transit information.
1614  int number_of_route_arcs = 0;
1615  while (node < Size()) {
1616  const int64 next = GetNext(node);
1617  // TODO(user): This shouldn't be needed anymore as such deltas should
1618  // have been filtered already.
1619  if (next == kUnassigned) {
1620  // LNS detected, return true since other paths were ok up to now.
1621  lns_detected_ = true;
1622  return true;
1623  }
1624  ++number_of_route_arcs;
1625  node = next;
1626  }
1627  delta_path_transits_.ReserveTransits(path, number_of_route_arcs);
1628  std::vector<int64> min_path_cumuls;
1629  min_path_cumuls.reserve(number_of_route_arcs + 1);
1630  min_path_cumuls.push_back(cumul);
1631  // Check that the path is feasible with regards to cumul bounds, scanning
1632  // the paths from start to end (caching path node sequences and transits
1633  // for further span cost filtering).
1634  node = path_start;
1635  while (node < Size()) {
1636  const int64 next = GetNext(node);
1637  const int64 transit = (*evaluators_[vehicle])(node, next);
1638  total_transit = CapAdd(total_transit, transit);
1639  const int64 transit_slack = CapAdd(transit, slacks_[node]->Min());
1640  delta_path_transits_.PushTransit(path, node, next, transit_slack);
1641  cumul = CapAdd(cumul, transit_slack);
1642  cumul = dimension_.GetFirstPossibleGreaterOrEqualValueForNode(next, cumul);
1643  if (cumul > std::min(capacity, cumuls_[next]->Max())) {
1644  return false;
1645  }
1646  cumul = std::max(cumuls_[next]->Min(), cumul);
1647  min_path_cumuls.push_back(cumul);
1648  node = next;
1649  if (filter_vehicle_costs) {
1650  cumul_cost_delta =
1651  CapAdd(cumul_cost_delta, GetCumulSoftCost(node, cumul));
1652  cumul_cost_delta =
1653  CapAdd(cumul_cost_delta, GetCumulPiecewiseLinearCost(node, cumul));
1654  }
1655  }
1656  const int64 min_end = cumul;
1657 
1658  if (!PickupToDeliveryLimitsRespected(delta_path_transits_, path,
1659  min_path_cumuls)) {
1660  return false;
1661  }
1662  if (FilterSlackCost() || FilterBreakCost(vehicle) ||
1663  FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1664  int64 slack_max = kint64max;
1665  if (vehicle_span_upper_bounds_[vehicle] < kint64max) {
1666  const int64 span_max = vehicle_span_upper_bounds_[vehicle];
1667  slack_max = std::min(slack_max, CapSub(span_max, total_transit));
1668  }
1669  const int64 max_start_from_min_end = ComputePathMaxStartFromEndCumul(
1670  delta_path_transits_, path, path_start, min_end);
1671  const int64 span_lb = CapSub(min_end, max_start_from_min_end);
1672  int64 min_total_slack = CapSub(span_lb, total_transit);
1673  if (min_total_slack > slack_max) return false;
1674 
1675  if (dimension_.HasBreakConstraints()) {
1676  for (const auto [limit, min_break_duration] :
1677  dimension_.GetBreakDistanceDurationOfVehicle(vehicle)) {
1678  // Minimal number of breaks depends on total transit:
1679  // 0 breaks for 0 <= total transit <= limit,
1680  // 1 break for limit + 1 <= total transit <= 2 * limit,
1681  // i breaks for i * limit + 1 <= total transit <= (i+1) * limit, ...
1682  if (limit == 0 || total_transit == 0) continue;
1683  const int num_breaks_lb = (total_transit - 1) / limit;
1684  const int64 slack_lb = CapProd(num_breaks_lb, min_break_duration);
1685  if (slack_lb > slack_max) return false;
1686  min_total_slack = std::max(min_total_slack, slack_lb);
1687  }
1688  // Compute a lower bound of the amount of break that must be made inside
1689  // the route. We compute a mandatory interval (might be empty)
1690  // [max_start, min_end[ during which the route will have to happen,
1691  // then the duration of break that must happen during this interval.
1692  int64 min_total_break = 0;
1693  int64 max_path_end = cumuls_[routing_model_.End(vehicle)]->Max();
1694  const int64 max_start = ComputePathMaxStartFromEndCumul(
1695  delta_path_transits_, path, path_start, max_path_end);
1696  for (const IntervalVar* br :
1697  dimension_.GetBreakIntervalsOfVehicle(vehicle)) {
1698  if (!br->MustBePerformed()) continue;
1699  if (max_start < br->EndMin() && br->StartMax() < min_end) {
1700  min_total_break = CapAdd(min_total_break, br->DurationMin());
1701  }
1702  }
1703  if (min_total_break > slack_max) return false;
1704  min_total_slack = std::max(min_total_slack, min_total_break);
1705  }
1706  if (filter_vehicle_costs) {
1707  cumul_cost_delta = CapAdd(
1708  cumul_cost_delta,
1709  CapProd(vehicle_span_cost_coefficients_[vehicle], min_total_slack));
1710  const int64 span_lower_bound = CapAdd(total_transit, min_total_slack);
1711  if (FilterSoftSpanCost()) {
1712  const SimpleBoundCosts::BoundCost bound_cost =
1713  dimension_.GetSoftSpanUpperBoundForVehicle(vehicle);
1714  if (bound_cost.bound < span_lower_bound) {
1715  const int64 violation = CapSub(span_lower_bound, bound_cost.bound);
1716  cumul_cost_delta =
1717  CapAdd(cumul_cost_delta, CapProd(bound_cost.cost, violation));
1718  }
1719  }
1720  if (FilterSoftSpanQuadraticCost()) {
1721  const SimpleBoundCosts::BoundCost bound_cost =
1722  dimension_.GetQuadraticCostSoftSpanUpperBoundForVehicle(vehicle);
1723  if (bound_cost.bound < span_lower_bound) {
1724  const int64 violation = CapSub(span_lower_bound, bound_cost.bound);
1725  cumul_cost_delta =
1726  CapAdd(cumul_cost_delta,
1727  CapProd(bound_cost.cost, CapProd(violation, violation)));
1728  }
1729  }
1730  }
1731  if (CapAdd(total_transit, min_total_slack) >
1732  vehicle_span_upper_bounds_[vehicle]) {
1733  return false;
1734  }
1735  }
1736  if (FilterCumulSoftLowerBounds() && filter_vehicle_costs) {
1737  cumul_cost_delta =
1738  CapAdd(cumul_cost_delta,
1739  GetPathCumulSoftLowerBoundCost(delta_path_transits_, path));
1740  }
1741  if (FilterPrecedences()) {
1742  StoreMinMaxCumulOfNodesOnPath(path, min_path_cumuls, /*is_delta=*/true);
1743  }
1744  if (!filter_vehicle_costs) {
1745  // If this route's costs should't be taken into account, reset the
1746  // cumul_cost_delta and delta_path_transits_ for this path.
1747  cumul_cost_delta = 0;
1748  delta_path_transits_.ClearPath(path);
1749  }
1750  if (FilterSpanCost() || FilterCumulSoftBounds() || FilterSlackCost() ||
1751  FilterCumulSoftLowerBounds() || FilterCumulPiecewiseLinearCosts() ||
1752  FilterSoftSpanCost(vehicle) || FilterSoftSpanQuadraticCost(vehicle)) {
1753  delta_paths_.insert(GetPath(path_start));
1754  delta_path_cumul_cost_values_[vehicle] = cumul_cost_delta;
1755  cumul_cost_delta =
1756  CapSub(cumul_cost_delta, current_cumul_cost_values_[path_start]);
1757  if (filter_vehicle_costs) {
1758  delta_max_end_cumul_ = std::max(delta_max_end_cumul_, min_end);
1759  }
1760  }
1761  cumul_cost_delta_ = CapAdd(cumul_cost_delta_, cumul_cost_delta);
1762  return true;
1763 }
1764 
1765 bool PathCumulFilter::FinalizeAcceptPath(const Assignment* delta,
1766  int64 objective_min,
1767  int64 objective_max) {
1768  if ((!FilterSpanCost() && !FilterCumulSoftBounds() && !FilterSlackCost() &&
1769  !FilterCumulSoftLowerBounds() && !FilterCumulPiecewiseLinearCosts() &&
1770  !FilterPrecedences() && !FilterSoftSpanCost() &&
1771  !FilterSoftSpanQuadraticCost()) ||
1772  lns_detected_) {
1773  return true;
1774  }
1775  if (FilterPrecedences()) {
1776  for (int64 node : delta_nodes_with_precedences_and_changed_cumul_
1777  .PositionsSetAtLeastOnce()) {
1778  const std::pair<int64, int64> node_min_max_cumul_in_delta =
1779  gtl::FindWithDefault(node_with_precedence_to_delta_min_max_cumuls_,
1780  node, {-1, -1});
1781  // NOTE: This node was seen in delta, so its delta min/max cumul should be
1782  // stored in the map.
1783  DCHECK(node_min_max_cumul_in_delta.first >= 0 &&
1784  node_min_max_cumul_in_delta.second >= 0);
1785  for (const RoutingDimension::NodePrecedence& precedence :
1786  node_index_to_precedences_[node]) {
1787  const bool node_is_first = (precedence.first_node == node);
1788  const int64 other_node =
1789  node_is_first ? precedence.second_node : precedence.first_node;
1790  if (GetNext(other_node) == kUnassigned ||
1791  GetNext(other_node) == other_node) {
1792  // The other node is unperformed, so the precedence constraint is
1793  // inactive.
1794  continue;
1795  }
1796  // max_cumul[second_node] should be greater or equal than
1797  // min_cumul[first_node] + offset.
1798  const std::pair<int64, int64>& other_min_max_cumul_in_delta =
1799  gtl::FindWithDefault(node_with_precedence_to_delta_min_max_cumuls_,
1800  other_node,
1801  current_min_max_node_cumuls_[other_node]);
1802 
1803  const int64 first_min_cumul = node_is_first
1804  ? node_min_max_cumul_in_delta.first
1805  : other_min_max_cumul_in_delta.first;
1806  const int64 second_max_cumul = node_is_first
1807  ? other_min_max_cumul_in_delta.second
1808  : node_min_max_cumul_in_delta.second;
1809 
1810  if (second_max_cumul < first_min_cumul + precedence.offset) {
1811  return false;
1812  }
1813  }
1814  }
1815  }
1816  int64 new_max_end = delta_max_end_cumul_;
1817  int64 new_min_start = kint64max;
1818  if (FilterSpanCost()) {
1819  if (new_max_end < current_max_end_.cumul_value) {
1820  // Delta max end is lower than the current solution one.
1821  // If the path supporting the current max end has been modified, we need
1822  // to check all paths to find the largest max end.
1823  if (!gtl::ContainsKey(delta_paths_,
1824  current_max_end_.cumul_value_support)) {
1825  new_max_end = current_max_end_.cumul_value;
1826  } else {
1827  for (int i = 0; i < current_max_end_.path_values.size(); ++i) {
1828  if (current_max_end_.path_values[i] > new_max_end &&
1829  !gtl::ContainsKey(delta_paths_, i)) {
1830  new_max_end = current_max_end_.path_values[i];
1831  }
1832  }
1833  }
1834  }
1835  // Now that the max end cumul has been found, compute the corresponding
1836  // min start cumul, first from the delta, then if the max end cumul has
1837  // changed, from the unchanged paths as well.
1838  for (int r = 0; r < delta_path_transits_.NumPaths(); ++r) {
1839  new_min_start =
1840  std::min(ComputePathMaxStartFromEndCumul(delta_path_transits_, r,
1841  Start(r), new_max_end),
1842  new_min_start);
1843  }
1844  if (new_max_end != current_max_end_.cumul_value) {
1845  for (int r = 0; r < NumPaths(); ++r) {
1846  if (gtl::ContainsKey(delta_paths_, r)) {
1847  continue;
1848  }
1849  new_min_start = std::min(new_min_start, ComputePathMaxStartFromEndCumul(
1850  current_path_transits_, r,
1851  Start(r), new_max_end));
1852  }
1853  } else if (new_min_start > current_min_start_.cumul_value) {
1854  // Delta min start is greater than the current solution one.
1855  // If the path supporting the current min start has been modified, we need
1856  // to check all paths to find the smallest min start.
1857  if (!gtl::ContainsKey(delta_paths_,
1858  current_min_start_.cumul_value_support)) {
1859  new_min_start = current_min_start_.cumul_value;
1860  } else {
1861  for (int i = 0; i < current_min_start_.path_values.size(); ++i) {
1862  if (current_min_start_.path_values[i] < new_min_start &&
1863  !gtl::ContainsKey(delta_paths_, i)) {
1864  new_min_start = current_min_start_.path_values[i];
1865  }
1866  }
1867  }
1868  }
1869  }
1870 
1871  // Filtering on objective value, calling LPs and MIPs if needed..
1872  accepted_objective_value_ =
1873  CapAdd(cumul_cost_delta_, CapProd(global_span_cost_coefficient_,
1874  CapSub(new_max_end, new_min_start)));
1875 
1876  if (can_use_lp_ && optimizer_ != nullptr &&
1877  accepted_objective_value_ <= objective_max) {
1878  const size_t num_touched_paths = GetTouchedPathStarts().size();
1879  std::vector<int64> path_delta_cost_values(num_touched_paths, 0);
1880  std::vector<bool> requires_mp(num_touched_paths, false);
1881  for (int i = 0; i < num_touched_paths; ++i) {
1882  const int64 start = GetTouchedPathStarts()[i];
1883  const int vehicle = start_to_vehicle_[start];
1884  if (!FilterWithDimensionCumulOptimizerForVehicle(vehicle)) {
1885  continue;
1886  }
1887  int64 path_delta_cost_with_lp = 0;
1888  const DimensionSchedulingStatus status =
1889  optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1890  vehicle, [this](int64 node) { return GetNext(node); },
1891  &path_delta_cost_with_lp);
1892  if (status == DimensionSchedulingStatus::INFEASIBLE) {
1893  return false;
1894  }
1895  DCHECK(gtl::ContainsKey(delta_paths_, GetPath(start)));
1896  const int64 path_cost_diff_with_lp = CapSub(
1897  path_delta_cost_with_lp, delta_path_cumul_cost_values_[vehicle]);
1898  if (path_cost_diff_with_lp > 0) {
1899  path_delta_cost_values[i] = path_delta_cost_with_lp;
1900  accepted_objective_value_ =
1901  CapAdd(accepted_objective_value_, path_cost_diff_with_lp);
1902  if (accepted_objective_value_ > objective_max) {
1903  return false;
1904  }
1905  } else {
1906  path_delta_cost_values[i] = delta_path_cumul_cost_values_[vehicle];
1907  }
1908  if (mp_optimizer_ != nullptr) {
1909  requires_mp[i] =
1910  FilterBreakCost(vehicle) ||
1911  (status == DimensionSchedulingStatus::RELAXED_OPTIMAL_ONLY);
1912  }
1913  }
1914  if (mp_optimizer_ == nullptr) {
1915  return accepted_objective_value_ <= objective_max;
1916  }
1917  for (int i = 0; i < num_touched_paths; ++i) {
1918  if (!requires_mp[i]) {
1919  continue;
1920  }
1921  const int64 start = GetTouchedPathStarts()[i];
1922  const int vehicle = start_to_vehicle_[start];
1923  int64 path_delta_cost_with_mp = 0;
1924  if (mp_optimizer_->ComputeRouteCumulCostWithoutFixedTransits(
1925  vehicle, [this](int64 node) { return GetNext(node); },
1926  &path_delta_cost_with_mp) ==
1927  DimensionSchedulingStatus::INFEASIBLE) {
1928  return false;
1929  }
1930  DCHECK(gtl::ContainsKey(delta_paths_, GetPath(start)));
1931  const int64 path_cost_diff_with_mp =
1932  CapSub(path_delta_cost_with_mp, path_delta_cost_values[i]);
1933  if (path_cost_diff_with_mp > 0) {
1934  accepted_objective_value_ =
1935  CapAdd(accepted_objective_value_, path_cost_diff_with_mp);
1936  if (accepted_objective_value_ > objective_max) {
1937  return false;
1938  }
1939  }
1940  }
1941  }
1942 
1943  return accepted_objective_value_ <= objective_max;
1944 }
1945 
1946 void PathCumulFilter::InitializeSupportedPathCumul(
1947  SupportedPathCumul* supported_cumul, int64 default_value) {
1948  supported_cumul->cumul_value = default_value;
1949  supported_cumul->cumul_value_support = -1;
1950  supported_cumul->path_values.resize(NumPaths(), default_value);
1951 }
1952 
1953 bool PathCumulFilter::PickupToDeliveryLimitsRespected(
1954  const PathTransits& path_transits, int path,
1955  const std::vector<int64>& min_path_cumuls) const {
1956  if (!dimension_.HasPickupToDeliveryLimits()) {
1957  return true;
1958  }
1959  const int num_pairs = routing_model_.GetPickupAndDeliveryPairs().size();
1960  DCHECK_GT(num_pairs, 0);
1961  std::vector<std::pair<int, int64>> visited_delivery_and_min_cumul_per_pair(
1962  num_pairs, {-1, -1});
1963 
1964  const int path_size = path_transits.PathSize(path);
1965  CHECK_EQ(min_path_cumuls.size(), path_size);
1966 
1967  int64 max_cumul = min_path_cumuls.back();
1968  for (int i = path_transits.PathSize(path) - 2; i >= 0; i--) {
1969  const int node_index = path_transits.Node(path, i);
1970  max_cumul = CapSub(max_cumul, path_transits.Transit(path, i));
1971  max_cumul = std::min(cumuls_[node_index]->Max(), max_cumul);
1972 
1973  const std::vector<std::pair<int, int>>& pickup_index_pairs =
1974  routing_model_.GetPickupIndexPairs(node_index);
1975  const std::vector<std::pair<int, int>>& delivery_index_pairs =
1976  routing_model_.GetDeliveryIndexPairs(node_index);
1977  if (!pickup_index_pairs.empty()) {
1978  // The node is a pickup. Check that it is not a delivery and that it
1979  // appears in a single pickup/delivery pair (as required when limits are
1980  // set on dimension cumuls for pickup and deliveries).
1981  DCHECK(delivery_index_pairs.empty());
1982  DCHECK_EQ(pickup_index_pairs.size(), 1);
1983  const int pair_index = pickup_index_pairs[0].first;
1984  // Get the delivery visited for this pair.
1985  const int delivery_index =
1986  visited_delivery_and_min_cumul_per_pair[pair_index].first;
1987  if (delivery_index < 0) {
1988  // No delivery visited after this pickup for this pickup/delivery pair.
1989  continue;
1990  }
1991  const int64 cumul_diff_limit = dimension_.GetPickupToDeliveryLimitForPair(
1992  pair_index, pickup_index_pairs[0].second, delivery_index);
1993  if (CapSub(visited_delivery_and_min_cumul_per_pair[pair_index].second,
1994  max_cumul) > cumul_diff_limit) {
1995  return false;
1996  }
1997  }
1998  if (!delivery_index_pairs.empty()) {
1999  // The node is a delivery. Check that it's not a pickup and it belongs to
2000  // a single pair.
2001  DCHECK(pickup_index_pairs.empty());
2002  DCHECK_EQ(delivery_index_pairs.size(), 1);
2003  const int pair_index = delivery_index_pairs[0].first;
2004  std::pair<int, int64>& delivery_index_and_cumul =
2005  visited_delivery_and_min_cumul_per_pair[pair_index];
2006  int& delivery_index = delivery_index_and_cumul.first;
2007  DCHECK_EQ(delivery_index, -1);
2008  delivery_index = delivery_index_pairs[0].second;
2009  delivery_index_and_cumul.second = min_path_cumuls[i];
2010  }
2011  }
2012  return true;
2013 }
2014 
2015 void PathCumulFilter::StoreMinMaxCumulOfNodesOnPath(
2016  int path, const std::vector<int64>& min_path_cumuls, bool is_delta) {
2017  const PathTransits& path_transits =
2018  is_delta ? delta_path_transits_ : current_path_transits_;
2019 
2020  const int path_size = path_transits.PathSize(path);
2021  DCHECK_EQ(min_path_cumuls.size(), path_size);
2022 
2023  int64 max_cumul = cumuls_[path_transits.Node(path, path_size - 1)]->Max();
2024  for (int i = path_size - 1; i >= 0; i--) {
2025  const int node_index = path_transits.Node(path, i);
2026 
2027  if (i < path_size - 1) {
2028  max_cumul = CapSub(max_cumul, path_transits.Transit(path, i));
2029  max_cumul = std::min(cumuls_[node_index]->Max(), max_cumul);
2030  }
2031 
2032  if (is_delta && node_index_to_precedences_[node_index].empty()) {
2033  // No need to update the delta cumul map for nodes without precedences.
2034  continue;
2035  }
2036 
2037  std::pair<int64, int64>& min_max_cumuls =
2038  is_delta ? node_with_precedence_to_delta_min_max_cumuls_[node_index]
2039  : current_min_max_node_cumuls_[node_index];
2040  min_max_cumuls.first = min_path_cumuls[i];
2041  min_max_cumuls.second = max_cumul;
2042 
2043  if (is_delta && !routing_model_.IsEnd(node_index) &&
2044  (min_max_cumuls.first !=
2045  current_min_max_node_cumuls_[node_index].first ||
2046  max_cumul != current_min_max_node_cumuls_[node_index].second)) {
2047  delta_nodes_with_precedences_and_changed_cumul_.Set(node_index);
2048  }
2049  }
2050 }
2051 
2052 int64 PathCumulFilter::ComputePathMaxStartFromEndCumul(
2053  const PathTransits& path_transits, int path, int64 path_start,
2054  int64 min_end_cumul) const {
2055  int64 cumul_from_min_end = min_end_cumul;
2056  int64 cumul_from_max_end =
2057  cumuls_[routing_model_.End(start_to_vehicle_[path_start])]->Max();
2058  for (int i = path_transits.PathSize(path) - 2; i >= 0; --i) {
2059  const int64 transit = path_transits.Transit(path, i);
2060  const int64 node = path_transits.Node(path, i);
2061  cumul_from_min_end =
2062  std::min(cumuls_[node]->Max(), CapSub(cumul_from_min_end, transit));
2063  cumul_from_max_end = dimension_.GetLastPossibleLessOrEqualValueForNode(
2064  node, CapSub(cumul_from_max_end, transit));
2065  }
2066  return std::min(cumul_from_min_end, cumul_from_max_end);
2067 }
2068 
2069 } // namespace
2070 
2072  const RoutingDimension& dimension,
2073  const RoutingSearchParameters& parameters,
2074  bool propagate_own_objective_value, bool filter_objective_cost,
2075  bool can_use_lp) {
2076  RoutingModel& model = *dimension.model();
2077  return model.solver()->RevAlloc(new PathCumulFilter(
2078  model, dimension, parameters, propagate_own_objective_value,
2079  filter_objective_cost, can_use_lp));
2080 }
2081 
2082 namespace {
2083 
2084 bool DimensionHasCumulCost(const RoutingDimension& dimension) {
2085  if (dimension.global_span_cost_coefficient() != 0) return true;
2086  if (dimension.HasSoftSpanUpperBounds()) return true;
2087  if (dimension.HasQuadraticCostSoftSpanUpperBounds()) return true;
2088  for (const int64 coefficient : dimension.vehicle_span_cost_coefficients()) {
2089  if (coefficient != 0) return true;
2090  }
2091  for (int i = 0; i < dimension.cumuls().size(); ++i) {
2092  if (dimension.HasCumulVarSoftUpperBound(i)) return true;
2093  if (dimension.HasCumulVarSoftLowerBound(i)) return true;
2094  if (dimension.HasCumulVarPiecewiseLinearCost(i)) return true;
2095  }
2096  return false;
2097 }
2098 
2099 bool DimensionHasCumulConstraint(const RoutingDimension& dimension) {
2100  if (dimension.HasBreakConstraints()) return true;
2101  if (dimension.HasPickupToDeliveryLimits()) return true;
2102  if (!dimension.GetNodePrecedences().empty()) return true;
2103  for (const int64 upper_bound : dimension.vehicle_span_upper_bounds()) {
2104  if (upper_bound != kint64max) return true;
2105  }
2106  for (const IntVar* const slack : dimension.slacks()) {
2107  if (slack->Min() > 0) return true;
2108  }
2109  const std::vector<IntVar*>& cumuls = dimension.cumuls();
2110  for (int i = 0; i < cumuls.size(); ++i) {
2111  IntVar* const cumul_var = cumuls[i];
2112  if (cumul_var->Min() > 0 && cumul_var->Max() < kint64max &&
2113  !dimension.model()->IsEnd(i)) {
2114  return true;
2115  }
2116  if (dimension.forbidden_intervals()[i].NumIntervals() > 0) return true;
2117  }
2118  return false;
2119 }
2120 
2121 } // namespace
2122 
2124  const PathState* path_state,
2125  const std::vector<RoutingDimension*>& dimensions,
2126  std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2127  // For every dimension that fits, add a UnaryDimensionChecker.
2128  for (const RoutingDimension* dimension : dimensions) {
2129  // Skip dimension if not unary.
2130  if (dimension->GetUnaryTransitEvaluator(0) == nullptr) continue;
2131 
2132  using Intervals = std::vector<UnaryDimensionChecker::Interval>;
2133  // Fill path capacities and classes.
2134  const int num_vehicles = dimension->model()->vehicles();
2135  Intervals path_capacity(num_vehicles);
2136  std::vector<int> path_class(num_vehicles);
2137  for (int v = 0; v < num_vehicles; ++v) {
2138  const auto& vehicle_capacities = dimension->vehicle_capacities();
2139  path_capacity[v] = {0, vehicle_capacities[v]};
2140  path_class[v] = dimension->vehicle_to_class(v);
2141  }
2142  // For each class, retrieve the demands of each node.
2143  // Dimension store evaluators with a double indirection for compacity:
2144  // vehicle -> vehicle_class -> evaluator_index.
2145  // We replicate this in UnaryDimensionChecker,
2146  // except we expand evaluator_index to an array of values for all nodes.
2147  const int num_vehicle_classes =
2148  1 + *std::max_element(path_class.begin(), path_class.end());
2149  std::vector<Intervals> demands(num_vehicle_classes);
2150  const int num_cumuls = dimension->cumuls().size();
2151  const int num_slacks = dimension->slacks().size();
2152  for (int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
2153  const int vehicle_class = path_class[vehicle];
2154  if (!demands[vehicle_class].empty()) continue;
2155  const auto& evaluator = dimension->GetUnaryTransitEvaluator(vehicle);
2156  Intervals class_demands(num_cumuls);
2157  for (int node = 0; node < num_cumuls; ++node) {
2158  if (node < num_slacks) {
2159  const int64 demand_min = evaluator(node);
2160  const int64 slack_max = dimension->SlackVar(node)->Max();
2161  class_demands[node] = {demand_min, CapAdd(demand_min, slack_max)};
2162  } else {
2163  class_demands[node] = {0, 0};
2164  }
2165  }
2166  demands[vehicle_class] = std::move(class_demands);
2167  }
2168  // Fill node capacities.
2169  Intervals node_capacity(num_cumuls);
2170  for (int node = 0; node < num_cumuls; ++node) {
2171  const IntVar* cumul = dimension->CumulVar(node);
2172  node_capacity[node] = {cumul->Min(), cumul->Max()};
2173  }
2174  // Make the dimension checker and pass ownership to the filter.
2175  auto checker = absl::make_unique<UnaryDimensionChecker>(
2176  path_state, std::move(path_capacity), std::move(path_class),
2177  std::move(demands), std::move(node_capacity));
2178  const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2180  dimension->model()->solver(), std::move(checker));
2181  filters->push_back({filter, kAccept});
2182  }
2183 }
2184 
2186  const std::vector<RoutingDimension*>& dimensions,
2187  const RoutingSearchParameters& parameters, bool filter_objective_cost,
2188  std::vector<LocalSearchFilterManager::FilterEvent>* filters) {
2189  const auto kAccept = LocalSearchFilterManager::FilterEventType::kAccept;
2190  // NOTE: We first sort the dimensions by increasing complexity of filtering:
2191  // - Dimensions without any cumul-related costs or constraints will have a
2192  // ChainCumulFilter.
2193  // - Dimensions with cumul costs or constraints, but no global span cost
2194  // and/or precedences will have a PathCumulFilter.
2195  // - Dimensions with a global span cost coefficient and/or precedences will
2196  // have a global LP filter.
2197  const int num_dimensions = dimensions.size();
2198 
2199  std::vector<bool> use_path_cumul_filter(num_dimensions);
2200  std::vector<bool> use_cumul_bounds_propagator_filter(num_dimensions);
2201  std::vector<bool> use_global_lp_filter(num_dimensions);
2202  std::vector<int> filtering_difficulty(num_dimensions);
2203  for (int d = 0; d < num_dimensions; d++) {
2204  const RoutingDimension& dimension = *dimensions[d];
2205  const bool has_cumul_cost = DimensionHasCumulCost(dimension);
2206  use_path_cumul_filter[d] =
2207  has_cumul_cost || DimensionHasCumulConstraint(dimension);
2208 
2209  const bool can_use_cumul_bounds_propagator_filter =
2210  !dimension.HasBreakConstraints() &&
2211  (!filter_objective_cost || !has_cumul_cost);
2212  const bool has_precedences = !dimension.GetNodePrecedences().empty();
2213  use_global_lp_filter[d] =
2214  (has_precedences && !can_use_cumul_bounds_propagator_filter) ||
2215  (filter_objective_cost && dimension.global_span_cost_coefficient() > 0);
2216 
2217  use_cumul_bounds_propagator_filter[d] =
2218  has_precedences && !use_global_lp_filter[d];
2219 
2220  filtering_difficulty[d] = 4 * use_global_lp_filter[d] +
2221  2 * use_cumul_bounds_propagator_filter[d] +
2222  use_path_cumul_filter[d];
2223  }
2224 
2225  std::vector<int> sorted_dimension_indices(num_dimensions);
2226  std::iota(sorted_dimension_indices.begin(), sorted_dimension_indices.end(),
2227  0);
2228  std::sort(sorted_dimension_indices.begin(), sorted_dimension_indices.end(),
2229  [&filtering_difficulty](int d1, int d2) {
2230  return filtering_difficulty[d1] < filtering_difficulty[d2];
2231  });
2232 
2233  for (const int d : sorted_dimension_indices) {
2234  const RoutingDimension& dimension = *dimensions[d];
2235  const RoutingModel& model = *dimension.model();
2236  // NOTE: We always add the [Chain|Path]CumulFilter to filter each route's
2237  // feasibility separately to try and cut bad decisions earlier in the
2238  // search, but we don't propagate the computed cost if the LPCumulFilter is
2239  // already doing it.
2240  const bool use_global_lp = use_global_lp_filter[d];
2241  if (use_path_cumul_filter[d]) {
2242  filters->push_back(
2243  {MakePathCumulFilter(dimension, parameters, !use_global_lp,
2244  filter_objective_cost),
2245  kAccept});
2246  } else {
2247  filters->push_back(
2248  {model.solver()->RevAlloc(new ChainCumulFilter(model, dimension)),
2249  kAccept});
2250  }
2251 
2252  if (use_global_lp) {
2253  DCHECK(model.GetMutableGlobalCumulOptimizer(dimension) != nullptr);
2254  filters->push_back({MakeGlobalLPCumulFilter(
2255  model.GetMutableGlobalCumulOptimizer(dimension),
2256  filter_objective_cost),
2257  kAccept});
2258  } else if (use_cumul_bounds_propagator_filter[d]) {
2259  filters->push_back({MakeCumulBoundsPropagatorFilter(dimension), kAccept});
2260  }
2261  }
2262 }
2263 
2264 namespace {
2265 
2266 // Filter for pickup/delivery precedences.
2267 class PickupDeliveryFilter : public BasePathFilter {
2268  public:
2269  PickupDeliveryFilter(const std::vector<IntVar*>& nexts, int next_domain_size,
2270  const RoutingModel::IndexPairs& pairs,
2271  const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2272  vehicle_policies);
2273  ~PickupDeliveryFilter() override {}
2274  bool AcceptPath(int64 path_start, int64 chain_start,
2275  int64 chain_end) override;
2276  std::string DebugString() const override { return "PickupDeliveryFilter"; }
2277 
2278  private:
2279  bool AcceptPathDefault(int64 path_start);
2280  template <bool lifo>
2281  bool AcceptPathOrdered(int64 path_start);
2282 
2283  std::vector<int> pair_firsts_;
2284  std::vector<int> pair_seconds_;
2285  const RoutingModel::IndexPairs pairs_;
2286  SparseBitset<> visited_;
2287  std::deque<int> visited_deque_;
2288  const std::vector<RoutingModel::PickupAndDeliveryPolicy> vehicle_policies_;
2289 };
2290 
2291 PickupDeliveryFilter::PickupDeliveryFilter(
2292  const std::vector<IntVar*>& nexts, int next_domain_size,
2293  const RoutingModel::IndexPairs& pairs,
2294  const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies)
2295  : BasePathFilter(nexts, next_domain_size),
2296  pair_firsts_(next_domain_size, kUnassigned),
2297  pair_seconds_(next_domain_size, kUnassigned),
2298  pairs_(pairs),
2299  visited_(Size()),
2300  vehicle_policies_(vehicle_policies) {
2301  for (int i = 0; i < pairs.size(); ++i) {
2302  const auto& index_pair = pairs[i];
2303  for (int first : index_pair.first) {
2304  pair_firsts_[first] = i;
2305  }
2306  for (int second : index_pair.second) {
2307  pair_seconds_[second] = i;
2308  }
2309  }
2310 }
2311 
2312 bool PickupDeliveryFilter::AcceptPath(int64 path_start, int64 chain_start,
2313  int64 chain_end) {
2314  switch (vehicle_policies_[GetPath(path_start)]) {
2316  return AcceptPathDefault(path_start);
2318  return AcceptPathOrdered<true>(path_start);
2320  return AcceptPathOrdered<false>(path_start);
2321  default:
2322  return true;
2323  }
2324 }
2325 
2326 bool PickupDeliveryFilter::AcceptPathDefault(int64 path_start) {
2327  visited_.ClearAll();
2328  int64 node = path_start;
2329  int64 path_length = 1;
2330  while (node < Size()) {
2331  // Detect sub-cycles (path is longer than longest possible path).
2332  if (path_length > Size()) {
2333  return false;
2334  }
2335  if (pair_firsts_[node] != kUnassigned) {
2336  // Checking on pair firsts is not actually necessary (inconsistencies
2337  // will get caught when checking pair seconds); doing it anyway to
2338  // cut checks early.
2339  for (int second : pairs_[pair_firsts_[node]].second) {
2340  if (visited_[second]) {
2341  return false;
2342  }
2343  }
2344  }
2345  if (pair_seconds_[node] != kUnassigned) {
2346  bool found_first = false;
2347  bool some_synced = false;
2348  for (int first : pairs_[pair_seconds_[node]].first) {
2349  if (visited_[first]) {
2350  found_first = true;
2351  break;
2352  }
2353  if (IsVarSynced(first)) {
2354  some_synced = true;
2355  }
2356  }
2357  if (!found_first && some_synced) {
2358  return false;
2359  }
2360  }
2361  visited_.Set(node);
2362  const int64 next = GetNext(node);
2363  if (next == kUnassigned) {
2364  // LNS detected, return true since path was ok up to now.
2365  return true;
2366  }
2367  node = next;
2368  ++path_length;
2369  }
2370  for (const int64 node : visited_.PositionsSetAtLeastOnce()) {
2371  if (pair_firsts_[node] != kUnassigned) {
2372  bool found_second = false;
2373  bool some_synced = false;
2374  for (int second : pairs_[pair_firsts_[node]].second) {
2375  if (visited_[second]) {
2376  found_second = true;
2377  break;
2378  }
2379  if (IsVarSynced(second)) {
2380  some_synced = true;
2381  }
2382  }
2383  if (!found_second && some_synced) {
2384  return false;
2385  }
2386  }
2387  }
2388  return true;
2389 }
2390 
2391 template <bool lifo>
2392 bool PickupDeliveryFilter::AcceptPathOrdered(int64 path_start) {
2393  visited_deque_.clear();
2394  int64 node = path_start;
2395  int64 path_length = 1;
2396  while (node < Size()) {
2397  // Detect sub-cycles (path is longer than longest possible path).
2398  if (path_length > Size()) {
2399  return false;
2400  }
2401  if (pair_firsts_[node] != kUnassigned) {
2402  if (lifo) {
2403  visited_deque_.push_back(node);
2404  } else {
2405  visited_deque_.push_front(node);
2406  }
2407  }
2408  if (pair_seconds_[node] != kUnassigned) {
2409  bool found_first = false;
2410  bool some_synced = false;
2411  for (int first : pairs_[pair_seconds_[node]].first) {
2412  if (!visited_deque_.empty() && visited_deque_.back() == first) {
2413  found_first = true;
2414  break;
2415  }
2416  if (IsVarSynced(first)) {
2417  some_synced = true;
2418  }
2419  }
2420  if (!found_first && some_synced) {
2421  return false;
2422  } else if (!visited_deque_.empty()) {
2423  visited_deque_.pop_back();
2424  }
2425  }
2426  const int64 next = GetNext(node);
2427  if (next == kUnassigned) {
2428  // LNS detected, return true since path was ok up to now.
2429  return true;
2430  }
2431  node = next;
2432  ++path_length;
2433  }
2434  while (!visited_deque_.empty()) {
2435  for (int second : pairs_[pair_firsts_[visited_deque_.back()]].second) {
2436  if (IsVarSynced(second)) {
2437  return false;
2438  }
2439  }
2440  visited_deque_.pop_back();
2441  }
2442  return true;
2443 }
2444 
2445 } // namespace
2446 
2448  const RoutingModel& routing_model, const RoutingModel::IndexPairs& pairs,
2449  const std::vector<RoutingModel::PickupAndDeliveryPolicy>&
2450  vehicle_policies) {
2451  return routing_model.solver()->RevAlloc(new PickupDeliveryFilter(
2452  routing_model.Nexts(), routing_model.Size() + routing_model.vehicles(),
2453  pairs, vehicle_policies));
2454 }
2455 
2456 namespace {
2457 
2458 // Vehicle variable filter
2459 class VehicleVarFilter : public BasePathFilter {
2460  public:
2461  explicit VehicleVarFilter(const RoutingModel& routing_model);
2462  ~VehicleVarFilter() override {}
2463  bool AcceptPath(int64 path_start, int64 chain_start,
2464  int64 chain_end) override;
2465  std::string DebugString() const override { return "VehicleVariableFilter"; }
2466 
2467  private:
2468  bool DisableFiltering() const override;
2469  bool IsVehicleVariableConstrained(int index) const;
2470 
2471  std::vector<int64> start_to_vehicle_;
2472  std::vector<IntVar*> vehicle_vars_;
2473  const int64 unconstrained_vehicle_var_domain_size_;
2474 };
2475 
2476 VehicleVarFilter::VehicleVarFilter(const RoutingModel& routing_model)
2477  : BasePathFilter(routing_model.Nexts(),
2478  routing_model.Size() + routing_model.vehicles()),
2479  vehicle_vars_(routing_model.VehicleVars()),
2480  unconstrained_vehicle_var_domain_size_(routing_model.vehicles()) {
2481  start_to_vehicle_.resize(Size(), -1);
2482  for (int i = 0; i < routing_model.vehicles(); ++i) {
2483  start_to_vehicle_[routing_model.Start(i)] = i;
2484  }
2485 }
2486 
2487 bool VehicleVarFilter::AcceptPath(int64 path_start, int64 chain_start,
2488  int64 chain_end) {
2489  const int64 vehicle = start_to_vehicle_[path_start];
2490  int64 node = chain_start;
2491  while (node != chain_end) {
2492  if (!vehicle_vars_[node]->Contains(vehicle)) {
2493  return false;
2494  }
2495  node = GetNext(node);
2496  }
2497  return vehicle_vars_[node]->Contains(vehicle);
2498 }
2499 
2500 bool VehicleVarFilter::DisableFiltering() const {
2501  for (int i = 0; i < vehicle_vars_.size(); ++i) {
2502  if (IsVehicleVariableConstrained(i)) return false;
2503  }
2504  return true;
2505 }
2506 
2507 bool VehicleVarFilter::IsVehicleVariableConstrained(int index) const {
2508  const IntVar* const vehicle_var = vehicle_vars_[index];
2509  // If vehicle variable contains -1 (optional node), then we need to
2510  // add it to the "unconstrained" domain. Impact we don't filter mandatory
2511  // nodes made inactive here, but it is covered by other filters.
2512  const int adjusted_unconstrained_vehicle_var_domain_size =
2513  vehicle_var->Min() >= 0 ? unconstrained_vehicle_var_domain_size_
2514  : unconstrained_vehicle_var_domain_size_ + 1;
2515  return vehicle_var->Size() != adjusted_unconstrained_vehicle_var_domain_size;
2516 }
2517 
2518 } // namespace
2519 
2521  const RoutingModel& routing_model) {
2522  return routing_model.solver()->RevAlloc(new VehicleVarFilter(routing_model));
2523 }
2524 
2525 namespace {
2526 
2527 class CumulBoundsPropagatorFilter : public IntVarLocalSearchFilter {
2528  public:
2529  explicit CumulBoundsPropagatorFilter(const RoutingDimension& dimension);
2530  bool Accept(const Assignment* delta, const Assignment* deltadelta,
2531  int64 objective_min, int64 objective_max) override;
2532  std::string DebugString() const override {
2533  return "CumulBoundsPropagatorFilter(" + propagator_.dimension().name() +
2534  ")";
2535  }
2536 
2537  private:
2538  CumulBoundsPropagator propagator_;
2539  const int64 cumul_offset_;
2540  SparseBitset<int64> delta_touched_;
2541  std::vector<int64> delta_nexts_;
2542 };
2543 
2544 CumulBoundsPropagatorFilter::CumulBoundsPropagatorFilter(
2545  const RoutingDimension& dimension)
2546  : IntVarLocalSearchFilter(dimension.model()->Nexts()),
2547  propagator_(&dimension),
2548  cumul_offset_(dimension.GetGlobalOptimizerOffset()),
2549  delta_touched_(Size()),
2550  delta_nexts_(Size()) {}
2551 
2552 bool CumulBoundsPropagatorFilter::Accept(const Assignment* delta,
2553  const Assignment* deltadelta,
2554  int64 objective_min,
2555  int64 objective_max) {
2556  delta_touched_.ClearAll();
2557  for (const IntVarElement& delta_element :
2558  delta->IntVarContainer().elements()) {
2559  int64 index = -1;
2560  if (FindIndex(delta_element.Var(), &index)) {
2561  if (!delta_element.Bound()) {
2562  // LNS detected
2563  return true;
2564  }
2565  delta_touched_.Set(index);
2566  delta_nexts_[index] = delta_element.Value();
2567  }
2568  }
2569  const auto& next_accessor = [this](int64 index) {
2570  return delta_touched_[index] ? delta_nexts_[index] : Value(index);
2571  };
2572 
2573  return propagator_.PropagateCumulBounds(next_accessor, cumul_offset_);
2574 }
2575 
2576 } // namespace
2577 
2579  const RoutingDimension& dimension) {
2580  return dimension.model()->solver()->RevAlloc(
2581  new CumulBoundsPropagatorFilter(dimension));
2582 }
2583 
2584 namespace {
2585 
2586 class LPCumulFilter : public IntVarLocalSearchFilter {
2587  public:
2588  LPCumulFilter(const std::vector<IntVar*>& nexts,
2589  GlobalDimensionCumulOptimizer* optimizer,
2590  bool filter_objective_cost);
2591  bool Accept(const Assignment* delta, const Assignment* deltadelta,
2592  int64 objective_min, int64 objective_max) override;
2593  int64 GetAcceptedObjectiveValue() const override;
2594  void OnSynchronize(const Assignment* delta) override;
2595  int64 GetSynchronizedObjectiveValue() const override;
2596  std::string DebugString() const override {
2597  return "LPCumulFilter(" + optimizer_.dimension()->name() + ")";
2598  }
2599 
2600  private:
2601  GlobalDimensionCumulOptimizer& optimizer_;
2602  const bool filter_objective_cost_;
2603  int64 synchronized_cost_without_transit_;
2604  int64 delta_cost_without_transit_;
2605  SparseBitset<int64> delta_touched_;
2606  std::vector<int64> delta_nexts_;
2607 };
2608 
2609 LPCumulFilter::LPCumulFilter(const std::vector<IntVar*>& nexts,
2610  GlobalDimensionCumulOptimizer* optimizer,
2611  bool filter_objective_cost)
2612  : IntVarLocalSearchFilter(nexts),
2613  optimizer_(*optimizer),
2614  filter_objective_cost_(filter_objective_cost),
2615  synchronized_cost_without_transit_(-1),
2616  delta_cost_without_transit_(-1),
2617  delta_touched_(Size()),
2618  delta_nexts_(Size()) {}
2619 
2620 bool LPCumulFilter::Accept(const Assignment* delta,
2621  const Assignment* deltadelta, int64 objective_min,
2622  int64 objective_max) {
2623  delta_touched_.ClearAll();
2624  for (const IntVarElement& delta_element :
2625  delta->IntVarContainer().elements()) {
2626  int64 index = -1;
2627  if (FindIndex(delta_element.Var(), &index)) {
2628  if (!delta_element.Bound()) {
2629  // LNS detected
2630  return true;
2631  }
2632  delta_touched_.Set(index);
2633  delta_nexts_[index] = delta_element.Value();
2634  }
2635  }
2636  const auto& next_accessor = [this](int64 index) {
2637  return delta_touched_[index] ? delta_nexts_[index] : Value(index);
2638  };
2639 
2640  if (!filter_objective_cost_) {
2641  // No need to compute the cost of the LP, only verify its feasibility.
2642  delta_cost_without_transit_ = 0;
2643  return optimizer_.IsFeasible(next_accessor);
2644  }
2645 
2646  if (!optimizer_.ComputeCumulCostWithoutFixedTransits(
2647  next_accessor, &delta_cost_without_transit_)) {
2648  // Infeasible.
2649  delta_cost_without_transit_ = kint64max;
2650  return false;
2651  }
2652  return delta_cost_without_transit_ <= objective_max;
2653 }
2654 
2655 int64 LPCumulFilter::GetAcceptedObjectiveValue() const {
2656  return delta_cost_without_transit_;
2657 }
2658 
2659 void LPCumulFilter::OnSynchronize(const Assignment* delta) {
2660  // TODO(user): Try to optimize this so the LP is not called when the last
2661  // computed delta cost corresponds to the solution being synchronized.
2662  const RoutingModel& model = *optimizer_.dimension()->model();
2663  if (!optimizer_.ComputeCumulCostWithoutFixedTransits(
2664  [this, &model](int64 index) {
2665  return IsVarSynced(index) ? Value(index)
2666  : model.IsStart(index) ? model.End(model.VehicleIndex(index))
2667  : index;
2668  },
2669  &synchronized_cost_without_transit_)) {
2670  // TODO(user): This should only happen if the LP solver times out.
2671  // DCHECK the fail wasn't due to an infeasible model.
2672  synchronized_cost_without_transit_ = 0;
2673  }
2674 }
2675 
2676 int64 LPCumulFilter::GetSynchronizedObjectiveValue() const {
2677  return synchronized_cost_without_transit_;
2678 }
2679 
2680 } // namespace
2681 
2683  GlobalDimensionCumulOptimizer* optimizer, bool filter_objective_cost) {
2684  const RoutingModel& model = *optimizer->dimension()->model();
2685  return model.solver()->RevAlloc(
2686  new LPCumulFilter(model.Nexts(), optimizer, filter_objective_cost));
2687 }
2688 
2690 
2691 CPFeasibilityFilter::CPFeasibilityFilter(RoutingModel* routing_model)
2692  : IntVarLocalSearchFilter(routing_model->Nexts()),
2693  model_(routing_model),
2694  solver_(routing_model->solver()),
2695  assignment_(solver_->MakeAssignment()),
2696  temp_assignment_(solver_->MakeAssignment()),
2697  restore_(solver_->MakeRestoreAssignment(temp_assignment_)),
2698  limit_(solver_->MakeCustomLimit(
2699  [routing_model]() { return routing_model->CheckLimit(); })) {
2700  assignment_->Add(routing_model->Nexts());
2701 }
2702 
2704  const Assignment* deltadelta,
2705  int64 objective_min, int64 objective_max) {
2706  temp_assignment_->Copy(assignment_);
2707  AddDeltaToAssignment(delta, temp_assignment_);
2708 
2709  return solver_->Solve(restore_, limit_);
2710 }
2711 
2713  AddDeltaToAssignment(delta, assignment_);
2714 }
2715 
2716 void CPFeasibilityFilter::AddDeltaToAssignment(const Assignment* delta,
2717  Assignment* assignment) {
2718  if (delta == nullptr) {
2719  return;
2720  }
2721  Assignment::IntContainer* const container =
2722  assignment->MutableIntVarContainer();
2723  const Assignment::IntContainer& delta_container = delta->IntVarContainer();
2724  const int delta_size = delta_container.Size();
2725 
2726  for (int i = 0; i < delta_size; i++) {
2727  const IntVarElement& delta_element = delta_container.Element(i);
2728  IntVar* const var = delta_element.Var();
2729  int64 index = kUnassigned;
2730  CHECK(FindIndex(var, &index));
2731  DCHECK_EQ(var, Var(index));
2732  const int64 value = delta_element.Value();
2733 
2734  container->AddAtPosition(var, index)->SetValue(value);
2735  if (model_->IsStart(index)) {
2736  if (model_->IsEnd(value)) {
2737  // Do not restore unused routes.
2738  container->MutableElement(index)->Deactivate();
2739  } else {
2740  // Re-activate the route's start in case it was deactivated before.
2741  container->MutableElement(index)->Activate();
2742  }
2743  }
2744  }
2745 }
2746 
2748  return routing_model->solver()->RevAlloc(
2749  new CPFeasibilityFilter(routing_model));
2750 }
2751 
2752 // TODO(user): Implement same-vehicle filter. Could be merged with node
2753 // precedence filter.
2754 
2755 // --- VehicleTypeCurator ---
2756 
2757 void VehicleTypeCurator::Reset(const std::function<bool(int)>& store_vehicle) {
2758  const std::vector<std::set<VehicleClassEntry>>& all_vehicle_classes_per_type =
2759  vehicle_type_container_->sorted_vehicle_classes_per_type;
2760  sorted_vehicle_classes_per_type_.resize(all_vehicle_classes_per_type.size());
2761  const std::vector<std::deque<int>>& all_vehicles_per_class =
2762  vehicle_type_container_->vehicles_per_vehicle_class;
2763  vehicles_per_vehicle_class_.resize(all_vehicles_per_class.size());
2764 
2765  for (int type = 0; type < all_vehicle_classes_per_type.size(); type++) {
2766  std::set<VehicleClassEntry>& stored_class_entries =
2767  sorted_vehicle_classes_per_type_[type];
2768  stored_class_entries.clear();
2769  for (VehicleClassEntry class_entry : all_vehicle_classes_per_type[type]) {
2770  const int vehicle_class = class_entry.vehicle_class;
2771  std::vector<int>& stored_vehicles =
2772  vehicles_per_vehicle_class_[vehicle_class];
2773  stored_vehicles.clear();
2774  for (int vehicle : all_vehicles_per_class[vehicle_class]) {
2775  if (store_vehicle(vehicle)) {
2776  stored_vehicles.push_back(vehicle);
2777  }
2778  }
2779  if (!stored_vehicles.empty()) {
2780  stored_class_entries.insert(class_entry);
2781  }
2782  }
2783  }
2784 }
2785 
2787  const std::function<bool(int)>& remove_vehicle) {
2788  for (std::set<VehicleClassEntry>& class_entries :
2789  sorted_vehicle_classes_per_type_) {
2790  auto class_entry_it = class_entries.begin();
2791  while (class_entry_it != class_entries.end()) {
2792  const int vehicle_class = class_entry_it->vehicle_class;
2793  std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
2794  vehicles.erase(std::remove_if(vehicles.begin(), vehicles.end(),
2795  [&remove_vehicle](int vehicle) {
2796  return remove_vehicle(vehicle);
2797  }),
2798  vehicles.end());
2799  if (vehicles.empty()) {
2800  class_entry_it = class_entries.erase(class_entry_it);
2801  } else {
2802  class_entry_it++;
2803  }
2804  }
2805  }
2806 }
2807 
2809  int type, std::function<bool(int)> vehicle_is_compatible,
2810  std::function<bool(int)> stop_and_return_vehicle) {
2811  std::set<VehicleTypeCurator::VehicleClassEntry>& sorted_classes =
2812  sorted_vehicle_classes_per_type_[type];
2813  auto vehicle_class_it = sorted_classes.begin();
2814 
2815  while (vehicle_class_it != sorted_classes.end()) {
2816  const int vehicle_class = vehicle_class_it->vehicle_class;
2817  std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
2818  DCHECK(!vehicles.empty());
2819 
2820  for (auto vehicle_it = vehicles.begin(); vehicle_it != vehicles.end();
2821  vehicle_it++) {
2822  const int vehicle = *vehicle_it;
2823  if (vehicle_is_compatible(vehicle)) {
2824  vehicles.erase(vehicle_it);
2825  if (vehicles.empty()) {
2826  sorted_classes.erase(vehicle_class_it);
2827  }
2828  return {vehicle, -1};
2829  }
2830  if (stop_and_return_vehicle(vehicle)) {
2831  return {-1, vehicle};
2832  }
2833  }
2834  // If no compatible vehicle was found in this class, move on to the next
2835  // vehicle class.
2836  vehicle_class_it++;
2837  }
2838  // No compatible vehicle of the given type was found and the stopping
2839  // condition wasn't met.
2840  return {-1, -1};
2841 }
2842 
2843 // --- First solution decision builder ---
2844 
2845 // IntVarFilteredDecisionBuilder
2846 
2848  std::unique_ptr<IntVarFilteredHeuristic> heuristic)
2849  : heuristic_(std::move(heuristic)) {}
2850 
2852  Assignment* const assignment = heuristic_->BuildSolution();
2853  if (assignment != nullptr) {
2854  VLOG(2) << "Number of decisions: " << heuristic_->number_of_decisions();
2855  VLOG(2) << "Number of rejected decisions: "
2856  << heuristic_->number_of_rejects();
2857  assignment->Restore();
2858  } else {
2859  solver->Fail();
2860  }
2861  return nullptr;
2862 }
2863 
2865  return heuristic_->number_of_decisions();
2866 }
2867 
2869  return heuristic_->number_of_rejects();
2870 }
2871 
2873  return absl::StrCat("IntVarFilteredDecisionBuilder(",
2874  heuristic_->DebugString(), ")");
2875 }
2876 
2877 // --- First solution heuristics ---
2878 
2879 // IntVarFilteredHeuristic
2880 
2882  Solver* solver, const std::vector<IntVar*>& vars,
2883  LocalSearchFilterManager* filter_manager)
2884  : assignment_(solver->MakeAssignment()),
2885  solver_(solver),
2886  vars_(vars),
2887  delta_(solver->MakeAssignment()),
2888  is_in_delta_(vars_.size(), false),
2889  empty_(solver->MakeAssignment()),
2890  filter_manager_(filter_manager),
2891  number_of_decisions_(0),
2892  number_of_rejects_(0) {
2893  assignment_->MutableIntVarContainer()->Resize(vars_.size());
2894  delta_indices_.reserve(vars_.size());
2895 }
2896 
2898  number_of_decisions_ = 0;
2899  number_of_rejects_ = 0;
2900  // Wiping assignment when starting a new search.
2902  assignment_->MutableIntVarContainer()->Resize(vars_.size());
2903  delta_->MutableIntVarContainer()->Clear();
2905 }
2906 
2908  ResetSolution();
2909  if (!InitializeSolution()) {
2910  return nullptr;
2911  }
2913  if (BuildSolutionInternal()) {
2914  return assignment_;
2915  }
2916  return nullptr;
2917 }
2918 
2920  const std::function<int64(int64)>& next_accessor) {
2921  ResetSolution();
2923  // NOTE: We don't need to clear or pre-set the two following vectors as the
2924  // for loop below will set all elements.
2925  start_chain_ends_.resize(model()->vehicles());
2926  end_chain_starts_.resize(model()->vehicles());
2927 
2928  for (int v = 0; v < model_->vehicles(); v++) {
2929  int64 node = model_->Start(v);
2930  while (!model_->IsEnd(node)) {
2931  const int64 next = next_accessor(node);
2932  DCHECK_NE(next, node);
2933  SetValue(node, next);
2934  SetVehicleIndex(node, v);
2935  node = next;
2936  }
2937  // We relax all routes from start to end, so routes can now be extended
2938  // by inserting nodes between the start and end.
2939  start_chain_ends_[v] = model()->Start(v);
2940  end_chain_starts_[v] = model()->End(v);
2941  }
2942  if (!Commit()) {
2943  return nullptr;
2944  }
2946  if (BuildSolutionInternal()) {
2947  return assignment_;
2948  }
2949  return nullptr;
2950 }
2951 
2953  ++number_of_decisions_;
2954  const bool accept = FilterAccept();
2955  if (accept) {
2956  const Assignment::IntContainer& delta_container = delta_->IntVarContainer();
2957  const int delta_size = delta_container.Size();
2958  Assignment::IntContainer* const container =
2960  for (int i = 0; i < delta_size; ++i) {
2961  const IntVarElement& delta_element = delta_container.Element(i);
2962  IntVar* const var = delta_element.Var();
2963  DCHECK_EQ(var, vars_[delta_indices_[i]]);
2964  container->AddAtPosition(var, delta_indices_[i])
2965  ->SetValue(delta_element.Value());
2966  }
2968  } else {
2969  ++number_of_rejects_;
2970  }
2971  // Reset is_in_delta to all false.
2972  for (const int delta_index : delta_indices_) {
2973  is_in_delta_[delta_index] = false;
2974  }
2975  delta_->Clear();
2976  delta_indices_.clear();
2977  return accept;
2978 }
2979 
2981  if (filter_manager_) filter_manager_->Synchronize(assignment_, delta_);
2982 }
2983 
2984 bool IntVarFilteredHeuristic::FilterAccept() {
2985  if (!filter_manager_) return true;
2986  LocalSearchMonitor* const monitor = solver_->GetLocalSearchMonitor();
2987  return filter_manager_->Accept(monitor, delta_, empty_, kint64min, kint64max);
2988 }
2989 
2990 // RoutingFilteredHeuristic
2991 
2993  RoutingModel* model, LocalSearchFilterManager* filter_manager)
2994  : IntVarFilteredHeuristic(model->solver(), model->Nexts(), filter_manager),
2995  model_(model) {}
2996 
2997 bool RoutingFilteredHeuristic::InitializeSolution() {
2998  // Find the chains of nodes (when nodes have their "Next" value bound in the
2999  // current solution, it forms a link in a chain). Eventually, starts[end]
3000  // will contain the index of the first node of the chain ending at node 'end'
3001  // and ends[start] will be the last node of the chain starting at node
3002  // 'start'. Values of starts[node] and ends[node] for other nodes is used
3003  // for intermediary computations and do not necessarily reflect actual chain
3004  // starts and ends.
3005 
3006  // Start by adding partial start chains to current assignment.
3007  start_chain_ends_.clear();
3008  start_chain_ends_.resize(model()->vehicles(), -1);
3009  end_chain_starts_.clear();
3010  end_chain_starts_.resize(model()->vehicles(), -1);
3011 
3013  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
3014  int64 node = model()->Start(vehicle);
3015  while (!model()->IsEnd(node) && Var(node)->Bound()) {
3016  const int64 next = Var(node)->Min();
3017  SetValue(node, next);
3018  SetVehicleIndex(node, vehicle);
3019  node = next;
3020  }
3021  start_chain_ends_[vehicle] = node;
3022  }
3023 
3024  std::vector<int64> starts(Size() + model()->vehicles(), -1);
3025  std::vector<int64> ends(Size() + model()->vehicles(), -1);
3026  for (int node = 0; node < Size() + model()->vehicles(); ++node) {
3027  // Each node starts as a singleton chain.
3028  starts[node] = node;
3029  ends[node] = node;
3030  }
3031  std::vector<bool> touched(Size(), false);
3032  for (int node = 0; node < Size(); ++node) {
3033  int current = node;
3034  while (!model()->IsEnd(current) && !touched[current]) {
3035  touched[current] = true;
3036  IntVar* const next_var = Var(current);
3037  if (next_var->Bound()) {
3038  current = next_var->Value();
3039  }
3040  }
3041  // Merge the sub-chain starting from 'node' and ending at 'current' with
3042  // the existing sub-chain starting at 'current'.
3043  starts[ends[current]] = starts[node];
3044  ends[starts[node]] = ends[current];
3045  }
3046 
3047  // Set each route to be the concatenation of the chain at its starts and the
3048  // chain at its end, without nodes in between.
3049  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
3050  end_chain_starts_[vehicle] = starts[model()->End(vehicle)];
3051  int64 node = start_chain_ends_[vehicle];
3052  if (!model()->IsEnd(node)) {
3053  int64 next = starts[model()->End(vehicle)];
3054  SetValue(node, next);
3055  SetVehicleIndex(node, vehicle);
3056  node = next;
3057  while (!model()->IsEnd(node)) {
3058  next = Var(node)->Min();
3059  SetValue(node, next);
3060  SetVehicleIndex(node, vehicle);
3061  node = next;
3062  }
3063  }
3064  }
3065 
3066  if (!Commit()) {
3068  return false;
3069  }
3070  return true;
3071 }
3072 
3075  node, 1, [this, node](int alternate) {
3076  if (node != alternate && !Contains(alternate)) {
3077  SetValue(alternate, alternate);
3078  }
3079  });
3080 }
3081 
3083  for (int index = 0; index < Size(); ++index) {
3084  if (!Contains(index)) {
3085  SetValue(index, index);
3086  }
3087  }
3088 }
3089 
3091  std::vector<bool> to_make_unperformed(Size(), false);
3092  for (const auto& [pickups, deliveries] :
3093  model()->GetPickupAndDeliveryPairs()) {
3094  int64 performed_pickup = -1;
3095  for (int64 pickup : pickups) {
3096  if (Contains(pickup) && Value(pickup) != pickup) {
3097  performed_pickup = pickup;
3098  break;
3099  }
3100  }
3101  int64 performed_delivery = -1;
3102  for (int64 delivery : deliveries) {
3103  if (Contains(delivery) && Value(delivery) != delivery) {
3104  performed_delivery = delivery;
3105  break;
3106  }
3107  }
3108  if ((performed_pickup == -1) != (performed_delivery == -1)) {
3109  if (performed_pickup != -1) {
3110  to_make_unperformed[performed_pickup] = true;
3111  }
3112  if (performed_delivery != -1) {
3113  to_make_unperformed[performed_delivery] = true;
3114  }
3115  }
3116  }
3117  for (int index = 0; index < Size(); ++index) {
3118  if (to_make_unperformed[index] || !Contains(index)) continue;
3119  int64 next = Value(index);
3120  while (next < Size() && to_make_unperformed[next]) {
3121  const int64 next_of_next = Value(next);
3122  SetValue(index, next_of_next);
3123  SetValue(next, next);
3124  next = next_of_next;
3125  }
3126  }
3127 }
3128 
3129 // CheapestInsertionFilteredHeuristic
3130 
3132  RoutingModel* model, std::function<int64(int64, int64, int64)> evaluator,
3133  std::function<int64(int64)> penalty_evaluator,
3134  LocalSearchFilterManager* filter_manager)
3135  : RoutingFilteredHeuristic(model, filter_manager),
3136  evaluator_(std::move(evaluator)),
3137  penalty_evaluator_(std::move(penalty_evaluator)) {}
3138 
3139 std::vector<std::vector<CheapestInsertionFilteredHeuristic::StartEndValue>>
3141  const std::vector<int>& vehicles) {
3142  std::vector<std::vector<StartEndValue>> start_end_distances_per_node(
3143  model()->Size());
3144 
3145  for (int node = 0; node < model()->Size(); node++) {
3146  if (Contains(node)) continue;
3147  std::vector<StartEndValue>& start_end_distances =
3148  start_end_distances_per_node[node];
3149 
3150  for (const int vehicle : vehicles) {
3151  const int64 start = model()->Start(vehicle);
3152  const int64 end = model()->End(vehicle);
3153 
3154  // We compute the distance of node to the start/end nodes of the route.
3155  const int64 distance =
3156  CapAdd(model()->GetArcCostForVehicle(start, node, vehicle),
3157  model()->GetArcCostForVehicle(node, end, vehicle));
3158  start_end_distances.push_back({distance, vehicle});
3159  }
3160  // Sort the distances for the node to all start/ends of available vehicles
3161  // in decreasing order.
3162  std::sort(start_end_distances.begin(), start_end_distances.end(),
3163  [](const StartEndValue& first, const StartEndValue& second) {
3164  return second < first;
3165  });
3166  }
3167  return start_end_distances_per_node;
3168 }
3169 
3170 template <class Queue>
3172  std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3173  Queue* priority_queue) {
3174  const int num_nodes = model()->Size();
3175  DCHECK_EQ(start_end_distances_per_node->size(), num_nodes);
3176 
3177  for (int node = 0; node < num_nodes; node++) {
3178  if (Contains(node)) continue;
3179  std::vector<StartEndValue>& start_end_distances =
3180  (*start_end_distances_per_node)[node];
3181  if (start_end_distances.empty()) {
3182  continue;
3183  }
3184  // Put the best StartEndValue for this node in the priority queue.
3185  const StartEndValue& start_end_value = start_end_distances.back();
3186  priority_queue->push(std::make_pair(start_end_value, node));
3187  start_end_distances.pop_back();
3188  }
3189 }
3190 
3192  int64 predecessor,
3193  int64 successor) {
3194  SetValue(predecessor, node);
3195  SetValue(node, successor);
3197 }
3198 
3200  int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle,
3201  std::vector<ValuedPosition>* valued_positions) {
3202  CHECK(valued_positions != nullptr);
3203  int64 insert_after = start;
3204  while (!model()->IsEnd(insert_after)) {
3205  const int64 insert_before =
3206  (insert_after == start) ? next_after_start : Value(insert_after);
3207  valued_positions->push_back(std::make_pair(
3208  GetInsertionCostForNodeAtPosition(node_to_insert, insert_after,
3209  insert_before, vehicle),
3210  insert_after));
3211  insert_after = insert_before;
3212  }
3213 }
3214 
3216  int64 node_to_insert, int64 insert_after, int64 insert_before,
3217  int vehicle) const {
3218  return CapSub(CapAdd(evaluator_(insert_after, node_to_insert, vehicle),
3219  evaluator_(node_to_insert, insert_before, vehicle)),
3220  evaluator_(insert_after, insert_before, vehicle));
3221 }
3222 
3224  int64 node_to_insert) const {
3225  if (penalty_evaluator_ != nullptr) {
3226  return penalty_evaluator_(node_to_insert);
3227  }
3228  return kint64max;
3229 }
3230 
3231 namespace {
3232 template <class T>
3233 void SortAndExtractPairSeconds(std::vector<std::pair<int64, T>>* pairs,
3234  std::vector<T>* sorted_seconds) {
3235  CHECK(pairs != nullptr);
3236  CHECK(sorted_seconds != nullptr);
3237  std::sort(pairs->begin(), pairs->end());
3238  sorted_seconds->reserve(pairs->size());
3239  for (const std::pair<int64, T>& p : *pairs) {
3240  sorted_seconds->push_back(p.second);
3241  }
3242 }
3243 } // namespace
3244 
3245 // Priority queue entries used by global cheapest insertion heuristic.
3246 
3247 // Entry in priority queue containing the insertion positions of a node pair.
3249  public:
3252  : heap_index_(-1),
3253  value_(kint64max),
3254  pickup_to_insert_(pickup_to_insert),
3255  pickup_insert_after_(pickup_insert_after),
3256  delivery_to_insert_(delivery_to_insert),
3257  delivery_insert_after_(delivery_insert_after),
3258  vehicle_(vehicle) {}
3259  // Note: for compatibility reasons, comparator follows tie-breaking rules used
3260  // in the first version of GlobalCheapestInsertion.
3261  bool operator<(const PairEntry& other) const {
3262  // We first compare by value, then we favor insertions (vehicle != -1).
3263  // The rest of the tie-breaking is done with std::tie.
3264  if (value_ != other.value_) {
3265  return value_ > other.value_;
3266  }
3267  if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
3268  return vehicle_ == -1;
3269  }
3270  return std::tie(pickup_insert_after_, pickup_to_insert_,
3271  delivery_insert_after_, delivery_to_insert_, vehicle_) >
3272  std::tie(other.pickup_insert_after_, other.pickup_to_insert_,
3273  other.delivery_insert_after_, other.delivery_to_insert_,
3274  other.vehicle_);
3275  }
3276  void SetHeapIndex(int h) { heap_index_ = h; }
3277  int GetHeapIndex() const { return heap_index_; }
3278  int64 value() const { return value_; }
3279  void set_value(int64 value) { value_ = value; }
3280  int pickup_to_insert() const { return pickup_to_insert_; }
3281  int pickup_insert_after() const { return pickup_insert_after_; }
3283  pickup_insert_after_ = pickup_insert_after;
3284  }
3285  int delivery_to_insert() const { return delivery_to_insert_; }
3286  int delivery_insert_after() const { return delivery_insert_after_; }
3287  int vehicle() const { return vehicle_; }
3288  void set_vehicle(int vehicle) { vehicle_ = vehicle; }
3289 
3290  private:
3291  int heap_index_;
3292  int64 value_;
3293  const int pickup_to_insert_;
3294  int pickup_insert_after_;
3295  const int delivery_to_insert_;
3296  const int delivery_insert_after_;
3297  int vehicle_;
3298 };
3299 
3300 // Entry in priority queue containing the insertion position of a node.
3302  public:
3304  : heap_index_(-1),
3305  value_(kint64max),
3306  node_to_insert_(node_to_insert),
3307  insert_after_(insert_after),
3308  vehicle_(vehicle) {}
3309  bool operator<(const NodeEntry& other) const {
3310  // See PairEntry::operator<(), above. This one is similar.
3311  if (value_ != other.value_) {
3312  return value_ > other.value_;
3313  }
3314  if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
3315  return vehicle_ == -1;
3316  }
3317  return std::tie(insert_after_, node_to_insert_, vehicle_) >
3318  std::tie(other.insert_after_, other.node_to_insert_, other.vehicle_);
3319  }
3320  void SetHeapIndex(int h) { heap_index_ = h; }
3321  int GetHeapIndex() const { return heap_index_; }
3322  int64 value() const { return value_; }
3323  void set_value(int64 value) { value_ = value; }
3324  int node_to_insert() const { return node_to_insert_; }
3325  int insert_after() const { return insert_after_; }
3326  void set_insert_after(int insert_after) { insert_after_ = insert_after; }
3327  int vehicle() const { return vehicle_; }
3328  void set_vehicle(int vehicle) { vehicle_ = vehicle; }
3329 
3330  private:
3331  int heap_index_;
3332  int64 value_;
3333  const int node_to_insert_;
3334  int insert_after_;
3335  int vehicle_;
3336 };
3337 
3338 // GlobalCheapestInsertionFilteredHeuristic
3339 
3343  std::function<int64(int64, int64, int64)> evaluator,
3344  std::function<int64(int64)> penalty_evaluator,
3345  LocalSearchFilterManager* filter_manager,
3347  : CheapestInsertionFilteredHeuristic(model, std::move(evaluator),
3348  std::move(penalty_evaluator),
3349  filter_manager),
3350  gci_params_(parameters),
3351  node_index_to_vehicle_(model->Size(), -1),
3352  empty_vehicle_type_curator_(nullptr) {
3353  CHECK_GT(gci_params_.neighbors_ratio, 0);
3354  CHECK_LE(gci_params_.neighbors_ratio, 1);
3355  CHECK_GE(gci_params_.min_neighbors, 1);
3356 
3357  if (NumNeighbors() >= NumNonStartEndNodes() - 1) {
3358  // All nodes are neighbors, so we set the neighbors_ratio to 1 to avoid
3359  // unnecessary computations in the code.
3360  gci_params_.neighbors_ratio = 1;
3361  }
3362 
3363  if (gci_params_.neighbors_ratio == 1) {
3364  gci_params_.use_neighbors_ratio_for_initialization = false;
3365  all_nodes_.resize(model->Size());
3366  std::iota(all_nodes_.begin(), all_nodes_.end(), 0);
3367  }
3368 }
3369 
3370 void GlobalCheapestInsertionFilteredHeuristic::ComputeNeighborhoods() {
3371  if (gci_params_.neighbors_ratio == 1 ||
3372  !node_index_to_neighbors_by_cost_class_.empty()) {
3373  // Neighborhood computations not needed or already done.
3374  return;
3375  }
3376 
3377  // TODO(user): Refactor the neighborhood computations in RoutingModel.
3378  const int64 num_neighbors = NumNeighbors();
3379  // If num_neighbors was greater or equal num_non_start_end_nodes - 1,
3380  // gci_params_.neighbors_ratio should have been set to 1.
3381  DCHECK_LT(num_neighbors, NumNonStartEndNodes() - 1);
3382 
3383  const RoutingModel& routing_model = *model();
3384  const int64 size = routing_model.Size();
3385  node_index_to_neighbors_by_cost_class_.resize(size);
3386  const int num_cost_classes = routing_model.GetCostClassesCount();
3387  for (int64 node_index = 0; node_index < size; node_index++) {
3388  node_index_to_neighbors_by_cost_class_[node_index].resize(num_cost_classes);
3389  for (int cc = 0; cc < num_cost_classes; cc++) {
3390  node_index_to_neighbors_by_cost_class_[node_index][cc] =
3391  absl::make_unique<SparseBitset<int64>>(size);
3392  }
3393  }
3394 
3395  for (int64 node_index = 0; node_index < size; ++node_index) {
3396  DCHECK(!routing_model.IsEnd(node_index));
3397  if (routing_model.IsStart(node_index)) {
3398  // We don't compute neighbors for vehicle starts: all nodes are considered
3399  // neighbors for a vehicle start.
3400  continue;
3401  }
3402 
3403  // TODO(user): Use the model's IndexNeighborFinder when available.
3404  for (int cost_class = 0; cost_class < num_cost_classes; cost_class++) {
3405  if (!routing_model.HasVehicleWithCostClassIndex(
3406  RoutingCostClassIndex(cost_class))) {
3407  // No vehicle with this cost class, avoid unnecessary computations.
3408  continue;
3409  }
3410  std::vector<std::pair</*cost*/ int64, /*node*/ int64>> costed_after_nodes;
3411  costed_after_nodes.reserve(size);
3412  for (int after_node = 0; after_node < size; ++after_node) {
3413  if (after_node != node_index && !routing_model.IsStart(after_node)) {
3414  costed_after_nodes.push_back(
3415  std::make_pair(routing_model.GetArcCostForClass(
3416  node_index, after_node, cost_class),
3417  after_node));
3418  }
3419  }
3420  std::nth_element(costed_after_nodes.begin(),
3421  costed_after_nodes.begin() + num_neighbors - 1,
3422  costed_after_nodes.end());
3423  costed_after_nodes.resize(num_neighbors);
3424 
3425  for (auto [cost, neighbor] : costed_after_nodes) {
3426  node_index_to_neighbors_by_cost_class_[node_index][cost_class]->Set(
3427  neighbor);
3428 
3429  // Add reverse neighborhood.
3430  DCHECK(!routing_model.IsEnd(neighbor) &&
3431  !routing_model.IsStart(neighbor));
3432  node_index_to_neighbors_by_cost_class_[neighbor][cost_class]->Set(
3433  node_index);
3434  }
3435  // Add all vehicle starts as neighbors to this node and vice-versa.
3436  for (int vehicle = 0; vehicle < routing_model.vehicles(); vehicle++) {
3437  const int64 vehicle_start = routing_model.Start(vehicle);
3438  node_index_to_neighbors_by_cost_class_[node_index][cost_class]->Set(
3439  vehicle_start);
3440  node_index_to_neighbors_by_cost_class_[vehicle_start][cost_class]->Set(
3441  node_index);
3442  }
3443  }
3444  }
3445 }
3446 
3447 bool GlobalCheapestInsertionFilteredHeuristic::IsNeighborForCostClass(
3448  int cost_class, int64 node_index, int64 neighbor_index) const {
3449  return gci_params_.neighbors_ratio == 1 ||
3450  (*node_index_to_neighbors_by_cost_class_[node_index]
3451  [cost_class])[neighbor_index];
3452 }
3453 
3454 bool GlobalCheapestInsertionFilteredHeuristic::CheckVehicleIndices() const {
3455  std::vector<bool> node_is_visited(model()->Size(), -1);
3456  for (int v = 0; v < model()->vehicles(); v++) {
3457  for (int node = model()->Start(v); !model()->IsEnd(node);
3458  node = Value(node)) {
3459  if (node_index_to_vehicle_[node] != v) {
3460  return false;
3461  }
3462  node_is_visited[node] = true;
3463  }
3464  }
3465 
3466  for (int node = 0; node < model()->Size(); node++) {
3467  if (!node_is_visited[node] && node_index_to_vehicle_[node] != -1) {
3468  return false;
3469  }
3470  }
3471 
3472  return true;
3473 }
3474 
3476  ComputeNeighborhoods();
3477  if (empty_vehicle_type_curator_ == nullptr) {
3478  empty_vehicle_type_curator_ = absl::make_unique<VehicleTypeCurator>(
3479  model()->GetVehicleTypeContainer());
3480  }
3481  // Store all empty vehicles in the empty_vehicle_type_curator_.
3482  empty_vehicle_type_curator_->Reset(
3483  [this](int vehicle) { return VehicleIsEmpty(vehicle); });
3484  // Insert partially inserted pairs.
3485  const RoutingModel::IndexPairs& pickup_delivery_pairs =
3487  std::vector<int> pairs_to_insert;
3488  absl::flat_hash_map<int, std::vector<int>> vehicle_to_pair_nodes;
3489  for (int index = 0; index < pickup_delivery_pairs.size(); index++) {
3490  const RoutingModel::IndexPair& index_pair = pickup_delivery_pairs[index];
3491  int pickup_vehicle = -1;
3492  for (int64 pickup : index_pair.first) {
3493  if (Contains(pickup)) {
3494  pickup_vehicle = node_index_to_vehicle_[pickup];
3495  break;
3496  }
3497  }
3498  int delivery_vehicle = -1;
3499  for (int64 delivery : index_pair.second) {
3500  if (Contains(delivery)) {
3501  delivery_vehicle = node_index_to_vehicle_[delivery];
3502  break;
3503  }
3504  }
3505  if (pickup_vehicle < 0 && delivery_vehicle < 0) {
3506  pairs_to_insert.push_back(index);
3507  }
3508  if (pickup_vehicle >= 0 && delivery_vehicle < 0) {
3509  std::vector<int>& pair_nodes = vehicle_to_pair_nodes[pickup_vehicle];
3510  for (int64 delivery : index_pair.second) {
3511  pair_nodes.push_back(delivery);
3512  }
3513  }
3514  if (pickup_vehicle < 0 && delivery_vehicle >= 0) {
3515  std::vector<int>& pair_nodes = vehicle_to_pair_nodes[delivery_vehicle];
3516  for (int64 pickup : index_pair.first) {
3517  pair_nodes.push_back(pickup);
3518  }
3519  }
3520  }
3521  for (const auto& vehicle_and_nodes : vehicle_to_pair_nodes) {
3522  InsertNodesOnRoutes(vehicle_and_nodes.second, {vehicle_and_nodes.first});
3523  }
3524 
3525  InsertPairsAndNodesByRequirementTopologicalOrder();
3526 
3527  // TODO(user): Adapt the pair insertions to also support seed and
3528  // sequential insertion.
3529  InsertPairs(pairs_to_insert);
3530  std::vector<int> nodes;
3531  for (int node = 0; node < model()->Size(); ++node) {
3532  if (!Contains(node) && model()->GetPickupIndexPairs(node).empty() &&
3533  model()->GetDeliveryIndexPairs(node).empty()) {
3534  nodes.push_back(node);
3535  }
3536  }
3537  InsertFarthestNodesAsSeeds();
3538  if (gci_params_.is_sequential) {
3539  SequentialInsertNodes(nodes);
3540  } else {
3541  InsertNodesOnRoutes(nodes, {});
3542  }
3544  DCHECK(CheckVehicleIndices());
3545  return Commit();
3546 }
3547 
3548 void GlobalCheapestInsertionFilteredHeuristic::
3549  InsertPairsAndNodesByRequirementTopologicalOrder() {
3550  for (const std::vector<int>& types :
3551  model()->GetTopologicallySortedVisitTypes()) {
3552  for (int type : types) {
3553  InsertPairs(model()->GetPairIndicesOfType(type));
3554  InsertNodesOnRoutes(model()->GetSingleNodesOfType(type), {});
3555  }
3556  }
3557 }
3558 
3559 void GlobalCheapestInsertionFilteredHeuristic::InsertPairs(
3560  const std::vector<int>& pair_indices) {
3561  AdjustablePriorityQueue<PairEntry> priority_queue;
3562  std::vector<PairEntries> pickup_to_entries;
3563  std::vector<PairEntries> delivery_to_entries;
3564  InitializePairPositions(pair_indices, &priority_queue, &pickup_to_entries,
3565  &delivery_to_entries);
3566  while (!priority_queue.IsEmpty()) {
3567  if (StopSearch()) {
3568  for (PairEntry* const entry : *priority_queue.Raw()) {
3569  delete entry;
3570  }
3571  return;
3572  }
3573  PairEntry* const entry = priority_queue.Top();
3574  const int64 pickup = entry->pickup_to_insert();
3575  const int64 delivery = entry->delivery_to_insert();
3576  if (Contains(pickup) || Contains(delivery)) {
3577  DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3578  &delivery_to_entries);
3579  continue;
3580  }
3581 
3582  const int entry_vehicle = entry->vehicle();
3583  if (entry_vehicle == -1) {
3584  // Pair is unperformed.
3585  SetValue(pickup, pickup);
3586  SetValue(delivery, delivery);
3587  if (!Commit()) {
3588  DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3589  &delivery_to_entries);
3590  }
3591  continue;
3592  }
3593 
3594  // Pair is performed.
3595  if (InsertPairEntryUsingEmptyVehicleTypeCurator(
3596  pair_indices, entry, &priority_queue, &pickup_to_entries,
3597  &delivery_to_entries)) {
3598  // The entry corresponded to an insertion on an empty vehicle, which was
3599  // handled by the method.
3600  continue;
3601  }
3602 
3603  const int64 pickup_insert_after = entry->pickup_insert_after();
3604  const int64 pickup_insert_before = Value(pickup_insert_after);
3605  InsertBetween(pickup, pickup_insert_after, pickup_insert_before);
3606 
3607  const int64 delivery_insert_after = entry->delivery_insert_after();
3608  const int64 delivery_insert_before = (delivery_insert_after == pickup)
3609  ? pickup_insert_before
3610  : Value(delivery_insert_after);
3611  InsertBetween(delivery, delivery_insert_after, delivery_insert_before);
3612  if (Commit()) {
3613  UpdateAfterPairInsertion(pair_indices, entry_vehicle, pickup,
3614  pickup_insert_after, delivery,
3615  delivery_insert_after, &priority_queue,
3616  &pickup_to_entries, &delivery_to_entries);
3617  } else {
3618  DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
3619  &delivery_to_entries);
3620  }
3621  }
3622 }
3623 
3624 bool GlobalCheapestInsertionFilteredHeuristic::
3625  InsertPairEntryUsingEmptyVehicleTypeCurator(
3626  const std::vector<int>& pair_indices,
3627  GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,
3629  GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
3630  priority_queue,
3631  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
3632  pickup_to_entries,
3633  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
3634  delivery_to_entries) {
3635  const int entry_vehicle = pair_entry->vehicle();
3636  if (entry_vehicle == -1 || !VehicleIsEmpty(entry_vehicle)) {
3637  return false;
3638  }
3639 
3640  // Trying to insert on an empty vehicle.
3641  // As we only have one pair_entry per empty vehicle type, we try inserting on
3642  // all vehicles of this type with the same fixed cost, as they all have the
3643  // same insertion value.
3644  const int64 pickup = pair_entry->pickup_to_insert();
3645  const int64 delivery = pair_entry->delivery_to_insert();
3646  const int64 entry_fixed_cost = model()->GetFixedCostOfVehicle(entry_vehicle);
3647  auto vehicle_is_compatible = [this, entry_fixed_cost, pickup,
3648  delivery](int vehicle) {
3649  if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {
3650  return false;
3651  }
3652  // NOTE: Only empty vehicles should be in the vehicle_curator_.
3653  DCHECK(VehicleIsEmpty(vehicle));
3654  const int64 end = model()->End(vehicle);
3655  InsertBetween(pickup, model()->Start(vehicle), end);
3656  InsertBetween(delivery, pickup, end);
3657  return Commit();
3658  };
3659  // Since the vehicles of the same type are sorted by increasing fixed
3660  // cost by the curator, we can stop as soon as a vehicle with a fixed cost
3661  // higher than the entry_fixed_cost is found which is empty, and adapt the
3662  // pair entry with this new vehicle.
3663  auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {
3664  return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
3665  };
3666  const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
3667  empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
3668  empty_vehicle_type_curator_->Type(entry_vehicle),
3669  vehicle_is_compatible, stop_and_return_vehicle);
3670  if (compatible_vehicle >= 0) {
3671  // The pair was inserted on this vehicle.
3672  const int64 vehicle_start = model()->Start(compatible_vehicle);
3673  const int num_previous_vehicle_entries =
3674  pickup_to_entries->at(vehicle_start).size() +
3675  delivery_to_entries->at(vehicle_start).size();
3676  UpdateAfterPairInsertion(pair_indices, compatible_vehicle, pickup,
3677  vehicle_start, delivery, pickup, priority_queue,
3678  pickup_to_entries, delivery_to_entries);
3679  if (compatible_vehicle != entry_vehicle) {
3680  // The pair was inserted on another empty vehicle of the same type
3681  // and same fixed cost as entry_vehicle.
3682  // Since this vehicle is empty and has the same fixed cost as the
3683  // entry_vehicle, it shouldn't be the representative of empty vehicles
3684  // for any pickup/delivery in the priority queue.
3685  DCHECK_EQ(num_previous_vehicle_entries, 0);
3686  return true;
3687  }
3688  // The previously unused entry_vehicle is now used, so we use the next
3689  // available vehicle of the same type to compute and store insertions on
3690  // empty vehicles.
3691  const int new_empty_vehicle =
3692  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
3693  empty_vehicle_type_curator_->Type(compatible_vehicle));
3694 
3695  if (new_empty_vehicle >= 0) {
3696  DCHECK(VehicleIsEmpty(new_empty_vehicle));
3697  // Add node entries after this vehicle start for uninserted pairs which
3698  // don't have entries on this empty vehicle.
3699  UpdatePairPositions(pair_indices, new_empty_vehicle,
3700  model()->Start(new_empty_vehicle), priority_queue,
3701  pickup_to_entries, delivery_to_entries);
3702  }
3703  } else if (next_fixed_cost_empty_vehicle >= 0) {
3704  // Could not insert on this vehicle or any other vehicle of the same type
3705  // with the same fixed cost, but found an empty vehicle of this type with
3706  // higher fixed cost.
3707  DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));
3708  // Update the pair entry to correspond to an insertion on this
3709  // next_fixed_cost_empty_vehicle instead of the previous entry_vehicle.
3710  pair_entry->set_vehicle(next_fixed_cost_empty_vehicle);
3711  pickup_to_entries->at(pair_entry->pickup_insert_after()).erase(pair_entry);
3712  pair_entry->set_pickup_insert_after(
3713  model()->Start(next_fixed_cost_empty_vehicle));
3714  pickup_to_entries->at(pair_entry->pickup_insert_after()).insert(pair_entry);
3715  DCHECK_EQ(pair_entry->delivery_insert_after(), pickup);
3716  UpdatePairEntry(pair_entry, priority_queue);
3717  } else {
3718  DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
3719  delivery_to_entries);
3720  }
3721 
3722  return true;
3723 }
3724 
3725 void GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(
3726  const std::vector<int>& nodes, const absl::flat_hash_set<int>& vehicles) {
3727  AdjustablePriorityQueue<NodeEntry> priority_queue;
3728  std::vector<NodeEntries> position_to_node_entries;
3729  InitializePositions(nodes, vehicles, &priority_queue,
3730  &position_to_node_entries);
3731  // The following boolean indicates whether or not all vehicles are being
3732  // considered for insertion of the nodes simultaneously.
3733  // In the sequential version of the heuristic, as well as when inserting
3734  // single pickup or deliveries from pickup/delivery pairs, this will be false.
3735  // In the general parallel version of the heuristic, all_vehicles is true.
3736  const bool all_vehicles =
3737  vehicles.empty() || vehicles.size() == model()->vehicles();
3738 
3739  while (!priority_queue.IsEmpty()) {
3740  NodeEntry* const node_entry = priority_queue.Top();
3741  if (StopSearch()) {
3742  for (NodeEntry* const entry : *priority_queue.Raw()) {
3743  delete entry;
3744  }
3745  return;
3746  }
3747  const int64 node_to_insert = node_entry->node_to_insert();
3748  if (Contains(node_to_insert)) {
3749  DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3750  continue;
3751  }
3752 
3753  const int entry_vehicle = node_entry->vehicle();
3754  if (entry_vehicle == -1) {
3755  DCHECK(all_vehicles);
3756  // Make node unperformed.
3757  SetValue(node_to_insert, node_to_insert);
3758  if (!Commit()) {
3759  DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3760  }
3761  continue;
3762  }
3763 
3764  // Make node performed.
3765  if (InsertNodeEntryUsingEmptyVehicleTypeCurator(
3766  nodes, all_vehicles, node_entry, &priority_queue,
3767  &position_to_node_entries)) {
3768  DCHECK(all_vehicles);
3769  continue;
3770  }
3771 
3772  const int64 insert_after = node_entry->insert_after();
3773  InsertBetween(node_to_insert, insert_after, Value(insert_after));
3774  if (Commit()) {
3775  UpdatePositions(nodes, entry_vehicle, node_to_insert, all_vehicles,
3776  &priority_queue, &position_to_node_entries);
3777  UpdatePositions(nodes, entry_vehicle, insert_after, all_vehicles,
3778  &priority_queue, &position_to_node_entries);
3779  SetVehicleIndex(node_to_insert, entry_vehicle);
3780  } else {
3781  DeleteNodeEntry(node_entry, &priority_queue, &position_to_node_entries);
3782  }
3783  }
3784 }
3785 
3786 bool GlobalCheapestInsertionFilteredHeuristic::
3787  InsertNodeEntryUsingEmptyVehicleTypeCurator(
3788  const std::vector<int>& nodes, bool all_vehicles,
3789  GlobalCheapestInsertionFilteredHeuristic::NodeEntry* const node_entry,
3791  GlobalCheapestInsertionFilteredHeuristic::NodeEntry>*
3792  priority_queue,
3793  std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
3794  position_to_node_entries) {
3795  const int entry_vehicle = node_entry->vehicle();
3796  if (entry_vehicle == -1 || !all_vehicles || !VehicleIsEmpty(entry_vehicle)) {
3797  return false;
3798  }
3799 
3800  // Trying to insert on an empty vehicle, and all vehicles are being
3801  // considered simultaneously.
3802  // As we only have one node_entry per type, we try inserting on all vehicles
3803  // of this type with the same fixed cost as they all have the same insertion
3804  // value.
3805  const int64 node_to_insert = node_entry->node_to_insert();
3806  const int64 entry_fixed_cost = model()->GetFixedCostOfVehicle(entry_vehicle);
3807  auto vehicle_is_compatible = [this, entry_fixed_cost,
3808  node_to_insert](int vehicle) {
3809  if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {
3810  return false;
3811  }
3812  // NOTE: Only empty vehicles should be in the vehicle_curator_.
3813  DCHECK(VehicleIsEmpty(vehicle));
3814  InsertBetween(node_to_insert, model()->Start(vehicle),
3815  model()->End(vehicle));
3816  return Commit();
3817  };
3818  // Since the vehicles of the same type are sorted by increasing fixed
3819  // cost by the curator, we can stop as soon as an empty vehicle with a fixed
3820  // cost higher than the entry_fixed_cost is found, and add new entries for
3821  // this new vehicle.
3822  auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {
3823  return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
3824  };
3825  const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
3826  empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
3827  empty_vehicle_type_curator_->Type(entry_vehicle),
3828  vehicle_is_compatible, stop_and_return_vehicle);
3829  if (compatible_vehicle >= 0) {
3830  // The node was inserted on this vehicle.
3831  UpdatePositions(nodes, compatible_vehicle, node_to_insert, all_vehicles,
3832  priority_queue, position_to_node_entries);
3833  const int64 compatible_start = model()->Start(compatible_vehicle);
3834  const bool no_prior_entries_for_this_vehicle =
3835  position_to_node_entries->at(compatible_start).empty();
3836  UpdatePositions(nodes, compatible_vehicle, compatible_start, all_vehicles,
3837  priority_queue, position_to_node_entries);
3838  SetVehicleIndex(node_to_insert, compatible_vehicle);
3839  if (compatible_vehicle != entry_vehicle) {
3840  // The node was inserted on another empty vehicle of the same type
3841  // and same fixed cost as entry_vehicle.
3842  // Since this vehicle is empty and has the same fixed cost as the
3843  // entry_vehicle, it shouldn't be the representative of empty vehicles
3844  // for any node in the priority queue.
3845  DCHECK(no_prior_entries_for_this_vehicle);
3846  return true;
3847  }
3848  // The previously unused entry_vehicle is now used, so we use the next
3849  // available vehicle of the same type to compute and store insertions on
3850  // empty vehicles.
3851  const int new_empty_vehicle =
3852  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
3853  empty_vehicle_type_curator_->Type(compatible_vehicle));
3854 
3855  if (new_empty_vehicle >= 0) {
3856  DCHECK(VehicleIsEmpty(new_empty_vehicle));
3857  // Add node entries after this vehicle start for uninserted nodes which
3858  // don't have entries on this empty vehicle.
3859  UpdatePositions(nodes, new_empty_vehicle,
3860  model()->Start(new_empty_vehicle), all_vehicles,
3861  priority_queue, position_to_node_entries);
3862  }
3863  } else if (next_fixed_cost_empty_vehicle >= 0) {
3864  // Could not insert on this vehicle or any other vehicle of the same
3865  // type with the same fixed cost, but found an empty vehicle of this type
3866  // with higher fixed cost.
3867  DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));
3868  // Update the insertion entry to be on next_empty_vehicle instead of the
3869  // previous entry_vehicle.
3870  position_to_node_entries->at(node_entry->insert_after()).erase(node_entry);
3871  node_entry->set_insert_after(model()->Start(next_fixed_cost_empty_vehicle));
3872  position_to_node_entries->at(node_entry->insert_after()).insert(node_entry);
3873  node_entry->set_vehicle(next_fixed_cost_empty_vehicle);
3874  UpdateNodeEntry(node_entry, priority_queue);
3875  } else {
3876  DeleteNodeEntry(node_entry, priority_queue, position_to_node_entries);
3877  }
3878 
3879  return true;
3880 }
3881 
3882 void GlobalCheapestInsertionFilteredHeuristic::SequentialInsertNodes(
3883  const std::vector<int>& nodes) {
3884  std::vector<bool> is_vehicle_used;
3885  absl::flat_hash_set<int> used_vehicles;
3886  std::vector<int> unused_vehicles;
3887 
3888  DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
3889  if (!used_vehicles.empty()) {
3890  InsertNodesOnRoutes(nodes, used_vehicles);
3891  }
3892 
3893  std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
3894  ComputeStartEndDistanceForVehicles(unused_vehicles);
3895  std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed>>
3896  first_node_queue;
3897  InitializePriorityQueue(&start_end_distances_per_node, &first_node_queue);
3898 
3899  int vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
3900  &is_vehicle_used);
3901 
3902  while (vehicle >= 0) {
3903  InsertNodesOnRoutes(nodes, {vehicle});
3904  vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
3905  &is_vehicle_used);
3906  }
3907 }
3908 
3909 void GlobalCheapestInsertionFilteredHeuristic::DetectUsedVehicles(
3910  std::vector<bool>* is_vehicle_used, std::vector<int>* unused_vehicles,
3911  absl::flat_hash_set<int>* used_vehicles) {
3912  is_vehicle_used->clear();
3913  is_vehicle_used->resize(model()->vehicles());
3914 
3915  used_vehicles->clear();
3916  used_vehicles->reserve(model()->vehicles());
3917 
3918  unused_vehicles->clear();
3919  unused_vehicles->reserve(model()->vehicles());
3920 
3921  for (int vehicle = 0; vehicle < model()->vehicles(); vehicle++) {
3922  if (!VehicleIsEmpty(vehicle)) {
3923  (*is_vehicle_used)[vehicle] = true;
3924  used_vehicles->insert(vehicle);
3925  } else {
3926  (*is_vehicle_used)[vehicle] = false;
3927  unused_vehicles->push_back(vehicle);
3928  }
3929  }
3930 }
3931 
3932 void GlobalCheapestInsertionFilteredHeuristic::InsertFarthestNodesAsSeeds() {
3933  if (gci_params_.farthest_seeds_ratio <= 0) return;
3934  // Insert at least 1 farthest Seed if the parameter is positive.
3935  const int num_seeds = static_cast<int>(
3936  std::ceil(gci_params_.farthest_seeds_ratio * model()->vehicles()));
3937 
3938  std::vector<bool> is_vehicle_used;
3939  absl::flat_hash_set<int> used_vehicles;
3940  std::vector<int> unused_vehicles;
3941  DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
3942  std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
3943  ComputeStartEndDistanceForVehicles(unused_vehicles);
3944 
3945  // Priority queue where the Seeds with a larger distance are given higher
3946  // priority.
3947  std::priority_queue<Seed> farthest_node_queue;
3948  InitializePriorityQueue(&start_end_distances_per_node, &farthest_node_queue);
3949 
3950  int inserted_seeds = 0;
3951  while (!farthest_node_queue.empty() && inserted_seeds < num_seeds) {
3952  InsertSeedNode(&start_end_distances_per_node, &farthest_node_queue,
3953  &is_vehicle_used);
3954  inserted_seeds++;
3955  }
3956 
3957  // NOTE: As we don't use the empty_vehicle_type_curator_ when inserting seed
3958  // nodes on routes, some previously empty vehicles may now be used, so we
3959  // update the curator accordingly to ensure it still only stores empty
3960  // vehicles.
3961  DCHECK(empty_vehicle_type_curator_ != nullptr);
3962  empty_vehicle_type_curator_->Update(
3963  [this](int vehicle) { return !VehicleIsEmpty(vehicle); });
3964 }
3965 
3966 template <class Queue>
3967 int GlobalCheapestInsertionFilteredHeuristic::InsertSeedNode(
3968  std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3969  Queue* priority_queue, std::vector<bool>* is_vehicle_used) {
3970  while (!priority_queue->empty()) {
3971  if (StopSearch()) break;
3972  const Seed& seed = priority_queue->top();
3973 
3974  const int seed_node = seed.second;
3975  const int seed_vehicle = seed.first.vehicle;
3976 
3977  std::vector<StartEndValue>& other_start_end_values =
3978  (*start_end_distances_per_node)[seed_node];
3979 
3980  if (Contains(seed_node)) {
3981  // The node is already inserted, it is therefore no longer considered as
3982  // a potential seed.
3983  priority_queue->pop();
3984  other_start_end_values.clear();
3985  continue;
3986  }
3987  if (!(*is_vehicle_used)[seed_vehicle]) {
3988  // Try to insert this seed_node on this vehicle's route.
3989  const int64 start = model()->Start(seed_vehicle);
3990  const int64 end = model()->End(seed_vehicle);
3991  DCHECK_EQ(Value(start), end);
3992  InsertBetween(seed_node, start, end);
3993  if (Commit()) {
3994  priority_queue->pop();
3995  (*is_vehicle_used)[seed_vehicle] = true;
3996  other_start_end_values.clear();
3997  SetVehicleIndex(seed_node, seed_vehicle);
3998  return seed_vehicle;
3999  }
4000  }
4001  // Either the vehicle is already used, or the Commit() wasn't successful.
4002  // In both cases, we remove this Seed from the priority queue, and insert
4003  // the next StartEndValue from start_end_distances_per_node[seed_node]
4004  // in the priority queue.
4005  priority_queue->pop();
4006  if (!other_start_end_values.empty()) {
4007  const StartEndValue& next_seed_value = other_start_end_values.back();
4008  priority_queue->push(std::make_pair(next_seed_value, seed_node));
4009  other_start_end_values.pop_back();
4010  }
4011  }
4012  // No seed node was inserted.
4013  return -1;
4014 }
4015 
4016 void GlobalCheapestInsertionFilteredHeuristic::InitializePairPositions(
4017  const std::vector<int>& pair_indices,
4019  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4020  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4021  pickup_to_entries,
4022  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4023  delivery_to_entries) {
4024  priority_queue->Clear();
4025  pickup_to_entries->clear();
4026  pickup_to_entries->resize(model()->Size());
4027  delivery_to_entries->clear();
4028  delivery_to_entries->resize(model()->Size());
4029  const RoutingModel::IndexPairs& pickup_delivery_pairs =
4031  for (int index : pair_indices) {
4032  const RoutingModel::IndexPair& index_pair = pickup_delivery_pairs[index];
4033  for (int64 pickup : index_pair.first) {
4034  if (Contains(pickup)) continue;
4035  for (int64 delivery : index_pair.second) {
4036  if (Contains(delivery)) continue;
4037  // Add insertion entry making pair unperformed. When the pair is part
4038  // of a disjunction we do not try to make any of its pairs unperformed
4039  // as it requires having an entry with all pairs being unperformed.
4040  // TODO(user): Adapt the code to make pair disjunctions unperformed.
4041  if (gci_params_.add_unperformed_entries &&
4042  index_pair.first.size() == 1 && index_pair.second.size() == 1 &&
4043  GetUnperformedValue(pickup) != kint64max &&
4044  GetUnperformedValue(delivery) != kint64max) {
4045  AddPairEntry(pickup, -1, delivery, -1, -1, priority_queue, nullptr,
4046  nullptr);
4047  }
4048  // Add all other insertion entries with pair performed.
4049  InitializeInsertionEntriesPerformingPair(
4050  pickup, delivery, priority_queue, pickup_to_entries,
4051  delivery_to_entries);
4052  }
4053  }
4054  }
4055 }
4056 
4057 void GlobalCheapestInsertionFilteredHeuristic::
4058  InitializeInsertionEntriesPerformingPair(
4059  int64 pickup, int64 delivery,
4061  GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
4062  priority_queue,
4063  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4064  pickup_to_entries,
4065  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4066  delivery_to_entries) {
4067  if (!gci_params_.use_neighbors_ratio_for_initialization) {
4068  std::vector<std::pair<std::pair<int64, int>, std::pair<int64, int64>>>
4069  valued_positions;
4070  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
4071  if (VehicleIsEmpty(vehicle) &&
4072  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4073  empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4074  // We only consider the least expensive empty vehicle of each type for
4075  // entries.
4076  continue;
4077  }
4078  const int64 start = model()->Start(vehicle);
4079  std::vector<ValuedPosition> valued_pickup_positions;
4080  AppendEvaluatedPositionsAfter(pickup, start, Value(start), vehicle,
4081  &valued_pickup_positions);
4082  for (const ValuedPosition& valued_pickup_position :
4083  valued_pickup_positions) {
4084  const int64 pickup_position = valued_pickup_position.second;
4085  CHECK(!model()->IsEnd(pickup_position));
4086  std::vector<ValuedPosition> valued_delivery_positions;
4087  AppendEvaluatedPositionsAfter(delivery, pickup, Value(pickup_position),
4088  vehicle, &valued_delivery_positions);
4089  for (const ValuedPosition& valued_delivery_position :
4090  valued_delivery_positions) {
4091  valued_positions.push_back(std::make_pair(
4092  std::make_pair(CapAdd(valued_pickup_position.first,
4093  valued_delivery_position.first),
4094  vehicle),
4095  std::make_pair(pickup_position,
4096  valued_delivery_position.second)));
4097  }
4098  }
4099  }
4100  for (const auto& [cost_for_vehicle, pair_positions] : valued_positions) {
4101  DCHECK_NE(pair_positions.first, pair_positions.second);
4102  AddPairEntry(pickup, pair_positions.first, delivery,
4103  pair_positions.second, cost_for_vehicle.second,
4104  priority_queue, pickup_to_entries, delivery_to_entries);
4105  }
4106  return;
4107  }
4108 
4109  // We're only considering the closest neighbors as insertion positions for
4110  // the pickup/delivery pair.
4111  for (int cost_class = 0; cost_class < model()->GetCostClassesCount();
4112  cost_class++) {
4113  absl::flat_hash_set<std::pair<int64, int64>> existing_insertion_positions;
4114  // Explore the neighborhood of the pickup.
4115  for (const int64 pickup_insert_after :
4116  GetNeighborsOfNodeForCostClass(cost_class, pickup)) {
4117  if (!Contains(pickup_insert_after)) {
4118  continue;
4119  }
4120  const int vehicle = node_index_to_vehicle_[pickup_insert_after];
4121  if (model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
4122  continue;
4123  }
4124 
4125  if (VehicleIsEmpty(vehicle) &&
4126  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4127  empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4128  // We only consider the least expensive empty vehicle of each type for
4129  // entries.
4130  continue;
4131  }
4132 
4133  int64 delivery_insert_after = pickup;
4134  while (!model()->IsEnd(delivery_insert_after)) {
4135  const std::pair<int64, int64> insertion_position = {
4136  pickup_insert_after, delivery_insert_after};
4137  DCHECK(!gtl::ContainsKey(existing_insertion_positions,
4138  insertion_position));
4139  existing_insertion_positions.insert(insertion_position);
4140 
4141  AddPairEntry(pickup, pickup_insert_after, delivery,
4142  delivery_insert_after, vehicle, priority_queue,
4143  pickup_to_entries, delivery_to_entries);
4144  delivery_insert_after = (delivery_insert_after == pickup)
4145  ? Value(pickup_insert_after)
4146  : Value(delivery_insert_after);
4147  }
4148  }
4149 
4150  // Explore the neighborhood of the delivery.
4151  for (const int64 delivery_insert_after :
4152  GetNeighborsOfNodeForCostClass(cost_class, delivery)) {
4153  if (!Contains(delivery_insert_after)) {
4154  continue;
4155  }
4156  const int vehicle = node_index_to_vehicle_[delivery_insert_after];
4157  if (model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
4158  continue;
4159  }
4160 
4161  if (VehicleIsEmpty(vehicle)) {
4162  // Vehicle is empty.
4163  DCHECK_EQ(delivery_insert_after, model()->Start(vehicle));
4164  }
4165 
4166  int64 pickup_insert_after = model()->Start(vehicle);
4167  while (pickup_insert_after != delivery_insert_after) {
4168  if (!gtl::ContainsKey(
4169  existing_insertion_positions,
4170  std::make_pair(pickup_insert_after, delivery_insert_after))) {
4171  AddPairEntry(pickup, pickup_insert_after, delivery,
4172  delivery_insert_after, vehicle, priority_queue,
4173  pickup_to_entries, delivery_to_entries);
4174  }
4175  pickup_insert_after = Value(pickup_insert_after);
4176  }
4177  }
4178  }
4179 }
4180 
4181 void GlobalCheapestInsertionFilteredHeuristic::UpdateAfterPairInsertion(
4182  const std::vector<int>& pair_indices, int vehicle, int64 pickup,
4183  int64 pickup_position, int64 delivery, int64 delivery_position,
4184  AdjustablePriorityQueue<PairEntry>* priority_queue,
4185  std::vector<PairEntries>* pickup_to_entries,
4186  std::vector<PairEntries>* delivery_to_entries) {
4187  UpdatePairPositions(pair_indices, vehicle, pickup_position, priority_queue,
4188  pickup_to_entries, delivery_to_entries);
4189  UpdatePairPositions(pair_indices, vehicle, pickup, priority_queue,
4190  pickup_to_entries, delivery_to_entries);
4191  UpdatePairPositions(pair_indices, vehicle, delivery, priority_queue,
4192  pickup_to_entries, delivery_to_entries);
4193  if (delivery_position != pickup) {
4194  UpdatePairPositions(pair_indices, vehicle, delivery_position,
4195  priority_queue, pickup_to_entries, delivery_to_entries);
4196  }
4197  SetVehicleIndex(pickup, vehicle);
4198  SetVehicleIndex(delivery, vehicle);
4199 }
4200 
4201 void GlobalCheapestInsertionFilteredHeuristic::UpdatePickupPositions(
4202  const std::vector<int>& pair_indices, int vehicle,
4203  int64 pickup_insert_after,
4205  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4206  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4207  pickup_to_entries,
4208  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4209  delivery_to_entries) {
4210  // First, remove entries which have already been inserted and keep track of
4211  // the entries which are being kept and must be updated.
4212  using Pair = std::pair<int64, int64>;
4213  using Insertion = std::pair<Pair, /*delivery_insert_after*/ int64>;
4214  absl::flat_hash_set<Insertion> existing_insertions;
4215  std::vector<PairEntry*> to_remove;
4216  for (PairEntry* const pair_entry :
4217  pickup_to_entries->at(pickup_insert_after)) {
4218  DCHECK(priority_queue->Contains(pair_entry));
4219  DCHECK_EQ(pair_entry->pickup_insert_after(), pickup_insert_after);
4220  if (Contains(pair_entry->pickup_to_insert()) ||
4221  Contains(pair_entry->delivery_to_insert())) {
4222  to_remove.push_back(pair_entry);
4223  } else {
4224  DCHECK(delivery_to_entries->at(pair_entry->delivery_insert_after())
4225  .contains(pair_entry));
4226  UpdatePairEntry(pair_entry, priority_queue);
4227  existing_insertions.insert(
4228  {{pair_entry->pickup_to_insert(), pair_entry->delivery_to_insert()},
4229  pair_entry->delivery_insert_after()});
4230  }
4231  }
4232  for (PairEntry* const pair_entry : to_remove) {
4233  DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
4234  delivery_to_entries);
4235  }
4236  // Create new entries for which the pickup is to be inserted after
4237  // pickup_insert_after.
4238  const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
4239  const int64 pickup_insert_before = Value(pickup_insert_after);
4240  const RoutingModel::IndexPairs& pickup_delivery_pairs =
4242  for (int pair_index : pair_indices) {
4243  const RoutingModel::IndexPair& index_pair =
4244  pickup_delivery_pairs[pair_index];
4245  for (int64 pickup : index_pair.first) {
4246  if (Contains(pickup) ||
4247  !IsNeighborForCostClass(cost_class, pickup_insert_after, pickup)) {
4248  continue;
4249  }
4250  for (int64 delivery : index_pair.second) {
4251  if (Contains(delivery)) {
4252  continue;
4253  }
4254  int64 delivery_insert_after = pickup;
4255  while (!model()->IsEnd(delivery_insert_after)) {
4256  const Insertion insertion = {{pickup, delivery},
4257  delivery_insert_after};
4258  if (!gtl::ContainsKey(existing_insertions, insertion)) {
4259  AddPairEntry(pickup, pickup_insert_after, delivery,
4260  delivery_insert_after, vehicle, priority_queue,
4261  pickup_to_entries, delivery_to_entries);
4262  }
4263  if (delivery_insert_after == pickup) {
4264  delivery_insert_after = pickup_insert_before;
4265  } else {
4266  delivery_insert_after = Value(delivery_insert_after);
4267  }
4268  }
4269  }
4270  }
4271  }
4272 }
4273 
4274 void GlobalCheapestInsertionFilteredHeuristic::UpdateDeliveryPositions(
4275  const std::vector<int>& pair_indices, int vehicle,
4276  int64 delivery_insert_after,
4278  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4279  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4280  pickup_to_entries,
4281  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4282  delivery_to_entries) {
4283  // First, remove entries which have already been inserted and keep track of
4284  // the entries which are being kept and must be updated.
4285  using Pair = std::pair<int64, int64>;
4286  using Insertion = std::pair<Pair, /*pickup_insert_after*/ int64>;
4287  absl::flat_hash_set<Insertion> existing_insertions;
4288  std::vector<PairEntry*> to_remove;
4289  for (PairEntry* const pair_entry :
4290  delivery_to_entries->at(delivery_insert_after)) {
4291  DCHECK(priority_queue->Contains(pair_entry));
4292  DCHECK_EQ(pair_entry->delivery_insert_after(), delivery_insert_after);
4293  if (Contains(pair_entry->pickup_to_insert()) ||
4294  Contains(pair_entry->delivery_to_insert())) {
4295  to_remove.push_back(pair_entry);
4296  } else {
4297  DCHECK(pickup_to_entries->at(pair_entry->pickup_insert_after())
4298  .contains(pair_entry));
4299  existing_insertions.insert(
4300  {{pair_entry->pickup_to_insert(), pair_entry->delivery_to_insert()},
4301  pair_entry->pickup_insert_after()});
4302  UpdatePairEntry(pair_entry, priority_queue);
4303  }
4304  }
4305  for (PairEntry* const pair_entry : to_remove) {
4306  DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
4307  delivery_to_entries);
4308  }
4309  // Create new entries for which the delivery is to be inserted after
4310  // delivery_insert_after.
4311  const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
4312  const RoutingModel::IndexPairs& pickup_delivery_pairs =
4314  for (int pair_index : pair_indices) {
4315  const RoutingModel::IndexPair& index_pair =
4316  pickup_delivery_pairs[pair_index];
4317  for (int64 delivery : index_pair.second) {
4318  if (Contains(delivery) ||
4319  !IsNeighborForCostClass(cost_class, delivery_insert_after,
4320  delivery)) {
4321  continue;
4322  }
4323  for (int64 pickup : index_pair.first) {
4324  if (Contains(pickup)) {
4325  continue;
4326  }
4327  int64 pickup_insert_after = model()->Start(vehicle);
4328  while (pickup_insert_after != delivery_insert_after) {
4329  const Insertion insertion = {{pickup, delivery}, pickup_insert_after};
4330  if (!gtl::ContainsKey(existing_insertions, insertion)) {
4331  AddPairEntry(pickup, pickup_insert_after, delivery,
4332  delivery_insert_after, vehicle, priority_queue,
4333  pickup_to_entries, delivery_to_entries);
4334  }
4335  pickup_insert_after = Value(pickup_insert_after);
4336  }
4337  }
4338  }
4339  }
4340 }
4341 
4342 void GlobalCheapestInsertionFilteredHeuristic::DeletePairEntry(
4343  GlobalCheapestInsertionFilteredHeuristic::PairEntry* entry,
4345  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4346  std::vector<PairEntries>* pickup_to_entries,
4347  std::vector<PairEntries>* delivery_to_entries) {
4348  priority_queue->Remove(entry);
4349  if (entry->pickup_insert_after() != -1) {
4350  pickup_to_entries->at(entry->pickup_insert_after()).erase(entry);
4351  }
4352  if (entry->delivery_insert_after() != -1) {
4353  delivery_to_entries->at(entry->delivery_insert_after()).erase(entry);
4354  }
4355  delete entry;
4356 }
4357 
4358 void GlobalCheapestInsertionFilteredHeuristic::AddPairEntry(
4359  int64 pickup, int64 pickup_insert_after, int64 delivery,
4360  int64 delivery_insert_after, int vehicle,
4362  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
4363  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4364  pickup_entries,
4365  std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
4366  delivery_entries) const {
4367  if (pickup_insert_after == -1) {
4368  DCHECK_EQ(delivery_insert_after, -1);
4369  DCHECK_EQ(vehicle, -1);
4370  PairEntry* pair_entry = new PairEntry(pickup, -1, delivery, -1, -1);
4371  pair_entry->set_value(
4372  absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4373  ? 0
4374  : CapAdd(GetUnperformedValue(pickup),
4375  GetUnperformedValue(delivery)));
4376  priority_queue->Add(pair_entry);
4377  return;
4378  }
4379 
4380  PairEntry* const pair_entry = new PairEntry(
4381  pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle);
4382  pair_entry->set_value(GetInsertionValueForPairAtPositions(
4383  pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle));
4384 
4385  // Add entry to priority_queue and pickup_/delivery_entries.
4386  DCHECK(!priority_queue->Contains(pair_entry));
4387  pickup_entries->at(pickup_insert_after).insert(pair_entry);
4388  delivery_entries->at(delivery_insert_after).insert(pair_entry);
4389  priority_queue->Add(pair_entry);
4390 }
4391 
4392 void GlobalCheapestInsertionFilteredHeuristic::UpdatePairEntry(
4393  GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,
4395  GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue)
4396  const {
4397  pair_entry->set_value(GetInsertionValueForPairAtPositions(
4398  pair_entry->pickup_to_insert(), pair_entry->pickup_insert_after(),
4399  pair_entry->delivery_to_insert(), pair_entry->delivery_insert_after(),
4400  pair_entry->vehicle()));
4401 
4402  // Update the priority_queue.
4403  DCHECK(priority_queue->Contains(pair_entry));
4404  priority_queue->NoteChangedPriority(pair_entry);
4405 }
4406 
4407 int64 GlobalCheapestInsertionFilteredHeuristic::
4408  GetInsertionValueForPairAtPositions(int64 pickup, int64 pickup_insert_after,
4409  int64 delivery,
4410  int64 delivery_insert_after,
4411  int vehicle) const {
4412  DCHECK_GE(pickup_insert_after, 0);
4413  const int64 pickup_insert_before = Value(pickup_insert_after);
4414  const int64 pickup_value = GetInsertionCostForNodeAtPosition(
4415  pickup, pickup_insert_after, pickup_insert_before, vehicle);
4416 
4417  DCHECK_GE(delivery_insert_after, 0);
4418  const int64 delivery_insert_before = (delivery_insert_after == pickup)
4419  ? pickup_insert_before
4420  : Value(delivery_insert_after);
4421  const int64 delivery_value = GetInsertionCostForNodeAtPosition(
4422  delivery, delivery_insert_after, delivery_insert_before, vehicle);
4423 
4424  const int64 penalty_shift =
4425  absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4426  ? CapAdd(GetUnperformedValue(pickup), GetUnperformedValue(delivery))
4427  : 0;
4428  return CapSub(CapAdd(pickup_value, delivery_value), penalty_shift);
4429 }
4430 
4431 void GlobalCheapestInsertionFilteredHeuristic::InitializePositions(
4432  const std::vector<int>& nodes, const absl::flat_hash_set<int>& vehicles,
4434  GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4435  std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4436  position_to_node_entries) {
4437  priority_queue->Clear();
4438  position_to_node_entries->clear();
4439  position_to_node_entries->resize(model()->Size());
4440 
4441  const int num_vehicles =
4442  vehicles.empty() ? model()->vehicles() : vehicles.size();
4443  const bool all_vehicles = (num_vehicles == model()->vehicles());
4444 
4445  for (int node : nodes) {
4446  if (Contains(node)) {
4447  continue;
4448  }
4449  // Add insertion entry making node unperformed.
4450  if (gci_params_.add_unperformed_entries &&
4451  GetUnperformedValue(node) != kint64max) {
4452  AddNodeEntry(node, -1, -1, all_vehicles, priority_queue, nullptr);
4453  }
4454  // Add all insertion entries making node performed.
4455  InitializeInsertionEntriesPerformingNode(node, vehicles, priority_queue,
4456  position_to_node_entries);
4457  }
4458 }
4459 
4460 void GlobalCheapestInsertionFilteredHeuristic::
4461  InitializeInsertionEntriesPerformingNode(
4462  int64 node, const absl::flat_hash_set<int>& vehicles,
4464  GlobalCheapestInsertionFilteredHeuristic::NodeEntry>*
4465  priority_queue,
4466  std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4467  position_to_node_entries) {
4468  const int num_vehicles =
4469  vehicles.empty() ? model()->vehicles() : vehicles.size();
4470  const bool all_vehicles = (num_vehicles == model()->vehicles());
4471 
4472  if (!gci_params_.use_neighbors_ratio_for_initialization) {
4473  auto vehicles_it = vehicles.begin();
4474  for (int v = 0; v < num_vehicles; v++) {
4475  const int vehicle = vehicles.empty() ? v : *vehicles_it++;
4476 
4477  const int64 start = model()->Start(vehicle);
4478  if (all_vehicles && VehicleIsEmpty(vehicle) &&
4479  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4480  empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4481  // We only consider the least expensive empty vehicle of each type for
4482  // entries.
4483  continue;
4484  }
4485  std::vector<ValuedPosition> valued_positions;
4486  AppendEvaluatedPositionsAfter(node, start, Value(start), vehicle,
4487  &valued_positions);
4488  for (const std::pair<int64, int64>& valued_position : valued_positions) {
4489  AddNodeEntry(node, valued_position.second, vehicle, all_vehicles,
4490  priority_queue, position_to_node_entries);
4491  }
4492  }
4493  return;
4494  }
4495 
4496  // We're only considering the closest neighbors as insertion positions for
4497  // the node.
4498  const auto insert_on_vehicle_for_cost_class = [this, &vehicles, all_vehicles](
4499  int v, int cost_class) {
4500  return (model()->GetCostClassIndexOfVehicle(v).value() == cost_class) &&
4501  (all_vehicles || vehicles.contains(v));
4502  };
4503  for (int cost_class = 0; cost_class < model()->GetCostClassesCount();
4504  cost_class++) {
4505  for (const int64 insert_after :
4506  GetNeighborsOfNodeForCostClass(cost_class, node)) {
4507  if (!Contains(insert_after)) {
4508  continue;
4509  }
4510  const int vehicle = node_index_to_vehicle_[insert_after];
4511  if (vehicle == -1 ||
4512  !insert_on_vehicle_for_cost_class(vehicle, cost_class)) {
4513  continue;
4514  }
4515  if (all_vehicles && VehicleIsEmpty(vehicle) &&
4516  empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
4517  empty_vehicle_type_curator_->Type(vehicle)) != vehicle) {
4518  // We only consider the least expensive empty vehicle of each type for
4519  // entries.
4520  continue;
4521  }
4522  AddNodeEntry(node, insert_after, vehicle, all_vehicles, priority_queue,
4523  position_to_node_entries);
4524  }
4525  }
4526 }
4527 
4528 void GlobalCheapestInsertionFilteredHeuristic::UpdatePositions(
4529  const std::vector<int>& nodes, int vehicle, int64 insert_after,
4530  bool all_vehicles,
4532  GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4533  std::vector<GlobalCheapestInsertionFilteredHeuristic::NodeEntries>*
4534  node_entries) {
4535  // Either create new entries if we are inserting after a newly inserted node
4536  // or remove entries which have already been inserted.
4537  std::vector<NodeEntry*> to_remove;
4538  absl::flat_hash_set<int> existing_insertions;
4539  for (NodeEntry* const node_entry : node_entries->at(insert_after)) {
4540  DCHECK_EQ(node_entry->insert_after(), insert_after);
4541  const int64 node_to_insert = node_entry->node_to_insert();
4542  if (Contains(node_to_insert)) {
4543  to_remove.push_back(node_entry);
4544  } else {
4545  UpdateNodeEntry(node_entry, priority_queue);
4546  existing_insertions.insert(node_to_insert);
4547  }
4548  }
4549  for (NodeEntry* const node_entry : to_remove) {
4550  DeleteNodeEntry(node_entry, priority_queue, node_entries);
4551  }
4552  const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
4553  for (int node_to_insert : nodes) {
4554  if (!Contains(node_to_insert) &&
4555  !existing_insertions.contains(node_to_insert) &&
4556  IsNeighborForCostClass(cost_class, insert_after, node_to_insert)) {
4557  AddNodeEntry(node_to_insert, insert_after, vehicle, all_vehicles,
4558  priority_queue, node_entries);
4559  }
4560  }
4561 }
4562 
4563 void GlobalCheapestInsertionFilteredHeuristic::DeleteNodeEntry(
4564  GlobalCheapestInsertionFilteredHeuristic::NodeEntry* entry,
4566  GlobalCheapestInsertionFilteredHeuristic::NodeEntry>* priority_queue,
4567  std::vector<NodeEntries>* node_entries) {
4568  priority_queue->Remove(entry);
4569  if (entry->insert_after() != -1) {
4570  node_entries->at(entry->insert_after()).erase(entry);
4571  }
4572  delete entry;
4573 }
4574 
4575 void GlobalCheapestInsertionFilteredHeuristic::AddNodeEntry(
4576  int64 node, int64 insert_after, int vehicle, bool all_vehicles,
4577  AdjustablePriorityQueue<NodeEntry>* priority_queue,
4578  std::vector<NodeEntries>* node_entries) const {
4579  const int64 node_penalty = GetUnperformedValue(node);
4580  const int64 penalty_shift =
4581  absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4582  ? node_penalty
4583  : 0;
4584  if (insert_after == -1) {
4585  DCHECK_EQ(vehicle, -1);
4586  if (!all_vehicles) {
4587  // NOTE: In the case where we're not considering all routes
4588  // simultaneously, we don't add insertion entries making nodes
4589  // unperformed.
4590  return;
4591  }
4592  NodeEntry* const node_entry = new NodeEntry(node, -1, -1);
4593  node_entry->set_value(CapSub(node_penalty, penalty_shift));
4594  priority_queue->Add(node_entry);
4595  return;
4596  }
4597 
4598  const int64 insertion_cost = GetInsertionCostForNodeAtPosition(
4599  node, insert_after, Value(insert_after), vehicle);
4600  if (!all_vehicles && insertion_cost > node_penalty) {
4601  // NOTE: When all vehicles aren't considered for insertion, we don't
4602  // add entries making nodes unperformed, so we don't add insertions
4603  // which cost more than the node penalty either.
4604  return;
4605  }
4606 
4607  NodeEntry* const node_entry = new NodeEntry(node, insert_after, vehicle);
4608  node_entry->set_value(CapSub(insertion_cost, penalty_shift));
4609  // Add entry to priority_queue and node_entries.
4610  DCHECK(!priority_queue->Contains(node_entry));
4611  node_entries->at(insert_after).insert(node_entry);
4612  priority_queue->Add(node_entry);
4613 }
4614 
4615 void GlobalCheapestInsertionFilteredHeuristic::UpdateNodeEntry(
4616  NodeEntry* const node_entry,
4617  AdjustablePriorityQueue<NodeEntry>* priority_queue) const {
4618  const int64 node = node_entry->node_to_insert();
4619  const int64 insert_after = node_entry->insert_after();
4620  DCHECK_GE(insert_after, 0);
4621  const int64 insertion_cost = GetInsertionCostForNodeAtPosition(
4622  node, insert_after, Value(insert_after), node_entry->vehicle());
4623  const int64 penalty_shift =
4624  absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
4625  ? GetUnperformedValue(node)
4626  : 0;
4627 
4628  node_entry->set_value(CapSub(insertion_cost, penalty_shift));
4629  // Update the priority_queue.
4630  DCHECK(priority_queue->Contains(node_entry));
4631  priority_queue->NoteChangedPriority(node_entry);
4632 }
4633 
4634 // LocalCheapestInsertionFilteredHeuristic
4635 // TODO(user): Add support for penalty costs.
4639  std::function<int64(int64, int64, int64)> evaluator,
4640  LocalSearchFilterManager* filter_manager)
4641  : CheapestInsertionFilteredHeuristic(model, std::move(evaluator), nullptr,
4642  filter_manager) {
4643  std::vector<int> all_vehicles(model->vehicles());
4644  std::iota(std::begin(all_vehicles), std::end(all_vehicles), 0);
4645 
4646  start_end_distances_per_node_ =
4647  ComputeStartEndDistanceForVehicles(all_vehicles);
4648 }
4649 
4651  // Marking if we've tried inserting a node.
4652  std::vector<bool> visited(model()->Size(), false);
4653  // Possible positions where the current node can inserted.
4654  std::vector<int64> insertion_positions;
4655  // Possible positions where its associated delivery node can inserted (if the
4656  // current node has one).
4657  std::vector<int64> delivery_insertion_positions;
4658  // Iterating on pickup and delivery pairs
4659  const RoutingModel::IndexPairs& index_pairs =
4661  for (const auto& index_pair : index_pairs) {
4662  for (int64 pickup : index_pair.first) {
4663  if (Contains(pickup)) {
4664  continue;
4665  }
4666  for (int64 delivery : index_pair.second) {
4667  // If either is already in the solution, let it be inserted in the
4668  // standard node insertion loop.
4669  if (Contains(delivery)) {
4670  continue;
4671  }
4672  if (StopSearch()) return false;
4673  visited[pickup] = true;
4674  visited[delivery] = true;
4675  ComputeEvaluatorSortedPositions(pickup, &insertion_positions);
4676  for (const int64 pickup_insertion : insertion_positions) {
4677  const int pickup_insertion_next = Value(pickup_insertion);
4678  ComputeEvaluatorSortedPositionsOnRouteAfter(
4679  delivery, pickup, pickup_insertion_next,
4680  &delivery_insertion_positions);
4681  bool found = false;
4682  for (const int64 delivery_insertion : delivery_insertion_positions) {
4683  InsertBetween(pickup, pickup_insertion, pickup_insertion_next);
4684  const int64 delivery_insertion_next =
4685  (delivery_insertion == pickup_insertion) ? pickup
4686  : (delivery_insertion == pickup) ? pickup_insertion_next
4687  : Value(delivery_insertion);
4688  InsertBetween(delivery, delivery_insertion,
4689  delivery_insertion_next);
4690  if (Commit()) {
4691  found = true;
4692  break;
4693  }
4694  }
4695  if (found) {
4696  break;
4697  }
4698  }
4699  }
4700  }
4701  }
4702 
4703  std::priority_queue<Seed> node_queue;
4704  InitializePriorityQueue(&start_end_distances_per_node_, &node_queue);
4705 
4706  while (!node_queue.empty()) {
4707  const int node = node_queue.top().second;
4708  node_queue.pop();
4709  if (Contains(node) || visited[node]) continue;
4710  ComputeEvaluatorSortedPositions(node, &insertion_positions);
4711  for (const int64 insertion : insertion_positions) {
4712  if (StopSearch()) return false;
4713  InsertBetween(node, insertion, Value(insertion));
4714  if (Commit()) {
4715  break;
4716  }
4717  }
4718  }
4720  return Commit();
4721 }
4722 
4723 void LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPositions(
4724  int64 node, std::vector<int64>* sorted_positions) {
4725  CHECK(sorted_positions != nullptr);
4726  CHECK(!Contains(node));
4727  sorted_positions->clear();
4728  const int size = model()->Size();
4729  if (node < size) {
4730  std::vector<std::pair<int64, int64>> valued_positions;
4731  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
4732  const int64 start = model()->Start(vehicle);
4733  AppendEvaluatedPositionsAfter(node, start, Value(start), vehicle,
4734  &valued_positions);
4735  }
4736  SortAndExtractPairSeconds(&valued_positions, sorted_positions);
4737  }
4738 }
4739 
4740 void LocalCheapestInsertionFilteredHeuristic::
4741  ComputeEvaluatorSortedPositionsOnRouteAfter(
4742  int64 node, int64 start, int64 next_after_start,
4743  std::vector<int64>* sorted_positions) {
4744  CHECK(sorted_positions != nullptr);
4745  CHECK(!Contains(node));
4746  sorted_positions->clear();
4747  const int size = model()->Size();
4748  if (node < size) {
4749  // TODO(user): Take vehicle into account.
4750  std::vector<std::pair<int64, int64>> valued_positions;
4751  AppendEvaluatedPositionsAfter(node, start, next_after_start, 0,
4752  &valued_positions);
4753  SortAndExtractPairSeconds(&valued_positions, sorted_positions);
4754  }
4755 }
4756 
4757 // CheapestAdditionFilteredHeuristic
4758 
4760  RoutingModel* model, LocalSearchFilterManager* filter_manager)
4761  : RoutingFilteredHeuristic(model, filter_manager) {}
4762 
4764  const int kUnassigned = -1;
4766  std::vector<std::vector<int64>> deliveries(Size());
4767  std::vector<std::vector<int64>> pickups(Size());
4768  for (const RoutingModel::IndexPair& pair : pairs) {
4769  for (int first : pair.first) {
4770  for (int second : pair.second) {
4771  deliveries[first].push_back(second);
4772  pickups[second].push_back(first);
4773  }
4774  }
4775  }
4776  // To mimic the behavior of PathSelector (cf. search.cc), iterating on
4777  // routes with partial route at their start first then on routes with largest
4778  // index.
4779  std::vector<int> sorted_vehicles(model()->vehicles(), 0);
4780  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
4781  sorted_vehicles[vehicle] = vehicle;
4782  }
4783  std::sort(sorted_vehicles.begin(), sorted_vehicles.end(),
4784  PartialRoutesAndLargeVehicleIndicesFirst(*this));
4785  // Neighbors of the node currently being extended.
4786  for (const int vehicle : sorted_vehicles) {
4787  int64 last_node = GetStartChainEnd(vehicle);
4788  bool extend_route = true;
4789  // Extend the route of the current vehicle while it's possible. We can
4790  // iterate more than once if pickup and delivery pairs have been inserted
4791  // in the last iteration (see comment below); the new iteration will try to
4792  // extend the route after the last delivery on the route.
4793  while (extend_route) {
4794  extend_route = false;
4795  bool found = true;
4796  int64 index = last_node;
4797  int64 end = GetEndChainStart(vehicle);
4798  // Extend the route until either the end node of the vehicle is reached
4799  // or no node or node pair can be added. Deliveries in pickup and
4800  // delivery pairs are added at the same time as pickups, at the end of the
4801  // route, in reverse order of the pickups. Deliveries are never added
4802  // alone.
4803  while (found && !model()->IsEnd(index)) {
4804  found = false;
4805  std::vector<int64> neighbors;
4806  if (index < model()->Nexts().size()) {
4807  std::unique_ptr<IntVarIterator> it(
4808  model()->Nexts()[index]->MakeDomainIterator(false));
4809  auto next_values = InitAndGetValues(it.get());
4810  neighbors = GetPossibleNextsFromIterator(index, next_values.begin(),
4811  next_values.end());
4812  }
4813  for (int i = 0; !found && i < neighbors.size(); ++i) {
4814  int64 next = -1;
4815  switch (i) {
4816  case 0:
4817  next = FindTopSuccessor(index, neighbors);
4818  break;
4819  case 1:
4820  SortSuccessors(index, &neighbors);
4821  ABSL_FALLTHROUGH_INTENDED;
4822  default:
4823  next = neighbors[i];
4824  }
4825  if (model()->IsEnd(next) && next != end) {
4826  continue;
4827  }
4828  // Only add a delivery if one of its pickups has been added already.
4829  if (!model()->IsEnd(next) && !pickups[next].empty()) {
4830  bool contains_pickups = false;
4831  for (int64 pickup : pickups[next]) {
4832  if (Contains(pickup)) {
4833  contains_pickups = true;
4834  break;
4835  }
4836  }
4837  if (!contains_pickups) {
4838  continue;
4839  }
4840  }
4841  std::vector<int64> next_deliveries;
4842  if (next < deliveries.size()) {
4843  next_deliveries = GetPossibleNextsFromIterator(
4844  next, deliveries[next].begin(), deliveries[next].end());
4845  }
4846  if (next_deliveries.empty()) next_deliveries = {kUnassigned};
4847  for (int j = 0; !found && j < next_deliveries.size(); ++j) {
4848  if (StopSearch()) return false;
4849  int delivery = -1;
4850  switch (j) {
4851  case 0:
4852  delivery = FindTopSuccessor(next, next_deliveries);
4853  break;
4854  case 1:
4855  SortSuccessors(next, &next_deliveries);
4856  ABSL_FALLTHROUGH_INTENDED;
4857  default:
4858  delivery = next_deliveries[j];
4859  }
4860  // Insert "next" after "index", and before "end" if it is not the
4861  // end already.
4862  SetValue(index, next);
4863  if (!model()->IsEnd(next)) {
4864  SetValue(next, end);
4866  if (delivery != kUnassigned) {
4867  SetValue(next, delivery);
4868  SetValue(delivery, end);
4870  }
4871  }
4872  if (Commit()) {
4873  index = next;
4874  found = true;
4875  if (delivery != kUnassigned) {
4876  if (model()->IsEnd(end) && last_node != delivery) {
4877  last_node = delivery;
4878  extend_route = true;
4879  }
4880  end = delivery;
4881  }
4882  break;
4883  }
4884  }
4885  }
4886  }
4887  }
4888  }
4890  return Commit();
4891 }
4892 
4893 bool CheapestAdditionFilteredHeuristic::
4894  PartialRoutesAndLargeVehicleIndicesFirst::operator()(int vehicle1,
4895  int vehicle2) const {
4896  const bool has_partial_route1 = (builder_.model()->Start(vehicle1) !=
4897  builder_.GetStartChainEnd(vehicle1));
4898  const bool has_partial_route2 = (builder_.model()->Start(vehicle2) !=
4899  builder_.GetStartChainEnd(vehicle2));
4900  if (has_partial_route1 == has_partial_route2) {
4901  return vehicle2 < vehicle1;
4902  } else {
4903  return has_partial_route2 < has_partial_route1;
4904  }
4905 }
4906 
4907 // EvaluatorCheapestAdditionFilteredHeuristic
4908 
4911  RoutingModel* model, std::function<int64(int64, int64)> evaluator,
4912  LocalSearchFilterManager* filter_manager)
4913  : CheapestAdditionFilteredHeuristic(model, filter_manager),
4914  evaluator_(std::move(evaluator)) {}
4915 
4916 int64 EvaluatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
4917  int64 node, const std::vector<int64>& successors) {
4918  int64 best_evaluation = kint64max;
4919  int64 best_successor = -1;
4920  for (int64 successor : successors) {
4921  const int64 evaluation =
4922  (successor >= 0) ? evaluator_(node, successor) : kint64max;
4923  if (evaluation < best_evaluation ||
4924  (evaluation == best_evaluation && successor > best_successor)) {
4925  best_evaluation = evaluation;
4926  best_successor = successor;
4927  }
4928  }
4929  return best_successor;
4930 }
4931 
4932 void EvaluatorCheapestAdditionFilteredHeuristic::SortSuccessors(
4933  int64 node, std::vector<int64>* successors) {
4934  std::vector<std::pair<int64, int64>> values;
4935  values.reserve(successors->size());
4936  for (int64 successor : *successors) {
4937  // Tie-breaking on largest node index to mimic the behavior of
4938  // CheapestValueSelector (search.cc).
4939  values.push_back({evaluator_(node, successor), -successor});
4940  }
4941  std::sort(values.begin(), values.end());
4942  successors->clear();
4943  for (auto value : values) {
4944  successors->push_back(-value.second);
4945  }
4946 }
4947 
4948 // ComparatorCheapestAdditionFilteredHeuristic
4949 
4953  LocalSearchFilterManager* filter_manager)
4954  : CheapestAdditionFilteredHeuristic(model, filter_manager),
4955  comparator_(std::move(comparator)) {}
4956 
4957 int64 ComparatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
4958  int64 node, const std::vector<int64>& successors) {
4959  return *std::min_element(successors.begin(), successors.end(),
4960  [this, node](int successor1, int successor2) {
4961  return comparator_(node, successor1, successor2);
4962  });
4963 }
4964 
4965 void ComparatorCheapestAdditionFilteredHeuristic::SortSuccessors(
4966  int64 node, std::vector<int64>* successors) {
4967  std::sort(successors->begin(), successors->end(),
4968  [this, node](int successor1, int successor2) {
4969  return comparator_(node, successor1, successor2);
4970  });
4971 }
4972 
4973 // Class storing and allowing access to the savings according to the number of
4974 // vehicle types.
4975 // The savings are stored and sorted in sorted_savings_per_vehicle_type_.
4976 // Furthermore, when there is more than one vehicle type, the savings for a same
4977 // before-->after arc are sorted in costs_and_savings_per_arc_[arc] by
4978 // increasing cost(s-->before-->after-->e), where s and e are the start and end
4979 // of the route, in order to make sure the arc is served by the route with the
4980 // closest depot (start/end) possible.
4981 // When there is only one vehicle "type" (i.e. all vehicles have the same
4982 // start/end and cost class), each arc has a single saving value associated to
4983 // it, so we ignore this last step to avoid unnecessary computations, and only
4984 // work with sorted_savings_per_vehicle_type_[0].
4985 // In case of multiple vehicle types, the best savings for each arc, i.e. the
4986 // savings corresponding to the closest vehicle type, are inserted and sorted in
4987 // sorted_savings_.
4988 //
4989 // This class also handles skipped Savings:
4990 // The vectors skipped_savings_starting/ending_at_ contain all the Savings that
4991 // weren't added to the model, which we want to consider for later:
4992 // 1) When a Saving before-->after with both nodes uncontained cannot be used to
4993 // start a new route (no more available vehicles or could not commit on any
4994 // of those available).
4995 // 2) When only one of the nodes of the Saving is contained but on a different
4996 // vehicle type.
4997 // In these cases, the Update() method is called with update_best_saving = true,
4998 // which in turn calls SkipSavingForArc() (within
4999 // UpdateNextAndSkippedSavingsForArcWithType()) to mark the Saving for this arc
5000 // (with the correct type in the second case) as "skipped", by storing it in
5001 // skipped_savings_starting_at_[before] and skipped_savings_ending_at_[after].
5002 //
5003 // UpdateNextAndSkippedSavingsForArcWithType() also updates the next_savings_
5004 // vector, which stores the savings to go through once we've iterated through
5005 // all sorted_savings_.
5006 // In the first case above, where neither nodes are contained, we skip the
5007 // current Saving (current_saving_), and add the next best Saving for this arc
5008 // to next_savings_ (in case this skipped Saving is never considered).
5009 // In the second case with a specific type, we search for the Saving with the
5010 // correct type for this arc, and add it to both next_savings_ and the skipped
5011 // Savings.
5012 //
5013 // The skipped Savings are then re-considered when one of their ends gets
5014 // inserted:
5015 // When another Saving other_node-->before (or after-->other_node) gets
5016 // inserted, all skipped Savings in skipped_savings_starting_at_[before] (or
5017 // skipped_savings_ending_at_[after]) are once again considered by calling
5018 // ReinjectSkippedSavingsStartingAt() (or ReinjectSkippedSavingsEndingAt()).
5019 // Then, when calling GetSaving(), we iterate through the reinjected Savings in
5020 // order of insertion in the vectors while there are reinjected savings.
5021 template <typename Saving>
5023  public:
5024  explicit SavingsContainer(const SavingsFilteredHeuristic* savings_db,
5025  int vehicle_types)
5026  : savings_db_(savings_db),
5027  vehicle_types_(vehicle_types),
5028  index_in_sorted_savings_(0),
5029  single_vehicle_type_(vehicle_types == 1),
5030  using_incoming_reinjected_saving_(false),
5031  sorted_(false),
5032  to_update_(true) {}
5033 
5034  void InitializeContainer(int64 size, int64 saving_neighbors) {
5035  sorted_savings_per_vehicle_type_.clear();
5036  sorted_savings_per_vehicle_type_.resize(vehicle_types_);
5037  for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
5038  savings.reserve(size * saving_neighbors);
5039  }
5040 
5041  sorted_savings_.clear();
5042  costs_and_savings_per_arc_.clear();
5043  arc_indices_per_before_node_.clear();
5044 
5045  if (!single_vehicle_type_) {
5046  costs_and_savings_per_arc_.reserve(size * saving_neighbors);
5047  arc_indices_per_before_node_.resize(size);
5048  for (int before_node = 0; before_node < size; before_node++) {
5049  arc_indices_per_before_node_[before_node].reserve(saving_neighbors);
5050  }
5051  }
5052  skipped_savings_starting_at_.clear();
5053  skipped_savings_starting_at_.resize(size);
5054  skipped_savings_ending_at_.clear();
5055  skipped_savings_ending_at_.resize(size);
5056  incoming_reinjected_savings_ = nullptr;
5057  outgoing_reinjected_savings_ = nullptr;
5058  incoming_new_reinjected_savings_ = nullptr;
5059  outgoing_new_reinjected_savings_ = nullptr;
5060  }
5061 
5062  void AddNewSaving(const Saving& saving, int64 total_cost, int64 before_node,
5063  int64 after_node, int vehicle_type) {
5064  CHECK(!sorted_savings_per_vehicle_type_.empty())
5065  << "Container not initialized!";
5066  sorted_savings_per_vehicle_type_[vehicle_type].push_back(saving);
5067  UpdateArcIndicesCostsAndSavings(before_node, after_node,
5068  {total_cost, saving});
5069  }
5070 
5071  void Sort() {
5072  CHECK(!sorted_) << "Container already sorted!";
5073 
5074  for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
5075  std::sort(savings.begin(), savings.end());
5076  }
5077 
5078  if (single_vehicle_type_) {
5079  const auto& savings = sorted_savings_per_vehicle_type_[0];
5080  sorted_savings_.resize(savings.size());
5081  std::transform(savings.begin(), savings.end(), sorted_savings_.begin(),
5082  [](const Saving& saving) {
5083  return SavingAndArc({saving, /*arc_index*/ -1});
5084  });
5085  } else {
5086  // For each arc, sort the savings by decreasing total cost
5087  // start-->a-->b-->end.
5088  // The best saving for each arc is therefore the last of its vector.
5089  sorted_savings_.reserve(vehicle_types_ *
5090  costs_and_savings_per_arc_.size());
5091 
5092  for (int arc_index = 0; arc_index < costs_and_savings_per_arc_.size();
5093  arc_index++) {
5094  std::vector<std::pair<int64, Saving>>& costs_and_savings =
5095  costs_and_savings_per_arc_[arc_index];
5096  DCHECK(!costs_and_savings.empty());
5097 
5098  std::sort(
5099  costs_and_savings.begin(), costs_and_savings.end(),
5100  [](const std::pair<int64, Saving>& cs1,
5101  const std::pair<int64, Saving>& cs2) { return cs1 > cs2; });
5102 
5103  // Insert all Savings for this arc with the lowest cost into
5104  // sorted_savings_.
5105  // TODO(user): Also do this when reiterating on next_savings_.
5106  const int64 cost = costs_and_savings.back().first;
5107  while (!costs_and_savings.empty() &&
5108  costs_and_savings.back().first == cost) {
5109  sorted_savings_.push_back(
5110  {costs_and_savings.back().second, arc_index});
5111  costs_and_savings.pop_back();
5112  }
5113  }
5114  std::sort(sorted_savings_.begin(), sorted_savings_.end());
5115  next_saving_type_and_index_for_arc_.clear();
5116  next_saving_type_and_index_for_arc_.resize(
5117  costs_and_savings_per_arc_.size(), {-1, -1});
5118  }
5119  sorted_ = true;
5120  index_in_sorted_savings_ = 0;
5121  to_update_ = false;
5122  }
5123 
5124  bool HasSaving() {
5125  return index_in_sorted_savings_ < sorted_savings_.size() ||
5126  HasReinjectedSavings();
5127  }
5128 
5130  CHECK(sorted_) << "Calling GetSaving() before Sort() !";
5131  CHECK(!to_update_)
5132  << "Update() should be called between two calls to GetSaving() !";
5133 
5134  to_update_ = true;
5135 
5136  if (HasReinjectedSavings()) {
5137  if (incoming_reinjected_savings_ != nullptr &&
5138  outgoing_reinjected_savings_ != nullptr) {
5139  // Get the best Saving among the two.
5140  SavingAndArc& incoming_saving = incoming_reinjected_savings_->front();
5141  SavingAndArc& outgoing_saving = outgoing_reinjected_savings_->front();
5142  if (incoming_saving < outgoing_saving) {
5143  current_saving_ = incoming_saving;
5144  using_incoming_reinjected_saving_ = true;
5145  } else {
5146  current_saving_ = outgoing_saving;
5147  using_incoming_reinjected_saving_ = false;
5148  }
5149  } else {
5150  if (incoming_reinjected_savings_ != nullptr) {
5151  current_saving_ = incoming_reinjected_savings_->front();
5152  using_incoming_reinjected_saving_ = true;
5153  }
5154  if (outgoing_reinjected_savings_ != nullptr) {
5155  current_saving_ = outgoing_reinjected_savings_->front();
5156  using_incoming_reinjected_saving_ = false;
5157  }
5158  }
5159  } else {
5160  current_saving_ = sorted_savings_[index_in_sorted_savings_];
5161  }
5162  return current_saving_.saving;
5163  }
5164 
5165  void Update(bool update_best_saving, int type = -1) {
5166  CHECK(to_update_) << "Container already up to date!";
5167  if (update_best_saving) {
5168  const int64 arc_index = current_saving_.arc_index;
5169  UpdateNextAndSkippedSavingsForArcWithType(arc_index, type);
5170  }
5171  if (!HasReinjectedSavings()) {
5172  index_in_sorted_savings_++;
5173 
5174  if (index_in_sorted_savings_ == sorted_savings_.size()) {
5175  sorted_savings_.swap(next_savings_);
5176  gtl::STLClearObject(&next_savings_);
5177  index_in_sorted_savings_ = 0;
5178 
5179  std::sort(sorted_savings_.begin(), sorted_savings_.end());
5180  next_saving_type_and_index_for_arc_.clear();
5181  next_saving_type_and_index_for_arc_.resize(
5182  costs_and_savings_per_arc_.size(), {-1, -1});
5183  }
5184  }
5185  UpdateReinjectedSavings();
5186  to_update_ = false;
5187  }
5188 
5189  void UpdateWithType(int type) {
5190  CHECK(!single_vehicle_type_);
5191  Update(/*update_best_saving*/ true, type);
5192  }
5193 
5194  const std::vector<Saving>& GetSortedSavingsForVehicleType(int type) {
5195  CHECK(sorted_) << "Savings not sorted yet!";
5196  CHECK_LT(type, vehicle_types_);
5197  return sorted_savings_per_vehicle_type_[type];
5198  }
5199 
5201  CHECK(outgoing_new_reinjected_savings_ == nullptr);
5202  outgoing_new_reinjected_savings_ = &(skipped_savings_starting_at_[node]);
5203  }
5204 
5206  CHECK(incoming_new_reinjected_savings_ == nullptr);
5207  incoming_new_reinjected_savings_ = &(skipped_savings_ending_at_[node]);
5208  }
5209 
5210  private:
5211  struct SavingAndArc {
5212  Saving saving;
5213  int64 arc_index;
5214 
5215  bool operator<(const SavingAndArc& other) const {
5216  return std::tie(saving, arc_index) <
5217  std::tie(other.saving, other.arc_index);
5218  }
5219  };
5220 
5221  // Skips the Saving for the arc before_node-->after_node, by adding it to the
5222  // skipped_savings_ vector of the nodes, if they're uncontained.
5223  void SkipSavingForArc(const SavingAndArc& saving_and_arc) {
5224  const Saving& saving = saving_and_arc.saving;
5225  const int64 before_node = savings_db_->GetBeforeNodeFromSaving(saving);
5226  const int64 after_node = savings_db_->GetAfterNodeFromSaving(saving);
5227  if (!savings_db_->Contains(before_node)) {
5228  skipped_savings_starting_at_[before_node].push_back(saving_and_arc);
5229  }
5230  if (!savings_db_->Contains(after_node)) {
5231  skipped_savings_ending_at_[after_node].push_back(saving_and_arc);
5232  }
5233  }
5234 
5235  // Called within Update() when update_best_saving is true, this method updates
5236  // the next_savings_ and skipped savings vectors for a given arc_index and
5237  // vehicle type.
5238  // When a Saving with the right type has already been added to next_savings_
5239  // for this arc, no action is needed on next_savings_.
5240  // Otherwise, if such a Saving exists, GetNextSavingForArcWithType() will find
5241  // and assign it to next_saving, which is then used to update next_savings_.
5242  // Finally, the right Saving is skipped for this arc: if looking for a
5243  // specific type (i.e. type != -1), next_saving (which has the correct type)
5244  // is skipped, otherwise the current_saving_ is.
5245  void UpdateNextAndSkippedSavingsForArcWithType(int64 arc_index, int type) {
5246  if (single_vehicle_type_) {
5247  // No next Saving, skip the current Saving.
5248  CHECK_EQ(type, -1);
5249  SkipSavingForArc(current_saving_);
5250  return;
5251  }
5252  CHECK_GE(arc_index, 0);
5253  auto& type_and_index = next_saving_type_and_index_for_arc_[arc_index];
5254  const int previous_index = type_and_index.second;
5255  const int previous_type = type_and_index.first;
5256  bool next_saving_added = false;
5257  Saving next_saving;
5258 
5259  if (previous_index >= 0) {
5260  // Next Saving already added for this arc.
5261  DCHECK_GE(previous_type, 0);
5262  if (type == -1 || previous_type == type) {
5263  // Not looking for a specific type, or correct type already in
5264  // next_savings_.
5265  next_saving_added = true;
5266  next_saving = next_savings_[previous_index].saving;
5267  }
5268  }
5269 
5270  if (!next_saving_added &&
5271  GetNextSavingForArcWithType(arc_index, type, &next_saving)) {
5272  type_and_index.first = savings_db_->GetVehicleTypeFromSaving(next_saving);
5273  if (previous_index >= 0) {
5274  // Update the previous saving.
5275  next_savings_[previous_index] = {next_saving, arc_index};
5276  } else {
5277  // Insert the new next Saving for this arc.
5278  type_and_index.second = next_savings_.size();
5279  next_savings_.push_back({next_saving, arc_index});
5280  }
5281  next_saving_added = true;
5282  }
5283 
5284  // Skip the Saving based on the vehicle type.
5285  if (type == -1) {
5286  // Skip the current Saving.
5287  SkipSavingForArc(current_saving_);
5288  } else {
5289  // Skip the Saving with the correct type, already added to next_savings_
5290  // if it was found.
5291  if (next_saving_added) {
5292  SkipSavingForArc({next_saving, arc_index});
5293  }
5294  }
5295  }
5296 
5297  void UpdateReinjectedSavings() {
5298  UpdateGivenReinjectedSavings(incoming_new_reinjected_savings_,
5299  &incoming_reinjected_savings_,
5300  using_incoming_reinjected_saving_);
5301  UpdateGivenReinjectedSavings(outgoing_new_reinjected_savings_,
5302  &outgoing_reinjected_savings_,
5303  !using_incoming_reinjected_saving_);
5304  incoming_new_reinjected_savings_ = nullptr;
5305  outgoing_new_reinjected_savings_ = nullptr;
5306  }
5307 
5308  void UpdateGivenReinjectedSavings(
5309  std::deque<SavingAndArc>* new_reinjected_savings,
5310  std::deque<SavingAndArc>** reinjected_savings,
5311  bool using_reinjected_savings) {
5312  if (new_reinjected_savings == nullptr) {
5313  // No new reinjected savings, update the previous ones if needed.
5314  if (*reinjected_savings != nullptr && using_reinjected_savings) {
5315  CHECK(!(*reinjected_savings)->empty());
5316  (*reinjected_savings)->pop_front();
5317  if ((*reinjected_savings)->empty()) {
5318  *reinjected_savings = nullptr;
5319  }
5320  }
5321  return;
5322  }
5323 
5324  // New savings reinjected.
5325  // Forget about the previous reinjected savings and add the new ones if
5326  // there are any.
5327  if (*reinjected_savings != nullptr) {
5328  (*reinjected_savings)->clear();
5329  }
5330  *reinjected_savings = nullptr;
5331  if (!new_reinjected_savings->empty()) {
5332  *reinjected_savings = new_reinjected_savings;
5333  }
5334  }
5335 
5336  bool HasReinjectedSavings() {
5337  return outgoing_reinjected_savings_ != nullptr ||
5338  incoming_reinjected_savings_ != nullptr;
5339  }
5340 
5341  void UpdateArcIndicesCostsAndSavings(
5342  int64 before_node, int64 after_node,
5343  const std::pair<int64, Saving>& cost_and_saving) {
5344  if (single_vehicle_type_) {
5345  return;
5346  }
5347  absl::flat_hash_map<int, int>& arc_indices =
5348  arc_indices_per_before_node_[before_node];
5349  const auto& arc_inserted = arc_indices.insert(
5350  std::make_pair(after_node, costs_and_savings_per_arc_.size()));
5351  const int index = arc_inserted.first->second;
5352  if (arc_inserted.second) {
5353  costs_and_savings_per_arc_.push_back({cost_and_saving});
5354  } else {
5355  DCHECK_LT(index, costs_and_savings_per_arc_.size());
5356  costs_and_savings_per_arc_[index].push_back(cost_and_saving);
5357  }
5358  }
5359 
5360  bool GetNextSavingForArcWithType(int64 arc_index, int type,
5361  Saving* next_saving) {
5362  std::vector<std::pair<int64, Saving>>& costs_and_savings =
5363  costs_and_savings_per_arc_[arc_index];
5364 
5365  bool found_saving = false;
5366  while (!costs_and_savings.empty() && !found_saving) {
5367  const Saving& saving = costs_and_savings.back().second;
5368  if (type == -1 || savings_db_->GetVehicleTypeFromSaving(saving) == type) {
5369  *next_saving = saving;
5370  found_saving = true;
5371  }
5372  costs_and_savings.pop_back();
5373  }
5374  return found_saving;
5375  }
5376 
5377  const SavingsFilteredHeuristic* const savings_db_;
5378  const int vehicle_types_;
5379  int64 index_in_sorted_savings_;
5380  std::vector<std::vector<Saving>> sorted_savings_per_vehicle_type_;
5381  std::vector<SavingAndArc> sorted_savings_;
5382  std::vector<SavingAndArc> next_savings_;
5383  std::vector<std::pair</*type*/ int, /*index*/ int>>
5384  next_saving_type_and_index_for_arc_;
5385  SavingAndArc current_saving_;
5386  const bool single_vehicle_type_;
5387  std::vector<std::vector<std::pair</*cost*/ int64, Saving>>>
5388  costs_and_savings_per_arc_;
5389  std::vector<absl::flat_hash_map</*after_node*/ int, /*arc_index*/ int>>
5390  arc_indices_per_before_node_;
5391  std::vector<std::deque<SavingAndArc>> skipped_savings_starting_at_;
5392  std::vector<std::deque<SavingAndArc>> skipped_savings_ending_at_;
5393  std::deque<SavingAndArc>* outgoing_reinjected_savings_;
5394  std::deque<SavingAndArc>* incoming_reinjected_savings_;
5395  bool using_incoming_reinjected_saving_;
5396  std::deque<SavingAndArc>* outgoing_new_reinjected_savings_;
5397  std::deque<SavingAndArc>* incoming_new_reinjected_savings_;
5398  bool sorted_;
5399  bool to_update_;
5400 };
5401 
5402 // SavingsFilteredHeuristic
5403 
5404 SavingsFilteredHeuristic::SavingsFilteredHeuristic(
5405  RoutingModel* model, const RoutingIndexManager* manager,
5407  : RoutingFilteredHeuristic(model, filter_manager),
5408  vehicle_type_curator_(nullptr),
5409  manager_(manager),
5410  savings_params_(parameters) {
5411  DCHECK_GT(savings_params_.neighbors_ratio, 0);
5412  DCHECK_LE(savings_params_.neighbors_ratio, 1);
5413  DCHECK_GT(savings_params_.max_memory_usage_bytes, 0);
5414  DCHECK_GT(savings_params_.arc_coefficient, 0);
5415  const int size = model->Size();
5416  size_squared_ = size * size;
5417 }
5418 
5420 
5422  if (vehicle_type_curator_ == nullptr) {
5423  vehicle_type_curator_ = absl::make_unique<VehicleTypeCurator>(
5424  model()->GetVehicleTypeContainer());
5425  }
5426  // Only store empty vehicles in the vehicle_type_curator_.
5427  vehicle_type_curator_->Reset(
5428  [this](int vehicle) { return VehicleIsEmpty(vehicle); });
5429  ComputeSavings();
5431  // Free all the space used to store the Savings in the container.
5432  savings_container_.reset();
5434  if (!Commit()) return false;
5436  return Commit();
5437 }
5438 
5440  int type, int64 before_node, int64 after_node) {
5441  auto vehicle_is_compatible = [this, before_node, after_node](int vehicle) {
5442  if (!model()->VehicleVar(before_node)->Contains(vehicle) ||
5443  !model()->VehicleVar(after_node)->Contains(vehicle)) {
5444  return false;
5445  }
5446  // Try to commit the arc on this vehicle.
5447  DCHECK(VehicleIsEmpty(vehicle));
5448  const int64 start = model()->Start(vehicle);
5449  const int64 end = model()->End(vehicle);
5450  SetValue(start, before_node);
5451  SetValue(before_node, after_node);
5452  SetValue(after_node, end);
5453  return Commit();
5454  };
5455 
5456  return vehicle_type_curator_
5457  ->GetCompatibleVehicleOfType(
5458  type, vehicle_is_compatible,
5459  /*stop_and_return_vehicle*/ [](int) { return false; })
5460  .first;
5461 }
5462 
5463 void SavingsFilteredHeuristic::AddSymmetricArcsToAdjacencyLists(
5464  std::vector<std::vector<int64>>* adjacency_lists) {
5465  for (int64 node = 0; node < adjacency_lists->size(); node++) {
5466  for (int64 neighbor : (*adjacency_lists)[node]) {
5467  if (model()->IsStart(neighbor) || model()->IsEnd(neighbor)) {
5468  continue;
5469  }
5470  (*adjacency_lists)[neighbor].push_back(node);
5471  }
5472  }
5473  std::transform(adjacency_lists->begin(), adjacency_lists->end(),
5474  adjacency_lists->begin(), [](std::vector<int64> vec) {
5475  std::sort(vec.begin(), vec.end());
5476  vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
5477  return vec;
5478  });
5479 }
5480 
5481 // Computes the savings related to each pair of non-start and non-end nodes.
5482 // The savings value for an arc a-->b for a vehicle starting at node s and
5483 // ending at node e is:
5484 // saving = cost(s-->a-->e) + cost(s-->b-->e) - cost(s-->a-->b-->e), i.e.
5485 // saving = cost(a-->e) + cost(s-->b) - cost(a-->b)
5486 // The saving value also considers a coefficient for the cost of the arc
5487 // a-->b, which results in:
5488 // saving = cost(a-->e) + cost(s-->b) - [arc_coefficient_ * cost(a-->b)]
5489 // The higher this saving value, the better the arc.
5490 // Here, the value stored for the savings is -saving, which are therefore
5491 // considered in decreasing order.
5492 void SavingsFilteredHeuristic::ComputeSavings() {
5493  const int num_vehicle_types = vehicle_type_curator_->NumTypes();
5494  const int size = model()->Size();
5495 
5496  std::vector<int64> uncontained_non_start_end_nodes;
5497  uncontained_non_start_end_nodes.reserve(size);
5498  for (int node = 0; node < size; node++) {
5499  if (!model()->IsStart(node) && !model()->IsEnd(node) && !Contains(node)) {
5500  uncontained_non_start_end_nodes.push_back(node);
5501  }
5502  }
5503 
5504  const int64 saving_neighbors =
5505  std::min(MaxNumNeighborsPerNode(num_vehicle_types),
5506  static_cast<int64>(uncontained_non_start_end_nodes.size()));
5507 
5509  absl::make_unique<SavingsContainer<Saving>>(this, num_vehicle_types);
5510  savings_container_->InitializeContainer(size, saving_neighbors);
5511 
5512  std::vector<std::vector<int64>> adjacency_lists(size);
5513 
5514  for (int type = 0; type < num_vehicle_types; ++type) {
5515  const int vehicle =
5516  vehicle_type_curator_->GetLowestFixedCostVehicleOfType(type);
5517  if (vehicle < 0) {
5518  continue;
5519  }
5520 
5521  const int64 cost_class =
5522  model()->GetCostClassIndexOfVehicle(vehicle).value();
5523  const int64 start = model()->Start(vehicle);
5524  const int64 end = model()->End(vehicle);
5525  const int64 fixed_cost = model()->GetFixedCostOfVehicle(vehicle);
5526 
5527  // Compute the neighbors for each non-start/end node not already inserted in
5528  // the model.
5529  for (int before_node : uncontained_non_start_end_nodes) {
5530  std::vector<std::pair</*cost*/ int64, /*node*/ int64>> costed_after_nodes;
5531  costed_after_nodes.reserve(uncontained_non_start_end_nodes.size());
5532  for (int after_node : uncontained_non_start_end_nodes) {
5533  if (after_node != before_node) {
5534  costed_after_nodes.push_back(std::make_pair(
5535  model()->GetArcCostForClass(before_node, after_node, cost_class),
5536  after_node));
5537  }
5538  }
5539  if (saving_neighbors < costed_after_nodes.size()) {
5540  std::nth_element(costed_after_nodes.begin(),
5541  costed_after_nodes.begin() + saving_neighbors,
5542  costed_after_nodes.end());
5543  costed_after_nodes.resize(saving_neighbors);
5544  }
5545  adjacency_lists[before_node].resize(costed_after_nodes.size());
5546  std::transform(costed_after_nodes.begin(), costed_after_nodes.end(),
5547  adjacency_lists[before_node].begin(),
5548  [](std::pair<int64, int64> cost_and_node) {
5549  return cost_and_node.second;
5550  });
5551  }
5552  if (savings_params_.add_reverse_arcs) {
5553  AddSymmetricArcsToAdjacencyLists(&adjacency_lists);
5554  }
5555 
5556  // Build the savings for this vehicle type given the adjacency_lists.
5557  for (int before_node : uncontained_non_start_end_nodes) {
5558  const int64 before_to_end_cost =
5559  model()->GetArcCostForClass(before_node, end, cost_class);
5560  const int64 start_to_before_cost =
5561  CapSub(model()->GetArcCostForClass(start, before_node, cost_class),
5562  fixed_cost);
5563  for (int64 after_node : adjacency_lists[before_node]) {
5564  if (model()->IsStart(after_node) || model()->IsEnd(after_node) ||
5565  before_node == after_node || Contains(after_node)) {
5566  continue;
5567  }
5568  const int64 arc_cost =
5569  model()->GetArcCostForClass(before_node, after_node, cost_class);
5570  const int64 start_to_after_cost =
5571  CapSub(model()->GetArcCostForClass(start, after_node, cost_class),
5572  fixed_cost);
5573  const int64 after_to_end_cost =
5574  model()->GetArcCostForClass(after_node, end, cost_class);
5575 
5576  const double weighted_arc_cost_fp =
5577  savings_params_.arc_coefficient * arc_cost;
5578  const int64 weighted_arc_cost =
5579  weighted_arc_cost_fp < kint64max
5580  ? static_cast<int64>(weighted_arc_cost_fp)
5581  : kint64max;
5582  const int64 saving_value = CapSub(
5583  CapAdd(before_to_end_cost, start_to_after_cost), weighted_arc_cost);
5584 
5585  const Saving saving =
5586  BuildSaving(-saving_value, type, before_node, after_node);
5587 
5588  const int64 total_cost =
5589  CapAdd(CapAdd(start_to_before_cost, arc_cost), after_to_end_cost);
5590 
5591  savings_container_->AddNewSaving(saving, total_cost, before_node,
5592  after_node, type);
5593  }
5594  }
5595  }
5596  savings_container_->Sort();
5597 }
5598 
5599 int64 SavingsFilteredHeuristic::MaxNumNeighborsPerNode(
5600  int num_vehicle_types) const {
5601  const int64 size = model()->Size();
5602 
5603  const int64 num_neighbors_with_ratio =
5604  std::max(1.0, size * savings_params_.neighbors_ratio);
5605 
5606  // A single Saving takes 2*8 bytes of memory.
5607  // max_memory_usage_in_savings_unit = num_savings * multiplicative_factor,
5608  // Where multiplicative_factor is the memory taken (in Savings unit) for each
5609  // computed Saving.
5610  const double max_memory_usage_in_savings_unit =
5611  savings_params_.max_memory_usage_bytes / 16;
5612 
5613  // In the SavingsContainer, for each Saving, the Savings are stored:
5614  // - Once in "sorted_savings_per_vehicle_type", and (at most) once in
5615  // "sorted_savings_" --> factor 2
5616  // - If num_vehicle_types > 1, they're also stored by arc_index in
5617  // "costs_and_savings_per_arc", along with their int64 cost --> factor 1.5
5618  //
5619  // On top of that,
5620  // - In the sequential version, the Saving* are also stored by in-coming and
5621  // outgoing node (in in/out_savings_ptr), adding another 2*8 bytes per
5622  // Saving --> factor 1.
5623  // - In the parallel version, skipped Savings are also stored in
5624  // skipped_savings_starting/ending_at_, resulting in a maximum added factor
5625  // of 2 for each Saving.
5626  // These extra factors are given by ExtraSavingsMemoryMultiplicativeFactor().
5627  double multiplicative_factor = 2.0 + ExtraSavingsMemoryMultiplicativeFactor();
5628  if (num_vehicle_types > 1) {
5629  multiplicative_factor += 1.5;
5630  }
5631  const double num_savings =
5632  max_memory_usage_in_savings_unit / multiplicative_factor;
5633  const int64 num_neighbors_with_memory_restriction =
5634  std::max(1.0, num_savings / (num_vehicle_types * size));
5635 
5636  return std::min(num_neighbors_with_ratio,
5637  num_neighbors_with_memory_restriction);
5638 }
5639 
5640 // SequentialSavingsFilteredHeuristic
5641 
5642 void SequentialSavingsFilteredHeuristic::BuildRoutesFromSavings() {
5643  const int vehicle_types = vehicle_type_curator_->NumTypes();
5644  DCHECK_GT(vehicle_types, 0);
5645  const int size = model()->Size();
5646  // Store savings for each incoming and outgoing node and by vehicle type. This
5647  // is necessary to quickly extend partial chains without scanning all savings.
5648  std::vector<std::vector<const Saving*>> in_savings_ptr(size * vehicle_types);
5649  std::vector<std::vector<const Saving*>> out_savings_ptr(size * vehicle_types);
5650  for (int type = 0; type < vehicle_types; type++) {
5651  const int vehicle_type_offset = type * size;
5652  const std::vector<Saving>& sorted_savings_for_type =
5653  savings_container_->GetSortedSavingsForVehicleType(type);
5654  for (const Saving& saving : sorted_savings_for_type) {
5655  DCHECK_EQ(GetVehicleTypeFromSaving(saving), type);
5656  const int before_node = GetBeforeNodeFromSaving(saving);
5657  in_savings_ptr[vehicle_type_offset + before_node].push_back(&saving);
5658  const int after_node = GetAfterNodeFromSaving(saving);
5659  out_savings_ptr[vehicle_type_offset + after_node].push_back(&saving);
5660  }
5661  }
5662 
5663  // Build routes from savings.
5664  while (savings_container_->HasSaving()) {
5665  // First find the best saving to start a new route.
5666  const Saving saving = savings_container_->GetSaving();
5667  int before_node = GetBeforeNodeFromSaving(saving);
5668  int after_node = GetAfterNodeFromSaving(saving);
5669  const bool nodes_not_contained =
5670  !Contains(before_node) && !Contains(after_node);
5671 
5672  bool committed = false;
5673 
5674  if (nodes_not_contained) {
5675  // Find the right vehicle to start the route with this Saving.
5676  const int type = GetVehicleTypeFromSaving(saving);
5677  const int vehicle =
5678  StartNewRouteWithBestVehicleOfType(type, before_node, after_node);
5679 
5680  if (vehicle >= 0) {
5681  committed = true;
5682  const int64 start = model()->Start(vehicle);
5683  const int64 end = model()->End(vehicle);
5684  // Then extend the route from both ends of the partial route.
5685  int in_index = 0;
5686  int out_index = 0;
5687  const int saving_offset = type * size;
5688 
5689  while (in_index < in_savings_ptr[saving_offset + after_node].size() ||
5690  out_index <
5691  out_savings_ptr[saving_offset + before_node].size()) {
5692  if (StopSearch()) return;
5693  // First determine how to extend the route.
5694  int before_before_node = -1;
5695  int after_after_node = -1;
5696  if (in_index < in_savings_ptr[saving_offset + after_node].size()) {
5697  const Saving& in_saving =
5698  *(in_savings_ptr[saving_offset + after_node][in_index]);
5699  if (out_index <
5700  out_savings_ptr[saving_offset + before_node].size()) {
5701  const Saving& out_saving =
5702  *(out_savings_ptr[saving_offset + before_node][out_index]);
5703  if (GetSavingValue(in_saving) < GetSavingValue(out_saving)) {
5704  // Should extend after after_node
5705  after_after_node = GetAfterNodeFromSaving(in_saving);
5706  } else {
5707  // Should extend before before_node
5708  before_before_node = GetBeforeNodeFromSaving(out_saving);
5709  }
5710  } else {
5711  // Should extend after after_node
5712  after_after_node = GetAfterNodeFromSaving(in_saving);
5713  }
5714  } else {
5715  // Should extend before before_node
5716  before_before_node = GetBeforeNodeFromSaving(
5717  *(out_savings_ptr[saving_offset + before_node][out_index]));
5718  }
5719  // Extend the route
5720  if (after_after_node != -1) {
5721  DCHECK_EQ(before_before_node, -1);
5722  // Extending after after_node
5723  if (!Contains(after_after_node)) {
5724  SetValue(after_node, after_after_node);
5725  SetValue(after_after_node, end);
5726  if (Commit()) {
5727  in_index = 0;
5728  after_node = after_after_node;
5729  } else {
5730  ++in_index;
5731  }
5732  } else {
5733  ++in_index;
5734  }
5735  } else {
5736  // Extending before before_node
5737  CHECK_GE(before_before_node, 0);
5738  if (!Contains(before_before_node)) {
5739  SetValue(start, before_before_node);
5740  SetValue(before_before_node, before_node);
5741  if (Commit()) {
5742  out_index = 0;
5743  before_node = before_before_node;
5744  } else {
5745  ++out_index;
5746  }
5747  } else {
5748  ++out_index;
5749  }
5750  }
5751  }
5752  }
5753  }
5754  savings_container_->Update(nodes_not_contained && !committed);
5755  }
5756 }
5757 
5758 // ParallelSavingsFilteredHeuristic
5759 
5760 void ParallelSavingsFilteredHeuristic::BuildRoutesFromSavings() {
5761  // Initialize the vehicles of the first/last non start/end nodes served by
5762  // each route.
5763  const int64 size = model()->Size();
5764  const int vehicles = model()->vehicles();
5765 
5766  first_node_on_route_.resize(vehicles, -1);
5767  last_node_on_route_.resize(vehicles, -1);
5768  vehicle_of_first_or_last_node_.resize(size, -1);
5769 
5770  for (int vehicle = 0; vehicle < vehicles; vehicle++) {
5771  const int64 start = model()->Start(vehicle);
5772  const int64 end = model()->End(vehicle);
5773  if (!Contains(start)) {
5774  continue;
5775  }
5776  int64 node = Value(start);
5777  if (node != end) {
5778  vehicle_of_first_or_last_node_[node] = vehicle;
5779  first_node_on_route_[vehicle] = node;
5780 
5781  int64 next = Value(node);
5782  while (next != end) {
5783  node = next;
5784  next = Value(node);
5785  }
5786  vehicle_of_first_or_last_node_[node] = vehicle;
5787  last_node_on_route_[vehicle] = node;
5788  }
5789  }
5790 
5791  while (savings_container_->HasSaving()) {
5792  if (StopSearch()) return;
5793  const Saving saving = savings_container_->GetSaving();
5794  const int64 before_node = GetBeforeNodeFromSaving(saving);
5795  const int64 after_node = GetAfterNodeFromSaving(saving);
5796  const int type = GetVehicleTypeFromSaving(saving);
5797 
5798  if (!Contains(before_node) && !Contains(after_node)) {
5799  // Neither nodes are contained, start a new route.
5800  bool committed = false;
5801 
5802  const int vehicle =
5803  StartNewRouteWithBestVehicleOfType(type, before_node, after_node);
5804 
5805  if (vehicle >= 0) {
5806  committed = true;
5807  // Store before_node and after_node as first and last nodes of the route
5808  vehicle_of_first_or_last_node_[before_node] = vehicle;
5809  vehicle_of_first_or_last_node_[after_node] = vehicle;
5810  first_node_on_route_[vehicle] = before_node;
5811  last_node_on_route_[vehicle] = after_node;
5812  savings_container_->ReinjectSkippedSavingsStartingAt(after_node);
5813  savings_container_->ReinjectSkippedSavingsEndingAt(before_node);
5814  }
5815  savings_container_->Update(!committed);
5816  continue;
5817  }
5818 
5819  if (Contains(before_node) && Contains(after_node)) {
5820  // Merge the two routes if before_node is last and after_node first of its
5821  // route, the two nodes aren't already on the same route, and the vehicle
5822  // types are compatible.
5823  const int v1 = vehicle_of_first_or_last_node_[before_node];
5824  const int64 last_node = v1 == -1 ? -1 : last_node_on_route_[v1];
5825 
5826  const int v2 = vehicle_of_first_or_last_node_[after_node];
5827  const int64 first_node = v2 == -1 ? -1 : first_node_on_route_[v2];
5828 
5829  if (before_node == last_node && after_node == first_node && v1 != v2 &&
5830  vehicle_type_curator_->Type(v1) == vehicle_type_curator_->Type(v2)) {
5831  CHECK_EQ(Value(before_node), model()->End(v1));
5832  CHECK_EQ(Value(model()->Start(v2)), after_node);
5833 
5834  // We try merging the two routes.
5835  // TODO(user): Try to use skipped savings to start new routes when
5836  // a vehicle becomes available after a merge (not trivial because it can
5837  // result in an infinite loop).
5838  MergeRoutes(v1, v2, before_node, after_node);
5839  }
5840  }
5841 
5842  if (Contains(before_node) && !Contains(after_node)) {
5843  const int vehicle = vehicle_of_first_or_last_node_[before_node];
5844  const int64 last_node = vehicle == -1 ? -1 : last_node_on_route_[vehicle];
5845 
5846  if (before_node == last_node) {
5847  const int64 end = model()->End(vehicle);
5848  CHECK_EQ(Value(before_node), end);
5849 
5850  const int route_type = vehicle_type_curator_->Type(vehicle);
5851  if (type != route_type) {
5852  // The saving doesn't correspond to the type of the vehicle serving
5853  // before_node. We update the container with the correct type.
5854  savings_container_->UpdateWithType(route_type);
5855  continue;
5856  }
5857 
5858  // Try adding after_node on route of before_node.
5859  SetValue(before_node, after_node);
5860  SetValue(after_node, end);
5861  if (Commit()) {
5862  if (first_node_on_route_[vehicle] != before_node) {
5863  // before_node is no longer the start or end of its route
5864  DCHECK_NE(Value(model()->Start(vehicle)), before_node);
5865  vehicle_of_first_or_last_node_[before_node] = -1;
5866  }
5867  vehicle_of_first_or_last_node_[after_node] = vehicle;
5868  last_node_on_route_[vehicle] = after_node;
5869  savings_container_->ReinjectSkippedSavingsStartingAt(after_node);
5870  }
5871  }
5872  }
5873 
5874  if (!Contains(before_node) && Contains(after_node)) {
5875  const int vehicle = vehicle_of_first_or_last_node_[after_node];
5876  const int64 first_node =
5877  vehicle == -1 ? -1 : first_node_on_route_[vehicle];
5878 
5879  if (after_node == first_node) {
5880  const int64 start = model()->Start(vehicle);
5881  CHECK_EQ(Value(start), after_node);
5882 
5883  const int route_type = vehicle_type_curator_->Type(vehicle);
5884  if (type != route_type) {
5885  // The saving doesn't correspond to the type of the vehicle serving
5886  // after_node. We update the container with the correct type.
5887  savings_container_->UpdateWithType(route_type);
5888  continue;
5889  }
5890 
5891  // Try adding before_node on route of after_node.
5892  SetValue(before_node, after_node);
5893  SetValue(start, before_node);
5894  if (Commit()) {
5895  if (last_node_on_route_[vehicle] != after_node) {
5896  // after_node is no longer the start or end of its route
5897  DCHECK_NE(Value(after_node), model()->End(vehicle));
5898  vehicle_of_first_or_last_node_[after_node] = -1;
5899  }
5900  vehicle_of_first_or_last_node_[before_node] = vehicle;
5901  first_node_on_route_[vehicle] = before_node;
5902  savings_container_->ReinjectSkippedSavingsEndingAt(before_node);
5903  }
5904  }
5905  }
5906  savings_container_->Update(/*update_best_saving*/ false);
5907  }
5908 }
5909 
5910 void ParallelSavingsFilteredHeuristic::MergeRoutes(int first_vehicle,
5911  int second_vehicle,
5912  int64 before_node,
5913  int64 after_node) {
5914  if (StopSearch()) return;
5915  const int64 new_first_node = first_node_on_route_[first_vehicle];
5916  DCHECK_EQ(vehicle_of_first_or_last_node_[new_first_node], first_vehicle);
5917  CHECK_EQ(Value(model()->Start(first_vehicle)), new_first_node);
5918  const int64 new_last_node = last_node_on_route_[second_vehicle];
5919  DCHECK_EQ(vehicle_of_first_or_last_node_[new_last_node], second_vehicle);
5920  CHECK_EQ(Value(new_last_node), model()->End(second_vehicle));
5921 
5922  // Select the vehicle with lower fixed cost to merge the routes.
5923  int used_vehicle = first_vehicle;
5924  int unused_vehicle = second_vehicle;
5925  if (model()->GetFixedCostOfVehicle(first_vehicle) >
5926  model()->GetFixedCostOfVehicle(second_vehicle)) {
5927  used_vehicle = second_vehicle;
5928  unused_vehicle = first_vehicle;
5929  }
5930 
5931  SetValue(before_node, after_node);
5932  SetValue(model()->Start(unused_vehicle), model()->End(unused_vehicle));
5933  if (used_vehicle == first_vehicle) {
5934  SetValue(new_last_node, model()->End(used_vehicle));
5935  } else {
5936  SetValue(model()->Start(used_vehicle), new_first_node);
5937  }
5938  bool committed = Commit();
5939  if (!committed &&
5940  model()->GetVehicleClassIndexOfVehicle(first_vehicle).value() !=
5941  model()->GetVehicleClassIndexOfVehicle(second_vehicle).value()) {
5942  // Try committing on other vehicle instead.
5943  std::swap(used_vehicle, unused_vehicle);
5944  SetValue(before_node, after_node);
5945  SetValue(model()->Start(unused_vehicle), model()->End(unused_vehicle));
5946  if (used_vehicle == first_vehicle) {
5947  SetValue(new_last_node, model()->End(used_vehicle));
5948  } else {
5949  SetValue(model()->Start(used_vehicle), new_first_node);
5950  }
5951  committed = Commit();
5952  }
5953  if (committed) {
5954  // Make unused_vehicle available
5955  vehicle_type_curator_->ReinjectVehicleOfClass(
5956  unused_vehicle,
5957  model()->GetVehicleClassIndexOfVehicle(unused_vehicle).value(),
5958  model()->GetFixedCostOfVehicle(unused_vehicle));
5959 
5960  // Update the first and last nodes on vehicles.
5961  first_node_on_route_[unused_vehicle] = -1;
5962  last_node_on_route_[unused_vehicle] = -1;
5963  vehicle_of_first_or_last_node_[before_node] = -1;
5964  vehicle_of_first_or_last_node_[after_node] = -1;
5965  first_node_on_route_[used_vehicle] = new_first_node;
5966  last_node_on_route_[used_vehicle] = new_last_node;
5967  vehicle_of_first_or_last_node_[new_last_node] = used_vehicle;
5968  vehicle_of_first_or_last_node_[new_first_node] = used_vehicle;
5969  }
5970 }
5971 
5972 // ChristofidesFilteredHeuristic
5974  RoutingModel* model, LocalSearchFilterManager* filter_manager,
5975  bool use_minimum_matching)
5976  : RoutingFilteredHeuristic(model, filter_manager),
5977  use_minimum_matching_(use_minimum_matching) {}
5978 
5979 // TODO(user): Support pickup & delivery.
5981  const int size = model()->Size() - model()->vehicles() + 1;
5982  // Node indices for Christofides solver.
5983  // 0: start/end node
5984  // >0: non start/end nodes
5985  // TODO(user): Add robustness to fixed arcs by collapsing them into meta-
5986  // nodes.
5987  std::vector<int> indices(1, 0);
5988  for (int i = 1; i < size; ++i) {
5989  if (!model()->IsStart(i) && !model()->IsEnd(i)) {
5990  indices.push_back(i);
5991  }
5992  }
5993  const int num_cost_classes = model()->GetCostClassesCount();
5994  std::vector<std::vector<int>> path_per_cost_class(num_cost_classes);
5995  std::vector<bool> class_covered(num_cost_classes, false);
5996  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
5997  const int64 cost_class =
5998  model()->GetCostClassIndexOfVehicle(vehicle).value();
5999  if (!class_covered[cost_class]) {
6000  class_covered[cost_class] = true;
6001  const int64 start = model()->Start(vehicle);
6002  const int64 end = model()->End(vehicle);
6003  auto cost = [this, &indices, start, end, cost_class](int from, int to) {
6004  DCHECK_LT(from, indices.size());
6005  DCHECK_LT(to, indices.size());
6006  const int from_index = (from == 0) ? start : indices[from];
6007  const int to_index = (to == 0) ? end : indices[to];
6008  const int64 cost =
6009  model()->GetArcCostForClass(from_index, to_index, cost_class);
6010  // To avoid overflow issues, capping costs at kint64max/2, the maximum
6011  // value supported by MinCostPerfectMatching.
6012  // TODO(user): Investigate if ChristofidesPathSolver should not
6013  // return a status to bail out fast in case of problem.
6014  return std::min(cost, kint64max / 2);
6015  };
6016  using Cost = decltype(cost);
6018  indices.size(), cost);
6019  if (use_minimum_matching_) {
6020  christofides_solver.SetMatchingAlgorithm(
6022  MINIMUM_WEIGHT_MATCHING);
6023  }
6024  if (christofides_solver.Solve()) {
6025  path_per_cost_class[cost_class] =
6026  christofides_solver.TravelingSalesmanPath();
6027  }
6028  }
6029  }
6030  // TODO(user): Investigate if sorting paths per cost improves solutions.
6031  for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
6032  const int64 cost_class =
6033  model()->GetCostClassIndexOfVehicle(vehicle).value();
6034  const std::vector<int>& path = path_per_cost_class[cost_class];
6035  if (path.empty()) continue;
6036  DCHECK_EQ(0, path[0]);
6037  DCHECK_EQ(0, path.back());
6038  // Extend route from start.
6039  int prev = GetStartChainEnd(vehicle);
6040  const int end = model()->End(vehicle);
6041  for (int i = 1; i < path.size() - 1 && prev != end; ++i) {
6042  if (StopSearch()) return false;
6043  int next = indices[path[i]];
6044  if (!Contains(next)) {
6045  SetValue(prev, next);
6046  SetValue(next, end);
6047  if (Commit()) {
6048  prev = next;
6049  }
6050  }
6051  }
6052  }
6054  return Commit();
6055 }
6056 
6057 namespace {
6058 // The description is in routing.h:MakeGuidedSlackFinalizer
6059 class GuidedSlackFinalizer : public DecisionBuilder {
6060  public:
6061  GuidedSlackFinalizer(const RoutingDimension* dimension, RoutingModel* model,
6062  std::function<int64(int64)> initializer);
6063  Decision* Next(Solver* solver) override;
6064 
6065  private:
6066  int64 SelectValue(int64 index);
6067  int64 ChooseVariable();
6068 
6069  const RoutingDimension* const dimension_;
6070  RoutingModel* const model_;
6071  const std::function<int64(int64)> initializer_;
6072  RevArray<bool> is_initialized_;
6073  std::vector<int64> initial_values_;
6074  Rev<int64> current_index_;
6075  Rev<int64> current_route_;
6076  RevArray<int64> last_delta_used_;
6077 
6078  DISALLOW_COPY_AND_ASSIGN(GuidedSlackFinalizer);
6079 };
6080 
6081 GuidedSlackFinalizer::GuidedSlackFinalizer(
6082  const RoutingDimension* dimension, RoutingModel* model,
6083  std::function<int64(int64)> initializer)
6084  : dimension_(ABSL_DIE_IF_NULL(dimension)),
6085  model_(ABSL_DIE_IF_NULL(model)),
6086  initializer_(std::move(initializer)),
6087  is_initialized_(dimension->slacks().size(), false),
6088  initial_values_(dimension->slacks().size(), kint64min),
6089  current_index_(model_->Start(0)),
6090  current_route_(0),
6091  last_delta_used_(dimension->slacks().size(), 0) {}
6092 
6093 Decision* GuidedSlackFinalizer::Next(Solver* solver) {
6094  CHECK_EQ(solver, model_->solver());
6095  const int node_idx = ChooseVariable();
6096  CHECK(node_idx == -1 ||
6097  (node_idx >= 0 && node_idx < dimension_->slacks().size()));
6098  if (node_idx != -1) {
6099  if (!is_initialized_[node_idx]) {
6100  initial_values_[node_idx] = initializer_(node_idx);
6101  is_initialized_.SetValue(solver, node_idx, true);
6102  }
6103  const int64 value = SelectValue(node_idx);
6104  IntVar* const slack_variable = dimension_->SlackVar(node_idx);
6105  return solver->MakeAssignVariableValue(slack_variable, value);
6106  }
6107  return nullptr;
6108 }
6109 
6110 int64 GuidedSlackFinalizer::SelectValue(int64 index) {
6111  const IntVar* const slack_variable = dimension_->SlackVar(index);
6112  const int64 center = initial_values_[index];
6113  const int64 max_delta =
6114  std::max(center - slack_variable->Min(), slack_variable->Max() - center) +
6115  1;
6116  int64 delta = last_delta_used_[index];
6117 
6118  // The sequence of deltas is 0, 1, -1, 2, -2 ...
6119  // Only the values inside the domain of variable are returned.
6120  while (std::abs(delta) < max_delta &&
6121  !slack_variable->Contains(center + delta)) {
6122  if (delta > 0) {
6123  delta = -delta;
6124  } else {
6125  delta = -delta + 1;
6126  }
6127  }
6128  last_delta_used_.SetValue(model_->solver(), index, delta);
6129  return center + delta;
6130 }
6131 
6132 int64 GuidedSlackFinalizer::ChooseVariable() {
6133  int64 int_current_node = current_index_.Value();
6134  int64 int_current_route = current_route_.Value();
6135 
6136  while (int_current_route < model_->vehicles()) {
6137  while (!model_->IsEnd(int_current_node) &&
6138  dimension_->SlackVar(int_current_node)->Bound()) {
6139  int_current_node = model_->NextVar(int_current_node)->Value();
6140  }
6141  if (!model_->IsEnd(int_current_node)) {
6142  break;
6143  }
6144  int_current_route += 1;
6145  if (int_current_route < model_->vehicles()) {
6146  int_current_node = model_->Start(int_current_route);
6147  }
6148  }
6149 
6150  CHECK(int_current_route == model_->vehicles() ||
6151  !dimension_->SlackVar(int_current_node)->Bound());
6152  current_index_.SetValue(model_->solver(), int_current_node);
6153  current_route_.SetValue(model_->solver(), int_current_route);
6154  if (int_current_route < model_->vehicles()) {
6155  return int_current_node;
6156  } else {
6157  return -1;
6158  }
6159 }
6160 } // namespace
6161 
6163  const RoutingDimension* dimension,
6164  std::function<int64(int64)> initializer) {
6165  return solver_->RevAlloc(
6166  new GuidedSlackFinalizer(dimension, this, std::move(initializer)));
6167 }
6168 
6170  CHECK_EQ(base_dimension_, this);
6171  CHECK(!model_->IsEnd(node));
6172  // Recall that the model is cumul[i+1] = cumul[i] + transit[i] + slack[i]. Our
6173  // aim is to find a value for slack[i] such that cumul[i+1] + transit[i+1] is
6174  // minimized.
6175  const int64 next = model_->NextVar(node)->Value();
6176  if (model_->IsEnd(next)) {
6177  return SlackVar(node)->Min();
6178  }
6179  const int64 next_next = model_->NextVar(next)->Value();
6180  const int64 serving_vehicle = model_->VehicleVar(node)->Value();
6181  CHECK_EQ(serving_vehicle, model_->VehicleVar(next)->Value());
6182  const RoutingModel::StateDependentTransit transit_from_next =
6184  state_dependent_class_evaluators_
6185  [state_dependent_vehicle_to_class_[serving_vehicle]])(next,
6186  next_next);
6187  // We have that transit[i+1] is a function of cumul[i+1].
6188  const int64 next_cumul_min = CumulVar(next)->Min();
6189  const int64 next_cumul_max = CumulVar(next)->Max();
6190  const int64 optimal_next_cumul =
6191  transit_from_next.transit_plus_identity->RangeMinArgument(
6192  next_cumul_min, next_cumul_max + 1);
6193  // A few checks to make sure we're on the same page.
6194  DCHECK_LE(next_cumul_min, optimal_next_cumul);
6195  DCHECK_LE(optimal_next_cumul, next_cumul_max);
6196  // optimal_next_cumul = cumul + transit + optimal_slack, so
6197  // optimal_slack = optimal_next_cumul - cumul - transit.
6198  // In the current implementation TransitVar(i) = transit[i] + slack[i], so we
6199  // have to find the transit from the evaluators.
6200  const int64 current_cumul = CumulVar(node)->Value();
6201  const int64 current_state_independent_transit = model_->TransitCallback(
6202  class_evaluators_[vehicle_to_class_[serving_vehicle]])(node, next);
6203  const int64 current_state_dependent_transit =
6204  model_
6206  state_dependent_class_evaluators_
6207  [state_dependent_vehicle_to_class_[serving_vehicle]])(node,
6208  next)
6209  .transit->Query(current_cumul);
6210  const int64 optimal_slack = optimal_next_cumul - current_cumul -
6211  current_state_independent_transit -
6212  current_state_dependent_transit;
6213  CHECK_LE(SlackVar(node)->Min(), optimal_slack);
6214  CHECK_LE(optimal_slack, SlackVar(node)->Max());
6215  return optimal_slack;
6216 }
6217 
6218 namespace {
6219 class GreedyDescentLSOperator : public LocalSearchOperator {
6220  public:
6221  explicit GreedyDescentLSOperator(std::vector<IntVar*> variables);
6222 
6223  bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
6224  void Start(const Assignment* assignment) override;
6225 
6226  private:
6227  int64 FindMaxDistanceToDomain(const Assignment* assignment);
6228 
6229  const std::vector<IntVar*> variables_;
6230  const Assignment* center_;
6231  int64 current_step_;
6232  // The deltas are returned in this order:
6233  // (current_step_, 0, ... 0), (-current_step_, 0, ... 0),
6234  // (0, current_step_, ... 0), (0, -current_step_, ... 0),
6235  // ...
6236  // (0, ... 0, current_step_), (0, ... 0, -current_step_).
6237  // current_direction_ keeps track what was the last returned delta.
6238  int64 current_direction_;
6239 
6240  DISALLOW_COPY_AND_ASSIGN(GreedyDescentLSOperator);
6241 };
6242 
6243 GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)
6244  : variables_(std::move(variables)),
6245  center_(nullptr),
6246  current_step_(0),
6247  current_direction_(0) {}
6248 
6249 bool GreedyDescentLSOperator::MakeNextNeighbor(Assignment* delta,
6250  Assignment* /*deltadelta*/) {
6251  static const int64 sings[] = {1, -1};
6252  for (; 1 <= current_step_; current_step_ /= 2) {
6253  for (; current_direction_ < 2 * variables_.size();) {
6254  const int64 variable_idx = current_direction_ / 2;
6255  IntVar* const variable = variables_[variable_idx];
6256  const int64 sign_index = current_direction_ % 2;
6257  const int64 sign = sings[sign_index];
6258  const int64 offset = sign * current_step_;
6259  const int64 new_value = center_->Value(variable) + offset;
6260  ++current_direction_;
6261  if (variable->Contains(new_value)) {
6262  delta->Add(variable);
6263  delta->SetValue(variable, new_value);
6264  return true;
6265  }
6266  }
6267  current_direction_ = 0;
6268  }
6269  return false;
6270 }
6271 
6272 void GreedyDescentLSOperator::Start(const Assignment* assignment) {
6273  CHECK(assignment != nullptr);
6274  current_step_ = FindMaxDistanceToDomain(assignment);
6275  center_ = assignment;
6276 }
6277 
6278 int64 GreedyDescentLSOperator::FindMaxDistanceToDomain(
6279  const Assignment* assignment) {
6280  int64 result = kint64min;
6281  for (const IntVar* const var : variables_) {
6282  result = std::max(result, std::abs(var->Max() - assignment->Value(var)));
6283  result = std::max(result, std::abs(var->Min() - assignment->Value(var)));
6284  }
6285  return result;
6286 }
6287 } // namespace
6288 
6289 std::unique_ptr<LocalSearchOperator> RoutingModel::MakeGreedyDescentLSOperator(
6290  std::vector<IntVar*> variables) {
6291  return std::unique_ptr<LocalSearchOperator>(
6292  new GreedyDescentLSOperator(std::move(variables)));
6293 }
6294 
6296  const RoutingDimension* dimension) {
6297  CHECK(dimension != nullptr);
6298  CHECK(dimension->base_dimension() == dimension);
6299  std::function<int64(int64)> slack_guide = [dimension](int64 index) {
6300  return dimension->ShortestTransitionSlack(index);
6301  };
6302  DecisionBuilder* const guided_finalizer =
6303  MakeGuidedSlackFinalizer(dimension, slack_guide);
6304  DecisionBuilder* const slacks_finalizer =
6305  solver_->MakeSolveOnce(guided_finalizer);
6306  std::vector<IntVar*> start_cumuls(vehicles_, nullptr);
6307  for (int64 vehicle_idx = 0; vehicle_idx < vehicles_; ++vehicle_idx) {
6308  start_cumuls[vehicle_idx] = dimension->CumulVar(starts_[vehicle_idx]);
6309  }
6310  LocalSearchOperator* const hill_climber =
6311  solver_->RevAlloc(new GreedyDescentLSOperator(start_cumuls));
6313  solver_->MakeLocalSearchPhaseParameters(CostVar(), hill_climber,
6314  slacks_finalizer);
6315  Assignment* const first_solution = solver_->MakeAssignment();
6316  first_solution->Add(start_cumuls);
6317  for (IntVar* const cumul : start_cumuls) {
6318  first_solution->SetValue(cumul, cumul->Min());
6319  }
6320  DecisionBuilder* const finalizer =
6321  solver_->MakeLocalSearchPhase(first_solution, parameters);
6322  return finalizer;
6323 }
6324 } // namespace operations_research
int64 min
Definition: alldiff_cst.cc:138
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define DCHECK_LE(val1, val2)
Definition: base/logging.h:887
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define CHECK_EQ(val1, val2)
Definition: base/logging.h:697
#define CHECK_GE(val1, val2)
Definition: base/logging.h:701
#define CHECK_GT(val1, val2)
Definition: base/logging.h:702
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_GT(val1, val2)
Definition: base/logging.h:890
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define CHECK_LE(val1, val2)
Definition: base/logging.h:699
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
#define ABSL_DIE_IF_NULL
Definition: base/logging.h:39
#define VLOG(verboselevel)
Definition: base/logging.h:978
const std::vector< T * > * Raw() const
bool Contains(const T *val) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
const E & Element(const V *const var) const
void Resize(size_t size)
Advanced usage: Resizes the container, potentially adding elements with null variables.
An Assignment is a variable -> domains mapping, used to report solutions to the user.
int64 Value(const IntVar *const var) const
const IntContainer & IntVarContainer() const
void SetValue(const IntVar *const var, int64 value)
void Copy(const Assignment *assignment)
Copies 'assignment' to the current assignment, clearing its previous content.
AssignmentContainer< IntVar, IntVarElement > IntContainer
IntVarElement * Add(IntVar *const var)
virtual std::string DebugString() const
Generic path-based filter class.
Definition: routing.h:3832
static const int64 kUnassigned
Definition: routing.h:3841
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size)
void OnSynchronize(const Assignment *delta) override
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
Definition: routing.h:3908
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
void OnSynchronize(const Assignment *delta) override
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
Definition: routing.h:3543
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(const std::vector< int > &vehicles)
Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::ve...
std::function< int64(int64, int64, int64)> evaluator_
Definition: routing.h:3184
void InsertBetween(int64 node, int64 predecessor, int64 successor)
Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subs...
void InitializePriorityQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, Queue *priority_queue)
Initializes the priority_queue by inserting the best entry corresponding to each node,...
void AppendEvaluatedPositionsAfter(int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle, std::vector< ValuedPosition > *valued_positions)
Helper method to the ComputeEvaluatorSortedPositions* methods.
int64 GetUnperformedValue(int64 node_to_insert) const
Returns the cost of unperforming node 'node_to_insert'.
int64 GetInsertionCostForNodeAtPosition(int64 node_to_insert, int64 insert_after, int64 insert_before, int vehicle) const
Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'veh...
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
ChristofidesFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
std::vector< NodeIndex > TravelingSalesmanPath()
Definition: christofides.h:241
void SetMatchingAlgorithm(MatchingAlgorithm matching)
Definition: christofides.h:61
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
bool operator<(const NodeEntry &other) const
int vehicle() const
void set_vehicle(int vehicle)
int insert_after() const
int GetHeapIndex() const
int64 value() const
void set_insert_after(int insert_after)
NodeEntry(int node_to_insert, int insert_after, int vehicle)
void SetHeapIndex(int h)
void set_value(int64 value)
int node_to_insert() const
bool operator<(const PairEntry &other) const
int vehicle() const
void set_vehicle(int vehicle)
int GetHeapIndex() const
int64 value() const
PairEntry(int pickup_to_insert, int pickup_insert_after, int delivery_to_insert, int delivery_insert_after, int vehicle)
int pickup_insert_after() const
void set_pickup_insert_after(int pickup_insert_after)
int delivery_insert_after() const
void SetHeapIndex(int h)
void set_value(int64 value)
int delivery_to_insert() const
int pickup_to_insert() const
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
Utility class to encapsulate an IntVarIterator and use it in a range-based loop.
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64 Max() const =0
virtual int64 Min() const =0
Decision * Next(Solver *solver) override
This is the main method of the decision builder class.
int64 number_of_decisions() const
Returns statistics from its underlying heuristic.
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
Generic filter-based heuristic applied to IntVars.
Definition: routing.h:2997
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
int Size() const
Returns the number of variables the decision builder is trying to instantiate.
Definition: routing.h:3050
bool Contains(int64 index) const
Returns true if the variable of index 'index' is in the current solution.
Definition: routing.h:3045
int64 Value(int64 index) const
Returns the value of the variable of index 'index' in the last committed solution.
Definition: routing.h:3041
bool Commit()
Commits the modifications to the current solution if these modifications are "filter-feasible",...
IntVar * Var(int64 index) const
Returns the variable of index 'index'.
Definition: routing.h:3052
void ResetSolution()
Resets the data members for a new solution.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
virtual bool InitializeSolution()
Virtual method to initialize the solution.
Definition: routing.h:3019
void SetValue(int64 index, int64 value)
Modifies the current solution by setting the variable of index 'index' to value 'value'.
Definition: routing.h:3030
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, LocalSearchFilterManager *filter_manager)
Assignment *const BuildSolution()
Builds a solution.
The class IntVar is a subset of IntExpr.
virtual bool Contains(int64 v) const =0
This method returns whether the value 'v' is in the domain of the variable.
virtual int64 Value() const =0
This method returns the value of the variable.
bool FindIndex(IntVar *const var, int64 *index) const
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
bool Accept(LocalSearchMonitor *const monitor, const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max)
Returns true iff all filters return true, and the sum of their accepted objectives is between objecti...
void Synchronize(const Assignment *assignment, const Assignment *delta)
Synchronizes all filters to assignment.
The base class for all local search operators.
virtual int64 RangeMinArgument(int64 from, int64 to) const =0
Reversible array of POD types.
This class adds reversibility to a POD type.
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
int64 global_span_cost_coefficient() const
Definition: routing.h:2681
RoutingModel * model() const
Returns the model on which the dimension was created.
Definition: routing.h:2372
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
Definition: routing.h:2386
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
Definition: routing.cc:6900
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
Definition: routing.h:2608
int64 ShortestTransitionSlack(int64 node) const
It makes sense to use the function only for self-dependent dimension.
IntVar * SlackVar(int64 index) const
Definition: routing.h:2389
const std::vector< NodePrecedence > & GetNodePrecedences() const
Definition: routing.h:2656
Filter-based heuristic dedicated to routing.
Definition: routing.h:3076
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
Definition: routing.h:3086
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
Definition: routing.h:3088
const Assignment * BuildSolutionFromRoutes(const std::function< int64(int64)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
virtual void SetVehicleIndex(int64 node, int vehicle)
Definition: routing.h:3102
bool StopSearch() override
Returns true if the search must be stopped.
Definition: routing.h:3101
void MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed.
void MakeDisjunctionNodesUnperformed(int64 node)
Make nodes in the same disjunction as 'node' unperformed.
void MakePartiallyPerformedPairsUnperformed()
Make all partially performed pickup and delivery pairs unperformed.
bool VehicleIsEmpty(int vehicle) const
Definition: routing.h:3104
RoutingFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
Manager for any NodeIndex <-> variable index conversion.
RoutingIndexPair IndexPair
Definition: routing.h:247
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(int64 index, int64 max_cardinality, F f) const
Calls f for each variable index of indices in the same disjunctions as the node corresponding to the ...
Definition: routing.h:639
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
Definition: routing.h:1251
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1347
bool CheckLimit()
Returns true if the search limit has been crossed.
Definition: routing.h:1330
static std::unique_ptr< LocalSearchOperator > MakeGreedyDescentLSOperator(std::vector< IntVar * > variables)
Perhaps move it to constraint_solver.h.
int64 GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
Definition: routing.cc:1210
Solver * solver() const
Returns the underlying constraint solver.
Definition: routing.h:1327
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
RoutingIndexPairs IndexPairs
Definition: routing.h:248
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
Definition: routing.h:1222
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
Definition: routing.cc:3928
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:746
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
Definition: routing.h:234
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
Definition: routing.h:232
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
Definition: routing.h:236
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1345
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
Definition: routing.h:1200
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
Definition: routing.h:1224
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
Definition: routing.h:421
DecisionBuilder * MakeSelfDependentDimensionFinalizer(const RoutingDimension *dimension)
SWIG
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
Definition: routing.h:1268
DecisionBuilder * MakeGuidedSlackFinalizer(const RoutingDimension *dimension, std::function< int64(int64)> initializer)
The next few members are in the public section only for testing purposes.
const TransitCallback2 & TransitCallback(int callback_index) const
Definition: routing.h:413
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
Definition: routing.cc:3896
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
Definition: routing.cc:1707
RoutingDisjunctionIndex DisjunctionIndex
Definition: routing.h:240
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
Definition: routing.cc:1713
void AddNewSaving(const Saving &saving, int64 total_cost, int64 before_node, int64 after_node, int vehicle_type)
void InitializeContainer(int64 size, int64 saving_neighbors)
SavingsContainer(const SavingsFilteredHeuristic *savings_db, int vehicle_types)
const std::vector< Saving > & GetSortedSavingsForVehicleType(int type)
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
Definition: routing.h:3635
int StartNewRouteWithBestVehicleOfType(int type, int64 before_node, int64 after_node)
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->a...
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
Definition: routing.h:3699
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
int64 GetVehicleTypeFromSaving(const Saving &saving) const
Returns the cost class from a saving.
Definition: routing.h:3670
std::unique_ptr< SavingsContainer< Saving > > savings_container_
Definition: routing.h:3697
int64 GetSavingValue(const Saving &saving) const
Returns the saving value from a saving.
Definition: routing.h:3682
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int64 GetBeforeNodeFromSaving(const Saving &saving) const
Returns the "before node" from a saving.
Definition: routing.h:3674
int64 GetAfterNodeFromSaving(const Saving &saving) const
Returns the "after node" from a saving.
Definition: routing.h:3678
std::function< bool(int64, int64, int64)> VariableValueComparator
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
bool Solve(DecisionBuilder *const db, const std::vector< SearchMonitor * > &monitors)
T * RevAlloc(T *object)
Registers the given object as being reversible.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
void Set(IntegerType index)
Definition: bitset.h:803
void Update(const std::function< bool(int)> &remove_vehicle)
Goes through all the currently stored vehicles and removes vehicles for which remove_vehicle() return...
std::pair< int, int > GetCompatibleVehicleOfType(int type, std::function< bool(int)> vehicle_is_compatible, std::function< bool(int)> stop_and_return_vehicle)
Searches for the best compatible vehicle of the given type, i.e.
void Reset(const std::function< bool(int)> &store_vehicle)
Resets the vehicles stored, storing only vehicles from the vehicle_type_container_ for which store_ve...
Block * next
SatParameters parameters
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
const int64 limit_
const std::vector< IntVar * > cumuls_
GRBmodel * model
static const int64 kint64max
int64_t int64
static const int64 kint64min
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
Collection::value_type::second_type & LookupOrInsert(Collection *const collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:207
void STLClearObject(T *obj)
Definition: stl_util.h:123
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
const Collection::value_type::second_type & FindWithDefault(const Collection &collection, const typename Collection::value_type::first_type &key, const typename Collection::value_type::second_type &value)
Definition: map_util.h:26
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters &parameters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
int64 CapSub(int64 x, int64 y)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
int64 CapAdd(int64 x, int64 y)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
int64 CapProd(int64 x, int64 y)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
LocalSearchFilter * MakeUnaryDimensionFilter(Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
static const int kUnassigned
Definition: routing.cc:638
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
int index
Definition: pack.cc:508
int64 delta
Definition: resource.cc:1684
int64 cost
int64 capacity
int cumul_value_support
std::vector< int64 > path_values
int64 bound
int64 cumul_value
ABSL_FLAG(bool, routing_strong_debug_checks, false, "Run stronger checks in debug; these stronger tests might change " "the complexity of the code in particular.")
int64 coefficient
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
Definition: routing.h:3209
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
Definition: routing.h:3200
double farthest_seeds_ratio
The ratio of routes on which to insert farthest nodes as seeds before starting the cheapest insertion...
Definition: routing.h:3203
bool use_neighbors_ratio_for_initialization
If true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion p...
Definition: routing.h:3214
bool add_unperformed_entries
If true, entries are created for making the nodes/pairs unperformed, and when the cost of making a no...
Definition: routing.h:3219
What follows is relevant for models with time/state dependent transits.
Definition: routing.h:264
RangeMinMaxIndexFunction * transit_plus_identity
f(x)
Definition: routing.h:266
Definition: routing.h:359
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
Definition: routing.h:378
std::vector< std::deque< int > > vehicles_per_vehicle_class
Definition: routing.h:379
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
Definition: routing.h:3640
double arc_coefficient
arc_coefficient is a strictly positive parameter indicating the coefficient of the arc being consider...
Definition: routing.h:3649
double max_memory_usage_bytes
The number of neighbors considered for each node is also adapted so that the stored Savings don't use...
Definition: routing.h:3643
bool add_reverse_arcs
If add_reverse_arcs is true, the neighborhood relationships are considered symmetrically.
Definition: routing.h:3646