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"
73ABSL_FLAG(
bool, routing_shift_insertion_cost_by_penalty,
true,
74 "Shift insertion costs by the penalty of the inserted node(s).");
77 "The number of sectors the space is divided into before it is sweeped"
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);
94 dst->SetValue(dst_next_var, src->Value(src_model->NextVar(i)));
98bool AreAssignmentsEquivalent(
const RoutingModel& model,
101 for (
IntVar* next_var : model.Nexts()) {
102 if (assignment1.Value(next_var) != assignment2.Value(next_var)) {
110 return search_parameters.has_time_limit()
113 : absl::InfiniteDuration();
119bool UpdateTimeLimits(
Solver* solver, int64_t start_time_ms,
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;
129 time_left, search_parameters.mutable_time_limit());
136 RoutingModel* primary_model,
137 const std::vector<RoutingModel*>& alternative_models,
139 int max_non_improving_iterations) {
141 nullptr, primary_model, alternative_models, parameters,
142 max_non_improving_iterations);
146 const Assignment* assignment, RoutingModel* primary_model,
147 const std::vector<RoutingModel*>& alternative_models,
149 int max_non_improving_iterations) {
151 assignment, primary_model, parameters, alternative_models, {},
152 max_non_improving_iterations);
156 const Assignment* assignment, RoutingModel* primary_model,
158 const std::vector<RoutingModel*>& alternative_models,
159 const std::vector<RoutingSearchParameters>& alternative_parameters,
160 int max_non_improving_iterations) {
162 if (max_non_improving_iterations < 0)
return nullptr;
164 if (max_non_improving_iterations == 0 || alternative_models.empty()) {
165 return primary_model->SolveFromAssignmentWithParameters(assignment,
174 const bool run_metaheuristic_phase =
177 if (run_metaheuristic_phase) {
181 std::vector<RoutingSearchParameters> mutable_alternative_parameters =
182 alternative_parameters;
183 DCHECK(mutable_alternative_parameters.empty() ||
184 mutable_alternative_parameters.size() == alternative_models.size());
186 mutable_alternative_parameters) {
187 if (!mutable_alternative_parameter.has_time_limit() &&
189 *mutable_alternative_parameter.mutable_time_limit() =
193 const absl::Duration
time_limit = GetTimeLimit(mutable_search_parameters);
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());
203 DCHECK(assignment ==
nullptr ||
204 assignment->
solver() == primary_model->solver());
206 assignment, mutable_search_parameters);
207 if (
solution ==
nullptr)
return nullptr;
210 while (iteration < max_non_improving_iterations) {
215 for (
int i = 0; i < alternative_models.size(); ++i) {
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;
224 ConvertAssignment(primary_model,
solution, alternative_models[i],
226 solution = alternative_models[i]->SolveFromAssignmentWithParameters(
227 first_solutions[i], mutable_alternative_parameter);
231 if (!UpdateTimeLimits(primary_model->solver(), start_time_ms,
time_limit,
232 mutable_search_parameters)) {
233 return best_assignment;
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;
242 if (AreAssignmentsEquivalent(*primary_model, *
solution,
243 *current_solution)) {
248 if (AreAssignmentsEquivalent(*primary_model, *
solution, *best_assignment)) {
255 if (run_metaheuristic_phase &&
256 UpdateTimeLimits(primary_model->solver(), start_time_ms,
time_limit,
257 mutable_search_parameters)) {
259 return primary_model->SolveFromAssignmentWithParameters(
260 best_assignment, mutable_search_parameters);
262 return best_assignment;
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());
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);
289 if (!stored_vehicles.empty()) {
290 stored_class_entries.insert(class_entry);
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);
309 if (vehicles.empty()) {
310 class_entry_it = class_entries.erase(class_entry_it);
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]) {
323 vehicles_per_vehicle_class_[vehicle_class_entry.vehicle_class]) {
324 if (vehicle_is_compatible(vehicle))
return true;
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();
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());
342 for (
auto vehicle_it = vehicles.begin(); vehicle_it != vehicles.end();
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);
350 return {vehicle, -1};
352 if (stop_and_return_vehicle(vehicle)) {
353 return {-1, vehicle};
372 bool has_pickup_deliveries,
bool has_node_precedences,
373 bool has_single_vehicle_node) {
374 if (has_pickup_deliveries || has_node_precedences) {
377 if (has_single_vehicle_node) {
384 const int64_t size = model.Size();
385 const int num_vehicles = model.vehicles();
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) {
400 std::vector<bool> touched(size,
false);
401 for (
int node = 0; node < size; ++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();
412 starts[ends[current]] = starts[node];
413 ends[starts[node]] = ends[current];
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)];
421 return end_chain_starts;
429 std::unique_ptr<IntVarFilteredHeuristic> heuristic)
430 : heuristic_(
std::move(heuristic)) {}
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();
446 return heuristic_->number_of_decisions();
450 return heuristic_->number_of_rejects();
454 return absl::StrCat(
"IntVarFilteredDecisionBuilder(",
455 heuristic_->DebugString(),
")");
463 Solver* solver,
const std::vector<IntVar*>& vars,
464 const std::vector<IntVar*>& secondary_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());
479 assignment_->MutableIntVarContainer()->Resize(vars_.size());
480 is_in_delta_.resize(vars_.size(),
false);
481 delta_indices_.reserve(vars_.size());
485 number_of_decisions_ = 0;
486 number_of_rejects_ = 0;
489 delta_->MutableIntVarContainer()->Clear();
491 assignment_->MutableIntVarContainer()->Resize(vars_.size());
508 const std::function<int64_t(int64_t)>& next_accessor) {
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);
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_;
545 if (filter_manager_ !=
nullptr) {
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;
563 delta_->IntVarContainer();
564 const int delta_size = delta_container.
Size();
567 for (
int i = 0; i < delta_size; ++i) {
570 DCHECK_EQ(var, vars_[delta_indices_[i]]);
577 ++number_of_rejects_;
580 for (
const int delta_index : delta_indices_) {
581 is_in_delta_[delta_index] =
false;
584 delta_indices_.clear();
585 return accept ? std::optional<int64_t>{objective_upper_bound} : std::nullopt;
589 if (filter_manager_) filter_manager_->Synchronize(
assignment_, delta_);
591 objective_upper_bound_ = std::numeric_limits<int64_t>::max();
594bool IntVarFilteredHeuristic::FilterAccept(
bool ignore_upper_bound) {
595 if (!filter_manager_)
return true;
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_);
606 RoutingModel*
model, std::function<
bool()> stop_search,
609 model->CostsAreHomogeneousAcrossVehicles()
611 :
model->VehicleVars(),
614 stop_search_(
std::move(stop_search)) {}
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();
630 start_chain_ends_[vehicle] = node;
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];
644 while (!
model()->IsEnd(node)) {
661 model()->ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(
662 node, 1, [
this, node](
int alternate) {
663 if (node != alternate && !
Contains(alternate)) {
664 SetNext(alternate, alternate, -1);
672 absl::btree_set<std::pair<int64_t, int>> empty_vehicles;
673 for (
int vehicle = 0; vehicle < model_->vehicles(); ++vehicle) {
675 empty_vehicles.insert({
model()->GetFixedCostOfVehicle(vehicle), vehicle});
678 for (
int index = 0; index < model_->Size(); ++index) {
679 if (
StopSearch() || empty_vehicles.empty())
return;
682 for (
auto [cost, vehicle] : empty_vehicles) {
683 SetNext(model_->Start(vehicle), index, vehicle);
684 SetNext(index, model_->End(vehicle), vehicle);
686 empty_vehicles.erase({cost, vehicle});
696 for (
int index = 0; index < model_->Size(); ++index) {
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) {
713 performed_pickup = pickup;
717 int64_t performed_delivery = -1;
718 for (int64_t delivery : deliveries) {
720 performed_delivery = delivery;
724 if ((performed_pickup == -1) != (performed_delivery == -1)) {
725 if (performed_pickup != -1) {
726 to_make_unperformed[performed_pickup] =
true;
728 if (performed_delivery != -1) {
729 to_make_unperformed[performed_delivery] =
true;
733 for (
int index = 0; index < num_nexts; ++index) {
734 if (to_make_unperformed[index] || !
Contains(index))
continue;
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);
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,
760void ProcessVehicleStartEndCosts(
761 const RoutingModel& model,
int node,
762 const std::function<
void(int64_t,
int)>& process_cost,
764 bool ignore_end =
false) {
765 const auto start_end_cost = [&model, ignore_start, ignore_end](int64_t node,
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);
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]) {
784 process_cost(start_end_cost(node, v), v);
787 for (
const int v : vehicle_set) {
788 if (!vehicle_var->Contains(v))
continue;
789 process_cost(start_end_cost(node, v), v);
795std::vector<std::vector<CheapestInsertionFilteredHeuristic::StartEndValue>>
797 absl::Span<const int> vehicles) {
800 std::vector<std::vector<StartEndValue>> start_end_distances_per_node(
804 for (
int v : vehicles) vehicle_set.
Set(v);
806 for (
int node = 0; node <
model.Size(); node++) {
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())));
814 ProcessVehicleStartEndCosts(
816 [&start_end_distances](int64_t dist,
int v) {
817 start_end_distances.push_back({dist, v});
823 absl::c_sort(start_end_distances,
825 return second < first;
828 return start_end_distances_per_node;
832 int node, std::vector<StartEndValue>* start_end_distances,
SeedQueue* sq) {
833 if (start_end_distances->empty()) {
838 StartEndValue& start_end_value = start_end_distances->back();
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,
846 .vehicle = start_end_value.
vehicle,
847 .is_node_index =
true,
849 start_end_distances->pop_back();
853 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
855 const int num_nodes =
model()->Size();
856 DCHECK_EQ(start_end_distances_per_node->size(), num_nodes);
858 for (
int node = 0; node < num_nodes; node++) {
880 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
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,
890 evaluator_(node_to_insert, insert_before, vehicle)),
894std::optional<int64_t>
896 int64_t node_to_insert, int64_t insert_after, int64_t insert_before,
897 int vehicle,
int hint_weight) {
900 node_to_insert, insert_after, insert_before, vehicle);
902 InsertBetween(node_to_insert, insert_after, insert_before, vehicle);
903 return Evaluate(
false, hint_weight > 0,
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);
919 pickup, pickup_insert_after, pickup_insert_before, vehicle);
921 delivery, delivery_insert_after, delivery_insert_before, vehicle);
922 return CapAdd(pickup_cost, delivery_cost);
925 InsertBetween(pickup, pickup_insert_after, pickup_insert_before, vehicle);
926 InsertBetween(delivery, delivery_insert_after, delivery_insert_before,
934 int64_t node_to_insert)
const {
938 return std::numeric_limits<int64_t>::max();
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,
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);
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) {
970 node_is_visited[node] =
true;
974 for (
int node = 0; node <
model()->Size(); node++) {
975 if (!node_is_visited[node] && node_index_to_vehicle_[node] != -1) {
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;
994 if (empty_vehicle_type_curator_ ==
nullptr) {
995 empty_vehicle_type_curator_ = std::make_unique<VehicleTypeCurator>(
996 model()->GetVehicleTypeContainer());
999 empty_vehicle_type_curator_->Reset(
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++) {
1009 pickup_delivery_pairs[index];
1010 const auto& [pickups, deliveries] = pickup_delivery_pair;
1011 int pickup_vehicle = -1;
1012 for (int64_t pickup : pickups) {
1014 pickup_vehicle = node_index_to_vehicle_[pickup];
1018 int delivery_vehicle = -1;
1019 for (int64_t delivery : deliveries) {
1021 delivery_vehicle = node_index_to_vehicle_[delivery];
1025 if (pickup_vehicle < 0 && delivery_vehicle < 0) {
1026 pairs_to_insert_by_bucket[GetBucketOfPair(pickup_delivery_pair)]
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);
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);
1043 const auto unperform_unassigned_and_check = [
this]() {
1047 for (
const auto& [vehicle, nodes] : vehicle_to_pair_nodes) {
1048 if (!InsertNodesOnRoutes(nodes, {vehicle})) {
1049 return unperform_unassigned_and_check();
1053 if (!InsertPairsAndNodesByRequirementTopologicalOrder()) {
1054 return unperform_unassigned_and_check();
1059 if (!InsertPairs(pairs_to_insert_by_bucket)) {
1060 return unperform_unassigned_and_check();
1062 std::map<int64_t, std::vector<int>> nodes_by_bucket;
1063 for (
int node = 0; node <
model()->Size(); ++node) {
1065 !
model()->IsDelivery(node)) {
1066 nodes_by_bucket[GetBucketOfNode(node)].push_back(node);
1069 InsertFarthestNodesAsSeeds();
1070 if (gci_params_.is_sequential) {
1071 if (!SequentialInsertNodes(nodes_by_bucket)) {
1072 return unperform_unassigned_and_check();
1074 }
else if (!InsertNodesOnRoutes(nodes_by_bucket, {})) {
1075 return unperform_unassigned_and_check();
1077 DCHECK(CheckVehicleIndices());
1078 return unperform_unassigned_and_check();
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])]
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);
1098 if (!InsertNodesOnRoutes(nodes_by_bucket, {}))
return false;
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) {
1116 for (int64_t delivery : deliveries) {
1117 if (
Contains(delivery))
return true;
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);
1128 if (!InitializePairPositions(pair_indices_to_insert, &priority_queue,
1129 &pickup_to_entries, &delivery_to_entries)) {
1132 while (!priority_queue.
IsEmpty()) {
1133 if (StopSearchAndCleanup(&priority_queue)) {
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();
1140 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1141 &delivery_to_entries);
1145 const int entry_vehicle = entry->vehicle();
1146 if (entry_vehicle == -1) {
1149 SetNext(delivery, delivery, -1);
1151 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1152 &delivery_to_entries);
1158 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle)) {
1159 if (!InsertPairEntryUsingEmptyVehicleTypeCurator(
1160 pair_indices_to_insert, entry, &priority_queue,
1161 &pickup_to_entries, &delivery_to_entries)) {
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);
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);
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)) {
1186 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,
1187 &delivery_to_entries);
1192 for (
auto it = pair_indices_to_insert.begin(),
1193 last = pair_indices_to_insert.end();
1195 if (pair_is_performed(*it)) {
1196 pair_indices_to_insert.erase(it++);
1205bool GlobalCheapestInsertionFilteredHeuristic::
1206 InsertPairEntryUsingEmptyVehicleTypeCurator(
1207 const absl::flat_hash_set<int>& pair_indices,
1208 GlobalCheapestInsertionFilteredHeuristic::PairEntry*
const pair_entry,
1209 AdjustablePriorityQueue<
1210 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
1212 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1214 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
1215 delivery_to_entries) {
1216 const int entry_vehicle = pair_entry->vehicle();
1217 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle));
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) {
1243 auto stop_and_return_vehicle = [
this, entry_fixed_cost](
int vehicle) {
1244 return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
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) {
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)) {
1261 if (compatible_vehicle != entry_vehicle) {
1268 num_previous_vehicle_entries == 0 ||
1269 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=
1270 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());
1276 const int new_empty_vehicle =
1277 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
1278 empty_vehicle_type_curator_->Type(compatible_vehicle));
1280 if (new_empty_vehicle >= 0) {
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);
1295 if (!AddPairEntriesWithPickupAfter(
1296 pair_indices, new_empty_vehicle, new_empty_vehicle_start,
1298 pickup_to_entries, delivery_to_entries)) {
1302 }
else if (next_fixed_cost_empty_vehicle >= 0) {
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);
1320 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
1321 delivery_to_entries);
1351 : entries_(num_nodes), touched_entries_(num_nodes) {}
1353 priority_queue_.Clear();
1354 for (Entries& entries : entries_) entries.Clear();
1355 touched_entries_.ResetAllToFalse();
1358 return priority_queue_.IsEmpty() &&
1359 touched_entries_.NumberOfSetCallsWithDifferentArguments() == 0;
1362 return insert_after >= entries_.size() ||
1363 entries_[insert_after].entries.empty();
1367 for (
int touched : touched_entries_.PositionsSetAtLeastOnce()) {
1368 SortInsertions(&entries_[touched]);
1370 touched_entries_.ResetAllToFalse();
1371 DCHECK(!priority_queue_.IsEmpty());
1372 Entries* entries = priority_queue_.Top();
1373 DCHECK(!entries->entries.empty());
1374 return entries->Top();
1378 CHECK_EQ(touched_entries_.NumberOfSetCallsWithDifferentArguments(), 0);
1379 Entries* top = priority_queue_.Top();
1380 if (top->IncrementTop()) {
1381 priority_queue_.NoteChangedPriority(top);
1383 priority_queue_.Remove(top);
1388 if (
IsEmpty(insert_after))
return;
1389 Entries& entries = entries_[insert_after];
1390 if (priority_queue_.Contains(&entries)) {
1391 priority_queue_.Remove(&entries);
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);
1404 bool operator<(
const Entries& other)
const {
1405 DCHECK(!entries.empty());
1406 DCHECK(!other.entries.empty());
1407 return other.entries[other.top] < entries[top];
1414 void SetHeapIndex(
int index) { heap_index = index; }
1415 int GetHeapIndex()
const {
return heap_index; }
1416 bool IncrementTop() {
1418 return top < entries.size();
1420 Entry*
Top() {
return &entries[top]; }
1422 std::vector<Entry> entries;
1424 int heap_index = -1;
1427 void SortInsertions(Entries* entries) {
1429 if (entries->entries.empty())
return;
1430 absl::c_sort(entries->entries);
1431 if (!priority_queue_.Contains(entries)) {
1432 priority_queue_.Add(entries);
1434 priority_queue_.NoteChangedPriority(entries);
1438 AdjustablePriorityQueue<Entries> priority_queue_;
1439 std::vector<Entries> entries_;
1440 SparseBitset<int> touched_entries_;
1443bool GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(
1444 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,
1445 const absl::flat_hash_set<int>& vehicles) {
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);
1452 if (!InitializePositions(nodes_to_insert, vehicles, &queue)) {
1461 const bool all_vehicles =
1462 vehicles.empty() || vehicles.size() ==
model()->vehicles();
1464 while (!queue.IsEmpty()) {
1473 const int entry_vehicle = node_entry->vehicle;
1474 if (entry_vehicle == -1) {
1475 DCHECK(all_vehicles);
1477 SetNext(node_to_insert, node_to_insert, -1);
1485 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles)) {
1486 DCHECK(all_vehicles);
1487 if (!InsertNodeEntryUsingEmptyVehicleTypeCurator(
1488 nodes_to_insert, all_vehicles, &queue)) {
1494 const int64_t insert_after = node_entry->insert_after;
1497 if (!UpdateAfterNodeInsertion(nodes_to_insert, entry_vehicle,
1498 node_to_insert, insert_after,
1499 all_vehicles, &queue)) {
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);
1514 nodes_to_insert.ResetAllToFalse();
1515 for (
int node : non_inserted_nodes) {
1516 nodes_to_insert.Set(node);
1522bool GlobalCheapestInsertionFilteredHeuristic::
1525 NodeEntryQueue* queue) {
1527 const int entry_vehicle = node_entry->
vehicle;
1528 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles));
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) {
1548 model()->End(vehicle), vehicle);
1555 auto stop_and_return_vehicle = [
this, entry_fixed_cost](
int vehicle) {
1556 return model()->GetFixedCostOfVehicle(vehicle) > entry_fixed_cost;
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) {
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)) {
1571 if (compatible_vehicle != entry_vehicle) {
1578 no_prior_entries_for_this_vehicle ||
1579 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=
1580 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());
1586 const int new_empty_vehicle =
1587 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(
1588 empty_vehicle_type_curator_->Type(compatible_vehicle));
1590 if (new_empty_vehicle >= 0) {
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)) {
1604 }
else if (next_fixed_cost_empty_vehicle >= 0) {
1612 const int64_t insert_after =
model()->Start(next_fixed_cost_empty_vehicle);
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)
1620 queue->PushInsertion(node_to_insert, insert_after,
1621 next_fixed_cost_empty_vehicle, bucket,
1622 CapSub(insertion_cost, penalty_shift));
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;
1636 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);
1637 if (!used_vehicles.empty() &&
1638 !InsertNodesOnRoutes(nodes_by_bucket, used_vehicles)) {
1642 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =
1647 int vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
1650 while (vehicle >= 0) {
1651 if (!InsertNodesOnRoutes(nodes_by_bucket, {vehicle})) {
1654 vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,
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());
1666 used_vehicles->clear();
1667 used_vehicles->reserve(
model()->vehicles());
1669 unused_vehicles->clear();
1670 unused_vehicles->reserve(
model()->vehicles());
1672 for (
int vehicle = 0; vehicle <
model()->vehicles(); vehicle++) {
1674 (*is_vehicle_used)[vehicle] =
true;
1675 used_vehicles->insert(vehicle);
1677 (*is_vehicle_used)[vehicle] =
false;
1678 unused_vehicles->push_back(vehicle);
1683bool GlobalCheapestInsertionFilteredHeuristic::IsCheapestClassRepresentative(
1684 int vehicle)
const {
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();
1702void GlobalCheapestInsertionFilteredHeuristic::InsertFarthestNodesAsSeeds() {
1704 if (gci_params_.farthest_seeds_ratio <= 0)
return;
1706 const int num_seeds =
static_cast<int>(
1707 std::ceil(gci_params_.farthest_seeds_ratio *
model()->vehicles()));
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 =
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) {
1733 DCHECK(empty_vehicle_type_curator_ !=
nullptr);
1734 empty_vehicle_type_curator_->Update(
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()) {
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();
1750 std::vector<StartEndValue>& other_start_end_values =
1751 (*start_end_distances_per_node)[seed_node];
1756 other_start_end_values.clear();
1759 if (!(*is_vehicle_used)[seed_vehicle]) {
1761 const int64_t start =
model()->Start(seed_vehicle);
1766 (*is_vehicle_used)[seed_vehicle] =
true;
1767 other_start_end_values.clear();
1768 SetVehicleIndex(seed_node, seed_vehicle);
1769 return seed_vehicle;
1781bool GlobalCheapestInsertionFilteredHeuristic::InitializePairPositions(
1782 const absl::flat_hash_set<int>& pair_indices,
1783 AdjustablePriorityQueue<
1784 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,
1785 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
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) {
1800 for (int64_t delivery : deliveries) {
1802 if (StopSearchAndCleanup(priority_queue))
return false;
1807 if (gci_params_.add_unperformed_entries && pickups.size() == 1 &&
1808 deliveries.size() == 1 &&
1810 std::numeric_limits<int64_t>::max() &&
1812 std::numeric_limits<int64_t>::max()) {
1813 AddPairEntry(pickup, -1, delivery, -1, -1, priority_queue,
nullptr,
1817 InitializeInsertionEntriesPerformingPair(
1818 pickup, delivery, priority_queue, pickup_to_entries,
1819 delivery_to_entries);
1826void GlobalCheapestInsertionFilteredHeuristic::
1827 InitializeInsertionEntriesPerformingPair(
1828 int64_t pickup, int64_t delivery,
1829 AdjustablePriorityQueue<
1830 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*
1832 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
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)) {
1843 if (!IsCheapestClassRepresentative(vehicle))
continue;
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);
1856 pickup_insert_after =
Value(pickup_insert_after);
1864 for (
int cost_class = 0; cost_class <
model()->GetCostClassesCount();
1866 absl::flat_hash_set<std::pair<int64_t, int64_t>>
1867 existing_insertion_positions;
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)) {
1875 const int vehicle = node_index_to_vehicle_[pickup_insert_after];
1877 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
1881 if (!IsCheapestClassRepresentative(vehicle))
continue;
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);
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);
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)) {
1910 const int vehicle = node_index_to_vehicle_[delivery_insert_after];
1912 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
1921 delivery_insert_after ==
model()->Start(vehicle));
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);
1931 pickup_insert_after =
Value(pickup_insert_after);
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) {
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);
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());
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)) {
1969 if (!AddPairEntriesAfter(pair_indices, vehicle, pickup,
1971 priority_queue, pickup_to_entries,
1972 delivery_to_entries) ||
1973 !AddPairEntriesAfter(pair_indices, vehicle, delivery,
1975 priority_queue, pickup_to_entries,
1976 delivery_to_entries)) {
1979 SetVehicleIndex(pickup, vehicle);
1980 SetVehicleIndex(delivery, vehicle);
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>*
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));
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);
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);
2018 for (PairEntry*
const pair_entry : to_remove) {
2019 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,
2020 delivery_to_entries);
2022 insert_after =
Value(insert_after);
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>*
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;
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) {
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);
2066 if (delivery_insert_after == pickup) {
2067 delivery_insert_after = pickup_insert_before;
2069 delivery_insert_after =
Value(delivery_insert_after);
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>*
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;
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) {
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);
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);
2132 if (entry->delivery_insert_after() != -1) {
2133 delivery_to_entries->at(entry->delivery_insert_after()).erase(entry);
2135 pair_entry_allocator_.FreeEntry(entry);
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>*
2145 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*
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)) {
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);
2159 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(
2160 empty_vehicle_type_curator_->Type(vehicle),
2161 vehicle_is_compatible)) {
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)
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);
2182 const std::optional<int64_t> insertion_cost =
2184 delivery_insert_after, vehicle);
2186 if (!insertion_cost.has_value())
return;
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));
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);
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()
2216 if (!insertion_cost.has_value()) {
2220 pair_entry->set_value(
CapSub(*insertion_cost, penalty_shift));
2223 DCHECK(priority_queue->
Contains(pair_entry));
2228bool GlobalCheapestInsertionFilteredHeuristic::InitializePositions(
2230 NodeEntryQueue* queue) {
2233 const int num_vehicles =
2234 vehicles.empty() ?
model()->vehicles() : vehicles.size();
2235 const bool all_vehicles = (num_vehicles ==
model()->vehicles());
2237 for (
int node : nodes.PositionsSetAtLeastOnce()) {
2242 if (gci_params_.add_unperformed_entries &&
2244 AddNodeEntry(node, node, -1, all_vehicles, queue);
2247 InitializeInsertionEntriesPerformingNode(node, vehicles, queue);
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());
2260 if (!gci_params_.use_neighbors_ratio_for_initialization) {
2261 auto vehicles_it = vehicles.begin();
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;
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);
2283 for (
int cost_class = 0; cost_class <
model()->GetCostClassesCount();
2285 for (
const int64_t insert_after :
2286 node_index_to_neighbors_by_cost_class_
2287 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, node)) {
2291 const int vehicle = node_index_to_vehicle_[insert_after];
2292 if (vehicle == -1 ||
2293 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {
2297 if (!IsCheapestClassRepresentative(vehicle))
continue;
2298 }
else if (!vehicles.contains(vehicle)) {
2301 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2306bool GlobalCheapestInsertionFilteredHeuristic::UpdateAfterNodeInsertion(
2308 int64_t insert_after,
bool all_vehicles, NodeEntryQueue* queue) {
2311 if (!UpdateExistingNodeEntriesOnChain(nodes, vehicle, insert_after,
2312 Value(insert_after), all_vehicles,
2324 if (!AddNodeEntriesAfter(nodes, vehicle, node, all_vehicles, queue)) {
2327 SetVehicleIndex(node, vehicle);
2331bool GlobalCheapestInsertionFilteredHeuristic::UpdateExistingNodeEntriesOnChain(
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);
2343bool GlobalCheapestInsertionFilteredHeuristic::AddNodeEntriesAfter(
2345 bool all_vehicles, NodeEntryQueue* queue) {
2346 const int cost_class =
model()->GetCostClassIndexOfVehicle(vehicle).value();
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()) {
2355 for (
int node : neighbors) {
2357 if (!
Contains(node) && nodes[node]) {
2358 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
2363 for (
int node : nodes.PositionsSetAtLeastOnce()) {
2366 node_index_to_neighbors_by_cost_class_->IsNeighborhoodArcForCostClass(
2367 cost_class, insert_after, node)) {
2368 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);
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;
2383 const auto vehicle_is_compatible = [vehicle_var](
int vehicle) {
2384 return vehicle_var->Contains(vehicle);
2386 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(
2387 empty_vehicle_type_curator_->Type(vehicle),
2388 vehicle_is_compatible)) {
2392 const int num_allowed_vehicles = vehicle_var->Size();
2394 const int64_t penalty_shift =
2395 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)
2398 if (vehicle == -1) {
2399 DCHECK_EQ(node, insert_after);
2400 if (!all_vehicles) {
2406 queue->PushInsertion(node, node, -1, num_allowed_vehicles,
2407 CapSub(node_penalty, penalty_shift));
2411 const std::optional<int64_t> insertion_cost =
2414 if (!insertion_cost.has_value())
return;
2415 if (!all_vehicles && *insertion_cost > node_penalty) {
2421 queue->PushInsertion(node, insert_after, vehicle, num_allowed_vehicles,
2422 CapSub(*insertion_cost, penalty_shift));
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,
2430 const int num_nodes = path.size();
2431 DCHECK_GE(num_nodes, 2);
2432 const int kNoPrevIncrease = -1;
2433 const int kNoNextDecrease = num_nodes;
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;
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;
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];
2466 vehicle, {{.pred = path[pickup_pos], .node = pickup},
2467 {.pred = delivery_pred, .node = delivery}});
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) {
2477 append(pos, next_increase_[pos] - 1);
2478 append(pos, next_decrease_[pos] - 1);
2486 if (next_increase_[pos] - 1 != pos) {
2488 if (prev_decrease_[pos] != pos) append(prev_decrease_[pos], pos);
2492 append(pos, next_decrease_[pos] - 1);
2493 if (!is_before_increase && next_decrease_[pos] - 1 != pos) {
2502 if (prev_increase_[pos] != pos) append(prev_increase_[pos], pos);
2512 RoutingModel*
model, std::function<
bool()> stop_search,
2513 std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
2515 std::vector<RoutingSearchParameters::InsertionSortingProperty>
2516 insertion_sorting_properties,
2519 std::function<
bool(
const std::vector<RoutingModel::VariableValuePair>&,
2520 std::vector<RoutingModel::VariableValuePair>*)>
2521 optimize_on_insertion)
2523 std::move(evaluator), nullptr,
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() ==
2534 DCHECK(!insertion_sorting_properties_.empty());
2540 synchronize_insertion_optimizer_ =
true;
2544 if (hint !=
nullptr && use_first_solution_hint_) {
2546 for (
int i = 0; i <
model()->Nexts().size(); ++i) {
2549 if (element !=
nullptr && element->
Bound()) {
2555 ComputeInsertionOrder();
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) {
2565 in_state.push_back({i,
Value(i)});
2568 synchronize_insertion_optimizer_ =
false;
2571 in_state.push_back({index,
Value(index)});
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) {
2587std::vector<std::vector<int64_t>> ComputeStartToPickupCosts(
2588 const RoutingModel& model, absl::Span<const int64_t> pickups,
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);
2595 ProcessVehicleStartEndCosts(
2597 [&cost_from_start](int64_t cost,
int v) { cost_from_start[v] = cost; },
2598 vehicle_set,
false,
true);
2600 return pickup_costs;
2604std::vector<std::vector<int64_t>> ComputeDeliveryToEndCosts(
2605 const RoutingModel& model, absl::Span<const int64_t> deliveries,
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);
2612 ProcessVehicleStartEndCosts(
2614 [&cost_to_end](int64_t cost,
int v) { cost_to_end[v] = cost; },
2615 vehicle_set,
true,
false);
2617 return delivery_costs;
2624int64_t GetNegMaxDistanceFromVehicles(
const RoutingModel& model,
2626 const auto& [pickups, deliveries] =
2627 model.GetPickupAndDeliveryPairs()[pair_index];
2630 for (
int v = 0; v < model.vehicles(); ++v) vehicle_set.Set(v);
2633 const std::vector<std::vector<int64_t>> pickup_costs =
2634 ComputeStartToPickupCosts(model, pickups, vehicle_set);
2637 const std::vector<std::vector<int64_t>> delivery_costs =
2638 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);
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) {
2651 closest_vehicle_distance =
2652 std::min(closest_vehicle_distance,
2653 CapAdd(cost_from_start[v], cost_to_end[v]));
2655 max_pair_distance = std::max(max_pair_distance, closest_vehicle_distance);
2658 return CapOpp(max_pair_distance);
2666std::optional<int64_t> GetAvgPickupDeliveryPairDistanceFromVehicles(
2667 const RoutingModel& model,
int pair_index,
2669 const auto& [pickups, deliveries] =
2670 model.GetPickupAndDeliveryPairs()[pair_index];
2673 const std::vector<std::vector<int64_t>> pickup_costs =
2674 ComputeStartToPickupCosts(model, pickups, vehicle_set);
2677 const std::vector<std::vector<int64_t>> delivery_costs =
2678 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);
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) {
2693 distance_from_vehicle_sum =
2694 CapAdd(distance_from_vehicle_sum,
2695 CapAdd(cost_from_start[v], cost_to_end[v]));
2698 if (valid_vehicles > 0) {
2699 avg_pair_distance_sum =
CapAdd(
2700 distance_from_vehicle_sum / valid_vehicles, avg_pair_distance_sum);
2705 return valid_pairs > 0
2706 ? std::make_optional<int64_t>(avg_pair_distance_sum / valid_pairs)
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];
2720 max_capacity = std::max(max_capacity, capacity);
2723 return 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) {
2735 double dimension_usage_sum = 0;
2736 for (
const RoutingDimension* dimension : dimensions) {
2738 DCHECK(dimension->IsUnary());
2739 double dimension_usage_per_vehicle_sum = 0;
2740 int valid_vehicles = 0;
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);
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;
2757 if (valid_vehicles > 0) {
2760 dimension_usage_sum +=
2761 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);
2768 dimension_usage_sum);
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()) {
2780 const auto& [pickups, deliveries] =
2781 model.GetPickupAndDeliveryPairs()[pair_index];
2782 if (pickups.empty() || deliveries.empty()) {
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;
2791 for (
int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {
2792 const int64_t capacity = dimension->vehicle_capacities()[vehicle];
2793 if (capacity == 0)
continue;
2798 const RoutingModel::TransitCallback1& transit_evaluator =
2799 dimension->GetUnaryTransitEvaluator(vehicle);
2801 double pickup_sum = 0;
2802 for (int64_t pickup : pickups) {
2803 pickup_sum += 1.0 * std::abs(transit_evaluator(pickup)) / capacity;
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;
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);
2815 if (valid_vehicles > 0) {
2818 dimension_usage_sum +=
2819 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);
2826 dimension_usage_sum);
2830void LocalCheapestInsertionFilteredHeuristic::ComputeInsertionOrder() {
2831 if (use_random_insertion_order_) {
2832 if (insertion_order_.empty()) {
2834 insertion_order_.reserve(
model.Size() +
2835 model.GetPickupAndDeliveryPairs().size());
2836 for (
int pair_index = 0;
2837 pair_index <
model.GetPickupAndDeliveryPairs().size();
2839 insertion_order_.push_back(
2840 {.is_node_index =
false, .index = pair_index});
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});
2848 absl::c_shuffle(insertion_order_, rnd_);
2852 if (!insertion_order_.empty())
return;
2861 insertion_order_.reserve(
model.Size() +
2862 model.GetPickupAndDeliveryPairs().size());
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,
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());
2879 properties.push_back(-hint_weight);
2880 properties.push_back(-reversed_hint_weight);
2882 bool neg_min_distance_to_vehicles_appended =
false;
2883 for (
const int property : insertion_sorting_properties_) {
2886 properties.push_back(num_allowed_vehicles);
2889 properties.push_back(
CapOpp(penalty));
2891 case RoutingSearchParameters::
2892 SORTING_PROPERTY_PENALTY_OVER_ALLOWED_VEHICLES_RATIO:
2893 properties.push_back(
CapOpp(penalty / num_allowed_vehicles));
2895 case RoutingSearchParameters::
2896 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:
2897 properties.push_back(
CapOpp(avg_distance_to_vehicle));
2899 case RoutingSearchParameters::
2900 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:
2901 properties.push_back(avg_distance_to_vehicle);
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;
2909 properties.push_back(
CapOpp(avg_dimension_usage));
2913 <<
"Unknown RoutingSearchParameter::InsertionSortingProperty "
2923 if (!neg_min_distance_to_vehicles_appended) {
2924 properties.push_back(neg_min_distance_to_vehicles);
2932 bool compute_avg_pickup_delivery_pair_distance_from_vehicles =
false;
2933 bool compute_avg_dimension_usage =
false;
2935 insertion_sorting_properties_) {
2937 RoutingSearchParameters::
2938 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS ||
2940 RoutingSearchParameters::
2941 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS) {
2942 compute_avg_pickup_delivery_pair_distance_from_vehicles =
true;
2946 compute_avg_dimension_usage =
true;
2950 Bitset64<int> vehicle_set(
model.vehicles());
2951 for (
int v = 0; v <
model.vehicles(); ++v) vehicle_set.Set(v);
2953 const std::vector<RoutingDimension*> unary_dimensions =
2954 compute_avg_dimension_usage ?
model.GetUnaryDimensions()
2955 : std::vector<RoutingDimension*>();
2957 const int64_t max_dimension_capacity =
2958 compute_avg_dimension_usage
2959 ? GetMaxFiniteDimensionCapacity(
model, unary_dimensions)
2963 const std::vector<PickupDeliveryPair>& pairs =
2964 model.GetPickupAndDeliveryPairs();
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()));
2977 std::max(pickup_penalty,
model.UnperformedPenalty(pickup));
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()));
2987 std::max(delivery_penalty,
model.UnperformedPenalty(delivery));
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,
2996 : std::make_optional<int64_t>(0);
2998 if (!maybe_avg_pair_to_vehicle_cost.has_value()) {
3004 const int64_t avg_pair_dimension_usage =
3005 compute_avg_dimension_usage
3006 ? GetAvgPickupDeliveryPairUnaryDimensionUsage(
3007 model, unary_dimensions, max_dimension_capacity, pair_index)
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);
3016 insertion_order_.push_back({.properties = std::move(properties),
3018 .is_node_index =
false,
3019 .index = pair_index});
3022 for (
int node = 0; node <
model.Size(); ++node) {
3023 if (
model.IsStart(node) ||
model.IsEnd(node))
continue;
3025 int64_t min_distance = std::numeric_limits<int64_t>::max();
3026 int64_t sum_distance = 0;
3027 ProcessVehicleStartEndCosts(
3029 [&min_distance, &sum_distance](int64_t dist,
int) {
3030 min_distance = std::min(min_distance, dist);
3031 sum_distance =
CapAdd(dist, sum_distance);
3034 DCHECK_GT(vehicle_set.size(), 0);
3036 const int64_t avg_dimension_usage =
3037 compute_avg_dimension_usage
3038 ? GetAvgNodeUnaryDimensionUsage(
model, unary_dimensions,
3039 max_dimension_capacity, node)
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),
3046 insertion_order_.push_back({.properties = std::move(properties),
3048 .is_node_index =
true,
3052 absl::c_sort(insertion_order_, std::greater<Seed>());
3053 absl::c_reverse(insertion_order_);
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,
3069 if (
Evaluate(
true,
true).has_value()) {
3070 OptimizeOnInsertion(std::move(indices));
3076void LocalCheapestInsertionFilteredHeuristic::InsertBestPickupThenDelivery(
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) {
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},
3091 for (
const NodeInsertion& delivery_insertion :
3092 ComputeEvaluatorSortedPositionsOnRouteAfter(
3093 delivery, pickup,
Value(pickup_insertion.insert_after),
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);
3110void LocalCheapestInsertionFilteredHeuristic::InsertBestPair(
3112 for (
int pickup : pair.pickup_alternatives) {
3113 for (
int delivery : pair.delivery_alternatives) {
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);
3135void LocalCheapestInsertionFilteredHeuristic::InsertBestPairMultitour(
3137 using InsertionSequence = InsertionSequenceContainer::InsertionSequence;
3138 using Insertion = InsertionSequenceContainer::Insertion;
3140 std::vector<int> path;
3141 std::vector<bool> path_node_is_pickup;
3142 std::vector<bool> path_node_is_delivery;
3144 auto fill_path = [&path, &path_node_is_pickup, &path_node_is_delivery,
3145 this](
int vehicle) {
3147 path_node_is_pickup.clear();
3148 path_node_is_delivery.clear();
3149 const int start =
model()->Start(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));
3156 path.push_back(
end);
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
3169 :
Value(insertion.pred);
3170 hint_weight +=
IsHint(insertion.pred, insertion.node);
3171 hint_weight +=
IsHint(insertion.node, succ);
3174 sequence.Vehicle());
3177 insertion.node, insertion.pred, succ, sequence.Vehicle());
3180 previous_node = insertion.node;
3181 previous_succ = succ;
3188 sequence.Cost() = sequence_cost;
3189 sequence.SetHintWeight(hint_weight);
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());
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());
3206 for (
int pickup : pair.pickup_alternatives) {
3207 const IntVar* pickup_vehicle_var =
model()->VehicleVar(pickup);
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},
3223 insertion_generator_.AppendPickupDeliveryMultitourInsertions(
3224 pickup, delivery, vehicle, path, path_node_is_pickup,
3225 path_node_is_delivery, insertion_container_);
3228 price_insertion_sequences();
3230 insertion_container_.RemoveIf(
3231 [](
const InsertionSequence& sequence) ->
bool {
3234 insertion_container_.Sort();
3235 for (InsertionSequence sequence : insertion_container_) {
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
3243 :
Value(insertion.pred);
3244 InsertBetween(insertion.node, insertion.pred, succ, vehicle);
3245 previous_node = insertion.node;
3246 previous_succ = succ;
3251 if (MustUpdateBinCapacities()) {
3252 bin_capacities_->AddItemToBin(pickup, vehicle);
3253 bin_capacities_->AddItemToBin(delivery, vehicle);
3264 std::vector<bool>* data) {
3265 for (
const int64_t pickup : pair.pickup_alternatives) {
3266 data->at(pickup) =
false;
3268 for (
const int64_t delivery : pair.delivery_alternatives) {
3269 data->at(delivery) =
false;
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);
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) {
3297 pickup_contained =
true;
3301 bool delivery_contained =
false;
3302 for (int64_t delivery : deliveries) {
3304 delivery_contained =
true;
3308 ignore_pair_index[pair_index] = pickup_contained || delivery_contained;
3309 if (pickup_contained == delivery_contained) {
3314 SetFalseForAllAlternatives(pairs[pair_index], &insert_as_single_node);
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;
3323 const auto& pair = pairs[index];
3324 switch (pair_insertion_strategy_) {
3327 InsertBestPair(pair);
3330 InsertBestPickupThenDelivery(pair);
3333 InsertBestPairMultitour(pair);
3336 LOG(ERROR) <<
"Unknown pair insertion strategy value.";
3343 if (
Contains(index) || !insert_as_single_node[index]) {
3346 for (
const NodeInsertion& insertion :
3347 ComputeEvaluatorSortedPositions(index)) {
3352 Value(insertion.insert_after), insertion.vehicle);
3357 if (MustUpdateBinCapacities()) {
3358 bin_capacities_->AddItemToBin(index, insertion.vehicle);
3360 OptimizeOnInsertion(std::move(indices));
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);
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});
3387 insert_after = insert_before;
3391std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>
3392LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPositions(
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)) {
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_) {
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);
3419 for (
size_t i = old_num_insertions;
i < sorted_insertions.size(); ++
i) {
3420 CapAddTo(delta_cost, &sorted_insertions[i].value);
3424 absl::c_sort(sorted_insertions);
3425 return sorted_insertions;
3428std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>
3429LocalCheapestInsertionFilteredHeuristic::
3430 ComputeEvaluatorSortedPositionsOnRouteAfter(int64_t node, int64_t start,
3431 int64_t next_after_start,
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;
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},
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)) {
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);
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();
3486 bin_capacities_->RemoveItemFromBin(pickup, vehicle);
3487 bin_capacities_->RemoveItemFromBin(delivery, vehicle);
3489 sorted_pickup_delivery_insertions.push_back(
3490 {insert_pickup_after, insert_delivery_after, -hint_weight,
3491 total_cost, vehicle});
3493 insert_delivery_after = insert_delivery_before;
3495 insert_pickup_after = insert_pickup_before;
3498 absl::c_sort(sorted_pickup_delivery_insertions);
3499 return sorted_pickup_delivery_insertions;
3505 RoutingModel*
model, std::function<
bool()> stop_search,
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);
3526 std::vector<int> sorted_vehicles(
model()->vehicles(), 0);
3527 for (
int vehicle = 0; vehicle <
model()->vehicles(); ++vehicle) {
3528 sorted_vehicles[vehicle] = vehicle;
3530 absl::c_sort(sorted_vehicles,
3531 PartialRoutesAndLargeVehicleIndicesFirst(*
this));
3533 for (
const int vehicle : sorted_vehicles) {
3535 bool extend_route =
true;
3540 while (extend_route) {
3541 extend_route =
false;
3543 int64_t index = last_node;
3550 while (found && !
model()->IsEnd(index)) {
3552 std::vector<int64_t> neighbors;
3553 if (index <
model()->Nexts().size()) {
3554 std::unique_ptr<IntVarIterator> it(
3555 model()->Nexts()[index]->MakeDomainIterator(
false));
3557 neighbors = GetPossibleNextsFromIterator(index, next_values.begin(),
3560 for (
int i = 0; !found && i < neighbors.size(); ++i) {
3564 next = FindTopSuccessor(index, neighbors);
3567 SortSuccessors(index, &neighbors);
3568 ABSL_FALLTHROUGH_INTENDED;
3570 next = neighbors[i];
3572 if (
model()->IsEnd(next) && next !=
end) {
3576 if (!
model()->IsEnd(next) && !pickups[next].empty()) {
3577 bool contains_pickups =
false;
3578 for (int64_t pickup : pickups[next]) {
3580 contains_pickups =
true;
3584 if (!contains_pickups) {
3588 std::vector<int64_t> next_deliveries;
3589 if (next < deliveries.size()) {
3590 next_deliveries = GetPossibleNextsFromIterator(
3591 next, deliveries[next].
begin(), deliveries[next].
end());
3593 if (next_deliveries.empty()) next_deliveries = {
kUnassigned};
3594 for (
int j = 0; !found && j < next_deliveries.size(); ++j) {
3599 delivery = FindTopSuccessor(next, next_deliveries);
3602 SortSuccessors(next, &next_deliveries);
3603 ABSL_FALLTHROUGH_INTENDED;
3605 delivery = next_deliveries[j];
3609 SetNext(index, next, vehicle);
3610 if (!
model()->IsEnd(next)) {
3614 SetNext(next, delivery, vehicle);
3623 if (
model()->IsEnd(
end) && last_node != delivery) {
3624 last_node = delivery;
3625 extend_route =
true;
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;
3650 return has_partial_route2 < has_partial_route1;
3658 RoutingModel*
model, std::function<
bool()> stop_search,
3659 std::function<int64_t(int64_t, int64_t)> evaluator,
3663 evaluator_(
std::move(evaluator)) {}
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;
3679 return best_successor;
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) {
3689 values.push_back({evaluator_(node, successor), successor});
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);
3696 successors->clear();
3697 for (
auto value : values) {
3698 successors->push_back(value.second);
3706 RoutingModel*
model, std::function<
bool()> stop_search,
3711 comparator_(
std::move(comparator)) {}
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);
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);
3776template <
typename Saving>
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),
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);
3796 sorted_savings_.clear();
3797 costs_and_savings_per_arc_.clear();
3798 arc_indices_per_before_node_.clear();
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);
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;
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});
3827 CHECK(!sorted_) <<
"Container already sorted!";
3829 for (std::vector<Saving>& savings : sorted_savings_per_vehicle_type_) {
3830 absl::c_sort(savings);
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, -1});
3844 sorted_savings_.reserve(vehicle_types_ *
3845 costs_and_savings_per_arc_.size());
3847 for (
int arc_index = 0; arc_index < costs_and_savings_per_arc_.size();
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());
3855 [](
const std::pair<int64_t, Saving>& cs1,
3856 const std::pair<int64_t, Saving>& cs2) {
return cs1 > cs2; });
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();
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});
3875 index_in_sorted_savings_ = 0;
3880 return index_in_sorted_savings_ < sorted_savings_.size() ||
3881 HasReinjectedSavings();
3885 CHECK(sorted_) <<
"Calling GetSaving() before Sort() !";
3887 <<
"Update() should be called between two calls to GetSaving() !";
3891 if (HasReinjectedSavings()) {
3892 if (incoming_reinjected_savings_ !=
nullptr &&
3893 outgoing_reinjected_savings_ !=
nullptr) {
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;
3901 current_saving_ = outgoing_saving;
3902 using_incoming_reinjected_saving_ =
false;
3905 if (incoming_reinjected_savings_ !=
nullptr) {
3906 current_saving_ = incoming_reinjected_savings_->front();
3907 using_incoming_reinjected_saving_ =
true;
3909 if (outgoing_reinjected_savings_ !=
nullptr) {
3910 current_saving_ = outgoing_reinjected_savings_->front();
3911 using_incoming_reinjected_saving_ =
false;
3915 current_saving_ = sorted_savings_[index_in_sorted_savings_];
3917 return current_saving_.
saving;
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);
3926 if (!HasReinjectedSavings()) {
3927 index_in_sorted_savings_++;
3929 if (index_in_sorted_savings_ == sorted_savings_.size()) {
3930 sorted_savings_.swap(next_savings_);
3932 index_in_sorted_savings_ = 0;
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});
3940 UpdateReinjectedSavings();
3945 CHECK(!single_vehicle_type_);
3950 CHECK(sorted_) <<
"Savings not sorted yet!";
3951 CHECK_LT(type, vehicle_types_);
3952 return sorted_savings_per_vehicle_type_[type];
3956 CHECK(outgoing_new_reinjected_savings_ ==
nullptr);
3957 outgoing_new_reinjected_savings_ = &(skipped_savings_starting_at_[node]);
3961 CHECK(incoming_new_reinjected_savings_ ==
nullptr);
3962 incoming_new_reinjected_savings_ = &(skipped_savings_ending_at_[node]);
3966 struct SavingAndArc {
3970 bool operator<(
const SavingAndArc& other)
const {
3971 return std::tie(saving, arc_index) <
3972 std::tie(other.saving, other.arc_index);
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);
3985 if (!savings_db_->Contains(after_node)) {
3986 skipped_savings_ending_at_[after_node].push_back(saving_and_arc);
4000 void UpdateNextAndSkippedSavingsForArcWithType(int64_t arc_index,
int type) {
4001 if (single_vehicle_type_) {
4004 SkipSavingForArc(current_saving_);
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;
4014 if (previous_index >= 0) {
4016 DCHECK_GE(previous_type, 0);
4017 if (type == -1 || previous_type == type) {
4020 next_saving_added =
true;
4021 next_saving = next_savings_[previous_index].saving;
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) {
4030 next_savings_[previous_index] = {next_saving, arc_index};
4033 type_and_index.second = next_savings_.size();
4034 next_savings_.push_back({next_saving, arc_index});
4036 next_saving_added =
true;
4042 SkipSavingForArc(current_saving_);
4046 if (next_saving_added) {
4047 SkipSavingForArc({next_saving, arc_index});
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;
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) {
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;
4082 if (*reinjected_savings !=
nullptr) {
4083 (*reinjected_savings)->clear();
4085 *reinjected_savings =
nullptr;
4086 if (!new_reinjected_savings->empty()) {
4087 *reinjected_savings = new_reinjected_savings;
4091 bool HasReinjectedSavings() {
4092 return outgoing_reinjected_savings_ !=
nullptr ||
4093 incoming_reinjected_savings_ !=
nullptr;
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_) {
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});
4110 DCHECK_LT(index, costs_and_savings_per_arc_.size());
4111 costs_and_savings_per_arc_[index].push_back(cost_and_saving);
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];
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;
4127 costs_and_savings.pop_back();
4129 return found_saving;
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< int,
int>>
4138 next_saving_type_and_index_for_arc_;
4139 SavingAndArc current_saving_;
4140 std::vector<std::vector<std::pair< int64_t, Saving>>>
4141 costs_and_savings_per_arc_;
4142 std::vector<absl::flat_hash_map< int,
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_;
4160 RoutingModel*
model, std::function<
bool()> stop_search,
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);
4176 model()->GetVehicleTypeContainer());
4181 if (!ComputeSavings())
return false;
4187 if (!
Evaluate(
true).has_value())
return false;
4193 int type, int64_t before_node, int64_t after_node) {
4194 auto vehicle_is_compatible = [
this, before_node, after_node](
int vehicle) {
4201 SetNext(
model()->Start(vehicle), before_node, vehicle);
4202 SetNext(before_node, after_node, vehicle);
4208 ->GetCompatibleVehicleOfType(
4209 type, vehicle_is_compatible,
4210 [](
int) {
return false; })
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)) {
4221 (*adjacency_lists)[neighbor].push_back(node);
4224 absl::c_transform(*adjacency_lists, adjacency_lists->begin(),
4225 [](std::vector<int64_t> vec) {
4227 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
4243bool SavingsFilteredHeuristic::ComputeSavings() {
4245 const int size =
model()->Size();
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++) {
4251 uncontained_non_start_end_nodes.push_back(node);
4255 const int64_t saving_neighbors =
4256 std::min(MaxNumNeighborsPerNode(num_vehicle_types),
4257 static_cast<int64_t
>(uncontained_non_start_end_nodes.size()));
4260 std::make_unique<SavingsContainer<Saving>>(
this, num_vehicle_types);
4263 std::vector<std::vector<int64_t>> adjacency_lists(size);
4265 for (
int type = 0; type < num_vehicle_types; ++type) {
4268 if (vehicle < 0)
continue;
4270 const int64_t cost_class =
4271 model()->GetCostClassIndexOfVehicle(vehicle).value();
4272 const int64_t start =
model()->Start(vehicle);
4274 const int64_t fixed_cost =
model()->GetFixedCostOfVehicle(vehicle);
4278 for (
int before_node : uncontained_non_start_end_nodes) {
4279 std::vector<std::pair< int64_t, int64_t>>
4281 costed_after_nodes.reserve(uncontained_non_start_end_nodes.size());
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),
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);
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;
4303 if (savings_params_.add_reverse_arcs) {
4304 AddSymmetricArcsToAdjacencyLists(&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),
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)) {
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),
4326 const int64_t after_to_end_cost =
4327 model()->GetArcCostForClass(after_node,
end, cost_class);
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);
4339 BuildSaving(-saving_value, type, before_node, after_node);
4341 const int64_t total_cost =
4342 CapAdd(
CapAdd(start_to_before_cost, arc_cost), after_to_end_cost);
4353int64_t SavingsFilteredHeuristic::MaxNumNeighborsPerNode(
4354 int num_vehicle_types)
const {
4355 const int64_t size =
model()->Size();
4357 const int64_t num_neighbors_with_ratio =
4358 std::max(1.0, size * savings_params_.neighbors_ratio);
4364 const double max_memory_usage_in_savings_unit =
4365 savings_params_.max_memory_usage_bytes / 16;
4382 if (num_vehicle_types > 1) {
4383 multiplicative_factor += 1.5;
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));
4390 return std::min(num_neighbors_with_ratio,
4391 num_neighbors_with_memory_restriction);
4398 DCHECK_GT(vehicle_types, 0);
4399 const int size =
model()->Size();
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 =
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);
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);
4426 if (nodes_contained) {
4432 const int type = saving.vehicle_type;
4440 const int64_t start =
model()->Start(vehicle);
4445 const int saving_offset = type * size;
4447 while (in_index < in_savings_ptr[saving_offset + after_node].size() ||
4448 out_index < out_savings_ptr[saving_offset + before_node].size()) {
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;
4462 before_before_node = out_saving.before_node;
4465 after_after_node = in_saving.after_node;
4468 before_before_node =
4469 out_savings_ptr[saving_offset + before_node][out_index]
4473 if (after_after_node != -1) {
4474 DCHECK_EQ(before_before_node, -1);
4478 SetNext(after_node, after_after_node, vehicle);
4482 after_node = after_after_node;
4487 CHECK_GE(before_before_node, 0);
4489 if (!
Contains(before_before_node)) {
4490 SetNext(start, before_before_node, vehicle);
4491 SetNext(before_before_node, before_node, vehicle);
4494 before_node = before_before_node;
4508 const int64_t size =
model()->Size();
4509 const int vehicles =
model()->vehicles();
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);
4515 for (
int vehicle = 0; vehicle < vehicles; vehicle++) {
4516 const int64_t start =
model()->Start(vehicle);
4521 int64_t node =
Value(start);
4523 vehicle_of_first_or_last_node_[node] = vehicle;
4524 first_node_on_route_[vehicle] = node;
4526 int64_t next =
Value(node);
4527 while (next !=
end) {
4531 vehicle_of_first_or_last_node_[node] = vehicle;
4532 last_node_on_route_[vehicle] = node;
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;
4545 bool committed =
false;
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;
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];
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];
4574 if (before_node == last_node && after_node == first_node && v1 != v2 &&
4576 CHECK_EQ(
Value(before_node),
model()->End(v1));
4577 CHECK_EQ(
Value(
model()->Start(v2)), after_node);
4583 MergeRoutes(v1, v2, before_node, 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];
4592 if (before_node == last_node) {
4597 if (type != route_type) {
4605 SetNext(before_node, after_node, vehicle);
4608 if (first_node_on_route_[vehicle] != before_node) {
4610 DCHECK_NE(
Value(
model()->Start(vehicle)), before_node);
4611 vehicle_of_first_or_last_node_[before_node] = -1;
4613 vehicle_of_first_or_last_node_[after_node] = vehicle;
4614 last_node_on_route_[vehicle] = 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];
4625 if (after_node == first_node) {
4626 const int64_t start =
model()->Start(vehicle);
4627 CHECK_EQ(
Value(start), after_node);
4630 if (type != route_type) {
4638 SetNext(before_node, after_node, vehicle);
4639 SetNext(start, before_node, vehicle);
4641 if (last_node_on_route_[vehicle] != after_node) {
4643 DCHECK_NE(
Value(after_node),
model()->End(vehicle));
4644 vehicle_of_first_or_last_node_[after_node] = -1;
4646 vehicle_of_first_or_last_node_[before_node] = vehicle;
4647 first_node_on_route_[vehicle] = before_node;
4656void ParallelSavingsFilteredHeuristic::MergeRoutes(
int first_vehicle,
4658 int64_t before_node,
4659 int64_t after_node) {
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));
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;
4677 SetNext(before_node, after_node, used_vehicle);
4680 if (used_vehicle == first_vehicle) {
4681 SetNext(new_last_node,
model()->End(used_vehicle), used_vehicle);
4683 SetNext(
model()->Start(used_vehicle), new_first_node, used_vehicle);
4685 bool committed =
Evaluate(
true).has_value();
4687 model()->GetVehicleClassIndexOfVehicle(first_vehicle).value() !=
4688 model()->GetVehicleClassIndexOfVehicle(second_vehicle).value()) {
4690 std::swap(used_vehicle, unused_vehicle);
4691 SetNext(before_node, after_node, used_vehicle);
4694 if (used_vehicle == first_vehicle) {
4695 SetNext(new_last_node,
model()->End(used_vehicle), used_vehicle);
4697 SetNext(
model()->Start(used_vehicle), new_first_node, used_vehicle);
4699 committed =
Evaluate(
true).has_value();
4705 model()->GetVehicleClassIndexOfVehicle(unused_vehicle).value(),
4706 model()->GetFixedCostOfVehicle(unused_vehicle));
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;
4723 RoutingModel*
model, std::function<
bool()> stop_search,
4726 use_minimum_matching_(use_minimum_matching) {}
4730 const int size =
model()->Size() -
model()->vehicles() + 1;
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);
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);
4763 return std::min(cost, std::numeric_limits<int64_t>::max() / 2);
4765 using Cost =
decltype(cost);
4767 indices.size(), cost);
4768 if (use_minimum_matching_) {
4771 MatchingAlgorithm::MINIMUM_WEIGHT_MATCHING);
4773 if (christofides_solver.
Solve()) {
4774 path_per_cost_class[cost_class] =
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());
4789 const int end =
model()->End(vehicle);
4790 for (
int i = 1; i < path.size() - 1 && prev !=
end; ++i) {
4792 int next = indices[path[i]];
4811 SweepIndex(
const int64_t index,
const double angle,
const double distance)
4812 : index(index), angle(angle), distance(distance) {}
4813 ~SweepIndex() =
default;
4820struct SweepIndexSortAngle {
4821 bool operator()(
const SweepIndex& node1,
const SweepIndex& node2)
const {
4822 return (node1.angle < node2.angle);
4824} SweepIndexAngleComparator;
4826struct SweepIndexSortDistance {
4827 bool operator()(
const SweepIndex& node1,
const SweepIndex& node2)
const {
4828 return (node1.distance < node2.distance);
4830} SweepIndexDistanceComparator;
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;
4845 const double pi_rad = 3.14159265;
4847 const int x0 = coordinates_[0];
4848 const int y0 = coordinates_[1];
4850 std::vector<SweepIndex> sweep_indices;
4851 for (int64_t index = 0; index < static_cast<int>(coordinates_.size()) / 2;
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));
4862 absl::c_sort(sweep_indices, SweepIndexDistanceComparator);
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);
4874 for (
const SweepIndex& sweep_index : sweep_indices) {
4875 indices->push_back(sweep_index.index);
4882 Link(std::pair<int, int> link,
double value,
int vehicle_class,
4883 int64_t start_depot, int64_t end_depot)
4886 vehicle_class(vehicle_class),
4887 start_depot(start_depot),
4888 end_depot(end_depot) {}
4891 std::pair<int, int> link;
4894 int64_t start_depot;
4903class RouteConstructor {
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),
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),
4917 index_to_chain_index_(num_indices, -1),
4918 index_to_vehicle_class_index_(num_indices, -1) {
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]);
4927 cumuls_.resize(dimensions_.size());
4928 for (std::vector<int64_t>& cumuls : cumuls_) {
4929 cumuls.resize(num_indices_);
4931 new_possible_cumuls_.resize(dimensions_.size());
4934 ~RouteConstructor() =
default;
4937 model_->solver()->TopPeriodicCheck();
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;
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;
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());
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());
4974 const int route_index1 = in_route_[index1];
4975 const int route_index2 = in_route_[index2];
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;
4987 model_->solver()->TopPeriodicCheck();
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]);
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]);
5002 absl::c_sort(final_routes_, RouteComparator);
5004 const int extra_vehicles = std::max(
5005 0,
static_cast<int>(final_chains_.size()) - model_->vehicles());
5007 int chain_index = 0;
5008 for (chain_index = extra_vehicles; chain_index < final_chains_.size();
5010 if (chain_index - extra_vehicles >= model_->vehicles()) {
5013 const int start = final_chains_[chain_index].head;
5014 const int end = final_chains_[chain_index].tail;
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));
5025 for (
int route_index = 0; route_index < final_routes_.size();
5027 if (chain_index - extra_vehicles >= model_->vehicles()) {
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()) {
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));
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);
5058 enum MergeStatus { FIRST_SECOND, SECOND_FIRST, NO_MERGE };
5061 bool operator()(absl::Span<const int> route1,
5062 absl::Span<const int> route2)
const {
5063 return (route1.size() < route2.size());
5074 bool operator()(
const Chain& chain1,
const Chain& chain2)
const {
5075 return (chain1.nodes < chain2.nodes);
5079 bool Head(
int node)
const {
5080 return (node == routes_[in_route_[node]].front());
5083 bool Tail(
int node)
const {
5084 return (node == routes_[in_route_[node]].back());
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;
5098 if (it == route.end()) {
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);
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();
5113 if (available_cumul_next > dimension.CumulVar(next)->Max()) {
5116 if (available_cumul_next <= cumuls_[dimension_index][next]) {
5119 cumul = available_cumul_next;
5124 bool CheckRouteConnection(absl::Span<const int> route1,
5125 const std::vector<int>& route2,
int dimension_index,
5126 int64_t , 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;
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());
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);
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();
5154 bool feasible_route =
true;
5155 if (new_available_cumul_head2 > dimension.CumulVar(head2)->Max()) {
5158 if (new_available_cumul_head2 <= cumuls_[dimension_index][head2]) {
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];
5169 if (!feasible_route || (new_possible_cumul_tail2 +
5170 dimension.GetTransitValue(tail2, end_depot, 0) >
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))) {
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))) {
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);
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) {
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)),
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)),
5234 temp_assignment->Add(nexts_[
end]);
5235 temp_assignment->SetValue(nexts_[
end], model_->End(chain_index));
5238 return solver_->Solve(solver_->MakeRestoreAssignment(temp_assignment));
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);
5263 index_to_chain_index_[head1] = chain_index;
5264 index_to_chain_index_[tail2] = chain_index;
5265 chains_.push_back(chain);
5267 }
else if (chain_index1 >= 0 && chain_index2 < 0) {
5268 if (check_assignment_) {
5269 Assignment*
const temp_assignment =
5270 solver_->MakeAssignment(assignment_);
5272 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
5273 head1, tail1, head2, tail2);
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;
5281 }
else if (chain_index1 < 0 && chain_index2 >= 0) {
5282 if (check_assignment_) {
5283 Assignment*
const temp_assignment =
5284 solver_->MakeAssignment(assignment_);
5286 CheckTempAssignment(temp_assignment, chain_index2, chain_index1,
5287 head1, tail1, head2, tail2);
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;
5296 if (check_assignment_) {
5297 Assignment*
const temp_assignment =
5298 solver_->MakeAssignment(assignment_);
5300 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,
5301 head1, tail1, head2, tail2);
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);
5312 assignment_->Add(nexts_[tail1]);
5313 assignment_->SetValue(nexts_[tail1], head2);
5318 bool Merge(
bool merge,
int index1,
int index2) {
5320 if (UpdateAssignment(routes_[index1], routes_[index2])) {
5322 for (
const int node : routes_[index2]) {
5323 in_route_[node] = index1;
5324 routes_[index1].push_back(node);
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;
5334 deleted_routes_.insert(index2);
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_;
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_;
5367 SweepBuilder(RoutingModel*
const model,
bool check_assignment)
5368 : model_(model), check_assignment_(check_assignment) {}
5369 ~SweepBuilder()
override =
default;
5371 Decision*
Next(Solver*
const solver)
override {
5376 Assignment*
const assignment = solver->MakeAssignment();
5377 route_constructor_ = std::make_unique<RouteConstructor>(
5378 assignment, model_, check_assignment_, num_indices_, links_);
5380 route_constructor_->Construct();
5381 route_constructor_.reset(
nullptr);
5383 assignment->Restore();
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));
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) {
5405 Link(std::make_pair(first, second), 0, 0, depot, depot));
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_;
5420 bool check_assignment) {
5421 return model->solver()->RevAlloc(
new SweepBuilder(model, check_assignment));
5430class AllUnperformed :
public DecisionBuilder {
5433 explicit AllUnperformed(RoutingModel*
const model) : model_(model) {}
5434 ~AllUnperformed()
override =
default;
5435 Decision*
Next(Solver*
const )
override {
5438 model_->CostVar()->FreezeQueue();
5439 for (
int i = 0;
i < model_->Size(); ++
i) {
5440 if (!model_->IsStart(i)) {
5441 model_->ActiveVar(i)->SetValue(0);
5444 model_->CostVar()->UnfreezeQueue();
5449 RoutingModel*
const model_;
5454 return model->solver()->RevAlloc(
new AllUnperformed(model));
5459class GuidedSlackFinalizer :
public DecisionBuilder {
5461 GuidedSlackFinalizer(
const RoutingDimension* dimension, RoutingModel* model,
5462 std::function<int64_t(int64_t)> initializer);
5465 GuidedSlackFinalizer(
const GuidedSlackFinalizer&) =
delete;
5466 GuidedSlackFinalizer& operator=(
const GuidedSlackFinalizer&) =
delete;
5468 Decision*
Next(Solver* solver)
override;
5471 int64_t SelectValue(int64_t index);
5472 int64_t ChooseVariable();
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_;
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)),
5495 last_delta_used_(dimension->slacks().size(), 0) {}
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);
5507 const int64_t value = SelectValue(node_idx);
5508 IntVar*
const slack_variable = dimension_->SlackVar(node_idx);
5509 return solver->MakeAssignVariableValue(slack_variable, value);
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) +
5520 int64_t delta = last_delta_used_[index];
5524 while (std::abs(delta) < max_delta &&
5525 !slack_variable->Contains(center + delta)) {
5532 last_delta_used_.SetValue(model_->solver(), index, delta);
5533 return center + delta;
5536int64_t GuidedSlackFinalizer::ChooseVariable() {
5537 int64_t int_current_node = current_index_.Value();
5538 int64_t int_current_route = current_route_.Value();
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();
5545 if (!model_->IsEnd(int_current_node)) {
5548 int_current_route += 1;
5549 if (int_current_route < model_->vehicles()) {
5550 int_current_node = model_->Start(int_current_route);
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;
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)));
5573int64_t RoutingDimension::ShortestTransitionSlack(int64_t node)
const {
5574 CHECK_EQ(base_dimension_,
this);
5575 CHECK(!model_->IsEnd(node));
5579 const int64_t next = model_->NextVar(node)->Value();
5580 if (model_->IsEnd(next)) {
5581 return SlackVar(node)->Min();
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,
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);
5598 DCHECK_LE(next_cumul_min, optimal_next_cumul);
5599 DCHECK_LE(optimal_next_cumul, next_cumul_max);
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 =
5609 ->StateDependentTransitCallback(
5610 state_dependent_class_evaluators_
5611 [state_dependent_vehicle_to_class_[serving_vehicle]])(node,
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;
5623class GreedyDescentLSOperator :
public LocalSearchOperator {
5625 explicit GreedyDescentLSOperator(std::vector<IntVar*> variables);
5628 GreedyDescentLSOperator(
const GreedyDescentLSOperator&) =
delete;
5629 GreedyDescentLSOperator& operator=(
const GreedyDescentLSOperator&) =
delete;
5631 bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta)
override;
5632 void Start(
const Assignment* assignment)
override;
5635 int64_t FindMaxDistanceToDomain(
const Assignment* assignment);
5637 const std::vector<IntVar*> variables_;
5638 const Assignment* center_;
5639 int64_t current_step_;
5646 int64_t current_direction_;
5649GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)
5650 : variables_(
std::move(variables)),
5653 current_direction_(0) {}
5655bool GreedyDescentLSOperator::MakeNextNeighbor(Assignment* delta,
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);
5673 current_direction_ = 0;
5678void GreedyDescentLSOperator::Start(
const Assignment* assignment) {
5679 CHECK(assignment !=
nullptr);
5680 current_step_ = FindMaxDistanceToDomain(assignment);
5681 center_ = assignment;
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)));
5695std::unique_ptr<LocalSearchOperator> RoutingModel::MakeGreedyDescentLSOperator(
5696 std::vector<IntVar*> variables) {
5697 return std::unique_ptr<LocalSearchOperator>(
5698 new GreedyDescentLSOperator(std::move(variables)));
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);
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));
5715 LocalSearchOperator*
const hill_climber =
5716 solver_->RevAlloc(
new GreedyDescentLSOperator(start_cumuls));
5717 LocalSearchPhaseParameters*
const parameters =
5718 solver_->MakeLocalSearchPhaseParameters(CostVar(), hill_climber,
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());
5725 DecisionBuilder*
const finalizer =
5726 solver_->MakeLocalSearchPhase(first_solution, parameters);
bool Contains(const T *val) const
void NoteChangedPriority(T *val)
const E & Element(const V *const var) const
E * AddAtPosition(V *var, int position)
const E * ElementPtrOrNull(const V *const var) const
void Copy(const Assignment *assignment)
AssignmentContainer< IntVar, IntVarElement > IntContainer
const IntContainer & IntVarContainer() const
int64_t ObjectiveValue() const
IndexType size() const
Returns how many bits this Bitset64 can hold.
void Set(IndexType i)
Sets the bit at position i to 1.
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
bool HasHintedNext(int node) 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)
std::vector< int > hint_prev_values_
bool IsHint(int node, int64_t next) const
std::vector< int > hint_next_values_
void InitializeSeedQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, SeedQueue *sq)
std::vector< EvaluatorCache > evaluator_cache_
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)
bool HasHintedPrev(int node) const
std::function< int64_t(int64_t)> penalty_evaluator_
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.
bool BuildSolutionInternal() override
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.
static constexpr Value PATH_MOST_CONSTRAINED_ARC
FirstSolutionStrategy_Value Value
nested types -------------------------------------------------—
static constexpr Value PATH_CHEAPEST_ARC
static constexpr Value PARALLEL_CHEAPEST_INSERTION
NodeEntryQueue(int num_nodes)
void PushInsertion(int64_t node, int64_t insert_after, int vehicle, int bucket, int64_t value)
bool IsEmpty(int64_t insert_after) const
void ClearInsertions(int64_t insert_after)
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_rejects() const
int64_t number_of_decisions() const
Returns statistics from its underlying heuristic.
std::string DebugString() const override
-------— Decision Builder -------—
Decision * Next(Solver *solver) override
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
— First solution decision builder —
bool HasSecondaryVars() const
Returns true if there are secondary variables.
Assignment *const assignment_
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.
Assignment * BuildSolution()
int64_t SecondaryVarIndex(int64_t index) const
Returns the index of a secondary var.
int64_t Value(int64_t index) const
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)
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
virtual void ResetVehicleIndices()
virtual void SetVehicleIndex(int64_t, int)
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 VehicleIsEmpty(int vehicle) const
void MakeDisjunctionNodesUnperformed(int64_t node)
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,.
RoutingModel * model() const
bool StopSearch() override
Returns true if the search must be stopped.
void AddUnassignedNodesToEmptyVehicles()
Adds all unassigned nodes to empty vehicles.
void MakePartiallyPerformedPairsUnperformed()
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 Update(bool update_best_saving, int type=-1)
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)
void UpdateWithType(int type)
void ReinjectSkippedSavingsEndingAt(int64_t node)
void ReinjectSkippedSavingsStartingAt(int64_t node)
virtual void BuildRoutesFromSavings()=0
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.
~SavingsFilteredHeuristic() override
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.
int64_t wall_time() const
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 —
void InsertOrDie(Collection *const collection, const typename Collection::value_type &value)
void STLClearObject(T *obj)
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).
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)
LocalSearchMetaheuristic_Value
const Assignment * SolveFromAssignmentWithAlternativeSolvers(const Assignment *assignment, RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters ¶meters, int max_non_improving_iterations)
Same as above, but taking an initial solution.
static const int kUnassigned
--— Routing model --—
DecisionBuilder * MakeSweepDecisionBuilder(RoutingModel *model, bool check_assignment)
double Cost
Basic non-strict type for cost. The speed penalty for using double is ~2%.
ClosedInterval::Iterator begin(ClosedInterval interval)
const Assignment * SolveWithAlternativeSolvers(RoutingModel *primary_model, const std::vector< RoutingModel * > &alternative_models, const RoutingSearchParameters ¶meters, int max_non_improving_iterations)
int64_t CapOpp(int64_t v)
Note(user): -kint64min != kint64max, but kint64max == ~kint64min.
inline ::absl::StatusOr< absl::Duration > DecodeGoogleApiProto(const google::protobuf::Duration &proto)
inline ::absl::StatusOr< google::protobuf::Duration > EncodeGoogleApiProto(absl::Duration d)
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).")
const bool prioritize_farthest_nodes
std::priority_queue< Seed, std::vector< Seed >, std::greater< Seed > > priority_queue
bool operator<(const Entry &other) const
static const int64_t kint64max