19#include "absl/container/flat_hash_set.h"
25 const std::vector<IntVar*>& vars,
26 const std::vector<IntVar*>& secondary_vars,
27 std::function<
int(
int64)> start_empty_path_class,
30 std::move(start_empty_path_class)),
31 arc_evaluator_(
std::move(arc_evaluator)) {}
38 if (chain_end == destination)
return false;
39 const int64 max_arc_value = arc_evaluator_(destination, chain_end);
42 if (
next == destination)
return false;
46 return MoveChainAndRepair(before_chain, chain_end, destination);
49bool MakeRelocateNeighborsOperator::MoveChainAndRepair(
int64 before_chain,
52 if (
MoveChain(before_chain, chain_end, destination)) {
55 int64 last = chain_end;
56 if (current == last) {
57 current = before_chain;
59 while (last >= 0 && !
IsPathStart(current) && current != last) {
60 last = Reposition(current, last);
61 current =
Prev(current);
69int64 MakeRelocateNeighborsOperator::Reposition(
int64 before_to_move,
71 const int64 kNoChange = -1;
72 const int64 to_move =
Next(before_to_move);
74 if (
Var(to_move)->Contains(
next)) {
79 while (prev != up_to) {
80 if (
Var(prev)->Contains(to_move) &&
Var(to_move)->Contains(
next)) {
87 if (
Var(prev)->Contains(to_move)) {
95 const std::vector<IntVar*>& vars,
96 const std::vector<IntVar*>& secondary_vars,
97 std::function<
int(
int64)> start_empty_path_class,
100 std::move(start_empty_path_class)),
102 inactive_pair_first_index_(0),
103 inactive_pair_second_index_(0),
107 while (inactive_pair_ < pairs_.size()) {
110 if (inactive_pair_first_index_ < pairs_[inactive_pair_].first.size() - 1) {
111 ++inactive_pair_first_index_;
112 }
else if (inactive_pair_second_index_ <
113 pairs_[inactive_pair_].second.size() - 1) {
114 inactive_pair_first_index_ = 0;
115 ++inactive_pair_second_index_;
117 inactive_pair_ = FindNextInactivePair(inactive_pair_ + 1);
118 inactive_pair_first_index_ = 0;
119 inactive_pair_second_index_ = 0;
132 return MakeActive(pairs_[inactive_pair_].second[inactive_pair_second_index_],
134 MakeActive(pairs_[inactive_pair_].first[inactive_pair_first_index_],
147void MakePairActiveOperator::OnNodeInitialization() {
148 inactive_pair_ = FindNextInactivePair(0);
149 inactive_pair_first_index_ = 0;
150 inactive_pair_second_index_ = 0;
153int MakePairActiveOperator::FindNextInactivePair(
int pair_index)
const {
155 if (!ContainsActiveNodes(pairs_[
index].first) &&
156 !ContainsActiveNodes(pairs_[
index].second)) {
160 return pairs_.size();
163bool MakePairActiveOperator::ContainsActiveNodes(
164 const std::vector<int64>& nodes)
const {
165 for (
int64 node : nodes) {
172 const std::vector<IntVar*>& vars,
173 const std::vector<IntVar*>& secondary_vars,
174 std::function<
int(
int64)> start_empty_path_class,
177 std::move(start_empty_path_class)) {
185 if (second_index < 0) {
193 const std::vector<IntVar*>& vars,
194 const std::vector<IntVar*>& secondary_vars,
195 std::function<
int(
int64)> start_empty_path_class,
198 std::move(start_empty_path_class)) {
208 int64 first_prev =
Prev(first_pair_node);
210 if (second_pair_node < 0 ||
IsPathEnd(second_pair_node) ||
214 const int64 second_prev =
Prev(second_pair_node);
216 const int64 first_node_destination =
BaseNode(kPairFirstNodeDestination);
217 if (first_node_destination == second_pair_node) {
222 const int64 second_node_destination =
BaseNode(kPairSecondNodeDestination);
223 if (second_prev == first_pair_node && first_node_destination == first_prev &&
224 second_node_destination == first_prev) {
234 if (second_pair_node == second_node_destination ||
235 first_pair_node == first_node_destination) {
238 const bool moved_second_pair_node =
239 MoveChain(second_prev, second_pair_node, second_node_destination);
242 const bool moved_first_pair_node =
243 MoveChain(
Prev(first_pair_node), first_pair_node, first_node_destination);
248 return moved_first_pair_node || moved_second_pair_node;
254 if (base_index == kPairSecondNodeDestination) {
255 return BaseNode(kPairFirstNodeDestination);
262 const std::vector<IntVar*>& vars,
263 const std::vector<IntVar*>& secondary_vars,
264 std::function<
int(
int64)> start_empty_path_class,
267 std::move(start_empty_path_class)) {
276 if (sibling1 == -1)
return false;
278 if (node2 == sibling1)
return false;
280 if (sibling2 == -1)
return false;
285 const bool ok =
MoveChain(prev1, node1, node2);
290 const std::vector<IntVar*>& vars,
291 const std::vector<IntVar*>& secondary_vars,
292 std::function<
int(
int64)> start_empty_path_class,
295 std::move(start_empty_path_class)) {
301 int64 prev1, sibling1, sibling_prev1 = -1;
302 if (!GetPreviousAndSibling(node1, &prev1, &sibling1, &sibling_prev1)) {
306 int64 prev2, sibling2, sibling_prev2 = -1;
307 if (!GetPreviousAndSibling(node2, &prev2, &sibling2, &sibling_prev2)) {
312 if (node1 == prev2) {
314 if (sibling_prev1 == node2) sibling_prev1 = node1;
315 if (sibling_prev2 == node2) sibling_prev2 = node1;
316 }
else if (node2 == prev1) {
318 if (sibling_prev1 == node1) sibling_prev1 = node2;
319 if (sibling_prev2 == node1) sibling_prev2 = node2;
322 if (sibling_prev1 == node1) {
323 sibling_prev1 = node2;
324 }
else if (sibling_prev1 == node2) {
325 sibling_prev1 = node1;
327 if (sibling_prev2 == node1) {
328 sibling_prev2 = node2;
329 }
else if (sibling_prev2 == node2) {
330 sibling_prev2 = node1;
333 if (!status)
return false;
335 if (sibling1 == sibling_prev2) {
336 status =
MoveChain(sibling_prev2, sibling2, sibling_prev1);
337 }
else if (sibling2 == sibling_prev1) {
338 status =
MoveChain(sibling_prev1, sibling1, sibling_prev2);
340 status =
MoveChain(sibling_prev1, sibling1, sibling2) &&
341 MoveChain(sibling_prev2, sibling2, sibling_prev1);
351bool PairExchangeOperator::GetPreviousAndSibling(
353 int64* sibling_previous)
const {
355 *previous =
Prev(node);
357 *sibling_previous = *sibling >= 0 ?
Prev(*sibling) : -1;
358 return *sibling_previous >= 0;
362 const std::vector<IntVar*>& vars,
363 const std::vector<IntVar*>& secondary_vars,
364 std::function<
int(
int64)> start_empty_path_class,
367 std::move(start_empty_path_class)) {
373 StartNode(kSecondPairSecondNodeDestination));
375 StartNode(kFirstPairFirstNodeDestination));
377 StartNode(kFirstPairSecondNodeDestination));
388 nodes[0][0] =
BaseNode(kFirstPairFirstNode);
389 nodes[1][0] =
BaseNode(kSecondPairFirstNode);
390 if (nodes[1][0] <= nodes[0][0]) {
395 if (!GetPreviousAndSibling(nodes[0][0], &prev[0][0], &nodes[0][1],
400 if (!GetPreviousAndSibling(nodes[1][0], &prev[1][0], &nodes[1][1],
406 if (!LoadAndCheckDest(0, 0, kFirstPairFirstNodeDestination, nodes, dest)) {
410 if (!LoadAndCheckDest(0, 1, kFirstPairSecondNodeDestination, nodes, dest)) {
414 if (
StartNode(kSecondPairFirstNodeDestination) !=
416 !LoadAndCheckDest(1, 0, kSecondPairFirstNodeDestination, nodes, dest)) {
420 if (!LoadAndCheckDest(1, 1, kSecondPairSecondNodeDestination, nodes, dest)) {
425 if (!MoveNode(0, 1, nodes, dest, prev)) {
429 if (!MoveNode(0, 0, nodes, dest, prev)) {
433 if (!MoveNode(1, 1, nodes, dest, prev)) {
436 if (!MoveNode(1, 0, nodes, dest, prev)) {
442bool PairExchangeRelocateOperator::MoveNode(
int pair,
int node,
445 if (!
MoveChain(prev[pair][node], nodes[pair][node], dest[pair][node])) {
449 if (prev[1 - pair][0] == dest[pair][node]) {
450 prev[1 - pair][0] = nodes[pair][node];
452 if (prev[1 - pair][1] == dest[pair][node]) {
453 prev[1 - pair][1] = nodes[pair][node];
458bool PairExchangeRelocateOperator::LoadAndCheckDest(
int pair,
int node,
461 int64 dest[2][2])
const {
462 dest[pair][node] =
BaseNode(base_node);
464 return !(nodes[0][0] == dest[pair][node] || nodes[0][1] == dest[pair][node] ||
465 nodes[1][0] == dest[pair][node] || nodes[1][1] == dest[pair][node]);
472 return base_index == kFirstPairFirstNodeDestination ||
473 base_index == kFirstPairSecondNodeDestination ||
474 base_index == kSecondPairSecondNodeDestination;
478 if (base_index == kFirstPairSecondNodeDestination ||
479 base_index == kSecondPairSecondNodeDestination) {
486bool PairExchangeRelocateOperator::GetPreviousAndSibling(
488 int64* sibling_previous)
const {
490 *previous =
Prev(node);
492 *sibling_previous = *sibling >= 0 ?
Prev(*sibling) : -1;
493 return *sibling_previous >= 0;
497 const std::vector<IntVar*>& vars,
const std::vector<IntVar*>& path_vars,
498 std::function<
int(
int64)> start_empty_path_class,
501 index_pairs_(index_pairs),
505 number_of_nexts_(vars.size()),
506 ignore_path_vars_(path_vars.empty()) {
507 if (!ignore_path_vars_) {
514 const int64 kNoPath = -1;
519 if (pair_index_ < index_pairs_.size()) {
521 ignore_path_vars_ ? 0LL :
Value(first_active_ + number_of_nexts_);
522 const int64 prev_first = prevs_[first_active_];
523 const int64 next_first =
Value(first_active_);
525 SetNext(first_active_, first_active_, kNoPath);
527 const int64 insert_first = index_pairs_[pair_index_].first[first_index_];
528 SetNext(prev_first, insert_first, path);
529 SetNext(insert_first, next_first, path);
530 int64 prev_second = prevs_[second_active_];
531 if (prev_second == first_active_) {
532 prev_second = insert_first;
536 :
Value(second_active_ + number_of_nexts_));
537 const int64 next_second =
Value(second_active_);
539 SetNext(second_active_, second_active_, kNoPath);
541 const int64 insert_second =
542 index_pairs_[pair_index_].second[second_index_];
543 SetNext(prev_second, insert_second, path);
544 SetNext(insert_second, next_second, path);
547 if (second_index_ >= index_pairs_[pair_index_].second.size()) {
550 if (first_index_ >= index_pairs_[pair_index_].first.size()) {
569 prevs_.resize(number_of_nexts_, -1);
572 if (
next >= prevs_.size()) prevs_.resize(
next + 1, -1);
581 if (!UpdateActiveNodes())
break;
582 if (first_active_ != -1 && second_active_ != -1) {
589bool SwapIndexPairOperator::UpdateActiveNodes() {
590 if (pair_index_ < index_pairs_.size()) {
591 for (
const int64 first : index_pairs_[pair_index_].first) {
592 if (
Value(first) != first) {
593 first_active_ = first;
597 for (
const int64 second : index_pairs_[pair_index_].second) {
598 if (
Value(second) != second) {
599 second_active_ = second;
609 const std::vector<IntVar*>& vars,
610 const std::vector<IntVar*>& secondary_vars,
611 std::function<
int(
int64)> start_empty_path_class,
614 std::move(start_empty_path_class)),
621 while (inactive_node_ <
Size()) {
644void IndexPairSwapActiveOperator::OnNodeInitialization() {
646 for (
int i = 0; i <
Size(); ++i) {
652 inactive_node_ =
Size();
658 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
659 bool keep_inverse_values)
661 keep_inverse_values),
662 model_(*heuristic->
model()),
663 removed_nodes_(model_.Size()),
664 heuristic_(
std::move(heuristic)),
665 consider_vehicle_vars_(!model_.CostsAreHomogeneousAcrossVehicles()) {
666 if (consider_vehicle_vars_) {
671bool FilteredHeuristicLocalSearchOperator::MakeOneNeighbor() {
675 if (MakeChangesAndInsertNodes()) {
682bool FilteredHeuristicLocalSearchOperator::MakeChangesAndInsertNodes() {
685 const std::function<
int64(
int64)> next_accessor =
687 if (next_accessor ==
nullptr) {
690 const Assignment*
const result_assignment =
691 heuristic_->BuildSolutionFromRoutes(next_accessor);
693 if (result_assignment ==
nullptr) {
697 bool has_change =
false;
698 const std::vector<IntVarElement>& elements =
699 result_assignment->IntVarContainer().elements();
705 const IntVarElement& node_element = elements[node_index];
708 const int64 new_node_value = node_element.Value();
711 const int64 vehicle_var_index = VehicleVarIndex(node_index);
712 if (
OldValue(node_index) != new_node_value ||
713 (consider_vehicle_vars_ &&
OldValue(vehicle_var_index) != vehicle)) {
715 SetValue(node_index, new_node_value);
716 if (consider_vehicle_vars_) {
717 SetValue(vehicle_var_index, vehicle);
720 node_index = new_node_value;
726 const IntVarElement& node_element = elements[node];
728 if (node_element.Value() == node) {
732 if (consider_vehicle_vars_) {
733 const int64 vehicle_var_index = VehicleVarIndex(node);
745 std::unique_ptr<RoutingFilteredHeuristic> heuristic)
749 just_started_(false) {}
751void FilteredHeuristicPathLNSOperator::OnStart() {
754 last_route_ = current_route_;
755 if (CurrentRouteIsEmpty()) {
756 IncrementCurrentRouteToNextNonEmpty();
758 just_started_ =
true;
761bool FilteredHeuristicPathLNSOperator::IncrementPosition() {
763 just_started_ =
false;
764 return !CurrentRouteIsEmpty();
766 IncrementCurrentRouteToNextNonEmpty();
767 return current_route_ != last_route_;
770bool FilteredHeuristicPathLNSOperator::CurrentRouteIsEmpty()
const {
774void FilteredHeuristicPathLNSOperator::IncrementCurrentRouteToNextNonEmpty() {
777 ++current_route_ %= num_routes;
778 if (current_route_ == last_route_) {
782 }
while (CurrentRouteIsEmpty());
786FilteredHeuristicPathLNSOperator::SetupNextAccessorForNeighbor() {
791 while (node != end_node) {
796 return [
this, start_node, end_node](
int64 node) {
797 if (node == start_node)
return end_node;
806 std::unique_ptr<RoutingFilteredHeuristic> heuristic)
808 route_to_relocate_index_(0),
809 empty_route_index_(0),
810 just_started_(false) {}
812void RelocatePathAndHeuristicInsertUnperformedOperator::OnStart() {
813 has_unperformed_nodes_ =
false;
815 routes_to_relocate_.clear();
816 empty_routes_.clear();
817 std::vector<bool> empty_vehicle_of_vehicle_class_added(
822 has_unperformed_nodes_ =
true;
833 routes_to_relocate_.push_back(vehicle);
836 const int vehicle_class =
838 if (!empty_vehicle_of_vehicle_class_added[vehicle_class]) {
839 empty_routes_.push_back(vehicle);
840 empty_vehicle_of_vehicle_class_added[vehicle_class] =
true;
844 if (empty_route_index_ >= empty_routes_.size()) {
845 empty_route_index_ = 0;
847 if (route_to_relocate_index_ >= routes_to_relocate_.size()) {
848 route_to_relocate_index_ = 0;
850 last_empty_route_index_ = empty_route_index_;
851 last_route_to_relocate_index_ = route_to_relocate_index_;
853 just_started_ =
true;
856bool RelocatePathAndHeuristicInsertUnperformedOperator::IncrementPosition() {
857 if (!has_unperformed_nodes_ || empty_routes_.empty() ||
858 routes_to_relocate_.empty()) {
862 just_started_ =
false;
865 return IncrementRoutes();
868bool RelocatePathAndHeuristicInsertUnperformedOperator::IncrementRoutes() {
869 ++empty_route_index_ %= empty_routes_.size();
870 if (empty_route_index_ != last_empty_route_index_) {
873 ++route_to_relocate_index_ %= routes_to_relocate_.size();
874 return route_to_relocate_index_ != last_route_to_relocate_index_;
877std::function<
int64(
int64)> RelocatePathAndHeuristicInsertUnperformedOperator::
878 SetupNextAccessorForNeighbor() {
879 const int empty_route = empty_routes_[empty_route_index_];
880 const int relocated_route = routes_to_relocate_[route_to_relocate_index_];
891 const int64 first_relocated_node =
OldValue(relocated_route_start);
892 const int64 last_relocated_node = last_node_on_route_[relocated_route];
895 return [
this, empty_start_node, empty_end_node, first_relocated_node,
896 last_relocated_node, relocated_route_start,
897 relocated_route_end](
int64 node) {
898 if (node == relocated_route_start)
return relocated_route_end;
899 if (node == empty_start_node)
return first_relocated_node;
900 if (node == last_relocated_node)
return empty_end_node;
908 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
int num_close_nodes)
911 pickup_delivery_pairs_(model_.GetPickupAndDeliveryPairs()),
914 close_nodes_(model_.Size()),
915 new_nexts_(model_.Size()),
916 changed_nexts_(model_.Size()),
917 new_prevs_(model_.Size()),
918 changed_prevs_(model_.Size()) {
920 const int64 max_num_neighbors =
922 const int64 num_closest_neighbors =
923 std::min<int64>(num_close_nodes, max_num_neighbors);
926 if (num_closest_neighbors == 0)
return;
930 for (
int64 node = 0; node < size; node++) {
933 std::vector<std::pair< double,
int64>> costed_after_nodes;
934 costed_after_nodes.reserve(size);
935 for (
int64 after_node = 0; after_node < size; after_node++) {
937 after_node == node) {
940 double total_cost = 0.0;
943 for (
int cost_class = 1; cost_class < num_cost_classes; cost_class++) {
946 costed_after_nodes.emplace_back(total_cost, after_node);
949 std::nth_element(costed_after_nodes.begin(),
950 costed_after_nodes.begin() + num_closest_neighbors - 1,
951 costed_after_nodes.end());
952 std::vector<int64>& neighbors = close_nodes_[node];
953 neighbors.reserve(num_closest_neighbors);
955 neighbors.push_back(costed_after_nodes[
index].second);
960void FilteredHeuristicCloseNodesLNSOperator::OnStart() {
961 last_node_ = current_node_;
962 just_started_ =
true;
965bool FilteredHeuristicCloseNodesLNSOperator::IncrementPosition() {
967 just_started_ =
false;
971 return current_node_ != last_node_;
974void FilteredHeuristicCloseNodesLNSOperator::RemoveNode(
int64 node) {
980 const int64 prev = Prev(node);
982 changed_nexts_.
Set(prev);
983 new_nexts_[prev] =
next;
986 new_prevs_[
next] = prev;
990void FilteredHeuristicCloseNodesLNSOperator::RemoveNodeAndActiveSibling(
992 if (!IsActive(node))
return;
995 for (
int64 sibling_node : GetActiveSiblings(node)) {
997 RemoveNode(sibling_node);
1002std::vector<int64> FilteredHeuristicCloseNodesLNSOperator::GetActiveSiblings(
1007 std::vector<int64> active_siblings;
1009 for (
int64 sibling_delivery :
1010 pickup_delivery_pairs_[index_pair.first].second) {
1011 if (IsActive(sibling_delivery)) {
1012 active_siblings.push_back(sibling_delivery);
1017 for (std::pair<int64, int64> index_pair :
1019 for (
int64 sibling_pickup :
1020 pickup_delivery_pairs_[index_pair.first].first) {
1021 if (IsActive(sibling_pickup)) {
1022 active_siblings.push_back(sibling_pickup);
1027 return active_siblings;
1031FilteredHeuristicCloseNodesLNSOperator::SetupNextAccessorForNeighbor() {
1040 RemoveNodeAndActiveSibling(current_node_);
1042 for (
int64 neighbor : close_nodes_[current_node_]) {
1043 RemoveNodeAndActiveSibling(neighbor);
1046 return [
this](
int64 node) {
return Next(node); };
1053 std::unique_ptr<RoutingFilteredHeuristic> heuristic,
1054 int num_arcs_to_consider,
1059 num_arcs_to_consider_(num_arcs_to_consider),
1060 current_expensive_arc_indices_({-1, -1}),
1061 arc_cost_for_route_start_(std::move(arc_cost_for_route_start)),
1062 just_started_(
false) {
1066void FilteredHeuristicExpensiveChainLNSOperator::OnStart() {
1067 last_route_ = current_route_;
1068 just_started_ =
true;
1071bool FilteredHeuristicExpensiveChainLNSOperator::IncrementPosition() {
1072 if (just_started_) {
1073 just_started_ =
false;
1074 return FindMostExpensiveChainsOnRemainingRoutes();
1077 if (IncrementCurrentArcIndices())
return true;
1079 return IncrementRoute() && FindMostExpensiveChainsOnRemainingRoutes();
1083FilteredHeuristicExpensiveChainLNSOperator::SetupNextAccessorForNeighbor() {
1084 const int first_arc_index = current_expensive_arc_indices_.first;
1085 const int second_arc_index = current_expensive_arc_indices_.second;
1087 DCHECK_LT(first_arc_index, second_arc_index);
1088 DCHECK_LT(second_arc_index, most_expensive_arc_starts_and_ranks_.size());
1090 const std::pair<int, int>& first_start_and_rank =
1091 most_expensive_arc_starts_and_ranks_[first_arc_index];
1092 const std::pair<int, int>& second_start_and_rank =
1093 most_expensive_arc_starts_and_ranks_[second_arc_index];
1094 int64 before_chain, after_chain;
1095 if (first_start_and_rank.second < second_start_and_rank.second) {
1096 before_chain = first_start_and_rank.first;
1097 after_chain =
OldValue(second_start_and_rank.first);
1099 before_chain = second_start_and_rank.first;
1100 after_chain =
OldValue(first_start_and_rank.first);
1103 int node =
Value(before_chain);
1104 while (node != after_chain) {
1109 return [
this, before_chain, after_chain](
int64 node) {
1110 if (node == before_chain)
return after_chain;
1115bool FilteredHeuristicExpensiveChainLNSOperator::IncrementRoute() {
1117 return current_route_ != last_route_;
1120bool FilteredHeuristicExpensiveChainLNSOperator::IncrementCurrentArcIndices() {
1121 int& second_index = current_expensive_arc_indices_.second;
1122 if (++second_index < most_expensive_arc_starts_and_ranks_.size()) {
1125 int& first_index = current_expensive_arc_indices_.first;
1126 if (first_index + 2 < most_expensive_arc_starts_and_ranks_.size()) {
1128 second_index = first_index + 1;
1139bool FindMostExpensiveArcsOnRoute(
1140 int num_arcs,
int64 start,
const std::function<
int64(
int64)>& next_accessor,
1141 const std::function<
bool(
int64)>& is_end,
1143 std::vector<std::pair<int64, int>>* most_expensive_arc_starts_and_ranks,
1144 std::pair<int, int>* first_expensive_arc_indices) {
1145 if (is_end(next_accessor(start))) {
1147 *first_expensive_arc_indices = {-1, -1};
1153 using ArcCostNegativeRankStart = std::tuple<int64, int, int64>;
1154 std::priority_queue<ArcCostNegativeRankStart,
1155 std::vector<ArcCostNegativeRankStart>,
1156 std::greater<ArcCostNegativeRankStart>>
1159 int64 before_node = start;
1161 while (!is_end(before_node)) {
1162 const int64 after_node = next_accessor(before_node);
1163 const int64 arc_cost =
1164 arc_cost_for_route_start(before_node, after_node, start);
1165 arc_info_pq.emplace(arc_cost, -rank, before_node);
1167 before_node = after_node;
1170 if (rank > num_arcs) {
1178 most_expensive_arc_starts_and_ranks->resize(arc_info_pq.size());
1179 int arc_index = arc_info_pq.size() - 1;
1180 while (!arc_info_pq.empty()) {
1181 const ArcCostNegativeRankStart& arc_info = arc_info_pq.top();
1182 (*most_expensive_arc_starts_and_ranks)[arc_index] = {
1183 std::get<2>(arc_info), -std::get<1>(arc_info)};
1188 *first_expensive_arc_indices = {0, 1};
1194bool FilteredHeuristicExpensiveChainLNSOperator::
1195 FindMostExpensiveChainsOnRemainingRoutes() {
1197 if (FindMostExpensiveArcsOnRoute(
1198 num_arcs_to_consider_,
model_.
Start(current_route_),
1199 [
this](
int64 i) { return OldValue(i); },
1200 [
this](
int64 node) { return model_.IsEnd(node); },
1201 arc_cost_for_route_start_, &most_expensive_arc_starts_and_ranks_,
1202 ¤t_expensive_arc_indices_)) {
1205 }
while (IncrementRoute());
1211 const std::vector<IntVar*>& vars,
1212 const std::vector<IntVar*>& secondary_vars,
1213 std::function<
int(
int64)> start_empty_path_class,
int num_arcs_to_consider,
1216 std::move(start_empty_path_class)),
1217 num_arcs_to_consider_(num_arcs_to_consider),
1219 current_expensive_arc_indices_({-1, -1}),
1220 arc_cost_for_path_start_(std::move(arc_cost_for_path_start)),
1222 has_non_empty_paths_to_explore_(
false) {
1227 const int first_arc_index = current_expensive_arc_indices_.first;
1228 const int second_arc_index = current_expensive_arc_indices_.second;
1230 DCHECK_LT(first_arc_index, second_arc_index);
1231 DCHECK_LT(second_arc_index, most_expensive_arc_starts_and_ranks_.size());
1233 const std::pair<int, int>& first_start_and_rank =
1234 most_expensive_arc_starts_and_ranks_[first_arc_index];
1235 const std::pair<int, int>& second_start_and_rank =
1236 most_expensive_arc_starts_and_ranks_[second_arc_index];
1237 if (first_start_and_rank.second < second_start_and_rank.second) {
1239 second_start_and_rank.first,
BaseNode(0)) &&
1240 MoveChain(first_start_and_rank.first, second_start_and_rank.first,
1244 first_start_and_rank.first,
BaseNode(0)) &&
1245 MoveChain(second_start_and_rank.first, first_start_and_rank.first,
1250 while (has_non_empty_paths_to_explore_) {
1254 if (IncrementCurrentArcIndices()) {
1258 IncrementCurrentPath();
1259 has_non_empty_paths_to_explore_ =
1260 current_path_ != end_path_ &&
1261 FindMostExpensiveChainsOnRemainingPaths();
1269void RelocateExpensiveChain::OnNodeInitialization() {
1275 end_path_ = current_path_;
1276 has_non_empty_paths_to_explore_ = FindMostExpensiveChainsOnRemainingPaths();
1279void RelocateExpensiveChain::IncrementCurrentPath() {
1281 if (++current_path_ == num_paths) {
1286bool RelocateExpensiveChain::IncrementCurrentArcIndices() {
1287 int& second_index = current_expensive_arc_indices_.second;
1288 if (++second_index < most_expensive_arc_starts_and_ranks_.size()) {
1291 int& first_index = current_expensive_arc_indices_.first;
1292 if (first_index + 2 < most_expensive_arc_starts_and_ranks_.size()) {
1294 second_index = first_index + 1;
1300bool RelocateExpensiveChain::FindMostExpensiveChainsOnRemainingPaths() {
1302 if (FindMostExpensiveArcsOnRoute(
1303 num_arcs_to_consider_,
path_starts()[current_path_],
1306 arc_cost_for_path_start_, &most_expensive_arc_starts_and_ranks_,
1307 ¤t_expensive_arc_indices_)) {
1310 IncrementCurrentPath();
1311 }
while (current_path_ != end_path_);
1316 const std::vector<IntVar*>& vars,
1317 const std::vector<IntVar*>& secondary_vars,
1318 std::function<
int(
int64)> start_empty_path_class,
1322 std::move(start_empty_path_class)) {
1326 for (
int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
1327 for (
const int node : pairs[pair_index].first) {
1328 is_pickup_node_[node] =
true;
1329 pair_of_node_[node] = pair_index;
1331 for (
const int node : pairs[pair_index].second) {
1332 is_delivery_node_[node] =
true;
1333 pair_of_node_[node] = pair_index;
1336 opened_pairs_bitset_.resize(pairs.size(),
false);
1339bool RelocateSubtrip::RelocateSubTripFromPickup(
const int64 chain_first_node,
1340 const int64 insertion_node) {
1341 if (
IsPathEnd(insertion_node))
return false;
1342 if (
Prev(chain_first_node) == insertion_node)
1345 int num_opened_pairs = 0;
1347 rejected_nodes_ = {
Prev(chain_first_node)};
1348 subtrip_nodes_ = {insertion_node};
1349 int current = chain_first_node;
1351 if (current == insertion_node) {
1353 opened_pairs_bitset_.assign(opened_pairs_bitset_.size(),
false);
1356 const int pair = pair_of_node_[current];
1357 if (is_delivery_node_[current] && !opened_pairs_bitset_[pair]) {
1358 rejected_nodes_.push_back(current);
1360 subtrip_nodes_.push_back(current);
1361 if (is_pickup_node_[current]) {
1363 opened_pairs_bitset_[pair] =
true;
1364 }
else if (is_delivery_node_[current]) {
1366 opened_pairs_bitset_[pair] =
false;
1369 current =
Next(current);
1370 }
while (num_opened_pairs != 0 && !
IsPathEnd(current));
1372 rejected_nodes_.push_back(current);
1373 subtrip_nodes_.push_back(
Next(insertion_node));
1376 const int64 rejected_path =
Path(chain_first_node);
1377 for (
int i = 1; i < rejected_nodes_.size(); ++i) {
1378 SetNext(rejected_nodes_[i - 1], rejected_nodes_[i], rejected_path);
1380 const int64 insertion_path =
Path(insertion_node);
1381 for (
int i = 1; i < subtrip_nodes_.size(); ++i) {
1382 SetNext(subtrip_nodes_[i - 1], subtrip_nodes_[i], insertion_path);
1387bool RelocateSubtrip::RelocateSubTripFromDelivery(
const int64 chain_last_node,
1388 const int64 insertion_node) {
1389 if (
IsPathEnd(insertion_node))
return false;
1392 DCHECK(std::none_of(opened_pairs_bitset_.begin(), opened_pairs_bitset_.end(),
1393 [](
bool value) { return value; }));
1394 int num_opened_pairs = 0;
1396 rejected_nodes_ = {
Next(chain_last_node)};
1397 subtrip_nodes_ = {
Next(insertion_node)};
1398 int current = chain_last_node;
1400 if (current == insertion_node) {
1401 opened_pairs_bitset_.assign(opened_pairs_bitset_.size(),
false);
1404 const int pair = pair_of_node_[current];
1405 if (is_pickup_node_[current] && !opened_pairs_bitset_[pair]) {
1406 rejected_nodes_.push_back(current);
1408 subtrip_nodes_.push_back(current);
1409 if (is_delivery_node_[current]) {
1411 opened_pairs_bitset_[pair] =
true;
1412 }
else if (is_pickup_node_[current]) {
1414 opened_pairs_bitset_[pair] =
false;
1417 current =
Prev(current);
1418 }
while (num_opened_pairs != 0 && !
IsPathStart(current));
1420 if (current == insertion_node)
return false;
1421 rejected_nodes_.push_back(current);
1422 subtrip_nodes_.push_back(insertion_node);
1426 std::reverse(rejected_nodes_.begin(), rejected_nodes_.end());
1427 std::reverse(subtrip_nodes_.begin(), subtrip_nodes_.end());
1430 const int64 rejected_path =
Path(chain_last_node);
1431 for (
int i = 1; i < rejected_nodes_.size(); ++i) {
1432 SetNext(rejected_nodes_[i - 1], rejected_nodes_[i], rejected_path);
1434 const int64 insertion_path =
Path(insertion_node);
1435 for (
int i = 1; i < subtrip_nodes_.size(); ++i) {
1436 SetNext(subtrip_nodes_[i - 1], subtrip_nodes_[i], insertion_path);
1442 if (is_pickup_node_[
BaseNode(0)]) {
1444 }
else if (is_delivery_node_[
BaseNode(0)]) {
1452 const std::vector<IntVar*>& vars,
1453 const std::vector<IntVar*>& secondary_vars,
1454 std::function<
int(
int64)> start_empty_path_class,
1457 std::move(start_empty_path_class)) {
1461 for (
int pair_index = 0; pair_index < pairs.size(); ++pair_index) {
1462 for (
const int node : pairs[pair_index].first) {
1463 is_pickup_node_[node] =
true;
1464 pair_of_node_[node] = pair_index;
1466 for (
const int node : pairs[pair_index].second) {
1467 is_delivery_node_[node] =
true;
1468 pair_of_node_[node] = pair_index;
1471 opened_pairs_set_.resize(pairs.size(),
false);
1474void ExchangeSubtrip::SetPath(
const std::vector<int64>& path,
int path_id) {
1475 for (
int i = 1; i < path.size(); ++i) {
1476 SetNext(path[i - 1], path[i], path_id);
1481bool VectorContains(
const std::vector<int64>& values,
int64 target) {
1482 return std::find(values.begin(), values.end(), target) != values.end();
1487 if (pair_of_node_[
BaseNode(0)] == -1)
return false;
1488 if (pair_of_node_[
BaseNode(1)] == -1)
return false;
1494 if (!ExtractChainsAndCheckCanonical(
BaseNode(0), &rejects0_, &subtrip0_)) {
1499 if (!ExtractChainsAndCheckCanonical(
BaseNode(1), &rejects1_, &subtrip1_)) {
1505 if (VectorContains(rejects0_, subtrip1_.front()))
return false;
1506 if (VectorContains(rejects1_, subtrip0_.front()))
return false;
1507 if (VectorContains(subtrip0_, subtrip1_.front()))
return false;
1508 if (VectorContains(subtrip1_, subtrip0_.front()))
return false;
1512 path0_ = {
Prev(subtrip0_.front())};
1513 path1_ = {
Prev(subtrip1_.front())};
1514 const int64 last0 =
Next(subtrip0_.back());
1515 const int64 last1 =
Next(subtrip1_.back());
1516 const bool concatenated01 = last0 == subtrip1_.front();
1517 const bool concatenated10 = last1 == subtrip0_.front();
1519 if (is_delivery_node_[
BaseNode(0)]) std::swap(subtrip1_, rejects0_);
1520 path0_.insert(path0_.end(), subtrip1_.begin(), subtrip1_.end());
1521 path0_.insert(path0_.end(), rejects0_.begin(), rejects0_.end());
1522 path0_.push_back(last0);
1524 if (is_delivery_node_[
BaseNode(1)]) std::swap(subtrip0_, rejects1_);
1525 path1_.insert(path1_.end(), subtrip0_.begin(), subtrip0_.end());
1526 path1_.insert(path1_.end(), rejects1_.begin(), rejects1_.end());
1527 path1_.push_back(last1);
1530 if (concatenated01) {
1532 path1_.front() = path0_.back();
1533 }
else if (concatenated10) {
1535 path0_.front() = path1_.back();
1542 SetPath(path0_, path0_id);
1543 SetPath(path1_, path1_id);
1547bool ExchangeSubtrip::ExtractChainsAndCheckCanonical(
1548 int64 base_node, std::vector<int64>* rejects, std::vector<int64>* subtrip) {
1549 const bool extracted =
1550 is_pickup_node_[base_node]
1551 ? ExtractChainsFromPickup(base_node, rejects, subtrip)
1552 : ExtractChainsFromDelivery(base_node, rejects, subtrip);
1553 if (!extracted)
return false;
1555 return !is_delivery_node_[base_node] ||
1556 pair_of_node_[subtrip->front()] != pair_of_node_[subtrip->back()] ||
1560bool ExchangeSubtrip::ExtractChainsFromPickup(
int64 base_node,
1561 std::vector<int64>* rejects,
1562 std::vector<int64>* subtrip) {
1563 DCHECK(is_pickup_node_[base_node]);
1564 DCHECK(rejects->empty());
1565 DCHECK(subtrip->empty());
1568 opened_pairs_set_.assign(opened_pairs_set_.size(),
false);
1569 int num_opened_pairs = 0;
1570 int current = base_node;
1572 const int pair = pair_of_node_[current];
1573 if (is_delivery_node_[current] && !opened_pairs_set_[pair]) {
1574 rejects->push_back(current);
1576 subtrip->push_back(current);
1577 if (is_pickup_node_[current]) {
1579 opened_pairs_set_[pair] =
true;
1580 }
else if (is_delivery_node_[current]) {
1582 opened_pairs_set_[pair] =
false;
1585 current =
Next(current);
1586 }
while (num_opened_pairs != 0 && !
IsPathEnd(current));
1587 return num_opened_pairs == 0;
1590bool ExchangeSubtrip::ExtractChainsFromDelivery(
int64 base_node,
1591 std::vector<int64>* rejects,
1592 std::vector<int64>* subtrip) {
1593 DCHECK(is_delivery_node_[base_node]);
1594 DCHECK(rejects->empty());
1595 DCHECK(subtrip->empty());
1598 opened_pairs_set_.assign(opened_pairs_set_.size(),
false);
1599 int num_opened_pairs = 0;
1600 int current = base_node;
1602 const int pair = pair_of_node_[current];
1603 if (is_pickup_node_[current] && !opened_pairs_set_[pair]) {
1604 rejects->push_back(current);
1606 subtrip->push_back(current);
1607 if (is_delivery_node_[current]) {
1609 opened_pairs_set_[pair] =
true;
1610 }
else if (is_pickup_node_[current]) {
1612 opened_pairs_set_[pair] =
false;
1615 current =
Prev(current);
1616 }
while (num_opened_pairs != 0 && !
IsPathStart(current));
1617 if (num_opened_pairs != 0)
return false;
1618 std::reverse(rejects->begin(), rejects->end());
1619 std::reverse(subtrip->begin(), subtrip->end());
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
#define VLOG(verboselevel)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
bool MakeNeighbor() override
ExchangeSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
FilteredHeuristicCloseNodesLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_close_nodes)
FilteredHeuristicExpensiveChainLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_route_start)
Class of operators using a RoutingFilteredHeuristic to insert unperformed nodes after changes have be...
FilteredHeuristicLocalSearchOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic, bool keep_inverse_values=false)
virtual bool IncrementPosition()=0
virtual std::function< int64(int64)> SetupNextAccessorForNeighbor()=0
Virtual method to return the next_accessor to be passed to the heuristic to build a new solution.
SparseBitset removed_nodes_
Keeps track of removed nodes when making a neighbor.
const RoutingModel & model_
FilteredHeuristicPathLNSOperator(std::unique_ptr< RoutingFilteredHeuristic > heuristic)
bool MakeNeighbor() override
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
IndexPairSwapActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the...
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
bool MakeNeighbor() override
LightPairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool MakeNeighbor() override
MakePairActiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
MakePairInactiveOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool MakeNeighbor() override
bool MakeNeighbor() override
MakeRelocateNeighborsOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, RoutingTransitCallback2 arc_evaluator)
bool MakeNeighbor() override
PairExchangeOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool MakeNeighbor() override
bool OnSamePathAsPreviousBase(int64 base_index) override
Returns true if a base node has to be on the same path as the "previous" base node (base node of inde...
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
PairExchangeRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
bool MakeNeighbor() override
PairRelocateOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
int64 GetBaseNodeRestartPosition(int base_index) override
Returns the index of the node to which the base node of index base_index must be set to when it reach...
Base class of the local search operators dedicated to path modifications (a path is a set of nodes li...
int64 BaseAlternativeNode(int i) const
Returns the alternative node for the ith base node.
void AddPairAlternativeSets(const std::vector< std::pair< std::vector< int64 >, std::vector< int64 > > > &pair_alternative_sets)
Adds all sets of node alternatives of a vector of alternative pairs.
bool SwapActiveAndInactive(int64 active, int64 inactive)
Replaces active by inactive in the current path, making active inactive.
virtual void OnNodeInitialization()
Called by OnStart() after initializing node information.
int64 BaseNode(int i) const
Returns the ith base node of the operator.
bool IsInactive(int64 node) const
Returns true if node is inactive.
bool IsPathEnd(int64 node) const
Returns true if node is the last node on the path; defined by the fact that node is outside the range...
virtual void SetNextBaseToIncrement(int64 base_index)
Set the next base to increment on next iteration.
const std::vector< int64 > & path_starts() const
Returns the vector of path start nodes.
int64 OldNext(int64 node) const
void SetNext(int64 from, int64 to, int64 path)
Sets 'to' to be the node after 'from' on the given path.
bool MakeActive(int64 node, int64 destination)
Insert the inactive node after destination.
int64 Prev(int64 node) const
Returns the node before node in the current delta.
int64 StartNode(int i) const
Returns the start node of the ith base node.
int64 Next(int64 node) const
Returns the node after node in the current delta.
const int number_of_nexts_
void ResetPosition()
Reset the position of the operator to its position when Start() was last called; this can be used to ...
bool IsPathStart(int64 node) const
Returns true if node is the first node on the path.
int64 BaseSiblingAlternativeNode(int i) const
Returns the alternative node for the sibling of the ith base node.
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
bool MakeChainInactive(int64 before_chain, int64 chain_end)
Makes the nodes on the chain starting after before_chain and ending at chain_end inactive.
int64 Path(int64 node) const
Returns the index of the path to which node belongs in the current delta.
bool CheckChainValidity(int64 before_chain, int64 chain_end, int64 exclude) const
Returns true if the chain is a valid path without cycles from before_chain to chain_end and does not ...
int64 GetActiveAlternativeSibling(int node) const
Returns the active node in the alternative set of the sibling of the given node.
bool MoveChain(int64 before_chain, int64 chain_end, int64 destination)
Moves the chain starting after the node before_chain and ending at the node chain_end after the node ...
bool MakeNeighbor() override
RelocateExpensiveChain(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, int num_arcs_to_consider, std::function< int64(int64, int64, int64)> arc_cost_for_path_start)
bool MakeOneNeighbor() override
This method should not be overridden. Override MakeNeighbor() instead.
bool MakeNeighbor() override
RelocateSubtrip(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &pairs)
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
int64 Size() const
Returns the number of next variables in the model.
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
int vehicles() const
Returns the number of vehicle routes in the model.
int VehicleIndex(int64 index) const
Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/en...
int64 Start(int vehicle) const
Model inspection.
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
void Set(IntegerType index)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
void OnStart() override
Called by Start() after synchronizing the operator with the current assignment.
bool MakeNextNeighbor(Assignment *delta, Assignment *deltadelta) override
Redefines MakeNextNeighbor to export a simpler interface.
SwapIndexPairOperator(const std::vector< IntVar * > &vars, const std::vector< IntVar * > &path_vars, std::function< int(int64)> start_empty_path_class, const RoutingIndexPairs &index_pairs)
std::string DebugString() const override
void RevertChanges(bool incremental)
IntVar * Var(int64 index) const
Returns the variable of given index.
const int64 & OldValue(int64 index) const
bool ApplyChanges(Assignment *delta, Assignment *deltadelta) const
void AddVars(const std::vector< IntVar * > &vars)
const int64 & Value(int64 index) const
Returns the value in the current assignment of the variable of given index.
void SetValue(int64 index, const int64 &value)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::function< int64(int64, int64)> RoutingTransitCallback2
std::vector< RoutingIndexPair > RoutingIndexPairs