1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

20

21#include <algorithm>

22#include <cmath>

23#include <cstdint>

24#include <cstdlib>

25#include <deque>

26#include <functional>

27#include <limits>

28#include <map>

29#include <memory>

30#include <optional>

31#include <set>

32#include <string>

33#include <tuple>

34#include <utility>

35#include <vector>

36

37#include "absl/algorithm/container.h"

38#include "absl/base/attributes.h"

39#include "absl/container/btree_set.h"

40#include "absl/container/flat_hash_map.h"

41#include "absl/container/flat_hash_set.h"

42#include "absl/container/inlined_vector.h"

43#include "absl/flags/flag.h"

44#include "absl/log/check.h"

45#include "absl/log/die_if_null.h"

46#include "absl/log/log.h"

47#include "absl/strings/str_cat.h"

48#include "absl/strings/string_view.h"

49#include "absl/time/time.h"

50#include "absl/types/span.h"

71

74}

75

76ABSL_FLAG(bool, routing_shift_insertion_cost_by_penalty, true,

77 "Shift insertion costs by the penalty of the inserted node(s).");

78

80 "The number of sectors the space is divided into before it is sweeped"

81 " by the ray.");

82

84

85namespace {

86void ConvertAssignment(const RoutingModel* src_model, const Assignment* src,

87 const RoutingModel* dst_model, Assignment* dst) {

88 DCHECK_EQ(src_model->Nexts().size(), dst_model->Nexts().size());

89 DCHECK_NE(src, nullptr);

90 DCHECK_EQ(src_model->solver(), src->solver());

91 DCHECK_EQ(dst_model->solver(), dst->solver());

92 for (int i = 0; i < src_model->Nexts().size(); i++) {

93 IntVar* const dst_next_var = dst_model->NextVar(i);

94 if (!dst->Contains(dst_next_var)) {

95 dst->Add(dst_next_var);

96 }

97 dst->SetValue(dst_next_var, src->Value(src_model->NextVar(i)));

98 }

99}

100

101bool AreAssignmentsEquivalent(const RoutingModel& model,

104 for (IntVar* next_var : model.Nexts()) {

105 if (assignment1.Value(next_var) != assignment2.Value(next_var)) {

106 return false;

107 }

108 }

109 return true;

110}

111

113 return search_parameters.has_time_limit()

115 .value()

116 : absl::InfiniteDuration();

117}

118

119

120

121

122bool UpdateTimeLimits(Solver* solver, int64_t start_time_ms,

123 absl::Duration time_limit,

125 if (!search_parameters.has_time_limit()) return true;

126 const absl::Duration elapsed_time =

127 absl::Milliseconds(solver->wall_time() - start_time_ms);

128 const absl::Duration time_left =

129 std::min(time_limit - elapsed_time, GetTimeLimit(search_parameters));

130 if (time_left <= absl::ZeroDuration()) return false;

132 time_left, search_parameters.mutable_time_limit());

133 DCHECK_OK(status);

134 return true;

135}

136}

137

147

157

267

268

269

298

320

332

367

368

369

370

371

372

373

385

426

427

428

429

430

434

447

451

455

460

461

462

463

464

486

496

509

541

590

596

597bool IntVarFilteredHeuristic::FilterAccept(bool ignore_upper_bound) {

598 if (!filter_manager_) return true;

600 return filter_manager_->Accept(

601 monitor, delta_, empty_, std::numeric_limits<int64_t>::min(),

602 ignore_upper_bound ? std::numeric_limits<int64_t>::max()

603 : objective_upper_bound_);

604}

605

606

607

618

622

623

624 start_chain_ends_.resize(model()->vehicles());

625 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {

626 int64_t node = model()->Start(vehicle);

627 while (!model()->IsEnd(node) && Var(node)->Bound()) {

628 const int64_t next = Var(node)->Min();

629 SetNext(node, next, vehicle);

631 node = next;

632 }

633 start_chain_ends_[vehicle] = node;

634 }

635

637

638

639

640 for (int vehicle = 0; vehicle < model()->vehicles(); ++vehicle) {

641 int64_t node = start_chain_ends_[vehicle];

642 if (!model()->IsEnd(node)) {

643 int64_t next = end_chain_starts_[vehicle];

644 SetNext(node, next, vehicle);

646 node = next;

647 while (!model()->IsEnd(node)) {

648 next = Var(node)->Min();

649 SetNext(node, next, vehicle);

651 node = next;

652 }

653 }

654 }

655

656 if (!Evaluate(true).has_value()) {

658 return false;

659 }

660 return true;

661}

662

671

695

707

749

750

751

761

762namespace {

763void ProcessVehicleStartEndCosts(

765 const std::function<void(int64_t, int)>& process_cost,

766 const Bitset64<int>& vehicle_set, bool ignore_start = false,

767 bool ignore_end = false) {

768 const auto start_end_cost = [&model, ignore_start, ignore_end](int64_t node,

769 int v) {

770 const int64_t start_cost =

772 const int64_t end_cost =

774 return CapAdd(start_cost, end_cost);

775 };

776

777

778

779

780 const IntVar* const vehicle_var = model.VehicleVar(node);

781 if (vehicle_var->Size() < vehicle_set.size()) {

782 std::unique_ptr<IntVarIterator> it(vehicle_var->MakeDomainIterator(false));

783 for (const int v : InitAndGetValues(it.get())) {

784 if (v < 0 || !vehicle_set[v]) {

785 continue;

786 }

787 process_cost(start_end_cost(node, v), v);

788 }

789 } else {

790 for (const int v : vehicle_set) {

791 if (!vehicle_var->Contains(v)) continue;

792 process_cost(start_end_cost(node, v), v);

793 }

794 }

795}

796}

797

798std::vector<std::vector<CheapestInsertionFilteredHeuristic::StartEndValue>>

833

854

866

880

881int64_t

896

897std::optional<int64_t>

909

910std::optional<int64_t>

935

943

944

945

966

967bool GlobalCheapestInsertionFilteredHeuristic::CheckVehicleIndices() const {

968 std::vector<bool> node_is_visited(model()->Size(), false);

970 for (int node = model()->Start(v); !model()->IsEnd(node);

971 node = Value(node)) {

972 if (node_index_to_vehicle_[node] != v) {

973 return false;

974 }

975 node_is_visited[node] = true;

976 }

977 }

978

979 for (int node = 0; node < model()->Size(); node++) {

980 if (!node_is_visited[node] && node_index_to_vehicle_[node] != -1) {

981 return false;

982 }

983 }

984

985 return true;

986}

987

1088

1089bool GlobalCheapestInsertionFilteredHeuristic::

1090 InsertPairsAndNodesByRequirementTopologicalOrder() {

1091 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

1093 for (const std::vector<int>& types :

1094 model()->GetTopologicallySortedVisitTypes()) {

1095 for (int type : types) {

1096 std::map<int64_t, std::vector<int>> pairs_to_insert_by_bucket;

1097 for (int index : model()->GetPairIndicesOfType(type)) {

1098 pairs_to_insert_by_bucket[GetBucketOfPair(pickup_delivery_pairs[index])]

1099 .push_back(index);

1100 }

1101 if (!InsertPairs(pairs_to_insert_by_bucket)) return false;

1102 std::map<int64_t, std::vector<int>> nodes_by_bucket;

1103 for (int node : model()->GetSingleNodesOfType(type)) {

1104 nodes_by_bucket[GetBucketOfNode(node)].push_back(node);

1105 }

1106 if (!InsertNodesOnRoutes(nodes_by_bucket, {})) return false;

1107 }

1108 }

1109 return true;

1110}

1111

1112bool GlobalCheapestInsertionFilteredHeuristic::

1113 InsertPairsAndNodesByPrecedenceTopologicalOrder() {

1114 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

1116 for (const std::vector<std::vector<int>>& ordered_nodes :

1117 model()->GetTopologicallySortedNodePrecedences()) {

1118 for (const std::vector<int>& nodes : ordered_nodes) {

1119 std::map<int64_t, std::vector<int>> pairs_to_insert_by_bucket;

1120 for (int node : nodes) {

1121 if (Contains(node)) continue;

1122 if (!model()->IsPickup(node) && !model()->IsDelivery(node)) continue;

1123 const std::optional<RoutingModel::PickupDeliveryPosition>

1125 if (pickup_position.has_value()) {

1126 const int index = pickup_position->pd_pair_index;

1127 pairs_to_insert_by_bucket[GetBucketOfPair(

1128 pickup_delivery_pairs[index])]

1129 .push_back(index);

1130 }

1131 const std::optional<RoutingModel::PickupDeliveryPosition>

1133 if (delivery_position.has_value()) {

1134 const int index = delivery_position->pd_pair_index;

1135 pairs_to_insert_by_bucket[GetBucketOfPair(

1136 pickup_delivery_pairs[index])]

1137 .push_back(index);

1138 }

1139 }

1140 if (!InsertPairs(pairs_to_insert_by_bucket)) return false;

1141 std::map<int64_t, std::vector<int>> nodes_by_bucket;

1142 for (int node : nodes) {

1143 if (Contains(node)) continue;

1144 nodes_by_bucket[GetBucketOfNode(node)].push_back(node);

1145 }

1146 if (!InsertNodesOnRoutes(nodes_by_bucket, {})) return false;

1147 }

1148 }

1149 return true;

1150}

1151

1152bool GlobalCheapestInsertionFilteredHeuristic::InsertPairs(

1153 const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket) {

1154 AdjustablePriorityQueue<PairEntry> priority_queue;

1155 std::vector<PairEntries> pickup_to_entries;

1156 std::vector<PairEntries> delivery_to_entries;

1157 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

1159 auto pair_is_performed = [this, &pickup_delivery_pairs](int pair_index) {

1160 const auto& [pickups, deliveries] = pickup_delivery_pairs[pair_index];

1161 for (int64_t pickup : pickups) {

1162 if (Contains(pickup)) return true;

1163 }

1164 for (int64_t delivery : deliveries) {

1165 if (Contains(delivery)) return true;

1166 }

1167 return false;

1168 };

1169 absl::flat_hash_set<int> pair_indices_to_insert;

1170 for (const auto& [bucket, pair_indices] : pair_indices_by_bucket) {

1171 for (const int pair_index : pair_indices) {

1172 if (!pair_is_performed(pair_index)) {

1173 pair_indices_to_insert.insert(pair_index);

1174 }

1175 }

1176 if (!InitializePairPositions(pair_indices_to_insert, &priority_queue,

1177 &pickup_to_entries, &delivery_to_entries)) {

1178 return false;

1179 }

1180 while (!priority_queue.IsEmpty()) {

1181 if (StopSearchAndCleanup(&priority_queue)) {

1182 return false;

1183 }

1184 PairEntry* const entry = priority_queue.Top();

1185 const int64_t pickup = entry->pickup_to_insert();

1186 const int64_t delivery = entry->delivery_to_insert();

1188 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,

1189 &delivery_to_entries);

1190 continue;

1191 }

1192

1193 const int entry_vehicle = entry->vehicle();

1194 if (entry_vehicle == -1) {

1195

1196 SetNext(pickup, pickup, -1);

1197 SetNext(delivery, delivery, -1);

1198 if (!Evaluate(true).has_value()) {

1199 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,

1200 &delivery_to_entries);

1201 }

1202 continue;

1203 }

1204

1205

1206 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle)) {

1207 if (!InsertPairEntryUsingEmptyVehicleTypeCurator(

1208 pair_indices_to_insert, entry, &priority_queue,

1209 &pickup_to_entries, &delivery_to_entries)) {

1210 return false;

1211 }

1212

1213

1214 continue;

1215 }

1216

1217 const int64_t pickup_insert_after = entry->pickup_insert_after();

1218 const int64_t pickup_insert_before = Value(pickup_insert_after);

1219 InsertBetween(pickup, pickup_insert_after, pickup_insert_before);

1220

1221 const int64_t delivery_insert_after = entry->delivery_insert_after();

1222 const int64_t delivery_insert_before = (delivery_insert_after == pickup)

1223 ? pickup_insert_before

1224 : Value(delivery_insert_after);

1225 InsertBetween(delivery, delivery_insert_after, delivery_insert_before);

1226 if (Evaluate(true).has_value()) {

1227 if (!UpdateAfterPairInsertion(

1228 pair_indices_to_insert, entry_vehicle, pickup,

1229 pickup_insert_after, delivery, delivery_insert_after,

1230 &priority_queue, &pickup_to_entries, &delivery_to_entries)) {

1231 return false;

1232 }

1233 } else {

1234 DeletePairEntry(entry, &priority_queue, &pickup_to_entries,

1235 &delivery_to_entries);

1236 }

1237 }

1238

1239

1240 for (auto it = pair_indices_to_insert.begin(),

1241 last = pair_indices_to_insert.end();

1242 it != last;) {

1243 if (pair_is_performed(*it)) {

1244 pair_indices_to_insert.erase(it++);

1245 } else {

1246 ++it;

1247 }

1248 }

1249 }

1250 return true;

1251}

1252

1253bool GlobalCheapestInsertionFilteredHeuristic::

1254 InsertPairEntryUsingEmptyVehicleTypeCurator(

1255 const absl::flat_hash_set<int>& pair_indices,

1256 GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,

1257 AdjustablePriorityQueue<

1258 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*

1259 priority_queue,

1260 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1261 pickup_to_entries,

1262 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1263 delivery_to_entries) {

1264 const int entry_vehicle = pair_entry->vehicle();

1265 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle));

1266

1267

1268

1269

1270

1271 const int64_t pickup = pair_entry->pickup_to_insert();

1272 const int64_t delivery = pair_entry->delivery_to_insert();

1273 const int64_t entry_fixed_cost =

1275 auto vehicle_is_compatible = [this, entry_fixed_cost, pickup,

1276 delivery](int vehicle) {

1277 if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {

1278 return false;

1279 }

1280

1282 const int64_t end = model()->End(vehicle);

1285 return Evaluate(true).has_value();

1286 };

1287

1288

1289

1290

1291 auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {

1293 };

1294 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =

1295 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(

1296 empty_vehicle_type_curator_->Type(entry_vehicle),

1297 vehicle_is_compatible, stop_and_return_vehicle);

1298 if (compatible_vehicle >= 0) {

1299

1300 const int64_t vehicle_start = model()->Start(compatible_vehicle);

1301 const int num_previous_vehicle_entries =

1302 pickup_to_entries->at(vehicle_start).size() +

1303 delivery_to_entries->at(vehicle_start).size();

1304 if (!UpdateAfterPairInsertion(

1305 pair_indices, compatible_vehicle, pickup, vehicle_start, delivery,

1306 pickup, priority_queue, pickup_to_entries, delivery_to_entries)) {

1307 return false;

1308 }

1309 if (compatible_vehicle != entry_vehicle) {

1310

1311

1312

1313

1314

1315 DCHECK(

1316 num_previous_vehicle_entries == 0 ||

1317 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=

1318 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());

1319 return true;

1320 }

1321

1322

1323

1324 const int new_empty_vehicle =

1325 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(

1326 empty_vehicle_type_curator_->Type(compatible_vehicle));

1327

1328 if (new_empty_vehicle >= 0) {

1330

1331

1332

1333

1334

1335 const int64_t new_empty_vehicle_start = model()->Start(new_empty_vehicle);

1336 const std::vector<PairEntry*> to_remove(

1337 pickup_to_entries->at(new_empty_vehicle_start).begin(),

1338 pickup_to_entries->at(new_empty_vehicle_start).end());

1339 for (PairEntry* entry : to_remove) {

1340 DeletePairEntry(entry, priority_queue, pickup_to_entries,

1341 delivery_to_entries);

1342 }

1343 if (!AddPairEntriesWithPickupAfter(

1344 pair_indices, new_empty_vehicle, new_empty_vehicle_start,

1345 -1, priority_queue,

1346 pickup_to_entries, delivery_to_entries)) {

1347 return false;

1348 }

1349 }

1350 } else if (next_fixed_cost_empty_vehicle >= 0) {

1351

1352

1353

1354 DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));

1355

1356

1357 pair_entry->set_vehicle(next_fixed_cost_empty_vehicle);

1358 pickup_to_entries->at(pair_entry->pickup_insert_after()).erase(pair_entry);

1359 pair_entry->set_pickup_insert_after(

1360 model()->Start(next_fixed_cost_empty_vehicle));

1361 pickup_to_entries->at(pair_entry->pickup_insert_after()).insert(pair_entry);

1362 DCHECK_EQ(pair_entry->delivery_insert_after(), pickup);

1363 if (!UpdatePairEntry(pair_entry, priority_queue)) {

1364 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,

1365 delivery_to_entries);

1366 }

1367 } else {

1368 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,

1369 delivery_to_entries);

1370 }

1371

1372 return true;

1373}

1374

1490

1491bool GlobalCheapestInsertionFilteredHeuristic::InsertNodesOnRoutes(

1492 const std::map<int64_t, std::vector<int>>& nodes_by_bucket,

1493 const absl::flat_hash_set<int>& vehicles) {

1495 SparseBitset<int> nodes_to_insert(model()->Size());

1496 for (const auto& [bucket, nodes] : nodes_by_bucket) {

1497 for (int node : nodes) {

1498 nodes_to_insert.Set(node);

1499 }

1500 if (!InitializePositions(nodes_to_insert, vehicles, &queue)) {

1501 return false;

1502 }

1503

1504

1505

1506

1507

1508

1509 const bool all_vehicles =

1510 vehicles.empty() || vehicles.size() == model()->vehicles();

1511

1512 while (!queue.IsEmpty()) {

1515 const int64_t node_to_insert = node_entry->node_to_insert;

1516 if (Contains(node_to_insert)) {

1517 queue.Pop();

1518 continue;

1519 }

1520

1521 const int entry_vehicle = node_entry->vehicle;

1522 if (entry_vehicle == -1) {

1523 DCHECK(all_vehicles);

1524

1525 SetNext(node_to_insert, node_to_insert, -1);

1526 if (!Evaluate(true).has_value()) {

1527 queue.Pop();

1528 }

1529 continue;

1530 }

1531

1532

1533 if (UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles)) {

1534 DCHECK(all_vehicles);

1535 if (!InsertNodeEntryUsingEmptyVehicleTypeCurator(

1536 nodes_to_insert, all_vehicles, &queue)) {

1537 return false;

1538 }

1539 continue;

1540 }

1541

1542 const int64_t insert_after = node_entry->insert_after;

1544 if (Evaluate(true).has_value()) {

1545 if (!UpdateAfterNodeInsertion(nodes_to_insert, entry_vehicle,

1546 node_to_insert, insert_after,

1547 all_vehicles, &queue)) {

1548 return false;

1549 }

1550 } else {

1551 queue.Pop();

1552 }

1553 }

1554

1555

1556 std::vector<int> non_inserted_nodes;

1557 non_inserted_nodes.reserve(

1558 nodes_to_insert.NumberOfSetCallsWithDifferentArguments());

1559 for (int node : nodes_to_insert.PositionsSetAtLeastOnce()) {

1560 if (!Contains(node)) non_inserted_nodes.push_back(node);

1561 }

1562 nodes_to_insert.ResetAllToFalse();

1563 for (int node : non_inserted_nodes) {

1564 nodes_to_insert.Set(node);

1565 }

1566 }

1567 return true;

1568}

1569

1570bool GlobalCheapestInsertionFilteredHeuristic::

1571 InsertNodeEntryUsingEmptyVehicleTypeCurator(const SparseBitset<int>& nodes,

1572 bool all_vehicles,

1573 NodeEntryQueue* queue) {

1575 const int entry_vehicle = node_entry->vehicle;

1576 DCHECK(UseEmptyVehicleTypeCuratorForVehicle(entry_vehicle, all_vehicles));

1578

1579

1580

1581

1582

1583

1584 const int64_t node_to_insert = node_entry->node_to_insert;

1585 const int bucket = node_entry->bucket;

1586 const int64_t entry_fixed_cost =

1588 auto vehicle_is_compatible = [this, entry_fixed_cost,

1589 node_to_insert](int vehicle) {

1590 if (model()->GetFixedCostOfVehicle(vehicle) != entry_fixed_cost) {

1591 return false;

1592 }

1593

1596 model()->End(vehicle), vehicle);

1597 return Evaluate(true).has_value();

1598 };

1599

1600

1601

1602

1603 auto stop_and_return_vehicle = [this, entry_fixed_cost](int vehicle) {

1605 };

1606 const auto [compatible_vehicle, next_fixed_cost_empty_vehicle] =

1607 empty_vehicle_type_curator_->GetCompatibleVehicleOfType(

1608 empty_vehicle_type_curator_->Type(entry_vehicle),

1609 vehicle_is_compatible, stop_and_return_vehicle);

1610 if (compatible_vehicle >= 0) {

1611

1612 const int64_t compatible_start = model()->Start(compatible_vehicle);

1613 const bool no_prior_entries_for_this_vehicle =

1614 queue->IsEmpty(compatible_start);

1615 if (!UpdateAfterNodeInsertion(nodes, compatible_vehicle, node_to_insert,

1616 compatible_start, all_vehicles, queue)) {

1617 return false;

1618 }

1619 if (compatible_vehicle != entry_vehicle) {

1620

1621

1622

1623

1624

1625 DCHECK(

1626 no_prior_entries_for_this_vehicle ||

1627 model()->GetVehicleClassIndexOfVehicle(compatible_vehicle).value() !=

1628 model()->GetVehicleClassIndexOfVehicle(entry_vehicle).value());

1629 return true;

1630 }

1631

1632

1633

1634 const int new_empty_vehicle =

1635 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(

1636 empty_vehicle_type_curator_->Type(compatible_vehicle));

1637

1638 if (new_empty_vehicle >= 0) {

1640

1641

1642

1643

1644

1645 const int64_t new_empty_vehicle_start = model()->Start(new_empty_vehicle);

1646 queue->ClearInsertions(new_empty_vehicle_start);

1647 if (!AddNodeEntriesAfter(nodes, new_empty_vehicle,

1648 new_empty_vehicle_start, all_vehicles, queue)) {

1649 return false;

1650 }

1651 }

1652 } else if (next_fixed_cost_empty_vehicle >= 0) {

1653

1654

1655

1656 DCHECK(VehicleIsEmpty(next_fixed_cost_empty_vehicle));

1657

1658

1659 queue->Pop();

1660 const int64_t insert_after = model()->Start(next_fixed_cost_empty_vehicle);

1662 node_to_insert, insert_after, Value(insert_after),

1663 next_fixed_cost_empty_vehicle);

1664 const int64_t penalty_shift =

1665 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)

1667 : 0;

1668 queue->PushInsertion(node_to_insert, insert_after,

1669 next_fixed_cost_empty_vehicle, bucket,

1670 CapSub(insertion_cost, penalty_shift));

1671 } else {

1672 queue->Pop();

1673 }

1674

1675 return true;

1676}

1677

1678bool GlobalCheapestInsertionFilteredHeuristic::SequentialInsertNodes(

1679 const std::map<int64_t, std::vector<int>>& nodes_by_bucket) {

1680 std::vector<bool> is_vehicle_used;

1681 absl::flat_hash_set<int> used_vehicles;

1682 std::vector<int> unused_vehicles;

1683

1684 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);

1685 if (!used_vehicles.empty() &&

1686 !InsertNodesOnRoutes(nodes_by_bucket, used_vehicles)) {

1687 return false;

1688 }

1689

1690 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =

1692 SeedQueue first_node_queue(false);

1694

1695 int vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,

1696 &is_vehicle_used);

1697

1698 while (vehicle >= 0) {

1699 if (!InsertNodesOnRoutes(nodes_by_bucket, {vehicle})) {

1700 return false;

1701 }

1702 vehicle = InsertSeedNode(&start_end_distances_per_node, &first_node_queue,

1703 &is_vehicle_used);

1704 }

1705 return true;

1706}

1707

1708void GlobalCheapestInsertionFilteredHeuristic::DetectUsedVehicles(

1709 std::vector<bool>* is_vehicle_used, std::vector<int>* unused_vehicles,

1710 absl::flat_hash_set<int>* used_vehicles) {

1711 is_vehicle_used->clear();

1712 is_vehicle_used->resize(model()->vehicles());

1713

1714 used_vehicles->clear();

1715 used_vehicles->reserve(model()->vehicles());

1716

1717 unused_vehicles->clear();

1718 unused_vehicles->reserve(model()->vehicles());

1719

1720 for (int vehicle = 0; vehicle < model()->vehicles(); vehicle++) {

1722 (*is_vehicle_used)[vehicle] = true;

1723 used_vehicles->insert(vehicle);

1724 } else {

1725 (*is_vehicle_used)[vehicle] = false;

1726 unused_vehicles->push_back(vehicle);

1727 }

1728 }

1729}

1730

1731bool GlobalCheapestInsertionFilteredHeuristic::IsCheapestClassRepresentative(

1732 int vehicle) const {

1734

1735

1736

1737 return true;

1738 }

1740

1741

1742 const int curator_vehicle =

1743 empty_vehicle_type_curator_->GetLowestFixedCostVehicleOfType(

1744 empty_vehicle_type_curator_->Type(vehicle));

1745 return curator_vehicle == vehicle ||

1748}

1749

1750void GlobalCheapestInsertionFilteredHeuristic::InsertFarthestNodesAsSeeds() {

1751

1752 if (gci_params_.farthest_seeds_ratio() <= 0) return;

1753

1754 const int num_seeds = static_cast<int>(

1755 std::ceil(gci_params_.farthest_seeds_ratio() * model()->vehicles()));

1756

1757 std::vector<bool> is_vehicle_used;

1758 absl::flat_hash_set<int> used_vehicles;

1759 std::vector<int> unused_vehicles;

1760 DetectUsedVehicles(&is_vehicle_used, &unused_vehicles, &used_vehicles);

1761 std::vector<std::vector<StartEndValue>> start_end_distances_per_node =

1763

1764

1765

1766 SeedQueue farthest_node_queue(true);

1767 InitializeSeedQueue(&start_end_distances_per_node, &farthest_node_queue);

1768

1769 int inserted_seeds = 0;

1770 while (inserted_seeds++ < num_seeds) {

1771 if (InsertSeedNode(&start_end_distances_per_node, &farthest_node_queue,

1772 &is_vehicle_used) < 0) {

1773 break;

1774 }

1775 }

1776

1777

1778

1779

1780

1781 DCHECK(empty_vehicle_type_curator_ != nullptr);

1782 empty_vehicle_type_curator_->Update(

1783 [this](int vehicle) { return !VehicleIsEmpty(vehicle); });

1784}

1785

1786int GlobalCheapestInsertionFilteredHeuristic::InsertSeedNode(

1787 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,

1788 SeedQueue* sq, std::vector<bool>* is_vehicle_used) {

1789 auto& priority_queue = sq->priority_queue;

1790 while (!priority_queue.empty()) {

1792 const Seed& seed = priority_queue.top();

1793 const int seed_node = seed.index;

1794 DCHECK(seed.is_node_index);

1795 const int seed_vehicle = seed.vehicle;

1796 priority_queue.pop();

1797

1798 std::vector<StartEndValue>& other_start_end_values =

1799 (*start_end_distances_per_node)[seed_node];

1800

1802

1803

1804 other_start_end_values.clear();

1805 continue;

1806 }

1807 if (!(*is_vehicle_used)[seed_vehicle]) {

1808

1809 const int64_t start = model()->Start(seed_vehicle);

1810 const int64_t end = model()->End(seed_vehicle);

1811 DCHECK_EQ(Value(start), end);

1813 if (Evaluate(true).has_value()) {

1814 (*is_vehicle_used)[seed_vehicle] = true;

1815 other_start_end_values.clear();

1816 SetVehicleIndex(seed_node, seed_vehicle);

1817 return seed_vehicle;

1818 }

1819 }

1820

1821

1822

1824 }

1825

1826 return -1;

1827}

1828

1829bool GlobalCheapestInsertionFilteredHeuristic::InitializePairPositions(

1830 const absl::flat_hash_set<int>& pair_indices,

1831 AdjustablePriorityQueue<

1832 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

1833 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1834 pickup_to_entries,

1835 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1836 delivery_to_entries) {

1837 priority_queue->Clear();

1838 pickup_to_entries->clear();

1839 pickup_to_entries->resize(model()->Size());

1840 delivery_to_entries->clear();

1841 delivery_to_entries->resize(model()->Size());

1842 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

1844 for (int index : pair_indices) {

1845 const auto& [pickups, deliveries] = pickup_delivery_pairs[index];

1846 for (int64_t pickup : pickups) {

1847 if (Contains(pickup)) continue;

1848 for (int64_t delivery : deliveries) {

1849 if (Contains(delivery)) continue;

1850 if (StopSearchAndCleanup(priority_queue)) return false;

1851

1852

1853

1854

1855 if (gci_params_.add_unperformed_entries() && pickups.size() == 1 &&

1856 deliveries.size() == 1 &&

1858 std::numeric_limits<int64_t>::max() &&

1860 std::numeric_limits<int64_t>::max()) {

1861 AddPairEntry(pickup, -1, delivery, -1, -1, priority_queue, nullptr,

1862 nullptr);

1863 }

1864

1865 InitializeInsertionEntriesPerformingPair(

1866 pickup, delivery, priority_queue, pickup_to_entries,

1867 delivery_to_entries);

1868 }

1869 }

1870 }

1871 return true;

1872}

1873

1874void GlobalCheapestInsertionFilteredHeuristic::

1875 InitializeInsertionEntriesPerformingPair(

1876 int64_t pickup, int64_t delivery,

1877 AdjustablePriorityQueue<

1878 GlobalCheapestInsertionFilteredHeuristic::PairEntry>*

1879 priority_queue,

1880 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1881 pickup_to_entries,

1882 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

1883 delivery_to_entries) {

1884 if (!gci_params_.use_neighbors_ratio_for_initialization()) {

1885 std::unique_ptr<IntVarIterator> vehicle_it(

1886 model()->VehicleVar(pickup)->MakeDomainIterator(false));

1887 for (const int vehicle : InitAndGetValues(vehicle_it.get())) {

1888 if (vehicle < 0 || !model()->VehicleVar(delivery)->Contains(vehicle)) {

1889 continue;

1890 }

1891 if (!IsCheapestClassRepresentative(vehicle)) continue;

1892

1893 int64_t pickup_insert_after = model()->Start(vehicle);

1894 while (!model()->IsEnd(pickup_insert_after)) {

1895 int64_t delivery_insert_after = pickup;

1896 while (!model()->IsEnd(delivery_insert_after)) {

1897 AddPairEntry(pickup, pickup_insert_after, delivery,

1898 delivery_insert_after, vehicle, priority_queue,

1899 pickup_to_entries, delivery_to_entries);

1900 delivery_insert_after = (delivery_insert_after == pickup)

1901 ? Value(pickup_insert_after)

1902 : Value(delivery_insert_after);

1903 }

1904 pickup_insert_after = Value(pickup_insert_after);

1905 }

1906 }

1907 return;

1908 }

1909

1910

1911

1913 cost_class++) {

1914 absl::flat_hash_set<std::pair<int64_t, int64_t>>

1915 existing_insertion_positions;

1916

1917 for (const int64_t pickup_insert_after :

1918 node_index_to_neighbors_by_cost_class_

1919 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, pickup)) {

1920 if (!Contains(pickup_insert_after)) {

1921 continue;

1922 }

1923 const int vehicle = node_index_to_vehicle_[pickup_insert_after];

1924 if (vehicle < 0 ||

1925 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {

1926 continue;

1927 }

1928

1929 if (!IsCheapestClassRepresentative(vehicle)) continue;

1930

1931 if (!model()->VehicleVar(pickup)->Contains(vehicle) ||

1932 !model()->VehicleVar(delivery)->Contains(vehicle)) {

1933 continue;

1934 }

1935 int64_t delivery_insert_after = pickup;

1936 while (!model()->IsEnd(delivery_insert_after)) {

1937 const std::pair<int64_t, int64_t> insertion_position = {

1938 pickup_insert_after, delivery_insert_after};

1939 DCHECK(!existing_insertion_positions.contains(insertion_position));

1940 existing_insertion_positions.insert(insertion_position);

1941

1942 AddPairEntry(pickup, pickup_insert_after, delivery,

1943 delivery_insert_after, vehicle, priority_queue,

1944 pickup_to_entries, delivery_to_entries);

1945 delivery_insert_after = (delivery_insert_after == pickup)

1946 ? Value(pickup_insert_after)

1947 : Value(delivery_insert_after);

1948 }

1949 }

1950

1951

1952 for (const int64_t delivery_insert_after :

1953 node_index_to_neighbors_by_cost_class_

1954 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, delivery)) {

1955 if (!Contains(delivery_insert_after)) {

1956 continue;

1957 }

1958 const int vehicle = node_index_to_vehicle_[delivery_insert_after];

1959 if (vehicle < 0 ||

1960 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {

1961 continue;

1962 }

1963 if (!model()->VehicleVar(pickup)->Contains(vehicle) ||

1964 !model()->VehicleVar(delivery)->Contains(vehicle)) {

1965 continue;

1966 }

1967

1969 delivery_insert_after == model()->Start(vehicle));

1970

1971 int64_t pickup_insert_after = model()->Start(vehicle);

1972 while (pickup_insert_after != delivery_insert_after) {

1973 if (!existing_insertion_positions.contains(

1974 std::make_pair(pickup_insert_after, delivery_insert_after))) {

1975 AddPairEntry(pickup, pickup_insert_after, delivery,

1976 delivery_insert_after, vehicle, priority_queue,

1977 pickup_to_entries, delivery_to_entries);

1978 }

1979 pickup_insert_after = Value(pickup_insert_after);

1980 }

1981 }

1982 }

1983}

1984

1985bool GlobalCheapestInsertionFilteredHeuristic::UpdateAfterPairInsertion(

1986 const absl::flat_hash_set<int>& pair_indices, int vehicle, int64_t pickup,

1987 int64_t pickup_position, int64_t delivery, int64_t delivery_position,

1988 AdjustablePriorityQueue<PairEntry>* priority_queue,

1989 std::vector<PairEntries>* pickup_to_entries,

1990 std::vector<PairEntries>* delivery_to_entries) {

1991

1992

1993 const std::vector<PairEntry*> to_remove(

1994 delivery_to_entries->at(pickup).begin(),

1995 delivery_to_entries->at(pickup).end());

1996 for (PairEntry* pair_entry : to_remove) {

1997 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,

1998 delivery_to_entries);

1999 }

2000 DCHECK(pickup_to_entries->at(pickup).empty());

2001 DCHECK(pickup_to_entries->at(delivery).empty());

2002 DCHECK(delivery_to_entries->at(pickup).empty());

2003 DCHECK(delivery_to_entries->at(delivery).empty());

2004

2005

2006 if (!UpdateExistingPairEntriesAfter(pickup_position, priority_queue,

2007 pickup_to_entries, delivery_to_entries) ||

2008 !UpdateExistingPairEntriesAfter(delivery_position, priority_queue,

2009 pickup_to_entries, delivery_to_entries)) {

2010 return false;

2011 }

2012

2013

2014

2015 if (!AddPairEntriesAfter(pair_indices, vehicle, pickup,

2016 delivery,

2017 priority_queue, pickup_to_entries,

2018 delivery_to_entries) ||

2019 !AddPairEntriesAfter(pair_indices, vehicle, delivery,

2020 -1,

2021 priority_queue, pickup_to_entries,

2022 delivery_to_entries)) {

2023 return false;

2024 }

2025 SetVehicleIndex(pickup, vehicle);

2026 SetVehicleIndex(delivery, vehicle);

2027 return true;

2028}

2029

2030bool GlobalCheapestInsertionFilteredHeuristic::UpdateExistingPairEntriesAfter(

2031 int64_t insert_after,

2032 AdjustablePriorityQueue<

2033 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

2034 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2035 pickup_to_entries,

2036 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2037 delivery_to_entries) {

2038 DCHECK(!model()->IsEnd(insert_after));

2039

2040

2041 std::vector<PairEntry*> to_remove;

2042 for (const PairEntries* pair_entries :

2043 {&pickup_to_entries->at(insert_after),

2044 &delivery_to_entries->at(insert_after)}) {

2045 if (StopSearchAndCleanup(priority_queue)) return false;

2046 for (PairEntry* const pair_entry : *pair_entries) {

2047 DCHECK(priority_queue->Contains(pair_entry));

2048 if (Contains(pair_entry->pickup_to_insert()) ||

2049 Contains(pair_entry->delivery_to_insert())) {

2050 to_remove.push_back(pair_entry);

2051 } else {

2052 DCHECK(pickup_to_entries->at(pair_entry->pickup_insert_after())

2053 .contains(pair_entry));

2054 DCHECK(delivery_to_entries->at(pair_entry->delivery_insert_after())

2055 .contains(pair_entry));

2056 if (!UpdatePairEntry(pair_entry, priority_queue)) {

2057 to_remove.push_back(pair_entry);

2058 }

2059 }

2060 }

2061 }

2062 for (PairEntry* const pair_entry : to_remove) {

2063 DeletePairEntry(pair_entry, priority_queue, pickup_to_entries,

2064 delivery_to_entries);

2065 }

2066 return true;

2067}

2068

2069bool GlobalCheapestInsertionFilteredHeuristic::AddPairEntriesWithPickupAfter(

2070 const absl::flat_hash_set<int>& pair_indices, int vehicle,

2071 int64_t insert_after, int64_t skip_entries_inserting_delivery_after,

2072 AdjustablePriorityQueue<

2073 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

2074 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2075 pickup_to_entries,

2076 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2077 delivery_to_entries) {

2079 const int64_t pickup_insert_before = Value(insert_after);

2080 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

2082 DCHECK(pickup_to_entries->at(insert_after).empty());

2083 for (const int64_t pickup :

2084 node_index_to_neighbors_by_cost_class_

2085 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class, insert_after)) {

2086 if (StopSearchAndCleanup(priority_queue)) return false;

2088 continue;

2089 }

2090 if (const std::optional<RoutingModel::PickupDeliveryPosition> pickup_pos =

2091 model()->GetPickupPosition(pickup);

2092 pickup_pos.has_value()) {

2093 const int pair_index = pickup_pos->pd_pair_index;

2094 if (!pair_indices.contains(pair_index)) continue;

2095 for (const int64_t delivery :

2096 pickup_delivery_pairs[pair_index].delivery_alternatives) {

2098 !model()->VehicleVar(delivery)->Contains(vehicle)) {

2099 continue;

2100 }

2101 int64_t delivery_insert_after = pickup;

2102 while (!model()->IsEnd(delivery_insert_after)) {

2103 if (delivery_insert_after != skip_entries_inserting_delivery_after) {

2104 AddPairEntry(pickup, insert_after, delivery, delivery_insert_after,

2105 vehicle, priority_queue, pickup_to_entries,

2106 delivery_to_entries);

2107 }

2108 if (delivery_insert_after == pickup) {

2109 delivery_insert_after = pickup_insert_before;

2110 } else {

2111 delivery_insert_after = Value(delivery_insert_after);

2112 }

2113 }

2114 }

2115 }

2116 }

2117 return true;

2118}

2119

2120bool GlobalCheapestInsertionFilteredHeuristic::AddPairEntriesWithDeliveryAfter(

2121 const absl::flat_hash_set<int>& pair_indices, int vehicle,

2122 int64_t insert_after,

2123 AdjustablePriorityQueue<

2124 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

2125 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2126 pickup_to_entries,

2127 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2128 delivery_to_entries) {

2130 const std::vector<PickupDeliveryPair>& pickup_delivery_pairs =

2132 for (const int64_t delivery :

2133 node_index_to_neighbors_by_cost_class_

2134 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class, insert_after)) {

2135 if (StopSearchAndCleanup(priority_queue)) return false;

2137 !model()->VehicleVar(delivery)->Contains(vehicle)) {

2138 continue;

2139 }

2140 if (const std::optional<RoutingModel::PickupDeliveryPosition> delivery_pos =

2141 model()->GetDeliveryPosition(delivery);

2142 delivery_pos.has_value()) {

2143 const int pair_index = delivery_pos->pd_pair_index;

2144 if (!pair_indices.contains(pair_index)) continue;

2145 for (const int64_t pickup :

2146 pickup_delivery_pairs[pair_index].pickup_alternatives) {

2148 !model()->VehicleVar(pickup)->Contains(vehicle)) {

2149 continue;

2150 }

2151 int64_t pickup_insert_after = model()->Start(vehicle);

2152 while (pickup_insert_after != insert_after) {

2153 AddPairEntry(pickup, pickup_insert_after, delivery, insert_after,

2154 vehicle, priority_queue, pickup_to_entries,

2155 delivery_to_entries);

2156 pickup_insert_after = Value(pickup_insert_after);

2157 }

2158 }

2159 }

2160 }

2161 return true;

2162}

2163

2164void GlobalCheapestInsertionFilteredHeuristic::DeletePairEntry(

2165 GlobalCheapestInsertionFilteredHeuristic::PairEntry* entry,

2166 AdjustablePriorityQueue<

2167 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

2168 std::vector<PairEntries>* pickup_to_entries,

2169 std::vector<PairEntries>* delivery_to_entries) {

2170 priority_queue->Remove(entry);

2171 if (entry->pickup_insert_after() != -1) {

2172 pickup_to_entries->at(entry->pickup_insert_after()).erase(entry);

2173 }

2174 if (entry->delivery_insert_after() != -1) {

2175 delivery_to_entries->at(entry->delivery_insert_after()).erase(entry);

2176 }

2177 pair_entry_allocator_.FreeEntry(entry);

2178}

2179

2180void GlobalCheapestInsertionFilteredHeuristic::AddPairEntry(

2181 int64_t pickup, int64_t pickup_insert_after, int64_t delivery,

2182 int64_t delivery_insert_after, int vehicle,

2183 AdjustablePriorityQueue<

2184 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue,

2185 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2186 pickup_entries,

2187 std::vector<GlobalCheapestInsertionFilteredHeuristic::PairEntries>*

2188 delivery_entries) {

2189 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);

2190 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);

2191 if (!pickup_vehicle_var->Contains(vehicle) ||

2192 !delivery_vehicle_var->Contains(vehicle)) {

2193 if (vehicle == -1 || !VehicleIsEmpty(vehicle)) return;

2194

2195

2196 const auto vehicle_is_compatible = [pickup_vehicle_var,

2197 delivery_vehicle_var](int vehicle) {

2198 return pickup_vehicle_var->Contains(vehicle) &&

2199 delivery_vehicle_var->Contains(vehicle);

2200 };

2201 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(

2202 empty_vehicle_type_curator_->Type(vehicle),

2203 vehicle_is_compatible)) {

2204 return;

2205 }

2206 }

2207 const int num_allowed_vehicles =

2208 std::min(pickup_vehicle_var->Size(), delivery_vehicle_var->Size());

2209 const int64_t pair_penalty =

2211 const int64_t penalty_shift =

2212 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)

2213 ? pair_penalty

2214 : 0;

2215 if (pickup_insert_after == -1) {

2216 DCHECK_EQ(delivery_insert_after, -1);

2217 DCHECK_EQ(vehicle, -1);

2218 PairEntry* pair_entry = pair_entry_allocator_.NewEntry(

2219 pickup, -1, delivery, -1, -1, num_allowed_vehicles);

2220 pair_entry->set_value(CapSub(pair_penalty, penalty_shift));

2221 priority_queue->Add(pair_entry);

2222 return;

2223 }

2224 const std::optional<int64_t> insertion_cost =

2226 delivery_insert_after, vehicle);

2227

2228 if (!insertion_cost.has_value()) return;

2229

2230 PairEntry* const pair_entry = pair_entry_allocator_.NewEntry(

2231 pickup, pickup_insert_after, delivery, delivery_insert_after, vehicle,

2232 num_allowed_vehicles);

2233 pair_entry->set_value(CapSub(*insertion_cost, penalty_shift));

2234

2235

2236 DCHECK(!priority_queue->Contains(pair_entry));

2237 pickup_entries->at(pickup_insert_after).insert(pair_entry);

2238 delivery_entries->at(delivery_insert_after).insert(pair_entry);

2239 priority_queue->Add(pair_entry);

2240}

2241

2242bool GlobalCheapestInsertionFilteredHeuristic::UpdatePairEntry(

2243 GlobalCheapestInsertionFilteredHeuristic::PairEntry* const pair_entry,

2244 AdjustablePriorityQueue<

2245 GlobalCheapestInsertionFilteredHeuristic::PairEntry>* priority_queue) {

2246 const int64_t pickup = pair_entry->pickup_to_insert();

2247 const int64_t delivery = pair_entry->delivery_to_insert();

2248 const std::optional<int64_t> insertion_cost =

2250 pickup, pair_entry->pickup_insert_after(), delivery,

2251 pair_entry->delivery_insert_after(), pair_entry->vehicle());

2252 const int64_t penalty_shift =

2253 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty) &&

2254 insertion_cost.has_value()

2256 : 0;

2257

2258 if (!insertion_cost.has_value()) {

2259 return false;

2260 }

2261

2262 pair_entry->set_value(CapSub(*insertion_cost, penalty_shift));

2263

2264

2265 DCHECK(priority_queue->Contains(pair_entry));

2267 return true;

2268}

2269

2270bool GlobalCheapestInsertionFilteredHeuristic::InitializePositions(

2271 const SparseBitset<int>& nodes, const absl::flat_hash_set<int>& vehicles,

2272 NodeEntryQueue* queue) {

2273 queue->Clear();

2274

2275 const int num_vehicles =

2276 vehicles.empty() ? model()->vehicles() : vehicles.size();

2277 const bool all_vehicles = (num_vehicles == model()->vehicles());

2278

2279 for (int node : nodes.PositionsSetAtLeastOnce()) {

2280 if (Contains(node)) continue;

2281

2283

2284 if (gci_params_.add_unperformed_entries() &&

2286 AddNodeEntry(node, node, -1, all_vehicles, queue);

2287 }

2288

2289 InitializeInsertionEntriesPerformingNode(node, vehicles, queue);

2290 }

2291 return true;

2292}

2293

2294void GlobalCheapestInsertionFilteredHeuristic::

2295 InitializeInsertionEntriesPerformingNode(

2296 int64_t node, const absl::flat_hash_set<int>& vehicles,

2297 NodeEntryQueue* queue) {

2298 const int num_vehicles =

2299 vehicles.empty() ? model()->vehicles() : vehicles.size();

2300 const bool all_vehicles = (num_vehicles == model()->vehicles());

2301

2302 if (!gci_params_.use_neighbors_ratio_for_initialization()) {

2303 auto vehicles_it = vehicles.begin();

2304

2305

2306

2307

2308

2309 for (int v = 0; v < num_vehicles; v++) {

2310 const int vehicle = vehicles.empty() ? v : *vehicles_it++;

2311 if (!model()->VehicleVar(node)->Contains(vehicle)) continue;

2312 if (all_vehicles && !IsCheapestClassRepresentative(vehicle)) continue;

2313

2314 int64_t insert_after = model()->Start(vehicle);

2315 while (insert_after != model()->End(vehicle)) {

2316 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);

2317 insert_after = Value(insert_after);

2318 }

2319 }

2320 return;

2321 }

2322

2323

2324

2326 cost_class++) {

2327 for (const int64_t insert_after :

2328 node_index_to_neighbors_by_cost_class_

2329 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, node)) {

2330 if (!Contains(insert_after)) {

2331 continue;

2332 }

2333 const int vehicle = node_index_to_vehicle_[insert_after];

2334 if (vehicle == -1 ||

2335 model()->GetCostClassIndexOfVehicle(vehicle).value() != cost_class) {

2336 continue;

2337 }

2338 if (all_vehicles) {

2339 if (!IsCheapestClassRepresentative(vehicle)) continue;

2340 } else if (!vehicles.contains(vehicle)) {

2341 continue;

2342 }

2343 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);

2344 }

2345 }

2346}

2347

2348bool GlobalCheapestInsertionFilteredHeuristic::UpdateAfterNodeInsertion(

2350 int64_t insert_after, bool all_vehicles, NodeEntryQueue* queue) {

2351

2352

2353 if (!AddNodeEntriesAfter(nodes, vehicle, insert_after, all_vehicles, queue)) {

2354 return false;

2355 }

2356

2357

2358

2359

2360

2361 if (!AddNodeEntriesAfter(nodes, vehicle, node, all_vehicles, queue)) {

2362 return false;

2363 }

2364 SetVehicleIndex(node, vehicle);

2365 return true;

2366}

2367

2368bool GlobalCheapestInsertionFilteredHeuristic::AddNodeEntriesAfter(

2369 const SparseBitset<int>& nodes, int vehicle, int64_t insert_after,

2370 bool all_vehicles, NodeEntryQueue* queue) {

2371 temp_inserted_nodes_.ResetAllToFalse();

2373

2374

2375 queue->ClearInsertions(insert_after);

2376

2377 const auto add_node_entries_for_neighbors =

2378 [this, &nodes, &queue, insert_after, vehicle, all_vehicles](

2379 absl::Span<const int> neighbors,

2380 const std::function<bool(int64_t)>& is_neighbor) {

2381 if (neighbors.size() < nodes.NumberOfSetCallsWithDifferentArguments()) {

2382

2383 for (int node : neighbors) {

2385 if (!Contains(node) && nodes[node] && !temp_inserted_nodes_[node]) {

2386 temp_inserted_nodes_.Set(node);

2387 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);

2388 }

2389 }

2390 } else {

2391

2392 for (int node : nodes.PositionsSetAtLeastOnce()) {

2394 if (!Contains(node) && is_neighbor(node) &&

2395 !temp_inserted_nodes_[node]) {

2396 temp_inserted_nodes_.Set(node);

2397 AddNodeEntry(node, insert_after, vehicle, all_vehicles, queue);

2398 }

2399 }

2400 }

2401 return true;

2402 };

2403

2404 if (!add_node_entries_for_neighbors(

2405 node_index_to_neighbors_by_cost_class_

2406 ->GetOutgoingNeighborsOfNodeForCostClass(cost_class,

2407 insert_after),

2408 [this, insert_after, cost_class](int64_t node) {

2409 return node_index_to_neighbors_by_cost_class_

2410 ->IsNeighborhoodArcForCostClass(cost_class, insert_after, node);

2411 })) {

2412 return false;

2413 }

2414

2415 if (!node_index_to_neighbors_by_cost_class_->IsFullNeighborhood()) {

2416

2417

2418 const int64_t insert_before = Value(insert_after);

2419 if (model()->IsEnd(insert_before)) {

2420

2421 return true;

2422 }

2423 return add_node_entries_for_neighbors(

2424 node_index_to_neighbors_by_cost_class_

2425 ->GetIncomingNeighborsOfNodeForCostClass(cost_class, insert_before),

2426 [this, insert_before, cost_class](int64_t node) {

2427 return node_index_to_neighbors_by_cost_class_

2428 ->IsNeighborhoodArcForCostClass(cost_class, node, insert_before);

2429 });

2430 }

2431 return true;

2432}

2433

2434void GlobalCheapestInsertionFilteredHeuristic::AddNodeEntry(

2435 int64_t node, int64_t insert_after, int vehicle, bool all_vehicles,

2436 NodeEntryQueue* queue) {

2437 const IntVar* const vehicle_var = model()->VehicleVar(node);

2438 if (!vehicle_var->Contains(vehicle)) {

2439 if (!UseEmptyVehicleTypeCuratorForVehicle(vehicle, all_vehicles)) return;

2440

2441

2442 const auto vehicle_is_compatible = [vehicle_var](int vehicle) {

2443 return vehicle_var->Contains(vehicle);

2444 };

2445 if (!empty_vehicle_type_curator_->HasCompatibleVehicleOfType(

2446 empty_vehicle_type_curator_->Type(vehicle),

2447 vehicle_is_compatible)) {

2448 return;

2449 }

2450 }

2451 const int num_allowed_vehicles = vehicle_var->Size();

2453 const int64_t penalty_shift =

2454 absl::GetFlag(FLAGS_routing_shift_insertion_cost_by_penalty)

2455 ? node_penalty

2456 : 0;

2457 if (vehicle == -1) {

2458 DCHECK_EQ(node, insert_after);

2459 if (!all_vehicles) {

2460

2461

2462

2463 return;

2464 }

2465 queue->PushInsertion(node, node, -1, num_allowed_vehicles,

2466 CapSub(node_penalty, penalty_shift));

2467 return;

2468 }

2469

2470 const std::optional<int64_t> insertion_cost =

2472 vehicle);

2473 if (!insertion_cost.has_value()) return;

2474 if (!all_vehicles && *insertion_cost > node_penalty) {

2475

2476

2477

2478 return;

2479 }

2480 queue->PushInsertion(node, insert_after, vehicle, num_allowed_vehicles,

2481 CapSub(*insertion_cost, penalty_shift));

2482}

2483

2566

2567

2568

2594

2615

2616bool LocalCheapestInsertionFilteredHeuristic::OptimizeOnInsertion(

2617 std::vector<int> delta_indices) {

2618 if (optimize_on_insertion_ == nullptr) return false;

2619 std::vector<RoutingModel::VariableValuePair> in_state;

2620 if (synchronize_insertion_optimizer_) {

2621 for (int i = 0; i < model()->Nexts().size(); ++i) {

2623 in_state.push_back({i, Value(i)});

2624 }

2625 }

2626 synchronize_insertion_optimizer_ = false;

2627 } else {

2629 in_state.push_back({index, Value(index)});

2630 }

2631 }

2632 std::vector<RoutingModel::VariableValuePair> out_state;

2633 optimize_on_insertion_(in_state, &out_state);

2634 if (out_state.empty()) return false;

2635 for (const auto& [var, value] : out_state) {

2638 }

2639 }

2640 return Evaluate(true).has_value();

2641}

2642

2643namespace {

2644

2645std::vector<std::vector<int64_t>> ComputeStartToPickupCosts(

2646 const RoutingModel& model, absl::Span<const int64_t> pickups,

2648 std::vector<std::vector<int64_t>> pickup_costs(model.Size());

2649 for (int64_t pickup : pickups) {

2650 std::vector<int64_t>& cost_from_start = pickup_costs[pickup];

2651 cost_from_start.resize(model.vehicles(), -1);

2652

2653 ProcessVehicleStartEndCosts(

2654 model, pickup,

2655 [&cost_from_start](int64_t cost, int v) { cost_from_start[v] = cost; },

2656 vehicle_set, false, true);

2657 }

2658 return pickup_costs;

2659}

2660

2661

2662std::vector<std::vector<int64_t>> ComputeDeliveryToEndCosts(

2663 const RoutingModel& model, absl::Span<const int64_t> deliveries,

2665 std::vector<std::vector<int64_t>> delivery_costs(model.Size());

2666 for (int64_t delivery : deliveries) {

2667 std::vector<int64_t>& cost_to_end = delivery_costs[delivery];

2668 cost_to_end.resize(model.vehicles(), -1);

2669

2670 ProcessVehicleStartEndCosts(

2671 model, delivery,

2672 [&cost_to_end](int64_t cost, int v) { cost_to_end[v] = cost; },

2673 vehicle_set, true, false);

2674 }

2675 return delivery_costs;

2676}

2677

2678

2679

2680

2681

2682int64_t GetNegMaxDistanceFromVehicles(const RoutingModel& model,

2683 int pair_index) {

2684 const auto& [pickups, deliveries] =

2685 model.GetPickupAndDeliveryPairs()[pair_index];

2686

2688 for (int v = 0; v < model.vehicles(); ++v) vehicle_set.Set(v);

2689

2690

2691 const std::vector<std::vector<int64_t>> pickup_costs =

2692 ComputeStartToPickupCosts(model, pickups, vehicle_set);

2693

2694

2695 const std::vector<std::vector<int64_t>> delivery_costs =

2696 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);

2697

2698 int64_t max_pair_distance = 0;

2699 for (int64_t pickup : pickups) {

2700 const std::vector<int64_t>& cost_from_start = pickup_costs[pickup];

2701 for (int64_t delivery : deliveries) {

2702 const std::vector<int64_t>& cost_to_end = delivery_costs[delivery];

2703 int64_t closest_vehicle_distance = std::numeric_limits<int64_t>::max();

2704 for (int v = 0; v < model.vehicles(); v++) {

2705 if (cost_from_start[v] < 0 || cost_to_end[v] < 0) {

2706

2707 continue;

2708 }

2709 closest_vehicle_distance =

2710 std::min(closest_vehicle_distance,

2711 CapAdd(cost_from_start[v], cost_to_end[v]));

2712 }

2713 max_pair_distance = std::max(max_pair_distance, closest_vehicle_distance);

2714 }

2715 }

2716 return CapOpp(max_pair_distance);

2717}

2718

2719

2720

2721

2722

2723

2724std::optional<int64_t> GetAvgPickupDeliveryPairDistanceFromVehicles(

2727 const auto& [pickups, deliveries] =

2728 model.GetPickupAndDeliveryPairs()[pair_index];

2729

2730

2731 const std::vector<std::vector<int64_t>> pickup_costs =

2732 ComputeStartToPickupCosts(model, pickups, vehicle_set);

2733

2734

2735 const std::vector<std::vector<int64_t>> delivery_costs =

2736 ComputeDeliveryToEndCosts(model, deliveries, vehicle_set);

2737

2738 int64_t avg_pair_distance_sum = 0;

2739 int valid_pairs = 0;

2740 for (int64_t pickup : pickups) {

2741 const std::vector<int64_t>& cost_from_start = pickup_costs[pickup];

2742 for (int64_t delivery : deliveries) {

2743 const std::vector<int64_t>& cost_to_end = delivery_costs[delivery];

2744 int64_t distance_from_vehicle_sum = 0;

2745 int valid_vehicles = 0;

2746 for (int v = 0; v < model.vehicles(); v++) {

2747 if (cost_from_start[v] < 0 || cost_to_end[v] < 0) {

2748

2749 continue;

2750 }

2751 distance_from_vehicle_sum =

2752 CapAdd(distance_from_vehicle_sum,

2753 CapAdd(cost_from_start[v], cost_to_end[v]));

2754 ++valid_vehicles;

2755 }

2756 if (valid_vehicles > 0) {

2757 avg_pair_distance_sum = CapAdd(

2758 distance_from_vehicle_sum / valid_vehicles, avg_pair_distance_sum);

2759 ++valid_pairs;

2760 }

2761 }

2762 }

2763 return valid_pairs > 0

2764 ? std::make_optional<int64_t>(avg_pair_distance_sum / valid_pairs)

2765 : std::nullopt;

2766}

2767

2768

2769

2770int64_t GetMaxFiniteDimensionCapacity(

2772 const std::vector<RoutingDimension*>& dimensions) {

2773 int64_t max_capacity = 0;

2775 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {

2776 const int64_t capacity = dimension->vehicle_capacities()[vehicle];

2777 if (capacity == kint64max) continue;

2778 max_capacity = std::max(max_capacity, capacity);

2779 }

2780 }

2781 return max_capacity;

2782}

2783

2784

2785

2786int64_t GetAvgNodeUnaryDimensionUsage(

2787 const RoutingModel& model, const std::vector<RoutingDimension*>& dimensions,

2788 int64_t max_vehicle_capacity, int64_t node) {

2789 if (dimensions.empty() || max_vehicle_capacity == 0) {

2790 return 0;

2791 }

2792

2793 double dimension_usage_sum = 0;

2795

2796 DCHECK(dimension->IsUnary());

2797 double dimension_usage_per_vehicle_sum = 0;

2798 int valid_vehicles = 0;

2799

2800

2801 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {

2802 const int64_t capacity = dimension->vehicle_capacities()[vehicle];

2803 if (capacity == 0) continue;

2804 DCHECK_GE(capacity, 0);

2805 valid_vehicles++;

2806

2807

2808 if (capacity == kint64max) continue;

2810 dimension->GetUnaryTransitEvaluator(vehicle);

2811 dimension_usage_per_vehicle_sum +=

2812 1.0 * std::abs(transit_evaluator(node)) / capacity;

2813 }

2814

2815 if (valid_vehicles > 0) {

2816

2817

2818 dimension_usage_sum +=

2819 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);

2820 }

2821 }

2822

2823

2824

2826 dimension_usage_sum);

2827}

2828

2829

2830

2831int64_t GetAvgPickupDeliveryPairUnaryDimensionUsage(

2832 const RoutingModel& model, const std::vector<RoutingDimension*>& dimensions,

2833 int64_t max_vehicle_capacity, int pair_index) {

2834 if (dimensions.empty()) {

2835 return 0;

2836 }

2837

2838 const auto& [pickups, deliveries] =

2839 model.GetPickupAndDeliveryPairs()[pair_index];

2840 if (pickups.empty() || deliveries.empty()) {

2841 return 0;

2842 }

2843

2844 double dimension_usage_sum = 0;

2846 double dimension_usage_per_vehicle_sum = 0;

2847 int valid_vehicles = 0;

2848

2849 for (int vehicle = 0; vehicle < model.vehicles(); ++vehicle) {

2850 const int64_t capacity = dimension->vehicle_capacities()[vehicle];

2851 if (capacity == 0) continue;

2852 valid_vehicles++;

2853

2854

2855 if (capacity == kint64max) continue;

2857 dimension->GetUnaryTransitEvaluator(vehicle);

2858

2859 double pickup_sum = 0;

2860 for (int64_t pickup : pickups) {

2861 pickup_sum += 1.0 * std::abs(transit_evaluator(pickup)) / capacity;

2862 }

2863 const double avg_pickup_usage = pickup_sum / pickups.size();

2864 double delivery_sum = 0;

2865 for (int64_t delivery : deliveries) {

2866 delivery_sum += 1.0 * std::abs(transit_evaluator(delivery)) / capacity;

2867 }

2868 const double avg_delivery_usage = delivery_sum / deliveries.size();

2869 dimension_usage_per_vehicle_sum +=

2870 std::max(avg_pickup_usage, avg_delivery_usage);

2871 }

2872

2873 if (valid_vehicles > 0) {

2874

2875

2876 dimension_usage_sum +=

2877 std::min(1.0, dimension_usage_per_vehicle_sum / valid_vehicles);

2878 }

2879 }

2880

2881

2882

2884 dimension_usage_sum);

2885}

2886}

2887

2888void LocalCheapestInsertionFilteredHeuristic::ComputeInsertionOrder() {

2889 if (use_random_insertion_order_) {

2890 if (insertion_order_.empty()) {

2891 const RoutingModel& model = *this->model();

2892 insertion_order_.reserve(model.Size() +

2893 model.GetPickupAndDeliveryPairs().size());

2894 for (int pair_index = 0;

2895 pair_index < model.GetPickupAndDeliveryPairs().size();

2896 ++pair_index) {

2897 insertion_order_.push_back(

2898 {.is_node_index = false, .index = pair_index});

2899 }

2900 for (int node = 0; node < model.Size(); ++node) {

2901 if (model.IsStart(node) || model.IsEnd(node)) continue;

2902 insertion_order_.push_back({.is_node_index = true, .index = node});

2903 }

2904 }

2905

2906 absl::c_shuffle(insertion_order_, rnd_);

2907 return;

2908 }

2909

2910 if (!insertion_order_.empty()) return;

2911

2912

2913

2914

2915

2916

2917

2918 const RoutingModel& model = *this->model();

2919 insertion_order_.reserve(model.Size() +

2920 model.GetPickupAndDeliveryPairs().size());

2921

2922 auto get_insertion_properties =

2923 [this](int64_t penalty, int64_t num_allowed_vehicles,

2924 int64_t avg_distance_to_vehicle,

2925 int64_t neg_min_distance_to_vehicles, int hint_weight,

2926 int reversed_hint_weight, int64_t avg_dimension_usage) {

2927 DCHECK_NE(0, num_allowed_vehicles);

2928 absl::InlinedVector<int64_t, 8> properties;

2929 properties.reserve(insertion_sorting_properties_.size());

2930

2931

2932

2933

2934

2935 properties.push_back(-hint_weight);

2936 properties.push_back(-reversed_hint_weight);

2937

2938 bool neg_min_distance_to_vehicles_appended = false;

2939 for (const int property : insertion_sorting_properties_) {

2940 switch (property) {

2941 case LocalCheapestInsertionParameters::

2942 SORTING_PROPERTY_ALLOWED_VEHICLES:

2943 properties.push_back(num_allowed_vehicles);

2944 break;

2946 properties.push_back(CapOpp(penalty));

2947 break;

2948 case LocalCheapestInsertionParameters::

2949 SORTING_PROPERTY_PENALTY_OVER_ALLOWED_VEHICLES_RATIO:

2950 properties.push_back(CapOpp(penalty / num_allowed_vehicles));

2951 break;

2952 case LocalCheapestInsertionParameters::

2953 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:

2954 properties.push_back(CapOpp(avg_distance_to_vehicle));

2955 break;

2956 case LocalCheapestInsertionParameters::

2957 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS:

2958 properties.push_back(avg_distance_to_vehicle);

2959 break;

2960 case LocalCheapestInsertionParameters::

2961 SORTING_PROPERTY_LOWEST_MIN_ARC_COST_TO_VEHICLE_START_ENDS:

2962 properties.push_back(neg_min_distance_to_vehicles);

2963 neg_min_distance_to_vehicles_appended = true;

2964 break;

2965 case LocalCheapestInsertionParameters::

2966 SORTING_PROPERTY_HIGHEST_DIMENSION_USAGE:

2967 properties.push_back(CapOpp(avg_dimension_usage));

2968 break;

2969 default:

2970 LOG(DFATAL)

2971 << "Unknown RoutingSearchParameter::InsertionSortingProperty "

2972 "used!";

2973 break;

2974 }

2975 }

2976

2977

2978

2979

2980

2981 if (!neg_min_distance_to_vehicles_appended) {

2982 properties.push_back(neg_min_distance_to_vehicles);

2983 }

2984

2985 return properties;

2986 };

2987

2988

2989

2990 bool compute_avg_pickup_delivery_pair_distance_from_vehicles = false;

2991 bool compute_avg_dimension_usage = false;

2993 property : insertion_sorting_properties_) {

2994 if (property ==

2995 LocalCheapestInsertionParameters::

2996 SORTING_PROPERTY_HIGHEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS ||

2997 property ==

2998 LocalCheapestInsertionParameters::

2999 SORTING_PROPERTY_LOWEST_AVG_ARC_COST_TO_VEHICLE_START_ENDS) {

3000 compute_avg_pickup_delivery_pair_distance_from_vehicles = true;

3001 }

3002 if (property == LocalCheapestInsertionParameters::

3003 SORTING_PROPERTY_HIGHEST_DIMENSION_USAGE) {

3004 compute_avg_dimension_usage = true;

3005 }

3006 }

3007

3008 Bitset64<int> vehicle_set(model.vehicles());

3009 for (int v = 0; v < model.vehicles(); ++v) vehicle_set.Set(v);

3010

3011 const std::vector<RoutingDimension*> unary_dimensions =

3012 compute_avg_dimension_usage ? model.GetUnaryDimensions()

3013 : std::vector<RoutingDimension*>();

3014

3015 const int64_t max_dimension_capacity =

3016 compute_avg_dimension_usage

3017 ? GetMaxFiniteDimensionCapacity(model, unary_dimensions)

3018 : 0;

3019

3020

3021 const std::vector<PickupDeliveryPair>& pairs =

3022 model.GetPickupAndDeliveryPairs();

3023

3024 for (int pair_index = 0; pair_index < pairs.size(); ++pair_index) {

3025 const auto& [pickups, deliveries] = pairs[pair_index];

3026 int64_t num_allowed_vehicles = std::numeric_limits<int64_t>::max();

3027 int64_t pickup_penalty = 0;

3028 int hint_weight = 0;

3029 int reversed_hint_weight = 0;

3030 for (int64_t pickup : pickups) {

3031 num_allowed_vehicles =

3032 std::min(num_allowed_vehicles,

3033 static_cast<int64_t>(model.VehicleVar(pickup)->Size()));

3034 pickup_penalty =

3035 std::max(pickup_penalty, model.UnperformedPenalty(pickup));

3038 }

3039 int64_t delivery_penalty = 0;

3040 for (int64_t delivery : deliveries) {

3041 num_allowed_vehicles =

3042 std::min(num_allowed_vehicles,

3043 static_cast<int64_t>(model.VehicleVar(delivery)->Size()));

3044 delivery_penalty =

3045 std::max(delivery_penalty, model.UnperformedPenalty(delivery));

3047 reversed_hint_weight += HasHintedPrev(delivery);

3048 }

3049

3050 const std::optional<int64_t> maybe_avg_pair_to_vehicle_cost =

3051 compute_avg_pickup_delivery_pair_distance_from_vehicles

3052 ? GetAvgPickupDeliveryPairDistanceFromVehicles(model, pair_index,

3053 vehicle_set)

3054 : std::make_optional<int64_t>(0);

3055

3056 if (!maybe_avg_pair_to_vehicle_cost.has_value()) {

3057

3058

3059 continue;

3060 }

3061

3062 const int64_t avg_pair_dimension_usage =

3063 compute_avg_dimension_usage

3064 ? GetAvgPickupDeliveryPairUnaryDimensionUsage(

3065 model, unary_dimensions, max_dimension_capacity, pair_index)

3066 : 0;

3067

3068 absl::InlinedVector<int64_t, 8> properties = get_insertion_properties(

3069 CapAdd(pickup_penalty, delivery_penalty), num_allowed_vehicles,

3070 maybe_avg_pair_to_vehicle_cost.value(),

3071 GetNegMaxDistanceFromVehicles(model, pair_index), hint_weight,

3072 reversed_hint_weight, avg_pair_dimension_usage);

3073

3074 insertion_order_.push_back({.properties = std::move(properties),

3075 .vehicle = 0,

3076 .is_node_index = false,

3077 .index = pair_index});

3078 }

3079

3080 for (int node = 0; node < model.Size(); ++node) {

3081 if (model.IsStart(node) || model.IsEnd(node)) continue;

3082

3083 int64_t min_distance = std::numeric_limits<int64_t>::max();

3084 int64_t sum_distance = 0;

3085 ProcessVehicleStartEndCosts(

3087 [&min_distance, &sum_distance](int64_t dist, int) {

3088 min_distance = std::min(min_distance, dist);

3089 sum_distance = CapAdd(dist, sum_distance);

3090 },

3091 vehicle_set);

3092 DCHECK_GT(vehicle_set.size(), 0);

3093

3094 const int64_t avg_dimension_usage =

3095 compute_avg_dimension_usage

3096 ? GetAvgNodeUnaryDimensionUsage(model, unary_dimensions,

3097 max_dimension_capacity, node)

3098 : 0;

3099

3100 absl::InlinedVector<int64_t, 8> properties = get_insertion_properties(

3101 model.UnperformedPenalty(node), model.VehicleVar(node)->Size(),

3102 sum_distance / vehicle_set.size(), CapOpp(min_distance),

3104 insertion_order_.push_back({.properties = std::move(properties),

3105 .vehicle = 0,

3106 .is_node_index = true,

3107 .index = node});

3108 }

3109

3110 absl::c_sort(insertion_order_, std::greater<Seed>());

3111 absl::c_reverse(insertion_order_);

3112}

3113

3114bool LocalCheapestInsertionFilteredHeuristic::InsertPair(

3115 int64_t pickup, int64_t insert_pickup_after, int64_t delivery,

3116 int64_t insert_delivery_after, int vehicle) {

3117 const int64_t insert_pickup_before = Value(insert_pickup_after);

3118 InsertBetween(pickup, insert_pickup_after, insert_pickup_before, vehicle);

3119 DCHECK_NE(insert_delivery_after, insert_pickup_after);

3120 const int64_t insert_delivery_before = (insert_delivery_after == pickup)

3121 ? insert_pickup_before

3122 : Value(insert_delivery_after);

3123 InsertBetween(delivery, insert_delivery_after, insert_delivery_before,

3124 vehicle);

3125

3127 if (Evaluate(true, true).has_value()) {

3128 OptimizeOnInsertion(std::move(indices));

3129 return true;

3130 }

3131 return false;

3132}

3133

3134void LocalCheapestInsertionFilteredHeuristic::InsertBestPickupThenDelivery(

3136 for (int pickup : index_pair.pickup_alternatives) {

3137 std::vector<NodeInsertion> pickup_insertions =

3138 ComputeEvaluatorSortedPositions(pickup);

3139 for (int delivery : index_pair.delivery_alternatives) {

3141 for (const NodeInsertion& pickup_insertion : pickup_insertions) {

3142 const int vehicle = pickup_insertion.vehicle;

3143 if (!model()->VehicleVar(delivery)->Contains(vehicle)) continue;

3144 if (MustUpdateBinCapacities() &&

3145 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},

3146 vehicle)) {

3147 continue;

3148 }

3149 for (const NodeInsertion& delivery_insertion :

3150 ComputeEvaluatorSortedPositionsOnRouteAfter(

3151 delivery, pickup, Value(pickup_insertion.insert_after),

3152 vehicle)) {

3153 if (InsertPair(pickup, pickup_insertion.insert_after, delivery,

3154 delivery_insertion.insert_after, vehicle)) {

3155 if (MustUpdateBinCapacities()) {

3156 bin_capacities_->AddItemToBin(pickup, vehicle);

3157 bin_capacities_->AddItemToBin(delivery, vehicle);

3158 }

3159 return;

3160 }

3161 }

3163 }

3164 }

3165 }

3166}

3167

3168void LocalCheapestInsertionFilteredHeuristic::InsertBestPair(

3170 for (int pickup : pair.pickup_alternatives) {

3171 for (int delivery : pair.delivery_alternatives) {

3173 std::vector<PickupDeliveryInsertion> sorted_pair_positions =

3174 ComputeEvaluatorSortedPairPositions(pickup, delivery);

3175 if (sorted_pair_positions.empty()) continue;

3176 for (const auto [insert_pickup_after, insert_delivery_after,

3177 unused_hint_weight, unused_value, vehicle] :

3178 sorted_pair_positions) {

3179 if (InsertPair(pickup, insert_pickup_after, delivery,

3180 insert_delivery_after, vehicle)) {

3181 if (MustUpdateBinCapacities()) {

3182 bin_capacities_->AddItemToBin(pickup, vehicle);

3183 bin_capacities_->AddItemToBin(delivery, vehicle);

3184 }

3185 return;

3186 }

3188 }

3189 }

3190 }

3191}

3192

3193void LocalCheapestInsertionFilteredHeuristic::InsertBestPairMultitour(

3195 using InsertionSequence = InsertionSequenceContainer::InsertionSequence;

3196 using Insertion = InsertionSequenceContainer::Insertion;

3197

3198 std::vector<int> path;

3199 std::vector<bool> path_node_is_pickup;

3200 std::vector<bool> path_node_is_delivery;

3201

3202 auto fill_path = [&path, &path_node_is_pickup, &path_node_is_delivery,

3203 this](int vehicle) {

3204 path.clear();

3205 path_node_is_pickup.clear();

3206 path_node_is_delivery.clear();

3207 const int start = model()->Start(vehicle);

3209 for (int node = start; node != end; node = Value(node)) {

3210 path.push_back(node);

3211 path_node_is_pickup.push_back(model()->IsPickup(node));

3212 path_node_is_delivery.push_back(model()->IsDelivery(node));

3213 }

3214 path.push_back(end);

3215 };

3216

3217

3218 auto price_insertion_sequences = [this]() {

3219 for (InsertionSequence sequence : insertion_container_) {

3220 int64_t sequence_cost = 0;

3221 int previous_node = -1;

3222 int previous_succ = -1;

3223 int hint_weight = 0;

3224 for (const Insertion& insertion : sequence) {

3225 const int succ = previous_node == insertion.pred

3226 ? previous_succ

3227 : Value(insertion.pred);

3228 hint_weight += IsHint(insertion.pred, insertion.node);

3229 hint_weight += IsHint(insertion.node, succ);

3231 InsertBetween(insertion.node, insertion.pred, succ,

3232 sequence.Vehicle());

3233 } else {

3235 insertion.node, insertion.pred, succ, sequence.Vehicle());

3236 CapAddTo(cost, &sequence_cost);

3237 }

3238 previous_node = insertion.node;

3239 previous_succ = succ;

3240 }

3242 sequence_cost =

3243 Evaluate(false, hint_weight > 0)

3245 }

3246 sequence.Cost() = sequence_cost;

3247 sequence.SetHintWeight(hint_weight);

3248 }

3249 if (bin_capacities_ == nullptr || evaluator_ == nullptr) return;

3250 for (InsertionSequence sequence : insertion_container_) {

3251 const int64_t old_cost = bin_capacities_->TotalCost();

3252 for (const Insertion& insertion : sequence) {

3253 bin_capacities_->AddItemToBin(insertion.node, sequence.Vehicle());

3254 }

3255 const int64_t new_cost = bin_capacities_->TotalCost();

3256 const int64_t delta_cost = CapSub(new_cost, old_cost);

3257 CapAddTo(delta_cost, &sequence.Cost());

3258 for (const Insertion& insertion : sequence) {

3259 bin_capacities_->RemoveItemFromBin(insertion.node, sequence.Vehicle());

3260 }

3261 }

3262 };

3263

3264 for (int pickup : pair.pickup_alternatives) {

3265 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);

3267 for (int delivery : pair.delivery_alternatives) {

3268 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);

3269 insertion_container_.Clear();

3270 std::unique_ptr<IntVarIterator> pickup_vehicles(

3271 pickup_vehicle_var->MakeDomainIterator(false));

3272 for (const int vehicle : InitAndGetValues(pickup_vehicles.get())) {

3273 if (vehicle == -1) continue;

3274 if (!delivery_vehicle_var->Contains(vehicle)) continue;

3275 if (MustUpdateBinCapacities() &&

3276 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},

3277 vehicle)) {

3278 continue;

3279 }

3280 fill_path(vehicle);

3281 insertion_generator_.AppendPickupDeliveryMultitourInsertions(

3282 pickup, delivery, vehicle, path, path_node_is_pickup,

3283 path_node_is_delivery, insertion_container_);

3284 }

3286 price_insertion_sequences();

3288 insertion_container_.RemoveIf(

3289 [](const InsertionSequence& sequence) -> bool {

3290 return sequence.Cost() == kint64max;

3291 });

3292 insertion_container_.Sort();

3293 for (InsertionSequence sequence : insertion_container_) {

3295 int previous_node = -1;

3296 int previous_succ = -1;

3297 const int vehicle = sequence.Vehicle();

3298 for (const Insertion& insertion : sequence) {

3299 const int succ = previous_node == insertion.pred

3300 ? previous_succ

3301 : Value(insertion.pred);

3302 InsertBetween(insertion.node, insertion.pred, succ, vehicle);

3303 previous_node = insertion.node;

3304 previous_succ = succ;

3305 }

3306 if (Evaluate(true, true)

3307 .has_value()) {

3308

3309 if (MustUpdateBinCapacities()) {

3310 bin_capacities_->AddItemToBin(pickup, vehicle);

3311 bin_capacities_->AddItemToBin(delivery, vehicle);

3312 }

3313 return;

3314 }

3315 }

3316 }

3317 }

3318}

3319

3320namespace {

3322 std::vector<bool>* data) {

3323 for (const int64_t pickup : pair.pickup_alternatives) {

3324 data->at(pickup) = false;

3325 }

3326 for (const int64_t delivery : pair.delivery_alternatives) {

3327 data->at(delivery) = false;

3328 }

3329}

3330}

3331

3427

3428void LocalCheapestInsertionFilteredHeuristic::AppendInsertionPositionsAfter(

3429 int64_t node_to_insert, int64_t start, int64_t next_after_start,

3430 int vehicle, std::vector<NodeInsertion>* node_insertions) {

3431 DCHECK(node_insertions != nullptr);

3432 int64_t insert_after = start;

3433 if (!model()->VehicleVar(node_to_insert)->Contains(vehicle)) return;

3434 while (!model()->IsEnd(insert_after)) {

3435 const int64_t insert_before =

3436 (insert_after == start) ? next_after_start : Value(insert_after);

3437 const int hint_weight = IsHint(insert_after, node_to_insert) +

3438 IsHint(node_to_insert, insert_before) -

3439 IsHint(insert_after, insert_before);

3441 node_to_insert, insert_after, insert_before, vehicle, hint_weight);

3442 if (insertion_cost.has_value()) {

3443 node_insertions->push_back(

3444 {insert_after, vehicle, -hint_weight, *insertion_cost});

3445 }

3446 insert_after = insert_before;

3447 }

3448}

3449

3450std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>

3451LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPositions(

3452 int64_t node) {

3454 const int size = model()->Size();

3455 if (node >= size) return {};

3456 std::vector<NodeInsertion> sorted_insertions;

3458 std::unique_ptr<IntVarIterator> node_vehicles(

3459 vehicle_var->MakeDomainIterator(false));

3460 for (const int vehicle : InitAndGetValues(node_vehicles.get())) {

3461 if (vehicle == -1) continue;

3462 if (MustUpdateBinCapacities() &&

3463 !bin_capacities_->CheckAdditionFeasibility(node, vehicle)) {

3464 continue;

3465 }

3466 const int64_t start = model()->Start(vehicle);

3467 const size_t old_num_insertions = sorted_insertions.size();

3468 AppendInsertionPositionsAfter(node, start, Value(start), vehicle,

3469 &sorted_insertions);

3470 if (MustUpdateBinCapacities() && evaluator_) {

3471

3472 const int64_t old_cost = bin_capacities_->TotalCost();

3473 bin_capacities_->AddItemToBin(node, vehicle);

3474 const int64_t new_cost = bin_capacities_->TotalCost();

3475 bin_capacities_->RemoveItemFromBin(node, vehicle);

3476 const int64_t delta_cost = CapSub(new_cost, old_cost);

3477

3478 for (size_t i = old_num_insertions; i < sorted_insertions.size(); ++i) {

3479 CapAddTo(delta_cost, &sorted_insertions[i].value);

3480 }

3481 }

3482 }

3483 absl::c_sort(sorted_insertions);

3484 return sorted_insertions;

3485}

3486

3487std::vector<LocalCheapestInsertionFilteredHeuristic::NodeInsertion>

3488LocalCheapestInsertionFilteredHeuristic::

3489 ComputeEvaluatorSortedPositionsOnRouteAfter(int64_t node, int64_t start,

3490 int64_t next_after_start,

3491 int vehicle) {

3493 const int size = model()->Size();

3494 if (node >= size) return {};

3495 std::vector<NodeInsertion> sorted_insertions;

3496 AppendInsertionPositionsAfter(node, start, next_after_start, vehicle,

3497 &sorted_insertions);

3498 absl::c_sort(sorted_insertions);

3499 return sorted_insertions;

3500}

3501

3502std::vector<PickupDeliveryInsertion>

3503LocalCheapestInsertionFilteredHeuristic::ComputeEvaluatorSortedPairPositions(

3504 int pickup, int delivery) {

3505 std::vector<PickupDeliveryInsertion> sorted_pickup_delivery_insertions;

3506 const int size = model()->Size();

3507 DCHECK_LT(pickup, size);

3508 DCHECK_LT(delivery, size);

3509 const IntVar* pickup_vehicle_var = model()->VehicleVar(pickup);

3510 const IntVar* delivery_vehicle_var = model()->VehicleVar(delivery);

3511 std::unique_ptr<IntVarIterator> pickup_vehicles(

3512 pickup_vehicle_var->MakeDomainIterator(false));

3513 for (const int vehicle : InitAndGetValues(pickup_vehicles.get())) {

3514 if (vehicle == -1) continue;

3515 if (!delivery_vehicle_var->Contains(vehicle)) continue;

3516 if (MustUpdateBinCapacities() &&

3517 !bin_capacities_->CheckAdditionsFeasibility({pickup, delivery},

3518 vehicle)) {

3519 continue;

3520 }

3521 int64_t insert_pickup_after = model()->Start(vehicle);

3522 while (!model()->IsEnd(insert_pickup_after)) {

3523 const int64_t insert_pickup_before = Value(insert_pickup_after);

3524 int64_t insert_delivery_after = pickup;

3525 while (!model()->IsEnd(insert_delivery_after)) {

3527 const int64_t insert_delivery_before =

3528 insert_delivery_after == pickup ? insert_pickup_before

3529 : Value(insert_delivery_after);

3530 const int hint_weight = IsHint(insert_pickup_after, pickup) +

3531 IsHint(insert_delivery_after, delivery) +

3532 IsHint(pickup, insert_pickup_before) +

3533 IsHint(delivery, insert_delivery_before);

3535 pickup, insert_pickup_after, delivery, insert_delivery_after,

3536 vehicle, hint_weight);

3537 if (insertion_cost.has_value()) {

3538 int64_t total_cost = *insertion_cost;

3539 if (evaluator_ && MustUpdateBinCapacities()) {

3540 const int64_t old_cost = bin_capacities_->TotalCost();

3541 bin_capacities_->AddItemToBin(pickup, vehicle);

3542 bin_capacities_->AddItemToBin(delivery, vehicle);

3543 const int64_t new_cost = bin_capacities_->TotalCost();

3545 bin_capacities_->RemoveItemFromBin(pickup, vehicle);

3546 bin_capacities_->RemoveItemFromBin(delivery, vehicle);

3547 }

3548 sorted_pickup_delivery_insertions.push_back(

3549 {insert_pickup_after, insert_delivery_after, -hint_weight,

3550 total_cost, vehicle});

3551 }

3552 insert_delivery_after = insert_delivery_before;

3553 }

3554 insert_pickup_after = insert_pickup_before;

3555 }

3556 }

3557 absl::c_sort(sorted_pickup_delivery_insertions);

3558 return sorted_pickup_delivery_insertions;

3559}

3560

3561

3562

3567

3698

3699bool CheapestAdditionFilteredHeuristic::

3700 PartialRoutesAndLargeVehicleIndicesFirst::operator()(int vehicle1,

3701 int vehicle2) const {

3702 const bool has_partial_route1 = (builder_.model()->Start(vehicle1) !=

3703 builder_.GetStartChainEnd(vehicle1));

3704 const bool has_partial_route2 = (builder_.model()->Start(vehicle2) !=

3705 builder_.GetStartChainEnd(vehicle2));

3706 if (has_partial_route1 == has_partial_route2) {

3707 return vehicle2 < vehicle1;

3708 } else {

3709 return has_partial_route2 < has_partial_route1;

3710 }

3711}

3712

3713

3714

3723

3724int64_t EvaluatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(

3725 int64_t node, const std::vector<int64_t>& successors) {

3726 int64_t best_evaluation = std::numeric_limits<int64_t>::max();

3727 int64_t best_successor = -1;

3728 for (int64_t successor : successors) {

3729 const int64_t evaluation = (successor >= 0)

3730 ? evaluator_(node, successor)

3731 : std::numeric_limits<int64_t>::max();

3732 if (evaluation < best_evaluation ||

3733 (evaluation == best_evaluation && successor > best_successor)) {

3734 best_evaluation = evaluation;

3735 best_successor = successor;

3736 }

3737 }

3738 return best_successor;

3739}

3740

3741void EvaluatorCheapestAdditionFilteredHeuristic::SortSuccessors(

3742 int64_t node, std::vector<int64_t>* successors) {

3743 std::vector<std::pair<int64_t, int64_t>> values;

3744 values.reserve(successors->size());

3745 for (int64_t successor : *successors) {

3746

3747

3748 values.push_back({evaluator_(node, successor), successor});

3749 }

3750 absl::c_sort(values, [](const std::pair<int64_t, int64_t>& s1,

3751 const std::pair<int64_t, int64_t>& s2) {

3752 return s1.first < s2.first ||

3753 (s1.first == s2.first && s1.second > s2.second);

3754 });

3755 successors->clear();

3756 for (auto value : values) {

3757 successors->push_back(value.second);

3758 }

3759}

3760

3761

3762

3771

3772int64_t ComparatorCheapestAdditionFilteredHeuristic::FindTopSuccessor(

3773 int64_t node, const std::vector<int64_t>& successors) {

3774 return *absl::c_min_element(

3775 successors, [this, node](int successor1, int successor2) {

3776 return comparator_(node, successor1, successor2);

3777 });

3778}

3779

3780void ComparatorCheapestAdditionFilteredHeuristic::SortSuccessors(

3781 int64_t node, std::vector<int64_t>* successors) {

3782 absl::c_sort(*successors, [this, node](int successor1, int successor2) {

3783 return comparator_(node, successor1, successor2);

3784 });

3785}

3786

3787

3788

3789

3790

3791

3792

3793

3794

3795

3796

3797

3798

3799

3800

3801

3802

3803

3804

3805

3806

3807

3808

3809

3810

3811

3812

3813

3814

3815

3816

3817

3818

3819

3820

3821

3822

3823

3824

3825

3826

3827

3828

3829

3830

3831

3832

3833

3834

3835template <typename Saving>

4215

4216

4217

4229

4231

4250

4272

4273void SavingsFilteredHeuristic::AddSymmetricArcsToAdjacencyLists(

4274 std::vector<std::vector<int64_t>>* adjacency_lists) {

4275 for (int64_t node = 0; node < adjacency_lists->size(); node++) {

4276 for (int64_t neighbor : (*adjacency_lists)[node]) {

4277 if (model()->IsStart(neighbor) || model()->IsEnd(neighbor)) {

4278 continue;

4279 }

4280 (*adjacency_lists)[neighbor].push_back(node);

4281 }

4282 }

4283 absl::c_transform(*adjacency_lists, adjacency_lists->begin(),

4284 [](std::vector<int64_t> vec) {

4285 absl::c_sort(vec);

4286 vec.erase(std::unique(vec.begin(), vec.end()), vec.end());

4287 return vec;

4288 });

4289}

4290

4291

4292

4293

4294

4295

4296

4297

4298

4299

4300

4301

4302bool SavingsFilteredHeuristic::ComputeSavings() {

4304 const int size = model()->Size();

4305

4306 std::vector<int64_t> uncontained_non_start_end_nodes;

4307 uncontained_non_start_end_nodes.reserve(size);

4308 for (int node = 0; node < size; node++) {

4309 if (!model()->IsStart(node) && !model()->IsEnd(node) && !Contains(node)) {

4310 uncontained_non_start_end_nodes.push_back(node);

4311 }

4312 }

4313

4314 const int64_t saving_neighbors =

4315 std::min(MaxNumNeighborsPerNode(num_vehicle_types),

4316 static_cast<int64_t>(uncontained_non_start_end_nodes.size()));

4317

4319 std::make_unique<SavingsContainer<Saving>>(this, num_vehicle_types);

4322 std::vector<std::vector<int64_t>> adjacency_lists(size);

4323

4324 for (int type = 0; type < num_vehicle_types; ++type) {

4325 const int vehicle =

4327 if (vehicle < 0) continue;

4328

4329 const int64_t cost_class =

4331 const int64_t start = model()->Start(vehicle);

4332 const int64_t end = model()->End(vehicle);

4334

4335

4336

4337 for (int before_node : uncontained_non_start_end_nodes) {

4338 std::vector<std::pair< int64_t, int64_t>>

4339 costed_after_nodes;

4340 costed_after_nodes.reserve(uncontained_non_start_end_nodes.size());

4342 for (int after_node : uncontained_non_start_end_nodes) {

4343 if (after_node != before_node) {

4344 costed_after_nodes.push_back(std::make_pair(

4345 model()->GetArcCostForClass(before_node, after_node, cost_class),

4346 after_node));

4347 }

4348 }

4349 if (saving_neighbors < costed_after_nodes.size()) {

4350 std::nth_element(costed_after_nodes.begin(),

4351 costed_after_nodes.begin() + saving_neighbors,

4352 costed_after_nodes.end());

4353 costed_after_nodes.resize(saving_neighbors);

4354 }

4355 adjacency_lists[before_node].resize(costed_after_nodes.size());

4356 std::transform(costed_after_nodes.begin(), costed_after_nodes.end(),

4357 adjacency_lists[before_node].begin(),

4358 [](std::pair<int64_t, int64_t> cost_and_node) {

4359 return cost_and_node.second;

4360 });

4361 }

4362 if (savings_params_.add_reverse_arcs()) {

4363 AddSymmetricArcsToAdjacencyLists(&adjacency_lists);

4364 }

4366

4367

4368 for (int before_node : uncontained_non_start_end_nodes) {

4369 const int64_t before_to_end_cost =

4371 const int64_t start_to_before_cost =

4372 CapSub(model()->GetArcCostForClass(start, before_node, cost_class),

4373 fixed_cost);

4375 for (int64_t after_node : adjacency_lists[before_node]) {

4376 if (model()->IsStart(after_node) || model()->IsEnd(after_node) ||

4377 before_node == after_node || Contains(after_node)) {

4378 continue;

4379 }

4380 const int64_t arc_cost =

4382 const int64_t start_to_after_cost =

4383 CapSub(model()->GetArcCostForClass(start, after_node, cost_class),

4384 fixed_cost);

4385 const int64_t after_to_end_cost =

4387

4388 const double weighted_arc_cost_fp =

4389 savings_params_.arc_coefficient() * arc_cost;

4390 const int64_t weighted_arc_cost =

4391 weighted_arc_cost_fp < std::numeric_limits<int64_t>::max()

4392 ? static_cast<int64_t>(weighted_arc_cost_fp)

4393 : std::numeric_limits<int64_t>::max();

4394 const int64_t saving_value = CapSub(

4395 CapAdd(before_to_end_cost, start_to_after_cost), weighted_arc_cost);

4396

4397 const Saving saving =

4398 BuildSaving(-saving_value, type, before_node, after_node);

4399

4400 const int64_t total_cost =

4401 CapAdd(CapAdd(start_to_before_cost, arc_cost), after_to_end_cost);

4402

4404 after_node, type);

4405 }

4406 }

4407 }

4410}

4411

4412int64_t SavingsFilteredHeuristic::MaxNumNeighborsPerNode(

4413 int num_vehicle_types) const {

4414 const int64_t size = model()->Size();

4415

4416 const int64_t num_neighbors_with_ratio =

4417 std::max(1.0, size * savings_params_.neighbors_ratio());

4418

4419

4420

4421

4422

4423 const double max_memory_usage_in_savings_unit =

4424 savings_params_.max_memory_usage_bytes() / 16;

4425

4426

4427

4428

4429

4430

4431

4432

4433

4434

4435

4436

4437

4438

4439

4441 if (num_vehicle_types > 1) {

4442 multiplicative_factor += 1.5;

4443 }

4444 const double num_savings =

4445 max_memory_usage_in_savings_unit / multiplicative_factor;

4446 const int64_t num_neighbors_with_memory_restriction =

4447 std::max(1.0, num_savings / (num_vehicle_types * size));

4448

4449 return std::min(num_neighbors_with_ratio,

4450 num_neighbors_with_memory_restriction);

4451}

4452

4453

4454

4457 DCHECK_GT(vehicle_types, 0);

4458 const int size = model()->Size();

4459

4460

4461 std::vector<std::vector<const Saving*>> in_savings_ptr(size * vehicle_types);

4462 std::vector<std::vector<const Saving*>> out_savings_ptr(size * vehicle_types);

4463 for (int type = 0; type < vehicle_types; type++) {

4464 const int vehicle_type_offset = type * size;

4465 const std::vector<Saving>& sorted_savings_for_type =

4467 for (const Saving& saving : sorted_savings_for_type) {

4468 DCHECK_EQ(saving.vehicle_type, type);

4469 const int before_node = saving.before_node;

4470 in_savings_ptr[vehicle_type_offset + before_node].push_back(&saving);

4471 const int after_node = saving.after_node;

4472 out_savings_ptr[vehicle_type_offset + after_node].push_back(&saving);

4473 }

4474 }

4475

4476

4479

4481 int before_node = saving.before_node;

4482 int after_node = saving.after_node;

4483 const bool nodes_contained = Contains(before_node) || Contains(after_node);

4484

4485 if (nodes_contained) {

4487 continue;

4488 }

4489

4490

4491 const int type = saving.vehicle_type;

4492 const int vehicle =

4494 if (vehicle < 0) {

4496 continue;

4497 }

4498

4499 const int64_t start = model()->Start(vehicle);

4500 const int64_t end = model()->End(vehicle);

4501

4502 int in_index = 0;

4503 int out_index = 0;

4504 const int saving_offset = type * size;

4505

4506 while (in_index < in_savings_ptr[saving_offset + after_node].size() ||

4507 out_index < out_savings_ptr[saving_offset + before_node].size()) {

4509

4510 int before_before_node = -1;

4511 int after_after_node = -1;

4512 if (in_index < in_savings_ptr[saving_offset + after_node].size()) {

4513 const Saving& in_saving =

4514 *(in_savings_ptr[saving_offset + after_node][in_index]);

4515 if (out_index < out_savings_ptr[saving_offset + before_node].size()) {

4516 const Saving& out_saving =

4517 *(out_savings_ptr[saving_offset + before_node][out_index]);

4518 if (in_saving.saving < out_saving.saving) {

4519 after_after_node = in_saving.after_node;

4520 } else {

4521 before_before_node = out_saving.before_node;

4522 }

4523 } else {

4524 after_after_node = in_saving.after_node;

4525 }

4526 } else {

4527 before_before_node =

4528 out_savings_ptr[saving_offset + before_node][out_index]

4529 ->before_node;

4530 }

4531

4532 if (after_after_node != -1) {

4533 DCHECK_EQ(before_before_node, -1);

4534 ++in_index;

4535

4536 if (!Contains(after_after_node)) {

4537 SetNext(after_node, after_after_node, vehicle);

4538 SetNext(after_after_node, end, vehicle);

4539 if (Evaluate(true).has_value()) {

4540 in_index = 0;

4541 after_node = after_after_node;

4542 }

4543 }

4544 } else {

4545

4546 CHECK_GE(before_before_node, 0);

4547 ++out_index;

4548 if (!Contains(before_before_node)) {

4549 SetNext(start, before_before_node, vehicle);

4550 SetNext(before_before_node, before_node, vehicle);

4551 if (Evaluate(true).has_value()) {

4552 out_index = 0;

4553 before_node = before_before_node;

4554 }

4555 }

4556 }

4557 }

4559 }

4560}

4561

4562

4563

4565

4566

4567 const int64_t size = model()->Size();

4569

4570 first_node_on_route_.resize(vehicles, -1);

4571 last_node_on_route_.resize(vehicles, -1);

4572 vehicle_of_first_or_last_node_.resize(size, -1);

4573

4574 for (int vehicle = 0; vehicle < vehicles; vehicle++) {

4575 const int64_t start = model()->Start(vehicle);

4576 const int64_t end = model()->End(vehicle);

4578 continue;

4579 }

4580 int64_t node = Value(start);

4581 if (node != end) {

4582 vehicle_of_first_or_last_node_[node] = vehicle;

4583 first_node_on_route_[vehicle] = node;

4584

4585 int64_t next = Value(node);

4586 while (next != end) {

4587 node = next;

4588 next = Value(node);

4589 }

4590 vehicle_of_first_or_last_node_[node] = vehicle;

4591 last_node_on_route_[vehicle] = node;

4592 }

4593 }

4594

4598 const int64_t before_node = saving.before_node;

4599 const int64_t after_node = saving.after_node;

4600 const int type = saving.vehicle_type;

4601

4603

4604 bool committed = false;

4605

4606 const int vehicle =

4608

4609 if (vehicle >= 0) {

4610 committed = true;

4611

4612 vehicle_of_first_or_last_node_[before_node] = vehicle;

4613 vehicle_of_first_or_last_node_[after_node] = vehicle;

4614 first_node_on_route_[vehicle] = before_node;

4615 last_node_on_route_[vehicle] = after_node;

4618 }

4620 continue;

4621 }

4622

4624

4625

4626

4627 const int v1 = vehicle_of_first_or_last_node_[before_node];

4628 const int64_t last_node = v1 == -1 ? -1 : last_node_on_route_[v1];

4629

4630 const int v2 = vehicle_of_first_or_last_node_[after_node];

4631 const int64_t first_node = v2 == -1 ? -1 : first_node_on_route_[v2];

4632

4633 if (before_node == last_node && after_node == first_node && v1 != v2 &&

4635 CHECK_EQ(Value(before_node), model()->End(v1));

4636 CHECK_EQ(Value(model()->Start(v2)), after_node);

4637

4638

4639

4640

4641

4642 MergeRoutes(v1, v2, before_node, after_node);

4643 }

4644 }

4645

4647 const int vehicle = vehicle_of_first_or_last_node_[before_node];

4648 const int64_t last_node =

4649 vehicle == -1 ? -1 : last_node_on_route_[vehicle];

4650

4651 if (before_node == last_node) {

4652 const int64_t end = model()->End(vehicle);

4653 CHECK_EQ(Value(before_node), end);

4654

4656 if (type != route_type) {

4657

4658

4660 continue;

4661 }

4662

4663

4664 SetNext(before_node, after_node, vehicle);

4666 if (Evaluate(true).has_value()) {

4667 if (first_node_on_route_[vehicle] != before_node) {

4668

4669 DCHECK_NE(Value(model()->Start(vehicle)), before_node);

4670 vehicle_of_first_or_last_node_[before_node] = -1;

4671 }

4672 vehicle_of_first_or_last_node_[after_node] = vehicle;

4673 last_node_on_route_[vehicle] = after_node;

4675 }

4676 }

4677 }

4678

4680 const int vehicle = vehicle_of_first_or_last_node_[after_node];

4681 const int64_t first_node =

4682 vehicle == -1 ? -1 : first_node_on_route_[vehicle];

4683

4684 if (after_node == first_node) {

4685 const int64_t start = model()->Start(vehicle);

4686 CHECK_EQ(Value(start), after_node);

4687

4689 if (type != route_type) {

4690

4691

4693 continue;

4694 }

4695

4696

4697 SetNext(before_node, after_node, vehicle);

4698 SetNext(start, before_node, vehicle);

4699 if (Evaluate(true).has_value()) {

4700 if (last_node_on_route_[vehicle] != after_node) {

4701

4702 DCHECK_NE(Value(after_node), model()->End(vehicle));

4703 vehicle_of_first_or_last_node_[after_node] = -1;

4704 }

4705 vehicle_of_first_or_last_node_[before_node] = vehicle;

4706 first_node_on_route_[vehicle] = before_node;

4708 }

4709 }

4710 }

4712 }

4713}

4714

4715void ParallelSavingsFilteredHeuristic::MergeRoutes(int first_vehicle,

4716 int second_vehicle,

4717 int64_t before_node,

4718 int64_t after_node) {

4720 const int64_t new_first_node = first_node_on_route_[first_vehicle];

4721 DCHECK_EQ(vehicle_of_first_or_last_node_[new_first_node], first_vehicle);

4722 CHECK_EQ(Value(model()->Start(first_vehicle)), new_first_node);

4723 const int64_t new_last_node = last_node_on_route_[second_vehicle];

4724 DCHECK_EQ(vehicle_of_first_or_last_node_[new_last_node], second_vehicle);

4725 CHECK_EQ(Value(new_last_node), model()->End(second_vehicle));

4726

4727

4728 int used_vehicle = first_vehicle;

4729 int unused_vehicle = second_vehicle;

4730 if (model()->GetFixedCostOfVehicle(first_vehicle) >

4731 model()->GetFixedCostOfVehicle(second_vehicle)) {

4732 used_vehicle = second_vehicle;

4733 unused_vehicle = first_vehicle;

4734 }

4735

4736 SetNext(before_node, after_node, used_vehicle);

4737 SetNext(model()->Start(unused_vehicle), model()->End(unused_vehicle),

4738 unused_vehicle);

4739 if (used_vehicle == first_vehicle) {

4740 SetNext(new_last_node, model()->End(used_vehicle), used_vehicle);

4741 } else {

4742 SetNext(model()->Start(used_vehicle), new_first_node, used_vehicle);

4743 }

4744 bool committed = Evaluate(true).has_value();

4745 if (!committed &&

4746 model()->GetVehicleClassIndexOfVehicle(first_vehicle).value() !=

4747 model()->GetVehicleClassIndexOfVehicle(second_vehicle).value()) {

4748

4749 std::swap(used_vehicle, unused_vehicle);

4750 SetNext(before_node, after_node, used_vehicle);

4751 SetNext(model()->Start(unused_vehicle), model()->End(unused_vehicle),

4752 unused_vehicle);

4753 if (used_vehicle == first_vehicle) {

4754 SetNext(new_last_node, model()->End(used_vehicle), used_vehicle);

4755 } else {

4756 SetNext(model()->Start(used_vehicle), new_first_node, used_vehicle);

4757 }

4758 committed = Evaluate(true).has_value();

4759 }

4760 if (committed) {

4761

4763 unused_vehicle,

4764 model()->GetVehicleClassIndexOfVehicle(unused_vehicle).value(),

4765 model()->GetFixedCostOfVehicle(unused_vehicle));

4766

4767

4768 first_node_on_route_[unused_vehicle] = -1;

4769 last_node_on_route_[unused_vehicle] = -1;

4770 vehicle_of_first_or_last_node_[before_node] = -1;

4771 vehicle_of_first_or_last_node_[after_node] = -1;

4772 first_node_on_route_[used_vehicle] = new_first_node;

4773 last_node_on_route_[used_vehicle] = new_last_node;

4774 vehicle_of_first_or_last_node_[new_last_node] = used_vehicle;

4775 vehicle_of_first_or_last_node_[new_first_node] = used_vehicle;

4776 }

4777}

4778

4779

4780

4786

4787

4864

4865

4866

4867

4868namespace {

4869struct SweepIndex {

4870 SweepIndex(const int64_t index, const double angle, const double distance)

4871 : index(index), angle(angle), distance(distance) {}

4872 ~SweepIndex() = default;

4873

4874 int64_t index;

4875 double angle;

4876 double distance;

4877};

4878

4879struct SweepIndexSortAngle {

4880 bool operator()(const SweepIndex& node1, const SweepIndex& node2) const {

4881 return (node1.angle < node2.angle);

4882 }

4883} SweepIndexAngleComparator;

4884

4885struct SweepIndexSortDistance {

4886 bool operator()(const SweepIndex& node1, const SweepIndex& node2) const {

4887 return (node1.distance < node2.distance);

4888 }

4889} SweepIndexDistanceComparator;

4890}

4891

4900

4901

4902

4937

4938namespace {

4939

4940struct Link {

4941 Link(std::pair<int, int> link, double value, int vehicle_class,

4942 int64_t start_depot, int64_t end_depot)

4943 : link(link),

4944 value(value),

4945 vehicle_class(vehicle_class),

4946 start_depot(start_depot),

4947 end_depot(end_depot) {}

4948 ~Link() = default;

4949

4950 std::pair<int, int> link;

4951 int64_t value;

4952 int vehicle_class;

4953 int64_t start_depot;

4954 int64_t end_depot;

4955};

4956

4957

4958

4959

4960

4961

4962class RouteConstructor {

4963 public:

4964 RouteConstructor(Assignment* const assignment, RoutingModel* const model,

4965 bool check_assignment, int64_t num_indices,

4966 const std::vector<Link>& links_list)

4967 : assignment_(assignment),

4968 model_(model),

4969 check_assignment_(check_assignment),

4970 solver_(model_->solver()),

4971 num_indices_(num_indices),

4972 links_list_(links_list),

4973 nexts_(model_->Nexts()),

4974 in_route_(num_indices_, -1),

4975 final_routes_(),

4976 index_to_chain_index_(num_indices, -1),

4977 index_to_vehicle_class_index_(num_indices, -1) {

4978 {

4979 const std::vector<std::string> dimension_names =

4980 model_->GetAllDimensionNames();

4981 dimensions_.assign(dimension_names.size(), nullptr);

4982 for (int i = 0; i < dimension_names.size(); ++i) {

4983 dimensions_[i] = &model_->GetDimensionOrDie(dimension_names[i]);

4984 }

4985 }

4986 cumuls_.resize(dimensions_.size());

4987 for (std::vector<int64_t>& cumuls : cumuls_) {

4988 cumuls.resize(num_indices_);

4989 }

4990 new_possible_cumuls_.resize(dimensions_.size());

4991 }

4992

4993 ~RouteConstructor() = default;

4994

4995 void Construct() {

4996 model_->solver()->TopPeriodicCheck();

4997

4998 for (int index = 0; index < num_indices_; ++index) {

4999 if (!model_->IsStart(index) && !model_->IsEnd(index)) {

5000 routes_.push_back({index});

5001 in_route_[index] = routes_.size() - 1;

5002 }

5003 }

5004

5005 for (const Link& link : links_list_) {

5006 model_->solver()->TopPeriodicCheck();

5007 const int index1 = link.link.first;

5008 const int index2 = link.link.second;

5009 const int vehicle_class = link.vehicle_class;

5010 const int64_t start_depot = link.start_depot;

5011 const int64_t end_depot = link.end_depot;

5012

5013

5014 if (index_to_vehicle_class_index_[index1] < 0) {

5015 for (int dimension_index = 0; dimension_index < dimensions_.size();

5016 ++dimension_index) {

5017 cumuls_[dimension_index][index1] =

5018 std::max(dimensions_[dimension_index]->GetTransitValue(

5019 start_depot, index1, 0),

5020 dimensions_[dimension_index]->CumulVar(index1)->Min());

5021 }

5022 }

5023 if (index_to_vehicle_class_index_[index2] < 0) {

5024 for (int dimension_index = 0; dimension_index < dimensions_.size();

5025 ++dimension_index) {

5026 cumuls_[dimension_index][index2] =

5027 std::max(dimensions_[dimension_index]->GetTransitValue(

5028 start_depot, index2, 0),

5029 dimensions_[dimension_index]->CumulVar(index2)->Min());

5030 }

5031 }

5032

5033 const int route_index1 = in_route_[index1];

5034 const int route_index2 = in_route_[index2];

5035 const bool merge =

5036 route_index1 >= 0 && route_index2 >= 0 &&

5037 FeasibleMerge(routes_[route_index1], routes_[route_index2], index1,

5038 index2, route_index1, route_index2, vehicle_class,

5039 start_depot, end_depot);

5040 if (Merge(merge, route_index1, route_index2)) {

5041 index_to_vehicle_class_index_[index1] = vehicle_class;

5042 index_to_vehicle_class_index_[index2] = vehicle_class;

5043 }

5044 }

5045

5046 model_->solver()->TopPeriodicCheck();

5047

5048

5049

5050 for (int chain_index = 0; chain_index < chains_.size(); ++chain_index) {

5051 if (!deleted_chains_.contains(chain_index)) {

5052 final_chains_.push_back(chains_[chain_index]);

5053 }

5054 }

5055 absl::c_sort(final_chains_, ChainComparator);

5056 for (int route_index = 0; route_index < routes_.size(); ++route_index) {

5057 if (!deleted_routes_.contains(route_index)) {

5058 final_routes_.push_back(routes_[route_index]);

5059 }

5060 }

5061 absl::c_sort(final_routes_, RouteComparator);

5062

5063 const int extra_vehicles = std::max(

5064 0, static_cast<int>(final_chains_.size()) - model_->vehicles());

5065

5066 int chain_index = 0;

5067 for (chain_index = extra_vehicles; chain_index < final_chains_.size();

5068 ++chain_index) {

5069 if (chain_index - extra_vehicles >= model_->vehicles()) {

5070 break;

5071 }

5072 const int start = final_chains_[chain_index].head;

5073 const int end = final_chains_[chain_index].tail;

5074 assignment_->Add(

5075 model_->NextVar(model_->Start(chain_index - extra_vehicles)));

5076 assignment_->SetValue(

5077 model_->NextVar(model_->Start(chain_index - extra_vehicles)), start);

5078 assignment_->Add(nexts_[end]);

5079 assignment_->SetValue(nexts_[end],

5080 model_->End(chain_index - extra_vehicles));

5081 }

5082

5083

5084 for (int route_index = 0; route_index < final_routes_.size();

5085 ++route_index) {

5086 if (chain_index - extra_vehicles >= model_->vehicles()) {

5087 break;

5088 }

5089 DCHECK_LT(route_index, final_routes_.size());

5090 const int head = final_routes_[route_index].front();

5091 const int tail = final_routes_[route_index].back();

5092 if (head == tail && head < model_->Size()) {

5093 assignment_->Add(

5094 model_->NextVar(model_->Start(chain_index - extra_vehicles)));

5095 assignment_->SetValue(

5096 model_->NextVar(model_->Start(chain_index - extra_vehicles)), head);

5097 assignment_->Add(nexts_[tail]);

5098 assignment_->SetValue(nexts_[tail],

5099 model_->End(chain_index - extra_vehicles));

5100 ++chain_index;

5101 }

5102 }

5103

5104

5105 for (int index = 0; index < model_->Size(); ++index) {

5106 IntVar* const next = nexts_[index];

5107 if (!assignment_->Contains(next)) {

5108 assignment_->Add(next);

5109 if (next->Contains(index)) {

5110 assignment_->SetValue(next, index);

5111 }

5112 }

5113 }

5114 }

5115

5116 private:

5117 enum MergeStatus { FIRST_SECOND, SECOND_FIRST, NO_MERGE };

5118

5119 struct RouteSort {

5120 bool operator()(absl::Span<const int> route1,

5121 absl::Span<const int> route2) const {

5122 return (route1.size() < route2.size());

5123 }

5124 } RouteComparator;

5125

5126 struct Chain {

5127 int head;

5128 int tail;

5129 int nodes;

5130 };

5131

5132 struct ChainSort {

5133 bool operator()(const Chain& chain1, const Chain& chain2) const {

5134 return (chain1.nodes < chain2.nodes);

5135 }

5136 } ChainComparator;

5137

5138 bool Head(int node) const {

5139 return (node == routes_[in_route_[node]].front());

5140 }

5141

5142 bool Tail(int node) const {

5143 return (node == routes_[in_route_[node]].back());

5144 }

5145

5146 bool FeasibleRoute(const std::vector<int>& route, int64_t route_cumul,

5147 int dimension_index) {

5148 const RoutingDimension& dimension = *dimensions_[dimension_index];

5149 std::vector<int>::const_iterator it = route.begin();

5150 int64_t cumul = route_cumul;

5151 while (it != route.end()) {

5152 const int previous = *it;

5153 const int64_t cumul_previous = cumul;

5154 gtl::InsertOrDie(&(new_possible_cumuls_[dimension_index]), previous,

5155 cumul_previous);

5156 ++it;

5157 if (it == route.end()) {

5158 return true;

5159 }

5160 const int next = *it;

5161 int64_t available_from_previous =

5162 cumul_previous + dimension.GetTransitValue(previous, next, 0);

5163 int64_t available_cumul_next =

5164 std::max(cumuls_[dimension_index][next], available_from_previous);

5165

5166 const int64_t slack = available_cumul_next - available_from_previous;

5167 if (slack > dimension.SlackVar(previous)->Max()) {

5168 available_cumul_next =

5169 available_from_previous + dimension.SlackVar(previous)->Max();

5170 }

5171

5172 if (available_cumul_next > dimension.CumulVar(next)->Max()) {

5173 return false;

5174 }

5175 if (available_cumul_next <= cumuls_[dimension_index][next]) {

5176 return true;

5177 }

5178 cumul = available_cumul_next;

5179 }

5180 return true;

5181 }

5182

5183 bool CheckRouteConnection(absl::Span<const int> route1,

5184 const std::vector<int>& route2, int dimension_index,

5185 int64_t , int64_t end_depot) {

5186 const int tail1 = route1.back();

5187 const int head2 = route2.front();

5188 const int tail2 = route2.back();

5189 const RoutingDimension& dimension = *dimensions_[dimension_index];

5190 int non_depot_node = -1;

5191 for (int node = 0; node < num_indices_; ++node) {

5192 if (!model_->IsStart(node) && !model_->IsEnd(node)) {

5193 non_depot_node = node;

5194 break;

5195 }

5196 }

5197 CHECK_GE(non_depot_node, 0);

5198 const int64_t depot_threshold =

5199 std::max(dimension.SlackVar(non_depot_node)->Max(),

5200 dimension.CumulVar(non_depot_node)->Max());

5201

5202 int64_t available_from_tail1 = cumuls_[dimension_index][tail1] +

5203 dimension.GetTransitValue(tail1, head2, 0);

5204 int64_t new_available_cumul_head2 =

5205 std::max(cumuls_[dimension_index][head2], available_from_tail1);

5206

5207 const int64_t slack = new_available_cumul_head2 - available_from_tail1;

5208 if (slack > dimension.SlackVar(tail1)->Max()) {

5209 new_available_cumul_head2 =

5210 available_from_tail1 + dimension.SlackVar(tail1)->Max();

5211 }

5212

5213 bool feasible_route = true;

5214 if (new_available_cumul_head2 > dimension.CumulVar(head2)->Max()) {

5215 return false;

5216 }

5217 if (new_available_cumul_head2 <= cumuls_[dimension_index][head2]) {

5218 return true;

5219 }

5220

5221 feasible_route =

5222 FeasibleRoute(route2, new_available_cumul_head2, dimension_index);

5223 const int64_t new_possible_cumul_tail2 =

5224 new_possible_cumuls_[dimension_index].contains(tail2)

5225 ? new_possible_cumuls_[dimension_index][tail2]

5226 : cumuls_[dimension_index][tail2];

5227

5228 if (!feasible_route || (new_possible_cumul_tail2 +

5229 dimension.GetTransitValue(tail2, end_depot, 0) >

5230 depot_threshold)) {

5231 return false;

5232 }

5233 return true;

5234 }

5235

5236 bool FeasibleMerge(absl::Span<const int> route1,

5237 const std::vector<int>& route2, int node1, int node2,

5238 int route_index1, int route_index2, int vehicle_class,

5239 int64_t start_depot, int64_t end_depot) {

5240 if ((route_index1 == route_index2) || !(Tail(node1) && Head(node2))) {

5241 return false;

5242 }

5243

5244

5245 if (!((index_to_vehicle_class_index_[node1] == -1 &&

5246 index_to_vehicle_class_index_[node2] == -1) ||

5247 (index_to_vehicle_class_index_[node1] == vehicle_class &&

5248 index_to_vehicle_class_index_[node2] == -1) ||

5249 (index_to_vehicle_class_index_[node1] == -1 &&

5250 index_to_vehicle_class_index_[node2] == vehicle_class) ||

5251 (index_to_vehicle_class_index_[node1] == vehicle_class &&

5252 index_to_vehicle_class_index_[node2] == vehicle_class))) {

5253 return false;

5254 }

5255

5256

5257 bool merge = true;

5258 for (int dimension_index = 0; dimension_index < dimensions_.size();

5259 ++dimension_index) {

5260 new_possible_cumuls_[dimension_index].clear();

5261 merge = merge && CheckRouteConnection(route1, route2, dimension_index,

5262 start_depot, end_depot);

5263 if (!merge) {

5264 return false;

5265 }

5266 }

5267 return true;

5268 }

5269

5270 bool CheckTempAssignment(Assignment* const temp_assignment,

5271 int new_chain_index, int old_chain_index, int head1,

5272 int tail1, int head2, int tail2) {

5273

5274

5275 if (new_chain_index >= model_->vehicles()) return false;

5276 const int start = head1;

5277 temp_assignment->Add(model_->NextVar(model_->Start(new_chain_index)));

5278 temp_assignment->SetValue(model_->NextVar(model_->Start(new_chain_index)),

5279 start);

5280 temp_assignment->Add(nexts_[tail1]);

5281 temp_assignment->SetValue(nexts_[tail1], head2);

5282 temp_assignment->Add(nexts_[tail2]);

5283 temp_assignment->SetValue(nexts_[tail2], model_->End(new_chain_index));

5284 for (int chain_index = 0; chain_index < chains_.size(); ++chain_index) {

5285 if ((chain_index != new_chain_index) &&

5286 (chain_index != old_chain_index) &&

5287 (!deleted_chains_.contains(chain_index))) {

5288 const int start = chains_[chain_index].head;

5289 const int end = chains_[chain_index].tail;

5290 temp_assignment->Add(model_->NextVar(model_->Start(chain_index)));

5291 temp_assignment->SetValue(model_->NextVar(model_->Start(chain_index)),

5292 start);

5293 temp_assignment->Add(nexts_[end]);

5294 temp_assignment->SetValue(nexts_[end], model_->End(chain_index));

5295 }

5296 }

5297 return solver_->Solve(solver_->MakeRestoreAssignment(temp_assignment));

5298 }

5299

5300 bool UpdateAssignment(absl::Span<const int> route1,

5301 absl::Span<const int> route2) {

5302 bool feasible = true;

5303 const int head1 = route1.front();

5304 const int tail1 = route1.back();

5305 const int head2 = route2.front();

5306 const int tail2 = route2.back();

5307 const int chain_index1 = index_to_chain_index_[head1];

5308 const int chain_index2 = index_to_chain_index_[head2];

5309 if (chain_index1 < 0 && chain_index2 < 0) {

5310 const int chain_index = chains_.size();

5311 if (check_assignment_) {

5312 Assignment* const temp_assignment =

5313 solver_->MakeAssignment(assignment_);

5314 feasible = CheckTempAssignment(temp_assignment, chain_index, -1, head1,

5315 tail1, head2, tail2);

5316 }

5317 if (feasible) {

5318 Chain chain;

5319 chain.head = head1;

5320 chain.tail = tail2;

5321 chain.nodes = 2;

5322 index_to_chain_index_[head1] = chain_index;

5323 index_to_chain_index_[tail2] = chain_index;

5324 chains_.push_back(chain);

5325 }

5326 } else if (chain_index1 >= 0 && chain_index2 < 0) {

5327 if (check_assignment_) {

5328 Assignment* const temp_assignment =

5329 solver_->MakeAssignment(assignment_);

5330 feasible =

5331 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,

5332 head1, tail1, head2, tail2);

5333 }

5334 if (feasible) {

5335 index_to_chain_index_[tail2] = chain_index1;

5336 chains_[chain_index1].head = head1;

5337 chains_[chain_index1].tail = tail2;

5338 ++chains_[chain_index1].nodes;

5339 }

5340 } else if (chain_index1 < 0 && chain_index2 >= 0) {

5341 if (check_assignment_) {

5342 Assignment* const temp_assignment =

5343 solver_->MakeAssignment(assignment_);

5344 feasible =

5345 CheckTempAssignment(temp_assignment, chain_index2, chain_index1,

5346 head1, tail1, head2, tail2);

5347 }

5348 if (feasible) {

5349 index_to_chain_index_[head1] = chain_index2;

5350 chains_[chain_index2].head = head1;

5351 chains_[chain_index2].tail = tail2;

5352 ++chains_[chain_index2].nodes;

5353 }

5354 } else {

5355 if (check_assignment_) {

5356 Assignment* const temp_assignment =

5357 solver_->MakeAssignment(assignment_);

5358 feasible =

5359 CheckTempAssignment(temp_assignment, chain_index1, chain_index2,

5360 head1, tail1, head2, tail2);

5361 }

5362 if (feasible) {

5363 index_to_chain_index_[tail2] = chain_index1;

5364 chains_[chain_index1].head = head1;

5365 chains_[chain_index1].tail = tail2;

5366 chains_[chain_index1].nodes += chains_[chain_index2].nodes;

5367 deleted_chains_.insert(chain_index2);

5368 }

5369 }

5370 if (feasible) {

5371 assignment_->Add(nexts_[tail1]);

5372 assignment_->SetValue(nexts_[tail1], head2);

5373 }

5374 return feasible;

5375 }

5376

5377 bool Merge(bool merge, int index1, int index2) {

5378 if (merge) {

5379 if (UpdateAssignment(routes_[index1], routes_[index2])) {

5380

5381 for (const int node : routes_[index2]) {

5382 in_route_[node] = index1;

5383 routes_[index1].push_back(node);

5384 }

5385 for (int dimension_index = 0; dimension_index < dimensions_.size();

5386 ++dimension_index) {

5387 for (const std::pair<int, int64_t> new_possible_cumul :

5388 new_possible_cumuls_[dimension_index]) {

5389 cumuls_[dimension_index][new_possible_cumul.first] =

5390 new_possible_cumul.second;

5391 }

5392 }

5393 deleted_routes_.insert(index2);

5394 return true;

5395 }

5396 }

5397 return false;

5398 }

5399

5400 Assignment* const assignment_;

5401 RoutingModel* const model_;

5402 const bool check_assignment_;

5403 Solver* const solver_;

5404 const int64_t num_indices_;

5405 const std::vector<Link> links_list_;

5406 std::vector<IntVar*> nexts_;

5407 std::vector<const RoutingDimension*> dimensions_;

5408 std::vector<std::vector<int64_t>> cumuls_;

5409 std::vector<absl::flat_hash_map<int, int64_t>> new_possible_cumuls_;

5410 std::vector<std::vector<int>> routes_;

5411 std::vector<int> in_route_;

5412 absl::flat_hash_set<int> deleted_routes_;

5413 std::vector<std::vector<int>> final_routes_;

5414 std::vector<Chain> chains_;

5415 absl::flat_hash_set<int> deleted_chains_;

5416 std::vector<Chain> final_chains_;

5417 std::vector<int> index_to_chain_index_;

5418 std::vector<int> index_to_vehicle_class_index_;

5419};

5420

5421

5422

5423

5425 public:

5426 SweepBuilder(RoutingModel* const model, bool check_assignment)

5427 : model_(model), check_assignment_(check_assignment) {}

5428 ~SweepBuilder() override = default;

5429

5430 Decision* Next(Solver* const solver) override {

5431

5432 ModelSetup();

5433

5434

5435 Assignment* const assignment = solver->MakeAssignment();

5436 route_constructor_ = std::make_unique<RouteConstructor>(

5437 assignment, model_, check_assignment_, num_indices_, links_);

5438

5439 route_constructor_->Construct();

5440 route_constructor_.reset(nullptr);

5441

5442 assignment->Restore();

5443

5444 return nullptr;

5445 }

5446

5447 private:

5448 void ModelSetup() {

5449 const int depot = model_->GetDepot();

5450 num_indices_ = model_->Size() + model_->vehicles();

5451 if (absl::GetFlag(FLAGS_sweep_sectors) > 0 &&

5452 absl::GetFlag(FLAGS_sweep_sectors) < num_indices_) {

5453 model_->sweep_arranger()->SetSectors(absl::GetFlag(FLAGS_sweep_sectors));

5454 }

5455 std::vector<int64_t> indices;

5456 model_->sweep_arranger()->ArrangeIndices(&indices);

5457 for (int i = 0; i < indices.size() - 1; ++i) {

5458 const int64_t first = indices[i];

5459 const int64_t second = indices[i + 1];

5460 if ((model_->IsStart(first) || !model_->IsEnd(first)) &&

5461 (model_->IsStart(second) || !model_->IsEnd(second))) {

5462 if (first != depot && second != depot) {

5463 links_.push_back(

5464 Link(std::make_pair(first, second), 0, 0, depot, depot));

5465 }

5466 }

5467 }

5468 }

5469

5470 RoutingModel* const model_;

5471 std::unique_ptr<RouteConstructor> route_constructor_;

5472 const bool check_assignment_;

5473 int64_t num_indices_;

5474 std::vector<Link> links_;

5475};

5476}

5477

5482

5483

5484

5485namespace {

5486

5487

5488

5489class AllUnperformed : public DecisionBuilder {

5490 public:

5491

5492 explicit AllUnperformed(RoutingModel* const model) : model_(model) {}

5493 ~AllUnperformed() override = default;

5494 Decision* Next(Solver* const ) override {

5495

5496

5497 model_->CostVar()->FreezeQueue();

5498 for (int i = 0; i < model_->Size(); ++i) {

5499 if (!model_->IsStart(i)) {

5500 model_->ActiveVar(i)->SetValue(0);

5501 }

5502 }

5503 model_->CostVar()->UnfreezeQueue();

5504 return nullptr;

5505 }

5506

5507 private:

5508 RoutingModel* const model_;

5509};

5510}

5511

5515

5516namespace {

5517

5518class GuidedSlackFinalizer : public DecisionBuilder {

5519 public:

5520 GuidedSlackFinalizer(const RoutingDimension* dimension, RoutingModel* model,

5521 std::function<int64_t(int64_t)> initializer);

5522

5523

5524 GuidedSlackFinalizer(const GuidedSlackFinalizer&) = delete;

5525 GuidedSlackFinalizer& operator=(const GuidedSlackFinalizer&) = delete;

5526

5527 Decision* Next(Solver* solver) override;

5528

5529 private:

5530 int64_t SelectValue(int64_t index);

5531 int64_t ChooseVariable();

5532

5533 const RoutingDimension* const dimension_;

5534 RoutingModel* const model_;

5535 const std::function<int64_t(int64_t)> initializer_;

5536 RevArray<bool> is_initialized_;

5537 std::vector<int64_t> initial_values_;

5538 Rev<int64_t> current_index_;

5539 Rev<int64_t> current_route_;

5540 RevArray<int64_t> last_delta_used_;

5541};

5542

5543GuidedSlackFinalizer::GuidedSlackFinalizer(

5545 std::function<int64_t(int64_t)> initializer)

5546 : dimension_(ABSL_DIE_IF_NULL(dimension)),

5547 model_(ABSL_DIE_IF_NULL(model)),

5548 initializer_(std::move(initializer)),

5549 is_initialized_(dimension->slacks().size(), false),

5550 initial_values_(dimension->slacks().size(),

5551 std::numeric_limits<int64_t>::min()),

5552 current_index_(model_->Start(0)),

5553 current_route_(0),

5554 last_delta_used_(dimension->slacks().size(), 0) {}

5555

5556Decision* GuidedSlackFinalizer::Next(Solver* solver) {

5557 CHECK_EQ(solver, model_->solver());

5558 const int node_idx = ChooseVariable();

5559 CHECK(node_idx == -1 ||

5560 (node_idx >= 0 && node_idx < dimension_->slacks().size()));

5561 if (node_idx != -1) {

5562 if (!is_initialized_[node_idx]) {

5563 initial_values_[node_idx] = initializer_(node_idx);

5564 is_initialized_.SetValue(solver, node_idx, true);

5565 }

5566 const int64_t value = SelectValue(node_idx);

5567 IntVar* const slack_variable = dimension_->SlackVar(node_idx);

5568 return solver->MakeAssignVariableValue(slack_variable, value);

5569 }

5570 return nullptr;

5571}

5572

5573int64_t GuidedSlackFinalizer::SelectValue(int64_t index) {

5574 const IntVar* const slack_variable = dimension_->SlackVar(index);

5575 const int64_t center = initial_values_[index];

5576 const int64_t max_delta =

5577 std::max(center - slack_variable->Min(), slack_variable->Max() - center) +

5578 1;

5579 int64_t delta = last_delta_used_[index];

5580

5581

5582

5583 while (std::abs(delta) < max_delta &&

5584 !slack_variable->Contains(center + delta)) {

5585 if (delta > 0) {

5586 delta = -delta;

5587 } else {

5588 delta = -delta + 1;

5589 }

5590 }

5591 last_delta_used_.SetValue(model_->solver(), index, delta);

5592 return center + delta;

5593}

5594

5595int64_t GuidedSlackFinalizer::ChooseVariable() {

5596 int64_t int_current_node = current_index_.Value();

5597 int64_t int_current_route = current_route_.Value();

5598

5599 while (int_current_route < model_->vehicles()) {

5600 while (!model_->IsEnd(int_current_node) &&

5601 dimension_->SlackVar(int_current_node)->Bound()) {

5602 int_current_node = model_->NextVar(int_current_node)->Value();

5603 }

5604 if (!model_->IsEnd(int_current_node)) {

5605 break;

5606 }

5607 int_current_route += 1;

5608 if (int_current_route < model_->vehicles()) {

5609 int_current_node = model_->Start(int_current_route);

5610 }

5611 }

5612

5613 CHECK(int_current_route == model_->vehicles() ||

5614 !dimension_->SlackVar(int_current_node)->Bound());

5615 current_index_.SetValue(model_->solver(), int_current_node);

5616 current_route_.SetValue(model_->solver(), int_current_route);

5617 if (int_current_route < model_->vehicles()) {

5618 return int_current_node;

5619 } else {

5620 return -1;

5621 }

5622}

5623}

5624

5631

5680

5681namespace {

5683 public:

5684 explicit GreedyDescentLSOperator(std::vector<IntVar*> variables);

5685

5686

5687 GreedyDescentLSOperator(const GreedyDescentLSOperator&) = delete;

5688 GreedyDescentLSOperator& operator=(const GreedyDescentLSOperator&) = delete;

5689

5691 void Start(const Assignment* assignment) override;

5692

5693 private:

5694 int64_t FindMaxDistanceToDomain(const Assignment* assignment);

5695

5696 const std::vector<IntVar*> variables_;

5698 int64_t current_step_;

5699

5700

5701

5702

5703

5704

5705 int64_t current_direction_;

5706};

5707

5708GreedyDescentLSOperator::GreedyDescentLSOperator(std::vector<IntVar*> variables)

5709 : variables_(std::move(variables)),

5710 center_(nullptr),

5711 current_step_(0),

5712 current_direction_(0) {}

5713

5714bool GreedyDescentLSOperator::MakeNextNeighbor(Assignment* delta,

5716 static const int64_t sings[] = {1, -1};

5717 for (; 1 <= current_step_; current_step_ /= 2) {

5718 for (; current_direction_ < 2 * variables_.size();) {

5719 const int64_t variable_idx = current_direction_ / 2;

5720 IntVar* const variable = variables_[variable_idx];

5721 const int64_t sign_index = current_direction_ % 2;

5722 const int64_t sign = sings[sign_index];

5723 const int64_t offset = sign * current_step_;

5724 const int64_t new_value = center_->Value(variable) + offset;

5725 ++current_direction_;

5726 if (variable->Contains(new_value)) {

5727 delta->Add(variable);

5728 delta->SetValue(variable, new_value);

5729 return true;

5730 }

5731 }

5732 current_direction_ = 0;

5733 }

5734 return false;

5735}

5736

5737void GreedyDescentLSOperator::Start(const Assignment* assignment) {

5738 CHECK(assignment != nullptr);

5739 current_step_ = FindMaxDistanceToDomain(assignment);

5740 center_ = assignment;

5741}

5742

5743int64_t GreedyDescentLSOperator::FindMaxDistanceToDomain(

5744 const Assignment* assignment) {

5745 int64_t result = std::numeric_limits<int64_t>::min();

5746 for (const IntVar* const var : variables_) {

5747 result = std::max(result, std::abs(var->Max() - assignment->Value(var)));

5748 result = std::max(result, std::abs(var->Min() - assignment->Value(var)));

5749 }

5750 return result;

5751}

5752}

5753

5759

5788}