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"
40#include "ortools/util/bitset.h"
42
43ABSL_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.");
46ABSL_FLAG(bool, routing_shift_insertion_cost_by_penalty, true,
47 "Shift insertion costs by the penalty of the inserted node(s).");
48
49namespace operations_research {
50
51namespace {
52
53// Max active vehicles filter.
54
55class 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
117namespace {
118
119// Node disjunction filter class.
120
121class 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
292BasePathFilter::BasePathFilter(const std::vector<IntVar*>& nexts,
293 int next_domain_size)
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
372void 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
396bool 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
416void 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
499void 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
509void 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
520namespace {
521
522class 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
555VehicleAmortizedCostFilter::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
577void 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
585void 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
609void VehicleAmortizedCostFilter::InitializeAcceptPath() {
610 delta_vehicle_cost_ = current_vehicle_cost_;
611}
612
613bool 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
661bool 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
675namespace {
676
677class 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
701TypeRegulationsFilter::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
725void 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
748bool 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
805bool 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
824namespace {
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
831class 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
858ChainCumulFilter::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.
882void 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).
911bool 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
941class 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
1232PathCumulFilter::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
1377int64 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
1388int64 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
1399int64 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
1411int64 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
1426void 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
1597bool 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
1765bool 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
1946void 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
1953bool 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
2015void 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
2052int64 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
2082namespace {
2083
2084bool 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
2099bool 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
2264namespace {
2265
2266// Filter for pickup/delivery precedences.
2267class 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
2291PickupDeliveryFilter::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
2312bool 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
2326bool 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
2391template <bool lifo>
2392bool 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
2456namespace {
2457
2458// Vehicle variable filter
2459class 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
2476VehicleVarFilter::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
2487bool 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
2500bool 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
2507bool 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
2525namespace {
2526
2527class 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
2544CumulBoundsPropagatorFilter::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
2552bool 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
2584namespace {
2585
2586class 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
2609LPCumulFilter::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
2620bool 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
2655int64 LPCumulFilter::GetAcceptedObjectiveValue() const {
2656 return delta_cost_without_transit_;
2657}
2658
2659void 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
2676int64 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
2691CPFeasibilityFilter::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
2716void 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;
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
2757void 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
2984bool 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
2994 : IntVarFilteredHeuristic(model->solver(), model->Nexts(), filter_manager),
2995 model_(model) {}
2996
2997bool 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)) {
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
3139std::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
3170template <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
3231namespace {
3232template <class T>
3233void 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
3370void 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
3447bool 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
3454bool 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
3548void 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
3559void GlobalCheapestInsertionFilteredHeuristic::InsertPairs(
3560 const std::vector<int>& pair_indices) {
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
3624bool 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
3725void GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(
3726 const std::vector<int>& nodes, const absl::flat_hash_set<int>& vehicles) {
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
3786bool 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
3882void 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
3909void 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
3932void 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
3966template <class Queue>
3967int 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
4016void 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
4057void 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
4181void 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
4201void 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
4274void 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
4342void 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
4358void 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
4392void 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
4407int64 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
4431void 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
4460void 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
4528void 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
4563void 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
4575void 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
4615void 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_ =
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
4723void 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
4740void 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
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.
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
4893bool 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
4916int64 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
4932void 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
4957int64 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
4965void 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.
5021template <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
5404SavingsFilteredHeuristic::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
5457 ->GetCompatibleVehicleOfType(
5458 type, vehicle_is_compatible,
5459 /*stop_and_return_vehicle*/ [](int) { return false; })
5460 .first;
5461}
5462
5463void 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.
5492void 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
5599int64 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
5642void 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
5760void 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
5910void 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
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
6057namespace {
6058// The description is in routing.h:MakeGuidedSlackFinalizer
6059class 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
6081GuidedSlackFinalizer::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
6093Decision* 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
6110int64 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
6132int64 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
6218namespace {
6219class 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
6243GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)
6244 : variables_(std::move(variables)),
6245 center_(nullptr),
6246 current_step_(0),
6247 current_direction_(0) {}
6248
6249bool 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
6272void GreedyDescentLSOperator::Start(const Assignment* assignment) {
6273 CHECK(assignment != nullptr);
6274 current_step_ = FindMaxDistanceToDomain(assignment);
6275 center_ = assignment;
6276}
6277
6278int64 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
6289std::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
const E & Element(const V *const var) const
E * AddAtPosition(V *var, int position)
Advanced usage: Adds element at a given position; position has to have been allocated with Assignment...
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
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)
const IntContainer & IntVarContainer() const
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
IntVar * Var(int64 index) const
Returns the variable of index 'index'.
Definition: routing.h:3052
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",...
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
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
int64 global_span_cost_coefficient() const
Definition: routing.h:2681
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
Definition: routing.cc:6900
IntVar * SlackVar(int64 index) const
Definition: routing.h:2389
RoutingModel * model() const
Returns the model on which the dimension was created.
Definition: routing.h:2372
const std::vector< NodePrecedence > & GetNodePrecedences() const
Definition: routing.h:2656
int64 ShortestTransitionSlack(int64 node) const
It makes sense to use the function only for self-dependent dimension.
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
Definition: routing.h:2608
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.
Solver * solver() const
Returns the underlying constraint solver.
Definition: routing.h:1327
const TransitCallback2 & TransitCallback(int callback_index) const
Definition: routing.h:413
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
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:746
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.
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
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
RoutingIndexPairs IndexPairs
Definition: routing.h:248
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
Definition: routing.h:421
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
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
@ 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
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
Definition: routing.h:1222
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
Definition: routing.h:1224
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.
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)
const std::vector< Saving > & GetSortedSavingsForVehicleType(int type)
void InitializeContainer(int64 size, int64 saving_neighbors)
SavingsContainer(const SavingsFilteredHeuristic *savings_db, int vehicle_types)
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)
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
T * RevAlloc(T *object)
Registers the given object as being reversible.
void Set(IntegerType index)
Definition: bitset.h:803
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition: bitset.h:813
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
bool ContainsKey(const Collection &collection, const Key &key)
Definition: map_util.h:170
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
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...
int64 CapAdd(int64 x, int64 y)
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)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
int64 CapProd(int64 x, int64 y)
int64 CapSub(int64 x, int64 y)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
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)
STL namespace.
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