157 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
158 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
162 #include <functional>
169 #include "absl/container/flat_hash_map.h"
170 #include "absl/container/flat_hash_set.h"
171 #include "absl/functional/bind_front.h"
172 #include "absl/hash/hash.h"
173 #include "absl/time/time.h"
183 #include "ortools/constraint_solver/routing_enums.pb.h"
185 #include "ortools/constraint_solver/routing_parameters.pb.h"
188 #include "ortools/glop/parameters.pb.h"
198 class GlobalDimensionCumulOptimizer;
199 class LocalDimensionCumulOptimizer;
200 class LocalSearchOperator;
202 class IntVarFilteredDecisionBuilder;
203 class IntVarFilteredHeuristic;
204 class IndexNeighborFinder;
206 class RoutingDimension;
308 std::vector<DimensionCost>
316 if (
a.evaluator_index !=
b.evaluator_index) {
317 return a.evaluator_index <
b.evaluator_index;
319 return a.dimension_transit_evaluator_class_and_cost_coefficient <
320 b.dimension_transit_evaluator_class_and_cost_coefficient;
408 std::vector<std::vector<int64> > values);
414 CHECK_LT(callback_index, transit_evaluators_.size());
415 return transit_evaluators_[callback_index];
418 CHECK_LT(callback_index, unary_transit_evaluators_.size());
419 return unary_transit_evaluators_[callback_index];
422 int callback_index)
const {
423 CHECK_LT(callback_index, state_dependent_transit_evaluators_.size());
424 return state_dependent_transit_evaluators_[callback_index];
450 bool fix_start_cumul_to_zero,
const std::string&
name);
452 const std::vector<int>& evaluator_indices,
int64 slack_max,
455 std::vector<int64> vehicle_capacities,
456 bool fix_start_cumul_to_zero,
457 const std::string&
name);
459 const std::vector<int>& evaluator_indices,
int64 slack_max,
460 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
461 const std::string&
name);
472 bool fix_start_cumul_to_zero,
const std::string&
name);
474 bool fix_start_cumul_to_zero,
475 const std::string&
name) {
477 fix_start_cumul_to_zero,
name);
490 bool fix_start_cumul_to_zero,
491 const std::string&
name);
502 std::vector<std::vector<int64> > values,
511 const std::vector<int>& pure_transits,
512 const std::vector<int>& dependent_transits,
514 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
515 const std::string&
name) {
516 return AddDimensionDependentDimensionWithVehicleCapacityInternal(
517 pure_transits, dependent_transits, base_dimension, slack_max,
518 std::move(vehicle_capacities), fix_start_cumul_to_zero,
name);
524 int64 slack_max, std::vector<int64> vehicle_capacities,
525 bool fix_start_cumul_to_zero,
const std::string&
name);
529 int64 vehicle_capacity,
bool fix_start_cumul_to_zero,
530 const std::string&
name);
532 int pure_transit,
int dependent_transit,
534 int64 vehicle_capacity,
bool fix_start_cumul_to_zero,
535 const std::string&
name);
552 std::vector<IntVar*> spans,
553 std::vector<IntVar*> total_slacks);
560 return dimensions_.get();
567 const std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer> >&
569 return global_dimension_optimizers_;
571 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >&
573 return local_dimension_optimizers_;
575 const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >&
577 return local_dimension_mp_optimizers_;
591 bool HasDimension(
const std::string& dimension_name)
const;
594 const std::string& dimension_name)
const;
598 const std::string& dimension_name)
const;
605 primary_constrained_dimension_ = dimension_name;
609 return primary_constrained_dimension_;
629 int64 max_cardinality = 1);
633 return index_to_disjunctions_[
index];
638 template <
typename F>
642 if (disjunctions_[disjunction].
value.max_cardinality == max_cardinality) {
643 for (
const int64 d_index : disjunctions_[disjunction].indices) {
649 #if !defined(SWIGPYTHON)
654 return disjunctions_[
index].indices;
658 int64 GetDisjunctionPenalty(DisjunctionIndex index) const {
659 return disjunctions_[
index].value.penalty;
664 return disjunctions_[
index].value.max_cardinality;
672 std::vector<std::pair<int64, int64>> GetPerfectBinaryDisjunctions()
const;
678 void IgnoreDisjunctionsAlreadyForcedToZero();
683 void AddSoftSameVehicleConstraint(
const std::vector<int64>& indices,
690 void SetAllowedVehiclesForIndex(
const std::vector<int>& vehicles,
695 return allowed_vehicles_[
index].empty() ||
696 allowed_vehicles_[
index].find(vehicle) !=
697 allowed_vehicles_[
index].end();
715 void AddPickupAndDelivery(
int64 pickup,
int64 delivery);
719 void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction,
720 DisjunctionIndex delivery_disjunction);
725 const std::vector<std::pair<int, int> >&
726 GetPickupIndexPairs(
int64 node_index)
const;
728 const std::vector<std::pair<int, int> >&
729 GetDeliveryIndexPairs(
int64 node_index)
const;
734 void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy);
735 void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy,
737 PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(
742 int GetNumOfSingletonNodes()
const;
747 return pickup_delivery_pairs_;
749 const std::vector<std::pair<DisjunctionIndex, DisjunctionIndex>>&
751 return pickup_delivery_disjunctions_;
759 return implicit_pickup_delivery_pairs_without_alternatives_;
773 enum VisitTypePolicy {
788 TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED
791 void SetVisitType(
int64 index,
int type, VisitTypePolicy type_policy);
793 const std::vector<int>& GetSingleNodesOfType(
int type)
const;
794 const std::vector<int>& GetPairIndicesOfType(
int type)
const;
795 VisitTypePolicy GetVisitTypePolicy(
int64 index)
const;
800 void CloseVisitTypes();
806 return topologically_sorted_visit_types_;
813 void AddHardTypeIncompatibility(int type1, int type2);
814 void AddTemporalTypeIncompatibility(
int type1,
int type2);
816 const absl::flat_hash_set<int>& GetHardTypeIncompatibilitiesOfType(
818 const absl::flat_hash_set<int>& GetTemporalTypeIncompatibilitiesOfType(
823 return has_hard_type_incompatibilities_;
826 return has_temporal_type_incompatibilities_;
838 void AddSameVehicleRequiredTypeAlternatives(
839 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
844 void AddRequiredTypeAlternativesWhenAddingType(
845 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
851 void AddRequiredTypeAlternativesWhenRemovingType(
852 int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
856 const std::vector<absl::flat_hash_set<int> >&
857 GetSameVehicleRequiredTypeAlternativesOfType(
int type)
const;
859 const std::vector<absl::flat_hash_set<int> >&
860 GetRequiredTypeAlternativesWhenAddingType(
int type)
const;
862 const std::vector<absl::flat_hash_set<int> >&
863 GetRequiredTypeAlternativesWhenRemovingType(
int type)
const;
868 return has_same_vehicle_type_requirements_;
871 return has_temporal_type_requirements_;
877 return HasTemporalTypeIncompatibilities() ||
878 HasHardTypeIncompatibilities() || HasSameVehicleTypeRequirements() ||
879 HasTemporalTypeRequirements();
886 int64 UnperformedPenalty(
int64 var_index)
const;
890 int64 UnperformedPenaltyOrValue(
int64 default_value,
int64 var_index)
const;
894 int64 GetDepot()
const;
901 max_active_vehicles_ = max_active_vehicles;
908 void SetArcCostEvaluatorOfAllVehicles(
int evaluator_index);
910 void SetArcCostEvaluatorOfVehicle(
int evaluator_index,
int vehicle);
913 void SetFixedCostOfAllVehicles(
int64 cost);
915 void SetFixedCostOfVehicle(
int64 cost,
int vehicle);
919 int64 GetFixedCostOfVehicle(
int vehicle)
const;
936 void SetAmortizedCostFactorsOfAllVehicles(
int64 linear_cost_factor,
937 int64 quadratic_cost_factor);
939 void SetAmortizedCostFactorsOfVehicle(
int64 linear_cost_factor,
940 int64 quadratic_cost_factor,
944 return linear_cost_factor_of_vehicle_;
947 return quadratic_cost_factor_of_vehicle_;
952 consider_empty_route_costs_[vehicle] = consider_costs;
957 return consider_empty_route_costs_[vehicle];
964 return first_solution_evaluator_;
969 first_solution_evaluator_ = std::move(evaluator);
979 void AddAtSolutionCallback(std::function<
void()>
callback);
984 void AddVariableMinimizedByFinalizer(
IntVar*
var);
987 void AddVariableMaximizedByFinalizer(
IntVar*
var);
1003 void CloseModelWithParameters(
1004 const RoutingSearchParameters& search_parameters);
1020 const RoutingSearchParameters& search_parameters,
1021 std::vector<const Assignment*>* solutions =
nullptr);
1022 const Assignment* SolveFromAssignmentWithParameters(
1024 const RoutingSearchParameters& search_parameters,
1025 std::vector<const Assignment*>* solutions =
nullptr);
1031 void SetAssignmentFromOtherModelAssignment(
1040 int64 ComputeLowerBound();
1051 IntVar* ApplyLocks(
const std::vector<int64>& locks);
1060 bool ApplyLocksToAllVehicles(
const std::vector<std::vector<int64>>& locks,
1071 bool WriteAssignment(
const std::string& file_name)
const;
1075 Assignment* ReadAssignment(
const std::string& file_name);
1085 const std::vector<std::vector<int64>>& routes,
1086 bool ignore_inactive_indices);
1103 bool RoutesToAssignment(
const std::vector<std::vector<int64>>& routes,
1104 bool ignore_inactive_indices,
bool close_routes,
1109 void AssignmentToRoutes(
const Assignment& assignment,
1110 std::vector<std::vector<int64>>*
const routes)
const;
1116 std::vector<std::vector<int64>> GetRoutesFromAssignment(
1142 void AddToAssignment(
IntVar*
const var);
1154 const Assignment* PackCumulsOfOptimizerDimensionsFromAssignment(
1155 const Assignment* original_assignment, absl::Duration duration_limit);
1159 sweep_arranger_.reset(sweep_arranger);
1170 CHECK(filter !=
nullptr);
1172 LOG(
WARNING) <<
"Model is closed, filter addition will be ignored.";
1174 extra_filters_.push_back({filter, LocalSearchFilterManager::kRelax});
1175 extra_filters_.push_back({filter, LocalSearchFilterManager::kAccept});
1182 int64 End(
int vehicle)
const {
return ends_[vehicle]; }
1195 bool IsVehicleUsed(
const Assignment& assignment,
int vehicle)
const;
1197 #if !defined(SWIGPYTHON)
1200 const std::vector<IntVar*>&
Nexts()
const {
return nexts_; }
1203 const std::vector<IntVar*>&
VehicleVars()
const {
return vehicle_vars_; }
1213 return vehicle_active_[vehicle];
1218 return vehicle_costs_considered_[vehicle];
1229 int64 vehicle)
const;
1232 return costs_are_homogeneous_across_vehicles_;
1237 return GetArcCostForVehicle(from_index, to_index, 0);
1241 int64 GetArcCostForFirstSolution(
int64 from_index,
int64 to_index)
const;
1249 int64 cost_class_index)
const;
1254 DCHECK_LT(vehicle, cost_class_index_of_vehicle_.size());
1255 DCHECK_GE(cost_class_index_of_vehicle_[vehicle], 0);
1256 return cost_class_index_of_vehicle_[vehicle];
1262 if (cost_class_index == kCostClassIndexOfZeroCost) {
1263 return has_vehicle_with_zero_cost_class_;
1265 return cost_class_index < cost_classes_.size();
1271 return std::max(0, GetCostClassesCount() - 1);
1275 return vehicle_class_index_of_vehicle_[vehicle];
1282 return same_vehicle_groups_[same_vehicle_group_[node]];
1287 return vehicle_type_container_;
1313 std::string DebugOutputAssignment(
1315 const std::string& dimension_to_print)
const;
1322 std::vector<std::vector<std::pair<int64, int64>>> GetCumulBounds(
1338 return limit_->AbsoluteSolverDeadline() - solver_->Now();
1347 int64 Size()
const {
return nodes_ + vehicles_ - start_end_count_; }
1351 int64 GetNumberOfDecisionsInFirstSolution(
1352 const RoutingSearchParameters& search_parameters)
const;
1353 int64 GetNumberOfRejectsInFirstSolution(
1354 const RoutingSearchParameters& search_parameters)
const;
1358 return automatic_first_solution_strategy_;
1362 bool IsMatchingModel()
const;
1368 std::function<std::vector<operations_research::IntVar*>(
RoutingModel*)>;
1395 static std::unique_ptr<LocalSearchOperator> MakeGreedyDescentLSOperator(
1396 std::vector<IntVar*> variables);
1416 enum RoutingLocalSearchOperator {
1419 LIGHT_RELOCATE_PAIR,
1427 GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,
1428 LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,
1429 GLOBAL_CHEAPEST_INSERTION_PATH_LNS,
1430 LOCAL_CHEAPEST_INSERTION_PATH_LNS,
1431 RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,
1432 GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,
1433 LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,
1434 RELOCATE_EXPENSIVE_CHAIN,
1438 RELOCATE_AND_MAKE_ACTIVE,
1439 MAKE_ACTIVE_AND_RELOCATE,
1441 MAKE_CHAIN_INACTIVE,
1443 EXTENDED_SWAP_ACTIVE,
1449 EXCHANGE_RELOCATE_PAIR,
1452 LOCAL_SEARCH_OPERATOR_COUNTER
1458 template <
typename T>
1459 struct ValuedNodes {
1460 std::vector<int64> indices;
1463 struct DisjunctionValues {
1465 int64 max_cardinality;
1467 typedef ValuedNodes<DisjunctionValues> Disjunction;
1471 struct CostCacheElement {
1477 CostClassIndex cost_class_index;
1483 void AddNoCycleConstraintInternal();
1484 bool AddDimensionWithCapacityInternal(
1485 const std::vector<int>& evaluator_indices,
int64 slack_max,
1486 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
1487 const std::string&
name);
1488 bool AddDimensionDependentDimensionWithVehicleCapacityInternal(
1489 const std::vector<int>& pure_transits,
1490 const std::vector<int>& dependent_transits,
1491 const RoutingDimension* base_dimension,
int64 slack_max,
1492 std::vector<int64> vehicle_capacities,
bool fix_start_cumul_to_zero,
1493 const std::string&
name);
1494 bool InitializeDimensionInternal(
1495 const std::vector<int>& evaluator_indices,
1496 const std::vector<int>& state_dependent_evaluator_indices,
1497 int64 slack_max,
bool fix_start_cumul_to_zero,
1498 RoutingDimension* dimension);
1499 DimensionIndex GetDimensionIndex(
const std::string& dimension_name)
const;
1528 void StoreDimensionCumulOptimizers(
const RoutingSearchParameters&
parameters);
1530 void ComputeCostClasses(
const RoutingSearchParameters&
parameters);
1531 void ComputeVehicleClasses();
1539 void ComputeVehicleTypes();
1549 void FinalizeVisitTypes();
1551 void TopologicallySortVisitTypes();
1553 CostClassIndex cost_class_index)
const;
1554 void AppendHomogeneousArcCosts(
const RoutingSearchParameters&
parameters,
1556 std::vector<IntVar*>* cost_elements);
1557 void AppendArcCosts(
const RoutingSearchParameters&
parameters,
int node_index,
1558 std::vector<IntVar*>* cost_elements);
1559 Assignment* DoRestoreAssignment();
1560 static const CostClassIndex kCostClassIndexOfZeroCost;
1561 int64 SafeGetCostClassInt64OfVehicle(
int64 vehicle)
const {
1563 return (vehicle >= 0 ? GetCostClassIndexOfVehicle(vehicle)
1564 : kCostClassIndexOfZeroCost)
1568 const CostClass& cost_class)
const;
1570 IntVar* CreateDisjunction(DisjunctionIndex disjunction);
1572 void AddPickupAndDeliverySetsInternal(
const std::vector<int64>& pickups,
1573 const std::vector<int64>& deliveries);
1576 IntVar* CreateSameVehicleCost(
int vehicle_index);
1579 int FindNextActive(
int index,
const std::vector<int64>& indices)
const;
1583 bool RouteCanBeUsedByVehicle(
const Assignment& assignment,
int start_index,
1592 bool ReplaceUnusedVehicle(
int unused_vehicle,
int active_vehicle,
1593 Assignment* compact_assignment)
const;
1595 void QuietCloseModel();
1596 void QuietCloseModelWithParameters(
1604 bool SolveMatchingModel(Assignment* assignment,
1608 bool AppendAssignmentIfFeasible(
1609 const Assignment& assignment,
1610 std::vector<std::unique_ptr<Assignment>>* assignments);
1613 void LogSolution(
const RoutingSearchParameters&
parameters,
1614 const std::string& description,
int64 solution_cost,
1615 int64 start_time_ms);
1618 Assignment* CompactAssignmentInternal(
const Assignment& assignment,
1619 bool check_compact_assignment)
const;
1624 std::string FindErrorInSearchParametersForModel(
1625 const RoutingSearchParameters& search_parameters)
const;
1627 void SetupSearch(
const RoutingSearchParameters& search_parameters);
1630 Assignment* GetOrCreateAssignment();
1631 Assignment* GetOrCreateTmpAssignment();
1632 RegularLimit* GetOrCreateLimit();
1633 RegularLimit* GetOrCreateLocalSearchLimit();
1634 RegularLimit* GetOrCreateLargeNeighborhoodSearchLimit();
1635 RegularLimit* GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
1636 LocalSearchOperator* CreateInsertionOperator();
1637 LocalSearchOperator* CreateMakeInactiveOperator();
1639 LocalSearchOperator* CreateCPOperator(
const T& operator_factory) {
1640 return operator_factory(solver_.get(), nexts_,
1641 CostsAreHomogeneousAcrossVehicles()
1642 ? std::vector<IntVar*>()
1644 vehicle_start_class_callback_);
1647 LocalSearchOperator* CreateCPOperator() {
1648 return CreateCPOperator(absl::bind_front(MakeLocalSearchOperator<T>));
1650 template <
class T,
class Arg>
1651 LocalSearchOperator* CreateOperator(
const Arg& arg) {
1652 return solver_->RevAlloc(
new T(nexts_,
1653 CostsAreHomogeneousAcrossVehicles()
1654 ? std::vector<IntVar*>()
1656 vehicle_start_class_callback_, arg));
1659 LocalSearchOperator* CreatePairOperator() {
1660 return CreateOperator<T>(pickup_delivery_pairs_);
1662 void CreateNeighborhoodOperators(
const RoutingSearchParameters&
parameters);
1663 LocalSearchOperator* ConcatenateOperators(
1664 const RoutingSearchParameters& search_parameters,
1665 const std::vector<LocalSearchOperator*>& operators)
const;
1666 LocalSearchOperator* GetNeighborhoodOperators(
1667 const RoutingSearchParameters& search_parameters)
const;
1668 std::vector<LocalSearchFilterManager::FilterEvent>
1669 GetOrCreateLocalSearchFilters(
const RoutingSearchParameters&
parameters,
1670 bool filter_cost =
true);
1671 LocalSearchFilterManager* GetOrCreateLocalSearchFilterManager(
1673 std::vector<LocalSearchFilterManager::FilterEvent>
1674 GetOrCreateFeasibilityFilters(
const RoutingSearchParameters&
parameters);
1675 LocalSearchFilterManager* GetOrCreateFeasibilityFilterManager(
1677 LocalSearchFilterManager* GetOrCreateStrongFeasibilityFilterManager(
1679 DecisionBuilder* CreateSolutionFinalizer(SearchLimit* lns_limit);
1680 DecisionBuilder* CreateFinalizerForMinimizedAndMaximizedVariables();
1681 void CreateFirstSolutionDecisionBuilders(
1682 const RoutingSearchParameters& search_parameters);
1683 DecisionBuilder* GetFirstSolutionDecisionBuilder(
1684 const RoutingSearchParameters& search_parameters)
const;
1685 IntVarFilteredDecisionBuilder* GetFilteredFirstSolutionDecisionBuilderOrNull(
1686 const RoutingSearchParameters&
parameters)
const;
1687 LocalSearchPhaseParameters* CreateLocalSearchParameters(
1688 const RoutingSearchParameters& search_parameters);
1689 DecisionBuilder* CreateLocalSearchDecisionBuilder(
1690 const RoutingSearchParameters& search_parameters);
1691 void SetupDecisionBuilders(
const RoutingSearchParameters& search_parameters);
1692 void SetupMetaheuristics(
const RoutingSearchParameters& search_parameters);
1693 void SetupAssignmentCollector(
1694 const RoutingSearchParameters& search_parameters);
1695 void SetupTrace(
const RoutingSearchParameters& search_parameters);
1696 void SetupImprovementLimit(
const RoutingSearchParameters& search_parameters);
1697 void SetupSearchMonitors(
const RoutingSearchParameters& search_parameters);
1698 bool UsesLightPropagation(
1699 const RoutingSearchParameters& search_parameters)
const;
1700 GetTabuVarsCallback tabu_var_callback_;
1706 void DetectImplicitPickupAndDeliveries();
1708 int GetVehicleStartClass(
int64 start)
const;
1710 void InitSameVehicleGroups(
int number_of_groups) {
1711 same_vehicle_group_.assign(Size(), 0);
1712 same_vehicle_groups_.assign(number_of_groups, {});
1714 void SetSameVehicleGroup(
int index,
int group) {
1715 same_vehicle_group_[
index] = group;
1716 same_vehicle_groups_[group].push_back(
index);
1720 std::unique_ptr<Solver> solver_;
1723 int max_active_vehicles_;
1724 Constraint* no_cycle_constraint_ =
nullptr;
1726 std::vector<IntVar*> nexts_;
1727 std::vector<IntVar*> vehicle_vars_;
1728 std::vector<IntVar*> active_;
1730 std::vector<IntVar*> vehicle_active_;
1731 std::vector<IntVar*> vehicle_costs_considered_;
1736 std::vector<IntVar*> is_bound_to_end_;
1737 mutable RevSwitch is_bound_to_end_ct_added_;
1739 absl::flat_hash_map<std::string, DimensionIndex> dimension_name_to_index_;
1745 std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer> >
1746 global_dimension_optimizers_;
1748 std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >
1749 local_dimension_optimizers_;
1750 std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >
1751 local_dimension_mp_optimizers_;
1754 std::string primary_constrained_dimension_;
1756 IntVar* cost_ =
nullptr;
1757 std::vector<int> vehicle_to_transit_cost_;
1758 std::vector<int64> fixed_cost_of_vehicle_;
1759 std::vector<CostClassIndex> cost_class_index_of_vehicle_;
1760 bool has_vehicle_with_zero_cost_class_;
1761 std::vector<int64> linear_cost_factor_of_vehicle_;
1762 std::vector<int64> quadratic_cost_factor_of_vehicle_;
1763 bool vehicle_amortized_cost_factors_set_;
1774 std::vector<bool> consider_empty_route_costs_;
1778 bool costs_are_homogeneous_across_vehicles_;
1779 bool cache_callbacks_;
1780 mutable std::vector<CostCacheElement> cost_cache_;
1781 std::vector<VehicleClassIndex> vehicle_class_index_of_vehicle_;
1785 VehicleTypeContainer vehicle_type_container_;
1786 std::function<int(
int64)> vehicle_start_class_callback_;
1789 std::vector<std::vector<DisjunctionIndex> > index_to_disjunctions_;
1791 std::vector<ValuedNodes<int64> > same_vehicle_costs_;
1794 std::vector<absl::flat_hash_set<int>> allowed_vehicles_;
1797 IndexPairs pickup_delivery_pairs_;
1798 IndexPairs implicit_pickup_delivery_pairs_without_alternatives_;
1799 std::vector<std::pair<DisjunctionIndex, DisjunctionIndex> >
1800 pickup_delivery_disjunctions_;
1805 std::vector<std::vector<std::pair<int, int> > > index_to_pickup_index_pairs_;
1807 std::vector<std::vector<std::pair<int, int> > >
1808 index_to_delivery_index_pairs_;
1810 std::vector<PickupAndDeliveryPolicy> vehicle_pickup_delivery_policy_;
1812 std::vector<int> same_vehicle_group_;
1814 std::vector<std::vector<int>> same_vehicle_groups_;
1817 std::vector<int> index_to_visit_type_;
1819 std::vector<VisitTypePolicy> index_to_type_policy_;
1821 std::vector<std::vector<int> > single_nodes_of_type_;
1822 std::vector<std::vector<int> > pair_indices_of_type_;
1824 std::vector<absl::flat_hash_set<int> >
1825 hard_incompatible_types_per_type_index_;
1826 bool has_hard_type_incompatibilities_;
1827 std::vector<absl::flat_hash_set<int> >
1828 temporal_incompatible_types_per_type_index_;
1829 bool has_temporal_type_incompatibilities_;
1831 std::vector<std::vector<absl::flat_hash_set<int> > >
1832 same_vehicle_required_type_alternatives_per_type_index_;
1833 bool has_same_vehicle_type_requirements_;
1834 std::vector<std::vector<absl::flat_hash_set<int> > >
1835 required_type_alternatives_when_adding_type_index_;
1836 std::vector<std::vector<absl::flat_hash_set<int> > >
1837 required_type_alternatives_when_removing_type_index_;
1838 bool has_temporal_type_requirements_;
1839 absl::flat_hash_map<int, absl::flat_hash_set<VisitTypePolicy> >
1840 trivially_infeasible_visit_types_to_policies_;
1857 std::vector<std::vector<int> > topologically_sorted_visit_types_;
1859 int num_visit_types_;
1862 std::vector<int> index_to_equivalence_class_;
1863 std::vector<int> index_to_vehicle_;
1864 std::vector<int64> starts_;
1865 std::vector<int64> ends_;
1868 RoutingIndexManager manager_;
1869 int start_end_count_;
1871 bool closed_ =
false;
1872 Status status_ = ROUTING_NOT_SOLVED;
1873 bool enable_deep_serialization_ =
true;
1876 std::vector<DecisionBuilder*> first_solution_decision_builders_;
1877 std::vector<IntVarFilteredDecisionBuilder*>
1878 first_solution_filtered_decision_builders_;
1879 Solver::IndexEvaluator2 first_solution_evaluator_;
1881 FirstSolutionStrategy::UNSET;
1882 std::vector<LocalSearchOperator*> local_search_operators_;
1883 std::vector<SearchMonitor*> monitors_;
1884 SolutionCollector* collect_assignments_ =
nullptr;
1885 SolutionCollector* collect_one_assignment_ =
nullptr;
1886 SolutionCollector* packed_dimensions_assignment_collector_ =
nullptr;
1887 DecisionBuilder* solve_db_ =
nullptr;
1888 DecisionBuilder* improve_db_ =
nullptr;
1889 DecisionBuilder* restore_assignment_ =
nullptr;
1890 DecisionBuilder* restore_tmp_assignment_ =
nullptr;
1891 Assignment* assignment_ =
nullptr;
1892 Assignment* preassignment_ =
nullptr;
1893 Assignment* tmp_assignment_ =
nullptr;
1894 std::vector<IntVar*> extra_vars_;
1895 std::vector<IntervalVar*> extra_intervals_;
1896 std::vector<LocalSearchOperator*> extra_operators_;
1897 LocalSearchFilterManager* local_search_filter_manager_ =
nullptr;
1898 LocalSearchFilterManager* feasibility_filter_manager_ =
nullptr;
1899 LocalSearchFilterManager* strong_feasibility_filter_manager_ =
nullptr;
1900 std::vector<LocalSearchFilterManager::FilterEvent> extra_filters_;
1902 std::vector<std::pair<IntVar*, int64>> finalizer_variable_cost_pairs_;
1903 std::vector<std::pair<IntVar*, int64>> finalizer_variable_target_pairs_;
1904 absl::flat_hash_map<IntVar*, int> finalizer_variable_cost_index_;
1905 absl::flat_hash_set<IntVar*> finalizer_variable_target_set_;
1906 std::unique_ptr<SweepArranger> sweep_arranger_;
1909 RegularLimit*
limit_ =
nullptr;
1910 RegularLimit* ls_limit_ =
nullptr;
1911 RegularLimit* lns_limit_ =
nullptr;
1912 RegularLimit* first_solution_lns_limit_ =
nullptr;
1914 typedef std::pair<int64, int64> CacheKey;
1915 typedef absl::flat_hash_map<CacheKey, int64> TransitCallbackCache;
1916 typedef absl::flat_hash_map<CacheKey, StateDependentTransit>
1917 StateDependentTransitCallbackCache;
1919 std::vector<TransitCallback1> unary_transit_evaluators_;
1920 std::vector<TransitCallback2> transit_evaluators_;
1931 std::vector<bool> is_transit_evaluator_positive_;
1932 std::vector<VariableIndexEvaluator2> state_dependent_transit_evaluators_;
1933 std::vector<std::unique_ptr<StateDependentTransitCallbackCache>>
1934 state_dependent_transit_evaluators_cache_;
1946 static const char kLightElement[];
1947 static const char kLightElement2[];
1948 static const char kRemoveValues[];
1962 int num_chain_tasks = 0;
1978 duration_min.clear();
1979 duration_max.clear();
1982 is_preemptible.clear();
1983 forbidden_intervals.clear();
1984 distance_duration.clear();
1987 num_chain_tasks = 0;
1993 bool Propagate(Tasks* tasks);
1996 bool Precedences(Tasks* tasks);
1999 bool MirrorTasks(Tasks* tasks);
2001 bool EdgeFinding(Tasks* tasks);
2004 bool DetectablePrecedencesWithChain(Tasks* tasks);
2006 bool ForbiddenIntervals(Tasks* tasks);
2008 bool DistanceDuration(Tasks* tasks);
2011 bool ChainSpanMin(Tasks* tasks);
2016 bool ChainSpanMinDynamic(Tasks* tasks);
2023 std::vector<int> tasks_by_start_min_;
2024 std::vector<int> tasks_by_end_max_;
2025 std::vector<int> event_of_task_;
2026 std::vector<int> nonchain_tasks_by_start_max_;
2028 std::vector<int64> total_duration_before_;
2046 std::vector<int64>* values);
2066 return "GlobalVehicleBreaksConstraint";
2069 void Post()
override;
2070 void InitialPropagate()
override;
2073 void PropagateNode(
int node);
2074 void PropagateVehicle(
int vehicle);
2075 void PropagateMaxBreakDistance(
int vehicle);
2079 std::vector<Demon*> vehicle_demons_;
2080 std::vector<int64> path_;
2086 void FillPartialPathOfVehicle(
int vehicle);
2087 void FillPathTravels(
const std::vector<int64>& path);
2099 class TaskTranslator {
2103 before_start_(before_start),
2104 after_start_(after_start) {}
2109 if (start_ !=
nullptr) {
2111 }
else if (interval_ !=
nullptr) {
2112 interval_->SetStartMin(
value);
2116 if (start_ !=
nullptr) {
2118 }
else if (interval_ !=
nullptr) {
2119 interval_->SetStartMax(
value);
2123 if (interval_ !=
nullptr) {
2124 interval_->SetDurationMin(
value);
2128 if (start_ !=
nullptr) {
2130 }
else if (interval_ !=
nullptr) {
2131 interval_->SetEndMin(
value);
2135 if (start_ !=
nullptr) {
2137 }
else if (interval_ !=
nullptr) {
2138 interval_->SetEndMax(
value);
2143 IntVar* start_ =
nullptr;
2144 int64 before_start_;
2146 IntervalVar* interval_ =
nullptr;
2150 std::vector<TaskTranslator> task_translators_;
2153 DisjunctivePropagator disjunctive_propagator_;
2154 DisjunctivePropagator::Tasks tasks_;
2157 TravelBounds travel_bounds_;
2165 bool CheckVehicle(
int vehicle,
2166 const std::function<
int64(
int64)>& next_accessor);
2177 int num_type_added_to_vehicle = 0;
2183 int num_type_removed_from_vehicle = 0;
2188 int position_of_last_type_on_vehicle_up_to_visit = -1;
2195 bool TypeOccursOnRoute(
int type)
const;
2202 bool TypeCurrentlyOnRoute(
int type,
int pos)
const;
2204 void InitializeCheck(
int vehicle,
2205 const std::function<
int64(
int64)>& next_accessor);
2215 std::vector<TypePolicyOccurrence> occurrences_of_type_;
2216 std::vector<int64> current_route_visits_;
2223 bool check_hard_incompatibilities);
2227 bool HasRegulationsToCheck()
const override;
2228 bool CheckTypeRegulations(
int type, VisitTypePolicy policy,
int pos)
override;
2232 bool check_hard_incompatibilities_;
2243 bool HasRegulationsToCheck()
const override;
2244 void OnInitializeCheck()
override {
2245 types_with_same_vehicle_requirements_on_route_.clear();
2250 bool CheckRequiredTypesCurrentlyOnRoute(
2251 const std::vector<absl::flat_hash_set<int> >& required_type_alternatives,
2254 bool CheckTypeRegulations(
int type, VisitTypePolicy policy,
int pos)
override;
2255 bool FinalizeCheck()
const override;
2257 absl::flat_hash_set<int> types_with_same_vehicle_requirements_on_route_;
2304 void Post()
override;
2305 void InitialPropagate()
override;
2308 void PropagateNodeRegulations(
int node);
2309 void CheckRegulationsOnVehicle(
int vehicle);
2314 std::vector<Demon*> vehicle_demons_;
2336 : bound_costs_(num_bounds, default_bound_cost) {}
2339 int Size() {
return bound_costs_.size(); }
2344 std::vector<BoundCost> bound_costs_;
2380 int64 vehicle_class)
const {
2381 return model_->TransitCallback(class_evaluators_[vehicle_class])(from_index,
2391 #if !defined(SWIGPYTHON)
2396 const std::vector<IntVar*>&
transits()
const {
return transits_; }
2397 const std::vector<IntVar*>&
slacks()
const {
return slacks_; }
2398 #if !defined(SWIGCSHARP) && !defined(SWIGJAVA)
2401 return forbidden_intervals_;
2406 int64 max_value)
const;
2410 int64 min_value)
const {
2413 forbidden_intervals_[
index];
2414 const auto first_forbidden_interval_it =
2416 if (first_forbidden_interval_it != forbidden_intervals.
end() &&
2417 min_value >= first_forbidden_interval_it->start) {
2419 return CapAdd(first_forbidden_interval_it->end, 1);
2429 int64 max_value)
const {
2432 forbidden_intervals_[
index];
2433 const auto last_forbidden_interval_it =
2435 if (last_forbidden_interval_it != forbidden_intervals.
end() &&
2436 max_value <= last_forbidden_interval_it->end) {
2438 return CapSub(last_forbidden_interval_it->start, 1);
2445 return vehicle_capacities_;
2450 return model_->TransitCallback(
2451 class_evaluators_[vehicle_to_class_[vehicle]]);
2457 int vehicle)
const {
2458 return model_->UnaryTransitCallbackOrNull(
2459 class_evaluators_[vehicle_to_class_[vehicle]]);
2464 return model()->is_transit_evaluator_positive_
2465 [class_evaluators_[vehicle_to_class_[vehicle]]];
2473 void SetSpanUpperBoundForVehicle(
int64 upper_bound,
int vehicle);
2495 void SetCumulVarPiecewiseLinearCost(
int64 index,
2499 bool HasCumulVarPiecewiseLinearCost(
int64 index)
const;
2518 bool HasCumulVarSoftUpperBound(
int64 index)
const;
2541 bool HasCumulVarSoftLowerBound(
int64 index)
const;
2566 #if !defined(SWIGPYTHON)
2567 void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks,
int vehicle,
2568 int pre_travel_evaluator,
2569 int post_travel_evaluator);
2573 void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks,
int vehicle,
2574 std::vector<int64> node_visit_transits);
2580 void SetBreakDistanceDurationOfVehicle(
int64 distance,
int64 duration,
2584 void InitializeBreaks();
2586 bool HasBreakConstraints()
const;
2587 #if !defined(SWIGPYTHON)
2590 void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks,
int vehicle,
2591 std::vector<int64> node_visit_transits,
2595 const std::vector<IntervalVar*>& GetBreakIntervalsOfVehicle(
2600 const std::vector<std::pair<int64, int64> >&
2601 GetBreakDistanceDurationOfVehicle(
int vehicle)
const;
2604 int GetPreTravelEvaluatorOfVehicle(
int vehicle)
const;
2605 int GetPostTravelEvaluatorOfVehicle(
int vehicle)
const;
2616 int64 ShortestTransitionSlack(
int64 node)
const;
2619 const std::string&
name()
const {
return name_; }
2624 return path_precedence_graph_;
2639 void SetPickupToDeliveryLimitFunctionForPair(
2642 bool HasPickupToDeliveryLimits()
const;
2644 int64 GetPickupToDeliveryLimitForPair(
int pair_index,
int pickup,
2645 int delivery)
const;
2654 node_precedences_.push_back(precedence);
2657 return node_precedences_;
2662 AddNodePrecedence({first_node, second_node, offset});
2666 return vehicle_span_upper_bounds_[vehicle];
2670 return vehicle_span_upper_bounds_;
2674 return vehicle_span_cost_coefficients_[vehicle];
2678 return vehicle_span_cost_coefficients_;
2682 return global_span_cost_coefficient_;
2687 return global_optimizer_offset_;
2690 if (vehicle >= local_optimizer_offset_for_vehicle_.size()) {
2693 DCHECK_GE(local_optimizer_offset_for_vehicle_[vehicle], 0);
2694 return local_optimizer_offset_for_vehicle_[vehicle];
2701 if (!HasSoftSpanUpperBounds()) {
2702 vehicle_soft_span_upper_bound_ = absl::make_unique<SimpleBoundCosts>(
2705 vehicle_soft_span_upper_bound_->bound_cost(vehicle) = bound_cost;
2708 return vehicle_soft_span_upper_bound_ !=
nullptr;
2711 int vehicle)
const {
2712 DCHECK(HasSoftSpanUpperBounds());
2713 return vehicle_soft_span_upper_bound_->bound_cost(vehicle);
2719 if (!HasQuadraticCostSoftSpanUpperBounds()) {
2720 vehicle_quadratic_cost_soft_span_upper_bound_ =
2721 absl::make_unique<SimpleBoundCosts>(
2724 vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle) =
2728 return vehicle_quadratic_cost_soft_span_upper_bound_ !=
nullptr;
2731 int vehicle)
const {
2732 DCHECK(HasQuadraticCostSoftSpanUpperBounds());
2733 return vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle);
2744 struct PiecewiseLinearCost {
2745 PiecewiseLinearCost() :
var(nullptr),
cost(nullptr) {}
2747 std::unique_ptr<PiecewiseLinearFunction>
cost;
2751 RoutingDimension(RoutingModel*
model, std::vector<int64> vehicle_capacities,
2752 const std::string&
name,
2753 const RoutingDimension* base_dimension);
2754 RoutingDimension(RoutingModel*
model, std::vector<int64> vehicle_capacities,
2755 const std::string&
name, SelfBased);
2756 void Initialize(
const std::vector<int>& transit_evaluators,
2757 const std::vector<int>& state_dependent_transit_evaluators,
2759 void InitializeCumuls();
2760 void InitializeTransits(
2761 const std::vector<int>& transit_evaluators,
2762 const std::vector<int>& state_dependent_transit_evaluators,
2764 void InitializeTransitVariables(
int64 slack_max);
2766 void SetupCumulVarSoftUpperBoundCosts(
2767 std::vector<IntVar*>* cost_elements)
const;
2769 void SetupCumulVarSoftLowerBoundCosts(
2770 std::vector<IntVar*>* cost_elements)
const;
2771 void SetupCumulVarPiecewiseLinearCosts(
2772 std::vector<IntVar*>* cost_elements)
const;
2775 void SetupGlobalSpanCost(std::vector<IntVar*>* cost_elements)
const;
2776 void SetupSlackAndDependentTransitCosts()
const;
2778 void CloseModel(
bool use_light_propagation);
2780 void SetOffsetForGlobalOptimizer(
int64 offset) {
2784 void SetVehicleOffsetsForLocalOptimizer(std::vector<int64> offsets) {
2786 std::transform(offsets.begin(), offsets.end(), offsets.begin(),
2787 [](
int64 offset) { return std::max(Zero(), offset); });
2788 local_optimizer_offset_for_vehicle_ = std::move(offsets);
2792 std::vector<SortedDisjointIntervalList> forbidden_intervals_;
2793 std::vector<IntVar*> capacity_vars_;
2794 const std::vector<int64> vehicle_capacities_;
2795 std::vector<IntVar*> transits_;
2796 std::vector<IntVar*> fixed_transits_;
2799 std::vector<int> class_evaluators_;
2800 std::vector<int64> vehicle_to_class_;
2802 ReverseArcListGraph<int, int> path_precedence_graph_;
2808 std::vector<NodePrecedence> node_precedences_;
2813 const RoutingDimension*
const base_dimension_;
2818 std::vector<int> state_dependent_class_evaluators_;
2819 std::vector<int64> state_dependent_vehicle_to_class_;
2824 std::vector<PickupToDeliveryLimitFunction>
2825 pickup_to_delivery_limits_per_pair_index_;
2828 bool break_constraints_are_initialized_ =
false;
2830 std::vector<std::vector<IntervalVar*> > vehicle_break_intervals_;
2831 std::vector<std::vector<std::pair<int64, int64> > >
2832 vehicle_break_distance_duration_;
2837 std::vector<int> vehicle_pre_travel_evaluators_;
2838 std::vector<int> vehicle_post_travel_evaluators_;
2840 std::vector<IntVar*> slacks_;
2841 std::vector<IntVar*> dependent_transits_;
2842 std::vector<int64> vehicle_span_upper_bounds_;
2843 int64 global_span_cost_coefficient_;
2844 std::vector<int64> vehicle_span_cost_coefficients_;
2845 std::vector<SoftBound> cumul_var_soft_upper_bound_;
2846 std::vector<SoftBound> cumul_var_soft_lower_bound_;
2847 std::vector<PiecewiseLinearCost> cumul_var_piecewise_linear_cost_;
2848 RoutingModel*
const model_;
2849 const std::string name_;
2850 int64 global_optimizer_offset_;
2851 std::vector<int64> local_optimizer_offset_for_vehicle_;
2853 std::unique_ptr<SimpleBoundCosts> vehicle_soft_span_upper_bound_;
2854 std::unique_ptr<SimpleBoundCosts>
2855 vehicle_quadratic_cost_soft_span_upper_bound_;
2859 const std::vector<RoutingDimension*>& dimensions,
2860 const RoutingSearchParameters&
parameters,
bool filter_objective_cost,
2861 std::vector<LocalSearchFilterManager::FilterEvent>* filters);
2871 explicit SweepArranger(
const std::vector<std::pair<int64, int64>>& points);
2873 void ArrangeIndices(std::vector<int64>* indices);
2877 std::vector<int> coordinates_;
2887 std::vector<IntVar*> variables,
2888 std::vector<int64> targets);
2898 : vehicle_type_container_(&vehicle_type_container) {}
2900 int NumTypes()
const {
return vehicle_type_container_->NumTypes(); }
2902 int Type(
int vehicle)
const {
return vehicle_type_container_->Type(vehicle); }
2906 void Reset(
const std::function<
bool(
int)>& store_vehicle);
2910 void Update(
const std::function<
bool(
int)>& remove_vehicle);
2914 const std::set<VehicleClassEntry>& vehicle_classes =
2915 sorted_vehicle_classes_per_type_[type];
2916 if (vehicle_classes.empty()) {
2919 const int vehicle_class = (vehicle_classes.begin())->vehicle_class;
2920 DCHECK(!vehicles_per_vehicle_class_[vehicle_class].empty());
2921 return vehicles_per_vehicle_class_[vehicle_class][0];
2926 std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
2927 if (vehicles.empty()) {
2930 std::set<VehicleClassEntry>& vehicle_classes =
2931 sorted_vehicle_classes_per_type_[Type(vehicle)];
2932 const auto& insertion =
2933 vehicle_classes.insert({vehicle_class, fixed_cost});
2934 DCHECK(insertion.second);
2936 vehicles.push_back(vehicle);
2947 std::pair<int, int> GetCompatibleVehicleOfType(
2948 int type, std::function<
bool(
int)> vehicle_is_compatible,
2949 std::function<
bool(
int)> stop_and_return_vehicle);
2952 using VehicleClassEntry =
2956 std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;
2957 std::vector<std::vector<int> > vehicles_per_vehicle_class_;
2980 std::unique_ptr<IntVarFilteredHeuristic> heuristic);
2986 std::string DebugString()
const override;
2989 int64 number_of_decisions()
const;
2990 int64 number_of_rejects()
const;
2993 const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;
3013 virtual std::string
DebugString()
const {
return "IntVarFilteredHeuristic"; }
3017 void ResetSolution();
3031 if (!is_in_delta_[
index]) {
3033 delta_indices_.push_back(
index);
3034 is_in_delta_[
index] =
true;
3042 return assignment_->IntVarContainer().Element(
index).Value();
3046 return assignment_->IntVarContainer().Element(
index).Var() !=
nullptr;
3054 void SynchronizeFilters();
3061 bool FilterAccept();
3064 const std::vector<IntVar*>
vars_;
3066 std::vector<int> delta_indices_;
3067 std::vector<bool> is_in_delta_;
3071 int64 number_of_decisions_;
3072 int64 number_of_rejects_;
3083 const std::function<
int64(
int64)>& next_accessor);
3091 void MakeDisjunctionNodesUnperformed(
int64 node);
3093 void MakeUnassignedNodesUnperformed();
3098 void MakePartiallyPerformedPairsUnperformed();
3110 bool InitializeSolution()
override;
3113 std::vector<int64> start_chain_ends_;
3114 std::vector<int64> end_chain_starts_;
3122 std::function<
int64(
int64)> penalty_evaluator,
3133 return std::tie(distance, vehicle) <
3145 std::vector<std::vector<StartEndValue> >
3146 ComputeStartEndDistanceForVehicles(
const std::vector<int>& vehicles);
3152 template <
class Queue>
3154 std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
3155 Queue* priority_queue);
3167 void AppendEvaluatedPositionsAfter(
3169 std::vector<ValuedPosition>* valued_positions);
3176 int64 GetInsertionCostForNodeAtPosition(
int64 node_to_insert,
3178 int64 insert_before,
3182 int64 GetUnperformedValue(
int64 node_to_insert)
const;
3225 std::function<
int64(
int64)> penalty_evaluator,
3229 bool BuildSolutionInternal()
override;
3231 return "GlobalCheapestInsertionFilteredHeuristic";
3237 typedef absl::flat_hash_set<PairEntry*> PairEntries;
3238 typedef absl::flat_hash_set<NodeEntry*> NodeEntries;
3246 void InsertPairsAndNodesByRequirementTopologicalOrder();
3254 void InsertPairs(
const std::vector<int>& pair_indices);
3262 bool InsertPairEntryUsingEmptyVehicleTypeCurator(
3263 const std::vector<int>& pair_indices, PairEntry*
const pair_entry,
3265 std::vector<PairEntries>* pickup_to_entries,
3266 std::vector<PairEntries>* delivery_to_entries);
3275 void InsertNodesOnRoutes(
const std::vector<int>& nodes,
3276 const absl::flat_hash_set<int>& vehicles);
3285 bool InsertNodeEntryUsingEmptyVehicleTypeCurator(
3286 const std::vector<int>& nodes,
bool all_vehicles,
3287 NodeEntry*
const node_entry,
3289 std::vector<NodeEntries>* position_to_node_entries);
3296 void SequentialInsertNodes(
const std::vector<int>& nodes);
3301 void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,
3302 std::vector<int>* unused_vehicles,
3303 absl::flat_hash_set<int>* used_vehicles);
3308 void InsertFarthestNodesAsSeeds();
3318 template <
class Queue>
3320 std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3321 Queue* priority_queue, std::vector<bool>* is_vehicle_used);
3326 void InitializePairPositions(
3327 const std::vector<int>& pair_indices,
3329 std::vector<PairEntries>* pickup_to_entries,
3330 std::vector<PairEntries>* delivery_to_entries);
3336 void InitializeInsertionEntriesPerformingPair(
3339 std::vector<PairEntries>* pickup_to_entries,
3340 std::vector<PairEntries>* delivery_to_entries);
3344 void UpdateAfterPairInsertion(
3345 const std::vector<int>& pair_indices,
int vehicle,
int64 pickup,
3348 std::vector<PairEntries>* pickup_to_entries,
3349 std::vector<PairEntries>* delivery_to_entries);
3352 void UpdatePairPositions(
const std::vector<int>& pair_indices,
int vehicle,
3355 std::vector<PairEntries>* pickup_to_entries,
3356 std::vector<PairEntries>* delivery_to_entries) {
3357 UpdatePickupPositions(pair_indices, vehicle, insert_after, priority_queue,
3358 pickup_to_entries, delivery_to_entries);
3359 UpdateDeliveryPositions(pair_indices, vehicle, insert_after, priority_queue,
3360 pickup_to_entries, delivery_to_entries);
3364 void UpdatePickupPositions(
const std::vector<int>& pair_indices,
int vehicle,
3365 int64 pickup_insert_after,
3367 std::vector<PairEntries>* pickup_to_entries,
3368 std::vector<PairEntries>* delivery_to_entries);
3371 void UpdateDeliveryPositions(
3372 const std::vector<int>& pair_indices,
int vehicle,
3373 int64 delivery_insert_after,
3375 std::vector<PairEntries>* pickup_to_entries,
3376 std::vector<PairEntries>* delivery_to_entries);
3379 void DeletePairEntry(PairEntry* entry,
3381 std::vector<PairEntries>* pickup_to_entries,
3382 std::vector<PairEntries>* delivery_to_entries);
3387 void AddPairEntry(
int64 pickup,
int64 pickup_insert_after,
int64 delivery,
3388 int64 delivery_insert_after,
int vehicle,
3390 std::vector<PairEntries>* pickup_entries,
3391 std::vector<PairEntries>* delivery_entries)
const;
3394 void UpdatePairEntry(
3395 PairEntry*
const pair_entry,
3400 int64 GetInsertionValueForPairAtPositions(
int64 pickup,
3401 int64 pickup_insert_after,
3403 int64 delivery_insert_after,
3408 void InitializePositions(
const std::vector<int>& nodes,
3409 const absl::flat_hash_set<int>& vehicles,
3411 std::vector<NodeEntries>* position_to_node_entries);
3417 void InitializeInsertionEntriesPerformingNode(
3418 int64 node,
const absl::flat_hash_set<int>& vehicles,
3420 std::vector<NodeEntries>* position_to_node_entries);
3423 void UpdatePositions(
const std::vector<int>& nodes,
int vehicle,
3424 int64 insert_after,
bool all_vehicles,
3426 std::vector<NodeEntries>* node_entries);
3429 void DeleteNodeEntry(NodeEntry* entry,
3431 std::vector<NodeEntries>* node_entries);
3436 void AddNodeEntry(
int64 node,
int64 insert_after,
int vehicle,
3439 std::vector<NodeEntries>* node_entries)
const;
3442 void UpdateNodeEntry(
3443 NodeEntry*
const node_entry,
3448 void ComputeNeighborhoods();
3452 bool IsNeighborForCostClass(
int cost_class,
int64 node_index,
3453 int64 neighbor_index)
const;
3456 const std::vector<int64>& GetNeighborsOfNodeForCostClass(
3457 int cost_class,
int64 node_index)
const {
3458 return gci_params_.neighbors_ratio == 1
3460 : node_index_to_neighbors_by_cost_class_[node_index][cost_class]
3461 ->PositionsSetAtLeastOnce();
3464 int64 NumNonStartEndNodes()
const {
3465 return model()->Size() -
model()->vehicles();
3468 int64 NumNeighbors()
const {
3469 return std::max(gci_params_.min_neighbors,
3470 MathUtil::FastInt64Round(gci_params_.neighbors_ratio *
3471 NumNonStartEndNodes()));
3474 void ResetVehicleIndices()
override {
3475 node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);
3478 void SetVehicleIndex(
int64 node,
int vehicle)
override {
3479 DCHECK_LT(node, node_index_to_vehicle_.size());
3480 node_index_to_vehicle_[node] = vehicle;
3485 bool CheckVehicleIndices()
const;
3487 GlobalCheapestInsertionParameters gci_params_;
3489 std::vector<int> node_index_to_vehicle_;
3492 std::vector<std::vector<std::unique_ptr<SparseBitset<int64> > > >
3493 node_index_to_neighbors_by_cost_class_;
3496 std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;
3501 std::vector<int64> all_nodes_;
3517 bool BuildSolutionInternal()
override;
3519 return "LocalCheapestInsertionFilteredHeuristic";
3528 void ComputeEvaluatorSortedPositions(
int64 node,
3529 std::vector<int64>* sorted_positions);
3534 void ComputeEvaluatorSortedPositionsOnRouteAfter(
3536 std::vector<int64>* sorted_positions);
3538 std::vector<std::vector<StartEndValue>> start_end_distances_per_node_;
3548 bool BuildSolutionInternal()
override;
3551 class PartialRoutesAndLargeVehicleIndicesFirst {
3553 explicit PartialRoutesAndLargeVehicleIndicesFirst(
3555 : builder_(builder) {}
3556 bool operator()(
int vehicle1,
int vehicle2)
const;
3559 const CheapestAdditionFilteredHeuristic& builder_;
3562 template <
typename Iterator>
3563 std::vector<int64> GetPossibleNextsFromIterator(
int64 node, Iterator start,
3564 Iterator end)
const {
3565 const int size =
model()->Size();
3566 std::vector<int64> nexts;
3567 for (Iterator it = start; it != end; ++it) {
3569 if (
next != node && (
next >= size || !Contains(
next))) {
3570 nexts.push_back(
next);
3576 virtual void SortSuccessors(
int64 node, std::vector<int64>* successors) = 0;
3578 const std::vector<int64>& successors) = 0;
3592 return "EvaluatorCheapestAdditionFilteredHeuristic";
3597 void SortSuccessors(
int64 node, std::vector<int64>* successors)
override;
3599 const std::vector<int64>& successors)
override;
3615 return "ComparatorCheapestAdditionFilteredHeuristic";
3620 void SortSuccessors(
int64 node, std::vector<int64>* successors)
override;
3622 const std::vector<int64>& successors)
override;
3640 double neighbors_ratio = 1.0;
3643 double max_memory_usage_bytes = 6e9;
3646 bool add_reverse_arcs =
false;
3649 double arc_coefficient = 1.0;
3657 bool BuildSolutionInternal()
override;
3662 template <
typename S>
3671 return saving.second / size_squared_;
3675 return (saving.second % size_squared_) / Size();
3679 return (saving.second % size_squared_) % Size();
3693 int StartNewRouteWithBestVehicleOfType(
int type,
int64 before_node,
3707 void AddSymmetricArcsToAdjacencyLists(
3708 std::vector<std::vector<int64> >* adjacency_lists);
3717 void ComputeSavings();
3719 Saving BuildSaving(
int64 saving,
int vehicle_type,
int before_node,
3720 int after_node)
const {
3721 return std::make_pair(saving, vehicle_type * size_squared_ +
3722 before_node * Size() + after_node);
3728 int64 MaxNumNeighborsPerNode(
int num_vehicle_types)
const;
3731 const SavingsParameters savings_params_;
3732 int64 size_squared_;
3734 friend class SavingsFilteredHeuristicTestPeer;
3746 return "SequentialSavingsFilteredHeuristic";
3754 void BuildRoutesFromSavings()
override;
3755 double ExtraSavingsMemoryMultiplicativeFactor()
const override {
return 1.0; }
3767 return "ParallelSavingsFilteredHeuristic";
3781 void BuildRoutesFromSavings()
override;
3783 double ExtraSavingsMemoryMultiplicativeFactor()
const override {
return 2.0; }
3789 void MergeRoutes(
int first_vehicle,
int second_vehicle,
int64 before_node,
3793 std::vector<int64> first_node_on_route_;
3794 std::vector<int64> last_node_on_route_;
3798 std::vector<int> vehicle_of_first_or_last_node_;
3809 bool use_minimum_matching);
3811 bool BuildSolutionInternal()
override;
3813 return "ChristofidesFilteredHeuristic";
3817 const bool use_minimum_matching_;
3826 const RoutingSearchParameters& search_parameters,
3827 const Assignment* initial_solution,
3828 Assignment* solution);
3834 BasePathFilter(
const std::vector<IntVar*>& nexts,
int next_domain_size);
3837 int64 objective_min,
int64 objective_max)
override;
3854 return touched_paths_.PositionsSetAtLeastOnce();
3857 return new_synchronized_unperformed_nodes_.PositionsSetAtLeastOnce();
3861 enum Status { UNKNOWN, ENABLED, DISABLED };
3863 virtual bool DisableFiltering()
const {
return false; }
3864 virtual void OnBeforeSynchronizePaths() {}
3865 virtual void OnAfterSynchronizePaths() {}
3866 virtual void OnSynchronizePathFromStart(
int64 start) {}
3867 virtual void InitializeAcceptPath() {}
3868 virtual bool AcceptPath(
int64 path_start,
int64 chain_start,
3869 int64 chain_end) = 0;
3870 virtual bool FinalizeAcceptPath(
const Assignment*
delta,
int64 objective_min,
3871 int64 objective_max) {
3875 void ComputePathStarts(std::vector<int64>* path_starts,
3876 std::vector<int>* index_to_path);
3877 bool HavePathsChanged();
3878 void SynchronizeFullAssignment();
3879 void UpdateAllRanks();
3880 void UpdatePathRanksFromStart(
int start);
3882 std::vector<int64> node_path_starts_;
3883 std::vector<int64> starts_;
3884 std::vector<int> paths_;
3885 SparseBitset<int64> new_synchronized_unperformed_nodes_;
3886 std::vector<int64> new_nexts_;
3887 std::vector<int> delta_touched_;
3888 SparseBitset<> touched_paths_;
3890 std::vector<std::pair<int64, int64> > touched_path_chain_start_ends_;
3892 std::vector<int> ranks_;
3912 std::string
DebugString()
const override {
return "CPFeasibilityFilter"; }
3914 int64 objective_min,
int64 objective_max)
override;
3931 const RoutingModel& routing_model);
3933 const RoutingModel& routing_model);
3935 const RoutingModel& routing_model);
3937 const RoutingModel& routing_model);
3939 const std::vector<RoutingDimension*>& dimensions,
3940 const RoutingSearchParameters&
parameters,
bool filter_objective_cost,
3941 std::vector<LocalSearchFilterManager::FilterEvent>* filters);
3943 const PathState* path_state,
3944 const std::vector<RoutingDimension*>& dimensions,
3945 std::vector<LocalSearchFilterManager::FilterEvent>* filters);
3947 const RoutingDimension& dimension,
3949 bool propagate_own_objective_value,
bool filter_objective_cost,
3950 bool can_use_lp =
true);
3952 const RoutingDimension& dimension);
3954 GlobalDimensionCumulOptimizer* optimizer,
bool filter_objective_cost);
3956 const RoutingModel& routing_model,
const RoutingModel::IndexPairs& pairs,
3957 const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies);
3959 const RoutingModel& routing_model);
3961 const RoutingModel& routing_model,
const RoutingDimension& dimension);
const std::vector< IntVar * > vars_
#define CHECK_LT(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
An Assignment is a variable -> domains mapping, used to report solutions to the user.
A BaseObject is the root of all reversibly allocated objects.
Generic path-based filter class.
const std::vector< int64 > & GetTouchedPathStarts() const
static const int64 kUnassigned
const std::vector< int64 > & GetNewSynchronizedUnperformedNodes() const
~BasePathFilter() override
int Rank(int64 node) const
int64 GetNext(int64 node) const
int GetPath(int64 node) const
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
std::string DebugString() const override
~CPFeasibilityFilter() override
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
~CheapestAdditionFilteredHeuristic() override
std::function< int64(int64)> penalty_evaluator_
std::function< int64(int64, int64, int64)> evaluator_
void InitializePriorityQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, Queue *priority_queue)
Initializes the priority_queue by inserting the best entry corresponding to each node,...
std::pair< int64, int64 > ValuedPosition
~CheapestInsertionFilteredHeuristic() override
std::pair< StartEndValue, int > Seed
Christofides addition heuristic.
~ChristofidesFilteredHeuristic() override
std::string DebugString() const override
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc comparator.
~ComparatorCheapestAdditionFilteredHeuristic() override
std::string DebugString() const override
A constraint is the main modeling object.
A DecisionBuilder is responsible for creating the search tree.
A Decision represents a choice point in the search tree.
This class acts like a CP propagator: it takes a set of tasks given by their start/duration/end featu...
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc evaluator.
~EvaluatorCheapestAdditionFilteredHeuristic() override
std::string DebugString() const override
Filter-based decision builder which builds a solution by inserting nodes at their cheapest position o...
~GlobalCheapestInsertionFilteredHeuristic() override
std::string DebugString() const override
GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimensio...
std::string DebugString() const override
Decision builder building a solution using heuristics with local search filters to evaluate its feasi...
~IntVarFilteredDecisionBuilder() override
Generic filter-based heuristic applied to IntVars.
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
int Size() const
Returns the number of variables the decision builder is trying to instantiate.
bool Contains(int64 index) const
Returns true if the variable of index 'index' is in the current solution.
int64 Value(int64 index) const
Returns the value of the variable of index 'index' in the last committed solution.
virtual ~IntVarFilteredHeuristic()
IntVar * Var(int64 index) const
Returns the variable of index 'index'.
virtual bool StopSearch()
Returns true if the search must be stopped.
Assignment *const assignment_
virtual std::string DebugString() const
virtual bool InitializeSolution()
Virtual method to initialize the solution.
int64 number_of_rejects() const
int64 number_of_decisions() const
Returns statistics on search, number of decisions sent to filters, number of decisions rejected by fi...
void SetValue(int64 index, int64 value)
Modifies the current solution by setting the variable of index 'index' to value 'value'.
The class IntVar is a subset of IntExpr.
Interval variables are often used in scheduling.
Filter-base decision builder which builds a solution by inserting nodes at their cheapest position.
~LocalCheapestInsertionFilteredHeuristic() override
std::string DebugString() const override
Local Search Filters are used for fast neighbor pruning.
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
The base class for all local search operators.
ParallelSavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
~ParallelSavingsFilteredHeuristic() override
std::string DebugString() const override
Dimensions represent quantities accumulated at nodes along the routes.
void SetQuadraticCostSoftSpanUpperBoundForVehicle(SimpleBoundCosts::BoundCost bound_cost, int vehicle)
If the span of vehicle on this dimension is larger than bound, the cost will be increased by cost * (...
SimpleBoundCosts::BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const
void AddNodePrecedence(int64 first_node, int64 second_node, int64 offset)
int64 GetTransitValueFromClass(int64 from_index, int64 to_index, int64 vehicle_class) const
Same as above but taking a vehicle class of the dimension instead of a vehicle (the class of a vehicl...
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
int64 global_span_cost_coefficient() const
int64 GetSpanCostCoefficientForVehicle(int vehicle) const
void SetSoftSpanUpperBoundForVehicle(SimpleBoundCosts::BoundCost bound_cost, int vehicle)
If the span of vehicle on this dimension is larger than bound, the cost will be increased by cost * (...
RoutingModel * model() const
Returns the model on which the dimension was created.
int64 GetGlobalOptimizerOffset() const
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
const RoutingModel::TransitCallback1 & GetUnaryTransitEvaluator(int vehicle) const
Returns the unary callback evaluating the transit value between two node indices for a given vehicle.
IntVar * FixedTransitVar(int64 index) const
const std::vector< int64 > & vehicle_capacities() const
Returns the capacities for all vehicles.
std::function< int64(int, int)> PickupToDeliveryLimitFunction
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery a...
bool AreVehicleTransitsPositive(int vehicle) const
Returns true iff the transit evaluator of 'vehicle' is positive for all arcs.
const std::vector< IntVar * > & fixed_transits() const
const std::vector< IntVar * > & transits() const
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
void AddNodePrecedence(NodePrecedence precedence)
int64 GetLocalOptimizerOffsetForVehicle(int vehicle) const
const std::vector< int64 > & vehicle_span_upper_bounds() const
bool HasQuadraticCostSoftSpanUpperBounds() const
int64 GetFirstPossibleGreaterOrEqualValueForNode(int64 index, int64 min_value) const
Returns the smallest value outside the forbidden intervals of node 'index' that is greater than or eq...
int vehicle_to_class(int vehicle) const
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
int64 GetLastPossibleLessOrEqualValueForNode(int64 index, int64 max_value) const
Returns the largest value outside the forbidden intervals of node 'index' that is less than or equal ...
IntVar * TransitVar(int64 index) const
IntVar * SlackVar(int64 index) const
const std::vector< int64 > & vehicle_span_cost_coefficients() const
const ReverseArcListGraph< int, int > & GetPathPrecedenceGraph() const
Accessors.
const std::string & name() const
Returns the name of the dimension.
const std::vector< IntVar * > & slacks() const
const std::vector< NodePrecedence > & GetNodePrecedences() const
bool HasSoftSpanUpperBounds() const
SimpleBoundCosts::BoundCost GetQuadraticCostSoftSpanUpperBoundForVehicle(int vehicle) const
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
int64 GetSpanUpperBoundForVehicle(int vehicle) const
Filter-based heuristic dedicated to routing.
~RoutingFilteredHeuristic() override
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
RoutingModel * model() const
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
virtual void SetVehicleIndex(int64 node, int vehicle)
bool StopSearch() override
Returns true if the search must be stopped.
virtual void ResetVehicleIndices()
bool VehicleIsEmpty(int vehicle) const
Manager for any NodeIndex <-> variable index conversion.
bool AddDimensionWithVehicleTransitAndCapacity(const std::vector< int > &evaluator_indices, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
std::pair< int, bool > AddConstantDimension(int64 value, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > & GetPickupAndDeliveryDisjunctions() const
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
std::pair< int, bool > AddConstantDimensionWithSlack(int64 value, int64 capacity, int64 slack_max, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'value'; 'capacity' is t...
std::function< std::vector< operations_research::IntVar * >(RoutingModel *)> GetTabuVarsCallback
Sets the callback returning the variable to use for the Tabu Search metaheuristic.
int nodes() const
Sizes and indices Returns the number of nodes in the model.
const std::vector< int > & GetSameVehicleIndicesOfIndex(int node) const
Returns variable indices of nodes constrained to be on the same route.
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
RoutingIndexPair IndexPair
IntVar * ActiveVehicleVar(int vehicle) const
Returns the active variable of the vehicle.
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
RoutingTransitCallback1 TransitCallback1
int GetNumberOfVisitTypes() const
const std::vector< std::vector< int > > & GetTopologicallySortedVisitTypes() const
void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(int64 index, int64 max_cardinality, F f) const
Calls f for each variable index of indices in the same disjunctions as the node corresponding to the ...
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
int64 Size() const
Returns the number of next variables in the model.
Assignment * MutablePreAssignment()
bool CheckLimit()
Returns true if the search limit has been crossed.
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulOptimizers() const
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
VisitTypePolicy
Set the node visit types and incompatibilities/requirements between the types (see below).
@ TYPE_ADDED_TO_VEHICLE
When visited, the number of types 'T' on the vehicle increases by one.
@ ADDED_TYPE_REMOVED_FROM_VEHICLE
When visited, one instance of type 'T' previously added to the route (TYPE_ADDED_TO_VEHICLE),...
@ TYPE_ON_VEHICLE_UP_TO_VISIT
With the following policy, the visit enforces that type 'T' is considered on the route from its start...
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension with transits depending on the cumuls of another dimension.
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
Creates a cached StateDependentTransit from an std::function.
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
For every vehicle of the routing model:
LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer(const RoutingDimension &dimension) const
void AddLocalSearchFilter(LocalSearchFilter *filter)
Adds a custom local search filter to the list of filters used to speed up local search by pruning unf...
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
bool HasTemporalTypeRequirements() const
Solver * solver() const
Returns the underlying constraint solver.
RoutingTransitCallback2 TransitCallback2
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
const Solver::IndexEvaluator2 & first_solution_evaluator() const
Gets/sets the evaluator used during the search.
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
std::function< StateDependentTransit(int64, int64)> VariableIndexEvaluator2
Status
Status of the search.
@ ROUTING_SUCCESS
Problem solved successfully after calling RoutingModel::Solve().
@ ROUTING_FAIL
No solution found to the problem after calling RoutingModel::Solve().
@ ROUTING_NOT_SOLVED
Problem not solved yet (before calling RoutingModel::Solve()).
@ ROUTING_INVALID
Model, model parameters or flags are not valid.
@ ROUTING_FAIL_TIMEOUT
Time limit reached before finding a solution with RoutingModel::Solve().
bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const
Returns true iff the model contains a vehicle with the given cost_class_index.
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
void SetSweepArranger(SweepArranger *sweep_arranger)
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
RoutingIndexPairs IndexPairs
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
IntVar * VehicleCostsConsideredVar(int vehicle) const
Returns the variable specifying whether or not costs are considered for vehicle.
void ConsiderEmptyRouteCostsForVehicle(bool consider_costs, int vehicle)
int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback)
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
void SetMaximumNumberOfActiveVehicles(int max_active_vehicles)
Constrains the maximum number of active vehicles, aka the number of vehicles which do not have an emp...
const IndexPairs & GetImplicitUniquePickupAndDeliveryPairs() const
Returns implicit pickup and delivery pairs currently in the model.
std::pair< int, bool > AddVectorDimension(std::vector< int64 > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i]' for node i; ...
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
int RegisterTransitCallback(TransitCallback2 callback)
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulMPOptimizers() const
int GetMaximumNumberOfActiveVehicles() const
Returns the maximum number of active vehicles.
RoutingDimensionIndex DimensionIndex
std::pair< int, bool > AddMatrixDimension(std::vector< std::vector< int64 > > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i][next(i)]' for...
DisjunctionIndex AddDisjunction(const std::vector< int64 > &indices, int64 penalty=kNoPenalty, int64 max_cardinality=1)
Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active.
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
bool HasHardTypeIncompatibilities() const
Returns true iff any hard (resp.
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
const std::vector< int64 > & GetAmortizedLinearCostFactorOfVehicles() const
int64 GetHomogeneousCost(int64 from_index, int64 to_index) const
Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns t...
int RegisterPositiveTransitCallback(TransitCallback2 callback)
PickupAndDeliveryPolicy
Types of precedence policy applied to pickup and delivery pairs.
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
int vehicles() const
Returns the number of vehicle routes in the model.
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
const std::vector< int64 > & GetAmortizedQuadraticCostFactorOfVehicles() const
int VehicleIndex(int64 index) const
Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/en...
bool HasTypeRegulations() const
Returns true iff the model has any incompatibilities or requirements set on node types.
void SetFirstSolutionEvaluator(Solver::IndexEvaluator2 evaluator)
Takes ownership of evaluator.
RoutingVehicleClassIndex VehicleClassIndex
int RegisterUnaryTransitVector(std::vector< int64 > values)
Registers 'callback' and returns its index.
bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
int GetNonZeroCostClassesCount() const
Ditto, minus the 'always zero', built-in cost class.
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
bool HasSameVehicleTypeRequirements() const
Returns true iff any same-route (resp.
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
void SetPrimaryConstrainedDimension(const std::string &dimension_name)
Set the given dimension as "primary constrained".
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
int RegisterTransitMatrix(std::vector< std::vector< int64 > > values)
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int RegisterUnaryTransitCallback(TransitCallback1 callback)
int64 Start(int vehicle) const
Model inspection.
RoutingCostClassIndex CostClassIndex
bool HasTemporalTypeIncompatibilities() const
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
const TransitCallback2 & TransitCallback(int callback_index) const
const std::vector< std::unique_ptr< GlobalDimensionCumulOptimizer > > & GetGlobalDimensionCumulOptimizers() const
Returns [global|local]_dimension_optimizers_, which are empty if the model has not been closed.
operations_research::FirstSolutionStrategy::Value GetAutomaticFirstSolutionStrategy() const
Returns the automatic first solution strategy selected.
absl::Duration RemainingTime() const
Returns the time left in the search limit.
Status status() const
Returns the current status of the routing model.
const std::vector< int64 > & GetDisjunctionIndices(DisjunctionIndex index) const
Returns the variable indices of the nodes in the disjunction of index 'index'.
static const DimensionIndex kNoDimension
Constant used to express the "no dimension" index, returned when a dimension name does not correspond...
const Assignment *const PreAssignment() const
Returns an assignment used to fix some of the variables of the problem.
bool CostsAreHomogeneousAcrossVehicles() const
Whether costs are homogeneous across all vehicles.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
const VehicleTypeContainer & GetVehicleTypeContainer() const
static const DisjunctionIndex kNoDisjunction
Constant used to express the "no disjunction" index, returned when a node does not appear in any disj...
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
bool AreEmptyRouteCostsConsideredForVehicle(int vehicle) const
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
RoutingDisjunctionIndex DisjunctionIndex
IntVar * ActiveVar(int64 index) const
Returns the active variable of the node corresponding to index.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
std::pair< int64, int64 > Saving
int64 GetVehicleTypeFromSaving(const Saving &saving) const
Returns the cost class from a saving.
std::unique_ptr< SavingsContainer< Saving > > savings_container_
int64 GetSavingValue(const Saving &saving) const
Returns the saving value from a saving.
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int64 GetBeforeNodeFromSaving(const Saving &saving) const
Returns the "before node" from a saving.
int64 GetAfterNodeFromSaving(const Saving &saving) const
Returns the "after node" from a saving.
virtual void BuildRoutesFromSavings()=0
Base class of all search limits.
A search monitor is a simple set of callbacks to monitor all search events.
~SequentialSavingsFilteredHeuristic() override
SequentialSavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
std::string DebugString() const override
A structure meant to store soft bounds and associated violation constants.
BoundCost & bound_cost(int element)
SimpleBoundCosts(int num_bounds, BoundCost default_bound_cost)
BoundCost bound_cost(int element) const
SimpleBoundCosts(const SimpleBoundCosts &)=delete
SimpleBoundCosts operator=(const SimpleBoundCosts &)=delete
std::function< bool(int64, int64, int64)> VariableValueComparator
std::function< int64(int64, int64)> IndexEvaluator2
This class represents a sorted list of disjoint, closed intervals.
Iterator LastIntervalLessOrEqual(int64 value) const
ConstIterator end() const
Iterator FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
Class to arrange indices by by their distance and their angles from the depot.
void SetSectors(int sectors)
Checker for type incompatibilities.
~TypeIncompatibilityChecker() override
virtual bool HasRegulationsToCheck() const =0
virtual ~TypeRegulationsChecker()
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
virtual void OnInitializeCheck()
virtual bool FinalizeCheck() const
const RoutingModel & model_
The following constraint ensures that incompatibilities and requirements between types are respected.
Checker for type requirements.
~TypeRequirementChecker() override
TypeRequirementChecker(const RoutingModel &model)
Helper class that manages vehicles.
VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)
void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64 fixed_cost)
int Type(int vehicle) const
int GetLowestFixedCostVehicleOfType(int type) const
const std::vector< IntVar * > cumuls_
static const int64 kint64max
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
std::function< int64(const Model &)> Value(IntegerVariable v)
CpSolverResponse SolveWithParameters(const CpModelProto &model_proto, const SatParameters ¶ms)
Solves the given CpModelProto with the given parameters.
CpSolverResponse Solve(const CpModelProto &model_proto)
Solves the given CpModelProto and returns an instance of CpSolverResponse.
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
bool SolveModelWithSat(const RoutingModel &model, const RoutingSearchParameters &search_parameters, const Assignment *initial_solution, Assignment *solution)
Attempts to solve the model using the cp-sat solver.
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
std::pair< std::vector< int64 >, std::vector< int64 > > RoutingIndexPair
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters ¶meters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
int64 CapSub(int64 x, int64 y)
void AppendTasksFromPath(const std::vector< int64 > &path, const TravelBounds &travel_bounds, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
void FillTravelBoundsOfVehicle(int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
void AppendTasksFromIntervals(const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)
int64 CapAdd(int64 x, int64 y)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
std::function< int64(int64, int64)> RoutingTransitCallback2
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
std::function< int64(int64)> RoutingTransitCallback1
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
static const int kUnassigned
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
std::vector< RoutingIndexPair > RoutingIndexPairs
DecisionBuilder * MakeSetValuesFromTargets(Solver *solver, std::vector< IntVar * > variables, std::vector< int64 > targets)
A decision builder which tries to assign values to variables as close as possible to target values fi...
std::function< int64(int64, int64)> evaluator_
bool operator<(const StartEndValue &other) const
A structure to hold tasks described by their features.
std::vector< int64 > end_max
std::vector< int64 > start_min
std::vector< int64 > duration_min
std::vector< int64 > start_max
std::vector< const SortedDisjointIntervalList * > forbidden_intervals
std::vector< bool > is_preemptible
std::vector< int64 > duration_max
std::vector< std::pair< int64, int64 > > distance_duration
std::vector< int64 > end_min
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
double farthest_seeds_ratio
The ratio of routes on which to insert farthest nodes as seeds before starting the cheapest insertion...
bool use_neighbors_ratio_for_initialization
If true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion p...
bool add_unperformed_entries
If true, entries are created for making the nodes/pairs unperformed, and when the cost of making a no...
SUBTLE: The vehicle's fixed cost is skipped on purpose here, because we can afford to do so:
const RoutingDimension * dimension
int64 transit_evaluator_class
bool operator<(const DimensionCost &cost) const
CostClass(int evaluator_index)
int evaluator_index
Index of the arc cost evaluator, registered in the RoutingModel class.
static bool LessThan(const CostClass &a, const CostClass &b)
Comparator for STL containers and algorithms.
std::vector< DimensionCost > dimension_transit_evaluator_class_and_cost_coefficient
What follows is relevant for models with time/state dependent transits.
RangeIntToIntFunction * transit
RangeMinMaxIndexFunction * transit_plus_identity
f(x)
int64 fixed_cost
Contrarily to CostClass, here we need strict equivalence.
absl::StrongVector< DimensionIndex, int64 > dimension_capacities
absl::StrongVector< DimensionIndex, int64 > dimension_evaluator_classes
dimension_evaluators[d]->Run(from, to) is the transit value of arc from->to for a dimension d.
int start_equivalence_class
Vehicle start and end equivalence classes.
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_min
Bounds of cumul variables at start and end vehicle nodes.
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_min
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_max
int end_equivalence_class
uint64 unvisitable_nodes_fprint
Fingerprint of unvisitable non-start/end nodes.
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_max
CostClassIndex cost_class_index
The cost class of the vehicle.
bool operator<(const VehicleClassEntry &other) const
Struct used to sort and store vehicles by their type.
std::vector< int > type_index_of_vehicle
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
int Type(int vehicle) const
std::vector< std::deque< int > > vehicles_per_vehicle_class
std::vector< int64 > max_travels
std::vector< int64 > min_travels
std::vector< int64 > post_travels
std::vector< int64 > pre_travels