Home Original page

Google OR-Tools: ortools/constraint_solver/routing.h Source File

209 public:

211 const int num_indices = manager.num_indices();

212 const int num_paths = manager.num_vehicles();

213 path_of_node_.resize(num_indices, -1);

214 is_start_.resize(num_indices, false);

215 is_end_.resize(num_indices, false);

216 start_of_path_.resize(num_paths);

217 end_of_path_.resize(num_paths);

218 for (int v = 0; v < num_paths; ++v) {

220 start_of_path_[v] = start;

221 path_of_node_[start] = v;

222 is_start_[start] = true;

224 end_of_path_[v] = end;

225 path_of_node_[end] = v;

226 is_end_[end] = true;

227 }

228 }

229

230 bool IsStart(int64_t node) const { return is_start_[node]; }

231 bool IsEnd(int64_t node) const { return is_end_[node]; }

232 int GetPath(int64_t start_or_end_node) const {

233 return path_of_node_[start_or_end_node];

234 }

235 int NumPaths() const { return start_of_path_.size(); }

236 const std::vector<int64_t>& Paths() const { return path_of_node_; }

237 const std::vector<int64_t>& Starts() const { return start_of_path_; }

238 int64_t Start(int path) const { return start_of_path_[path]; }

239 int64_t End(int path) const { return end_of_path_[path]; }

240 const std::vector<int64_t>& Ends() const { return end_of_path_; }

241

242 private:

243 std::vector<bool> is_start_;

244 std::vector<bool> is_end_;

245 std::vector<int64_t> start_of_path_;

246 std::vector<int64_t> end_of_path_;

247 std::vector<int64_t> path_of_node_;

248};

259 public:

277

278#if !defined(SWIG)

297#endif

298

299#if !defined(SWIG)

303

318

326

327

338

344 template <typename H>

350 };

351 std::vector<DimensionCost>

353

356

362 template <typename H>

364 return H::combine(

365 std::move(h), c.evaluator_index,

366 c.dimension_transit_evaluator_class_and_cost_coefficient);

367 }

368 };

369#endif

370

384

386

387 int Type(int vehicle) const {

390 }

391

393

396

397 };

398

410 class ResourceGroup {

411 public:

414 public:

417

420

422 return a.start_domain_ == b.start_domain_ &&

423 a.end_domain_ == b.end_domain_;

424 }

425 template <typename H>

427 return H::combine(std::move(h), attributes.start_domain_,

428 attributes.end_domain_);

429 }

430

431 private:

435 Domain start_domain_;

438 };

439

441 class Resource {

442 public:

445 return index < dimension_attributes_per_index_.size()

446 ? attributes_[dimension_attributes_per_index_[index]]

447 : GetDefaultAttributes();

448 }

449

450 private:

453 SetDimensionAttributes(std::move(attributes), dimension);

454 }

455

459

460 absl::flat_hash_map<DimensionIndex, int> dimension_attributes_;

462 dimension_attributes_per_index_;

463 std::vector<ResourceGroup::Attributes> attributes_;

464

466 };

467

471

476

478 return vehicles_requiring_resource_;

479 }

480

482 return vehicle_requires_resource_[vehicle];

483 }

484

486 int vehicle, const std::vector<int>& allowed_resource_indices) {

487 DCHECK(!model_->closed_);

488

489

490

491 DCHECK(!allowed_resource_indices.empty());

492 DCHECK(vehicle_requires_resource_[vehicle]);

493 DCHECK_LT(vehicle, vehicle_allowed_resources_.size());

494 vehicle_allowed_resources_[vehicle].clear();

495 vehicle_allowed_resources_[vehicle].insert(

496 allowed_resource_indices.begin(), allowed_resource_indices.end());

497 }

499 DCHECK_LT(vehicle, vehicle_allowed_resources_.size());

500 vehicle_allowed_resources_[vehicle].clear();

501 }

503 int vehicle) const {

504 DCHECK_LT(vehicle, vehicle_allowed_resources_.size());

505 return vehicle_allowed_resources_[vehicle];

506 }

508 DCHECK_LT(vehicle, vehicle_allowed_resources_.size());

509 return vehicle_allowed_resources_[vehicle].empty() ||

510 vehicle_allowed_resources_[vehicle].contains(resource);

511 }

512

513 const std::vector<Resource>& GetResources() const { return resources_; }

515 DCHECK_LT(resource_index, resources_.size());

516 return resources_[resource_index];

517 }

519 const {

520 return affected_dimension_indices_;

521 }

522

524 return resource_indices_per_class_.size();

525 }

528 DCHECK_LT(resource_class, resource_indices_per_class_.size());

529 return resource_indices_per_class_[resource_class];

530 }

531

534 return resource_indices_per_class_;

535 }

536

538 DCHECK_LT(resource_index, resource_class_indices_.size());

539 return resource_class_indices_[resource_index];

540 }

543 DCHECK_LT(rc_index, resource_indices_per_class_.size());

544 const std::vector<int>& resource_indices =

545 resource_indices_per_class_[rc_index];

546 DCHECK(!resource_indices.empty());

547 return resources_[resource_indices[0]].GetDimensionAttributes(

548 dimension_index);

549 }

550

551 int Size() const { return resources_.size(); }

552 int Index() const { return index_; }

553

554 private:

557 model_(model),

558 vehicle_requires_resource_(model->vehicles(), false),

559 vehicle_allowed_resources_(model->vehicles()) {}

560

561 void ComputeResourceClasses();

562

563 const int index_;

565 std::vector<Resource> resources_;

566

567

568 std::vector<ResourceClassIndex> resource_class_indices_;

569

571 resource_indices_per_class_;

572

573

574 std::vector<bool> vehicle_requires_resource_;

575 std::vector<int> vehicles_requiring_resource_;

576

577

578

579

580 std::vector<absl::flat_hash_set<int> > vehicle_allowed_resources_;

581

583 absl::flat_hash_set<DimensionIndex> affected_dimension_indices_;

584

586 };

587

593

596 public:

599 int64_t solve_period);

600 bool Solve(const std::vector<RoutingModel::VariableValuePair>& in_state,

601 std::vector<RoutingModel::VariableValuePair>* out_state);

602

603 private:

606 const int64_t solve_period_ = 0;

607 int64_t call_count_ = 0;

609 absl::flat_hash_map<operations_research::IntVar*, int> var_to_index_;

610 };

611

614

618

622

629

630

633

635

642

647 int RegisterUnaryTransitVector(std::vector<int64_t> values);

648 int RegisterUnaryTransitCallback(

649 TransitCallback1 callback,

650 TransitEvaluatorSign sign = kTransitEvaluatorSignUnknown);

651

652 int RegisterTransitMatrix(

653 std::vector<std::vector<int64_t> > values);

654 int RegisterTransitCallback(

655 TransitCallback2 callback,

656 TransitEvaluatorSign sign = kTransitEvaluatorSignUnknown);

657 int RegisterCumulDependentTransitCallback(

658 CumulDependentTransitCallback2 callback);

659 int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback);

660

662 CHECK_LT(callback_index, transit_evaluators_.size());

663 return transit_evaluators_[callback_index];

664 }

666 CHECK_LT(callback_index, unary_transit_evaluators_.size());

667 return unary_transit_evaluators_[callback_index];

668 }

670 int callback_index) const {

671 CHECK_LT(callback_index, cumul_dependent_transit_evaluators_.size());

672 return cumul_dependent_transit_evaluators_[callback_index];

673 }

675 int callback_index) const {

676 CHECK_LT(callback_index, state_dependent_transit_evaluators_.size());

677 return state_dependent_transit_evaluators_[callback_index];

678 }

679

681

693

702 bool AddDimension(int evaluator_index, int64_t slack_max, int64_t capacity,

703 bool fix_start_cumul_to_zero, const std::string& name);

704 bool AddDimensionWithVehicleTransits(

705 const std::vector<int>& evaluator_indices, int64_t slack_max,

706 int64_t capacity, bool fix_start_cumul_to_zero, const std::string& name);

707 bool AddDimensionWithVehicleCapacity(int evaluator_index, int64_t slack_max,

708 std::vector<int64_t> vehicle_capacities,

709 bool fix_start_cumul_to_zero,

710 const std::string& name);

711 bool AddDimensionWithVehicleTransitAndCapacity(

712 const std::vector<int>& evaluator_indices, int64_t slack_max,

713 std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,

714 const std::string& name);

721 bool AddDimensionWithCumulDependentVehicleTransitAndCapacity(

722 const std::vector<int>& fixed_evaluator_indices,

723 const std::vector<int>& cumul_dependent_evaluator_indices,

724 int64_t slack_max, std::vector<int64_t> vehicle_capacities,

725 bool fix_start_cumul_to_zero, const std::string& name);

726

735 std::pair<int, bool> AddConstantDimensionWithSlack(

736 int64_t value, int64_t capacity, int64_t slack_max,

737 bool fix_start_cumul_to_zero, const std::string& name);

739 bool fix_start_cumul_to_zero,

740 const std::string& name) {

742 fix_start_cumul_to_zero, name);

743 }

744

753 std::pair<int, bool> AddVectorDimension(std::vector<int64_t> values,

754 int64_t capacity,

755 bool fix_start_cumul_to_zero,

756 const std::string& name);

766 std::pair<int, bool> AddMatrixDimension(

767 std::vector<std::vector<int64_t> > values,

768 int64_t capacity, bool fix_start_cumul_to_zero, const std::string& name);

776 const std::vector<int>& pure_transits,

777 const std::vector<int>& dependent_transits,

779 std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,

780 const std::string& name) {

781 return AddDimensionDependentDimensionWithVehicleCapacityInternal(

782 pure_transits, dependent_transits, base_dimension, slack_max,

783 std::move(vehicle_capacities), fix_start_cumul_to_zero, name);

784 }

785

787 bool AddDimensionDependentDimensionWithVehicleCapacity(

788 const std::vector<int>& transits, const RoutingDimension* base_dimension,

789 int64_t slack_max, std::vector<int64_t> vehicle_capacities,

790 bool fix_start_cumul_to_zero, const std::string& name);

792 bool AddDimensionDependentDimensionWithVehicleCapacity(

793 int transit, const RoutingDimension* base_dimension, int64_t slack_max,

794 int64_t vehicle_capacity, bool fix_start_cumul_to_zero,

795 const std::string& name);

796 bool AddDimensionDependentDimensionWithVehicleCapacity(

797 int pure_transit, int dependent_transit,

799 int64_t vehicle_capacity, bool fix_start_cumul_to_zero,

800 const std::string& name);

801

804 const std::function<int64_t(int64_t)>& f, int64_t domain_start,

805 int64_t domain_end);

806

808

809 std::vector<std::string> GetAllDimensionNames() const;

811 const std::vector<RoutingDimension*>& GetDimensions() const {

812 return dimensions_.get();

813 }

814

815 std::vector<RoutingDimension*> GetDimensionsWithSoftOrSpanCosts() const;

817 std::vector<RoutingDimension*> GetUnaryDimensions() const;

818

820 std::vector<const RoutingDimension*> GetDimensionsWithGlobalCumulOptimizers()

821 const;

822 std::vector<const RoutingDimension*> GetDimensionsWithLocalCumulOptimizers()

823 const;

824

827 return GetGlobalCumulOptimizerIndex(dimension) >= 0;

828 }

830 return GetLocalCumulOptimizerIndex(dimension) >= 0;

831 }

832

842

844 bool HasDimension(absl::string_view dimension_name) const;

847 const std::string& dimension_name) const;

851 const std::string& dimension_name) const;

857 DCHECK(dimension_name.empty() || HasDimension(dimension_name));

858 primary_constrained_dimension_ = dimension_name;

859 }

860

862 return primary_constrained_dimension_;

863 }

864

866 ResourceGroup* AddResourceGroup();

867

869 const {

870 return resource_groups_;

871 }

872

874 DCHECK_LT(rg_index, resource_groups_.size());

875 return resource_groups_[rg_index].get();

876 }

877

880 const std::vector<int>& GetDimensionResourceGroupIndices(

882

889

893

916 DisjunctionIndex AddDisjunction(const std::vector<int64_t>& indices,

917 int64_t penalty = kNoPenalty,

918 int64_t max_cardinality = 1,

919 PenaltyCostBehavior penalty_cost_behavior =

920 PenaltyCostBehavior::PENALIZE_ONCE);

922 const std::vector<DisjunctionIndex>& GetDisjunctionIndices(

923 int64_t index) const {

924 return index_to_disjunctions_[index];

925 }

927

929 template <typename F>

930 void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(

931 int64_t index, int64_t max_cardinality, F f) const {

933 if (disjunctions_[disjunction].value.max_cardinality == max_cardinality) {

934 for (const int64_t d_index : disjunctions_[disjunction].indices) {

935 f(d_index);

936 }

937 }

938 }

939 }

940#if !defined(SWIGPYTHON)

941

943 const std::vector<int64_t>& GetDisjunctionNodeIndices(

945 return disjunctions_[index].indices;

946 }

947#endif

948

949 int64_t GetDisjunctionPenalty(DisjunctionIndex index) const {

950 return disjunctions_[index].value.penalty;

951 }

953

954 int64_t GetDisjunctionMaxCardinality(DisjunctionIndex index) const {

955 return disjunctions_[index].value.max_cardinality;

956 }

958

959 PenaltyCostBehavior GetDisjunctionPenaltyCostBehavior(

961 return disjunctions_[index].value.penalty_cost_behavior;

962 }

964 int GetNumberOfDisjunctions() const { return disjunctions_.size(); }

982

991 return same_vehicle_costs_.size();

992 }

994

995 const std::vector<int64_t>& GetSoftSameVehicleIndices(int index) const {

996 return same_vehicle_costs_[index].indices;

997 }

999 int64_t GetSoftSameVehicleCost(int index) const {

1000 return same_vehicle_costs_[index].value;

1001 }

1002

1003

1007 void SetAllowedVehiclesForIndex(absl::Span<const int> vehicles,

1008 int64_t index);

1009

1011 bool IsVehicleAllowedForIndex(int vehicle, int64_t index) const {

1012 return allowed_vehicles_[index].empty() ||

1013 allowed_vehicles_[index].contains(vehicle);

1014 }

1015

1016

1030

1031 void AddPickupAndDelivery(int64_t pickup, int64_t delivery);

1035 void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction,

1036 DisjunctionIndex delivery_disjunction);

1037

1039 struct PickupDeliveryPosition {

1048 int64_t node_index) const;

1051 int64_t node_index) const;

1053 bool IsPickup(int64_t node_index) const {

1054 return index_to_pickup_position_[node_index].pd_pair_index != -1;

1056 bool IsDelivery(int64_t node_index) const {

1057 return index_to_delivery_position_[node_index].pd_pair_index != -1;

1061

1062 void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy);

1063 void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy,

1064 int vehicle);

1065 PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(

1066 int vehicle) const;

1069

1070 int GetNumOfSingletonNodes() const;

1071

1072#ifndef SWIG

1074 const std::vector<PickupDeliveryPair>& GetPickupAndDeliveryPairs() const {

1075 return pickup_delivery_pairs_;

1077 const std::vector<std::pair<DisjunctionIndex, DisjunctionIndex>>&

1078 GetPickupAndDeliveryDisjunctions() const {

1079 return pickup_delivery_disjunctions_;

1083

1085 const std::vector<PickupDeliveryPair>&

1086 GetImplicitUniquePickupAndDeliveryPairs() const {

1087 DCHECK(closed_);

1088 return implicit_pickup_delivery_pairs_without_alternatives_;

1089 }

1090#endif

1091

1092

1093

1094 std::optional<int64_t> GetFirstMatchingPickupDeliverySibling(

1095 int64_t node, const std::function<bool(int64_t)>& is_match) const;

1096

1106 enum VisitTypePolicy {

1108 TYPE_ADDED_TO_VEHICLE,

1110

1111

1112

1122 };

1123

1124 void SetVisitType(int64_t index, int type, VisitTypePolicy type_policy);

1129#ifndef SWIG

1131 return visit_type_components_;

1132 }

1133#endif

1135#ifndef SWIG

1136 const std::vector<std::vector<int>>& GetTopologicallySortedVisitTypes()

1137 const {

1138 DCHECK(closed_);

1139 return topologically_sorted_visit_types_;

1141 const std::vector<std::vector<std::vector<int>>>&

1142 GetTopologicallySortedNodePrecedences() const {

1143 DCHECK(closed_);

1144 return topologically_sorted_node_precedences_;

1145 }

1150

1154 void AddHardTypeIncompatibility(int type1, int type2);

1158 int type) const;

1160 int type) const;

1164 return !hard_incompatible_types_per_type_index_.empty();

1165 }

1166 bool HasTemporalTypeIncompatibilities() const {

1167 return !temporal_incompatible_types_per_type_index_.empty();

1168 }

1170

1173

1174

1175

1176

1177

1178

1179

1180

1181

1183 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);

1189 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);

1196 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);

1197

1200 const std::vector<absl::flat_hash_set<int> >&

1203 const std::vector<absl::flat_hash_set<int> >&

1206 const std::vector<absl::flat_hash_set<int> >&

1208

1212 return !same_vehicle_required_type_alternatives_per_type_index_.empty();

1213 }

1214 bool HasTemporalTypeRequirements() const {

1215 return !required_type_alternatives_when_adding_type_index_.empty() ||

1216 !required_type_alternatives_when_removing_type_index_.empty();

1217 }

1218

1219

1225 }

1236 int64_t var_index) const;

1241

1247 max_active_vehicles_ = max_active_vehicles;

1248 }

1250 int GetMaximumNumberOfActiveVehicles() const { return max_active_vehicles_; }

1266

1267

1268

1269

1270

1271

1272

1274 const std::string& distance,

1275 int64_t cost_per_unit, int vehicle);

1276

1277

1278

1279

1280

1281

1283 const std::string& distance,

1284 int64_t threshold,

1285 int64_t cost_per_unit_below_threshold,

1286 int64_t cost_per_unit_above_threshold,

1287 int vehicle);

1288

1305 int64_t quadratic_cost_factor);

1308 int64_t quadratic_cost_factor,

1309 int vehicle);

1310

1312 return linear_cost_factor_of_vehicle_;

1313 }

1314 const std::vector<int64_t>& GetAmortizedQuadraticCostFactorOfVehicles()

1315 const {

1316 return quadratic_cost_factor_of_vehicle_;

1317 }

1321

1322

1323#ifndef SWIG

1325 absl::AnyInvocable<std::optional<int64_t>(const std::vector<int64_t>&)>

1326 route_evaluator,

1327 bool costs_are_homogeneous_across_vehicles = false);

1328#endif

1329 std::optional<int64_t> GetRouteCost(const std::vector<int64_t>& route) const {

1330 int64_t route_cost = 0;

1331 for (auto& evaluator : route_evaluators_) {

1332 std::optional<int64_t> cost = evaluator(route);

1333 if (!cost.has_value()) return std::nullopt;

1334 CapAddTo(cost.value(), &route_cost);

1335 }

1336 return route_cost;

1337 }

1338

1339 void SetVehicleUsedWhenEmpty(bool is_used, int vehicle) {

1340 DCHECK_LT(vehicle, vehicles_);

1341 vehicle_used_when_empty_[vehicle] = is_used;

1342 }

1343

1344 bool IsVehicleUsedWhenEmpty(int vehicle) const {

1345 DCHECK_LT(vehicle, vehicles_);

1346 return vehicle_used_when_empty_[vehicle];

1347 }

1348

1350

1353 return first_solution_evaluator_;

1354 }

1355#endif

1358 first_solution_evaluator_ = std::move(evaluator);

1362

1365 hint_ = hint;

1366 }

1367

1369 return hint_;

1370 }

1374

1378

1385 bool track_unchecked_neighbors = false);

1386

1387

1400 int64_t cost);

1404 int64_t cost);

1408 int64_t target);

1412 int64_t target, int64_t cost);

1441 std::vector<const operations_research::Assignment*>* solutions = nullptr);

1447 std::vector<const operations_research::Assignment*>* solutions = nullptr);

1455 bool check_solution_in_cp,

1456 absl::flat_hash_set<operations_research::IntVar*>* touched = nullptr);

1460 const std::vector<const operations_research::Assignment*>& assignments,

1462 std::vector<const operations_research::Assignment*>* solutions = nullptr);

1483

1491 const RoutingSearchStats& search_stats() const { return search_stats_; }

1493 bool enable_deep_serialization() const { return enable_deep_serialization_; }

1512 bool close_routes);

1518 return preassignment_;

1519 }

1521 return preassignment_;

1522 }

1528

1531

1541 const std::vector<std::vector<int64_t>>& routes,

1542 bool ignore_inactive_indices);

1559 bool RoutesToAssignment(const std::vector<std::vector<int64_t>>& routes,

1560 bool ignore_inactive_indices, bool close_routes,

1566 std::vector<std::vector<int64_t>>* routes) const;

1571#ifndef SWIG

1574#endif

1615 absl::Duration duration_limit, bool* time_limit_was_reached = nullptr);

1616

1617#ifndef SWIG

1622 struct TransitionInfo {

1626

1628

1629

1631

1637

1641

1647

1648 std::string DebugString(std::string line_prefix = "") const;

1649 };

1650

1656

1657 std::string DebugString(std::string line_prefix = "") const;

1658 };

1659

1660#endif

1662#ifndef SWIG

1663

1667#endif

1669 int num_neighbors;

1670 bool add_vehicle_starts_to_neighbors = true;

1671 bool add_vehicle_ends_to_neighbors = false;

1672

1673

1674

1675

1676

1688 template <typename H>

1690 return H::combine(std::move(h), params.num_neighbors,

1694 }

1695 };

1696 class NodeNeighborsByCostClass {

1699 : routing_model_(*routing_model) {};

1700

1704

1704

1705

1708 int cost_class, int node_index) const {

1709 if (routing_model_.IsStart(node_index)) return empty_neighbors_;

1710

1711 if (node_index_to_incoming_neighbors_by_cost_class_.empty()) {

1713 return all_incoming_nodes_;

1714 }

1715 const std::vector<std::vector<int>>& node_index_to_incoming_neighbors =

1716 node_index_to_incoming_neighbors_by_cost_class_[cost_class];

1717 if (node_index_to_incoming_neighbors.empty()) {

1718 return empty_neighbors_;

1719 }

1720 return node_index_to_incoming_neighbors[node_index];

1721 }

1722

1726 const std::vector<int>& GetOutgoingNeighborsOfNodeForCostClass(

1727 int cost_class, int node_index) const {

1728 if (routing_model_.IsEnd(node_index)) return empty_neighbors_;

1729

1730 if (node_index_to_outgoing_neighbors_by_cost_class_.empty()) {

1731 DCHECK(IsFullNeighborhood());

1732 return all_outgoing_nodes_;

1733 }

1734 const std::vector<std::vector<int>>& node_index_to_outgoing_neighbors =

1735 node_index_to_outgoing_neighbors_by_cost_class_[cost_class];

1736 if (node_index_to_outgoing_neighbors.empty()) {

1737 return empty_neighbors_;

1738 }

1739 return node_index_to_outgoing_neighbors[node_index];

1740 }

1744 bool IsNeighborhoodArcForCostClass(int cost_class, int64_t from,

1745 int64_t to) const {

1746 if (node_index_to_outgoing_neighbor_indicator_by_cost_class_.empty()) {

1747 DCHECK(full_neighborhood_);

1748 return true;

1749 }

1750 if (routing_model_.IsEnd(from)) {

1751 return false;

1753 return node_index_to_outgoing_neighbor_indicator_by_cost_class_

1754 [cost_class][from][to];

1755 }

1756

1757 bool IsFullNeighborhood() const { return full_neighborhood_; }

1758

1759 private:

1760 const RoutingModel& routing_model_;

1761#if __cplusplus >= 202002L

1762 static constexpr std::vector<int> empty_neighbors_ = {};

1763#else

1764 inline static const std::vector<int> empty_neighbors_ = {};

1766

1767 std::vector<std::vector<std::vector<int>>>

1768 node_index_to_incoming_neighbors_by_cost_class_;

1769 std::vector<std::vector<std::vector<int>>>

1770 node_index_to_outgoing_neighbors_by_cost_class_;

1771 std::vector<std::vector<std::vector<bool>>>

1772 node_index_to_outgoing_neighbor_indicator_by_cost_class_;

1773

1774 std::vector<int> all_outgoing_nodes_;

1775 std::vector<int> all_incoming_nodes_;

1776

1777 bool full_neighborhood_ = false;

1778 };

1779

1785 double neighbors_ratio, int64_t min_neighbors,

1786 double& neighbors_ratio_used, bool add_vehicle_starts_to_neighbors = true,

1787 bool add_vehicle_ends_to_neighbors = false,

1788 bool only_sort_neighbors_for_partial_neighborhoods = true);

1799 CHECK(filter != nullptr);

1800 if (closed_) {

1801 LOG(WARNING) << "Model is closed, filter addition will be ignored.";

1802 }

1805 }

1809 int64_t Start(int vehicle) const { return paths_metadata_.Starts()[vehicle]; }

1811 int64_t End(int vehicle) const { return paths_metadata_.Ends()[vehicle]; }

1813 bool IsStart(int64_t index) const { return paths_metadata_.IsStart(index); }

1814

1815 bool IsEnd(int64_t index) const { return paths_metadata_.IsEnd(index); }

1819 return paths_metadata_.GetPath(index);

1820 }

1825 int64_t index) const;

1826

1828 int vehicle) const;

1829

1830#if !defined(SWIGPYTHON)

1833 const std::vector<operations_research::IntVar*>& Nexts() const {

1834 return nexts_;

1835 }

1838 const std::vector<operations_research::IntVar*>& VehicleVars() const {

1839 return vehicle_vars_;

1840 }

1844 const std::vector<operations_research::IntVar*>& ResourceVars(

1845 int resource_group) const {

1846 return resource_vars_[resource_group];

1847 }

1848#endif

1849

1852 return nexts_[index];

1853 }

1856 return active_[index];

1857 }

1859

1861 return vehicle_active_[vehicle];

1862 }

1867 return vehicle_route_considered_[vehicle];

1872 return vehicle_vars_[index];

1873 }

1878 int resource_group) const {

1879 DCHECK_LT(resource_group, resource_vars_.size());

1880 DCHECK_LT(vehicle, resource_vars_[resource_group].size());

1881 return resource_vars_[resource_group][vehicle];

1882 }

1889 int64_t vehicle) const;

1892 return costs_are_homogeneous_across_vehicles_;

1893 }

1896 int64_t GetHomogeneousCost(int64_t from_index, int64_t to_index) const {

1897 return GetArcCostForVehicle(from_index, to_index, 0);

1898 }

1902 int64_t to_index) const;

1907

1908

1910 int64_t cost_class_index) const;

1913 DCHECK(closed_);

1914 DCHECK_GE(vehicle, 0);

1915 DCHECK_LT(vehicle, cost_class_index_of_vehicle_.size());

1916 DCHECK_GE(cost_class_index_of_vehicle_[vehicle], 0);

1917 return cost_class_index_of_vehicle_[vehicle];

1918 }

1920

1922 DCHECK(closed_);

1923 if (cost_class_index == kCostClassIndexOfZeroCost) {

1924 return has_vehicle_with_zero_cost_class_;

1925 }

1926 return cost_class_index < cost_classes_.size();

1927 }

1931 int GetNonZeroCostClassesCount() const {

1932 return std::max(0, GetCostClassesCount() - 1);

1933 }

1934 VehicleClassIndex GetVehicleClassIndexOfVehicle(int64_t vehicle) const {

1935 DCHECK(closed_);

1936 return vehicle_class_index_of_vehicle_[vehicle];

1939

1941 DCHECK(closed_);

1946 .empty()) {

1947 return -1;

1949 return vehicle_type_container

1951 .front();

1952 }

1954 int GetVehicleClassesCount() const { return num_vehicle_classes_; }

1956 const std::vector<int>& GetSameVehicleIndicesOfIndex(int node) const {

1957 DCHECK(closed_);

1958 return same_vehicle_groups_[same_vehicle_group_[node]];

1959 }

1960 void AddSameActivityGroup(absl::Span<const int> nodes) {

1961 DCHECK(!closed_);

1963 for (auto it = nodes.begin() + 1; it != nodes.end(); ++it) {

1964 solver_->AddConstraint(

1966 }

1967 }

1968

1968

1970 DCHECK(closed_);

1971 return same_active_var_groups_[same_active_var_group_[node]];

1972 }

1974 int GetSameActivityGroupOfIndex(int node) const {

1975 DCHECK(closed_);

1976 return same_active_var_group_[node];

1979 const std::vector<int>& GetSameActivityGroups() const {

1980 DCHECK(closed_);

1981 return same_active_var_group_;

1984 int GetSameActivityGroupsCount() const {

1985 DCHECK(closed_);

1986 return same_active_var_groups_.size();

1989 const std::vector<int>& GetSameActivityIndicesOfGroup(int group) const {

1990 DCHECK(closed_);

1991 return same_active_var_groups_[group];

1996 void AddOrderedActivityGroup(std::vector<DisjunctionIndex> disjunctions) {

1997 DCHECK(!closed_);

1998 if (disjunctions.size() <= 1) return;

1999 ordered_activity_groups_.push_back(std::move(disjunctions));

2000 }

2001

2002 const std::vector<std::vector<DisjunctionIndex>>& GetOrderedActivityGroups()

2003 const {

2004 return ordered_activity_groups_;

2005 }

2006#endif

2007 const VehicleTypeContainer& GetVehicleTypeContainer() const {

2008 DCHECK(closed_);

2009 return vehicle_type_container_;

2014

2019

2020

2021

2022

2023

2024

2025

2026

2027

2028

2029

2037 const std::string& dimension_to_print) const;

2043#ifndef SWIG

2044 std::vector<std::vector<std::pair<int64_t, int64_t>>> GetCumulBounds(

2047#endif

2051 bool call_at_solution_monitors);

2054 Solver* solver() const { return solver_.get(); }

2055

2058 bool CheckLimit(absl::Duration offset = absl::ZeroDuration()) {

2059 DCHECK(limit_ != nullptr);

2060 return limit_->CheckWithOffset(offset);

2061 }

2065 DCHECK(limit_ != nullptr);

2066 return limit_->AbsoluteSolverDeadline() - solver_->Now();

2067 }

2068

2070 void UpdateTimeLimit(absl::Duration time_limit) {

2072 limit->UpdateLimits(time_limit, std::numeric_limits<int64_t>::max(),

2073 std::numeric_limits<int64_t>::max(),

2075 }

2076

2078 absl::Duration TimeBuffer() const { return time_buffer_; }

2079

2081 std::atomic<bool>* GetMutableCPSatInterrupt() { return &interrupt_cp_sat_; }

2083 std::atomic<bool>* GetMutableCPInterrupt() { return &interrupt_cp_; }

2084

2085 void CancelSearch() {

2086 interrupt_cp_sat_ = true;

2087 interrupt_cp_ = true;

2088 }

2092 int nodes() const { return nodes_; }

2093

2094 int vehicles() const { return vehicles_; }

2096 int64_t Size() const { return nodes_ + vehicles_ - start_end_count_; }

2097

2107 return automatic_first_solution_strategy_;

2108 }

2109

2111 bool IsMatchingModel() const;

2112

2117#ifndef SWIG

2121 std::function<std::vector<operations_research::IntVar*>(RoutingModel*)>;

2122

2124#endif

2125

2127

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

2142#ifndef SWIG

2143

2149 std::vector<operations_research::IntVar*> variables);

2150

2152 return monitors_;

2153 }

2154#endif

2163

2164

2165

2166

2167

2170

2172#ifndef SWIG

2173 BinCapacities* GetBinCapacities() { return bin_capacities_.get(); }

2174

2177 void SetSecondaryModel(RoutingModel* secondary_model,

2178 RoutingSearchParameters secondary_parameters) {

2179 DCHECK(!closed_);

2180 secondary_model_ = secondary_model;

2181 secondary_parameters_ = std::move(secondary_parameters);

2183#endif

2184

2192

2195 int64_t from_index, int64_t to_index) const;

2196

2197 private:

2199 enum RoutingLocalSearchOperator {

2200 RELOCATE = 0,

2201 RELOCATE_PAIR,

2202 LIGHT_RELOCATE_PAIR,

2203 RELOCATE_NEIGHBORS,

2204 EXCHANGE,

2205 EXCHANGE_PAIR,

2206 CROSS,

2207 CROSS_EXCHANGE,

2208 TWO_OPT,

2209 OR_OPT,

2210 GLOBAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS,

2211 LOCAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS,

2212 GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,

2213 LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,

2214 GLOBAL_CHEAPEST_INSERTION_PATH_LNS,

2215 LOCAL_CHEAPEST_INSERTION_PATH_LNS,

2216 RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,

2217 GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,

2218 LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,

2219 RELOCATE_EXPENSIVE_CHAIN,

2220 LIN_KERNIGHAN,

2221 TSP_OPT,

2222 MAKE_ACTIVE,

2223 RELOCATE_AND_MAKE_ACTIVE,

2224 MAKE_ACTIVE_AND_RELOCATE,

2225 EXCHANGE_AND_MAKE_ACTIVE,

2226 EXCHANGE_PATH_START_ENDS_AND_MAKE_ACTIVE,

2227 MAKE_INACTIVE,

2228 MAKE_CHAIN_INACTIVE,

2229 SWAP_ACTIVE,

2230 SWAP_ACTIVE_CHAIN,

2231 EXTENDED_SWAP_ACTIVE,

2232 SHORTEST_PATH_SWAP_ACTIVE,

2233 SHORTEST_PATH_TWO_OPT,

2234 NODE_PAIR_SWAP,

2235 PATH_LNS,

2236 FULL_PATH_LNS,

2237 TSP_LNS,

2238 INACTIVE_LNS,

2239 EXCHANGE_RELOCATE_PAIR,

2240 RELOCATE_SUBTRIP,

2241 EXCHANGE_SUBTRIP,

2242 LOCAL_SEARCH_OPERATOR_COUNTER

2243 };

2244

2248 template <typename T>

2249 struct ValuedNodes {

2250 std::vector<int64_t> indices;

2251 T value;

2252 };

2253 struct DisjunctionValues {

2254 int64_t penalty;

2255 int64_t max_cardinality;

2256 PenaltyCostBehavior penalty_cost_behavior;

2257 };

2258 typedef ValuedNodes<DisjunctionValues> Disjunction;

2259

2262 struct CostCacheElement {

2268 int index;

2269 CostClassIndex cost_class_index;

2270 int64_t cost;

2271 };

2272

2275 template <class DimensionCumulOptimizer>

2276 struct DimensionCumulOptimizers {

2277 std::unique_ptr<DimensionCumulOptimizer> lp_optimizer;

2278 std::unique_ptr<DimensionCumulOptimizer> mp_optimizer;

2279 };

2280

2282 void Initialize();

2283 void AddNoCycleConstraintInternal();

2284 bool AddDimensionWithCapacityInternal(

2285 const std::vector<int>& evaluator_indices,

2286 const std::vector<int>& cumul_dependent_evaluator_indices,

2287 int64_t slack_max, std::vector<int64_t> vehicle_capacities,

2288 bool fix_start_cumul_to_zero, const std::string& name);

2289 bool AddDimensionDependentDimensionWithVehicleCapacityInternal(

2290 const std::vector<int>& pure_transits,

2291 const std::vector<int>& dependent_transits,

2293 std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,

2294 const std::string& name);

2295 bool InitializeDimensionInternal(

2296 const std::vector<int>& evaluator_indices,

2297 const std::vector<int>& cumul_dependent_evaluator_indices,

2298 const std::vector<int>& state_dependent_evaluator_indices,

2299 int64_t slack_max, bool fix_start_cumul_to_zero,

2301 DimensionIndex GetDimensionIndex(absl::string_view dimension_name) const;

2302

2331

2337 void FinalizeAllowedVehicles();

2338

2340 void ComputeVehicleClasses();

2348 void ComputeVehicleTypes();

2350 void ComputeResourceClasses();

2360 void FinalizeVisitTypes();

2361 void ComputeVisitTypesConnectedComponents();

2362

2363 void TopologicallySortVisitTypes();

2364

2365

2366

2367 void FinalizePrecedences();

2368 int64_t GetArcCostForClassInternal(int64_t from_index, int64_t to_index,

2369 CostClassIndex cost_class_index) const;

2370 int64_t GetArcCostWithGuidedLocalSearchPenalties(int64_t from_index,

2371 int64_t to_index,

2372 int64_t vehicle) const {

2374 GetArcCostForVehicle(from_index, to_index, vehicle),

2375 solver()->GetGuidedLocalSearchPenalty(from_index, to_index, vehicle));

2376 }

2377 std::function<int64_t(int64_t, int64_t, int64_t)>

2378 GetLocalSearchArcCostCallback(

2380 int64_t GetHomogeneousArcCostWithGuidedLocalSearchPenalties(

2381 int64_t from_index, int64_t to_index) const {

2382 return GetArcCostWithGuidedLocalSearchPenalties(from_index, to_index,

2383 0);

2384 }

2385 std::function<int64_t(int64_t, int64_t)>

2386 GetLocalSearchHomogeneousArcCostCallback(

2388 void AppendHomogeneousArcCosts(

2390 std::vector<operations_research::IntVar*>* cost_elements);

2392 std::vector<operations_research::IntVar*>* cost_elements);

2393 operations_research::Assignment* DoRestoreAssignment();

2394 static const CostClassIndex kCostClassIndexOfZeroCost;

2395 int64_t SafeGetCostClassInt64OfVehicle(int64_t vehicle) const {

2396 DCHECK_LT(0, vehicles_);

2397 return (vehicle >= 0 ? GetCostClassIndexOfVehicle(vehicle)

2398 : kCostClassIndexOfZeroCost)

2399 .value();

2400 }

2401 int64_t GetDimensionTransitCostSum(int64_t i, int64_t j,

2402 const CostClass& cost_class) const;

2404 operations_research::IntVar* CreateDisjunction(DisjunctionIndex disjunction);

2406 void AddPickupAndDeliverySetsInternal(const std::vector<int64_t>& pickups,

2407 const std::vector<int64_t>& deliveries);

2410 operations_research::IntVar* CreateSameVehicleCost(int vehicle_index);

2413 int FindNextActive(int index, absl::Span<const int64_t> indices) const;

2414

2417 bool RouteCanBeUsedByVehicle(

2418 const operations_research::Assignment& assignment, int start_index,

2419 int vehicle) const;

2427 bool ReplaceUnusedVehicle(

2428 int unused_vehicle, int active_vehicle,

2429 operations_research::Assignment* compact_assignment) const;

2430

2431 void QuietCloseModel();

2432 void QuietCloseModelWithParameters(

2434 if (!closed_) {

2435 CloseModelWithParameters(parameters);

2436 }

2437 }

2438

2440 bool SolveMatchingModel(operations_research::Assignment* assignment,

2442#ifndef SWIG

2444 bool AppendAssignmentIfFeasible(

2445 const operations_research::Assignment& assignment,

2446 std::vector<std::unique_ptr<operations_research::Assignment>>*

2447 assignments,

2448 bool call_at_solution_monitors = true);

2449#endif

2452 absl::string_view description, int64_t solution_cost,

2453 int64_t start_time_ms);

2456 operations_research::Assignment* CompactAssignmentInternal(

2457 const operations_research::Assignment& assignment,

2458 bool check_compact_assignment) const;

2461 std::string FindErrorInSearchParametersForModel(

2466 void UpdateSearchFromParametersIfNeeded(

2469

2470 operations_research::Assignment* GetOrCreateAssignment();

2471 operations_research::Assignment* GetOrCreateTmpAssignment();

2474 RegularLimit* GetOrCreateLocalSearchLimit();

2475 RegularLimit* GetOrCreateLargeNeighborhoodSearchLimit();

2476 RegularLimit* GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();

2482 const std::vector<LocalSearchOperator*>& operators) const;

2485 const absl::flat_hash_set<RoutingLocalSearchOperator>&

2486 operators_to_consider) const;

2487

2488 struct FilterOptions {

2489 bool filter_objective;

2490 bool filter_with_cp_solver;

2491

2492 bool operator==(const FilterOptions& other) const {

2493 return other.filter_objective == filter_objective &&

2494 other.filter_with_cp_solver == filter_with_cp_solver;

2495 }

2496 template <typename H>

2497 friend H AbslHashValue(H h, const FilterOptions& options) {

2498 return H::combine(std::move(h), options.filter_objective,

2499 options.filter_with_cp_solver);

2500 }

2501 };

2502 std::vector<LocalSearchFilterManager::FilterEvent> CreateLocalSearchFilters(

2508 void CreateFirstSolutionDecisionBuilders(

2514#ifndef SWIG

2515 template <typename Heuristic, typename... Args>

2517 const Args&... args);

2518#endif

2521 DecisionBuilder* CreatePrimaryLocalSearchDecisionBuilder(

2525 void SetupAssignmentCollector(

2530 bool UsesLightPropagation(

2532 GetTabuVarsCallback tabu_var_callback_;

2533

2534

2535

2536

2537

2538 void DetectImplicitPickupAndDeliveries();

2539

2540 int GetVehicleStartClass(int64_t start) const;

2541

2542 void InitSameVehicleGroups(int number_of_groups) {

2543 same_vehicle_group_.assign(Size(), 0);

2544 same_vehicle_groups_.assign(number_of_groups, {});

2545 }

2546 void SetSameVehicleGroup(int index, int group) {

2547 same_vehicle_group_[index] = group;

2548 same_vehicle_groups_[group].push_back(index);

2549 }

2550

2551 void InitSameActiveVarGroups(int number_of_groups) {

2552 same_active_var_group_.assign(Size(), 0);

2553 same_active_var_groups_.assign(number_of_groups, {});

2554 }

2555 void SetSameActiveVarGroup(int index, int group) {

2556 same_active_var_group_[index] = group;

2557 same_active_var_groups_[group].push_back(index);

2558 }

2559

2562 int GetGlobalCumulOptimizerIndex(const RoutingDimension& dimension) const;

2563 int GetLocalCumulOptimizerIndex(const RoutingDimension& dimension) const;

2564

2566 std::unique_ptr<Solver> solver_;

2567 int nodes_;

2568 int vehicles_;

2569 int max_active_vehicles_;

2570 Constraint* no_cycle_constraint_ = nullptr;

2572 std::vector<operations_research::IntVar*> nexts_;

2573 std::vector<operations_research::IntVar*> vehicle_vars_;

2574 std::vector<operations_research::IntVar*> active_;

2580

2581 std::vector<std::vector<operations_research::IntVar*> > resource_vars_;

2582

2583

2584 std::vector<operations_research::IntVar*> vehicle_active_;

2585 std::vector<operations_research::IntVar*> vehicle_route_considered_;

2590 std::vector<operations_research::IntVar*> is_bound_to_end_;

2591 mutable RevSwitch is_bound_to_end_ct_added_;

2593 absl::flat_hash_map<std::string, DimensionIndex> dimension_name_to_index_;

2594 util_intops::StrongVector<DimensionIndex, RoutingDimension*> dimensions_;

2599

2600 std::vector<std::unique_ptr<ResourceGroup> > resource_groups_;

2602 util_intops::StrongVector<DimensionIndex, std::vector<int> >

2603 dimension_resource_group_indices_;

2604

2608 std::vector<DimensionCumulOptimizers<GlobalDimensionCumulOptimizer> >

2609 global_dimension_optimizers_;

2610 util_intops::StrongVector<DimensionIndex, int> global_optimizer_index_;

2611 std::vector<DimensionCumulOptimizers<LocalDimensionCumulOptimizer> >

2612 local_dimension_optimizers_;

2613 util_intops::StrongVector<DimensionIndex, int> local_optimizer_index_;

2614

2615 std::string primary_constrained_dimension_;

2617 operations_research::IntVar* cost_ = nullptr;

2618 std::vector<int> vehicle_to_transit_cost_;

2619 std::vector<int64_t> fixed_cost_of_vehicle_;

2620 std::vector<CostClassIndex> cost_class_index_of_vehicle_;

2621 bool has_vehicle_with_zero_cost_class_;

2622 std::vector<int64_t> linear_cost_factor_of_vehicle_;

2623 std::vector<int64_t> quadratic_cost_factor_of_vehicle_;

2624 bool vehicle_amortized_cost_factors_set_;

2625 mutable std::vector<

2626 absl::AnyInvocable<std::optional<int64_t>(const std::vector<int64_t>&)>>

2627 route_evaluators_;

2639 std::vector<bool> vehicle_used_when_empty_;

2640#ifndef SWIG

2641 absl::flat_hash_map<

2642 std::pair<std::string, std::string>,

2643 std::vector<Solver::PathEnergyCostConstraintSpecification::EnergyCost>,

2644 absl::Hash<std::pair<std::string, std::string>>>

2645 force_distance_to_energy_costs_;

2646 util_intops::StrongVector<CostClassIndex, CostClass> cost_classes_;

2647#endif

2648 bool costs_are_homogeneous_across_vehicles_;

2649 bool cache_callbacks_;

2650 mutable std::vector<CostCacheElement> cost_cache_;

2651 std::vector<VehicleClassIndex> vehicle_class_index_of_vehicle_;

2652 int num_vehicle_classes_;

2653

2654 VehicleTypeContainer vehicle_type_container_;

2655 std::function<int(int64_t)> vehicle_start_class_callback_;

2657 util_intops::StrongVector<DisjunctionIndex, Disjunction> disjunctions_;

2658

2659 std::vector<std::vector<DisjunctionIndex> > index_to_disjunctions_;

2661 std::vector<ValuedNodes<int64_t> > same_vehicle_costs_;

2663#ifndef SWIG

2664 std::vector<absl::flat_hash_set<int>> allowed_vehicles_;

2665#endif

2667 std::vector<PickupDeliveryPair> pickup_delivery_pairs_;

2668 std::vector<PickupDeliveryPair>

2669 implicit_pickup_delivery_pairs_without_alternatives_;

2670 std::vector<std::pair<DisjunctionIndex, DisjunctionIndex> >

2671 pickup_delivery_disjunctions_;

2672

2673

2674

2675

2676 std::vector<PickupDeliveryPosition> index_to_pickup_position_;

2677

2678 std::vector<PickupDeliveryPosition> index_to_delivery_position_;

2679

2680 std::vector<PickupAndDeliveryPolicy> vehicle_pickup_delivery_policy_;

2681

2682 std::vector<int> same_vehicle_group_;

2683

2684 std::vector<std::vector<int>> same_vehicle_groups_;

2685

2686 std::vector<int> same_active_var_group_;

2687

2688 std::vector<std::vector<int>> same_active_var_groups_;

2689

2690 std::vector<std::vector<DisjunctionIndex>> ordered_activity_groups_;

2691

2692

2693 std::vector<int> index_to_visit_type_;

2694

2695 std::vector<VisitTypePolicy> index_to_type_policy_;

2696

2697 std::vector<std::vector<int> > single_nodes_of_type_;

2698 std::vector<std::vector<int> > pair_indices_of_type_;

2699

2700 std::vector<absl::flat_hash_set<int> >

2701 hard_incompatible_types_per_type_index_;

2702 std::vector<absl::flat_hash_set<int> >

2703 temporal_incompatible_types_per_type_index_;

2704 const absl::flat_hash_set<int> empty_incompatibility_set_;

2705

2706 std::vector<std::vector<absl::flat_hash_set<int> > >

2707 same_vehicle_required_type_alternatives_per_type_index_;

2708 std::vector<std::vector<absl::flat_hash_set<int> > >

2709 required_type_alternatives_when_adding_type_index_;

2710 std::vector<std::vector<absl::flat_hash_set<int> > >

2711 required_type_alternatives_when_removing_type_index_;

2712 const std::vector<absl::flat_hash_set<int>> empty_required_type_alternatives_;

2713 absl::flat_hash_map<int, absl::flat_hash_set<VisitTypePolicy> >

2714 trivially_infeasible_visit_types_to_policies_;

2715

2716

2717

2718

2719

2720

2721

2722

2723

2724

2725

2726

2727

2728

2729

2730

2731 std::vector<std::vector<int> > topologically_sorted_visit_types_;

2732 std::vector<std::vector<int>> visit_type_components_;

2733

2734 int num_visit_types_;

2735 std::vector<std::vector<std::vector<int>>>

2736 topologically_sorted_node_precedences_;

2737

2738

2739 std::vector<int> index_to_equivalence_class_;

2741

2742

2744 int start_end_count_;

2745

2746 bool closed_ = false;

2748 bool enable_deep_serialization_ = true;

2749

2750

2753 std::unique_ptr<SecondaryOptimizer> secondary_optimizer_;

2754

2755

2756 std::vector<DecisionBuilder*> first_solution_decision_builders_;

2757 std::vector<IntVarFilteredDecisionBuilder*>

2758 first_solution_filtered_decision_builders_;

2762 const operations_research::Assignment* hint_ = nullptr;

2763 std::vector<LocalSearchOperator*> local_search_operators_;

2764 std::vector<SearchMonitor*> monitors_;

2765 std::vector<SearchMonitor*> secondary_ls_monitors_;

2766 std::vector<SearchMonitor*> at_solution_monitors_;

2767 std::vector<std::function<void()>> restore_dimension_values_reset_callbacks_;

2768 int monitors_before_setup_ = 0;

2769 int monitors_after_setup_ = 0;

2772 bool local_optimum_reached_ = false;

2773

2774 int64_t objective_lower_bound_ = kint64min;

2778 SolutionCollector* optimized_dimensions_assignment_collector_ = nullptr;

2785 operations_research::Assignment* assignment_ = nullptr;

2786 operations_research::Assignment* preassignment_ = nullptr;

2787 operations_research::Assignment* tmp_assignment_ = nullptr;

2790 std::vector<operations_research::IntVar*> extra_vars_;

2791 std::vector<IntervalVar*> extra_intervals_;

2792 std::vector<LocalSearchOperator*> extra_operators_;

2793 absl::flat_hash_map<FilterOptions, LocalSearchFilterManager*>

2794 local_search_filter_managers_;

2795 std::vector<LocalSearchFilterManager::FilterEvent> extra_filters_;

2796 absl::flat_hash_map<NodeNeighborsParameters,

2797 std::unique_ptr<NodeNeighborsByCostClass>>

2798 node_neighbors_by_cost_class_per_size_;

2799 std::unique_ptr<FinalizerVariables> finalizer_variables_;

2800#ifndef SWIG

2801 std::unique_ptr<SweepArranger> sweep_arranger_;

2802#endif

2803

2808 RegularLimit* first_solution_lns_limit_ = nullptr;

2809 absl::Duration time_buffer_;

2810

2812

2813 std::atomic<bool> interrupt_cp_sat_;

2814 std::atomic<bool> interrupt_cp_;

2815

2816 typedef std::pair<int64_t, int64_t> CacheKey;

2817 typedef absl::flat_hash_map<CacheKey, int64_t> TransitCallbackCache;

2818 typedef absl::flat_hash_map<CacheKey, StateDependentTransit>

2819 StateDependentTransitCallbackCache;

2820

2821

2822

2823

2824

2825

2826

2827

2828

2829 std::vector<TransitCallback1> unary_transit_evaluators_;

2830 std::vector<TransitCallback2> transit_evaluators_;

2831 std::vector<TransitEvaluatorSign> transit_evaluator_sign_;

2832

2833 std::vector<VariableIndexEvaluator2> state_dependent_transit_evaluators_;

2834 std::vector<std::unique_ptr<StateDependentTransitCallbackCache>>

2835 state_dependent_transit_evaluators_cache_;

2836

2837 std::vector<CumulDependentTransitCallback2>

2838 cumul_dependent_transit_evaluators_;

2839

2840

2841 std::unique_ptr<BinCapacities> bin_capacities_;

2842

2845 friend class ResourceGroup::Resource;

2846};

2847

2850 public:

2852 static const char kLightElement[];

2853 static const char kLightElement2[];

2854 static const char kRemoveValues[];

2855};

2857#if !defined(SWIG)

2864 public:

2868 bool CheckVehicle(int vehicle,

2880 int num_type_added_to_vehicle = 0;

2886 int num_type_removed_from_vehicle = 0;

2906

2908 const std::function<int64_t(int64_t)>& next_accessor);

2912 int pos) = 0;

2913 virtual bool FinalizeCheck() const { return true; }

2914

2916

2917 private:

2918 std::vector<TypePolicyOccurrence> occurrences_of_type_;

2919 std::vector<int64_t> current_route_visits_;

2920};

2921

2926 bool check_hard_incompatibilities);

2929 private:

2937

2944

2945 private:

2946 bool HasRegulationsToCheck() const override;

2947 void OnInitializeCheck() override {

2948 types_with_same_vehicle_requirements_on_route_.clear();

2949 }

2952

2953 bool CheckRequiredTypesCurrentlyOnRoute(

2954 absl::Span<const absl::flat_hash_set<int>> required_type_alternatives,

2955 int pos);

2956

2957 bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos) override;

2958 bool FinalizeCheck() const override;

2959

2960 absl::flat_hash_set<int> types_with_same_vehicle_requirements_on_route_;

2961};

2962

3052 std::vector<BoundCost> bound_costs_;

3053};

3093 return model_->TransitCallback(class_evaluators_[vehicle_class])(from_index,

3095 }

3099 return cumuls_[index];

3100 }

3103 }

3105 return fixed_transits_[index];

3106 }

3108 return slacks_[index];

3109 }

3115

3122 int64_t GetCumulVarMax(int64_t index) const { return CumulVar(index)->Max(); }

3124#if !defined(SWIGPYTHON)

3126

3126

3127 const std::vector<operations_research::IntVar*>& cumuls() const {

3128 return cumuls_;

3129 }

3130 const std::vector<operations_research::IntVar*>& fixed_transits() const {

3131 return fixed_transits_;

3132 }

3133 const std::vector<operations_research::IntVar*>& transits() const {

3134 return transits_;

3136 const std::vector<operations_research::IntVar*>& slacks() const {

3137 return slacks_;

3138 }

3139#if !defined(SWIGCSHARP) && !defined(SWIGJAVA)

3142 return forbidden_intervals_;

3143 }

3146 int64_t index, int64_t min_value, int64_t max_value) const;

3150 int64_t min_value) const {

3151 DCHECK_LT(index, forbidden_intervals_.size());

3153 forbidden_intervals_[index];

3154 const auto first_forbidden_interval_it =

3157 min_value >= first_forbidden_interval_it->start) {

3158

3159 return CapAdd(first_forbidden_interval_it->end, 1);

3163 }

3169 int64_t max_value) const {

3170 DCHECK_LT(index, forbidden_intervals_.size());

3172 forbidden_intervals_[index];

3173 const auto last_forbidden_interval_it =

3176 max_value <= last_forbidden_interval_it->end) {

3178 return CapSub(last_forbidden_interval_it->start, 1);

3179 }

3181 return max_value;

3182 }

3183

3184 const std::vector<int64_t>& vehicle_capacities() const {

3185 return vehicle_capacities_;

3186 }

3187

3188

3190 return model_->TransitCallback(

3191 class_evaluators_[vehicle_to_class_[vehicle]]);

3192 }

3193

3197 RoutingVehicleClassIndex vehicle_class) const {

3198 const int vehicle = model_->GetVehicleOfClass(vehicle_class);

3199 DCHECK_NE(vehicle, -1);

3200 return transit_evaluator(vehicle);

3201 }

3202

3203

3205 for (int evaluator_index : class_evaluators_) {

3206 if (model_->UnaryTransitCallbackOrNull(evaluator_index) == nullptr) {

3207 return false;

3209 }

3210 return true;

3211 }

3212

3215

3217 int vehicle) const {

3218 return model_->UnaryTransitCallbackOrNull(

3219 class_evaluators_[vehicle_to_class_[vehicle]]);

3220 }

3222 int vehicle) const {

3223 return model_->TransitCallback(

3224 class_evaluators_[vehicle_to_class_[vehicle]]);

3225 }

3228 bool AreVehicleTransitsPositive(int vehicle) const {

3229 const int evaluator_index = class_evaluators_[vehicle_to_class_[vehicle]];

3230 return model()->transit_evaluator_sign_[evaluator_index] ==

3232 }

3233 bool AllTransitEvaluatorSignsAreUnknown() const;

3234 RoutingModel::TransitEvaluatorSign GetTransitEvaluatorSign(

3235 int vehicle) const {

3236 const int evaluator_index = class_evaluators_[vehicle_to_class_[vehicle]];

3237 return model()->transit_evaluator_sign_[evaluator_index];

3238 }

3239 int vehicle_to_class(int vehicle) const { return vehicle_to_class_[vehicle]; }

3241 if (vehicle_to_cumul_dependent_class_.empty()) {

3242 return -1;

3243 }

3244 DCHECK_LT(vehicle, vehicle_to_cumul_dependent_class_.size());

3245 return vehicle_to_cumul_dependent_class_[vehicle];

3246 }

3258

3266

3277

3278#ifndef SWIG

3291 int64_t index) const;

3292#endif

3293

3303 int64_t coefficient);

3315

3326 int64_t coefficient);

3353

3354#if !defined(SWIGPYTHON)

3356 int pre_travel_evaluator,

3357 int post_travel_evaluator);

3358#endif

3359

3362 std::vector<int64_t> node_visit_transits);

3363

3369 int vehicle);

3375#if !defined(SWIGPYTHON)

3379 std::vector<IntervalVar*> breaks, int vehicle,

3380 std::vector<int64_t> node_visit_transits,

3381 std::function<int64_t(int64_t, int64_t)> delays);

3382

3385 int vehicle) const;

3388

3389 const std::vector<std::pair<int64_t, int64_t> >&

3391

3392#endif

3395

3405 int64_t ShortestTransitionSlack(int64_t node) const;

3406

3408 operations_research::RoutingDimensionIndex index() const {

3409 return index_;

3410 }

3412 const std::string& name() const { return name_; }

3413

3415#ifndef SWIG

3416 const ReverseArcListGraph<int, int>& GetPathPrecedenceGraph() const {

3417 return path_precedence_graph_;

3418 }

3419#endif

3420

3431

3434

3438 int pickup_alternative_index,

3439 int delivery_alternative_index) const;

3440

3442 int64_t first_node;

3443 int64_t second_node;

3444 int64_t offset;

3445 enum class PerformedConstraint {

3446

3447 kFirstAndSecondIndependent,

3448

3449 kSecondImpliesFirst,

3450

3451 kFirstImpliesSecond,

3452

3453 kFirstAndSecondEqual,

3454 };

3455 PerformedConstraint performed_constraint;

3456 };

3457

3458 void AddNodePrecedence(NodePrecedence precedence) {

3459 node_precedences_.push_back(precedence);

3460 }

3462 return node_precedences_;

3465

3468 kInactive,

3470 };

3472 bool first_unperformed, bool second_unperformed,

3476 if (first_unperformed || second_unperformed) {

3479 break;

3480 case NodePrecedence::PerformedConstraint::kSecondImpliesFirst:

3481 if (first_unperformed) {

3484 }

3485 if (second_unperformed) return PrecedenceStatus::kInactive;

3488 if (second_unperformed) {

3492 if (first_unperformed) return PrecedenceStatus::kInactive;

3493 break;

3494 case NodePrecedence::PerformedConstraint::kFirstAndSecondEqual:

3495 if (first_unperformed != second_unperformed) {

3496 return PrecedenceStatus::kInvalid;

3497 }

3498 if (first_unperformed) return PrecedenceStatus::kInactive;

3499 break;

3500 }

3501 return PrecedenceStatus::kActive;

3502 }

3503 void AddNodePrecedence(

3504 int64_t first_node, int64_t second_node, int64_t offset,

3505 NodePrecedence::PerformedConstraint performed_constraint =

3506 NodePrecedence::PerformedConstraint::kFirstAndSecondIndependent) {

3507 AddNodePrecedence({first_node, second_node, offset, performed_constraint});

3508 }

3509#else

3510 void AddNodePrecedence(int64_t first_node, int64_t second_node,

3511 int64_t offset) {

3512 AddNodePrecedence(

3513 {first_node, second_node, offset,

3514 NodePrecedence::PerformedConstraint::kFirstAndSecondIndependent});

3515 }

3516#endif

3517

3518 int64_t GetSpanUpperBoundForVehicle(int vehicle) const {

3519 return vehicle_span_upper_bounds_[vehicle];

3520 }

3521#ifndef SWIG

3522 const std::vector<int64_t>& vehicle_span_upper_bounds() const {

3523 return vehicle_span_upper_bounds_;

3524 }

3525#endif

3526 int64_t GetSpanCostCoefficientForVehicle(int vehicle) const {

3527 return vehicle_span_cost_coefficients_[vehicle];

3528 }

3529#ifndef SWIG

3530 int64_t GetSpanCostCoefficientForVehicleClass(

3531 RoutingVehicleClassIndex vehicle_class) const {

3532 const int vehicle = model_->GetVehicleOfClass(vehicle_class);

3533 DCHECK_NE(vehicle, -1);

3534 return GetSpanCostCoefficientForVehicle(vehicle);

3535 }

3536#endif

3537#ifndef SWIG

3539 return vehicle_span_cost_coefficients_;

3540 }

3541#endif

3544 return vehicle_slack_cost_coefficients_;

3545 }

3546#endif

3548 return vehicle_slack_cost_coefficients_[vehicle];

3549 }

3552 RoutingVehicleClassIndex vehicle_class) const {

3553 const int vehicle = model_->GetVehicleOfClass(vehicle_class);

3554 DCHECK_NE(vehicle, -1);

3556 }

3557#endif

3559 return global_span_cost_coefficient_;

3560 }

3561

3562 int64_t GetGlobalOptimizerOffset() const {

3563 DCHECK_GE(global_optimizer_offset_, 0);

3564 return global_optimizer_offset_;

3565 }

3566 int64_t GetLocalOptimizerOffsetForVehicle(int vehicle) const {

3567 if (vehicle >= local_optimizer_offset_for_vehicle_.size()) {

3568 return 0;

3569 }

3570 DCHECK_GE(local_optimizer_offset_for_vehicle_[vehicle], 0);

3571 return local_optimizer_offset_for_vehicle_[vehicle];

3572 }

3573

3576 void SetSoftSpanUpperBoundForVehicle(BoundCost bound_cost, int vehicle) {

3577 if (!HasSoftSpanUpperBounds()) {

3578 vehicle_soft_span_upper_bound_ = std::make_unique<SimpleBoundCosts>(

3579 model_->vehicles(), BoundCost{kint64max, 0});

3580 }

3581 vehicle_soft_span_upper_bound_->bound_cost(vehicle) = bound_cost;

3583 bool HasSoftSpanUpperBounds() const {

3584 return vehicle_soft_span_upper_bound_ != nullptr;

3585 }

3588 return vehicle_soft_span_upper_bound_->bound_cost(vehicle);

3589 }

3592 void SetQuadraticCostSoftSpanUpperBoundForVehicle(BoundCost bound_cost,

3593 int vehicle) {

3594 if (!HasQuadraticCostSoftSpanUpperBounds()) {

3595 vehicle_quadratic_cost_soft_span_upper_bound_ =

3596 std::make_unique<SimpleBoundCosts>(model_->vehicles(),

3598 }

3599 vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle) =

3600 bound_cost;

3601 }

3602 bool HasQuadraticCostSoftSpanUpperBounds() const {

3603 return vehicle_quadratic_cost_soft_span_upper_bound_ != nullptr;

3604 }

3605 BoundCost GetQuadraticCostSoftSpanUpperBoundForVehicle(int vehicle) const {

3607 return vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle);

3608 }

3609

3610 private:

3611 struct SoftBound {

3613 int64_t bound;

3614 int64_t coefficient;

3615 };

3616

3617 struct PiecewiseLinearCost {

3618 PiecewiseLinearCost() : var(nullptr), cost(nullptr) {}

3620 std::unique_ptr<PiecewiseLinearFunction> cost;

3621 };

3628 const std::string& name, SelfBased);

3629 void Initialize(absl::Span<const int> transit_evaluators,

3630 absl::Span<const int> cumul_dependent_transit_evaluators,

3631 absl::Span<const int> state_dependent_transit_evaluators,

3632 int64_t slack_max);

3633 void InitializeCumuls();

3634 void InitializeTransits(

3635 absl::Span<const int> transit_evaluators,

3636 absl::Span<const int> cumul_dependent_transit_evaluators,

3637 absl::Span<const int> state_dependent_transit_evaluators,

3638 int64_t slack_max);

3639 void InitializeTransitVariables(int64_t slack_max);

3641 void SetupCumulVarSoftUpperBoundCosts(

3642 std::vector<operations_research::IntVar*>* cost_elements) const;

3644 void SetupCumulVarSoftLowerBoundCosts(

3645 std::vector<operations_research::IntVar*>* cost_elements) const;

3646 void SetupCumulVarPiecewiseLinearCosts(

3647 std::vector<operations_research::IntVar*>* cost_elements) const;

3650 void SetupGlobalSpanCost(

3651 std::vector<operations_research::IntVar*>* cost_elements) const;

3652 void SetupSlackAndDependentTransitCosts() const;

3654 void CloseModel(bool use_light_propagation);

3655

3656 void SetOffsetForGlobalOptimizer(int64_t offset) {

3657 global_optimizer_offset_ = std::max(Zero(), offset);

3658 }

3660 void SetVehicleOffsetsForLocalOptimizer(std::vector<int64_t> offsets) {

3662 std::transform(offsets.begin(), offsets.end(), offsets.begin(),

3663 [](int64_t offset) { return std::max(Zero(), offset); });

3664 local_optimizer_offset_for_vehicle_ = std::move(offsets);

3665 }

3666

3667 std::vector<operations_research::IntVar*> cumuls_;

3668 std::vector<SortedDisjointIntervalList> forbidden_intervals_;

3669 std::vector<operations_research::IntVar*> capacity_vars_;

3670 const std::vector<int64_t> vehicle_capacities_;

3671 std::vector<operations_research::IntVar*> transits_;

3672 std::vector<operations_research::IntVar*> fixed_transits_;

3675 std::vector<int> class_evaluators_;

3676 std::vector<int> vehicle_to_class_;

3677

3681 std::vector<int> cumul_dependent_class_evaluators_;

3682 std::vector<int> vehicle_to_cumul_dependent_class_;

3683#ifndef SWIG

3685#endif

3686

3687

3688

3689

3690 std::vector<NodePrecedence> node_precedences_;

3691

3692

3693

3694

3695 const RoutingDimension* const base_dimension_;

3696

3697

3698

3699 std::vector<int> state_dependent_class_evaluators_;

3700 std::vector<int> state_dependent_vehicle_to_class_;

3701

3702

3703

3704

3705 std::vector<PickupToDeliveryLimitFunction>

3706 pickup_to_delivery_limits_per_pair_index_;

3707

3708

3709 bool break_constraints_are_initialized_ = false;

3710

3711 std::vector<std::vector<IntervalVar*> > vehicle_break_intervals_;

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

3713 vehicle_break_distance_duration_;

3714

3715

3716

3717

3718 std::vector<int> vehicle_pre_travel_evaluators_;

3719 std::vector<int> vehicle_post_travel_evaluators_;

3720

3721 std::vector<operations_research::IntVar*> slacks_;

3722 std::vector<operations_research::IntVar*> dependent_transits_;

3723 std::vector<int64_t> vehicle_span_upper_bounds_;

3724 int64_t global_span_cost_coefficient_;

3725 std::vector<int64_t> vehicle_span_cost_coefficients_;

3726 std::vector<int64_t> vehicle_slack_cost_coefficients_;

3727 std::vector<SoftBound> cumul_var_soft_upper_bound_;

3728 std::vector<SoftBound> cumul_var_soft_lower_bound_;

3729 std::vector<PiecewiseLinearCost> cumul_var_piecewise_linear_cost_;

3730 RoutingModel* const model_;

3731 const operations_research::RoutingDimensionIndex index_;

3732 const std::string name_;

3733 int64_t global_optimizer_offset_;

3734 std::vector<int64_t> local_optimizer_offset_for_vehicle_;

3736 std::unique_ptr<SimpleBoundCosts> vehicle_soft_span_upper_bound_;

3737 std::unique_ptr<SimpleBoundCosts>

3738 vehicle_quadratic_cost_soft_span_upper_bound_;

3739 friend class RoutingModel;

3740 friend class RoutingModelInspector;

3741};

3742

3747bool SolveModelWithSat(RoutingModel* model, RoutingSearchStats* search_stats,

3748 const RoutingSearchParameters& search_parameters,

3751

3752}

3753#endif