Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
routing_search.cc
Go to the documentation of this file.
1// Copyright 2010-2025 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
20
21#include <algorithm>
22#include <cmath>
23#include <cstdint>
24#include <cstdlib>
25#include <deque>
26#include <functional>
27#include <limits>
28#include <map>
29#include <memory>
30#include <optional>
31#include <set>
32#include <string>
33#include <tuple>
34#include <utility>
35#include <vector>
36
37#include "absl/algorithm/container.h"
38#include "absl/base/attributes.h"
39#include "absl/container/btree_set.h"
40#include "absl/container/flat_hash_map.h"
41#include "absl/container/flat_hash_set.h"
42#include "absl/container/inlined_vector.h"
43#include "absl/flags/flag.h"
44#include "absl/log/check.h"
45#include "absl/log/die_if_null.h"
46#include "absl/strings/str_cat.h"
47#include "absl/strings/string_view.h"
48#include "absl/time/time.h"
49#include "absl/types/span.h"
56#include "ortools/base/types.h"
65#include "ortools/util/bitset.h"
68
69namespace operations_research {
71} // namespace operations_research
72
73ABSL_FLAG(bool, routing_shift_insertion_cost_by_penalty, true,
74 "Shift insertion costs by the penalty of the inserted node(s).");
75
76ABSL_FLAG(int64_t, sweep_sectors, 1,
77 "The number of sectors the space is divided into before it is sweeped"
78 " by the ray.");
79
80namespace operations_research {
81
82namespace {
83void ConvertAssignment(const RoutingModel* src_model, const Assignment* src,
84 const RoutingModel* dst_model, Assignment* dst) {
85 DCHECK_EQ(src_model->Nexts().size(), dst_model->Nexts().size());
86 DCHECK_NE(src, nullptr);
87 DCHECK_EQ(src_model->solver(), src->solver());
88 DCHECK_EQ(dst_model->solver(), dst->solver());
89 for (int i = 0; i < src_model->Nexts().size(); i++) {
90 IntVar* const dst_next_var = dst_model->NextVar(i);
91 if (!dst->Contains(dst_next_var)) {
92 dst->Add(dst_next_var);
93 }
94 dst->SetValue(dst_next_var, src->Value(src_model->NextVar(i)));
95 }
96}
97
98bool AreAssignmentsEquivalent(const RoutingModel& model,
99 const Assignment& assignment1,
100 const Assignment& assignment2) {
101 for (IntVar* next_var : model.Nexts()) {
102 if (assignment1.Value(next_var) != assignment2.Value(next_var)) {
103 return false;
104 }
105 }
106 return true;
107}
108
109absl::Duration GetTimeLimit(const RoutingSearchParameters& search_parameters) {
110 return search_parameters.has_time_limit()
111 ? util_time::DecodeGoogleApiProto(search_parameters.time_limit())
112 .value()
113 : absl::InfiniteDuration();
114}
115
116// TODO(user): Refactor this function with other versions living in
117// routing.cc.
118// TODO(user): Should we update solution limits as well?
119bool UpdateTimeLimits(Solver* solver, int64_t start_time_ms,
120 absl::Duration time_limit,
121 RoutingSearchParameters& search_parameters) {
122 if (!search_parameters.has_time_limit()) return true;
123 const absl::Duration elapsed_time =
124 absl::Milliseconds(solver->wall_time() - start_time_ms);
125 const absl::Duration time_left =
126 std::min(time_limit - elapsed_time, GetTimeLimit(search_parameters));
127 if (time_left <= absl::ZeroDuration()) return false;
128 const absl::Status status = util_time::EncodeGoogleApiProto(
129 time_left, search_parameters.mutable_time_limit());
130 DCHECK_OK(status);
131 return true;
132}
133} // namespace
134
136 RoutingModel* primary_model,
137 const std::vector<RoutingModel*>& alternative_models,
138 const RoutingSearchParameters& parameters,
139 int max_non_improving_iterations) {
141 /*assignment=*/nullptr, primary_model, alternative_models, parameters,
142 max_non_improving_iterations);
143}
144
146 const Assignment* assignment, RoutingModel* primary_model,
147 const std::vector<RoutingModel*>& alternative_models,
148 const RoutingSearchParameters& parameters,
149 int max_non_improving_iterations) {
151 assignment, primary_model, parameters, alternative_models, {},
152 max_non_improving_iterations);
153}
154
156 const Assignment* assignment, RoutingModel* primary_model,
157 const RoutingSearchParameters& primary_parameters,
158 const std::vector<RoutingModel*>& alternative_models,
159 const std::vector<RoutingSearchParameters>& alternative_parameters,
160 int max_non_improving_iterations) {
161 const int64_t start_time_ms = primary_model->solver()->wall_time();
162 if (max_non_improving_iterations < 0) return nullptr;
163 // Shortcut if no alternative models will be explored.
164 if (max_non_improving_iterations == 0 || alternative_models.empty()) {
165 return primary_model->SolveFromAssignmentWithParameters(assignment,
166 primary_parameters);
167 }
168 RoutingSearchParameters mutable_search_parameters = primary_parameters;
169 // The first alternating phases are limited to greedy descent. The final pass
170 // at the end of this function will actually use the metaheuristic if needed.
171 // TODO(user): Add support for multiple metaheuristics.
172 const LocalSearchMetaheuristic_Value metaheuristic =
173 mutable_search_parameters.local_search_metaheuristic();
174 const bool run_metaheuristic_phase =
177 if (run_metaheuristic_phase) {
178 mutable_search_parameters.set_local_search_metaheuristic(
180 }
181 std::vector<RoutingSearchParameters> mutable_alternative_parameters =
182 alternative_parameters;
183 DCHECK(mutable_alternative_parameters.empty() ||
184 mutable_alternative_parameters.size() == alternative_models.size());
185 for (RoutingSearchParameters& mutable_alternative_parameter :
186 mutable_alternative_parameters) {
187 if (!mutable_alternative_parameter.has_time_limit() &&
188 mutable_search_parameters.has_time_limit()) {
189 *mutable_alternative_parameter.mutable_time_limit() =
190 mutable_search_parameters.time_limit();
191 }
192 }
193 const absl::Duration time_limit = GetTimeLimit(mutable_search_parameters);
194 Assignment* best_assignment = primary_model->solver()->MakeAssignment();
195 std::vector<Assignment*> first_solutions;
196 first_solutions.reserve(alternative_models.size());
197 for (RoutingModel* model : alternative_models) {
198 first_solutions.push_back(model->solver()->MakeAssignment());
199 }
200 Assignment* primary_first_solution =
201 primary_model->solver()->MakeAssignment();
202 Assignment* current_solution = primary_model->solver()->MakeAssignment();
203 DCHECK(assignment == nullptr ||
204 assignment->solver() == primary_model->solver());
205 const Assignment* solution = primary_model->SolveFromAssignmentWithParameters(
206 assignment, mutable_search_parameters);
207 if (solution == nullptr) return nullptr;
208 best_assignment->Copy(solution);
209 int iteration = 0;
210 while (iteration < max_non_improving_iterations) {
211 if (best_assignment->ObjectiveValue() > solution->ObjectiveValue()) {
212 best_assignment->Copy(solution);
213 }
214 current_solution->Copy(solution);
215 for (int i = 0; i < alternative_models.size(); ++i) {
216 RoutingSearchParameters& mutable_alternative_parameter =
217 mutable_alternative_parameters.empty()
218 ? mutable_search_parameters
219 : mutable_alternative_parameters[i];
220 if (!UpdateTimeLimits(primary_model->solver(), start_time_ms, time_limit,
221 mutable_alternative_parameter)) {
222 return best_assignment;
223 }
224 ConvertAssignment(primary_model, solution, alternative_models[i],
225 first_solutions[i]);
226 solution = alternative_models[i]->SolveFromAssignmentWithParameters(
227 first_solutions[i], mutable_alternative_parameter);
228 if (solution == nullptr) {
229 solution = first_solutions[i];
230 }
231 if (!UpdateTimeLimits(primary_model->solver(), start_time_ms, time_limit,
232 mutable_search_parameters)) {
233 return best_assignment;
234 }
235 ConvertAssignment(alternative_models[i], solution, primary_model,
236 primary_first_solution);
237 solution = primary_model->SolveFromAssignmentWithParameters(
238 primary_first_solution, mutable_search_parameters);
239 if (solution == nullptr) return best_assignment;
240 }
241 // No modifications done in this iteration, no need to continue.
242 if (AreAssignmentsEquivalent(*primary_model, *solution,
243 *current_solution)) {
244 break;
245 }
246 // We're back to the best assignment which means we will cycle if we
247 // continue the search.
248 if (AreAssignmentsEquivalent(*primary_model, *solution, *best_assignment)) {
249 break;
250 }
251 if (solution->ObjectiveValue() >= best_assignment->ObjectiveValue()) {
252 ++iteration;
253 }
254 }
255 if (run_metaheuristic_phase &&
256 UpdateTimeLimits(primary_model->solver(), start_time_ms, time_limit,
257 mutable_search_parameters)) {
258 mutable_search_parameters.set_local_search_metaheuristic(metaheuristic);
259 return primary_model->SolveFromAssignmentWithParameters(
260 best_assignment, mutable_search_parameters);
261 }
262 return best_assignment;
263}
264
265// --- VehicleTypeCurator ---
266
267void VehicleTypeCurator::Reset(const std::function<bool(int)>& store_vehicle) {
268 const std::vector<std::set<VehicleClassEntry>>& all_vehicle_classes_per_type =
269 vehicle_type_container_->sorted_vehicle_classes_per_type;
270 sorted_vehicle_classes_per_type_.resize(all_vehicle_classes_per_type.size());
271 const std::vector<std::deque<int>>& all_vehicles_per_class =
272 vehicle_type_container_->vehicles_per_vehicle_class;
273 vehicles_per_vehicle_class_.resize(all_vehicles_per_class.size());
274
275 for (int type = 0; type < all_vehicle_classes_per_type.size(); type++) {
276 std::set<VehicleClassEntry>& stored_class_entries =
277 sorted_vehicle_classes_per_type_[type];
278 stored_class_entries.clear();
279 for (VehicleClassEntry class_entry : all_vehicle_classes_per_type[type]) {
280 const int vehicle_class = class_entry.vehicle_class;
281 std::vector<int>& stored_vehicles =
282 vehicles_per_vehicle_class_[vehicle_class];
283 stored_vehicles.clear();
284 for (int vehicle : all_vehicles_per_class[vehicle_class]) {
285 if (store_vehicle(vehicle)) {
286 stored_vehicles.push_back(vehicle);
287 }
288 }
289 if (!stored_vehicles.empty()) {
290 stored_class_entries.insert(class_entry);
291 }
292 }
293 }
294}
295
297 const std::function<bool(int)>& remove_vehicle) {
298 for (std::set<VehicleClassEntry>& class_entries :
299 sorted_vehicle_classes_per_type_) {
300 auto class_entry_it = class_entries.begin();
301 while (class_entry_it != class_entries.end()) {
302 const int vehicle_class = class_entry_it->vehicle_class;
303 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
304 vehicles.erase(std::remove_if(vehicles.begin(), vehicles.end(),
305 [&remove_vehicle](int vehicle) {
306 return remove_vehicle(vehicle);
307 }),
308 vehicles.end());
309 if (vehicles.empty()) {
310 class_entry_it = class_entries.erase(class_entry_it);
311 } else {
312 class_entry_it++;
313 }
314 }
315 }
316}
317
319 int type, const std::function<bool(int)>& vehicle_is_compatible) const {
320 for (const VehicleClassEntry& vehicle_class_entry :
321 sorted_vehicle_classes_per_type_[type]) {
322 for (int vehicle :
323 vehicles_per_vehicle_class_[vehicle_class_entry.vehicle_class]) {
324 if (vehicle_is_compatible(vehicle)) return true;
325 }
326 }
327 return false;
328}
329
331 int type, const std::function<bool(int)>& vehicle_is_compatible,
332 const std::function<bool(int)>& stop_and_return_vehicle) {
333 std::set<VehicleTypeCurator::VehicleClassEntry>& sorted_classes =
334 sorted_vehicle_classes_per_type_[type];
335 auto vehicle_class_it = sorted_classes.begin();
336
337 while (vehicle_class_it != sorted_classes.end()) {
338 const int vehicle_class = vehicle_class_it->vehicle_class;
339 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
340 DCHECK(!vehicles.empty());
341
342 for (auto vehicle_it = vehicles.begin(); vehicle_it != vehicles.end();
343 vehicle_it++) {
344 const int vehicle = *vehicle_it;
345 if (vehicle_is_compatible(vehicle)) {
346 vehicles.erase(vehicle_it);
347 if (vehicles.empty()) {
348 sorted_classes.erase(vehicle_class_it);
349 }
350 return {vehicle, -1};
351 }
352 if (stop_and_return_vehicle(vehicle)) {
353 return {-1, vehicle};
354 }
355 }
356 // If no compatible vehicle was found in this class, move on to the next
357 // vehicle class.
358 vehicle_class_it++;
359 }
360 // No compatible vehicle of the given type was found and the stopping
361 // condition wasn't met.
362 return {-1, -1};
363}
364
365// - Models with pickup/deliveries or node precedences are best handled by
366// PARALLEL_CHEAPEST_INSERTION.
367// - As of January 2018, models with single nodes and at least one node with
368// only one allowed vehicle are better solved by PATH_MOST_CONSTRAINED_ARC.
369// - In all other cases, PATH_CHEAPEST_ARC is used.
370// TODO(user): Make this smarter.
372 bool has_pickup_deliveries, bool has_node_precedences,
373 bool has_single_vehicle_node) {
374 if (has_pickup_deliveries || has_node_precedences) {
376 }
377 if (has_single_vehicle_node) {
379 }
381}
382
383std::vector<int64_t> ComputeVehicleEndChainStarts(const RoutingModel& model) {
384 const int64_t size = model.Size();
385 const int num_vehicles = model.vehicles();
386 // Find the chains of nodes (when nodes have their "Next" value bound in the
387 // current solution, it forms a link in a chain). Eventually, starts[end]
388 // will contain the index of the first node of the chain ending at node 'end'
389 // and ends[start] will be the last node of the chain starting at node
390 // 'start'. Values of starts[node] and ends[node] for other nodes is used
391 // for intermediary computations and do not necessarily reflect actual chain
392 // starts and ends.
393 std::vector<int64_t> starts(size + num_vehicles, -1);
394 std::vector<int64_t> ends(size + num_vehicles, -1);
395 for (int node = 0; node < size + num_vehicles; ++node) {
396 // Each node starts as a singleton chain.
397 starts[node] = node;
398 ends[node] = node;
399 }
400 std::vector<bool> touched(size, false);
401 for (int node = 0; node < size; ++node) {
402 int current = node;
403 while (!model.IsEnd(current) && !touched[current]) {
404 touched[current] = true;
405 IntVar* const next_var = model.NextVar(current);
406 if (next_var->Bound()) {
407 current = next_var->Value();
408 }
409 }
410 // Merge the sub-chain starting from 'node' and ending at 'current' with
411 // the existing sub-chain starting at 'current'.
412 starts[ends[current]] = starts[node];
413 ends[starts[node]] = ends[current];
414 }
415
416 // Set the 'end_chain_starts' for every vehicle.
417 std::vector<int64_t> end_chain_starts(num_vehicles);
418 for (int vehicle = 0; vehicle < num_vehicles; ++vehicle) {
419 end_chain_starts[vehicle] = starts[model.End(vehicle)];
420 }
421 return end_chain_starts;
422}
423
424// --- First solution decision builder ---
425
426// IntVarFilteredDecisionBuilder
427
429 std::unique_ptr<IntVarFilteredHeuristic> heuristic)
430 : heuristic_(std::move(heuristic)) {}
431
433 Assignment* const assignment = heuristic_->BuildSolution();
434 if (assignment != nullptr) {
435 VLOG(2) << "Number of decisions: " << heuristic_->number_of_decisions();
436 VLOG(2) << "Number of rejected decisions: "
437 << heuristic_->number_of_rejects();
438 assignment->Restore();
439 } else {
440 solver->Fail();
441 }
442 return nullptr;
443}
444
446 return heuristic_->number_of_decisions();
447}
448
450 return heuristic_->number_of_rejects();
451}
452
454 return absl::StrCat("IntVarFilteredDecisionBuilder(",
455 heuristic_->DebugString(), ")");
456}
457
458// --- First solution heuristics ---
459
460// IntVarFilteredHeuristic
461
463 Solver* solver, const std::vector<IntVar*>& vars,
464 const std::vector<IntVar*>& secondary_vars,
465 LocalSearchFilterManager* filter_manager)
466 : assignment_(solver->MakeAssignment()),
467 solver_(solver),
468 vars_(vars),
469 base_vars_size_(vars.size()),
470 delta_(solver->MakeAssignment()),
471 empty_(solver->MakeAssignment()),
472 filter_manager_(filter_manager),
473 objective_upper_bound_(std::numeric_limits<int64_t>::max()),
474 number_of_decisions_(0),
475 number_of_rejects_(0) {
476 if (!secondary_vars.empty()) {
477 vars_.insert(vars_.end(), secondary_vars.begin(), secondary_vars.end());
478 }
479 assignment_->MutableIntVarContainer()->Resize(vars_.size());
480 is_in_delta_.resize(vars_.size(), false);
481 delta_indices_.reserve(vars_.size());
482}
483
485 number_of_decisions_ = 0;
486 number_of_rejects_ = 0;
487 // Wiping assignment when starting a new search.
488 assignment_->MutableIntVarContainer()->Clear();
489 delta_->MutableIntVarContainer()->Clear();
491 assignment_->MutableIntVarContainer()->Resize(vars_.size());
492}
493
495 // Initialize must be called before the state of the heuristic is changed, in
496 // particular before InitializeSolution() and BuildSolutionInternal().
497 Initialize();
498 if (!InitializeSolution()) {
499 return nullptr;
500 }
501 if (BuildSolutionInternal()) {
502 return assignment_;
503 }
504 return nullptr;
505}
506
508 const std::function<int64_t(int64_t)>& next_accessor) {
509 // Initialize must be called before the state of the heuristic is changed, in
510 // particular before InitializeSolution() and BuildSolutionInternal().
511 Initialize();
512 // NOTE(b/219043402): The filter manager must first be synchronized with a
513 // valid solution that properly connects route starts to route ends in order
514 // for future FilterAccept() calls to correctly detect infeasibilities.
515 if (!InitializeSolution()) {
516 return nullptr;
517 }
518
519 for (int v = 0; v < model_->vehicles(); v++) {
520 int64_t node = model_->Start(v);
521 while (!model_->IsEnd(node)) {
522 const int64_t next = next_accessor(node);
523 DCHECK_NE(next, node);
524 SetNext(node, next, v);
525 SetVehicleIndex(node, v);
526 node = next;
527 }
528 }
529 if (!Evaluate(/*commit=*/true).has_value()) {
531 return nullptr;
532 }
533 if (BuildSolutionInternal()) {
534 return assignment_;
535 }
536 return nullptr;
537}
538
540 bool commit, bool ignore_upper_bound, bool update_upper_bound) {
541 ++number_of_decisions_;
542 const bool accept = FilterAccept(ignore_upper_bound);
543 int64_t objective_upper_bound = objective_upper_bound_;
544 if (accept) {
545 if (filter_manager_ != nullptr) {
546 // objective upper_bound_ is used to reduce the number of potential
547 // insertion candidates, specifically when filter_manager_ filters cost.
548 // Rationale: the best cost candidate will always be valid and will be
549 // inserted so no use accepting degrading ones. However when a candidate
550 // is committed, the upper bound is relaxed to make sure further
551 // (cost-degrading) insertions will be accepted
552 // (cf. SynchronizeFilters()).
553 DCHECK(ignore_upper_bound ||
554 filter_manager_->GetAcceptedObjectiveValue() <=
555 objective_upper_bound_);
556 objective_upper_bound = filter_manager_->GetAcceptedObjectiveValue();
557 if (update_upper_bound) {
558 objective_upper_bound_ = objective_upper_bound;
559 }
560 }
561 if (commit) {
562 const Assignment::IntContainer& delta_container =
563 delta_->IntVarContainer();
564 const int delta_size = delta_container.Size();
565 Assignment::IntContainer* const container =
566 assignment_->MutableIntVarContainer();
567 for (int i = 0; i < delta_size; ++i) {
568 const IntVarElement& delta_element = delta_container.Element(i);
569 IntVar* const var = delta_element.Var();
570 DCHECK_EQ(var, vars_[delta_indices_[i]]);
571 container->AddAtPosition(var, delta_indices_[i])
572 ->SetValue(delta_element.Value());
573 }
575 }
576 } else {
577 ++number_of_rejects_;
578 }
579 // Reset is_in_delta to all false.
580 for (const int delta_index : delta_indices_) {
581 is_in_delta_[delta_index] = false;
582 }
583 delta_->Clear();
584 delta_indices_.clear();
585 return accept ? std::optional<int64_t>{objective_upper_bound} : std::nullopt;
586}
587
589 if (filter_manager_) filter_manager_->Synchronize(assignment_, delta_);
590 // Resetting the upper bound to allow cost-increasing insertions.
591 objective_upper_bound_ = std::numeric_limits<int64_t>::max();
592}
593
594bool IntVarFilteredHeuristic::FilterAccept(bool ignore_upper_bound) {
595 if (!filter_manager_) return true;
596 LocalSearchMonitor* const monitor = solver_->GetLocalSearchMonitor();
597 return filter_manager_->Accept(
598 monitor, delta_, empty_, std::numeric_limits<int64_t>::min(),
599 ignore_upper_bound ? std::numeric_limits<int64_t>::max()
600 : objective_upper_bound_);
601}
602
603// RoutingFilteredHeuristic
604
606 RoutingModel* model, std::function<bool()> stop_search,
607 LocalSearchFilterManager* filter_manager)
608 : IntVarFilteredHeuristic(model->solver(), model->Nexts(),
609 model->CostsAreHomogeneousAcrossVehicles()
610 ? std::vector<IntVar*>()
611 : model->VehicleVars(),
612 filter_manager),
613 model_(model),
614 stop_search_(std::move(stop_search)) {}
615
619
620 // Start by adding partial start chains to current assignment.
621 start_chain_ends_.resize(model()->vehicles());
622 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
623 int64_t node = model()->Start(vehicle);
624 while (!model()->IsEnd(node) && Var(node)->Bound()) {
625 const int64_t next = Var(node)->Min();
626 SetNext(node, next, vehicle);
627 SetVehicleIndex(node, vehicle);
628 node = next;
629 }
630 start_chain_ends_[vehicle] = node;
631 }
632
633 end_chain_starts_ = ComputeVehicleEndChainStarts(*model_);
634
635 // Set each route to be the concatenation of the chain at its start and the
636 // chain at its end, without nodes in between.
637 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
638 int64_t node = start_chain_ends_[vehicle];
639 if (!model()->IsEnd(node)) {
640 int64_t next = end_chain_starts_[vehicle];
641 SetNext(node, next, vehicle);
642 SetVehicleIndex(node, vehicle);
643 node = next;
644 while (!model()->IsEnd(node)) {
645 next = Var(node)->Min();
646 SetNext(node, next, vehicle);
647 SetVehicleIndex(node, vehicle);
648 node = next;
649 }
650 }
651 }
652
653 if (!Evaluate(/*commit=*/true).has_value()) {
655 return false;
656 }
657 return true;
658}
659
661 model()->ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(
662 node, 1, [this, node](int alternate) {
663 if (node != alternate && !Contains(alternate)) {
664 SetNext(alternate, alternate, -1);
665 }
666 });
667}
668
670 // TODO(user): check that delta_ is empty.
672 absl::btree_set<std::pair<int64_t, int>> empty_vehicles;
673 for (int vehicle = 0; vehicle < model_->vehicles(); ++vehicle) {
674 if (VehicleIsEmpty(vehicle)) {
675 empty_vehicles.insert({model()->GetFixedCostOfVehicle(vehicle), vehicle});
676 }
677 }
678 for (int index = 0; index < model_->Size(); ++index) {
679 if (StopSearch() || empty_vehicles.empty()) return;
680 DCHECK(!IsSecondaryVar(index));
681 if (Contains(index)) continue;
682 for (auto [cost, vehicle] : empty_vehicles) {
683 SetNext(model_->Start(vehicle), index, vehicle);
684 SetNext(index, model_->End(vehicle), vehicle);
685 if (Evaluate(/*commit=*/true).has_value()) {
686 empty_vehicles.erase({cost, vehicle});
687 break;
688 }
689 }
690 }
691}
692
694 // TODO(user): check that delta_ is empty.
696 for (int index = 0; index < model_->Size(); ++index) {
697 DCHECK(!IsSecondaryVar(index));
698 if (!Contains(index)) {
699 SetNext(index, index, -1);
700 }
701 }
702 return true;
703}
704
706 const int num_nexts = model()->Nexts().size();
707 std::vector<bool> to_make_unperformed(num_nexts, false);
708 for (const auto& [pickups, deliveries] :
709 model()->GetPickupAndDeliveryPairs()) {
710 int64_t performed_pickup = -1;
711 for (int64_t pickup : pickups) {
712 if (Contains(pickup) && Value(pickup) != pickup) {
713 performed_pickup = pickup;
714 break;
715 }
716 }
717 int64_t performed_delivery = -1;
718 for (int64_t delivery : deliveries) {
719 if (Contains(delivery) && Value(delivery) != delivery) {
720 performed_delivery = delivery;
721 break;
722 }
723 }
724 if ((performed_pickup == -1) != (performed_delivery == -1)) {
725 if (performed_pickup != -1) {
726 to_make_unperformed[performed_pickup] = true;
727 }
728 if (performed_delivery != -1) {
729 to_make_unperformed[performed_delivery] = true;
730 }
731 }
732 }
733 for (int index = 0; index < num_nexts; ++index) {
734 if (to_make_unperformed[index] || !Contains(index)) continue;
735 const int vehicle =
737 int64_t next = Value(index);
738 while (next < num_nexts && to_make_unperformed[next]) {
739 const int64_t next_of_next = Value(next);
740 SetNext(index, next_of_next, vehicle);
741 SetNext(next, next, -1);
742 next = next_of_next;
743 }
744 }
745}
746
747// CheapestInsertionFilteredHeuristic
748
750 RoutingModel* model, std::function<bool()> stop_search,
751 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
752 std::function<int64_t(int64_t)> penalty_evaluator,
753 LocalSearchFilterManager* filter_manager)
754 : RoutingFilteredHeuristic(model, std::move(stop_search), filter_manager),
755 evaluator_(std::move(evaluator)),
756 evaluator_cache_(model->Nexts().size()),
757 penalty_evaluator_(std::move(penalty_evaluator)) {}
758
759namespace {
760void ProcessVehicleStartEndCosts(
761 const RoutingModel& model, int node,
762 const std::function<void(int64_t, int)>& process_cost,
763 const Bitset64<int>& vehicle_set, bool ignore_start = false,
764 bool ignore_end = false) {
765 const auto start_end_cost = [&model, ignore_start, ignore_end](int64_t node,
766 int v) {
767 const int64_t start_cost =
768 ignore_start ? 0 : model.GetArcCostForVehicle(model.Start(v), node, v);
769 const int64_t end_cost =
770 ignore_end ? 0 : model.GetArcCostForVehicle(model.End(v), node, v);
771 return CapAdd(start_cost, end_cost);
772 };
773
774 // Iterating over an IntVar domain is faster than calling Contains.
775 // Therefore we iterate on 'vehicles' only if it's smaller than the domain
776 // size of the VehicleVar.
777 const IntVar* const vehicle_var = model.VehicleVar(node);
778 if (vehicle_var->Size() < vehicle_set.size()) {
779 std::unique_ptr<IntVarIterator> it(vehicle_var->MakeDomainIterator(false));
780 for (const int v : InitAndGetValues(it.get())) {
781 if (v < 0 || !vehicle_set[v]) {
782 continue;
783 }
784 process_cost(start_end_cost(node, v), v);
785 }
786 } else {
787 for (const int v : vehicle_set) {
788 if (!vehicle_var->Contains(v)) continue;
789 process_cost(start_end_cost(node, v), v);
790 }
791 }
792}
793} // namespace
794
795std::vector<std::vector<CheapestInsertionFilteredHeuristic::StartEndValue>>
797 absl::Span<const int> vehicles) {
798 // TODO(user): consider checking search limits.
799 const RoutingModel& model = *this->model();
800 std::vector<std::vector<StartEndValue>> start_end_distances_per_node(
801 model.Size());
802
803 Bitset64<int> vehicle_set(model.vehicles());
804 for (int v : vehicles) vehicle_set.Set(v);
805
806 for (int node = 0; node < model.Size(); node++) {
807 if (Contains(node)) continue;
808 std::vector<StartEndValue>& start_end_distances =
809 start_end_distances_per_node[node];
810 start_end_distances.reserve(
811 std::min(model.VehicleVar(node)->Size(),
812 static_cast<uint64_t>(vehicles.size())));
813
814 ProcessVehicleStartEndCosts(
815 model, node,
816 [&start_end_distances](int64_t dist, int v) {
817 start_end_distances.push_back({dist, v});
818 },
819 vehicle_set);
820
821 // Sort the distances for the node to all start/ends of available vehicles
822 // in decreasing order.
823 absl::c_sort(start_end_distances,
824 [](const StartEndValue& first, const StartEndValue& second) {
825 return second < first;
826 });
827 }
828 return start_end_distances_per_node;
829}
830
832 int node, std::vector<StartEndValue>* start_end_distances, SeedQueue* sq) {
833 if (start_end_distances->empty()) {
834 return;
835 }
836
837 // Put the best StartEndValue for this node in the priority queue.
838 StartEndValue& start_end_value = start_end_distances->back();
840 start_end_value.distance = CapOpp(start_end_value.distance);
841 }
842 const int64_t num_allowed_vehicles = model()->VehicleVar(node)->Size();
843 const int64_t neg_penalty = CapOpp(model()->UnperformedPenalty(node));
844 sq->priority_queue.push({.properties = {num_allowed_vehicles, neg_penalty,
845 start_end_value.distance},
846 .vehicle = start_end_value.vehicle,
847 .is_node_index = true,
848 .index = node});
849 start_end_distances->pop_back();
850}
851
853 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
854 SeedQueue* sq) {
855 const int num_nodes = model()->Size();
856 DCHECK_EQ(start_end_distances_per_node->size(), num_nodes);
857
858 for (int node = 0; node < num_nodes; node++) {
859 if (Contains(node)) continue;
860 AddSeedNodeToQueue(node, &start_end_distances_per_node->at(node), sq);
861 }
862}
863
865 int64_t predecessor,
866 int64_t successor,
867 int vehicle) {
868 SetValue(predecessor, node);
869 SetValue(node, successor);
871 if (HasSecondaryVars() && vehicle != -1) {
872 SetValue(SecondaryVarIndex(predecessor), vehicle);
873 SetValue(SecondaryVarIndex(node), vehicle);
874 SetValue(SecondaryVarIndex(successor), vehicle);
875 }
876}
877
878int64_t
880 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
881 int vehicle) const {
882 DCHECK(evaluator_ != nullptr);
883 EvaluatorCache& cache_entry = evaluator_cache_[insert_after];
884 if (cache_entry.node != insert_before || cache_entry.vehicle != vehicle) {
885 cache_entry = {.value = evaluator_(insert_after, insert_before, vehicle),
886 .node = insert_before,
887 .vehicle = vehicle};
888 }
889 return CapSub(CapAdd(evaluator_(insert_after, node_to_insert, vehicle),
890 evaluator_(node_to_insert, insert_before, vehicle)),
891 cache_entry.value);
892}
893
894std::optional<int64_t>
896 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
897 int vehicle, int hint_weight) {
898 if (evaluator_ != nullptr) {
900 node_to_insert, insert_after, insert_before, vehicle);
901 }
902 InsertBetween(node_to_insert, insert_after, insert_before, vehicle);
903 return Evaluate(/*commit=*/false, /*ignore_upper_bound=*/hint_weight > 0,
904 /*update_upper_bound=*/hint_weight >= 0);
905}
906
907std::optional<int64_t>
909 int64_t pickup, int64_t pickup_insert_after, int64_t delivery,
910 int64_t delivery_insert_after, int vehicle, int hint_weight) {
911 DCHECK_GE(pickup_insert_after, 0);
912 const int64_t pickup_insert_before = Value(pickup_insert_after);
913 DCHECK_GE(delivery_insert_after, 0);
914 const int64_t delivery_insert_before = (delivery_insert_after == pickup)
915 ? pickup_insert_before
916 : Value(delivery_insert_after);
917 if (evaluator_ != nullptr) {
918 const int64_t pickup_cost = GetEvaluatorInsertionCostForNodeAtPosition(
919 pickup, pickup_insert_after, pickup_insert_before, vehicle);
920 const int64_t delivery_cost = GetEvaluatorInsertionCostForNodeAtPosition(
921 delivery, delivery_insert_after, delivery_insert_before, vehicle);
922 return CapAdd(pickup_cost, delivery_cost);
923 }
924
925 InsertBetween(pickup, pickup_insert_after, pickup_insert_before, vehicle);
926 InsertBetween(delivery, delivery_insert_after, delivery_insert_before,
927 vehicle);
928 return Evaluate(/*commit=*/false,
929 /*ignore_upper_bound=*/hint_weight > 0,
930 /*update_upper_bound=*/hint_weight >= 0);
931}
932
934 int64_t node_to_insert) const {
935 if (penalty_evaluator_ != nullptr) {
936 return penalty_evaluator_(node_to_insert);
937 }
938 return std::numeric_limits<int64_t>::max();
939}
940
941// GlobalCheapestInsertionFilteredHeuristic
942
945 RoutingModel* model, std::function<bool()> stop_search,
946 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
947 std::function<int64_t(int64_t)> penalty_evaluator,
948 LocalSearchFilterManager* filter_manager,
951 model, std::move(stop_search), std::move(evaluator),
952 std::move(penalty_evaluator), filter_manager),
953 gci_params_(parameters),
954 node_index_to_vehicle_(model->Size(), -1),
955 node_index_to_neighbors_by_cost_class_(nullptr),
956 empty_vehicle_type_curator_(nullptr) {
957 CHECK_GT(gci_params_.neighbors_ratio, 0);
958 CHECK_LE(gci_params_.neighbors_ratio, 1);
959 CHECK_GE(gci_params_.min_neighbors, 1);
960}
961
962bool GlobalCheapestInsertionFilteredHeuristic::CheckVehicleIndices() const {
963 std::vector<bool> node_is_visited(model()->Size(), false);
964 for (int v = 0; v < model()->vehicles(); v++) {
965 for (int node = model()->Start(v); !model()->IsEnd(node);
966 node = Value(node)) {
967 if (node_index_to_vehicle_[node] != v) {
968 return false;
969 }
970 node_is_visited[node] = true;
971 }
972 }
973
974 for (int node = 0; node < model()->Size(); node++) {
975 if (!node_is_visited[node] && node_index_to_vehicle_[node] != -1) {
976 return false;
977 }
978 }
979
980 return true;
981}
982
984 // Get neighbors.
985 double neighbors_ratio_used = 1;
986 node_index_to_neighbors_by_cost_class_ =
987 model()->GetOrCreateNodeNeighborsByCostClass(gci_params_.neighbors_ratio,
988 gci_params_.min_neighbors,
989 neighbors_ratio_used);
990 if (neighbors_ratio_used == 1) {
991 gci_params_.use_neighbors_ratio_for_initialization = false;
992 }
993
994 if (empty_vehicle_type_curator_ == nullptr) {
995 empty_vehicle_type_curator_ = std::make_unique<VehicleTypeCurator>(
996 model()->GetVehicleTypeContainer());
997 }
998 // Store all empty vehicles in the empty_vehicle_type_curator_.
999 empty_vehicle_type_curator_->Reset(
1000 [this](int vehicle) { return VehicleIsEmpty(vehicle); });
1001 // Insert partially inserted pairs.
1002 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
1003 model()->GetPickupAndDeliveryPairs();
1004 std::map<int64_t, std::vector<int>> pairs_to_insert_by_bucket;
1005 absl::flat_hash_map<int, std::map<int64_t, std::vector<int>>>
1006 vehicle_to_pair_nodes;
1007 for (int index = 0; index < pickup_delivery_pairs.size(); index++) {
1008 const PickupDeliveryPair& pickup_delivery_pair =
1009 pickup_delivery_pairs[index];
1010 const auto& [pickups, deliveries] = pickup_delivery_pair;
1011 int pickup_vehicle = -1;
1012 for (int64_t pickup : pickups) {
1013 if (Contains(pickup)) {
1014 pickup_vehicle = node_index_to_vehicle_[pickup];
1015 break;
1016 }
1017 }
1018 int delivery_vehicle = -1;
1019 for (int64_t delivery : deliveries) {
1020 if (Contains(delivery)) {
1021 delivery_vehicle = node_index_to_vehicle_[delivery];
1022 break;
1023 }
1024 }
1025 if (pickup_vehicle < 0 && delivery_vehicle < 0) {
1026 pairs_to_insert_by_bucket[GetBucketOfPair(pickup_delivery_pair)]
1027 .push_back(index);
1028 }
1029 if (pickup_vehicle >= 0 && delivery_vehicle < 0) {
1030 std::vector<int>& pair_nodes = vehicle_to_pair_nodes[pickup_vehicle][1];
1031 for (int64_t delivery : deliveries) {
1032 pair_nodes.push_back(delivery);
1033 }
1034 }
1035 if (pickup_vehicle < 0 && delivery_vehicle >= 0) {
1036 std::vector<int>& pair_nodes = vehicle_to_pair_nodes[delivery_vehicle][1];
1037 for (int64_t pickup : pickups) {
1038 pair_nodes.push_back(pickup);
1039 }
1040 }
1041 }
1042
1043 const auto unperform_unassigned_and_check = [this]() {
1045 Evaluate(/*commit=*/true).has_value();
1046 };
1047 for (const auto& [vehicle, nodes] : vehicle_to_pair_nodes) {
1048 if (!InsertNodesOnRoutes(nodes, {vehicle})) {
1049 return unperform_unassigned_and_check();
1050 }
1051 }
1052
1053 if (!InsertPairsAndNodesByRequirementTopologicalOrder()) {
1054 return unperform_unassigned_and_check();
1055 }
1056
1057 // TODO(user): Adapt the pair insertions to also support seed and
1058 // sequential insertion.
1059 if (!InsertPairs(pairs_to_insert_by_bucket)) {
1060 return unperform_unassigned_and_check();
1061 }
1062 std::map<int64_t, std::vector<int>> nodes_by_bucket;
1063 for (int node = 0; node < model()->Size(); ++node) {
1064 if (!Contains(node) && !model()->IsPickup(node) &&
1065 !model()->IsDelivery(node)) {
1066 nodes_by_bucket[GetBucketOfNode(node)].push_back(node);
1067 }
1068 }
1069 InsertFarthestNodesAsSeeds();
1070 if (gci_params_.is_sequential) {
1071 if (!SequentialInsertNodes(nodes_by_bucket)) {
1072 return unperform_unassigned_and_check();
1073 }
1074 } else if (!InsertNodesOnRoutes(nodes_by_bucket, {})) {
1075 return unperform_unassigned_and_check();
1076 }
1077 DCHECK(CheckVehicleIndices());
1078 return unperform_unassigned_and_check();
1079}
1080
1081bool GlobalCheapestInsertionFilteredHeuristic::
1082 InsertPairsAndNodesByRequirementTopologicalOrder() {
1083 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
1084 model()->GetPickupAndDeliveryPairs();
1085 for (const std::vector<int>& types :
1086 model()->GetTopologicallySortedVisitTypes()) {
1087 for (int type : types) {
1088 std::map<int64_t, std::vector<int>> pairs_to_insert_by_bucket;
1089 for (int index : model()->GetPairIndicesOfType(type)) {
1090 pairs_to_insert_by_bucket[GetBucketOfPair(pickup_delivery_pairs[index])]
1091 .push_back(index);
1092 }
1093 if (!InsertPairs(pairs_to_insert_by_bucket)) return false;
1094 std::map<int64_t, std::vector<int>> nodes_by_bucket;
1095 for (int node : model()->GetSingleNodesOfType(type)) {
1096 nodes_by_bucket[GetBucketOfNode(node)].push_back(node);
1097 }
1098 if (!InsertNodesOnRoutes(nodes_by_bucket, {})) return false;
1099 }
1100 }
1101 return true;
1102}
1103
1104bool GlobalCheapestInsertionFilteredHeuristic::InsertPairs(
1105 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket) {
1106 AdjustablePriorityQueue<PairEntry> priority_queue;
1107 std::vector<PairEntries> pickup_to_entries;
1108 std::vector<PairEntries> delivery_to_entries;
1109 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
1110 model()->GetPickupAndDeliveryPairs();
1111 auto pair_is_performed = [this, &pickup_delivery_pairs](int pair_index) {
1112 const auto& [pickups, deliveries] = pickup_delivery_pairs[pair_index];
1113 for (int64_t pickup : pickups) {
1114 if (Contains(pickup)) return true;
1115 }
1116 for (int64_t delivery : deliveries) {
1117 if (Contains(delivery)) return true;
1118 }
1119 return false;
1120 };
1121 absl::flat_hash_set<int> pair_indices_to_insert;
1122 for (const auto& [bucket, pair_indices] : pair_indices_by_bucket) {
1123 for (const int pair_index : pair_indices) {
1124 if (!pair_is_performed(pair_index)) {
1125 pair_indices_to_insert.insert(pair_index);
1126 }
1127 }
1128 if (!InitializePairPositions(pair_indices_to_insert, &priority_queue,
1129 &pickup_to_entries, &delivery_to_entries)) {
1130 return false;
1131 }
1132 while (!priority_queue.IsEmpty()) {
1133 if (StopSearchAndCleanup(&priority_queue)) {
1134 return false;
1135 }
1136 PairEntry* const entry = priority_queue.Top();
1137 const int64_t pickup = entry->pickup_to_insert();
1138 const int64_t delivery = entry->delivery_to_insert();
1139 if (Contains(pickup) || Contains(delivery)) {
1140 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1141 &delivery_to_entries);
1142 continue;
1143 }
1144
1145 const int entry_vehicle = entry->vehicle();
1146 if (entry_vehicle == -1) {
1147 // Pair is unperformed.
1148 SetNext(pickup, pickup, -1);
1149 SetNext(delivery, delivery, -1);
1150 if (!Evaluate(/*commit=*/true).has_value()) {
1151 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1152 &delivery_to_entries);
1153 }
1154 continue;
1155 }
1156
1157 // Pair is performed.
1158 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle)) {
1159 if (!InsertPairEntryUsingEmptyVehicleTypeCurator(
1160 pair_indices_to_insert, entry, &priority_queue,
1161 &pickup_to_entries, &delivery_to_entries)) {
1162 return false;
1163 }
1164 // The entry corresponded to an insertion on an empty vehicle, which was
1165 // handled by the call to InsertPairEntryUsingEmptyVehicleTypeCurator().
1166 continue;
1167 }
1168
1169 const int64_t pickup_insert_after = entry->pickup_insert_after();
1170 const int64_t pickup_insert_before = Value(pickup_insert_after);
1171 InsertBetween(pickup, pickup_insert_after, pickup_insert_before);
1172
1173 const int64_t delivery_insert_after = entry->delivery_insert_after();
1174 const int64_t delivery_insert_before = (delivery_insert_after == pickup)
1175 ? pickup_insert_before
1176 : Value(delivery_insert_after);
1177 InsertBetween(delivery, delivery_insert_after, delivery_insert_before);
1178 if (Evaluate(/*commit=*/true).has_value()) {
1179 if (!UpdateAfterPairInsertion(
1180 pair_indices_to_insert, entry_vehicle, pickup,
1181 pickup_insert_after, delivery, delivery_insert_after,
1182 &priority_queue, &pickup_to_entries, &delivery_to_entries)) {
1183 return false;
1184 }
1185 } else {
1186 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1187 &delivery_to_entries);
1188 }
1189 }
1190 // In case all pairs could not be inserted, pushing uninserted ones to the
1191 // next bucket.
1192 for (auto it = pair_indices_to_insert.begin(),
1193 last = pair_indices_to_insert.end();
1194 it != last;) {
1195 if (pair_is_performed(*it)) {
1196 pair_indices_to_insert.erase(it++);
1197 } else {
1198 ++it;
1199 }
1200 }
1201 }
1202 return true;
1203}
1204
1205bool GlobalCheapestInsertionFilteredHeuristic::
1206 InsertPairEntryUsingEmptyVehicleTypeCurator(
1207 const absl::flat_hash_set<int>& pair_indices,
1208 GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,
1209 AdjustablePriorityQueue<
1210 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
1211 priority_queue,
1212 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1213 pickup_to_entries,
1214 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1215 delivery_to_entries) {
1216 const int entry_vehicle = pair_entry->vehicle();
1217 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle));
1218
1219 // Trying to insert on an empty vehicle.
1220 // As we only have one pair_entry per empty vehicle type, we try inserting on
1221 // all vehicles of this type with the same fixed cost, as they all have the
1222 // same insertion value.
1223 const int64_t pickup = pair_entry->pickup_to_insert();
1224 const int64_t delivery = pair_entry->delivery_to_insert();
1225 const int64_t entry_fixed_cost =
1226 model()->GetFixedCostOfVehicle(entry_vehicle);
1227 auto vehicle_is_compatible = [this, entry_fixed_cost, pickup,
1228 delivery](int vehicle) {
1229 if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {
1230 return false;
1231 }
1232 // NOTE: Only empty vehicles should be in the vehicle_curator_.
1233 DCHECK(VehicleIsEmpty(vehicle));
1234 const int64_t end = model()->End(vehicle);
1235 InsertBetween(pickup, model()->Start(vehicle), end, vehicle);
1236 InsertBetween(delivery, pickup, end, vehicle);
1237 return Evaluate(/*commit=*/true).has_value();
1238 };
1239 // Since the vehicles of the same type are sorted by increasing fixed
1240 // cost by the curator, we can stop as soon as a vehicle with a fixed cost
1241 // higher than the entry_fixed_cost is found which is empty, and adapt the
1242 // pair entry with this new vehicle.
1243 auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {
1244 return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
1245 };
1246 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
1247 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
1248 empty_vehicle_type_curator_->Type(entry_vehicle),
1249 vehicle_is_compatible, stop_and_return_vehicle);
1250 if (compatible_vehicle >= 0) {
1251 // The pair was inserted on this vehicle.
1252 const int64_t vehicle_start = model()->Start(compatible_vehicle);
1253 const int num_previous_vehicle_entries =
1254 pickup_to_entries->at(vehicle_start).size() +
1255 delivery_to_entries->at(vehicle_start).size();
1256 if (!UpdateAfterPairInsertion(
1257 pair_indices, compatible_vehicle, pickup, vehicle_start, delivery,
1258 pickup, priority_queue, pickup_to_entries, delivery_to_entries)) {
1259 return false;
1260 }
1261 if (compatible_vehicle != entry_vehicle) {
1262 // The pair was inserted on another empty vehicle of the same type
1263 // and same fixed cost as entry_vehicle.
1264 // Since this vehicle is empty and has the same fixed cost as the
1265 // entry_vehicle, it shouldn't be the representative of empty vehicles
1266 // for any pickup/delivery in the priority queue.
1267 DCHECK(
1268 num_previous_vehicle_entries == 0 ||
1269 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=
1270 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());
1271 return true;
1272 }
1273 // The previously unused entry_vehicle is now used, so we use the next
1274 // available vehicle of the same type to compute and store insertions on
1275 // empty vehicles.
1276 const int new_empty_vehicle =
1277 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
1278 empty_vehicle_type_curator_->Type(compatible_vehicle));
1279
1280 if (new_empty_vehicle >= 0) {
1281 DCHECK(VehicleIsEmpty(new_empty_vehicle));
1282 // Add node entries after this vehicle start for uninserted pairs which
1283 // don't have entries on this empty vehicle.
1284 // Clearing all existing entries before adding updated ones. Some could
1285 // have been added when next_fixed_cost_empty_vehicle >= 0 (see the next
1286 // branch).
1287 const int64_t new_empty_vehicle_start = model()->Start(new_empty_vehicle);
1288 const std::vector<PairEntry*> to_remove(
1289 pickup_to_entries->at(new_empty_vehicle_start).begin(),
1290 pickup_to_entries->at(new_empty_vehicle_start).end());
1291 for (PairEntry* entry : to_remove) {
1292 DeletePairEntry(entry, priority_queue, pickup_to_entries,
1293 delivery_to_entries);
1294 }
1295 if (!AddPairEntriesWithPickupAfter(
1296 pair_indices, new_empty_vehicle, new_empty_vehicle_start,
1297 /*skip_entries_inserting_delivery_after=*/-1, priority_queue,
1298 pickup_to_entries, delivery_to_entries)) {
1299 return false;
1300 }
1301 }
1302 } else if (next_fixed_cost_empty_vehicle >= 0) {
1303 // Could not insert on this vehicle or any other vehicle of the same type
1304 // with the same fixed cost, but found an empty vehicle of this type with
1305 // higher fixed cost.
1306 DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));
1307 // Update the pair entry to correspond to an insertion on this
1308 // next_fixed_cost_empty_vehicle instead of the previous entry_vehicle.
1309 pair_entry->set_vehicle(next_fixed_cost_empty_vehicle);
1310 pickup_to_entries->at(pair_entry->pickup_insert_after()).erase(pair_entry);
1311 pair_entry->set_pickup_insert_after(
1312 model()->Start(next_fixed_cost_empty_vehicle));
1313 pickup_to_entries->at(pair_entry->pickup_insert_after()).insert(pair_entry);
1314 DCHECK_EQ(pair_entry->delivery_insert_after(), pickup);
1315 if (!UpdatePairEntry(pair_entry, priority_queue)) {
1316 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
1317 delivery_to_entries);
1318 }
1319 } else {
1320 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
1321 delivery_to_entries);
1322 }
1323
1324 return true;
1325}
1326
1328 public:
1329 struct Entry {
1330 bool operator<(const Entry& other) const {
1331 if (bucket != other.bucket) {
1332 return bucket < other.bucket;
1333 }
1334 if (value != other.value) {
1335 return value < other.value;
1336 }
1337 if ((vehicle == -1) ^ (other.vehicle == -1)) {
1338 return other.vehicle == -1;
1339 }
1340 return std::tie(insert_after, node_to_insert, vehicle) <
1341 std::tie(other.insert_after, other.node_to_insert, other.vehicle);
1342 }
1343 int64_t value;
1348 };
1349
1350 explicit NodeEntryQueue(int num_nodes)
1351 : entries_(num_nodes), touched_entries_(num_nodes) {}
1352 void Clear() {
1353 priority_queue_.Clear();
1354 for (Entries& entries : entries_) entries.Clear();
1355 touched_entries_.ResetAllToFalse();
1356 }
1357 bool IsEmpty() const {
1358 return priority_queue_.IsEmpty() &&
1359 touched_entries_.NumberOfSetCallsWithDifferentArguments() == 0;
1360 }
1361 bool IsEmpty(int64_t insert_after) const {
1362 return insert_after >= entries_.size() ||
1363 entries_[insert_after].entries.empty();
1364 }
1366 DCHECK(!IsEmpty());
1367 for (int touched : touched_entries_.PositionsSetAtLeastOnce()) {
1368 SortInsertions(&entries_[touched]);
1369 }
1370 touched_entries_.ResetAllToFalse();
1371 DCHECK(!priority_queue_.IsEmpty());
1372 Entries* entries = priority_queue_.Top();
1373 DCHECK(!entries->entries.empty());
1374 return entries->Top();
1375 }
1376 void Pop() {
1377 if (IsEmpty()) return;
1378 CHECK_EQ(touched_entries_.NumberOfSetCallsWithDifferentArguments(), 0);
1379 Entries* top = priority_queue_.Top();
1380 if (top->IncrementTop()) {
1381 priority_queue_.NoteChangedPriority(top);
1382 } else {
1383 priority_queue_.Remove(top);
1384 top->Clear();
1385 }
1386 }
1387 void ClearInsertions(int64_t insert_after) {
1388 if (IsEmpty(insert_after)) return;
1389 Entries& entries = entries_[insert_after];
1390 if (priority_queue_.Contains(&entries)) {
1391 priority_queue_.Remove(&entries);
1392 }
1393 entries.Clear();
1394 }
1395 void PushInsertion(int64_t node, int64_t insert_after, int vehicle,
1396 int bucket, int64_t value) {
1397 entries_[insert_after].entries.push_back(
1398 {value, node, insert_after, vehicle, bucket});
1399 touched_entries_.Set(insert_after);
1400 }
1401
1402 private:
1403 struct Entries {
1404 bool operator<(const Entries& other) const {
1405 DCHECK(!entries.empty());
1406 DCHECK(!other.entries.empty());
1407 return other.entries[other.top] < entries[top];
1408 }
1409 void Clear() {
1410 entries.clear();
1411 top = 0;
1412 heap_index = -1;
1413 }
1414 void SetHeapIndex(int index) { heap_index = index; }
1415 int GetHeapIndex() const { return heap_index; }
1416 bool IncrementTop() {
1417 ++top;
1418 return top < entries.size();
1419 }
1420 Entry* Top() { return &entries[top]; }
1421
1422 std::vector<Entry> entries;
1423 int top = 0;
1424 int heap_index = -1;
1425 };
1426
1427 void SortInsertions(Entries* entries) {
1428 entries->top = 0;
1429 if (entries->entries.empty()) return;
1430 absl::c_sort(entries->entries);
1431 if (!priority_queue_.Contains(entries)) {
1432 priority_queue_.Add(entries);
1433 } else {
1434 priority_queue_.NoteChangedPriority(entries);
1435 }
1436 }
1437
1438 AdjustablePriorityQueue<Entries> priority_queue_;
1439 std::vector<Entries> entries_;
1440 SparseBitset<int> touched_entries_;
1441};
1442
1443bool GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(
1444 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,
1445 const absl::flat_hash_set<int>& vehicles) {
1446 NodeEntryQueue queue(model()->Nexts().size());
1447 SparseBitset<int> nodes_to_insert(model()->Size());
1448 for (const auto& [bucket, nodes] : nodes_by_bucket) {
1449 for (int node : nodes) {
1450 nodes_to_insert.Set(node);
1451 }
1452 if (!InitializePositions(nodes_to_insert, vehicles, &queue)) {
1453 return false;
1454 }
1455 // The following boolean indicates whether or not all vehicles are being
1456 // considered for insertion of the nodes simultaneously.
1457 // In the sequential version of the heuristic, as well as when inserting
1458 // single pickup or deliveries from pickup/delivery pairs, this will be
1459 // false. In the general parallel version of the heuristic, all_vehicles is
1460 // true.
1461 const bool all_vehicles =
1462 vehicles.empty() || vehicles.size() == model()->vehicles();
1463
1464 while (!queue.IsEmpty()) {
1465 const NodeEntryQueue::Entry* node_entry = queue.Top();
1466 if (StopSearch()) return false;
1467 const int64_t node_to_insert = node_entry->node_to_insert;
1468 if (Contains(node_to_insert)) {
1469 queue.Pop();
1470 continue;
1471 }
1472
1473 const int entry_vehicle = node_entry->vehicle;
1474 if (entry_vehicle == -1) {
1475 DCHECK(all_vehicles);
1476 // Make node unperformed.
1477 SetNext(node_to_insert, node_to_insert, -1);
1478 if (!Evaluate(/*commit=*/true).has_value()) {
1479 queue.Pop();
1480 }
1481 continue;
1482 }
1483
1484 // Make node performed.
1485 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles)) {
1486 DCHECK(all_vehicles);
1487 if (!InsertNodeEntryUsingEmptyVehicleTypeCurator(
1488 nodes_to_insert, all_vehicles, &queue)) {
1489 return false;
1490 }
1491 continue;
1492 }
1493
1494 const int64_t insert_after = node_entry->insert_after;
1495 InsertBetween(node_to_insert, insert_after, Value(insert_after));
1496 if (Evaluate(/*commit=*/true).has_value()) {
1497 if (!UpdateAfterNodeInsertion(nodes_to_insert, entry_vehicle,
1498 node_to_insert, insert_after,
1499 all_vehicles, &queue)) {
1500 return false;
1501 }
1502 } else {
1503 queue.Pop();
1504 }
1505 }
1506 // In case all nodes could not be inserted, pushing uninserted ones to the
1507 // next bucket.
1508 std::vector<int> non_inserted_nodes;
1509 non_inserted_nodes.reserve(
1510 nodes_to_insert.NumberOfSetCallsWithDifferentArguments());
1511 for (int node : nodes_to_insert.PositionsSetAtLeastOnce()) {
1512 if (!Contains(node)) non_inserted_nodes.push_back(node);
1513 }
1514 nodes_to_insert.ResetAllToFalse();
1515 for (int node : non_inserted_nodes) {
1516 nodes_to_insert.Set(node);
1517 }
1518 }
1519 return true;
1520}
1521
1522bool GlobalCheapestInsertionFilteredHeuristic::
1523 InsertNodeEntryUsingEmptyVehicleTypeCurator(const SparseBitset<int>& nodes,
1524 bool all_vehicles,
1525 NodeEntryQueue* queue) {
1526 const NodeEntryQueue::Entry* node_entry = queue->Top();
1527 const int entry_vehicle = node_entry->vehicle;
1528 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles));
1529 DCHECK(evaluator_ != nullptr);
1530
1531 // Trying to insert on an empty vehicle, and all vehicles are being
1532 // considered simultaneously.
1533 // As we only have one node_entry per type, we try inserting on all vehicles
1534 // of this type with the same fixed cost as they all have the same insertion
1535 // value.
1536 const int64_t node_to_insert = node_entry->node_to_insert;
1537 const int bucket = node_entry->bucket;
1538 const int64_t entry_fixed_cost =
1539 model()->GetFixedCostOfVehicle(entry_vehicle);
1540 auto vehicle_is_compatible = [this, entry_fixed_cost,
1541 node_to_insert](int vehicle) {
1542 if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {
1543 return false;
1544 }
1545 // NOTE: Only empty vehicles should be in the vehicle_curator_.
1546 DCHECK(VehicleIsEmpty(vehicle));
1547 InsertBetween(node_to_insert, model()->Start(vehicle),
1548 model()->End(vehicle), vehicle);
1549 return Evaluate(/*commit=*/true).has_value();
1550 };
1551 // Since the vehicles of the same type are sorted by increasing fixed
1552 // cost by the curator, we can stop as soon as an empty vehicle with a fixed
1553 // cost higher than the entry_fixed_cost is found, and add new entries for
1554 // this new vehicle.
1555 auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {
1556 return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
1557 };
1558 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =
1559 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(
1560 empty_vehicle_type_curator_->Type(entry_vehicle),
1561 vehicle_is_compatible, stop_and_return_vehicle);
1562 if (compatible_vehicle >= 0) {
1563 // The node was inserted on this vehicle.
1564 const int64_t compatible_start = model()->Start(compatible_vehicle);
1565 const bool no_prior_entries_for_this_vehicle =
1566 queue->IsEmpty(compatible_start);
1567 if (!UpdateAfterNodeInsertion(nodes, compatible_vehicle, node_to_insert,
1568 compatible_start, all_vehicles, queue)) {
1569 return false;
1570 }
1571 if (compatible_vehicle != entry_vehicle) {
1572 // The node was inserted on another empty vehicle of the same type
1573 // and same fixed cost as entry_vehicle.
1574 // Since this vehicle is empty and has the same fixed cost as the
1575 // entry_vehicle, it shouldn't be the representative of empty vehicles
1576 // for any node in the priority queue.
1577 DCHECK(
1578 no_prior_entries_for_this_vehicle ||
1579 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=
1580 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());
1581 return true;
1582 }
1583 // The previously unused entry_vehicle is now used, so we use the next
1584 // available vehicle of the same type to compute and store insertions on
1585 // empty vehicles.
1586 const int new_empty_vehicle =
1587 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
1588 empty_vehicle_type_curator_->Type(compatible_vehicle));
1589
1590 if (new_empty_vehicle >= 0) {
1591 DCHECK(VehicleIsEmpty(new_empty_vehicle));
1592 // Add node entries after this vehicle start for uninserted nodes which
1593 // don't have entries on this empty vehicle.
1594 // Clearing all existing entries before adding updated ones. Some could
1595 // have been added when next_fixed_cost_empty_vehicle >= 0 (see the next
1596 // branch).
1597 const int64_t new_empty_vehicle_start = model()->Start(new_empty_vehicle);
1598 queue->ClearInsertions(new_empty_vehicle_start);
1599 if (!AddNodeEntriesAfter(nodes, new_empty_vehicle,
1600 new_empty_vehicle_start, all_vehicles, queue)) {
1601 return false;
1602 }
1603 }
1604 } else if (next_fixed_cost_empty_vehicle >= 0) {
1605 // Could not insert on this vehicle or any other vehicle of the same
1606 // type with the same fixed cost, but found an empty vehicle of this type
1607 // with higher fixed cost.
1608 DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));
1609 // Update the insertion entry to be on next_empty_vehicle instead of the
1610 // previous entry_vehicle.
1611 queue->Pop();
1612 const int64_t insert_after = model()->Start(next_fixed_cost_empty_vehicle);
1613 const int64_t insertion_cost = GetEvaluatorInsertionCostForNodeAtPosition(
1614 node_to_insert, insert_after, Value(insert_after),
1615 next_fixed_cost_empty_vehicle);
1616 const int64_t penalty_shift =
1617 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
1618 ? GetUnperformedValue(node_to_insert)
1619 : 0;
1620 queue->PushInsertion(node_to_insert, insert_after,
1621 next_fixed_cost_empty_vehicle, bucket,
1622 CapSub(insertion_cost, penalty_shift));
1623 } else {
1624 queue->Pop();
1625 }
1626
1627 return true;
1628}
1629
1630bool GlobalCheapestInsertionFilteredHeuristic::SequentialInsertNodes(
1631 const std::map<int64_t, std::vector<int>>& nodes_by_bucket) {
1632 std::vector<bool> is_vehicle_used;
1633 absl::flat_hash_set<int> used_vehicles;
1634 std::vector<int> unused_vehicles;
1635
1636 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
1637 if (!used_vehicles.empty() &&
1638 !InsertNodesOnRoutes(nodes_by_bucket, used_vehicles)) {
1639 return false;
1640 }
1641
1642 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
1643 ComputeStartEndDistanceForVehicles(unused_vehicles);
1644 SeedQueue first_node_queue(/*prioritize_farthest_nodes=*/false);
1645 InitializeSeedQueue(&start_end_distances_per_node, &first_node_queue);
1646
1647 int vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
1648 &is_vehicle_used);
1649
1650 while (vehicle >= 0) {
1651 if (!InsertNodesOnRoutes(nodes_by_bucket, {vehicle})) {
1652 return false;
1653 }
1654 vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
1655 &is_vehicle_used);
1656 }
1657 return true;
1658}
1659
1660void GlobalCheapestInsertionFilteredHeuristic::DetectUsedVehicles(
1661 std::vector<bool>* is_vehicle_used, std::vector<int>* unused_vehicles,
1662 absl::flat_hash_set<int>* used_vehicles) {
1663 is_vehicle_used->clear();
1664 is_vehicle_used->resize(model()->vehicles());
1665
1666 used_vehicles->clear();
1667 used_vehicles->reserve(model()->vehicles());
1668
1669 unused_vehicles->clear();
1670 unused_vehicles->reserve(model()->vehicles());
1671
1672 for (int vehicle = 0; vehicle < model()->vehicles(); vehicle++) {
1673 if (!VehicleIsEmpty(vehicle)) {
1674 (*is_vehicle_used)[vehicle] = true;
1675 used_vehicles->insert(vehicle);
1676 } else {
1677 (*is_vehicle_used)[vehicle] = false;
1678 unused_vehicles->push_back(vehicle);
1679 }
1680 }
1681}
1682
1683bool GlobalCheapestInsertionFilteredHeuristic::IsCheapestClassRepresentative(
1684 int vehicle) const {
1685 if (evaluator_ == nullptr) {
1686 // When no evaluator_ is given, filters are used to evaluate the cost and
1687 // feasibility of inserting on each vehicle, so we don't use only one
1688 // class representative for each class.
1689 return true;
1690 }
1691 if (!VehicleIsEmpty(vehicle)) return true;
1692 // We only consider the least expensive empty vehicle of each type for
1693 // entries of the same vehicle class.
1694 const int curator_vehicle =
1695 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
1696 empty_vehicle_type_curator_->Type(vehicle));
1697 return curator_vehicle == vehicle ||
1698 model()->GetVehicleClassIndexOfVehicle(curator_vehicle).value() !=
1699 model()->GetVehicleClassIndexOfVehicle(vehicle).value();
1700}
1701
1702void GlobalCheapestInsertionFilteredHeuristic::InsertFarthestNodesAsSeeds() {
1703 // TODO(user): consider checking search limits.
1704 if (gci_params_.farthest_seeds_ratio <= 0) return;
1705 // Insert at least 1 farthest Seed if the parameter is positive.
1706 const int num_seeds = static_cast<int>(
1707 std::ceil(gci_params_.farthest_seeds_ratio * model()->vehicles()));
1708
1709 std::vector<bool> is_vehicle_used;
1710 absl::flat_hash_set<int> used_vehicles;
1711 std::vector<int> unused_vehicles;
1712 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
1713 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
1714 ComputeStartEndDistanceForVehicles(unused_vehicles);
1715
1716 // Priority queue where the Seeds with a larger distance are given higher
1717 // priority.
1718 SeedQueue farthest_node_queue(/*prioritize_farthest_nodes=*/true);
1719 InitializeSeedQueue(&start_end_distances_per_node, &farthest_node_queue);
1720
1721 int inserted_seeds = 0;
1722 while (inserted_seeds++ < num_seeds) {
1723 if (InsertSeedNode(&start_end_distances_per_node, &farthest_node_queue,
1724 &is_vehicle_used) < 0) {
1725 break;
1726 }
1727 }
1728
1729 // NOTE: As we don't use the empty_vehicle_type_curator_ when inserting seed
1730 // nodes on routes, some previously empty vehicles may now be used, so we
1731 // update the curator accordingly to ensure it still only stores empty
1732 // vehicles.
1733 DCHECK(empty_vehicle_type_curator_ != nullptr);
1734 empty_vehicle_type_curator_->Update(
1735 [this](int vehicle) { return !VehicleIsEmpty(vehicle); });
1736}
1737
1738int GlobalCheapestInsertionFilteredHeuristic::InsertSeedNode(
1739 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
1740 SeedQueue* sq, std::vector<bool>* is_vehicle_used) {
1741 auto& priority_queue = sq->priority_queue;
1742 while (!priority_queue.empty()) {
1743 if (StopSearch()) return -1;
1744 const Seed& seed = priority_queue.top();
1745 const int seed_node = seed.index;
1746 DCHECK(seed.is_node_index);
1747 const int seed_vehicle = seed.vehicle;
1748 priority_queue.pop();
1749
1750 std::vector<StartEndValue>& other_start_end_values =
1751 (*start_end_distances_per_node)[seed_node];
1752
1753 if (Contains(seed_node)) {
1754 // The node is already inserted, it is therefore no longer considered as
1755 // a potential seed.
1756 other_start_end_values.clear();
1757 continue;
1758 }
1759 if (!(*is_vehicle_used)[seed_vehicle]) {
1760 // Try to insert this seed_node on this vehicle's route.
1761 const int64_t start = model()->Start(seed_vehicle);
1762 const int64_t end = model()->End(seed_vehicle);
1763 DCHECK_EQ(Value(start), end);
1764 InsertBetween(seed_node, start, end, seed_vehicle);
1765 if (Evaluate(/*commit=*/true).has_value()) {
1766 (*is_vehicle_used)[seed_vehicle] = true;
1767 other_start_end_values.clear();
1768 SetVehicleIndex(seed_node, seed_vehicle);
1769 return seed_vehicle;
1770 }
1771 }
1772 // Either the vehicle is already used, or the Commit() wasn't successful.
1773 // In both cases, we insert the next StartEndValue from
1774 // start_end_distances_per_node[seed_node] in the priority queue.
1775 AddSeedNodeToQueue(seed_node, &other_start_end_values, sq);
1776 }
1777 // No seed node was inserted.
1778 return -1;
1779}
1780
1781bool GlobalCheapestInsertionFilteredHeuristic::InitializePairPositions(
1782 const absl::flat_hash_set<int>& pair_indices,
1783 AdjustablePriorityQueue<
1784 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
1785 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1786 pickup_to_entries,
1787 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1788 delivery_to_entries) {
1789 priority_queue->Clear();
1790 pickup_to_entries->clear();
1791 pickup_to_entries->resize(model()->Size());
1792 delivery_to_entries->clear();
1793 delivery_to_entries->resize(model()->Size());
1794 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
1795 model()->GetPickupAndDeliveryPairs();
1796 for (int index : pair_indices) {
1797 const auto& [pickups, deliveries] = pickup_delivery_pairs[index];
1798 for (int64_t pickup : pickups) {
1799 if (Contains(pickup)) continue;
1800 for (int64_t delivery : deliveries) {
1801 if (Contains(delivery)) continue;
1802 if (StopSearchAndCleanup(priority_queue)) return false;
1803 // Add insertion entry making pair unperformed. When the pair is part
1804 // of a disjunction we do not try to make any of its pairs unperformed
1805 // as it requires having an entry with all pairs being unperformed.
1806 // TODO(user): Adapt the code to make pair disjunctions unperformed.
1807 if (gci_params_.add_unperformed_entries && pickups.size() == 1 &&
1808 deliveries.size() == 1 &&
1809 GetUnperformedValue(pickup) !=
1810 std::numeric_limits<int64_t>::max() &&
1811 GetUnperformedValue(delivery) !=
1812 std::numeric_limits<int64_t>::max()) {
1813 AddPairEntry(pickup, -1, delivery, -1, -1, priority_queue, nullptr,
1814 nullptr);
1815 }
1816 // Add all other insertion entries with pair performed.
1817 InitializeInsertionEntriesPerformingPair(
1818 pickup, delivery, priority_queue, pickup_to_entries,
1819 delivery_to_entries);
1820 }
1821 }
1822 }
1823 return true;
1824}
1825
1826void GlobalCheapestInsertionFilteredHeuristic::
1827 InitializeInsertionEntriesPerformingPair(
1828 int64_t pickup, int64_t delivery,
1829 AdjustablePriorityQueue<
1830 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
1831 priority_queue,
1832 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1833 pickup_to_entries,
1834 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1835 delivery_to_entries) {
1836 if (!gci_params_.use_neighbors_ratio_for_initialization) {
1837 std::unique_ptr<IntVarIterator> vehicle_it(
1838 model()->VehicleVar(pickup)->MakeDomainIterator(false));
1839 for (const int vehicle : InitAndGetValues(vehicle_it.get())) {
1840 if (vehicle < 0 || !model()->VehicleVar(delivery)->Contains(vehicle)) {
1841 continue;
1842 }
1843 if (!IsCheapestClassRepresentative(vehicle)) continue;
1844
1845 int64_t pickup_insert_after = model()->Start(vehicle);
1846 while (!model()->IsEnd(pickup_insert_after)) {
1847 int64_t delivery_insert_after = pickup;
1848 while (!model()->IsEnd(delivery_insert_after)) {
1849 AddPairEntry(pickup, pickup_insert_after, delivery,
1850 delivery_insert_after, vehicle, priority_queue,
1851 pickup_to_entries, delivery_to_entries);
1852 delivery_insert_after = (delivery_insert_after == pickup)
1853 ? Value(pickup_insert_after)
1854 : Value(delivery_insert_after);
1855 }
1856 pickup_insert_after = Value(pickup_insert_after);
1857 }
1858 }
1859 return;
1860 }
1861
1862 // We're only considering the closest neighbors as insertion positions for
1863 // the pickup/delivery pair.
1864 for (int cost_class = 0; cost_class < model()->GetCostClassesCount();
1865 cost_class++) {
1866 absl::flat_hash_set<std::pair<int64_t, int64_t>>
1867 existing_insertion_positions;
1868 // Explore the neighborhood of the pickup.
1869 for (const int64_t pickup_insert_after :
1870 node_index_to_neighbors_by_cost_class_
1871 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, pickup)) {
1872 if (!Contains(pickup_insert_after)) {
1873 continue;
1874 }
1875 const int vehicle = node_index_to_vehicle_[pickup_insert_after];
1876 if (vehicle < 0 ||
1877 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
1878 continue;
1879 }
1880
1881 if (!IsCheapestClassRepresentative(vehicle)) continue;
1882
1883 if (!model()->VehicleVar(pickup)->Contains(vehicle) ||
1884 !model()->VehicleVar(delivery)->Contains(vehicle)) {
1885 continue;
1886 }
1887 int64_t delivery_insert_after = pickup;
1888 while (!model()->IsEnd(delivery_insert_after)) {
1889 const std::pair<int64_t, int64_t> insertion_position = {
1890 pickup_insert_after, delivery_insert_after};
1891 DCHECK(!existing_insertion_positions.contains(insertion_position));
1892 existing_insertion_positions.insert(insertion_position);
1893
1894 AddPairEntry(pickup, pickup_insert_after, delivery,
1895 delivery_insert_after, vehicle, priority_queue,
1896 pickup_to_entries, delivery_to_entries);
1897 delivery_insert_after = (delivery_insert_after == pickup)
1898 ? Value(pickup_insert_after)
1899 : Value(delivery_insert_after);
1900 }
1901 }
1902
1903 // Explore the neighborhood of the delivery.
1904 for (const int64_t delivery_insert_after :
1905 node_index_to_neighbors_by_cost_class_
1906 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, delivery)) {
1907 if (!Contains(delivery_insert_after)) {
1908 continue;
1909 }
1910 const int vehicle = node_index_to_vehicle_[delivery_insert_after];
1911 if (vehicle < 0 ||
1912 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
1913 continue;
1914 }
1915 if (!model()->VehicleVar(pickup)->Contains(vehicle) ||
1916 !model()->VehicleVar(delivery)->Contains(vehicle)) {
1917 continue;
1918 }
1919
1920 DCHECK(!VehicleIsEmpty(vehicle) ||
1921 delivery_insert_after == model()->Start(vehicle));
1922
1923 int64_t pickup_insert_after = model()->Start(vehicle);
1924 while (pickup_insert_after != delivery_insert_after) {
1925 if (!existing_insertion_positions.contains(
1926 std::make_pair(pickup_insert_after, delivery_insert_after))) {
1927 AddPairEntry(pickup, pickup_insert_after, delivery,
1928 delivery_insert_after, vehicle, priority_queue,
1929 pickup_to_entries, delivery_to_entries);
1930 }
1931 pickup_insert_after = Value(pickup_insert_after);
1932 }
1933 }
1934 }
1935}
1936
1937bool GlobalCheapestInsertionFilteredHeuristic::UpdateAfterPairInsertion(
1938 const absl::flat_hash_set<int>& pair_indices, int vehicle, int64_t pickup,
1939 int64_t pickup_position, int64_t delivery, int64_t delivery_position,
1940 AdjustablePriorityQueue<PairEntry>* priority_queue,
1941 std::vector<PairEntries>* pickup_to_entries,
1942 std::vector<PairEntries>* delivery_to_entries) {
1943 // Clearing any entries created after the pickup; these entries are the ones
1944 // where the delivery is to be inserted immediately after the pickup.
1945 const std::vector<PairEntry*> to_remove(
1946 delivery_to_entries->at(pickup).begin(),
1947 delivery_to_entries->at(pickup).end());
1948 for (PairEntry* pair_entry : to_remove) {
1949 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
1950 delivery_to_entries);
1951 }
1952 DCHECK(pickup_to_entries->at(pickup).empty());
1953 DCHECK(pickup_to_entries->at(delivery).empty());
1954 DCHECK(delivery_to_entries->at(pickup).empty());
1955 DCHECK(delivery_to_entries->at(delivery).empty());
1956 // Update cost of existing entries after nodes which have new nexts
1957 // (pickup_position and delivery_position).
1958 if (!UpdateExistingPairEntriesOnChain(pickup_position, Value(pickup_position),
1959 priority_queue, pickup_to_entries,
1960 delivery_to_entries) ||
1961 !UpdateExistingPairEntriesOnChain(
1962 delivery_position, Value(delivery_position), priority_queue,
1963 pickup_to_entries, delivery_to_entries)) {
1964 return false;
1965 }
1966 // Add new entries after nodes which have been inserted (pickup and delivery).
1967 // We skip inserting deliveries after 'delivery' in the first call to make
1968 // sure each pair is only inserted after ('pickup', 'delivery') once.
1969 if (!AddPairEntriesAfter(pair_indices, vehicle, pickup,
1970 /*skip_entries_inserting_delivery_after=*/delivery,
1971 priority_queue, pickup_to_entries,
1972 delivery_to_entries) ||
1973 !AddPairEntriesAfter(pair_indices, vehicle, delivery,
1974 /*skip_entries_inserting_delivery_after=*/-1,
1975 priority_queue, pickup_to_entries,
1976 delivery_to_entries)) {
1977 return false;
1978 }
1979 SetVehicleIndex(pickup, vehicle);
1980 SetVehicleIndex(delivery, vehicle);
1981 return true;
1982}
1983
1984bool GlobalCheapestInsertionFilteredHeuristic::UpdateExistingPairEntriesOnChain(
1985 int64_t insert_after_start, int64_t insert_after_end,
1986 AdjustablePriorityQueue<
1987 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
1988 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1989 pickup_to_entries,
1990 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1991 delivery_to_entries) {
1992 int64_t insert_after = insert_after_start;
1993 while (insert_after != insert_after_end) {
1994 DCHECK(!model()->IsEnd(insert_after));
1995 // Remove entries at 'insert_after' with nodes which have already been
1996 // inserted and update remaining entries.
1997 std::vector<PairEntry*> to_remove;
1998 for (const PairEntries* pair_entries :
1999 {&pickup_to_entries->at(insert_after),
2000 &delivery_to_entries->at(insert_after)}) {
2001 if (StopSearchAndCleanup(priority_queue)) return false;
2002 for (PairEntry* const pair_entry : *pair_entries) {
2003 DCHECK(priority_queue->Contains(pair_entry));
2004 if (Contains(pair_entry->pickup_to_insert()) ||
2005 Contains(pair_entry->delivery_to_insert())) {
2006 to_remove.push_back(pair_entry);
2007 } else {
2008 DCHECK(pickup_to_entries->at(pair_entry->pickup_insert_after())
2009 .contains(pair_entry));
2010 DCHECK(delivery_to_entries->at(pair_entry->delivery_insert_after())
2011 .contains(pair_entry));
2012 if (!UpdatePairEntry(pair_entry, priority_queue)) {
2013 to_remove.push_back(pair_entry);
2014 }
2015 }
2016 }
2017 }
2018 for (PairEntry* const pair_entry : to_remove) {
2019 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
2020 delivery_to_entries);
2021 }
2022 insert_after = Value(insert_after);
2023 }
2024 return true;
2025}
2026
2027bool GlobalCheapestInsertionFilteredHeuristic::AddPairEntriesWithPickupAfter(
2028 const absl::flat_hash_set<int>& pair_indices, int vehicle,
2029 int64_t insert_after, int64_t skip_entries_inserting_delivery_after,
2030 AdjustablePriorityQueue<
2031 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
2032 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2033 pickup_to_entries,
2034 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2035 delivery_to_entries) {
2036 const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
2037 const int64_t pickup_insert_before = Value(insert_after);
2038 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
2039 model()->GetPickupAndDeliveryPairs();
2040 DCHECK(pickup_to_entries->at(insert_after).empty());
2041 for (const int64_t pickup :
2042 node_index_to_neighbors_by_cost_class_
2043 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class, insert_after)) {
2044 if (StopSearchAndCleanup(priority_queue)) return false;
2045 if (Contains(pickup) || !model()->VehicleVar(pickup)->Contains(vehicle)) {
2046 continue;
2047 }
2048 if (const std::optional<RoutingModel::PickupDeliveryPosition> pickup_pos =
2049 model()->GetPickupPosition(pickup);
2050 pickup_pos.has_value()) {
2051 const int pair_index = pickup_pos->pd_pair_index;
2052 if (!pair_indices.contains(pair_index)) continue;
2053 for (const int64_t delivery :
2054 pickup_delivery_pairs[pair_index].delivery_alternatives) {
2055 if (Contains(delivery) ||
2056 !model()->VehicleVar(delivery)->Contains(vehicle)) {
2057 continue;
2058 }
2059 int64_t delivery_insert_after = pickup;
2060 while (!model()->IsEnd(delivery_insert_after)) {
2061 if (delivery_insert_after != skip_entries_inserting_delivery_after) {
2062 AddPairEntry(pickup, insert_after, delivery, delivery_insert_after,
2063 vehicle, priority_queue, pickup_to_entries,
2064 delivery_to_entries);
2065 }
2066 if (delivery_insert_after == pickup) {
2067 delivery_insert_after = pickup_insert_before;
2068 } else {
2069 delivery_insert_after = Value(delivery_insert_after);
2070 }
2071 }
2072 }
2073 }
2074 }
2075 return true;
2076}
2077
2078bool GlobalCheapestInsertionFilteredHeuristic::AddPairEntriesWithDeliveryAfter(
2079 const absl::flat_hash_set<int>& pair_indices, int vehicle,
2080 int64_t insert_after,
2081 AdjustablePriorityQueue<
2082 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
2083 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2084 pickup_to_entries,
2085 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2086 delivery_to_entries) {
2087 const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
2088 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =
2089 model()->GetPickupAndDeliveryPairs();
2090 for (const int64_t delivery :
2091 node_index_to_neighbors_by_cost_class_
2092 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class, insert_after)) {
2093 if (StopSearchAndCleanup(priority_queue)) return false;
2094 if (Contains(delivery) ||
2095 !model()->VehicleVar(delivery)->Contains(vehicle)) {
2096 continue;
2097 }
2098 if (const std::optional<RoutingModel::PickupDeliveryPosition> delivery_pos =
2099 model()->GetDeliveryPosition(delivery);
2100 delivery_pos.has_value()) {
2101 const int pair_index = delivery_pos->pd_pair_index;
2102 if (!pair_indices.contains(pair_index)) continue;
2103 for (const int64_t pickup :
2104 pickup_delivery_pairs[pair_index].pickup_alternatives) {
2105 if (Contains(pickup) ||
2106 !model()->VehicleVar(pickup)->Contains(vehicle)) {
2107 continue;
2108 }
2109 int64_t pickup_insert_after = model()->Start(vehicle);
2110 while (pickup_insert_after != insert_after) {
2111 AddPairEntry(pickup, pickup_insert_after, delivery, insert_after,
2112 vehicle, priority_queue, pickup_to_entries,
2113 delivery_to_entries);
2114 pickup_insert_after = Value(pickup_insert_after);
2115 }
2116 }
2117 }
2118 }
2119 return true;
2120}
2121
2122void GlobalCheapestInsertionFilteredHeuristic::DeletePairEntry(
2123 GlobalCheapestInsertionFilteredHeuristic::PairEntry* entry,
2124 AdjustablePriorityQueue<
2125 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
2126 std::vector<PairEntries>* pickup_to_entries,
2127 std::vector<PairEntries>* delivery_to_entries) {
2128 priority_queue->Remove(entry);
2129 if (entry->pickup_insert_after() != -1) {
2130 pickup_to_entries->at(entry->pickup_insert_after()).erase(entry);
2131 }
2132 if (entry->delivery_insert_after() != -1) {
2133 delivery_to_entries->at(entry->delivery_insert_after()).erase(entry);
2134 }
2135 pair_entry_allocator_.FreeEntry(entry);
2136}
2137
2138void GlobalCheapestInsertionFilteredHeuristic::AddPairEntry(
2139 int64_t pickup, int64_t pickup_insert_after, int64_t delivery,
2140 int64_t delivery_insert_after, int vehicle,
2141 AdjustablePriorityQueue<
2142 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
2143 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2144 pickup_entries,
2145 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
2146 delivery_entries) {
2147 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);
2148 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);
2149 if (!pickup_vehicle_var->Contains(vehicle) ||
2150 !delivery_vehicle_var->Contains(vehicle)) {
2151 if (vehicle == -1 || !VehicleIsEmpty(vehicle)) return;
2152 // We need to check there is not an equivalent empty vehicle the pair
2153 // could fit on.
2154 const auto vehicle_is_compatible = [pickup_vehicle_var,
2155 delivery_vehicle_var](int vehicle) {
2156 return pickup_vehicle_var->Contains(vehicle) &&
2157 delivery_vehicle_var->Contains(vehicle);
2158 };
2159 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(
2160 empty_vehicle_type_curator_->Type(vehicle),
2161 vehicle_is_compatible)) {
2162 return;
2163 }
2164 }
2165 const int num_allowed_vehicles =
2166 std::min(pickup_vehicle_var->Size(), delivery_vehicle_var->Size());
2167 const int64_t pair_penalty =
2169 const int64_t penalty_shift =
2170 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
2171 ? pair_penalty
2172 : 0;
2173 if (pickup_insert_after == -1) {
2174 DCHECK_EQ(delivery_insert_after, -1);
2175 DCHECK_EQ(vehicle, -1);
2176 PairEntry* pair_entry = pair_entry_allocator_.NewEntry(
2177 pickup, -1, delivery, -1, -1, num_allowed_vehicles);
2178 pair_entry->set_value(CapSub(pair_penalty, penalty_shift));
2179 priority_queue->Add(pair_entry);
2180 return;
2181 }
2182 const std::optional<int64_t> insertion_cost =
2183 GetInsertionCostForPairAtPositions(pickup, pickup_insert_after, delivery,
2184 delivery_insert_after, vehicle);
2185
2186 if (!insertion_cost.has_value()) return;
2187
2188 PairEntry* const pair_entry = pair_entry_allocator_.NewEntry(
2189 pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle,
2190 num_allowed_vehicles);
2191 pair_entry->set_value(CapSub(*insertion_cost, penalty_shift));
2192
2193 // Add entry to priority_queue and pickup_/delivery_entries.
2194 DCHECK(!priority_queue->Contains(pair_entry));
2195 pickup_entries->at(pickup_insert_after).insert(pair_entry);
2196 delivery_entries->at(delivery_insert_after).insert(pair_entry);
2197 priority_queue->Add(pair_entry);
2198}
2199
2200bool GlobalCheapestInsertionFilteredHeuristic::UpdatePairEntry(
2201 GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,
2202 AdjustablePriorityQueue<
2203 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue) {
2204 const int64_t pickup = pair_entry->pickup_to_insert();
2205 const int64_t delivery = pair_entry->delivery_to_insert();
2206 const std::optional<int64_t> insertion_cost =
2208 pickup, pair_entry->pickup_insert_after(), delivery,
2209 pair_entry->delivery_insert_after(), pair_entry->vehicle());
2210 const int64_t penalty_shift =
2211 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty) &&
2212 insertion_cost.has_value()
2213 ? CapAdd(GetUnperformedValue(pickup), GetUnperformedValue(delivery))
2214 : 0;
2215
2216 if (!insertion_cost.has_value()) {
2217 return false;
2218 }
2219
2220 pair_entry->set_value(CapSub(*insertion_cost, penalty_shift));
2221
2222 // Update the priority_queue.
2223 DCHECK(priority_queue->Contains(pair_entry));
2224 priority_queue->NoteChangedPriority(pair_entry);
2225 return true;
2226}
2227
2228bool GlobalCheapestInsertionFilteredHeuristic::InitializePositions(
2229 const SparseBitset<int>& nodes, const absl::flat_hash_set<int>& vehicles,
2230 NodeEntryQueue* queue) {
2231 queue->Clear();
2232
2233 const int num_vehicles =
2234 vehicles.empty() ? model()->vehicles() : vehicles.size();
2235 const bool all_vehicles = (num_vehicles == model()->vehicles());
2236
2237 for (int node : nodes.PositionsSetAtLeastOnce()) {
2238 if (Contains(node)) continue;
2239
2240 if (StopSearch()) return false;
2241 // Add insertion entry making node unperformed.
2242 if (gci_params_.add_unperformed_entries &&
2243 GetUnperformedValue(node) != std::numeric_limits<int64_t>::max()) {
2244 AddNodeEntry(node, node, -1, all_vehicles, queue);
2245 }
2246 // Add all insertion entries making node performed.
2247 InitializeInsertionEntriesPerformingNode(node, vehicles, queue);
2248 }
2249 return true;
2250}
2251
2252void GlobalCheapestInsertionFilteredHeuristic::
2253 InitializeInsertionEntriesPerformingNode(
2254 int64_t node, const absl::flat_hash_set<int>& vehicles,
2255 NodeEntryQueue* queue) {
2256 const int num_vehicles =
2257 vehicles.empty() ? model()->vehicles() : vehicles.size();
2258 const bool all_vehicles = (num_vehicles == model()->vehicles());
2259
2260 if (!gci_params_.use_neighbors_ratio_for_initialization) {
2261 auto vehicles_it = vehicles.begin();
2262 // TODO(user): Ideally we'd want to iterate on vehicle var values:
2263 // std::unique_ptr<IntVarIterator>
2264 // it(model()->VehicleVar(node)->MakeDomainIterator(false));
2265 // for (const int64_t v : InitAndGetValues(it)) {
2266 // Requires taking vehicles into account.
2267 for (int v = 0; v < num_vehicles; v++) {
2268 const int vehicle = vehicles.empty() ? v : *vehicles_it++;
2269 if (!model()->VehicleVar(node)->Contains(vehicle)) continue;
2270 if (all_vehicles && !IsCheapestClassRepresentative(vehicle)) continue;
2271
2272 int64_t insert_after = model()->Start(vehicle);
2273 while (insert_after != model()->End(vehicle)) {
2274 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2275 insert_after = Value(insert_after);
2276 }
2277 }
2278 return;
2279 }
2280
2281 // We're only considering the closest incoming neighbors as insertion
2282 // positions for the node.
2283 for (int cost_class = 0; cost_class < model()->GetCostClassesCount();
2284 cost_class++) {
2285 for (const int64_t insert_after :
2286 node_index_to_neighbors_by_cost_class_
2287 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, node)) {
2288 if (!Contains(insert_after)) {
2289 continue;
2290 }
2291 const int vehicle = node_index_to_vehicle_[insert_after];
2292 if (vehicle == -1 ||
2293 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
2294 continue;
2295 }
2296 if (all_vehicles) {
2297 if (!IsCheapestClassRepresentative(vehicle)) continue;
2298 } else if (!vehicles.contains(vehicle)) {
2299 continue;
2300 }
2301 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2302 }
2303 }
2304}
2305
2306bool GlobalCheapestInsertionFilteredHeuristic::UpdateAfterNodeInsertion(
2307 const SparseBitset<int>& nodes, int vehicle, int64_t node,
2308 int64_t insert_after, bool all_vehicles, NodeEntryQueue* queue) {
2309 // Update cost of existing entries after "insert_after" which now have new
2310 // nexts.
2311 if (!UpdateExistingNodeEntriesOnChain(nodes, vehicle, insert_after,
2312 Value(insert_after), all_vehicles,
2313 queue)) {
2314 return false;
2315 }
2316 // Add new entries after "node" which has just been inserted.
2317 // TODO(user): Also add node entries *before* the newly inserted node
2318 // in the case where we have non-full neighborhoods. This will leverage the
2319 // incoming neighbors of the newly inserted node, in case they're not also
2320 // outgoing neighbors of 'insert_after'.
2321 // NOTE: UpdateExistingNodeEntriesOnChain() could return the set of node
2322 // indices that already have entries between insert_after and node, to avoid
2323 // adding entries again for them when looking at incoming neighbors of node.
2324 if (!AddNodeEntriesAfter(nodes, vehicle, node, all_vehicles, queue)) {
2325 return false;
2326 }
2327 SetVehicleIndex(node, vehicle);
2328 return true;
2329}
2330
2331bool GlobalCheapestInsertionFilteredHeuristic::UpdateExistingNodeEntriesOnChain(
2332 const SparseBitset<int>& nodes, int vehicle, int64_t insert_after_start,
2333 int64_t insert_after_end, bool all_vehicles, NodeEntryQueue* queue) {
2334 int64_t insert_after = insert_after_start;
2335 while (insert_after != insert_after_end) {
2336 DCHECK(!model()->IsEnd(insert_after));
2337 AddNodeEntriesAfter(nodes, vehicle, insert_after, all_vehicles, queue);
2338 insert_after = Value(insert_after);
2339 }
2340 return true;
2341}
2342
2343bool GlobalCheapestInsertionFilteredHeuristic::AddNodeEntriesAfter(
2344 const SparseBitset<int>& nodes, int vehicle, int64_t insert_after,
2345 bool all_vehicles, NodeEntryQueue* queue) {
2346 const int cost_class = model()->GetCostClassIndexOfVehicle(vehicle).value();
2347 // Remove existing entries at 'insert_after', needed either when updating
2348 // entries or if unperformed node insertions were present.
2349 queue->ClearInsertions(insert_after);
2350 const std::vector<int>& neighbors =
2351 node_index_to_neighbors_by_cost_class_
2352 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class, insert_after);
2353 if (neighbors.size() < nodes.NumberOfSetCallsWithDifferentArguments()) {
2354 // Iterate on the neighbors.
2355 for (int node : neighbors) {
2356 if (StopSearch()) return false;
2357 if (!Contains(node) && nodes[node]) {
2358 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2359 }
2360 }
2361 } else {
2362 // Iterate on the nodes to insert.
2363 for (int node : nodes.PositionsSetAtLeastOnce()) {
2364 if (StopSearch()) return false;
2365 if (!Contains(node) &&
2366 node_index_to_neighbors_by_cost_class_->IsNeighborhoodArcForCostClass(
2367 cost_class, insert_after, node)) {
2368 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2369 }
2370 }
2371 }
2372 return true;
2373}
2374
2375void GlobalCheapestInsertionFilteredHeuristic::AddNodeEntry(
2376 int64_t node, int64_t insert_after, int vehicle, bool all_vehicles,
2377 NodeEntryQueue* queue) {
2378 const IntVar* const vehicle_var = model()->VehicleVar(node);
2379 if (!vehicle_var->Contains(vehicle)) {
2380 if (!UseEmptyVehicleTypeCuratorForVehicle(vehicle, all_vehicles)) return;
2381 // We need to check there is not an equivalent empty vehicle the node
2382 // could fit on.
2383 const auto vehicle_is_compatible = [vehicle_var](int vehicle) {
2384 return vehicle_var->Contains(vehicle);
2385 };
2386 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(
2387 empty_vehicle_type_curator_->Type(vehicle),
2388 vehicle_is_compatible)) {
2389 return;
2390 }
2391 }
2392 const int num_allowed_vehicles = vehicle_var->Size();
2393 const int64_t node_penalty = GetUnperformedValue(node);
2394 const int64_t penalty_shift =
2395 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
2396 ? node_penalty
2397 : 0;
2398 if (vehicle == -1) {
2399 DCHECK_EQ(node, insert_after);
2400 if (!all_vehicles) {
2401 // NOTE: In the case where we're not considering all routes
2402 // simultaneously, we don't add insertion entries making nodes
2403 // unperformed.
2404 return;
2405 }
2406 queue->PushInsertion(node, node, -1, num_allowed_vehicles,
2407 CapSub(node_penalty, penalty_shift));
2408 return;
2409 }
2410
2411 const std::optional<int64_t> insertion_cost =
2412 GetInsertionCostForNodeAtPosition(node, insert_after, Value(insert_after),
2413 vehicle);
2414 if (!insertion_cost.has_value()) return;
2415 if (!all_vehicles && *insertion_cost > node_penalty) {
2416 // NOTE: When all vehicles aren't considered for insertion, we don't
2417 // add entries making nodes unperformed, so we don't add insertions
2418 // which cost more than the node penalty either.
2419 return;
2420 }
2421 queue->PushInsertion(node, insert_after, vehicle, num_allowed_vehicles,
2422 CapSub(*insertion_cost, penalty_shift));
2423}
2424
2426 int pickup, int delivery, int vehicle, const std::vector<int>& path,
2427 const std::vector<bool>& path_node_is_pickup,
2428 const std::vector<bool>& path_node_is_delivery,
2429 InsertionSequenceContainer& insertions) {
2430 const int num_nodes = path.size();
2431 DCHECK_GE(num_nodes, 2);
2432 const int kNoPrevIncrease = -1;
2433 const int kNoNextDecrease = num_nodes;
2434 {
2435 prev_decrease_.resize(num_nodes - 1);
2436 prev_increase_.resize(num_nodes - 1);
2437 int prev_decrease = 0;
2438 int prev_increase = kNoPrevIncrease;
2439 for (int pos = 0; pos < num_nodes - 1; ++pos) {
2440 if (path_node_is_delivery[pos]) prev_decrease = pos;
2441 prev_decrease_[pos] = prev_decrease;
2442 if (path_node_is_pickup[pos]) prev_increase = pos;
2443 prev_increase_[pos] = prev_increase;
2444 }
2445 }
2446 {
2447 next_decrease_.resize(num_nodes - 1);
2448 next_increase_.resize(num_nodes - 1);
2449 int next_increase = num_nodes - 1;
2450 int next_decrease = kNoNextDecrease;
2451 for (int pos = num_nodes - 2; pos >= 0; --pos) {
2452 next_decrease_[pos] = next_decrease;
2453 if (path_node_is_delivery[pos]) next_decrease = pos;
2454 next_increase_[pos] = next_increase;
2455 if (path_node_is_pickup[pos]) next_increase = pos;
2456 }
2457 }
2458
2459 auto append = [pickup, delivery, vehicle, num_nodes, &path, &insertions](
2460 int pickup_pos, int delivery_pos) {
2461 if (pickup_pos < 0 || num_nodes - 1 <= pickup_pos) return;
2462 if (delivery_pos < 0 || num_nodes - 1 <= delivery_pos) return;
2463 const int delivery_pred =
2464 pickup_pos == delivery_pos ? pickup : path[delivery_pos];
2465 insertions.AddInsertionSequence(
2466 vehicle, {{.pred = path[pickup_pos], .node = pickup},
2467 {.pred = delivery_pred, .node = delivery}});
2468 };
2469
2470 // Find insertion positions for the input pair, pickup P and delivery D.
2471 for (int pos = 0; pos < num_nodes - 1; ++pos) {
2472 const bool is_after_decrease = prev_increase_[pos] < prev_decrease_[pos];
2473 const bool is_before_increase = next_increase_[pos] < next_decrease_[pos];
2474 if (is_after_decrease) {
2475 append(prev_increase_[pos], pos);
2476 if (is_before_increase) { // Upwards inflexion: vehicle is empty.
2477 append(pos, next_increase_[pos] - 1);
2478 append(pos, next_decrease_[pos] - 1);
2479 // Avoids duplicate insertions. If next_increase_[pos] - 1 == pos:
2480 // - append(pos, pos) is append(pos, next_increase_[pos] - 1)
2481 // - because is_after_decrease,
2482 // with pos' = prev_decrease_[pos],
2483 // next_increase_[pos'] == next_increase_[pos], so that
2484 // append(prev_decrease_[pos], pos) is
2485 // append(pos', next_increase_[pos'] - 1).
2486 if (next_increase_[pos] - 1 != pos) {
2487 append(pos, pos);
2488 if (prev_decrease_[pos] != pos) append(prev_decrease_[pos], pos);
2489 }
2490 }
2491 } else {
2492 append(pos, next_decrease_[pos] - 1);
2493 if (!is_before_increase && next_decrease_[pos] - 1 != pos) {
2494 // Downwards inflexion: vehicle is at its max.
2495 // Avoids duplicate insertions, when next_decrease_[pos] - 1 == pos:
2496 // - append(pos, pos) is append(pos, next_decrease_[pos] - 1)
2497 // - because is_before_increase, with pos' = prev_increase_[pos],
2498 // next_decrease_[pos'] == next_decrease_[pos], so that
2499 // append(prev_increase_[pos], pos) is
2500 // append(pos', next_decrease_[pos'] - 1).
2501 append(pos, pos);
2502 if (prev_increase_[pos] != pos) append(prev_increase_[pos], pos);
2503 }
2504 }
2505 }
2506}
2507
2508// LocalCheapestInsertionFilteredHeuristic
2509// TODO(user): Add support for penalty costs.
2512 RoutingModel* model, std::function<bool()> stop_search,
2513 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
2514 RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy,
2515 std::vector<RoutingSearchParameters::InsertionSortingProperty>
2516 insertion_sorting_properties,
2517 LocalSearchFilterManager* filter_manager, bool use_first_solution_hint,
2518 BinCapacities* bin_capacities,
2519 std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,
2520 std::vector<RoutingModel::VariableValuePair>*)>
2521 optimize_on_insertion)
2522 : CheapestInsertionFilteredHeuristic(model, std::move(stop_search),
2523 std::move(evaluator), nullptr,
2524 filter_manager),
2525 pair_insertion_strategy_(pair_insertion_strategy),
2526 insertion_sorting_properties_(std::move(insertion_sorting_properties)),
2527 use_first_solution_hint_(use_first_solution_hint),
2528 bin_capacities_(bin_capacities),
2529 optimize_on_insertion_(std::move(optimize_on_insertion)),
2530 use_random_insertion_order_(
2531 !insertion_sorting_properties_.empty() &&
2532 insertion_sorting_properties_.front() ==
2533 RoutingSearchParameters::SORTING_PROPERTY_RANDOM) {
2534 DCHECK(!insertion_sorting_properties_.empty());
2535}
2536
2538 // NOTE(user): Keeping the code in a separate function as opposed to
2539 // inlining here, to allow for future additions to this function.
2540 synchronize_insertion_optimizer_ = true;
2541 hint_next_values_.assign(model()->Size(), -1);
2542 hint_prev_values_.assign(model()->Size() + model()->vehicles(), -1);
2543 const Assignment* hint = model()->GetFirstSolutionHint();
2544 if (hint != nullptr && use_first_solution_hint_) {
2545 const Assignment::IntContainer& container = hint->IntVarContainer();
2546 for (int i = 0; i < model()->Nexts().size(); ++i) {
2547 const IntVarElement* element =
2548 container.ElementPtrOrNull(model()->NextVar(i));
2549 if (element != nullptr && element->Bound()) {
2550 hint_next_values_[i] = element->Value();
2551 hint_prev_values_[element->Value()] = i;
2552 }
2553 }
2554 }
2555 ComputeInsertionOrder();
2556}
2557
2558bool LocalCheapestInsertionFilteredHeuristic::OptimizeOnInsertion(
2559 std::vector<int> delta_indices) {
2560 if (optimize_on_insertion_ == nullptr) return false;
2561 std::vector<RoutingModel::VariableValuePair> in_state;
2562 if (synchronize_insertion_optimizer_) {
2563 for (int i = 0; i < model()->Nexts().size(); ++i) {
2564 if (Contains(i)) {
2565 in_state.push_back({i, Value(i)});
2566 }
2567 }
2568 synchronize_insertion_optimizer_ = false;
2569 } else {
2570 for (int index : delta_indices) {
2571 in_state.push_back({index, Value(index)});
2572 }
2573 }
2574 std::vector<RoutingModel::VariableValuePair> out_state;
2575 optimize_on_insertion_(in_state, &out_state);
2576 if (out_state.empty()) return false;
2577 for (const auto& [var, value] : out_state) {
2578 if (Contains(var)) {
2579 SetValue(var, value);
2580 }
2581 }
2582 return Evaluate(/*commit=*/true).has_value();
2583}
2584
2585namespace {
2586// Computes the cost from vehicle starts to pickups.
2587std::vector<std::vector<int64_t>> ComputeStartToPickupCosts(
2588 const RoutingModel& model, absl::Span<const int64_t> pickups,
2589 const Bitset64<int>& vehicle_set) {
2590 std::vector<std::vector<int64_t>> pickup_costs(model.Size());
2591 for (int64_t pickup : pickups) {
2592 std::vector<int64_t>& cost_from_start = pickup_costs[pickup];
2593 cost_from_start.resize(model.vehicles(), -1);
2594
2595 ProcessVehicleStartEndCosts(
2596 model, pickup,
2597 [&cost_from_start](int64_t cost, int v) { cost_from_start[v] = cost; },
2598 vehicle_set, /*ignore_start=*/false, /*ignore_end=*/true);
2599 }
2600 return pickup_costs;
2601}
2602
2603// Computes the cost from deliveries to vehicle ends.
2604std::vector<std::vector<int64_t>> ComputeDeliveryToEndCosts(
2605 const RoutingModel& model, absl::Span<const int64_t> deliveries,
2606 const Bitset64<int>& vehicle_set) {
2607 std::vector<std::vector<int64_t>> delivery_costs(model.Size());
2608 for (int64_t delivery : deliveries) {
2609 std::vector<int64_t>& cost_to_end = delivery_costs[delivery];
2610 cost_to_end.resize(model.vehicles(), -1);
2611
2612 ProcessVehicleStartEndCosts(
2613 model, delivery,
2614 [&cost_to_end](int64_t cost, int v) { cost_to_end[v] = cost; },
2615 vehicle_set, /*ignore_start=*/true, /*ignore_end=*/false);
2616 }
2617 return delivery_costs;
2618}
2619
2620// Returns the opposite of the maximum cost between all pickup/delivery nodes of
2621// the given pair from their "closest" vehicle.
2622// For a given pickup/delivery, the cost from the closest vehicle is defined as
2623// min_{v in vehicles}(ArcCost(start[v]->pickup) + ArcCost(delivery->end[v])).
2624int64_t GetNegMaxDistanceFromVehicles(const RoutingModel& model,
2625 int pair_index) {
2626 const auto& [pickups, deliveries] =
2627 model.GetPickupAndDeliveryPairs()[pair_index];
2628
2629 Bitset64<int> vehicle_set(model.vehicles());
2630 for (int v = 0; v < model.vehicles(); ++v) vehicle_set.Set(v);
2631
2632 // Precompute the cost from vehicle starts to every pickup in the pair.
2633 const std::vector<std::vector<int64_t>> pickup_costs =
2634 ComputeStartToPickupCosts(model, pickups, vehicle_set);
2635
2636 // Precompute the cost from every delivery in the pair to vehicle ends.
2637 const std::vector<std::vector<int64_t>> delivery_costs =
2638 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);
2639
2640 int64_t max_pair_distance = 0;
2641 for (int64_t pickup : pickups) {
2642 const std::vector<int64_t>& cost_from_start = pickup_costs[pickup];
2643 for (int64_t delivery : deliveries) {
2644 const std::vector<int64_t>& cost_to_end = delivery_costs[delivery];
2645 int64_t closest_vehicle_distance = std::numeric_limits<int64_t>::max();
2646 for (int v = 0; v < model.vehicles(); v++) {
2647 if (cost_from_start[v] < 0 || cost_to_end[v] < 0) {
2648 // Vehicle not in the pickup and/or delivery's vehicle var domain.
2649 continue;
2650 }
2651 closest_vehicle_distance =
2652 std::min(closest_vehicle_distance,
2653 CapAdd(cost_from_start[v], cost_to_end[v]));
2654 }
2655 max_pair_distance = std::max(max_pair_distance, closest_vehicle_distance);
2656 }
2657 }
2658 return CapOpp(max_pair_distance);
2659}
2660
2661// Returns the average distance between all pickup/delivery nodes of the given
2662// pair from all vehicles where they can be serverd. Returns an empty optional
2663// if no vehicle can serve the pair. For a given pickup/delivery, the distance
2664// from a vehicle v is defined as ArcCost(start[v]->pickup) +
2665// ArcCost(delivery->end[v]).
2666std::optional<int64_t> GetAvgPickupDeliveryPairDistanceFromVehicles(
2667 const RoutingModel& model, int pair_index,
2668 const Bitset64<int>& vehicle_set) {
2669 const auto& [pickups, deliveries] =
2670 model.GetPickupAndDeliveryPairs()[pair_index];
2671
2672 // Precompute the cost from vehicle starts to every pickup in the pair.
2673 const std::vector<std::vector<int64_t>> pickup_costs =
2674 ComputeStartToPickupCosts(model, pickups, vehicle_set);
2675
2676 // Precompute the cost from every delivery in the pair to vehicle ends.
2677 const std::vector<std::vector<int64_t>> delivery_costs =
2678 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);
2679
2680 int64_t avg_pair_distance_sum = 0;
2681 int valid_pairs = 0;
2682 for (int64_t pickup : pickups) {
2683 const std::vector<int64_t>& cost_from_start = pickup_costs[pickup];
2684 for (int64_t delivery : deliveries) {
2685 const std::vector<int64_t>& cost_to_end = delivery_costs[delivery];
2686 int64_t distance_from_vehicle_sum = 0;
2687 int valid_vehicles = 0;
2688 for (int v = 0; v < model.vehicles(); v++) {
2689 if (cost_from_start[v] < 0 || cost_to_end[v] < 0) {
2690 // Vehicle not in the pickup and/or delivery's vehicle var domain.
2691 continue;
2692 }
2693 distance_from_vehicle_sum =
2694 CapAdd(distance_from_vehicle_sum,
2695 CapAdd(cost_from_start[v], cost_to_end[v]));
2696 ++valid_vehicles;
2697 }
2698 if (valid_vehicles > 0) {
2699 avg_pair_distance_sum = CapAdd(
2700 distance_from_vehicle_sum / valid_vehicles, avg_pair_distance_sum);
2701 ++valid_pairs;
2702 }
2703 }
2704 }
2705 return valid_pairs > 0
2706 ? std::make_optional<int64_t>(avg_pair_distance_sum / valid_pairs)
2707 : std::nullopt;
2708}
2709
2710// Returns the maximum vehicle capacity for the given dimensions. Vehicles with
2711// infinite capacity are ignored.
2712int64_t GetMaxFiniteDimensionCapacity(
2713 const RoutingModel& model,
2714 const std::vector<RoutingDimension*>& dimensions) {
2715 int64_t max_capacity = 0;
2716 for (const RoutingDimension* dimension : dimensions) {
2717 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {
2718 const int64_t capacity = dimension->vehicle_capacities()[vehicle];
2719 if (capacity == kint64max) continue;
2720 max_capacity = std::max(max_capacity, capacity);
2721 }
2722 }
2723 return max_capacity;
2724}
2725
2726// Returns the average dimension usage of the given node scaled according to the
2727// given max capacity.
2728int64_t GetAvgNodeUnaryDimensionUsage(
2729 const RoutingModel& model, const std::vector<RoutingDimension*>& dimensions,
2730 int64_t max_vehicle_capacity, int64_t node) {
2731 if (dimensions.empty() || max_vehicle_capacity == 0) {
2732 return 0;
2733 }
2734
2735 double dimension_usage_sum = 0;
2736 for (const RoutingDimension* dimension : dimensions) {
2737 // TODO(user): extend to non unary dimensions.
2738 DCHECK(dimension->IsUnary());
2739 double dimension_usage_per_vehicle_sum = 0;
2740 int valid_vehicles = 0;
2741
2742 // TODO(user): limit computations to vehicles allowed for this node.
2743 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {
2744 const int64_t capacity = dimension->vehicle_capacities()[vehicle];
2745 if (capacity == 0) continue;
2746 DCHECK_GE(capacity, 0);
2747 valid_vehicles++;
2748 // If the capacity is infinite, bypass the "noise" added to the dimension
2749 // usage.
2750 if (capacity == kint64max) continue;
2751 const RoutingModel::TransitCallback1& transit_evaluator =
2752 dimension->GetUnaryTransitEvaluator(vehicle);
2753 dimension_usage_per_vehicle_sum +=
2754 1.0 * std::abs(transit_evaluator(node)) / capacity;
2755 }
2756
2757 if (valid_vehicles > 0) {
2758 // Cap the dimension usage to 1.0 in case some node demand is greater than
2759 // the vehicle capacity.
2760 dimension_usage_sum +=
2761 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);
2762 }
2763 }
2764
2765 // We multiply the computed dimension_usage_sum by the max_vehicle_capacity to
2766 // have a larger scale for rounding to int64_t.
2767 return MathUtil::SafeRound<int64_t>(max_vehicle_capacity *
2768 dimension_usage_sum);
2769}
2770
2771// Returns the average dimension usage of a pickup and delivery pair scaled
2772// according to the given max capacity.
2773int64_t GetAvgPickupDeliveryPairUnaryDimensionUsage(
2774 const RoutingModel& model, const std::vector<RoutingDimension*>& dimensions,
2775 int64_t max_vehicle_capacity, int pair_index) {
2776 if (dimensions.empty()) {
2777 return 0;
2778 }
2779
2780 const auto& [pickups, deliveries] =
2781 model.GetPickupAndDeliveryPairs()[pair_index];
2782 if (pickups.empty() || deliveries.empty()) {
2783 return 0;
2784 }
2785
2786 double dimension_usage_sum = 0;
2787 for (const RoutingDimension* dimension : dimensions) {
2788 double dimension_usage_per_vehicle_sum = 0;
2789 int valid_vehicles = 0;
2790 // TODO(user): limit computations to nodes allowed for this vehicle.
2791 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {
2792 const int64_t capacity = dimension->vehicle_capacities()[vehicle];
2793 if (capacity == 0) continue;
2794 valid_vehicles++;
2795 // If the capacity is infinite, bypass the "noise" added to the dimension
2796 // usage.
2797 if (capacity == kint64max) continue;
2798 const RoutingModel::TransitCallback1& transit_evaluator =
2799 dimension->GetUnaryTransitEvaluator(vehicle);
2800
2801 double pickup_sum = 0;
2802 for (int64_t pickup : pickups) {
2803 pickup_sum += 1.0 * std::abs(transit_evaluator(pickup)) / capacity;
2804 }
2805 const double avg_pickup_usage = pickup_sum / pickups.size();
2806 double delivery_sum = 0;
2807 for (int64_t delivery : deliveries) {
2808 delivery_sum += 1.0 * std::abs(transit_evaluator(delivery)) / capacity;
2809 }
2810 const double avg_delivery_usage = delivery_sum / deliveries.size();
2811 dimension_usage_per_vehicle_sum +=
2812 std::max(avg_pickup_usage, avg_delivery_usage);
2813 }
2814
2815 if (valid_vehicles > 0) {
2816 // Cap the dimension usage to 1.0 in case some node demand is greater than
2817 // the vehicle capacity.
2818 dimension_usage_sum +=
2819 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);
2820 }
2821 }
2822
2823 // We multiply the computed dimension_usage_sum by the max_vehicle_capacity to
2824 // have a larger scale for rounding to int64_t.
2825 return MathUtil::SafeRound<int64_t>(max_vehicle_capacity *
2826 dimension_usage_sum);
2827}
2828} // namespace
2829
2830void LocalCheapestInsertionFilteredHeuristic::ComputeInsertionOrder() {
2831 if (use_random_insertion_order_) {
2832 if (insertion_order_.empty()) {
2833 const RoutingModel& model = *this->model();
2834 insertion_order_.reserve(model.Size() +
2835 model.GetPickupAndDeliveryPairs().size());
2836 for (int pair_index = 0;
2837 pair_index < model.GetPickupAndDeliveryPairs().size();
2838 ++pair_index) {
2839 insertion_order_.push_back(
2840 {.is_node_index = false, .index = pair_index});
2841 }
2842 for (int node = 0; node < model.Size(); ++node) {
2843 if (model.IsStart(node) || model.IsEnd(node)) continue;
2844 insertion_order_.push_back({.is_node_index = true, .index = node});
2845 }
2846 }
2847 // We disregard all other properties and sort nodes/pairs in a random order.
2848 absl::c_shuffle(insertion_order_, rnd_);
2849 return;
2850 }
2851
2852 if (!insertion_order_.empty()) return;
2853
2854 // We consider pairs and single nodes simultaneously, to make sure the most
2855 // critical ones (fewer allowed vehicles and high penalties) get inserted
2856 // first.
2857 // TODO(user): Explore other metrics to evaluate criticality, more directly
2858 // mixing penalties and allowed vehicles (such as a ratio between the two).
2859
2860 const RoutingModel& model = *this->model();
2861 insertion_order_.reserve(model.Size() +
2862 model.GetPickupAndDeliveryPairs().size());
2863
2864 auto get_insertion_properties = [this](int64_t penalty,
2865 int64_t num_allowed_vehicles,
2866 int64_t avg_distance_to_vehicle,
2867 int64_t neg_min_distance_to_vehicles,
2868 int hint_weight,
2869 int reversed_hint_weight,
2870 int64_t avg_dimension_usage) {
2871 DCHECK_NE(0, num_allowed_vehicles);
2872 absl::InlinedVector<int64_t, 8> properties;
2873 properties.reserve(insertion_sorting_properties_.size());
2874
2875 // Always consider hints first. We favor nodes with hints over nodes with
2876 // reversed hints.
2877 // TODO(user): Figure out a way to insert hinted nodes in a logical
2878 // order. We could try toposorting hinted nodes.
2879 properties.push_back(-hint_weight);
2880 properties.push_back(-reversed_hint_weight);
2881
2882 bool neg_min_distance_to_vehicles_appended = false;
2883 for (const int property : insertion_sorting_properties_) {
2884 switch (property) {
2886 properties.push_back(num_allowed_vehicles);
2887 break;
2889 properties.push_back(CapOpp(penalty));
2890 break;
2891 case RoutingSearchParameters::
2892 SORTING_PROPERTY_PENALTY_OVER_ALLOWED_VEHICLES_RATIO:
2893 properties.push_back(CapOpp(penalty / num_allowed_vehicles));
2894 break;
2895 case RoutingSearchParameters::
2896 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:
2897 properties.push_back(CapOpp(avg_distance_to_vehicle));
2898 break;
2899 case RoutingSearchParameters::
2900 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:
2901 properties.push_back(avg_distance_to_vehicle);
2902 break;
2903 case RoutingSearchParameters::
2904 SORTING_PROPERTY_LOWEST_MIN_ARC_COST_TO_VEHICLE_START_ENDS:
2905 properties.push_back(neg_min_distance_to_vehicles);
2906 neg_min_distance_to_vehicles_appended = true;
2907 break;
2909 properties.push_back(CapOpp(avg_dimension_usage));
2910 break;
2911 default:
2912 LOG(DFATAL)
2913 << "Unknown RoutingSearchParameter::InsertionSortingProperty "
2914 "used!";
2915 break;
2916 }
2917 }
2918
2919 // Historically the negative max distance to vehicles has always been
2920 // considered to be the last property in the hierarchy defining how nodes
2921 // are sorted for the LCI heuristic, so we add it here iff it wasn't added
2922 // before
2923 if (!neg_min_distance_to_vehicles_appended) {
2924 properties.push_back(neg_min_distance_to_vehicles);
2925 }
2926
2927 return properties;
2928 };
2929
2930 // Identify whether the selected properties require a more expensive
2931 // preprocessing.
2932 bool compute_avg_pickup_delivery_pair_distance_from_vehicles = false;
2933 bool compute_avg_dimension_usage = false;
2935 insertion_sorting_properties_) {
2936 if (property ==
2937 RoutingSearchParameters::
2938 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS ||
2939 property ==
2940 RoutingSearchParameters::
2941 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS) {
2942 compute_avg_pickup_delivery_pair_distance_from_vehicles = true;
2943 }
2944 if (property ==
2946 compute_avg_dimension_usage = true;
2947 }
2948 }
2949
2950 Bitset64<int> vehicle_set(model.vehicles());
2951 for (int v = 0; v < model.vehicles(); ++v) vehicle_set.Set(v);
2952
2953 const std::vector<RoutingDimension*> unary_dimensions =
2954 compute_avg_dimension_usage ? model.GetUnaryDimensions()
2955 : std::vector<RoutingDimension*>();
2956
2957 const int64_t max_dimension_capacity =
2958 compute_avg_dimension_usage
2959 ? GetMaxFiniteDimensionCapacity(model, unary_dimensions)
2960 : 0;
2961
2962 // Iterating on pickup and delivery pairs.
2963 const std::vector<PickupDeliveryPair>& pairs =
2964 model.GetPickupAndDeliveryPairs();
2965
2966 for (int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
2967 const auto& [pickups, deliveries] = pairs[pair_index];
2968 int64_t num_allowed_vehicles = std::numeric_limits<int64_t>::max();
2969 int64_t pickup_penalty = 0;
2970 int hint_weight = 0;
2971 int reversed_hint_weight = 0;
2972 for (int64_t pickup : pickups) {
2973 num_allowed_vehicles =
2974 std::min(num_allowed_vehicles,
2975 static_cast<int64_t>(model.VehicleVar(pickup)->Size()));
2976 pickup_penalty =
2977 std::max(pickup_penalty, model.UnperformedPenalty(pickup));
2978 hint_weight += HasHintedNext(pickup);
2979 reversed_hint_weight += HasHintedPrev(pickup);
2980 }
2981 int64_t delivery_penalty = 0;
2982 for (int64_t delivery : deliveries) {
2983 num_allowed_vehicles =
2984 std::min(num_allowed_vehicles,
2985 static_cast<int64_t>(model.VehicleVar(delivery)->Size()));
2986 delivery_penalty =
2987 std::max(delivery_penalty, model.UnperformedPenalty(delivery));
2988 hint_weight += HasHintedNext(delivery);
2989 reversed_hint_weight += HasHintedPrev(delivery);
2990 }
2991
2992 const std::optional<int64_t> maybe_avg_pair_to_vehicle_cost =
2993 compute_avg_pickup_delivery_pair_distance_from_vehicles
2994 ? GetAvgPickupDeliveryPairDistanceFromVehicles(model, pair_index,
2995 vehicle_set)
2996 : std::make_optional<int64_t>(0);
2997
2998 if (!maybe_avg_pair_to_vehicle_cost.has_value()) {
2999 // There is no vehicle that can serve the pickup/delivery nodes in the
3000 // current pair index.
3001 continue;
3002 }
3003
3004 const int64_t avg_pair_dimension_usage =
3005 compute_avg_dimension_usage
3006 ? GetAvgPickupDeliveryPairUnaryDimensionUsage(
3007 model, unary_dimensions, max_dimension_capacity, pair_index)
3008 : 0;
3009
3010 absl::InlinedVector<int64_t, 8> properties = get_insertion_properties(
3011 CapAdd(pickup_penalty, delivery_penalty), num_allowed_vehicles,
3012 maybe_avg_pair_to_vehicle_cost.value(),
3013 GetNegMaxDistanceFromVehicles(model, pair_index), hint_weight,
3014 reversed_hint_weight, avg_pair_dimension_usage);
3015
3016 insertion_order_.push_back({.properties = std::move(properties),
3017 .vehicle = 0,
3018 .is_node_index = false,
3019 .index = pair_index});
3020 }
3021
3022 for (int node = 0; node < model.Size(); ++node) {
3023 if (model.IsStart(node) || model.IsEnd(node)) continue;
3024
3025 int64_t min_distance = std::numeric_limits<int64_t>::max();
3026 int64_t sum_distance = 0;
3027 ProcessVehicleStartEndCosts(
3028 model, node,
3029 [&min_distance, &sum_distance](int64_t dist, int) {
3030 min_distance = std::min(min_distance, dist);
3031 sum_distance = CapAdd(dist, sum_distance);
3032 },
3033 vehicle_set);
3034 DCHECK_GT(vehicle_set.size(), 0);
3035
3036 const int64_t avg_dimension_usage =
3037 compute_avg_dimension_usage
3038 ? GetAvgNodeUnaryDimensionUsage(model, unary_dimensions,
3039 max_dimension_capacity, node)
3040 : 0;
3041
3042 absl::InlinedVector<int64_t, 8> properties = get_insertion_properties(
3043 model.UnperformedPenalty(node), model.VehicleVar(node)->Size(),
3044 sum_distance / vehicle_set.size(), CapOpp(min_distance),
3045 HasHintedNext(node), HasHintedPrev(node), avg_dimension_usage);
3046 insertion_order_.push_back({.properties = std::move(properties),
3047 .vehicle = 0,
3048 .is_node_index = true,
3049 .index = node});
3050 }
3051
3052 absl::c_sort(insertion_order_, std::greater<Seed>());
3053 absl::c_reverse(insertion_order_);
3054}
3055
3056bool LocalCheapestInsertionFilteredHeuristic::InsertPair(
3057 int64_t pickup, int64_t insert_pickup_after, int64_t delivery,
3058 int64_t insert_delivery_after, int vehicle) {
3059 const int64_t insert_pickup_before = Value(insert_pickup_after);
3060 InsertBetween(pickup, insert_pickup_after, insert_pickup_before, vehicle);
3061 DCHECK_NE(insert_delivery_after, insert_pickup_after);
3062 const int64_t insert_delivery_before = (insert_delivery_after == pickup)
3063 ? insert_pickup_before
3064 : Value(insert_delivery_after);
3065 InsertBetween(delivery, insert_delivery_after, insert_delivery_before,
3066 vehicle);
3067 // Capturing the state of the delta before it gets wiped by Evaluate.
3068 std::vector<int> indices = delta_indices();
3069 if (Evaluate(/*commit=*/true, /*ignore_upper_bound=*/true).has_value()) {
3070 OptimizeOnInsertion(std::move(indices));
3071 return true;
3072 }
3073 return false;
3074}
3075
3076void LocalCheapestInsertionFilteredHeuristic::InsertBestPickupThenDelivery(
3077 const PickupDeliveryPair& index_pair) {
3078 for (int pickup : index_pair.pickup_alternatives) {
3079 std::vector<NodeInsertion> pickup_insertions =
3080 ComputeEvaluatorSortedPositions(pickup);
3081 for (int delivery : index_pair.delivery_alternatives) {
3082 if (StopSearch()) return;
3083 for (const NodeInsertion& pickup_insertion : pickup_insertions) {
3084 const int vehicle = pickup_insertion.vehicle;
3085 if (!model()->VehicleVar(delivery)->Contains(vehicle)) continue;
3086 if (MustUpdateBinCapacities() &&
3087 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},
3088 vehicle)) {
3089 continue;
3090 }
3091 for (const NodeInsertion& delivery_insertion :
3092 ComputeEvaluatorSortedPositionsOnRouteAfter(
3093 delivery, pickup, Value(pickup_insertion.insert_after),
3094 vehicle)) {
3095 if (InsertPair(pickup, pickup_insertion.insert_after, delivery,
3096 delivery_insertion.insert_after, vehicle)) {
3097 if (MustUpdateBinCapacities()) {
3098 bin_capacities_->AddItemToBin(pickup, vehicle);
3099 bin_capacities_->AddItemToBin(delivery, vehicle);
3100 }
3101 return;
3102 }
3103 }
3104 if (StopSearch()) return;
3105 }
3106 }
3107 }
3108}
3109
3110void LocalCheapestInsertionFilteredHeuristic::InsertBestPair(
3111 const PickupDeliveryPair& pair) {
3112 for (int pickup : pair.pickup_alternatives) {
3113 for (int delivery : pair.delivery_alternatives) {
3114 if (StopSearch()) return;
3115 std::vector<PickupDeliveryInsertion> sorted_pair_positions =
3116 ComputeEvaluatorSortedPairPositions(pickup, delivery);
3117 if (sorted_pair_positions.empty()) continue;
3118 for (const auto [insert_pickup_after, insert_delivery_after,
3119 unused_hint_weight, unused_value, vehicle] :
3120 sorted_pair_positions) {
3121 if (InsertPair(pickup, insert_pickup_after, delivery,
3122 insert_delivery_after, vehicle)) {
3123 if (MustUpdateBinCapacities()) {
3124 bin_capacities_->AddItemToBin(pickup, vehicle);
3125 bin_capacities_->AddItemToBin(delivery, vehicle);
3126 }
3127 return;
3128 }
3129 if (StopSearch()) return;
3130 }
3131 }
3132 }
3133}
3134
3135void LocalCheapestInsertionFilteredHeuristic::InsertBestPairMultitour(
3136 const PickupDeliveryPair& pair) {
3137 using InsertionSequence = InsertionSequenceContainer::InsertionSequence;
3138 using Insertion = InsertionSequenceContainer::Insertion;
3139
3140 std::vector<int> path;
3141 std::vector<bool> path_node_is_pickup;
3142 std::vector<bool> path_node_is_delivery;
3143 // Fills path with all nodes visited by vehicle, including start/end.
3144 auto fill_path = [&path, &path_node_is_pickup, &path_node_is_delivery,
3145 this](int vehicle) {
3146 path.clear();
3147 path_node_is_pickup.clear();
3148 path_node_is_delivery.clear();
3149 const int start = model()->Start(vehicle);
3150 const int end = model()->End(vehicle);
3151 for (int node = start; node != end; node = Value(node)) {
3152 path.push_back(node);
3153 path_node_is_pickup.push_back(model()->IsPickup(node));
3154 path_node_is_delivery.push_back(model()->IsDelivery(node));
3155 }
3156 path.push_back(end);
3157 };
3158
3159 // Fills value field of all insertions, kint64max if unevaluable.
3160 auto price_insertion_sequences = [this]() {
3161 for (InsertionSequence sequence : insertion_container_) {
3162 int64_t sequence_cost = 0;
3163 int previous_node = -1;
3164 int previous_succ = -1;
3165 int hint_weight = 0;
3166 for (const Insertion& insertion : sequence) {
3167 const int succ = previous_node == insertion.pred
3168 ? previous_succ
3169 : Value(insertion.pred);
3170 hint_weight += IsHint(insertion.pred, insertion.node);
3171 hint_weight += IsHint(insertion.node, succ);
3172 if (evaluator_ == nullptr) {
3173 InsertBetween(insertion.node, insertion.pred, succ,
3174 sequence.Vehicle());
3175 } else {
3177 insertion.node, insertion.pred, succ, sequence.Vehicle());
3178 CapAddTo(cost, &sequence_cost);
3179 }
3180 previous_node = insertion.node;
3181 previous_succ = succ;
3182 }
3183 if (evaluator_ == nullptr) {
3184 sequence_cost =
3185 Evaluate(/*commit=*/false, /*ignore_upper_bound=*/hint_weight > 0)
3186 .value_or(kint64max);
3187 }
3188 sequence.Cost() = sequence_cost;
3189 sequence.SetHintWeight(hint_weight);
3190 }
3191 if (bin_capacities_ == nullptr || evaluator_ == nullptr) return;
3192 for (InsertionSequence sequence : insertion_container_) {
3193 const int64_t old_cost = bin_capacities_->TotalCost();
3194 for (const Insertion& insertion : sequence) {
3195 bin_capacities_->AddItemToBin(insertion.node, sequence.Vehicle());
3196 }
3197 const int64_t new_cost = bin_capacities_->TotalCost();
3198 const int64_t delta_cost = CapSub(new_cost, old_cost);
3199 CapAddTo(delta_cost, &sequence.Cost());
3200 for (const Insertion& insertion : sequence) {
3201 bin_capacities_->RemoveItemFromBin(insertion.node, sequence.Vehicle());
3202 }
3203 }
3204 };
3205
3206 for (int pickup : pair.pickup_alternatives) {
3207 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);
3208 if (StopSearch()) return;
3209 for (int delivery : pair.delivery_alternatives) {
3210 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);
3211 insertion_container_.Clear();
3212 std::unique_ptr<IntVarIterator> pickup_vehicles(
3213 pickup_vehicle_var->MakeDomainIterator(false));
3214 for (const int vehicle : InitAndGetValues(pickup_vehicles.get())) {
3215 if (vehicle == -1) continue;
3216 if (!delivery_vehicle_var->Contains(vehicle)) continue;
3217 if (MustUpdateBinCapacities() &&
3218 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},
3219 vehicle)) {
3220 continue;
3221 }
3222 fill_path(vehicle);
3223 insertion_generator_.AppendPickupDeliveryMultitourInsertions(
3224 pickup, delivery, vehicle, path, path_node_is_pickup,
3225 path_node_is_delivery, insertion_container_);
3226 }
3227 if (StopSearch()) return;
3228 price_insertion_sequences();
3229 if (StopSearch()) return;
3230 insertion_container_.RemoveIf(
3231 [](const InsertionSequence& sequence) -> bool {
3232 return sequence.Cost() == kint64max;
3233 });
3234 insertion_container_.Sort();
3235 for (InsertionSequence sequence : insertion_container_) {
3236 if (StopSearch()) return;
3237 int previous_node = -1;
3238 int previous_succ = -1;
3239 const int vehicle = sequence.Vehicle();
3240 for (const Insertion& insertion : sequence) {
3241 const int succ = previous_node == insertion.pred
3242 ? previous_succ
3243 : Value(insertion.pred);
3244 InsertBetween(insertion.node, insertion.pred, succ, vehicle);
3245 previous_node = insertion.node;
3246 previous_succ = succ;
3247 }
3248 if (Evaluate(/*commit=*/true, /*ignore_upper_bound=*/true)
3249 .has_value()) {
3250 // Insertion succeeded.
3251 if (MustUpdateBinCapacities()) {
3252 bin_capacities_->AddItemToBin(pickup, vehicle);
3253 bin_capacities_->AddItemToBin(delivery, vehicle);
3254 }
3255 return;
3256 }
3257 }
3258 }
3259 }
3260}
3261
3262namespace {
3263void SetFalseForAllAlternatives(const PickupDeliveryPair& pair,
3264 std::vector<bool>* data) {
3265 for (const int64_t pickup : pair.pickup_alternatives) {
3266 data->at(pickup) = false;
3267 }
3268 for (const int64_t delivery : pair.delivery_alternatives) {
3269 data->at(delivery) = false;
3270 }
3271}
3272} // namespace
3273
3275 const RoutingModel& model = *this->model();
3276
3277 // Fill vehicle bins with nodes that are already inserted.
3278 if (MustUpdateBinCapacities()) {
3279 bin_capacities_->ClearItems();
3280 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {
3281 const int start = Value(model.Start(vehicle));
3282 for (int node = start; !model.IsEnd(node); node = Value(node)) {
3283 bin_capacities_->AddItemToBin(node, vehicle);
3284 }
3285 }
3286 }
3287
3288 const std::vector<PickupDeliveryPair>& pairs =
3289 model.GetPickupAndDeliveryPairs();
3290 std::vector<bool> ignore_pair_index(pairs.size(), false);
3291 std::vector<bool> insert_as_single_node(model.Size(), true);
3292 for (int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
3293 const auto& [pickups, deliveries] = pairs[pair_index];
3294 bool pickup_contained = false;
3295 for (int64_t pickup : pickups) {
3296 if (Contains(pickup)) {
3297 pickup_contained = true;
3298 break;
3299 }
3300 }
3301 bool delivery_contained = false;
3302 for (int64_t delivery : deliveries) {
3303 if (Contains(delivery)) {
3304 delivery_contained = true;
3305 break;
3306 }
3307 }
3308 ignore_pair_index[pair_index] = pickup_contained || delivery_contained;
3309 if (pickup_contained == delivery_contained) {
3310 // Either both pickup and delivery are already inserted for this pair, or
3311 // neither are inserted and should be considered as pair.
3312 // In both cases, the nodes in the pickup/delivery alternatives shouldn't
3313 // be considered for insertion as single nodes.
3314 SetFalseForAllAlternatives(pairs[pair_index], &insert_as_single_node);
3315 }
3316 }
3317
3318 for (const Seed& seed : insertion_order_) {
3319 const int index = seed.index;
3320 if (!seed.is_node_index) {
3321 if (ignore_pair_index[index]) continue;
3322
3323 const auto& pair = pairs[index];
3324 switch (pair_insertion_strategy_) {
3327 InsertBestPair(pair);
3328 break;
3330 InsertBestPickupThenDelivery(pair);
3331 break;
3333 InsertBestPairMultitour(pair);
3334 break;
3335 default:
3336 LOG(ERROR) << "Unknown pair insertion strategy value.";
3337 break;
3338 }
3339 if (StopSearch()) {
3340 return MakeUnassignedNodesUnperformed() && Evaluate(true).has_value();
3341 }
3342 } else {
3343 if (Contains(index) || !insert_as_single_node[index]) {
3344 continue;
3345 }
3346 for (const NodeInsertion& insertion :
3347 ComputeEvaluatorSortedPositions(index)) {
3348 if (StopSearch()) {
3349 return MakeUnassignedNodesUnperformed() && Evaluate(true).has_value();
3350 }
3351 InsertBetween(index, insertion.insert_after,
3352 Value(insertion.insert_after), insertion.vehicle);
3353 // Capturing the state of the delta before it gets wiped by Evaluate.
3354 std::vector<int> indices = delta_indices();
3355 if (Evaluate(/*commit=*/true, /*ignore_upper_bound=*/true)
3356 .has_value()) {
3357 if (MustUpdateBinCapacities()) {
3358 bin_capacities_->AddItemToBin(index, insertion.vehicle);
3359 }
3360 OptimizeOnInsertion(std::move(indices));
3361 break;
3362 }
3363 }
3364 }
3365 }
3366 return MakeUnassignedNodesUnperformed() && Evaluate(true).has_value();
3367}
3368
3369void LocalCheapestInsertionFilteredHeuristic::AppendInsertionPositionsAfter(
3370 int64_t node_to_insert, int64_t start, int64_t next_after_start,
3371 int vehicle, std::vector<NodeInsertion>* node_insertions) {
3372 DCHECK(node_insertions != nullptr);
3373 int64_t insert_after = start;
3374 if (!model()->VehicleVar(node_to_insert)->Contains(vehicle)) return;
3375 while (!model()->IsEnd(insert_after)) {
3376 const int64_t insert_before =
3377 (insert_after == start) ? next_after_start : Value(insert_after);
3378 const int hint_weight = IsHint(insert_after, node_to_insert) +
3379 IsHint(node_to_insert, insert_before) -
3380 IsHint(insert_after, insert_before);
3381 const auto insertion_cost = GetInsertionCostForNodeAtPosition(
3382 node_to_insert, insert_after, insert_before, vehicle, hint_weight);
3383 if (insertion_cost.has_value()) {
3384 node_insertions->push_back(
3385 {insert_after, vehicle, -hint_weight, *insertion_cost});
3386 }
3387 insert_after = insert_before;
3388 }
3389}
3390
3391std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>
3392LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPositions(
3393 int64_t node) {
3394 DCHECK(!Contains(node));
3395 const int size = model()->Size();
3396 if (node >= size) return {};
3397 std::vector<NodeInsertion> sorted_insertions;
3398 const IntVar* vehicle_var = model()->VehicleVar(node);
3399 std::unique_ptr<IntVarIterator> node_vehicles(
3400 vehicle_var->MakeDomainIterator(false));
3401 for (const int vehicle : InitAndGetValues(node_vehicles.get())) {
3402 if (vehicle == -1) continue;
3403 if (MustUpdateBinCapacities() &&
3404 !bin_capacities_->CheckAdditionFeasibility(node, vehicle)) {
3405 continue;
3406 }
3407 const int64_t start = model()->Start(vehicle);
3408 const size_t old_num_insertions = sorted_insertions.size();
3409 AppendInsertionPositionsAfter(node, start, Value(start), vehicle,
3410 &sorted_insertions);
3411 if (MustUpdateBinCapacities() && evaluator_) {
3412 // Compute cost incurred from soft capacities.
3413 const int64_t old_cost = bin_capacities_->TotalCost();
3414 bin_capacities_->AddItemToBin(node, vehicle);
3415 const int64_t new_cost = bin_capacities_->TotalCost();
3416 bin_capacities_->RemoveItemFromBin(node, vehicle);
3417 const int64_t delta_cost = CapSub(new_cost, old_cost);
3418 // Add soft cost to new insertions.
3419 for (size_t i = old_num_insertions; i < sorted_insertions.size(); ++i) {
3420 CapAddTo(delta_cost, &sorted_insertions[i].value);
3421 }
3422 }
3423 }
3424 absl::c_sort(sorted_insertions);
3425 return sorted_insertions;
3426}
3427
3428std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>
3429LocalCheapestInsertionFilteredHeuristic::
3430 ComputeEvaluatorSortedPositionsOnRouteAfter(int64_t node, int64_t start,
3431 int64_t next_after_start,
3432 int vehicle) {
3433 DCHECK(!Contains(node));
3434 const int size = model()->Size();
3435 if (node >= size) return {};
3436 std::vector<NodeInsertion> sorted_insertions;
3437 AppendInsertionPositionsAfter(node, start, next_after_start, vehicle,
3438 &sorted_insertions);
3439 absl::c_sort(sorted_insertions);
3440 return sorted_insertions;
3441}
3442
3443std::vector<PickupDeliveryInsertion>
3444LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPairPositions(
3445 int pickup, int delivery) {
3446 std::vector<PickupDeliveryInsertion> sorted_pickup_delivery_insertions;
3447 const int size = model()->Size();
3448 DCHECK_LT(pickup, size);
3449 DCHECK_LT(delivery, size);
3450 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);
3451 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);
3452 std::unique_ptr<IntVarIterator> pickup_vehicles(
3453 pickup_vehicle_var->MakeDomainIterator(false));
3454 for (const int vehicle : InitAndGetValues(pickup_vehicles.get())) {
3455 if (vehicle == -1) continue;
3456 if (!delivery_vehicle_var->Contains(vehicle)) continue;
3457 if (MustUpdateBinCapacities() &&
3458 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},
3459 vehicle)) {
3460 continue;
3461 }
3462 int64_t insert_pickup_after = model()->Start(vehicle);
3463 while (!model()->IsEnd(insert_pickup_after)) {
3464 const int64_t insert_pickup_before = Value(insert_pickup_after);
3465 int64_t insert_delivery_after = pickup;
3466 while (!model()->IsEnd(insert_delivery_after)) {
3467 if (StopSearch()) return {};
3468 const int64_t insert_delivery_before =
3469 insert_delivery_after == pickup ? insert_pickup_before
3470 : Value(insert_delivery_after);
3471 const int hint_weight = IsHint(insert_pickup_after, pickup) +
3472 IsHint(insert_delivery_after, delivery) +
3473 IsHint(pickup, insert_pickup_before) +
3474 IsHint(delivery, insert_delivery_before);
3475 const auto insertion_cost = GetInsertionCostForPairAtPositions(
3476 pickup, insert_pickup_after, delivery, insert_delivery_after,
3477 vehicle, hint_weight);
3478 if (insertion_cost.has_value()) {
3479 int64_t total_cost = *insertion_cost;
3480 if (evaluator_ && MustUpdateBinCapacities()) {
3481 const int64_t old_cost = bin_capacities_->TotalCost();
3482 bin_capacities_->AddItemToBin(pickup, vehicle);
3483 bin_capacities_->AddItemToBin(delivery, vehicle);
3484 const int64_t new_cost = bin_capacities_->TotalCost();
3485 CapAddTo(CapSub(new_cost, old_cost), &total_cost);
3486 bin_capacities_->RemoveItemFromBin(pickup, vehicle);
3487 bin_capacities_->RemoveItemFromBin(delivery, vehicle);
3488 }
3489 sorted_pickup_delivery_insertions.push_back(
3490 {insert_pickup_after, insert_delivery_after, -hint_weight,
3491 total_cost, vehicle});
3492 }
3493 insert_delivery_after = insert_delivery_before;
3494 }
3495 insert_pickup_after = insert_pickup_before;
3496 }
3497 }
3498 absl::c_sort(sorted_pickup_delivery_insertions);
3499 return sorted_pickup_delivery_insertions;
3500}
3501
3502// CheapestAdditionFilteredHeuristic
3503
3505 RoutingModel* model, std::function<bool()> stop_search,
3506 LocalSearchFilterManager* filter_manager)
3507 : RoutingFilteredHeuristic(model, std::move(stop_search), filter_manager) {}
3508
3510 const int kUnassigned = -1;
3511 const int num_nexts = model()->Nexts().size();
3512 std::vector<std::vector<int64_t>> deliveries(num_nexts);
3513 std::vector<std::vector<int64_t>> pickups(num_nexts);
3514 for (const auto& [pickup_alternatives, delivery_alternatives] :
3515 model()->GetPickupAndDeliveryPairs()) {
3516 for (int pickup : pickup_alternatives) {
3517 for (int delivery : delivery_alternatives) {
3518 deliveries[pickup].push_back(delivery);
3519 pickups[delivery].push_back(pickup);
3520 }
3521 }
3522 }
3523 // To mimic the behavior of PathSelector (cf. search.cc), iterating on
3524 // routes with partial route at their start first then on routes with largest
3525 // index.
3526 std::vector<int> sorted_vehicles(model()->vehicles(), 0);
3527 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
3528 sorted_vehicles[vehicle] = vehicle;
3529 }
3530 absl::c_sort(sorted_vehicles,
3531 PartialRoutesAndLargeVehicleIndicesFirst(*this));
3532 // Neighbors of the node currently being extended.
3533 for (const int vehicle : sorted_vehicles) {
3534 int64_t last_node = GetStartChainEnd(vehicle);
3535 bool extend_route = true;
3536 // Extend the route of the current vehicle while it's possible. We can
3537 // iterate more than once if pickup and delivery pairs have been inserted
3538 // in the last iteration (see comment below); the new iteration will try to
3539 // extend the route after the last delivery on the route.
3540 while (extend_route) {
3541 extend_route = false;
3542 bool found = true;
3543 int64_t index = last_node;
3544 int64_t end = GetEndChainStart(vehicle);
3545 // Extend the route until either the end node of the vehicle is reached
3546 // or no node or node pair can be added. Deliveries in pickup and
3547 // delivery pairs are added at the same time as pickups, at the end of the
3548 // route, in reverse order of the pickups. Deliveries are never added
3549 // alone.
3550 while (found && !model()->IsEnd(index)) {
3551 found = false;
3552 std::vector<int64_t> neighbors;
3553 if (index < model()->Nexts().size()) {
3554 std::unique_ptr<IntVarIterator> it(
3555 model()->Nexts()[index]->MakeDomainIterator(false));
3556 auto next_values = InitAndGetValues(it.get());
3557 neighbors = GetPossibleNextsFromIterator(index, next_values.begin(),
3558 next_values.end());
3559 }
3560 for (int i = 0; !found && i < neighbors.size(); ++i) {
3561 int64_t next = -1;
3562 switch (i) {
3563 case 0:
3564 next = FindTopSuccessor(index, neighbors);
3565 break;
3566 case 1:
3567 SortSuccessors(index, &neighbors);
3568 ABSL_FALLTHROUGH_INTENDED;
3569 default:
3570 next = neighbors[i];
3571 }
3572 if (model()->IsEnd(next) && next != end) {
3573 continue;
3574 }
3575 // Only add a delivery if one of its pickups has been added already.
3576 if (!model()->IsEnd(next) && !pickups[next].empty()) {
3577 bool contains_pickups = false;
3578 for (int64_t pickup : pickups[next]) {
3579 if (Contains(pickup)) {
3580 contains_pickups = true;
3581 break;
3582 }
3583 }
3584 if (!contains_pickups) {
3585 continue;
3586 }
3587 }
3588 std::vector<int64_t> next_deliveries;
3589 if (next < deliveries.size()) {
3590 next_deliveries = GetPossibleNextsFromIterator(
3591 next, deliveries[next].begin(), deliveries[next].end());
3592 }
3593 if (next_deliveries.empty()) next_deliveries = {kUnassigned};
3594 for (int j = 0; !found && j < next_deliveries.size(); ++j) {
3595 if (StopSearch()) return false;
3596 int delivery = -1;
3597 switch (j) {
3598 case 0:
3599 delivery = FindTopSuccessor(next, next_deliveries);
3600 break;
3601 case 1:
3602 SortSuccessors(next, &next_deliveries);
3603 ABSL_FALLTHROUGH_INTENDED;
3604 default:
3605 delivery = next_deliveries[j];
3606 }
3607 // Insert "next" after "index", and before "end" if it is not the
3608 // end already.
3609 SetNext(index, next, vehicle);
3610 if (!model()->IsEnd(next)) {
3611 SetNext(next, end, vehicle);
3613 if (delivery != kUnassigned) {
3614 SetNext(next, delivery, vehicle);
3615 SetNext(delivery, end, vehicle);
3617 }
3618 }
3619 if (Evaluate(/*commit=*/true).has_value()) {
3620 index = next;
3621 found = true;
3622 if (delivery != kUnassigned) {
3623 if (model()->IsEnd(end) && last_node != delivery) {
3624 last_node = delivery;
3625 extend_route = true;
3626 }
3627 end = delivery;
3628 }
3629 break;
3630 }
3631 }
3632 }
3633 }
3634 }
3635 }
3637 return Evaluate(/*commit=*/true).has_value();
3638}
3639
3640bool CheapestAdditionFilteredHeuristic::
3641 PartialRoutesAndLargeVehicleIndicesFirst::operator()(int vehicle1,
3642 int vehicle2) const {
3643 const bool has_partial_route1 = (builder_.model()->Start(vehicle1) !=
3644 builder_.GetStartChainEnd(vehicle1));
3645 const bool has_partial_route2 = (builder_.model()->Start(vehicle2) !=
3646 builder_.GetStartChainEnd(vehicle2));
3647 if (has_partial_route1 == has_partial_route2) {
3648 return vehicle2 < vehicle1;
3649 } else {
3650 return has_partial_route2 < has_partial_route1;
3651 }
3652}
3653
3654// EvaluatorCheapestAdditionFilteredHeuristic
3655
3658 RoutingModel* model, std::function<bool()> stop_search,
3659 std::function<int64_t(int64_t, int64_t)> evaluator,
3660 LocalSearchFilterManager* filter_manager)
3661 : CheapestAdditionFilteredHeuristic(model, std::move(stop_search),
3662 filter_manager),
3663 evaluator_(std::move(evaluator)) {}
3664
3665int64_t EvaluatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
3666 int64_t node, const std::vector<int64_t>& successors) {
3667 int64_t best_evaluation = std::numeric_limits<int64_t>::max();
3668 int64_t best_successor = -1;
3669 for (int64_t successor : successors) {
3670 const int64_t evaluation = (successor >= 0)
3671 ? evaluator_(node, successor)
3672 : std::numeric_limits<int64_t>::max();
3673 if (evaluation < best_evaluation ||
3674 (evaluation == best_evaluation && successor > best_successor)) {
3675 best_evaluation = evaluation;
3676 best_successor = successor;
3677 }
3678 }
3679 return best_successor;
3680}
3681
3682void EvaluatorCheapestAdditionFilteredHeuristic::SortSuccessors(
3683 int64_t node, std::vector<int64_t>* successors) {
3684 std::vector<std::pair<int64_t, int64_t>> values;
3685 values.reserve(successors->size());
3686 for (int64_t successor : *successors) {
3687 // Tie-breaking on largest node index to mimic the behavior of
3688 // CheapestValueSelector (search.cc).
3689 values.push_back({evaluator_(node, successor), successor});
3690 }
3691 absl::c_sort(values, [](const std::pair<int64_t, int64_t>& s1,
3692 const std::pair<int64_t, int64_t>& s2) {
3693 return s1.first < s2.first ||
3694 (s1.first == s2.first && s1.second > s2.second);
3695 });
3696 successors->clear();
3697 for (auto value : values) {
3698 successors->push_back(value.second);
3699 }
3700}
3701
3702// ComparatorCheapestAdditionFilteredHeuristic
3703
3706 RoutingModel* model, std::function<bool()> stop_search,
3708 LocalSearchFilterManager* filter_manager)
3709 : CheapestAdditionFilteredHeuristic(model, std::move(stop_search),
3710 filter_manager),
3711 comparator_(std::move(comparator)) {}
3712
3713int64_t ComparatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(
3714 int64_t node, const std::vector<int64_t>& successors) {
3715 return *absl::c_min_element(
3716 successors, [this, node](int successor1, int successor2) {
3717 return comparator_(node, successor1, successor2);
3718 });
3719}
3720
3721void ComparatorCheapestAdditionFilteredHeuristic::SortSuccessors(
3722 int64_t node, std::vector<int64_t>* successors) {
3723 absl::c_sort(*successors, [this, node](int successor1, int successor2) {
3724 return comparator_(node, successor1, successor2);
3725 });
3726}
3727
3728// Class storing and allowing access to the savings according to the number of
3729// vehicle types.
3730// The savings are stored and sorted in sorted_savings_per_vehicle_type_.
3731// Furthermore, when there is more than one vehicle type, the savings for a same
3732// before-->after arc are sorted in costs_and_savings_per_arc_[arc] by
3733// increasing cost(s-->before-->after-->e), where s and e are the start and end
3734// of the route, in order to make sure the arc is served by the route with the
3735// closest depot (start/end) possible.
3736// When there is only one vehicle "type" (i.e. all vehicles have the same
3737// start/end and cost class), each arc has a single saving value associated to
3738// it, so we ignore this last step to avoid unnecessary computations, and only
3739// work with sorted_savings_per_vehicle_type_[0].
3740// In case of multiple vehicle types, the best savings for each arc, i.e. the
3741// savings corresponding to the closest vehicle type, are inserted and sorted in
3742// sorted_savings_.
3743//
3744// This class also handles skipped Savings:
3745// The vectors skipped_savings_starting/ending_at_ contain all the Savings that
3746// weren't added to the model, which we want to consider for later:
3747// 1) When a Saving before-->after with both nodes uncontained cannot be used to
3748// start a new route (no more available vehicles or could not commit on any
3749// of those available).
3750// 2) When only one of the nodes of the Saving is contained but on a different
3751// vehicle type.
3752// In these cases, the Update() method is called with update_best_saving = true,
3753// which in turn calls SkipSavingForArc() (within
3754// UpdateNextAndSkippedSavingsForArcWithType()) to mark the Saving for this arc
3755// (with the correct type in the second case) as "skipped", by storing it in
3756// skipped_savings_starting_at_[before] and skipped_savings_ending_at_[after].
3757//
3758// UpdateNextAndSkippedSavingsForArcWithType() also updates the next_savings_
3759// vector, which stores the savings to go through once we've iterated through
3760// all sorted_savings_.
3761// In the first case above, where neither nodes are contained, we skip the
3762// current Saving (current_saving_), and add the next best Saving for this arc
3763// to next_savings_ (in case this skipped Saving is never considered).
3764// In the second case with a specific type, we search for the Saving with the
3765// correct type for this arc, and add it to both next_savings_ and the skipped
3766// Savings.
3767//
3768// The skipped Savings are then re-considered when one of their ends gets
3769// inserted:
3770// When another Saving other_node-->before (or after-->other_node) gets
3771// inserted, all skipped Savings in skipped_savings_starting_at_[before] (or
3772// skipped_savings_ending_at_[after]) are once again considered by calling
3773// ReinjectSkippedSavingsStartingAt() (or ReinjectSkippedSavingsEndingAt()).
3774// Then, when calling GetSaving(), we iterate through the reinjected Savings in
3775// order of insertion in the vectors while there are reinjected savings.
3776template <typename Saving>
3778 public:
3779 explicit SavingsContainer(const SavingsFilteredHeuristic* savings_db,
3780 int vehicle_types)
3781 : savings_db_(savings_db),
3782 index_in_sorted_savings_(0),
3783 vehicle_types_(vehicle_types),
3784 single_vehicle_type_(vehicle_types == 1),
3785 using_incoming_reinjected_saving_(false),
3786 sorted_(false),
3787 to_update_(true) {}
3788
3789 void InitializeContainer(int64_t size, int64_t saving_neighbors) {
3790 sorted_savings_per_vehicle_type_.clear();
3791 sorted_savings_per_vehicle_type_.resize(vehicle_types_);
3792 for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
3793 savings.reserve(size * saving_neighbors);
3794 }
3795
3796 sorted_savings_.clear();
3797 costs_and_savings_per_arc_.clear();
3798 arc_indices_per_before_node_.clear();
3799
3800 if (!single_vehicle_type_) {
3801 costs_and_savings_per_arc_.reserve(size * saving_neighbors);
3802 arc_indices_per_before_node_.resize(size);
3803 for (int before_node = 0; before_node < size; before_node++) {
3804 arc_indices_per_before_node_[before_node].reserve(saving_neighbors);
3805 }
3806 }
3807 skipped_savings_starting_at_.clear();
3808 skipped_savings_starting_at_.resize(size);
3809 skipped_savings_ending_at_.clear();
3810 skipped_savings_ending_at_.resize(size);
3811 incoming_reinjected_savings_ = nullptr;
3812 outgoing_reinjected_savings_ = nullptr;
3813 incoming_new_reinjected_savings_ = nullptr;
3814 outgoing_new_reinjected_savings_ = nullptr;
3815 }
3816
3817 void AddNewSaving(const Saving& saving, int64_t total_cost,
3818 int64_t before_node, int64_t after_node, int vehicle_type) {
3819 CHECK(!sorted_savings_per_vehicle_type_.empty())
3820 << "Container not initialized!";
3821 sorted_savings_per_vehicle_type_[vehicle_type].push_back(saving);
3822 UpdateArcIndicesCostsAndSavings(before_node, after_node,
3823 {total_cost, saving});
3824 }
3825
3826 void Sort() {
3827 CHECK(!sorted_) << "Container already sorted!";
3828
3829 for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
3830 absl::c_sort(savings);
3831 }
3832
3833 if (single_vehicle_type_) {
3834 const auto& savings = sorted_savings_per_vehicle_type_[0];
3835 sorted_savings_.resize(savings.size());
3836 absl::c_transform(savings, sorted_savings_.begin(),
3837 [](const Saving& saving) {
3838 return SavingAndArc({saving, /*arc_index*/ -1});
3839 });
3840 } else {
3841 // For each arc, sort the savings by decreasing total cost
3842 // start-->a-->b-->end.
3843 // The best saving for each arc is therefore the last of its vector.
3844 sorted_savings_.reserve(vehicle_types_ *
3845 costs_and_savings_per_arc_.size());
3846
3847 for (int arc_index = 0; arc_index < costs_and_savings_per_arc_.size();
3848 arc_index++) {
3849 std::vector<std::pair<int64_t, Saving>>& costs_and_savings =
3850 costs_and_savings_per_arc_[arc_index];
3851 DCHECK(!costs_and_savings.empty());
3852
3853 absl::c_sort(
3854 costs_and_savings,
3855 [](const std::pair<int64_t, Saving>& cs1,
3856 const std::pair<int64_t, Saving>& cs2) { return cs1 > cs2; });
3857
3858 // Insert all Savings for this arc with the lowest cost into
3859 // sorted_savings_.
3860 // TODO(user): Also do this when reiterating on next_savings_.
3861 const int64_t cost = costs_and_savings.back().first;
3862 while (!costs_and_savings.empty() &&
3863 costs_and_savings.back().first == cost) {
3864 sorted_savings_.push_back(
3865 {costs_and_savings.back().second, arc_index});
3866 costs_and_savings.pop_back();
3867 }
3868 }
3869 absl::c_sort(sorted_savings_);
3870 next_saving_type_and_index_for_arc_.clear();
3871 next_saving_type_and_index_for_arc_.resize(
3872 costs_and_savings_per_arc_.size(), {-1, -1});
3873 }
3874 sorted_ = true;
3875 index_in_sorted_savings_ = 0;
3876 to_update_ = false;
3877 }
3878
3879 bool HasSaving() {
3880 return index_in_sorted_savings_ < sorted_savings_.size() ||
3881 HasReinjectedSavings();
3882 }
3883
3885 CHECK(sorted_) << "Calling GetSaving() before Sort() !";
3886 CHECK(!to_update_)
3887 << "Update() should be called between two calls to GetSaving() !";
3888
3889 to_update_ = true;
3890
3891 if (HasReinjectedSavings()) {
3892 if (incoming_reinjected_savings_ != nullptr &&
3893 outgoing_reinjected_savings_ != nullptr) {
3894 // Get the best Saving among the two.
3895 SavingAndArc& incoming_saving = incoming_reinjected_savings_->front();
3896 SavingAndArc& outgoing_saving = outgoing_reinjected_savings_->front();
3897 if (incoming_saving < outgoing_saving) {
3898 current_saving_ = incoming_saving;
3899 using_incoming_reinjected_saving_ = true;
3900 } else {
3901 current_saving_ = outgoing_saving;
3902 using_incoming_reinjected_saving_ = false;
3903 }
3904 } else {
3905 if (incoming_reinjected_savings_ != nullptr) {
3906 current_saving_ = incoming_reinjected_savings_->front();
3907 using_incoming_reinjected_saving_ = true;
3908 }
3909 if (outgoing_reinjected_savings_ != nullptr) {
3910 current_saving_ = outgoing_reinjected_savings_->front();
3911 using_incoming_reinjected_saving_ = false;
3912 }
3913 }
3914 } else {
3915 current_saving_ = sorted_savings_[index_in_sorted_savings_];
3916 }
3917 return current_saving_.saving;
3918 }
3919
3920 void Update(bool update_best_saving, int type = -1) {
3921 CHECK(to_update_) << "Container already up to date!";
3922 if (update_best_saving) {
3923 const int64_t arc_index = current_saving_.arc_index;
3924 UpdateNextAndSkippedSavingsForArcWithType(arc_index, type);
3925 }
3926 if (!HasReinjectedSavings()) {
3927 index_in_sorted_savings_++;
3928
3929 if (index_in_sorted_savings_ == sorted_savings_.size()) {
3930 sorted_savings_.swap(next_savings_);
3931 gtl::STLClearObject(&next_savings_);
3932 index_in_sorted_savings_ = 0;
3933
3934 absl::c_sort(sorted_savings_);
3935 next_saving_type_and_index_for_arc_.clear();
3936 next_saving_type_and_index_for_arc_.resize(
3937 costs_and_savings_per_arc_.size(), {-1, -1});
3938 }
3939 }
3940 UpdateReinjectedSavings();
3941 to_update_ = false;
3942 }
3943
3944 void UpdateWithType(int type) {
3945 CHECK(!single_vehicle_type_);
3946 Update(/*update_best_saving*/ true, type);
3947 }
3948
3949 const std::vector<Saving>& GetSortedSavingsForVehicleType(int type) {
3950 CHECK(sorted_) << "Savings not sorted yet!";
3951 CHECK_LT(type, vehicle_types_);
3952 return sorted_savings_per_vehicle_type_[type];
3953 }
3954
3956 CHECK(outgoing_new_reinjected_savings_ == nullptr);
3957 outgoing_new_reinjected_savings_ = &(skipped_savings_starting_at_[node]);
3958 }
3959
3961 CHECK(incoming_new_reinjected_savings_ == nullptr);
3962 incoming_new_reinjected_savings_ = &(skipped_savings_ending_at_[node]);
3963 }
3964
3965 private:
3966 struct SavingAndArc {
3967 Saving saving;
3968 int64_t arc_index;
3969
3970 bool operator<(const SavingAndArc& other) const {
3971 return std::tie(saving, arc_index) <
3972 std::tie(other.saving, other.arc_index);
3973 }
3974 };
3975
3976 // Skips the Saving for the arc before_node-->after_node, by adding it to the
3977 // skipped_savings_ vector of the nodes, if they're uncontained.
3978 void SkipSavingForArc(const SavingAndArc& saving_and_arc) {
3979 const Saving& saving = saving_and_arc.saving;
3980 const int64_t before_node = saving.before_node;
3981 const int64_t after_node = saving.after_node;
3982 if (!savings_db_->Contains(before_node)) {
3983 skipped_savings_starting_at_[before_node].push_back(saving_and_arc);
3984 }
3985 if (!savings_db_->Contains(after_node)) {
3986 skipped_savings_ending_at_[after_node].push_back(saving_and_arc);
3987 }
3988 }
3989
3990 // Called within Update() when update_best_saving is true, this method updates
3991 // the next_savings_ and skipped savings vectors for a given arc_index and
3992 // vehicle type.
3993 // When a Saving with the right type has already been added to next_savings_
3994 // for this arc, no action is needed on next_savings_.
3995 // Otherwise, if such a Saving exists, GetNextSavingForArcWithType() will find
3996 // and assign it to next_saving, which is then used to update next_savings_.
3997 // Finally, the right Saving is skipped for this arc: if looking for a
3998 // specific type (i.e. type != -1), next_saving (which has the correct type)
3999 // is skipped, otherwise the current_saving_ is.
4000 void UpdateNextAndSkippedSavingsForArcWithType(int64_t arc_index, int type) {
4001 if (single_vehicle_type_) {
4002 // No next Saving, skip the current Saving.
4003 CHECK_EQ(type, -1);
4004 SkipSavingForArc(current_saving_);
4005 return;
4006 }
4007 CHECK_GE(arc_index, 0);
4008 auto& type_and_index = next_saving_type_and_index_for_arc_[arc_index];
4009 const int previous_index = type_and_index.second;
4010 const int previous_type = type_and_index.first;
4011 bool next_saving_added = false;
4012 Saving next_saving;
4013
4014 if (previous_index >= 0) {
4015 // Next Saving already added for this arc.
4016 DCHECK_GE(previous_type, 0);
4017 if (type == -1 || previous_type == type) {
4018 // Not looking for a specific type, or correct type already in
4019 // next_savings_.
4020 next_saving_added = true;
4021 next_saving = next_savings_[previous_index].saving;
4022 }
4023 }
4024
4025 if (!next_saving_added &&
4026 GetNextSavingForArcWithType(arc_index, type, &next_saving)) {
4027 type_and_index.first = next_saving.vehicle_type;
4028 if (previous_index >= 0) {
4029 // Update the previous saving.
4030 next_savings_[previous_index] = {next_saving, arc_index};
4031 } else {
4032 // Insert the new next Saving for this arc.
4033 type_and_index.second = next_savings_.size();
4034 next_savings_.push_back({next_saving, arc_index});
4035 }
4036 next_saving_added = true;
4037 }
4038
4039 // Skip the Saving based on the vehicle type.
4040 if (type == -1) {
4041 // Skip the current Saving.
4042 SkipSavingForArc(current_saving_);
4043 } else {
4044 // Skip the Saving with the correct type, already added to next_savings_
4045 // if it was found.
4046 if (next_saving_added) {
4047 SkipSavingForArc({next_saving, arc_index});
4048 }
4049 }
4050 }
4051
4052 void UpdateReinjectedSavings() {
4053 UpdateGivenReinjectedSavings(incoming_new_reinjected_savings_,
4054 &incoming_reinjected_savings_,
4055 using_incoming_reinjected_saving_);
4056 UpdateGivenReinjectedSavings(outgoing_new_reinjected_savings_,
4057 &outgoing_reinjected_savings_,
4058 !using_incoming_reinjected_saving_);
4059 incoming_new_reinjected_savings_ = nullptr;
4060 outgoing_new_reinjected_savings_ = nullptr;
4061 }
4062
4063 void UpdateGivenReinjectedSavings(
4064 std::deque<SavingAndArc>* new_reinjected_savings,
4065 std::deque<SavingAndArc>** reinjected_savings,
4066 bool using_reinjected_savings) {
4067 if (new_reinjected_savings == nullptr) {
4068 // No new reinjected savings, update the previous ones if needed.
4069 if (*reinjected_savings != nullptr && using_reinjected_savings) {
4070 CHECK(!(*reinjected_savings)->empty());
4071 (*reinjected_savings)->pop_front();
4072 if ((*reinjected_savings)->empty()) {
4073 *reinjected_savings = nullptr;
4074 }
4075 }
4076 return;
4077 }
4078
4079 // New savings reinjected.
4080 // Forget about the previous reinjected savings and add the new ones if
4081 // there are any.
4082 if (*reinjected_savings != nullptr) {
4083 (*reinjected_savings)->clear();
4084 }
4085 *reinjected_savings = nullptr;
4086 if (!new_reinjected_savings->empty()) {
4087 *reinjected_savings = new_reinjected_savings;
4088 }
4089 }
4090
4091 bool HasReinjectedSavings() {
4092 return outgoing_reinjected_savings_ != nullptr ||
4093 incoming_reinjected_savings_ != nullptr;
4094 }
4095
4096 void UpdateArcIndicesCostsAndSavings(
4097 int64_t before_node, int64_t after_node,
4098 const std::pair<int64_t, Saving>& cost_and_saving) {
4099 if (single_vehicle_type_) {
4100 return;
4101 }
4102 absl::flat_hash_map<int, int>& arc_indices =
4103 arc_indices_per_before_node_[before_node];
4104 const auto& arc_inserted = arc_indices.insert(
4105 std::make_pair(after_node, costs_and_savings_per_arc_.size()));
4106 const int index = arc_inserted.first->second;
4107 if (arc_inserted.second) {
4108 costs_and_savings_per_arc_.push_back({cost_and_saving});
4109 } else {
4110 DCHECK_LT(index, costs_and_savings_per_arc_.size());
4111 costs_and_savings_per_arc_[index].push_back(cost_and_saving);
4112 }
4113 }
4114
4115 bool GetNextSavingForArcWithType(int64_t arc_index, int type,
4116 Saving* next_saving) {
4117 std::vector<std::pair<int64_t, Saving>>& costs_and_savings =
4118 costs_and_savings_per_arc_[arc_index];
4119
4120 bool found_saving = false;
4121 while (!costs_and_savings.empty() && !found_saving) {
4122 const Saving& saving = costs_and_savings.back().second;
4123 if (type == -1 || saving.vehicle_type == type) {
4124 *next_saving = saving;
4125 found_saving = true;
4126 }
4127 costs_and_savings.pop_back();
4128 }
4129 return found_saving;
4130 }
4131
4132 const SavingsFilteredHeuristic* const savings_db_;
4133 int64_t index_in_sorted_savings_;
4134 std::vector<std::vector<Saving>> sorted_savings_per_vehicle_type_;
4135 std::vector<SavingAndArc> sorted_savings_;
4136 std::vector<SavingAndArc> next_savings_;
4137 std::vector<std::pair</*type*/ int, /*index*/ int>>
4138 next_saving_type_and_index_for_arc_;
4139 SavingAndArc current_saving_;
4140 std::vector<std::vector<std::pair</*cost*/ int64_t, Saving>>>
4141 costs_and_savings_per_arc_;
4142 std::vector<absl::flat_hash_map</*after_node*/ int, /*arc_index*/ int>>
4143 arc_indices_per_before_node_;
4144 std::vector<std::deque<SavingAndArc>> skipped_savings_starting_at_;
4145 std::vector<std::deque<SavingAndArc>> skipped_savings_ending_at_;
4146 std::deque<SavingAndArc>* outgoing_reinjected_savings_;
4147 std::deque<SavingAndArc>* incoming_reinjected_savings_;
4148 std::deque<SavingAndArc>* outgoing_new_reinjected_savings_;
4149 std::deque<SavingAndArc>* incoming_new_reinjected_savings_;
4150 const int vehicle_types_;
4151 const bool single_vehicle_type_;
4152 bool using_incoming_reinjected_saving_;
4153 bool sorted_;
4154 bool to_update_;
4155};
4156
4157// SavingsFilteredHeuristic
4158
4160 RoutingModel* model, std::function<bool()> stop_search,
4161 SavingsParameters parameters, LocalSearchFilterManager* filter_manager)
4162 : RoutingFilteredHeuristic(model, std::move(stop_search), filter_manager),
4163 vehicle_type_curator_(nullptr),
4164 savings_params_(parameters) {
4165 DCHECK_GT(savings_params_.neighbors_ratio, 0);
4166 DCHECK_LE(savings_params_.neighbors_ratio, 1);
4167 DCHECK_GT(savings_params_.max_memory_usage_bytes, 0);
4168 DCHECK_GT(savings_params_.arc_coefficient, 0);
4169}
4170
4172
4174 if (vehicle_type_curator_ == nullptr) {
4175 vehicle_type_curator_ = std::make_unique<VehicleTypeCurator>(
4176 model()->GetVehicleTypeContainer());
4177 }
4178 // Only store empty vehicles in the vehicle_type_curator_.
4179 vehicle_type_curator_->Reset(
4180 [this](int vehicle) { return VehicleIsEmpty(vehicle); });
4181 if (!ComputeSavings()) return false;
4183 // Free all the space used to store the Savings in the container.
4184 savings_container_.reset();
4187 if (!Evaluate(/*commit=*/true).has_value()) return false;
4189 return Evaluate(/*commit=*/true).has_value();
4190}
4191
4193 int type, int64_t before_node, int64_t after_node) {
4194 auto vehicle_is_compatible = [this, before_node, after_node](int vehicle) {
4195 if (!model()->VehicleVar(before_node)->Contains(vehicle) ||
4196 !model()->VehicleVar(after_node)->Contains(vehicle)) {
4197 return false;
4198 }
4199 // Try to commit the arc on this vehicle.
4200 DCHECK(VehicleIsEmpty(vehicle));
4201 SetNext(model()->Start(vehicle), before_node, vehicle);
4202 SetNext(before_node, after_node, vehicle);
4203 SetNext(after_node, model()->End(vehicle), vehicle);
4204 return Evaluate(/*commit=*/true).has_value();
4205 };
4206
4208 ->GetCompatibleVehicleOfType(
4209 type, vehicle_is_compatible,
4210 /*stop_and_return_vehicle*/ [](int) { return false; })
4211 .first;
4212}
4213
4214void SavingsFilteredHeuristic::AddSymmetricArcsToAdjacencyLists(
4215 std::vector<std::vector<int64_t>>* adjacency_lists) {
4216 for (int64_t node = 0; node < adjacency_lists->size(); node++) {
4217 for (int64_t neighbor : (*adjacency_lists)[node]) {
4218 if (model()->IsStart(neighbor) || model()->IsEnd(neighbor)) {
4219 continue;
4220 }
4221 (*adjacency_lists)[neighbor].push_back(node);
4222 }
4223 }
4224 absl::c_transform(*adjacency_lists, adjacency_lists->begin(),
4225 [](std::vector<int64_t> vec) {
4226 absl::c_sort(vec);
4227 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
4228 return vec;
4229 });
4230}
4231
4232// Computes the savings related to each pair of non-start and non-end nodes.
4233// The savings value for an arc a-->b for a vehicle starting at node s and
4234// ending at node e is:
4235// saving = cost(s-->a-->e) + cost(s-->b-->e) - cost(s-->a-->b-->e), i.e.
4236// saving = cost(a-->e) + cost(s-->b) - cost(a-->b)
4237// The saving value also considers a coefficient for the cost of the arc
4238// a-->b, which results in:
4239// saving = cost(a-->e) + cost(s-->b) - [arc_coefficient_ * cost(a-->b)]
4240// The higher this saving value, the better the arc.
4241// Here, the value stored for the savings is -saving, which are therefore
4242// considered in decreasing order.
4243bool SavingsFilteredHeuristic::ComputeSavings() {
4244 const int num_vehicle_types = vehicle_type_curator_->NumTypes();
4245 const int size = model()->Size();
4246
4247 std::vector<int64_t> uncontained_non_start_end_nodes;
4248 uncontained_non_start_end_nodes.reserve(size);
4249 for (int node = 0; node < size; node++) {
4250 if (!model()->IsStart(node) && !model()->IsEnd(node) && !Contains(node)) {
4251 uncontained_non_start_end_nodes.push_back(node);
4252 }
4253 }
4254
4255 const int64_t saving_neighbors =
4256 std::min(MaxNumNeighborsPerNode(num_vehicle_types),
4257 static_cast<int64_t>(uncontained_non_start_end_nodes.size()));
4258
4260 std::make_unique<SavingsContainer<Saving>>(this, num_vehicle_types);
4261 savings_container_->InitializeContainer(size, saving_neighbors);
4262 if (StopSearch()) return false;
4263 std::vector<std::vector<int64_t>> adjacency_lists(size);
4264
4265 for (int type = 0; type < num_vehicle_types; ++type) {
4266 const int vehicle =
4267 vehicle_type_curator_->GetLowestFixedCostVehicleOfType(type);
4268 if (vehicle < 0) continue;
4269
4270 const int64_t cost_class =
4271 model()->GetCostClassIndexOfVehicle(vehicle).value();
4272 const int64_t start = model()->Start(vehicle);
4273 const int64_t end = model()->End(vehicle);
4274 const int64_t fixed_cost = model()->GetFixedCostOfVehicle(vehicle);
4275
4276 // Compute the neighbors for each non-start/end node not already inserted in
4277 // the model.
4278 for (int before_node : uncontained_non_start_end_nodes) {
4279 std::vector<std::pair</*cost*/ int64_t, /*node*/ int64_t>>
4280 costed_after_nodes;
4281 costed_after_nodes.reserve(uncontained_non_start_end_nodes.size());
4282 if (StopSearch()) return false;
4283 for (int after_node : uncontained_non_start_end_nodes) {
4284 if (after_node != before_node) {
4285 costed_after_nodes.push_back(std::make_pair(
4286 model()->GetArcCostForClass(before_node, after_node, cost_class),
4287 after_node));
4288 }
4289 }
4290 if (saving_neighbors < costed_after_nodes.size()) {
4291 std::nth_element(costed_after_nodes.begin(),
4292 costed_after_nodes.begin() + saving_neighbors,
4293 costed_after_nodes.end());
4294 costed_after_nodes.resize(saving_neighbors);
4295 }
4296 adjacency_lists[before_node].resize(costed_after_nodes.size());
4297 std::transform(costed_after_nodes.begin(), costed_after_nodes.end(),
4298 adjacency_lists[before_node].begin(),
4299 [](std::pair<int64_t, int64_t> cost_and_node) {
4300 return cost_and_node.second;
4301 });
4302 }
4303 if (savings_params_.add_reverse_arcs) {
4304 AddSymmetricArcsToAdjacencyLists(&adjacency_lists);
4305 }
4306 if (StopSearch()) return false;
4307
4308 // Build the savings for this vehicle type given the adjacency_lists.
4309 for (int before_node : uncontained_non_start_end_nodes) {
4310 const int64_t before_to_end_cost =
4311 model()->GetArcCostForClass(before_node, end, cost_class);
4312 const int64_t start_to_before_cost =
4313 CapSub(model()->GetArcCostForClass(start, before_node, cost_class),
4314 fixed_cost);
4315 if (StopSearch()) return false;
4316 for (int64_t after_node : adjacency_lists[before_node]) {
4317 if (model()->IsStart(after_node) || model()->IsEnd(after_node) ||
4318 before_node == after_node || Contains(after_node)) {
4319 continue;
4320 }
4321 const int64_t arc_cost =
4322 model()->GetArcCostForClass(before_node, after_node, cost_class);
4323 const int64_t start_to_after_cost =
4324 CapSub(model()->GetArcCostForClass(start, after_node, cost_class),
4325 fixed_cost);
4326 const int64_t after_to_end_cost =
4327 model()->GetArcCostForClass(after_node, end, cost_class);
4328
4329 const double weighted_arc_cost_fp =
4330 savings_params_.arc_coefficient * arc_cost;
4331 const int64_t weighted_arc_cost =
4332 weighted_arc_cost_fp < std::numeric_limits<int64_t>::max()
4333 ? static_cast<int64_t>(weighted_arc_cost_fp)
4334 : std::numeric_limits<int64_t>::max();
4335 const int64_t saving_value = CapSub(
4336 CapAdd(before_to_end_cost, start_to_after_cost), weighted_arc_cost);
4337
4338 const Saving saving =
4339 BuildSaving(-saving_value, type, before_node, after_node);
4340
4341 const int64_t total_cost =
4342 CapAdd(CapAdd(start_to_before_cost, arc_cost), after_to_end_cost);
4343
4344 savings_container_->AddNewSaving(saving, total_cost, before_node,
4345 after_node, type);
4346 }
4347 }
4348 }
4349 savings_container_->Sort();
4350 return !StopSearch();
4351}
4352
4353int64_t SavingsFilteredHeuristic::MaxNumNeighborsPerNode(
4354 int num_vehicle_types) const {
4355 const int64_t size = model()->Size();
4356
4357 const int64_t num_neighbors_with_ratio =
4358 std::max(1.0, size * savings_params_.neighbors_ratio);
4359
4360 // A single Saving takes 2*8 bytes of memory.
4361 // max_memory_usage_in_savings_unit = num_savings * multiplicative_factor,
4362 // Where multiplicative_factor is the memory taken (in Savings unit) for each
4363 // computed Saving.
4364 const double max_memory_usage_in_savings_unit =
4365 savings_params_.max_memory_usage_bytes / 16;
4366
4367 // In the SavingsContainer, for each Saving, the Savings are stored:
4368 // - Once in "sorted_savings_per_vehicle_type", and (at most) once in
4369 // "sorted_savings_" --> factor 2
4370 // - If num_vehicle_types > 1, they're also stored by arc_index in
4371 // "costs_and_savings_per_arc", along with their int64_t cost --> factor 1.5
4372 //
4373 // On top of that,
4374 // - In the sequential version, the Saving* are also stored by in-coming and
4375 // outgoing node (in in/out_savings_ptr), adding another 2*8 bytes per
4376 // Saving --> factor 1.
4377 // - In the parallel version, skipped Savings are also stored in
4378 // skipped_savings_starting/ending_at_, resulting in a maximum added factor
4379 // of 2 for each Saving.
4380 // These extra factors are given by ExtraSavingsMemoryMultiplicativeFactor().
4381 double multiplicative_factor = 2.0 + ExtraSavingsMemoryMultiplicativeFactor();
4382 if (num_vehicle_types > 1) {
4383 multiplicative_factor += 1.5;
4384 }
4385 const double num_savings =
4386 max_memory_usage_in_savings_unit / multiplicative_factor;
4387 const int64_t num_neighbors_with_memory_restriction =
4388 std::max(1.0, num_savings / (num_vehicle_types * size));
4389
4390 return std::min(num_neighbors_with_ratio,
4391 num_neighbors_with_memory_restriction);
4392}
4393
4394// SequentialSavingsFilteredHeuristic
4395
4397 const int vehicle_types = vehicle_type_curator_->NumTypes();
4398 DCHECK_GT(vehicle_types, 0);
4399 const int size = model()->Size();
4400 // Store savings for each incoming and outgoing node and by vehicle type. This
4401 // is necessary to quickly extend partial chains without scanning all savings.
4402 std::vector<std::vector<const Saving*>> in_savings_ptr(size * vehicle_types);
4403 std::vector<std::vector<const Saving*>> out_savings_ptr(size * vehicle_types);
4404 for (int type = 0; type < vehicle_types; type++) {
4405 const int vehicle_type_offset = type * size;
4406 const std::vector<Saving>& sorted_savings_for_type =
4407 savings_container_->GetSortedSavingsForVehicleType(type);
4408 for (const Saving& saving : sorted_savings_for_type) {
4409 DCHECK_EQ(saving.vehicle_type, type);
4410 const int before_node = saving.before_node;
4411 in_savings_ptr[vehicle_type_offset + before_node].push_back(&saving);
4412 const int after_node = saving.after_node;
4413 out_savings_ptr[vehicle_type_offset + after_node].push_back(&saving);
4414 }
4415 }
4416
4417 // Build routes from savings.
4418 while (savings_container_->HasSaving()) {
4419 if (StopSearch()) return;
4420 // First find the best saving to start a new route.
4421 const Saving saving = savings_container_->GetSaving();
4422 int before_node = saving.before_node;
4423 int after_node = saving.after_node;
4424 const bool nodes_contained = Contains(before_node) || Contains(after_node);
4425
4426 if (nodes_contained) {
4427 savings_container_->Update(false);
4428 continue;
4429 }
4430
4431 // Find the right vehicle to start the route with this Saving.
4432 const int type = saving.vehicle_type;
4433 const int vehicle =
4434 StartNewRouteWithBestVehicleOfType(type, before_node, after_node);
4435 if (vehicle < 0) {
4436 savings_container_->Update(true);
4437 continue;
4438 }
4439
4440 const int64_t start = model()->Start(vehicle);
4441 const int64_t end = model()->End(vehicle);
4442 // Then extend the route from both ends of the partial route.
4443 int in_index = 0;
4444 int out_index = 0;
4445 const int saving_offset = type * size;
4446
4447 while (in_index < in_savings_ptr[saving_offset + after_node].size() ||
4448 out_index < out_savings_ptr[saving_offset + before_node].size()) {
4449 if (StopSearch()) return;
4450 // First determine how to extend the route.
4451 int before_before_node = -1;
4452 int after_after_node = -1;
4453 if (in_index < in_savings_ptr[saving_offset + after_node].size()) {
4454 const Saving& in_saving =
4455 *(in_savings_ptr[saving_offset + after_node][in_index]);
4456 if (out_index < out_savings_ptr[saving_offset + before_node].size()) {
4457 const Saving& out_saving =
4458 *(out_savings_ptr[saving_offset + before_node][out_index]);
4459 if (in_saving.saving < out_saving.saving) {
4460 after_after_node = in_saving.after_node;
4461 } else {
4462 before_before_node = out_saving.before_node;
4463 }
4464 } else {
4465 after_after_node = in_saving.after_node;
4466 }
4467 } else {
4468 before_before_node =
4469 out_savings_ptr[saving_offset + before_node][out_index]
4470 ->before_node;
4471 }
4472 // Extend the route
4473 if (after_after_node != -1) {
4474 DCHECK_EQ(before_before_node, -1);
4475 ++in_index;
4476 // Extending after after_node
4477 if (!Contains(after_after_node)) {
4478 SetNext(after_node, after_after_node, vehicle);
4479 SetNext(after_after_node, end, vehicle);
4480 if (Evaluate(/*commit=*/true).has_value()) {
4481 in_index = 0;
4482 after_node = after_after_node;
4483 }
4484 }
4485 } else {
4486 // Extending before before_node
4487 CHECK_GE(before_before_node, 0);
4488 ++out_index;
4489 if (!Contains(before_before_node)) {
4490 SetNext(start, before_before_node, vehicle);
4491 SetNext(before_before_node, before_node, vehicle);
4492 if (Evaluate(/*commit=*/true).has_value()) {
4493 out_index = 0;
4494 before_node = before_before_node;
4495 }
4496 }
4497 }
4498 }
4499 savings_container_->Update(false);
4500 }
4501}
4502
4503// ParallelSavingsFilteredHeuristic
4504
4506 // Initialize the vehicles of the first/last non start/end nodes served by
4507 // each route.
4508 const int64_t size = model()->Size();
4509 const int vehicles = model()->vehicles();
4510
4511 first_node_on_route_.resize(vehicles, -1);
4512 last_node_on_route_.resize(vehicles, -1);
4513 vehicle_of_first_or_last_node_.resize(size, -1);
4514
4515 for (int vehicle = 0; vehicle < vehicles; vehicle++) {
4516 const int64_t start = model()->Start(vehicle);
4517 const int64_t end = model()->End(vehicle);
4518 if (!Contains(start)) {
4519 continue;
4520 }
4521 int64_t node = Value(start);
4522 if (node != end) {
4523 vehicle_of_first_or_last_node_[node] = vehicle;
4524 first_node_on_route_[vehicle] = node;
4525
4526 int64_t next = Value(node);
4527 while (next != end) {
4528 node = next;
4529 next = Value(node);
4530 }
4531 vehicle_of_first_or_last_node_[node] = vehicle;
4532 last_node_on_route_[vehicle] = node;
4533 }
4534 }
4535
4536 while (savings_container_->HasSaving()) {
4537 if (StopSearch()) return;
4538 const Saving saving = savings_container_->GetSaving();
4539 const int64_t before_node = saving.before_node;
4540 const int64_t after_node = saving.after_node;
4541 const int type = saving.vehicle_type;
4542
4543 if (!Contains(before_node) && !Contains(after_node)) {
4544 // Neither nodes are contained, start a new route.
4545 bool committed = false;
4546
4547 const int vehicle =
4548 StartNewRouteWithBestVehicleOfType(type, before_node, after_node);
4549
4550 if (vehicle >= 0) {
4551 committed = true;
4552 // Store before_node and after_node as first and last nodes of the route
4553 vehicle_of_first_or_last_node_[before_node] = vehicle;
4554 vehicle_of_first_or_last_node_[after_node] = vehicle;
4555 first_node_on_route_[vehicle] = before_node;
4556 last_node_on_route_[vehicle] = after_node;
4557 savings_container_->ReinjectSkippedSavingsStartingAt(after_node);
4558 savings_container_->ReinjectSkippedSavingsEndingAt(before_node);
4559 }
4560 savings_container_->Update(!committed);
4561 continue;
4562 }
4563
4564 if (Contains(before_node) && Contains(after_node)) {
4565 // Merge the two routes if before_node is last and after_node first of its
4566 // route, the two nodes aren't already on the same route, and the vehicle
4567 // types are compatible.
4568 const int v1 = vehicle_of_first_or_last_node_[before_node];
4569 const int64_t last_node = v1 == -1 ? -1 : last_node_on_route_[v1];
4570
4571 const int v2 = vehicle_of_first_or_last_node_[after_node];
4572 const int64_t first_node = v2 == -1 ? -1 : first_node_on_route_[v2];
4573
4574 if (before_node == last_node && after_node == first_node && v1 != v2 &&
4575 vehicle_type_curator_->Type(v1) == vehicle_type_curator_->Type(v2)) {
4576 CHECK_EQ(Value(before_node), model()->End(v1));
4577 CHECK_EQ(Value(model()->Start(v2)), after_node);
4578
4579 // We try merging the two routes.
4580 // TODO(user): Try to use skipped savings to start new routes when
4581 // a vehicle becomes available after a merge (not trivial because it can
4582 // result in an infinite loop).
4583 MergeRoutes(v1, v2, before_node, after_node);
4584 }
4585 }
4586
4587 if (Contains(before_node) && !Contains(after_node)) {
4588 const int vehicle = vehicle_of_first_or_last_node_[before_node];
4589 const int64_t last_node =
4590 vehicle == -1 ? -1 : last_node_on_route_[vehicle];
4591
4592 if (before_node == last_node) {
4593 const int64_t end = model()->End(vehicle);
4594 CHECK_EQ(Value(before_node), end);
4595
4596 const int route_type = vehicle_type_curator_->Type(vehicle);
4597 if (type != route_type) {
4598 // The saving doesn't correspond to the type of the vehicle serving
4599 // before_node. We update the container with the correct type.
4600 savings_container_->UpdateWithType(route_type);
4601 continue;
4602 }
4603
4604 // Try adding after_node on route of before_node.
4605 SetNext(before_node, after_node, vehicle);
4606 SetNext(after_node, end, vehicle);
4607 if (Evaluate(/*commit=*/true).has_value()) {
4608 if (first_node_on_route_[vehicle] != before_node) {
4609 // before_node is no longer the start or end of its route
4610 DCHECK_NE(Value(model()->Start(vehicle)), before_node);
4611 vehicle_of_first_or_last_node_[before_node] = -1;
4612 }
4613 vehicle_of_first_or_last_node_[after_node] = vehicle;
4614 last_node_on_route_[vehicle] = after_node;
4615 savings_container_->ReinjectSkippedSavingsStartingAt(after_node);
4616 }
4617 }
4618 }
4619
4620 if (!Contains(before_node) && Contains(after_node)) {
4621 const int vehicle = vehicle_of_first_or_last_node_[after_node];
4622 const int64_t first_node =
4623 vehicle == -1 ? -1 : first_node_on_route_[vehicle];
4624
4625 if (after_node == first_node) {
4626 const int64_t start = model()->Start(vehicle);
4627 CHECK_EQ(Value(start), after_node);
4628
4629 const int route_type = vehicle_type_curator_->Type(vehicle);
4630 if (type != route_type) {
4631 // The saving doesn't correspond to the type of the vehicle serving
4632 // after_node. We update the container with the correct type.
4633 savings_container_->UpdateWithType(route_type);
4634 continue;
4635 }
4636
4637 // Try adding before_node on route of after_node.
4638 SetNext(before_node, after_node, vehicle);
4639 SetNext(start, before_node, vehicle);
4640 if (Evaluate(/*commit=*/true).has_value()) {
4641 if (last_node_on_route_[vehicle] != after_node) {
4642 // after_node is no longer the start or end of its route
4643 DCHECK_NE(Value(after_node), model()->End(vehicle));
4644 vehicle_of_first_or_last_node_[after_node] = -1;
4645 }
4646 vehicle_of_first_or_last_node_[before_node] = vehicle;
4647 first_node_on_route_[vehicle] = before_node;
4648 savings_container_->ReinjectSkippedSavingsEndingAt(before_node);
4649 }
4650 }
4651 }
4652 savings_container_->Update(/*update_best_saving*/ false);
4653 }
4654}
4655
4656void ParallelSavingsFilteredHeuristic::MergeRoutes(int first_vehicle,
4657 int second_vehicle,
4658 int64_t before_node,
4659 int64_t after_node) {
4660 if (StopSearch()) return;
4661 const int64_t new_first_node = first_node_on_route_[first_vehicle];
4662 DCHECK_EQ(vehicle_of_first_or_last_node_[new_first_node], first_vehicle);
4663 CHECK_EQ(Value(model()->Start(first_vehicle)), new_first_node);
4664 const int64_t new_last_node = last_node_on_route_[second_vehicle];
4665 DCHECK_EQ(vehicle_of_first_or_last_node_[new_last_node], second_vehicle);
4666 CHECK_EQ(Value(new_last_node), model()->End(second_vehicle));
4667
4668 // Select the vehicle with lower fixed cost to merge the routes.
4669 int used_vehicle = first_vehicle;
4670 int unused_vehicle = second_vehicle;
4671 if (model()->GetFixedCostOfVehicle(first_vehicle) >
4672 model()->GetFixedCostOfVehicle(second_vehicle)) {
4673 used_vehicle = second_vehicle;
4674 unused_vehicle = first_vehicle;
4675 }
4676
4677 SetNext(before_node, after_node, used_vehicle);
4678 SetNext(model()->Start(unused_vehicle), model()->End(unused_vehicle),
4679 unused_vehicle);
4680 if (used_vehicle == first_vehicle) {
4681 SetNext(new_last_node, model()->End(used_vehicle), used_vehicle);
4682 } else {
4683 SetNext(model()->Start(used_vehicle), new_first_node, used_vehicle);
4684 }
4685 bool committed = Evaluate(/*commit=*/true).has_value();
4686 if (!committed &&
4687 model()->GetVehicleClassIndexOfVehicle(first_vehicle).value() !=
4688 model()->GetVehicleClassIndexOfVehicle(second_vehicle).value()) {
4689 // Try committing on other vehicle instead.
4690 std::swap(used_vehicle, unused_vehicle);
4691 SetNext(before_node, after_node, used_vehicle);
4692 SetNext(model()->Start(unused_vehicle), model()->End(unused_vehicle),
4693 unused_vehicle);
4694 if (used_vehicle == first_vehicle) {
4695 SetNext(new_last_node, model()->End(used_vehicle), used_vehicle);
4696 } else {
4697 SetNext(model()->Start(used_vehicle), new_first_node, used_vehicle);
4698 }
4699 committed = Evaluate(/*commit=*/true).has_value();
4700 }
4701 if (committed) {
4702 // Make unused_vehicle available
4703 vehicle_type_curator_->ReinjectVehicleOfClass(
4704 unused_vehicle,
4705 model()->GetVehicleClassIndexOfVehicle(unused_vehicle).value(),
4706 model()->GetFixedCostOfVehicle(unused_vehicle));
4707
4708 // Update the first and last nodes on vehicles.
4709 first_node_on_route_[unused_vehicle] = -1;
4710 last_node_on_route_[unused_vehicle] = -1;
4711 vehicle_of_first_or_last_node_[before_node] = -1;
4712 vehicle_of_first_or_last_node_[after_node] = -1;
4713 first_node_on_route_[used_vehicle] = new_first_node;
4714 last_node_on_route_[used_vehicle] = new_last_node;
4715 vehicle_of_first_or_last_node_[new_last_node] = used_vehicle;
4716 vehicle_of_first_or_last_node_[new_first_node] = used_vehicle;
4717 }
4718}
4719
4720// ChristofidesFilteredHeuristic
4721
4723 RoutingModel* model, std::function<bool()> stop_search,
4724 LocalSearchFilterManager* filter_manager, bool use_minimum_matching)
4725 : RoutingFilteredHeuristic(model, std::move(stop_search), filter_manager),
4726 use_minimum_matching_(use_minimum_matching) {}
4727
4728// TODO(user): Support pickup & delivery.
4730 const int size = model()->Size() - model()->vehicles() + 1;
4731 // Node indices for Christofides solver.
4732 // 0: start/end node
4733 // >0: non start/end nodes
4734 // TODO(user): Add robustness to fixed arcs by collapsing them into meta-
4735 // nodes.
4736 std::vector<int> indices(1, 0);
4737 for (int i = 1; i < size; ++i) {
4738 if (!model()->IsStart(i) && !model()->IsEnd(i)) {
4739 indices.push_back(i);
4740 }
4741 }
4742 const int num_cost_classes = model()->GetCostClassesCount();
4743 std::vector<std::vector<int>> path_per_cost_class(num_cost_classes);
4744 std::vector<bool> class_covered(num_cost_classes, false);
4745 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
4746 const int64_t cost_class =
4747 model()->GetCostClassIndexOfVehicle(vehicle).value();
4748 if (!class_covered[cost_class]) {
4749 class_covered[cost_class] = true;
4750 const int64_t start = model()->Start(vehicle);
4751 const int64_t end = model()->End(vehicle);
4752 auto cost = [this, &indices, start, end, cost_class](int from, int to) {
4753 DCHECK_LT(from, indices.size());
4754 DCHECK_LT(to, indices.size());
4755 const int from_index = (from == 0) ? start : indices[from];
4756 const int to_index = (to == 0) ? end : indices[to];
4757 const int64_t cost =
4758 model()->GetArcCostForClass(from_index, to_index, cost_class);
4759 // To avoid overflow issues, capping costs at kint64max/2, the maximum
4760 // value supported by MinCostPerfectMatching.
4761 // TODO(user): Investigate if ChristofidesPathSolver should not
4762 // return a status to bail out fast in case of problem.
4763 return std::min(cost, std::numeric_limits<int64_t>::max() / 2);
4764 };
4765 using Cost = decltype(cost);
4767 indices.size(), cost);
4768 if (use_minimum_matching_) {
4769 christofides_solver.SetMatchingAlgorithm(
4771 MatchingAlgorithm::MINIMUM_WEIGHT_MATCHING);
4772 }
4773 if (christofides_solver.Solve()) {
4774 path_per_cost_class[cost_class] =
4775 christofides_solver.TravelingSalesmanPath();
4776 }
4777 }
4778 }
4779 // TODO(user): Investigate if sorting paths per cost improves solutions.
4780 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {
4781 const int64_t cost_class =
4782 model()->GetCostClassIndexOfVehicle(vehicle).value();
4783 const std::vector<int>& path = path_per_cost_class[cost_class];
4784 if (path.empty()) continue;
4785 DCHECK_EQ(0, path[0]);
4786 DCHECK_EQ(0, path.back());
4787 // Extend route from start.
4788 int prev = GetStartChainEnd(vehicle);
4789 const int end = model()->End(vehicle);
4790 for (int i = 1; i < path.size() - 1 && prev != end; ++i) {
4791 if (StopSearch()) return false;
4792 int next = indices[path[i]];
4793 if (!Contains(next)) {
4794 SetNext(prev, next, vehicle);
4795 SetNext(next, end, vehicle);
4796 if (Evaluate(/*commit=*/true).has_value()) {
4797 prev = next;
4798 }
4799 }
4800 }
4801 }
4803 return Evaluate(/*commit=*/true).has_value();
4804}
4805
4806// Sweep heuristic
4807// TODO(user): Clean up to match other first solution strategies.
4808
4809namespace {
4810struct SweepIndex {
4811 SweepIndex(const int64_t index, const double angle, const double distance)
4812 : index(index), angle(angle), distance(distance) {}
4813 ~SweepIndex() = default;
4814
4815 int64_t index;
4816 double angle;
4817 double distance;
4818};
4819
4820struct SweepIndexSortAngle {
4821 bool operator()(const SweepIndex& node1, const SweepIndex& node2) const {
4822 return (node1.angle < node2.angle);
4823 }
4824} SweepIndexAngleComparator;
4825
4826struct SweepIndexSortDistance {
4827 bool operator()(const SweepIndex& node1, const SweepIndex& node2) const {
4828 return (node1.distance < node2.distance);
4829 }
4830} SweepIndexDistanceComparator;
4831} // namespace
4832
4834 absl::Span<const std::pair<int64_t, int64_t>> points)
4835 : coordinates_(2 * points.size(), 0), sectors_(1) {
4836 for (int64_t i = 0; i < points.size(); ++i) {
4837 coordinates_[2 * i] = points[i].first;
4838 coordinates_[2 * i + 1] = points[i].second;
4839 }
4840}
4841
4842// Splits the space of the indices into sectors and sorts the indices of each
4843// sector with ascending angle from the depot.
4844void SweepArranger::ArrangeIndices(std::vector<int64_t>* indices) {
4845 const double pi_rad = 3.14159265;
4846 // Suppose that the center is at x0, y0.
4847 const int x0 = coordinates_[0];
4848 const int y0 = coordinates_[1];
4849
4850 std::vector<SweepIndex> sweep_indices;
4851 for (int64_t index = 0; index < static_cast<int>(coordinates_.size()) / 2;
4852 ++index) {
4853 const int x = coordinates_[2 * index];
4854 const int y = coordinates_[2 * index + 1];
4855 const double x_delta = x - x0;
4856 const double y_delta = y - y0;
4857 double square_distance = x_delta * x_delta + y_delta * y_delta;
4858 double angle = square_distance == 0 ? 0 : std::atan2(y_delta, x_delta);
4859 angle = angle >= 0 ? angle : 2 * pi_rad + angle;
4860 sweep_indices.push_back(SweepIndex(index, angle, square_distance));
4861 }
4862 absl::c_sort(sweep_indices, SweepIndexDistanceComparator);
4863
4864 const int size = static_cast<int>(sweep_indices.size()) / sectors_;
4865 for (int sector = 0; sector < sectors_; ++sector) {
4866 std::vector<SweepIndex> cluster;
4867 std::vector<SweepIndex>::iterator begin =
4868 sweep_indices.begin() + sector * size;
4869 std::vector<SweepIndex>::iterator end =
4870 sector == sectors_ - 1 ? sweep_indices.end()
4871 : sweep_indices.begin() + (sector + 1) * size;
4872 std::sort(begin, end, SweepIndexAngleComparator);
4873 }
4874 for (const SweepIndex& sweep_index : sweep_indices) {
4875 indices->push_back(sweep_index.index);
4876 }
4877}
4878
4879namespace {
4880
4881struct Link {
4882 Link(std::pair<int, int> link, double value, int vehicle_class,
4883 int64_t start_depot, int64_t end_depot)
4884 : link(link),
4885 value(value),
4886 vehicle_class(vehicle_class),
4887 start_depot(start_depot),
4888 end_depot(end_depot) {}
4889 ~Link() = default;
4890
4891 std::pair<int, int> link;
4892 int64_t value;
4893 int vehicle_class;
4894 int64_t start_depot;
4895 int64_t end_depot;
4896};
4897
4898// The RouteConstructor creates the routes of a VRP instance subject to its
4899// constraints by iterating on a list of arcs appearing in descending order
4900// of priority.
4901// TODO(user): Use the dimension class in this class.
4902// TODO(user): Add support for vehicle-dependent dimension transits.
4903class RouteConstructor {
4904 public:
4905 RouteConstructor(Assignment* const assignment, RoutingModel* const model,
4906 bool check_assignment, int64_t num_indices,
4907 const std::vector<Link>& links_list)
4908 : assignment_(assignment),
4909 model_(model),
4910 check_assignment_(check_assignment),
4911 solver_(model_->solver()),
4912 num_indices_(num_indices),
4913 links_list_(links_list),
4914 nexts_(model_->Nexts()),
4915 in_route_(num_indices_, -1),
4916 final_routes_(),
4917 index_to_chain_index_(num_indices, -1),
4918 index_to_vehicle_class_index_(num_indices, -1) {
4919 {
4920 const std::vector<std::string> dimension_names =
4921 model_->GetAllDimensionNames();
4922 dimensions_.assign(dimension_names.size(), nullptr);
4923 for (int i = 0; i < dimension_names.size(); ++i) {
4924 dimensions_[i] = &model_->GetDimensionOrDie(dimension_names[i]);
4925 }
4926 }
4927 cumuls_.resize(dimensions_.size());
4928 for (std::vector<int64_t>& cumuls : cumuls_) {
4929 cumuls.resize(num_indices_);
4930 }
4931 new_possible_cumuls_.resize(dimensions_.size());
4932 }
4933
4934 ~RouteConstructor() = default;
4935
4936 void Construct() {
4937 model_->solver()->TopPeriodicCheck();
4938 // Initial State: Each order is served by its own vehicle.
4939 for (int index = 0; index < num_indices_; ++index) {
4940 if (!model_->IsStart(index) && !model_->IsEnd(index)) {
4941 routes_.push_back({index});
4942 in_route_[index] = routes_.size() - 1;
4943 }
4944 }
4945
4946 for (const Link& link : links_list_) {
4947 model_->solver()->TopPeriodicCheck();
4948 const int index1 = link.link.first;
4949 const int index2 = link.link.second;
4950 const int vehicle_class = link.vehicle_class;
4951 const int64_t start_depot = link.start_depot;
4952 const int64_t end_depot = link.end_depot;
4953
4954 // Initialisation of cumuls_ if the indices are encountered for first time
4955 if (index_to_vehicle_class_index_[index1] < 0) {
4956 for (int dimension_index = 0; dimension_index < dimensions_.size();
4957 ++dimension_index) {
4958 cumuls_[dimension_index][index1] =
4959 std::max(dimensions_[dimension_index]->GetTransitValue(
4960 start_depot, index1, 0),
4961 dimensions_[dimension_index]->CumulVar(index1)->Min());
4962 }
4963 }
4964 if (index_to_vehicle_class_index_[index2] < 0) {
4965 for (int dimension_index = 0; dimension_index < dimensions_.size();
4966 ++dimension_index) {
4967 cumuls_[dimension_index][index2] =
4968 std::max(dimensions_[dimension_index]->GetTransitValue(
4969 start_depot, index2, 0),
4970 dimensions_[dimension_index]->CumulVar(index2)->Min());
4971 }
4972 }
4973
4974 const int route_index1 = in_route_[index1];
4975 const int route_index2 = in_route_[index2];
4976 const bool merge =
4977 route_index1 >= 0 && route_index2 >= 0 &&
4978 FeasibleMerge(routes_[route_index1], routes_[route_index2], index1,
4979 index2, route_index1, route_index2, vehicle_class,
4980 start_depot, end_depot);
4981 if (Merge(merge, route_index1, route_index2)) {
4982 index_to_vehicle_class_index_[index1] = vehicle_class;
4983 index_to_vehicle_class_index_[index2] = vehicle_class;
4984 }
4985 }
4986
4987 model_->solver()->TopPeriodicCheck();
4988 // Beyond this point not checking limits anymore as the rest of the code is
4989 // linear and that given we managed to build a solution would be ludicrous
4990 // to drop it now.
4991 for (int chain_index = 0; chain_index < chains_.size(); ++chain_index) {
4992 if (!deleted_chains_.contains(chain_index)) {
4993 final_chains_.push_back(chains_[chain_index]);
4994 }
4995 }
4996 absl::c_sort(final_chains_, ChainComparator);
4997 for (int route_index = 0; route_index < routes_.size(); ++route_index) {
4998 if (!deleted_routes_.contains(route_index)) {
4999 final_routes_.push_back(routes_[route_index]);
5000 }
5001 }
5002 absl::c_sort(final_routes_, RouteComparator);
5003
5004 const int extra_vehicles = std::max(
5005 0, static_cast<int>(final_chains_.size()) - model_->vehicles());
5006 // Bind the Start and End of each chain
5007 int chain_index = 0;
5008 for (chain_index = extra_vehicles; chain_index < final_chains_.size();
5009 ++chain_index) {
5010 if (chain_index - extra_vehicles >= model_->vehicles()) {
5011 break;
5012 }
5013 const int start = final_chains_[chain_index].head;
5014 const int end = final_chains_[chain_index].tail;
5015 assignment_->Add(
5016 model_->NextVar(model_->Start(chain_index - extra_vehicles)));
5017 assignment_->SetValue(
5018 model_->NextVar(model_->Start(chain_index - extra_vehicles)), start);
5019 assignment_->Add(nexts_[end]);
5020 assignment_->SetValue(nexts_[end],
5021 model_->End(chain_index - extra_vehicles));
5022 }
5023
5024 // Create the single order routes
5025 for (int route_index = 0; route_index < final_routes_.size();
5026 ++route_index) {
5027 if (chain_index - extra_vehicles >= model_->vehicles()) {
5028 break;
5029 }
5030 DCHECK_LT(route_index, final_routes_.size());
5031 const int head = final_routes_[route_index].front();
5032 const int tail = final_routes_[route_index].back();
5033 if (head == tail && head < model_->Size()) {
5034 assignment_->Add(
5035 model_->NextVar(model_->Start(chain_index - extra_vehicles)));
5036 assignment_->SetValue(
5037 model_->NextVar(model_->Start(chain_index - extra_vehicles)), head);
5038 assignment_->Add(nexts_[tail]);
5039 assignment_->SetValue(nexts_[tail],
5040 model_->End(chain_index - extra_vehicles));
5041 ++chain_index;
5042 }
5043 }
5044
5045 // Unperformed
5046 for (int index = 0; index < model_->Size(); ++index) {
5047 IntVar* const next = nexts_[index];
5048 if (!assignment_->Contains(next)) {
5049 assignment_->Add(next);
5050 if (next->Contains(index)) {
5051 assignment_->SetValue(next, index);
5052 }
5053 }
5054 }
5055 }
5056
5057 private:
5058 enum MergeStatus { FIRST_SECOND, SECOND_FIRST, NO_MERGE };
5059
5060 struct RouteSort {
5061 bool operator()(absl::Span<const int> route1,
5062 absl::Span<const int> route2) const {
5063 return (route1.size() < route2.size());
5064 }
5065 } RouteComparator;
5066
5067 struct Chain {
5068 int head;
5069 int tail;
5070 int nodes;
5071 };
5072
5073 struct ChainSort {
5074 bool operator()(const Chain& chain1, const Chain& chain2) const {
5075 return (chain1.nodes < chain2.nodes);
5076 }
5077 } ChainComparator;
5078
5079 bool Head(int node) const {
5080 return (node == routes_[in_route_[node]].front());
5081 }
5082
5083 bool Tail(int node) const {
5084 return (node == routes_[in_route_[node]].back());
5085 }
5086
5087 bool FeasibleRoute(const std::vector<int>& route, int64_t route_cumul,
5088 int dimension_index) {
5089 const RoutingDimension& dimension = *dimensions_[dimension_index];
5090 std::vector<int>::const_iterator it = route.begin();
5091 int64_t cumul = route_cumul;
5092 while (it != route.end()) {
5093 const int previous = *it;
5094 const int64_t cumul_previous = cumul;
5095 gtl::InsertOrDie(&(new_possible_cumuls_[dimension_index]), previous,
5096 cumul_previous);
5097 ++it;
5098 if (it == route.end()) {
5099 return true;
5100 }
5101 const int next = *it;
5102 int64_t available_from_previous =
5103 cumul_previous + dimension.GetTransitValue(previous, next, 0);
5104 int64_t available_cumul_next =
5105 std::max(cumuls_[dimension_index][next], available_from_previous);
5106
5107 const int64_t slack = available_cumul_next - available_from_previous;
5108 if (slack > dimension.SlackVar(previous)->Max()) {
5109 available_cumul_next =
5110 available_from_previous + dimension.SlackVar(previous)->Max();
5111 }
5112
5113 if (available_cumul_next > dimension.CumulVar(next)->Max()) {
5114 return false;
5115 }
5116 if (available_cumul_next <= cumuls_[dimension_index][next]) {
5117 return true;
5118 }
5119 cumul = available_cumul_next;
5120 }
5121 return true;
5122 }
5123
5124 bool CheckRouteConnection(absl::Span<const int> route1,
5125 const std::vector<int>& route2, int dimension_index,
5126 int64_t /*start_depot*/, int64_t end_depot) {
5127 const int tail1 = route1.back();
5128 const int head2 = route2.front();
5129 const int tail2 = route2.back();
5130 const RoutingDimension& dimension = *dimensions_[dimension_index];
5131 int non_depot_node = -1;
5132 for (int node = 0; node < num_indices_; ++node) {
5133 if (!model_->IsStart(node) && !model_->IsEnd(node)) {
5134 non_depot_node = node;
5135 break;
5136 }
5137 }
5138 CHECK_GE(non_depot_node, 0);
5139 const int64_t depot_threshold =
5140 std::max(dimension.SlackVar(non_depot_node)->Max(),
5141 dimension.CumulVar(non_depot_node)->Max());
5142
5143 int64_t available_from_tail1 = cumuls_[dimension_index][tail1] +
5144 dimension.GetTransitValue(tail1, head2, 0);
5145 int64_t new_available_cumul_head2 =
5146 std::max(cumuls_[dimension_index][head2], available_from_tail1);
5147
5148 const int64_t slack = new_available_cumul_head2 - available_from_tail1;
5149 if (slack > dimension.SlackVar(tail1)->Max()) {
5150 new_available_cumul_head2 =
5151 available_from_tail1 + dimension.SlackVar(tail1)->Max();
5152 }
5153
5154 bool feasible_route = true;
5155 if (new_available_cumul_head2 > dimension.CumulVar(head2)->Max()) {
5156 return false;
5157 }
5158 if (new_available_cumul_head2 <= cumuls_[dimension_index][head2]) {
5159 return true;
5160 }
5161
5162 feasible_route =
5163 FeasibleRoute(route2, new_available_cumul_head2, dimension_index);
5164 const int64_t new_possible_cumul_tail2 =
5165 new_possible_cumuls_[dimension_index].contains(tail2)
5166 ? new_possible_cumuls_[dimension_index][tail2]
5167 : cumuls_[dimension_index][tail2];
5168
5169 if (!feasible_route || (new_possible_cumul_tail2 +
5170 dimension.GetTransitValue(tail2, end_depot, 0) >
5171 depot_threshold)) {
5172 return false;
5173 }
5174 return true;
5175 }
5176
5177 bool FeasibleMerge(const std::vector<int>& route1,
5178 const std::vector<int>& route2, int node1, int node2,
5179 int route_index1, int route_index2, int vehicle_class,
5180 int64_t start_depot, int64_t end_depot) {
5181 if ((route_index1 == route_index2) || !(Tail(node1) && Head(node2))) {
5182 return false;
5183 }
5184
5185 // Vehicle Class Check
5186 if (!((index_to_vehicle_class_index_[node1] == -1 &&
5187 index_to_vehicle_class_index_[node2] == -1) ||
5188 (index_to_vehicle_class_index_[node1] == vehicle_class &&
5189 index_to_vehicle_class_index_[node2] == -1) ||
5190 (index_to_vehicle_class_index_[node1] == -1 &&
5191 index_to_vehicle_class_index_[node2] == vehicle_class) ||
5192 (index_to_vehicle_class_index_[node1] == vehicle_class &&
5193 index_to_vehicle_class_index_[node2] == vehicle_class))) {
5194 return false;
5195 }
5196
5197 // Check Route1 -> Route2 connection for every dimension
5198 bool merge = true;
5199 for (int dimension_index = 0; dimension_index < dimensions_.size();
5200 ++dimension_index) {
5201 new_possible_cumuls_[dimension_index].clear();
5202 merge = merge && CheckRouteConnection(route1, route2, dimension_index,
5203 start_depot, end_depot);
5204 if (!merge) {
5205 return false;
5206 }
5207 }
5208 return true;
5209 }
5210
5211 bool CheckTempAssignment(Assignment* const temp_assignment,
5212 int new_chain_index, int old_chain_index, int head1,
5213 int tail1, int head2, int tail2) {
5214 // TODO(user): If the chain index is greater than the number of vehicles,
5215 // use another vehicle instead.
5216 if (new_chain_index >= model_->vehicles()) return false;
5217 const int start = head1;
5218 temp_assignment->Add(model_->NextVar(model_->Start(new_chain_index)));
5219 temp_assignment->SetValue(model_->NextVar(model_->Start(new_chain_index)),
5220 start);
5221 temp_assignment->Add(nexts_[tail1]);
5222 temp_assignment->SetValue(nexts_[tail1], head2);
5223 temp_assignment->Add(nexts_[tail2]);
5224 temp_assignment->SetValue(nexts_[tail2], model_->End(new_chain_index));
5225 for (int chain_index = 0; chain_index < chains_.size(); ++chain_index) {
5226 if ((chain_index != new_chain_index) &&
5227 (chain_index != old_chain_index) &&
5228 (!deleted_chains_.contains(chain_index))) {
5229 const int start = chains_[chain_index].head;
5230 const int end = chains_[chain_index].tail;
5231 temp_assignment->Add(model_->NextVar(model_->Start(chain_index)));
5232 temp_assignment->SetValue(model_->NextVar(model_->Start(chain_index)),
5233 start);
5234 temp_assignment->Add(nexts_[end]);
5235 temp_assignment->SetValue(nexts_[end], model_->End(chain_index));
5236 }
5237 }
5238 return solver_->Solve(solver_->MakeRestoreAssignment(temp_assignment));
5239 }
5240
5241 bool UpdateAssignment(absl::Span<const int> route1,
5242 absl::Span<const int> route2) {
5243 bool feasible = true;
5244 const int head1 = route1.front();
5245 const int tail1 = route1.back();
5246 const int head2 = route2.front();
5247 const int tail2 = route2.back();
5248 const int chain_index1 = index_to_chain_index_[head1];
5249 const int chain_index2 = index_to_chain_index_[head2];
5250 if (chain_index1 < 0 && chain_index2 < 0) {
5251 const int chain_index = chains_.size();
5252 if (check_assignment_) {
5253 Assignment* const temp_assignment =
5254 solver_->MakeAssignment(assignment_);
5255 feasible = CheckTempAssignment(temp_assignment, chain_index, -1, head1,
5256 tail1, head2, tail2);
5257 }
5258 if (feasible) {
5259 Chain chain;
5260 chain.head = head1;
5261 chain.tail = tail2;
5262 chain.nodes = 2;
5263 index_to_chain_index_[head1] = chain_index;
5264 index_to_chain_index_[tail2] = chain_index;
5265 chains_.push_back(chain);
5266 }
5267 } else if (chain_index1 >= 0 && chain_index2 < 0) {
5268 if (check_assignment_) {
5269 Assignment* const temp_assignment =
5270 solver_->MakeAssignment(assignment_);
5271 feasible =
5272 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
5273 head1, tail1, head2, tail2);
5274 }
5275 if (feasible) {
5276 index_to_chain_index_[tail2] = chain_index1;
5277 chains_[chain_index1].head = head1;
5278 chains_[chain_index1].tail = tail2;
5279 ++chains_[chain_index1].nodes;
5280 }
5281 } else if (chain_index1 < 0 && chain_index2 >= 0) {
5282 if (check_assignment_) {
5283 Assignment* const temp_assignment =
5284 solver_->MakeAssignment(assignment_);
5285 feasible =
5286 CheckTempAssignment(temp_assignment, chain_index2, chain_index1,
5287 head1, tail1, head2, tail2);
5288 }
5289 if (feasible) {
5290 index_to_chain_index_[head1] = chain_index2;
5291 chains_[chain_index2].head = head1;
5292 chains_[chain_index2].tail = tail2;
5293 ++chains_[chain_index2].nodes;
5294 }
5295 } else {
5296 if (check_assignment_) {
5297 Assignment* const temp_assignment =
5298 solver_->MakeAssignment(assignment_);
5299 feasible =
5300 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
5301 head1, tail1, head2, tail2);
5302 }
5303 if (feasible) {
5304 index_to_chain_index_[tail2] = chain_index1;
5305 chains_[chain_index1].head = head1;
5306 chains_[chain_index1].tail = tail2;
5307 chains_[chain_index1].nodes += chains_[chain_index2].nodes;
5308 deleted_chains_.insert(chain_index2);
5309 }
5310 }
5311 if (feasible) {
5312 assignment_->Add(nexts_[tail1]);
5313 assignment_->SetValue(nexts_[tail1], head2);
5314 }
5315 return feasible;
5316 }
5317
5318 bool Merge(bool merge, int index1, int index2) {
5319 if (merge) {
5320 if (UpdateAssignment(routes_[index1], routes_[index2])) {
5321 // Connection Route1 -> Route2
5322 for (const int node : routes_[index2]) {
5323 in_route_[node] = index1;
5324 routes_[index1].push_back(node);
5325 }
5326 for (int dimension_index = 0; dimension_index < dimensions_.size();
5327 ++dimension_index) {
5328 for (const std::pair<int, int64_t> new_possible_cumul :
5329 new_possible_cumuls_[dimension_index]) {
5330 cumuls_[dimension_index][new_possible_cumul.first] =
5331 new_possible_cumul.second;
5332 }
5333 }
5334 deleted_routes_.insert(index2);
5335 return true;
5336 }
5337 }
5338 return false;
5339 }
5340
5341 Assignment* const assignment_;
5342 RoutingModel* const model_;
5343 const bool check_assignment_;
5344 Solver* const solver_;
5345 const int64_t num_indices_;
5346 const std::vector<Link> links_list_;
5347 std::vector<IntVar*> nexts_;
5348 std::vector<const RoutingDimension*> dimensions_; // Not owned.
5349 std::vector<std::vector<int64_t>> cumuls_;
5350 std::vector<absl::flat_hash_map<int, int64_t>> new_possible_cumuls_;
5351 std::vector<std::vector<int>> routes_;
5352 std::vector<int> in_route_;
5353 absl::flat_hash_set<int> deleted_routes_;
5354 std::vector<std::vector<int>> final_routes_;
5355 std::vector<Chain> chains_;
5356 absl::flat_hash_set<int> deleted_chains_;
5357 std::vector<Chain> final_chains_;
5358 std::vector<int> index_to_chain_index_;
5359 std::vector<int> index_to_vehicle_class_index_;
5360};
5361
5362// Decision Builder building a first solution based on Sweep heuristic for
5363// Vehicle Routing Problem.
5364// Suitable only when distance is considered as the cost.
5365class SweepBuilder : public DecisionBuilder {
5366 public:
5367 SweepBuilder(RoutingModel* const model, bool check_assignment)
5368 : model_(model), check_assignment_(check_assignment) {}
5369 ~SweepBuilder() override = default;
5370
5371 Decision* Next(Solver* const solver) override {
5372 // Setup the model of the instance for the Sweep Algorithm
5373 ModelSetup();
5374
5375 // Build the assignment routes for the model
5376 Assignment* const assignment = solver->MakeAssignment();
5377 route_constructor_ = std::make_unique<RouteConstructor>(
5378 assignment, model_, check_assignment_, num_indices_, links_);
5379 // This call might cause backtracking if the search limit is reached.
5380 route_constructor_->Construct();
5381 route_constructor_.reset(nullptr);
5382 // This call might cause backtracking if the solution is not feasible.
5383 assignment->Restore();
5384
5385 return nullptr;
5386 }
5387
5388 private:
5389 void ModelSetup() {
5390 const int depot = model_->GetDepot();
5391 num_indices_ = model_->Size() + model_->vehicles();
5392 if (absl::GetFlag(FLAGS_sweep_sectors) > 0 &&
5393 absl::GetFlag(FLAGS_sweep_sectors) < num_indices_) {
5394 model_->sweep_arranger()->SetSectors(absl::GetFlag(FLAGS_sweep_sectors));
5395 }
5396 std::vector<int64_t> indices;
5397 model_->sweep_arranger()->ArrangeIndices(&indices);
5398 for (int i = 0; i < indices.size() - 1; ++i) {
5399 const int64_t first = indices[i];
5400 const int64_t second = indices[i + 1];
5401 if ((model_->IsStart(first) || !model_->IsEnd(first)) &&
5402 (model_->IsStart(second) || !model_->IsEnd(second))) {
5403 if (first != depot && second != depot) {
5404 links_.push_back(
5405 Link(std::make_pair(first, second), 0, 0, depot, depot));
5406 }
5407 }
5408 }
5409 }
5410
5411 RoutingModel* const model_;
5412 std::unique_ptr<RouteConstructor> route_constructor_;
5413 const bool check_assignment_;
5414 int64_t num_indices_;
5415 std::vector<Link> links_;
5416};
5417} // namespace
5418
5420 bool check_assignment) {
5421 return model->solver()->RevAlloc(new SweepBuilder(model, check_assignment));
5422}
5423
5424// AllUnperformed
5425
5426namespace {
5427// Decision builder to build a solution with all nodes inactive. It does no
5428// branching and may fail if some nodes cannot be made inactive.
5429
5430class AllUnperformed : public DecisionBuilder {
5431 public:
5432 // Does not take ownership of model.
5433 explicit AllUnperformed(RoutingModel* const model) : model_(model) {}
5434 ~AllUnperformed() override = default;
5435 Decision* Next(Solver* const /*solver*/) override {
5436 // Solver::(Un)FreezeQueue is private, passing through the public API
5437 // on PropagationBaseObject.
5438 model_->CostVar()->FreezeQueue();
5439 for (int i = 0; i < model_->Size(); ++i) {
5440 if (!model_->IsStart(i)) {
5441 model_->ActiveVar(i)->SetValue(0);
5442 }
5443 }
5444 model_->CostVar()->UnfreezeQueue();
5445 return nullptr;
5446 }
5447
5448 private:
5449 RoutingModel* const model_;
5450};
5451} // namespace
5452
5454 return model->solver()->RevAlloc(new AllUnperformed(model));
5455}
5456
5457namespace {
5458// The description is in routing.h:MakeGuidedSlackFinalizer
5459class GuidedSlackFinalizer : public DecisionBuilder {
5460 public:
5461 GuidedSlackFinalizer(const RoutingDimension* dimension, RoutingModel* model,
5462 std::function<int64_t(int64_t)> initializer);
5463
5464 // This type is neither copyable nor movable.
5465 GuidedSlackFinalizer(const GuidedSlackFinalizer&) = delete;
5466 GuidedSlackFinalizer& operator=(const GuidedSlackFinalizer&) = delete;
5467
5468 Decision* Next(Solver* solver) override;
5469
5470 private:
5471 int64_t SelectValue(int64_t index);
5472 int64_t ChooseVariable();
5473
5474 const RoutingDimension* const dimension_;
5475 RoutingModel* const model_;
5476 const std::function<int64_t(int64_t)> initializer_;
5477 RevArray<bool> is_initialized_;
5478 std::vector<int64_t> initial_values_;
5479 Rev<int64_t> current_index_;
5480 Rev<int64_t> current_route_;
5481 RevArray<int64_t> last_delta_used_;
5482};
5483
5484GuidedSlackFinalizer::GuidedSlackFinalizer(
5485 const RoutingDimension* dimension, RoutingModel* model,
5486 std::function<int64_t(int64_t)> initializer)
5487 : dimension_(ABSL_DIE_IF_NULL(dimension)),
5488 model_(ABSL_DIE_IF_NULL(model)),
5489 initializer_(std::move(initializer)),
5490 is_initialized_(dimension->slacks().size(), false),
5491 initial_values_(dimension->slacks().size(),
5492 std::numeric_limits<int64_t>::min()),
5493 current_index_(model_->Start(0)),
5494 current_route_(0),
5495 last_delta_used_(dimension->slacks().size(), 0) {}
5496
5497Decision* GuidedSlackFinalizer::Next(Solver* solver) {
5498 CHECK_EQ(solver, model_->solver());
5499 const int node_idx = ChooseVariable();
5500 CHECK(node_idx == -1 ||
5501 (node_idx >= 0 && node_idx < dimension_->slacks().size()));
5502 if (node_idx != -1) {
5503 if (!is_initialized_[node_idx]) {
5504 initial_values_[node_idx] = initializer_(node_idx);
5505 is_initialized_.SetValue(solver, node_idx, true);
5506 }
5507 const int64_t value = SelectValue(node_idx);
5508 IntVar* const slack_variable = dimension_->SlackVar(node_idx);
5509 return solver->MakeAssignVariableValue(slack_variable, value);
5510 }
5511 return nullptr;
5512}
5513
5514int64_t GuidedSlackFinalizer::SelectValue(int64_t index) {
5515 const IntVar* const slack_variable = dimension_->SlackVar(index);
5516 const int64_t center = initial_values_[index];
5517 const int64_t max_delta =
5518 std::max(center - slack_variable->Min(), slack_variable->Max() - center) +
5519 1;
5520 int64_t delta = last_delta_used_[index];
5521
5522 // The sequence of deltas is 0, 1, -1, 2, -2 ...
5523 // Only the values inside the domain of variable are returned.
5524 while (std::abs(delta) < max_delta &&
5525 !slack_variable->Contains(center + delta)) {
5526 if (delta > 0) {
5527 delta = -delta;
5528 } else {
5529 delta = -delta + 1;
5530 }
5531 }
5532 last_delta_used_.SetValue(model_->solver(), index, delta);
5533 return center + delta;
5534}
5535
5536int64_t GuidedSlackFinalizer::ChooseVariable() {
5537 int64_t int_current_node = current_index_.Value();
5538 int64_t int_current_route = current_route_.Value();
5539
5540 while (int_current_route < model_->vehicles()) {
5541 while (!model_->IsEnd(int_current_node) &&
5542 dimension_->SlackVar(int_current_node)->Bound()) {
5543 int_current_node = model_->NextVar(int_current_node)->Value();
5544 }
5545 if (!model_->IsEnd(int_current_node)) {
5546 break;
5547 }
5548 int_current_route += 1;
5549 if (int_current_route < model_->vehicles()) {
5550 int_current_node = model_->Start(int_current_route);
5551 }
5552 }
5553
5554 CHECK(int_current_route == model_->vehicles() ||
5555 !dimension_->SlackVar(int_current_node)->Bound());
5556 current_index_.SetValue(model_->solver(), int_current_node);
5557 current_route_.SetValue(model_->solver(), int_current_route);
5558 if (int_current_route < model_->vehicles()) {
5559 return int_current_node;
5560 } else {
5561 return -1;
5562 }
5563}
5564} // namespace
5565
5566DecisionBuilder* RoutingModel::MakeGuidedSlackFinalizer(
5567 const RoutingDimension* dimension,
5568 std::function<int64_t(int64_t)> initializer) {
5569 return solver_->RevAlloc(
5570 new GuidedSlackFinalizer(dimension, this, std::move(initializer)));
5571}
5572
5573int64_t RoutingDimension::ShortestTransitionSlack(int64_t node) const {
5574 CHECK_EQ(base_dimension_, this);
5575 CHECK(!model_->IsEnd(node));
5576 // Recall that the model is cumul[i+1] = cumul[i] + transit[i] + slack[i]. Our
5577 // aim is to find a value for slack[i] such that cumul[i+1] + transit[i+1] is
5578 // minimized.
5579 const int64_t next = model_->NextVar(node)->Value();
5580 if (model_->IsEnd(next)) {
5581 return SlackVar(node)->Min();
5582 }
5583 const int64_t next_next = model_->NextVar(next)->Value();
5584 const int64_t serving_vehicle = model_->VehicleVar(node)->Value();
5585 CHECK_EQ(serving_vehicle, model_->VehicleVar(next)->Value());
5586 const RoutingModel::StateDependentTransit transit_from_next =
5587 model_->StateDependentTransitCallback(
5588 state_dependent_class_evaluators_
5589 [state_dependent_vehicle_to_class_[serving_vehicle]])(next,
5590 next_next);
5591 // We have that transit[i+1] is a function of cumul[i+1].
5592 const int64_t next_cumul_min = CumulVar(next)->Min();
5593 const int64_t next_cumul_max = CumulVar(next)->Max();
5594 const int64_t optimal_next_cumul =
5595 transit_from_next.transit_plus_identity->RangeMinArgument(
5596 next_cumul_min, next_cumul_max + 1);
5597 // A few checks to make sure we're on the same page.
5598 DCHECK_LE(next_cumul_min, optimal_next_cumul);
5599 DCHECK_LE(optimal_next_cumul, next_cumul_max);
5600 // optimal_next_cumul = cumul + transit + optimal_slack, so
5601 // optimal_slack = optimal_next_cumul - cumul - transit.
5602 // In the current implementation TransitVar(i) = transit[i] + slack[i], so we
5603 // have to find the transit from the evaluators.
5604 const int64_t current_cumul = CumulVar(node)->Value();
5605 const int64_t current_state_independent_transit = model_->TransitCallback(
5606 class_evaluators_[vehicle_to_class_[serving_vehicle]])(node, next);
5607 const int64_t current_state_dependent_transit =
5608 model_
5609 ->StateDependentTransitCallback(
5610 state_dependent_class_evaluators_
5611 [state_dependent_vehicle_to_class_[serving_vehicle]])(node,
5612 next)
5613 .transit->Query(current_cumul);
5614 const int64_t optimal_slack = optimal_next_cumul - current_cumul -
5615 current_state_independent_transit -
5616 current_state_dependent_transit;
5617 CHECK_LE(SlackVar(node)->Min(), optimal_slack);
5618 CHECK_LE(optimal_slack, SlackVar(node)->Max());
5619 return optimal_slack;
5620}
5621
5622namespace {
5623class GreedyDescentLSOperator : public LocalSearchOperator {
5624 public:
5625 explicit GreedyDescentLSOperator(std::vector<IntVar*> variables);
5626
5627 // This type is neither copyable nor movable.
5628 GreedyDescentLSOperator(const GreedyDescentLSOperator&) = delete;
5629 GreedyDescentLSOperator& operator=(const GreedyDescentLSOperator&) = delete;
5630
5631 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
5632 void Start(const Assignment* assignment) override;
5633
5634 private:
5635 int64_t FindMaxDistanceToDomain(const Assignment* assignment);
5636
5637 const std::vector<IntVar*> variables_;
5638 const Assignment* center_;
5639 int64_t current_step_;
5640 // The deltas are returned in this order:
5641 // (current_step_, 0, ... 0), (-current_step_, 0, ... 0),
5642 // (0, current_step_, ... 0), (0, -current_step_, ... 0),
5643 // ...
5644 // (0, ... 0, current_step_), (0, ... 0, -current_step_).
5645 // current_direction_ keeps track what was the last returned delta.
5646 int64_t current_direction_;
5647};
5648
5649GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)
5650 : variables_(std::move(variables)),
5651 center_(nullptr),
5652 current_step_(0),
5653 current_direction_(0) {}
5654
5655bool GreedyDescentLSOperator::MakeNextNeighbor(Assignment* delta,
5656 Assignment* /*deltadelta*/) {
5657 static const int64_t sings[] = {1, -1};
5658 for (; 1 <= current_step_; current_step_ /= 2) {
5659 for (; current_direction_ < 2 * variables_.size();) {
5660 const int64_t variable_idx = current_direction_ / 2;
5661 IntVar* const variable = variables_[variable_idx];
5662 const int64_t sign_index = current_direction_ % 2;
5663 const int64_t sign = sings[sign_index];
5664 const int64_t offset = sign * current_step_;
5665 const int64_t new_value = center_->Value(variable) + offset;
5666 ++current_direction_;
5667 if (variable->Contains(new_value)) {
5668 delta->Add(variable);
5669 delta->SetValue(variable, new_value);
5670 return true;
5671 }
5672 }
5673 current_direction_ = 0;
5674 }
5675 return false;
5676}
5677
5678void GreedyDescentLSOperator::Start(const Assignment* assignment) {
5679 CHECK(assignment != nullptr);
5680 current_step_ = FindMaxDistanceToDomain(assignment);
5681 center_ = assignment;
5682}
5683
5684int64_t GreedyDescentLSOperator::FindMaxDistanceToDomain(
5685 const Assignment* assignment) {
5686 int64_t result = std::numeric_limits<int64_t>::min();
5687 for (const IntVar* const var : variables_) {
5688 result = std::max(result, std::abs(var->Max() - assignment->Value(var)));
5689 result = std::max(result, std::abs(var->Min() - assignment->Value(var)));
5690 }
5691 return result;
5692}
5693} // namespace
5694
5695std::unique_ptr<LocalSearchOperator> RoutingModel::MakeGreedyDescentLSOperator(
5696 std::vector<IntVar*> variables) {
5697 return std::unique_ptr<LocalSearchOperator>(
5698 new GreedyDescentLSOperator(std::move(variables)));
5699}
5700
5701DecisionBuilder* RoutingModel::MakeSelfDependentDimensionFinalizer(
5702 const RoutingDimension* dimension) {
5703 CHECK(dimension != nullptr);
5704 CHECK(dimension->base_dimension() == dimension);
5705 DecisionBuilder* const guided_finalizer =
5706 MakeGuidedSlackFinalizer(dimension, [dimension](int64_t index) {
5707 return dimension->ShortestTransitionSlack(index);
5708 });
5709 DecisionBuilder* const slacks_finalizer =
5710 solver_->MakeSolveOnce(guided_finalizer);
5711 std::vector<IntVar*> start_cumuls(vehicles_, nullptr);
5712 for (int64_t vehicle_idx = 0; vehicle_idx < vehicles_; ++vehicle_idx) {
5713 start_cumuls[vehicle_idx] = dimension->CumulVar(Start(vehicle_idx));
5714 }
5715 LocalSearchOperator* const hill_climber =
5716 solver_->RevAlloc(new GreedyDescentLSOperator(start_cumuls));
5717 LocalSearchPhaseParameters* const parameters =
5718 solver_->MakeLocalSearchPhaseParameters(CostVar(), hill_climber,
5719 slacks_finalizer);
5720 Assignment* const first_solution = solver_->MakeAssignment();
5721 first_solution->Add(start_cumuls);
5722 for (IntVar* const cumul : start_cumuls) {
5723 first_solution->SetValue(cumul, cumul->Min());
5724 }
5725 DecisionBuilder* const finalizer =
5726 solver_->MakeLocalSearchPhase(first_solution, parameters);
5727 return finalizer;
5728}
5729} // namespace operations_research
bool Contains(const T *val) const
const E & Element(const V *const var) const
const E * ElementPtrOrNull(const V *const var) const
void Copy(const Assignment *assignment)
AssignmentContainer< IntVar, IntVarElement > IntContainer
const IntContainer & IntVarContainer() const
IndexType size() const
Returns how many bits this Bitset64 can hold.
Definition bitset.h:463
void Set(IndexType i)
Sets the bit at position i to 1.
Definition bitset.h:543
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
CheapestAdditionFilteredHeuristic.
std::function< int64_t(int64_t, int64_t, int64_t)> evaluator_
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(absl::Span< const int > vehicles)
int64_t GetEvaluatorInsertionCostForNodeAtPosition(int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle) const
std::optional< int64_t > GetInsertionCostForPairAtPositions(int64_t pickup_to_insert, int64_t pickup_insert_after, int64_t delivery_to_insert, int64_t delivery_insert_after, int vehicle, int hint_weight=0)
void InitializeSeedQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, SeedQueue *sq)
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, std::function< int64_t(int64_t)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
int64_t GetUnperformedValue(int64_t node_to_insert) const
std::optional< int64_t > GetInsertionCostForNodeAtPosition(int64_t node_to_insert, int64_t insert_after, int64_t insert_before, int vehicle, int hint_weight=0)
void InsertBetween(int64_t node, int64_t predecessor, int64_t successor, int vehicle=-1)
void AddSeedNodeToQueue(int node, std::vector< StartEndValue > *start_end_distances, SeedQueue *sq)
clang-format on
ChristofidesFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
ChristofidesFilteredHeuristic.
void SetMatchingAlgorithm(MatchingAlgorithm matching)
std::vector< NodeIndex > TravelingSalesmanPath()
Returns the approximate TSP tour.
static Iterator End(ClosedInterval interval)
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
FirstSolutionStrategy_Value Value
nested types -------------------------------------------------—
void PushInsertion(int64_t node, int64_t insert_after, int vehicle, int bucket, int64_t value)
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, std::function< int64_t(int64_t)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
void AddInsertionSequence(int vehicle, std::initializer_list< Insertion > insertion_sequence)
void AppendPickupDeliveryMultitourInsertions(int pickup, int delivery, int vehicle, const std::vector< int > &path, const std::vector< bool > &path_node_is_pickup, const std::vector< bool > &path_node_is_delivery, InsertionSequenceContainer &insertions)
virtual bool Bound() const
Returns true if the min and the max of the expression are equal.
virtual int64_t Min() const =0
int64_t number_of_decisions() const
Returns statistics from its underlying heuristic.
std::string DebugString() const override
-------— Decision Builder -------—
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
— First solution decision builder —
bool HasSecondaryVars() const
Returns true if there are secondary variables.
void ResetSolution()
Resets the data members for a new solution.
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, LocalSearchFilterManager *filter_manager)
— First solution heuristics —
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
bool Contains(int64_t index) const
Returns true if the variable of index 'index' is in the current solution.
virtual void Initialize()
Initialize the heuristic; called before starting to build a new solution.
int64_t SecondaryVarIndex(int64_t index) const
Returns the index of a secondary var.
void SetValue(int64_t index, int64_t value)
virtual bool InitializeSolution()
Virtual method to initialize the solution.
const std::vector< int > & delta_indices() const
Returns the indices of the nodes currently in the insertion delta.
IntVar * Var(int64_t index) const
Returns the variable of index 'index'.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
std::optional< int64_t > Evaluate(bool commit, bool ignore_upper_bound=false, bool update_upper_bound=true)
bool IsSecondaryVar(int64_t index) const
Returns true if 'index' is a secondary variable index.
virtual int64_t Value() const =0
void Initialize() override
Initialize the heuristic; called before starting to build a new solution.
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, std::function< int64_t(int64_t, int64_t, int64_t)> evaluator, RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy, std::vector< RoutingSearchParameters::InsertionSortingProperty > insertion_sorting_properties, LocalSearchFilterManager *filter_manager, bool use_first_solution_hint, BinCapacities *bin_capacities=nullptr, std::function< bool(const std::vector< RoutingModel::VariableValuePair > &, std::vector< RoutingModel::VariableValuePair > *)> optimize_on_insertion=nullptr)
Takes ownership of evaluator.
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
bool Accept(LocalSearchMonitor *monitor, const Assignment *delta, const Assignment *deltadelta, int64_t objective_min, int64_t objective_max)
-------— Local Search Phase Parameters -------—
static IntOut SafeRound(FloatIn x)
Definition mathutil.h:227
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
Assignment * BuildSolutionFromRoutes(const std::function< int64_t(int64_t)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
void SetNext(int64_t node, int64_t next, int vehicle)
bool MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed, always returns true.
RoutingFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, LocalSearchFilterManager *filter_manager)
RoutingFilteredHeuristic.
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
bool StopSearch() override
Returns true if the search must be stopped.
void AddUnassignedNodesToEmptyVehicles()
Adds all unassigned nodes to empty vehicles.
static constexpr PairInsertionStrategy BEST_PICKUP_DELIVERY_PAIR_MULTITOUR
::operations_research::LocalSearchMetaheuristic_Value local_search_metaheuristic() const
const ::google::protobuf::Duration & time_limit() const
static constexpr InsertionSortingProperty SORTING_PROPERTY_ALLOWED_VEHICLES
static constexpr PairInsertionStrategy BEST_PICKUP_THEN_BEST_DELIVERY
static constexpr InsertionSortingProperty SORTING_PROPERTY_PENALTY
void set_local_search_metaheuristic(::operations_research::LocalSearchMetaheuristic_Value value)
static constexpr PairInsertionStrategy BEST_PICKUP_DELIVERY_PAIR
RoutingSearchParameters_PairInsertionStrategy PairInsertionStrategy
static constexpr InsertionSortingProperty SORTING_PROPERTY_HIGHEST_DIMENSION_USAGE
bool has_time_limit() const
.google.protobuf.Duration time_limit = 9;
static constexpr PairInsertionStrategy AUTOMATIC
RoutingSearchParameters_InsertionSortingProperty InsertionSortingProperty
const std::vector< Saving > & GetSortedSavingsForVehicleType(int type)
void InitializeContainer(int64_t size, int64_t saving_neighbors)
void AddNewSaving(const Saving &saving, int64_t total_cost, int64_t before_node, int64_t after_node, int vehicle_type)
SavingsContainer(const SavingsFilteredHeuristic *savings_db, int vehicle_types)
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
SavingsFilteredHeuristic(RoutingModel *model, std::function< bool()> stop_search, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
SavingsFilteredHeuristic.
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node, int64_t after_node)
std::unique_ptr< SavingsContainer< Saving > > savings_container_
clang-format off
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
clang-format on
For the time being, Solver is neither MT_SAFE nor MT_HOT.
void Fail()
Abandon the current branch in the search tree. A backtrack will follow.
LocalSearchMonitor * GetLocalSearchMonitor() const
Returns the local search monitor.
Assignment * MakeAssignment()
This method creates an empty assignment.
std::function< bool(int64_t, int64_t, int64_t)> VariableValueComparator
SweepArranger(absl::Span< const std::pair< int64_t, int64_t > > points)
void ArrangeIndices(std::vector< int64_t > *indices)
void Update(const std::function< bool(int)> &remove_vehicle)
bool HasCompatibleVehicleOfType(int type, const std::function< bool(int)> &vehicle_is_compatible) const
std::pair< int, int > GetCompatibleVehicleOfType(int type, const std::function< bool(int)> &vehicle_is_compatible, const std::function< bool(int)> &stop_and_return_vehicle)
void Reset(const std::function< bool(int)> &store_vehicle)
— VehicleTypeCurator —
time_limit
Definition solve.cc:22
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
Definition map_util.h:159
void STLClearObject(T *obj)
Definition stl_util.h:120
For infeasible and unbounded see Not checked if options check_solutions_if_inf_or_unbounded and the If options first_solution_only is false
problem is infeasible or unbounded (default).
Definition matchers.h:468
In SWIG mode, we don't want anything besides these top-level includes.
const Assignment * SolveFromAssignmentWithAlternativeSolversAndParameters(const Assignment *assignment, RoutingModel *primary_model, const RoutingSearchParameters &primary_parameters, const std::vector< RoutingModel * > &alternative_models, const std::vector< RoutingSearchParameters > &alternative_parameters, int max_non_improving_iterations)
Same as above but taking alternative parameters for each alternative model.
DecisionBuilder * MakeAllUnperformed(RoutingModel *model)
Returns a DecisionBuilder making all nodes unperformed.
int64_t CapAdd(int64_t x, int64_t y)
void CapAddTo(int64_t x, int64_t *y)
FirstSolutionStrategy::Value AutomaticFirstSolutionStrategy(bool has_pickup_deliveries, bool has_node_precedences, bool has_single_vehicle_node)
Select next search node to expand Select next item_i to add this new search node to the search Generate a new search node where item_i is not in the knapsack Check validity of this new partial solution(using propagators) - If valid
std::vector< int64_t > ComputeVehicleEndChainStarts(const RoutingModel &model)
int64_t CapSub(int64_t x, int64_t y)
ClosedInterval::Iterator end(ClosedInterval interval)
const Assignment * SolveFromAssignmentWithAlternativeSolvers(const Assignment *assignment, RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters &parameters, int max_non_improving_iterations)
Same as above, but taking an initial solution.
static const int kUnassigned
--— Routing model --—
Definition routing.cc:507
DecisionBuilder * MakeSweepDecisionBuilder(RoutingModel *model, bool check_assignment)
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
Definition base_types.h:32
ClosedInterval::Iterator begin(ClosedInterval interval)
const Assignment * SolveWithAlternativeSolvers(RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters &parameters, int max_non_improving_iterations)
int64_t CapOpp(int64_t v)
Note(user): -kint64min != kint64max, but kint64max == ~kint64min.
STL namespace.
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
Definition protoutil.h:42
inline ::absl::StatusOr< google::protobuf::Duration > EncodeGoogleApiProto(absl::Duration d)
Definition protoutil.h:27
bool Next()
trees with all degrees equal to
ABSL_FLAG(bool, routing_shift_insertion_cost_by_penalty, true, "Shift insertion costs by the penalty of the inserted node(s).")
std::priority_queue< Seed, std::vector< Seed >, std::greater< Seed > > priority_queue
static const int64_t kint64max
Definition types.h:32