OR-Tools  8.2
routing.h
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
68 // TODO(user): Add a section on costs (vehicle arc costs, span costs,
69 // disjunctions costs).
70 //
156 
157 #ifndef OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
158 #define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
159 
160 #include <cstddef>
161 #include <deque>
162 #include <functional>
163 #include <memory>
164 #include <queue>
165 #include <string>
166 #include <utility>
167 #include <vector>
168 
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"
177 #include "ortools/base/hash.h"
178 #include "ortools/base/logging.h"
179 #include "ortools/base/macros.h"
180 #include "ortools/base/mathutil.h"
183 #include "ortools/constraint_solver/routing_enums.pb.h"
185 #include "ortools/constraint_solver/routing_parameters.pb.h"
187 #include "ortools/glop/lp_solver.h"
188 #include "ortools/glop/parameters.pb.h"
189 #include "ortools/graph/graph.h"
190 #include "ortools/lp_data/lp_data.h"
192 #include "ortools/sat/theta_tree.h"
195 
196 namespace operations_research {
197 
198 class GlobalDimensionCumulOptimizer;
199 class LocalDimensionCumulOptimizer;
200 class LocalSearchOperator;
201 #ifndef SWIG
202 class IntVarFilteredDecisionBuilder;
203 class IntVarFilteredHeuristic;
204 class IndexNeighborFinder;
205 #endif
206 class RoutingDimension;
207 #ifndef SWIG
209 class SweepArranger;
210 #endif
211 struct SweepIndex;
212 
214  public:
216  enum Status {
227  };
228 
237  };
238  typedef RoutingCostClassIndex CostClassIndex;
239  typedef RoutingDimensionIndex DimensionIndex;
240  typedef RoutingDisjunctionIndex DisjunctionIndex;
241  typedef RoutingVehicleClassIndex VehicleClassIndex;
244 
245 // TODO(user): Remove all SWIG guards by adding the @ignore in .i.
246 #if !defined(SWIG)
249 #endif // SWIG
250 
251 #if !defined(SWIG)
267  };
268  typedef std::function<StateDependentTransit(int64, int64)>
270 #endif // SWIG
271 
272 #if !defined(SWIG)
273  struct CostClass {
276 
291 
297  struct DimensionCost {
301  bool operator<(const DimensionCost& cost) const {
302  if (transit_evaluator_class != cost.transit_evaluator_class) {
303  return transit_evaluator_class < cost.transit_evaluator_class;
304  }
305  return cost_coefficient < cost.cost_coefficient;
306  }
307  };
308  std::vector<DimensionCost>
310 
313 
315  static bool LessThan(const CostClass& a, const CostClass& b) {
316  if (a.evaluator_index != b.evaluator_index) {
317  return a.evaluator_index < b.evaluator_index;
318  }
319  return a.dimension_transit_evaluator_class_and_cost_coefficient <
320  b.dimension_transit_evaluator_class_and_cost_coefficient;
321  }
322  };
323 
324  struct VehicleClass {
333  // TODO(user): Find equivalent start/end nodes wrt dimensions and
334  // callbacks.
349 
351  static bool LessThan(const VehicleClass& a, const VehicleClass& b);
352  };
353 #endif // defined(SWIG)
354 
362 
363  bool operator<(const VehicleClassEntry& other) const {
364  return std::tie(fixed_cost, vehicle_class) <
365  std::tie(other.fixed_cost, other.vehicle_class);
366  }
367  };
368 
369  int NumTypes() const { return sorted_vehicle_classes_per_type.size(); }
370 
371  int Type(int vehicle) const {
372  DCHECK_LT(vehicle, type_index_of_vehicle.size());
373  return type_index_of_vehicle[vehicle];
374  }
375 
376  std::vector<int> type_index_of_vehicle;
377  // clang-format off
378  std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type;
379  std::vector<std::deque<int> > vehicles_per_vehicle_class;
380  // clang-format on
381  };
382 
384  static const int64 kNoPenalty;
385 
389 
393 
397  explicit RoutingModel(const RoutingIndexManager& index_manager);
398  RoutingModel(const RoutingIndexManager& index_manager,
399  const RoutingModelParameters& parameters);
400  ~RoutingModel();
401 
403  int RegisterUnaryTransitVector(std::vector<int64> values);
406 
408  std::vector<std::vector<int64> /*needed_for_swig*/> values);
411 
413  const TransitCallback2& TransitCallback(int callback_index) const {
414  CHECK_LT(callback_index, transit_evaluators_.size());
415  return transit_evaluators_[callback_index];
416  }
417  const TransitCallback1& UnaryTransitCallbackOrNull(int callback_index) const {
418  CHECK_LT(callback_index, unary_transit_evaluators_.size());
419  return unary_transit_evaluators_[callback_index];
420  }
422  int callback_index) const {
423  CHECK_LT(callback_index, state_dependent_transit_evaluators_.size());
424  return state_dependent_transit_evaluators_[callback_index];
425  }
426 
428 
440 
449  bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity,
450  bool fix_start_cumul_to_zero, const std::string& name);
452  const std::vector<int>& evaluator_indices, int64 slack_max,
453  int64 capacity, bool fix_start_cumul_to_zero, const std::string& name);
454  bool AddDimensionWithVehicleCapacity(int evaluator_index, 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);
470  std::pair<int, bool> AddConstantDimensionWithSlack(
471  int64 value, int64 capacity, int64 slack_max,
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);
478  }
488  std::pair<int, bool> AddVectorDimension(std::vector<int64> values,
489  int64 capacity,
490  bool fix_start_cumul_to_zero,
491  const std::string& name);
501  std::pair<int, bool> AddMatrixDimension(
502  std::vector<std::vector<int64> /*needed_for_swig*/> values,
503  int64 capacity, bool fix_start_cumul_to_zero, const std::string& name);
511  const std::vector<int>& pure_transits,
512  const std::vector<int>& dependent_transits,
513  const RoutingDimension* base_dimension, int64 slack_max,
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);
519  }
520 
523  const std::vector<int>& transits, const RoutingDimension* base_dimension,
524  int64 slack_max, std::vector<int64> vehicle_capacities,
525  bool fix_start_cumul_to_zero, const std::string& name);
528  int transit, const RoutingDimension* base_dimension, int64 slack_max,
529  int64 vehicle_capacity, bool fix_start_cumul_to_zero,
530  const std::string& name);
532  int pure_transit, int dependent_transit,
533  const RoutingDimension* base_dimension, int64 slack_max,
534  int64 vehicle_capacity, bool fix_start_cumul_to_zero,
535  const std::string& name);
536 
539  const std::function<int64(int64)>& f, int64 domain_start,
540  int64 domain_end);
541 
552  std::vector<IntVar*> spans,
553  std::vector<IntVar*> total_slacks);
554 
556  // TODO(user): rename.
557  std::vector<std::string> GetAllDimensionNames() const;
559  const std::vector<RoutingDimension*>& GetDimensions() const {
560  return dimensions_.get();
561  }
563  std::vector<RoutingDimension*> GetDimensionsWithSoftOrSpanCosts() const;
564  // clang-format off
567  const std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer> >&
569  return global_dimension_optimizers_;
570  }
571  const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >&
573  return local_dimension_optimizers_;
574  }
575  const std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >&
577  return local_dimension_mp_optimizers_;
578  }
579  // clang-format on
580 
584  const RoutingDimension& dimension) const;
586  const RoutingDimension& dimension) const;
588  const RoutingDimension& dimension) const;
589 
591  bool HasDimension(const std::string& dimension_name) const;
594  const std::string& dimension_name) const;
598  const std::string& dimension_name) const;
603  void SetPrimaryConstrainedDimension(const std::string& dimension_name) {
604  DCHECK(dimension_name.empty() || HasDimension(dimension_name));
605  primary_constrained_dimension_ = dimension_name;
606  }
608  const std::string& GetPrimaryConstrainedDimension() const {
609  return primary_constrained_dimension_;
610  }
627  DisjunctionIndex AddDisjunction(const std::vector<int64>& indices,
628  int64 penalty = kNoPenalty,
629  int64 max_cardinality = 1);
631  const std::vector<DisjunctionIndex>& GetDisjunctionIndices(
632  int64 index) const {
633  return index_to_disjunctions_[index];
634  }
638  template <typename F>
640  int64 index, int64 max_cardinality, F f) const {
641  for (const DisjunctionIndex disjunction : GetDisjunctionIndices(index)) {
642  if (disjunctions_[disjunction].value.max_cardinality == max_cardinality) {
643  for (const int64 d_index : disjunctions_[disjunction].indices) {
644  f(d_index);
645  }
646  }
647  }
648  }
649 #if !defined(SWIGPYTHON)
652  const std::vector<int64>& GetDisjunctionIndices(
653  DisjunctionIndex index) const {
654  return disjunctions_[index].indices;
655  }
656 #endif // !defined(SWIGPYTHON)
658  int64 GetDisjunctionPenalty(DisjunctionIndex index) const {
659  return disjunctions_[index].value.penalty;
660  }
664  return disjunctions_[index].value.max_cardinality;
665  }
667  int GetNumberOfDisjunctions() const { return disjunctions_.size(); }
672  std::vector<std::pair<int64, int64>> GetPerfectBinaryDisjunctions() const;
678  void IgnoreDisjunctionsAlreadyForcedToZero();
679 
683  void AddSoftSameVehicleConstraint(const std::vector<int64>& indices,
684  int64 cost);
685 
690  void SetAllowedVehiclesForIndex(const std::vector<int>& vehicles,
691  int64 index);
692 
694  bool IsVehicleAllowedForIndex(int vehicle, int64 index) {
695  return allowed_vehicles_[index].empty() ||
696  allowed_vehicles_[index].find(vehicle) !=
697  allowed_vehicles_[index].end();
698  }
699 
714  // TODO(user): Remove this when model introspection detects linked nodes.
715  void AddPickupAndDelivery(int64 pickup, int64 delivery);
719  void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction,
720  DisjunctionIndex delivery_disjunction);
721  // clang-format off
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;
730  // clang-format on
731 
734  void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy);
735  void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy,
736  int vehicle);
737  PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(
738  int vehicle) const;
741 
742  int GetNumOfSingletonNodes() const;
743 
744 #ifndef SWIG
747  return pickup_delivery_pairs_;
748  }
749  const std::vector<std::pair<DisjunctionIndex, DisjunctionIndex>>&
751  return pickup_delivery_disjunctions_;
752  }
758  DCHECK(closed_);
759  return implicit_pickup_delivery_pairs_without_alternatives_;
760  }
761 #endif // SWIG
773  enum VisitTypePolicy {
788  TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED
789  };
790  // TODO(user): Support multiple visit types per node?
791  void SetVisitType(int64 index, int type, VisitTypePolicy type_policy);
792  int GetVisitType(int64 index) const;
793  const std::vector<int>& GetSingleNodesOfType(int type) const;
794  const std::vector<int>& GetPairIndicesOfType(int type) const;
795  VisitTypePolicy GetVisitTypePolicy(int64 index) const;
798  // TODO(user): Reconsider the logic and potentially remove the need to
800  void CloseVisitTypes();
801  int GetNumberOfVisitTypes() const { return num_visit_types_; }
802 #ifndef SWIG
803  const std::vector<std::vector<int>>& GetTopologicallySortedVisitTypes()
804  const {
805  DCHECK(closed_);
806  return topologically_sorted_visit_types_;
807  }
808 #endif // SWIG
813  void AddHardTypeIncompatibility(int type1, int type2);
814  void AddTemporalTypeIncompatibility(int type1, int type2);
816  const absl::flat_hash_set<int>& GetHardTypeIncompatibilitiesOfType(
817  int type) const;
818  const absl::flat_hash_set<int>& GetTemporalTypeIncompatibilitiesOfType(
819  int type) const;
823  return has_hard_type_incompatibilities_;
824  }
826  return has_temporal_type_incompatibilities_;
827  }
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);
853  // clang-format off
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;
864  // clang-format on
868  return has_same_vehicle_type_requirements_;
869  }
871  return has_temporal_type_requirements_;
872  }
873 
876  bool HasTypeRegulations() const {
877  return HasTemporalTypeIncompatibilities() ||
878  HasHardTypeIncompatibilities() || HasSameVehicleTypeRequirements() ||
879  HasTemporalTypeRequirements();
880  }
881 
886  int64 UnperformedPenalty(int64 var_index) const;
890  int64 UnperformedPenaltyOrValue(int64 default_value, int64 var_index) const;
894  int64 GetDepot() const;
895 
900  void SetMaximumNumberOfActiveVehicles(int max_active_vehicles) {
901  max_active_vehicles_ = max_active_vehicles;
902  }
904  int GetMaximumNumberOfActiveVehicles() const { return 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;
920 
936  void SetAmortizedCostFactorsOfAllVehicles(int64 linear_cost_factor,
937  int64 quadratic_cost_factor);
939  void SetAmortizedCostFactorsOfVehicle(int64 linear_cost_factor,
940  int64 quadratic_cost_factor,
941  int vehicle);
942 
943  const std::vector<int64>& GetAmortizedLinearCostFactorOfVehicles() const {
944  return linear_cost_factor_of_vehicle_;
945  }
946  const std::vector<int64>& GetAmortizedQuadraticCostFactorOfVehicles() const {
947  return quadratic_cost_factor_of_vehicle_;
948  }
949 
950  void ConsiderEmptyRouteCostsForVehicle(bool consider_costs, int vehicle) {
951  DCHECK_LT(vehicle, vehicles_);
952  consider_empty_route_costs_[vehicle] = consider_costs;
953  }
954 
955  bool AreEmptyRouteCostsConsideredForVehicle(int vehicle) const {
956  DCHECK_LT(vehicle, vehicles_);
957  return consider_empty_route_costs_[vehicle];
958  }
959 
962 #ifndef SWIG
964  return first_solution_evaluator_;
965  }
966 #endif
969  first_solution_evaluator_ = std::move(evaluator);
970  }
973  void AddLocalSearchOperator(LocalSearchOperator* ls_operator);
975  void AddSearchMonitor(SearchMonitor* const monitor);
979  void AddAtSolutionCallback(std::function<void()> callback);
984  void AddVariableMinimizedByFinalizer(IntVar* var);
987  void AddVariableMaximizedByFinalizer(IntVar* var);
990  void AddWeightedVariableMinimizedByFinalizer(IntVar* var, int64 cost);
993  void AddVariableTargetToFinalizer(IntVar* var, int64 target);
1000  void CloseModel();
1003  void CloseModelWithParameters(
1004  const RoutingSearchParameters& search_parameters);
1011  const Assignment* Solve(const Assignment* assignment = nullptr);
1020  const RoutingSearchParameters& search_parameters,
1021  std::vector<const Assignment*>* solutions = nullptr);
1022  const Assignment* SolveFromAssignmentWithParameters(
1023  const Assignment* assignment,
1024  const RoutingSearchParameters& search_parameters,
1025  std::vector<const Assignment*>* solutions = nullptr);
1031  void SetAssignmentFromOtherModelAssignment(
1032  Assignment* target_assignment, const RoutingModel* source_model,
1033  const Assignment* source_assignment);
1039  // TODO(user): Add support for non-homogeneous costs and disjunctions.
1040  int64 ComputeLowerBound();
1042  Status status() const { return status_; }
1051  IntVar* ApplyLocks(const std::vector<int64>& locks);
1060  bool ApplyLocksToAllVehicles(const std::vector<std::vector<int64>>& locks,
1061  bool close_routes);
1066  const Assignment* const PreAssignment() const { return preassignment_; }
1067  Assignment* MutablePreAssignment() { return preassignment_; }
1071  bool WriteAssignment(const std::string& file_name) const;
1075  Assignment* ReadAssignment(const std::string& file_name);
1078  Assignment* RestoreAssignment(const Assignment& solution);
1084  Assignment* ReadAssignmentFromRoutes(
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,
1105  Assignment* const assignment) const;
1109  void AssignmentToRoutes(const Assignment& assignment,
1110  std::vector<std::vector<int64>>* const routes) const;
1115 #ifndef SWIG
1116  std::vector<std::vector<int64>> GetRoutesFromAssignment(
1117  const Assignment& assignment);
1118 #endif
1136  Assignment* CompactAssignment(const Assignment& assignment) const;
1140  Assignment* CompactAndCheckAssignment(const Assignment& assignment) const;
1142  void AddToAssignment(IntVar* const var);
1143  void AddIntervalToAssignment(IntervalVar* const interval);
1154  const Assignment* PackCumulsOfOptimizerDimensionsFromAssignment(
1155  const Assignment* original_assignment, absl::Duration duration_limit);
1156 #ifndef SWIG
1157  // TODO(user): Revisit if coordinates are added to the RoutingModel class.
1158  void SetSweepArranger(SweepArranger* sweep_arranger) {
1159  sweep_arranger_.reset(sweep_arranger);
1160  }
1162  SweepArranger* sweep_arranger() const { return sweep_arranger_.get(); }
1163 #endif
1170  CHECK(filter != nullptr);
1171  if (closed_) {
1172  LOG(WARNING) << "Model is closed, filter addition will be ignored.";
1173  }
1174  extra_filters_.push_back({filter, LocalSearchFilterManager::kRelax});
1175  extra_filters_.push_back({filter, LocalSearchFilterManager::kAccept});
1176  }
1177 
1180  int64 Start(int vehicle) const { return starts_[vehicle]; }
1182  int64 End(int vehicle) const { return ends_[vehicle]; }
1184  bool IsStart(int64 index) const;
1186  bool IsEnd(int64 index) const { return index >= Size(); }
1189  int VehicleIndex(int64 index) const { return index_to_vehicle_[index]; }
1193  int64 Next(const Assignment& assignment, int64 index) const;
1195  bool IsVehicleUsed(const Assignment& assignment, int vehicle) const;
1196 
1197 #if !defined(SWIGPYTHON)
1200  const std::vector<IntVar*>& Nexts() const { return nexts_; }
1203  const std::vector<IntVar*>& VehicleVars() const { return vehicle_vars_; }
1204 #endif
1207  IntVar* NextVar(int64 index) const { return nexts_[index]; }
1209  IntVar* ActiveVar(int64 index) const { return active_[index]; }
1212  IntVar* ActiveVehicleVar(int vehicle) const {
1213  return vehicle_active_[vehicle];
1214  }
1217  IntVar* VehicleCostsConsideredVar(int vehicle) const {
1218  return vehicle_costs_considered_[vehicle];
1219  }
1222  IntVar* VehicleVar(int64 index) const { return vehicle_vars_[index]; }
1224  IntVar* CostVar() const { return cost_; }
1225 
1228  int64 GetArcCostForVehicle(int64 from_index, int64 to_index,
1229  int64 vehicle) const;
1232  return costs_are_homogeneous_across_vehicles_;
1233  }
1236  int64 GetHomogeneousCost(int64 from_index, int64 to_index) const {
1237  return GetArcCostForVehicle(from_index, to_index, /*vehicle=*/0);
1238  }
1241  int64 GetArcCostForFirstSolution(int64 from_index, int64 to_index) const;
1248  int64 GetArcCostForClass(int64 from_index, int64 to_index,
1249  int64 /*CostClassIndex*/ cost_class_index) const;
1252  DCHECK(closed_);
1253  DCHECK_GE(vehicle, 0);
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];
1257  }
1260  bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const {
1261  DCHECK(closed_);
1262  if (cost_class_index == kCostClassIndexOfZeroCost) {
1263  return has_vehicle_with_zero_cost_class_;
1264  }
1265  return cost_class_index < cost_classes_.size();
1266  }
1268  int GetCostClassesCount() const { return cost_classes_.size(); }
1271  return std::max(0, GetCostClassesCount() - 1);
1272  }
1274  DCHECK(closed_);
1275  return vehicle_class_index_of_vehicle_[vehicle];
1276  }
1278  int GetVehicleClassesCount() const { return vehicle_classes_.size(); }
1280  const std::vector<int>& GetSameVehicleIndicesOfIndex(int node) const {
1281  DCHECK(closed_);
1282  return same_vehicle_groups_[same_vehicle_group_[node]];
1283  }
1284 
1286  DCHECK(closed_);
1287  return vehicle_type_container_;
1288  }
1289 
1308  bool ArcIsMoreConstrainedThanArc(int64 from, int64 to1, int64 to2);
1313  std::string DebugOutputAssignment(
1314  const Assignment& solution_assignment,
1315  const std::string& dimension_to_print) const;
1321 #ifndef SWIG
1322  std::vector<std::vector<std::pair<int64, int64>>> GetCumulBounds(
1323  const Assignment& solution_assignment, const RoutingDimension& dimension);
1324 #endif
1327  Solver* solver() const { return solver_.get(); }
1328 
1330  bool CheckLimit() {
1331  DCHECK(limit_ != nullptr);
1332  return limit_->Check();
1333  }
1334 
1336  absl::Duration RemainingTime() const {
1337  DCHECK(limit_ != nullptr);
1338  return limit_->AbsoluteSolverDeadline() - solver_->Now();
1339  }
1340 
1343  int nodes() const { return nodes_; }
1345  int vehicles() const { return vehicles_; }
1347  int64 Size() const { return nodes_ + vehicles_ - start_end_count_; }
1348 
1351  int64 GetNumberOfDecisionsInFirstSolution(
1352  const RoutingSearchParameters& search_parameters) const;
1353  int64 GetNumberOfRejectsInFirstSolution(
1354  const RoutingSearchParameters& search_parameters) const;
1358  return automatic_first_solution_strategy_;
1359  }
1360 
1362  bool IsMatchingModel() const;
1363 
1364 #ifndef SWIG
1368  std::function<std::vector<operations_research::IntVar*>(RoutingModel*)>;
1369 
1370  void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback);
1371 #endif // SWIG
1372 
1374  // TODO(user): Find a way to test and restrict the access at the same time.
1386  DecisionBuilder* MakeGuidedSlackFinalizer(
1387  const RoutingDimension* dimension,
1388  std::function<int64(int64)> initializer);
1389 #ifndef SWIG
1390  // TODO(user): MakeGreedyDescentLSOperator is too general for routing.h.
1395  static std::unique_ptr<LocalSearchOperator> MakeGreedyDescentLSOperator(
1396  std::vector<IntVar*> variables);
1397 #endif
1411  DecisionBuilder* MakeSelfDependentDimensionFinalizer(
1412  const RoutingDimension* dimension);
1413 
1414  private:
1416  enum RoutingLocalSearchOperator {
1417  RELOCATE = 0,
1418  RELOCATE_PAIR,
1419  LIGHT_RELOCATE_PAIR,
1420  RELOCATE_NEIGHBORS,
1421  EXCHANGE,
1422  EXCHANGE_PAIR,
1423  CROSS,
1424  CROSS_EXCHANGE,
1425  TWO_OPT,
1426  OR_OPT,
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,
1435  LIN_KERNIGHAN,
1436  TSP_OPT,
1437  MAKE_ACTIVE,
1438  RELOCATE_AND_MAKE_ACTIVE,
1439  MAKE_ACTIVE_AND_RELOCATE,
1440  MAKE_INACTIVE,
1441  MAKE_CHAIN_INACTIVE,
1442  SWAP_ACTIVE,
1443  EXTENDED_SWAP_ACTIVE,
1444  NODE_PAIR_SWAP,
1445  PATH_LNS,
1446  FULL_PATH_LNS,
1447  TSP_LNS,
1448  INACTIVE_LNS,
1449  EXCHANGE_RELOCATE_PAIR,
1450  RELOCATE_SUBTRIP,
1451  EXCHANGE_SUBTRIP,
1452  LOCAL_SEARCH_OPERATOR_COUNTER
1453  };
1454 
1458  template <typename T>
1459  struct ValuedNodes {
1460  std::vector<int64> indices;
1461  T value;
1462  };
1463  struct DisjunctionValues {
1464  int64 penalty;
1465  int64 max_cardinality;
1466  };
1467  typedef ValuedNodes<DisjunctionValues> Disjunction;
1468 
1471  struct CostCacheElement {
1476  int index;
1477  CostClassIndex cost_class_index;
1478  int64 cost;
1479  };
1480 
1482  void Initialize();
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;
1500 
1528  void StoreDimensionCumulOptimizers(const RoutingSearchParameters& parameters);
1529 
1530  void ComputeCostClasses(const RoutingSearchParameters& parameters);
1531  void ComputeVehicleClasses();
1539  void ComputeVehicleTypes();
1549  void FinalizeVisitTypes();
1550  // Called by FinalizeVisitTypes() to setup topologically_sorted_visit_types_.
1551  void TopologicallySortVisitTypes();
1552  int64 GetArcCostForClassInternal(int64 from_index, int64 to_index,
1553  CostClassIndex cost_class_index) const;
1554  void AppendHomogeneousArcCosts(const RoutingSearchParameters& parameters,
1555  int node_index,
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 {
1562  DCHECK_LT(0, vehicles_);
1563  return (vehicle >= 0 ? GetCostClassIndexOfVehicle(vehicle)
1564  : kCostClassIndexOfZeroCost)
1565  .value();
1566  }
1567  int64 GetDimensionTransitCostSum(int64 i, int64 j,
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;
1580 
1583  bool RouteCanBeUsedByVehicle(const Assignment& assignment, int start_index,
1584  int vehicle) const;
1592  bool ReplaceUnusedVehicle(int unused_vehicle, int active_vehicle,
1593  Assignment* compact_assignment) const;
1594 
1595  void QuietCloseModel();
1596  void QuietCloseModelWithParameters(
1597  const RoutingSearchParameters& parameters) {
1598  if (!closed_) {
1599  CloseModelWithParameters(parameters);
1600  }
1601  }
1602 
1604  bool SolveMatchingModel(Assignment* assignment,
1605  const RoutingSearchParameters& parameters);
1606 #ifndef SWIG
1608  bool AppendAssignmentIfFeasible(
1609  const Assignment& assignment,
1610  std::vector<std::unique_ptr<Assignment>>* assignments);
1611 #endif
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);
1629  // TODO(user): Document each auxiliary method.
1630  Assignment* GetOrCreateAssignment();
1631  Assignment* GetOrCreateTmpAssignment();
1632  RegularLimit* GetOrCreateLimit();
1633  RegularLimit* GetOrCreateLocalSearchLimit();
1634  RegularLimit* GetOrCreateLargeNeighborhoodSearchLimit();
1635  RegularLimit* GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
1636  LocalSearchOperator* CreateInsertionOperator();
1637  LocalSearchOperator* CreateMakeInactiveOperator();
1638  template <class T>
1639  LocalSearchOperator* CreateCPOperator(const T& operator_factory) {
1640  return operator_factory(solver_.get(), nexts_,
1641  CostsAreHomogeneousAcrossVehicles()
1642  ? std::vector<IntVar*>()
1643  : vehicle_vars_,
1644  vehicle_start_class_callback_);
1645  }
1646  template <class T>
1647  LocalSearchOperator* CreateCPOperator() {
1648  return CreateCPOperator(absl::bind_front(MakeLocalSearchOperator<T>));
1649  }
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*>()
1655  : vehicle_vars_,
1656  vehicle_start_class_callback_, arg));
1657  }
1658  template <class T>
1659  LocalSearchOperator* CreatePairOperator() {
1660  return CreateOperator<T>(pickup_delivery_pairs_);
1661  }
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(
1672  const RoutingSearchParameters& parameters);
1673  std::vector<LocalSearchFilterManager::FilterEvent>
1674  GetOrCreateFeasibilityFilters(const RoutingSearchParameters& parameters);
1675  LocalSearchFilterManager* GetOrCreateFeasibilityFilterManager(
1676  const RoutingSearchParameters& parameters);
1677  LocalSearchFilterManager* GetOrCreateStrongFeasibilityFilterManager(
1678  const RoutingSearchParameters& parameters);
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_;
1701 
1702  // Detects implicit pickup delivery pairs. These pairs are
1703  // non-pickup/delivery pairs for which there exists a unary dimension such
1704  // that the demand d of the implicit pickup is positive and the demand of the
1705  // implicit delivery is equal to -d.
1706  void DetectImplicitPickupAndDeliveries();
1707 
1708  int GetVehicleStartClass(int64 start) const;
1709 
1710  void InitSameVehicleGroups(int number_of_groups) {
1711  same_vehicle_group_.assign(Size(), 0);
1712  same_vehicle_groups_.assign(number_of_groups, {});
1713  }
1714  void SetSameVehicleGroup(int index, int group) {
1715  same_vehicle_group_[index] = group;
1716  same_vehicle_groups_[group].push_back(index);
1717  }
1718 
1720  std::unique_ptr<Solver> solver_;
1721  int nodes_;
1722  int vehicles_;
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_;
1729  // The following vectors are indexed by vehicle index.
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_;
1741  // clang-format off
1745  std::vector<std::unique_ptr<GlobalDimensionCumulOptimizer> >
1746  global_dimension_optimizers_;
1747  absl::StrongVector<DimensionIndex, int> global_optimizer_index_;
1748  std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >
1749  local_dimension_optimizers_;
1750  std::vector<std::unique_ptr<LocalDimensionCumulOptimizer> >
1751  local_dimension_mp_optimizers_;
1752  // clang-format off
1753  absl::StrongVector<DimensionIndex, int> local_optimizer_index_;
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_;
1775 #ifndef SWIG
1777 #endif // SWIG
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_;
1782 #ifndef SWIG
1784 #endif // SWIG
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_;
1793 #ifndef SWIG
1794  std::vector<absl::flat_hash_set<int>> allowed_vehicles_;
1795 #endif // SWIG
1797  IndexPairs pickup_delivery_pairs_;
1798  IndexPairs implicit_pickup_delivery_pairs_without_alternatives_;
1799  std::vector<std::pair<DisjunctionIndex, DisjunctionIndex> >
1800  pickup_delivery_disjunctions_;
1801  // clang-format off
1802  // If node_index is a pickup, index_to_pickup_index_pairs_[node_index] is the
1803  // vector of pairs {pair_index, pickup_index} such that
1804  // (pickup_delivery_pairs_[pair_index].first)[pickup_index] == node_index
1805  std::vector<std::vector<std::pair<int, int> > > index_to_pickup_index_pairs_;
1806  // Same as above for deliveries.
1807  std::vector<std::vector<std::pair<int, int> > >
1808  index_to_delivery_index_pairs_;
1809  // clang-format on
1810  std::vector<PickupAndDeliveryPolicy> vehicle_pickup_delivery_policy_;
1811  // Same vehicle group to which a node belongs.
1812  std::vector<int> same_vehicle_group_;
1813  // Same vehicle node groups.
1814  std::vector<std::vector<int>> same_vehicle_groups_;
1815  // Node visit types
1816  // Variable index to visit type index.
1817  std::vector<int> index_to_visit_type_;
1818  // Variable index to VisitTypePolicy.
1819  std::vector<VisitTypePolicy> index_to_type_policy_;
1820  // clang-format off
1821  std::vector<std::vector<int> > single_nodes_of_type_;
1822  std::vector<std::vector<int> > pair_indices_of_type_;
1823 
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_;
1830 
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</*type*/int, absl::flat_hash_set<VisitTypePolicy> >
1840  trivially_infeasible_visit_types_to_policies_;
1841 
1842  // Visit types sorted topologically based on required-->dependent requirement
1843  // arcs between the types (if the requirement/dependency graph is acyclic).
1844  // Visit types of the same topological level are sorted in each sub-vector
1845  // by decreasing requirement "tightness", computed as the pair of the two
1846  // following criteria:
1847  //
1848  // 1) How highly *dependent* this type is, determined by
1849  // (total number of required alternative sets for that type)
1850  // / (average number of types in the required alternative sets)
1851  // 2) How highly *required* this type t is, computed as
1852  // SUM_{S required set containing t} ( 1 / |S| ),
1853  // i.e. the sum of reverse number of elements of all required sets
1854  // containing the type t.
1855  //
1856  // The higher these two numbers, the tighter the type is wrt requirements.
1857  std::vector<std::vector<int> > topologically_sorted_visit_types_;
1858  // clang-format on
1859  int num_visit_types_;
1860  // Two indices are equivalent if they correspond to the same node (as given
1861  // to the constructors taking a RoutingIndexManager).
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_;
1866  // TODO(user): b/62478706 Once the port is done, this shouldn't be needed
1867  // anymore.
1868  RoutingIndexManager manager_;
1869  int start_end_count_;
1870  // Model status
1871  bool closed_ = false;
1872  Status status_ = ROUTING_NOT_SOLVED;
1873  bool enable_deep_serialization_ = true;
1874 
1875  // Search data
1876  std::vector<DecisionBuilder*> first_solution_decision_builders_;
1877  std::vector<IntVarFilteredDecisionBuilder*>
1878  first_solution_filtered_decision_builders_;
1879  Solver::IndexEvaluator2 first_solution_evaluator_;
1880  FirstSolutionStrategy::Value automatic_first_solution_strategy_ =
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_;
1901 #ifndef SWIG
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_;
1907 #endif
1908 
1909  RegularLimit* limit_ = nullptr;
1910  RegularLimit* ls_limit_ = nullptr;
1911  RegularLimit* lns_limit_ = nullptr;
1912  RegularLimit* first_solution_lns_limit_ = nullptr;
1913 
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;
1918 
1919  std::vector<TransitCallback1> unary_transit_evaluators_;
1920  std::vector<TransitCallback2> transit_evaluators_;
1921  // The following vector stores a boolean per transit_evaluator_, indicating
1922  // whether the transits are all positive.
1923  // is_transit_evaluator_positive_ will be set to true only when registering a
1924  // callback via RegisterPositiveTransitCallback(), and to false otherwise.
1925  // The actual positivity of the transit values will only be checked in debug
1926  // mode, when calling RegisterPositiveTransitCallback().
1927  // Therefore, RegisterPositiveTransitCallback() should only be called when the
1928  // transits are known to be positive, as the positivity of a callback will
1929  // allow some improvements in the solver, but will entail in errors if the
1930  // transits are falsely assumed positive.
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_;
1935 
1936  friend class RoutingDimension;
1938 
1940 };
1941 
1944  public:
1946  static const char kLightElement[];
1947  static const char kLightElement2[];
1948  static const char kRemoveValues[];
1949 };
1950 
1951 #if !defined(SWIG)
1955  public:
1961  struct Tasks {
1962  int num_chain_tasks = 0;
1963  std::vector<int64> start_min;
1964  std::vector<int64> start_max;
1965  std::vector<int64> duration_min;
1966  std::vector<int64> duration_max;
1967  std::vector<int64> end_min;
1968  std::vector<int64> end_max;
1969  std::vector<bool> is_preemptible;
1970  std::vector<const SortedDisjointIntervalList*> forbidden_intervals;
1971  std::vector<std::pair<int64, int64>> distance_duration;
1972  int64 span_min = 0;
1973  int64 span_max = kint64max;
1974 
1975  void Clear() {
1976  start_min.clear();
1977  start_max.clear();
1978  duration_min.clear();
1979  duration_max.clear();
1980  end_min.clear();
1981  end_max.clear();
1982  is_preemptible.clear();
1983  forbidden_intervals.clear();
1984  distance_duration.clear();
1985  span_min = 0;
1986  span_max = kint64max;
1987  num_chain_tasks = 0;
1988  }
1989  };
1990 
1993  bool Propagate(Tasks* tasks);
1994 
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);
2017 
2018  private:
2021  sat::ThetaLambdaTree<int64> theta_lambda_tree_;
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_;
2029 };
2030 
2032  std::vector<int64> min_travels;
2033  std::vector<int64> max_travels;
2034  std::vector<int64> pre_travels;
2035  std::vector<int64> post_travels;
2036 };
2037 
2038 void AppendTasksFromPath(const std::vector<int64>& path,
2039  const TravelBounds& travel_bounds,
2040  const RoutingDimension& dimension,
2042 void AppendTasksFromIntervals(const std::vector<IntervalVar*>& intervals,
2044 void FillPathEvaluation(const std::vector<int64>& path,
2045  const RoutingModel::TransitCallback2& evaluator,
2046  std::vector<int64>* values);
2047 void FillTravelBoundsOfVehicle(int vehicle, const std::vector<int64>& path,
2048  const RoutingDimension& dimension,
2049  TravelBounds* travel_bounds);
2050 #endif // !defined(SWIG)
2051 
2063  public:
2064  explicit GlobalVehicleBreaksConstraint(const RoutingDimension* dimension);
2065  std::string DebugString() const override {
2066  return "GlobalVehicleBreaksConstraint";
2067  }
2068 
2069  void Post() override;
2070  void InitialPropagate() override;
2071 
2072  private:
2073  void PropagateNode(int node);
2074  void PropagateVehicle(int vehicle);
2075  void PropagateMaxBreakDistance(int vehicle);
2076 
2077  const RoutingModel* model_;
2078  const RoutingDimension* const dimension_;
2079  std::vector<Demon*> vehicle_demons_;
2080  std::vector<int64> path_;
2081 
2086  void FillPartialPathOfVehicle(int vehicle);
2087  void FillPathTravels(const std::vector<int64>& path);
2088 
2099  class TaskTranslator {
2100  public:
2101  TaskTranslator(IntVar* start, int64 before_start, int64 after_start)
2102  : start_(start),
2103  before_start_(before_start),
2104  after_start_(after_start) {}
2105  explicit TaskTranslator(IntervalVar* interval) : interval_(interval) {}
2106  TaskTranslator() {}
2107 
2108  void SetStartMin(int64 value) {
2109  if (start_ != nullptr) {
2110  start_->SetMin(CapAdd(before_start_, value));
2111  } else if (interval_ != nullptr) {
2112  interval_->SetStartMin(value);
2113  }
2114  }
2115  void SetStartMax(int64 value) {
2116  if (start_ != nullptr) {
2117  start_->SetMax(CapAdd(before_start_, value));
2118  } else if (interval_ != nullptr) {
2119  interval_->SetStartMax(value);
2120  }
2121  }
2122  void SetDurationMin(int64 value) {
2123  if (interval_ != nullptr) {
2124  interval_->SetDurationMin(value);
2125  }
2126  }
2127  void SetEndMin(int64 value) {
2128  if (start_ != nullptr) {
2129  start_->SetMin(CapSub(value, after_start_));
2130  } else if (interval_ != nullptr) {
2131  interval_->SetEndMin(value);
2132  }
2133  }
2134  void SetEndMax(int64 value) {
2135  if (start_ != nullptr) {
2136  start_->SetMax(CapSub(value, after_start_));
2137  } else if (interval_ != nullptr) {
2138  interval_->SetEndMax(value);
2139  }
2140  }
2141 
2142  private:
2143  IntVar* start_ = nullptr;
2144  int64 before_start_;
2145  int64 after_start_;
2146  IntervalVar* interval_ = nullptr;
2147  };
2148 
2150  std::vector<TaskTranslator> task_translators_;
2151 
2153  DisjunctivePropagator disjunctive_propagator_;
2154  DisjunctivePropagator::Tasks tasks_;
2155 
2157  TravelBounds travel_bounds_;
2158 };
2159 
2161  public:
2162  explicit TypeRegulationsChecker(const RoutingModel& model);
2164 
2165  bool CheckVehicle(int vehicle,
2166  const std::function<int64(int64)>& next_accessor);
2167 
2168  protected:
2169 #ifndef SWIG
2171 #endif // SWIG
2172 
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;
2189  };
2190 
2195  bool TypeOccursOnRoute(int type) const;
2202  bool TypeCurrentlyOnRoute(int type, int pos) const;
2203 
2204  void InitializeCheck(int vehicle,
2205  const std::function<int64(int64)>& next_accessor);
2206  virtual void OnInitializeCheck() {}
2207  virtual bool HasRegulationsToCheck() const = 0;
2208  virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy,
2209  int pos) = 0;
2210  virtual bool FinalizeCheck() const { return true; }
2211 
2213 
2214  private:
2215  std::vector<TypePolicyOccurrence> occurrences_of_type_;
2216  std::vector<int64> current_route_visits_;
2217 };
2218 
2221  public:
2223  bool check_hard_incompatibilities);
2225 
2226  private:
2227  bool HasRegulationsToCheck() const override;
2228  bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos) override;
2232  bool check_hard_incompatibilities_;
2233 };
2234 
2237  public:
2241 
2242  private:
2243  bool HasRegulationsToCheck() const override;
2244  void OnInitializeCheck() override {
2245  types_with_same_vehicle_requirements_on_route_.clear();
2246  }
2247  // clang-format off
2250  bool CheckRequiredTypesCurrentlyOnRoute(
2251  const std::vector<absl::flat_hash_set<int> >& required_type_alternatives,
2252  int pos);
2253  // clang-format on
2254  bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos) override;
2255  bool FinalizeCheck() const override;
2256 
2257  absl::flat_hash_set<int> types_with_same_vehicle_requirements_on_route_;
2258 };
2259 
2301  public:
2302  explicit TypeRegulationsConstraint(const RoutingModel& model);
2303 
2304  void Post() override;
2305  void InitialPropagate() override;
2306 
2307  private:
2308  void PropagateNodeRegulations(int node);
2309  void CheckRegulationsOnVehicle(int vehicle);
2310 
2311  const RoutingModel& model_;
2312  TypeIncompatibilityChecker incompatibility_checker_;
2313  TypeRequirementChecker requirement_checker_;
2314  std::vector<Demon*> vehicle_demons_;
2315 };
2316 #if !defined SWIG
2330  public:
2331  struct BoundCost {
2334  };
2335  SimpleBoundCosts(int num_bounds, BoundCost default_bound_cost)
2336  : bound_costs_(num_bounds, default_bound_cost) {}
2337  BoundCost& bound_cost(int element) { return bound_costs_[element]; }
2338  BoundCost bound_cost(int element) const { return bound_costs_[element]; }
2339  int Size() { return bound_costs_.size(); }
2342 
2343  private:
2344  std::vector<BoundCost> bound_costs_;
2345 };
2346 #endif // !defined SWIG
2347 
2365 // TODO(user): Break constraints need to know the service time of nodes
2369  public:
2370  ~RoutingDimension();
2372  RoutingModel* model() const { return model_; }
2376  int64 GetTransitValue(int64 from_index, int64 to_index, int64 vehicle) const;
2380  int64 vehicle_class) const {
2381  return model_->TransitCallback(class_evaluators_[vehicle_class])(from_index,
2382  to_index);
2383  }
2386  IntVar* CumulVar(int64 index) const { return cumuls_[index]; }
2387  IntVar* TransitVar(int64 index) const { return transits_[index]; }
2388  IntVar* FixedTransitVar(int64 index) const { return fixed_transits_[index]; }
2389  IntVar* SlackVar(int64 index) const { return slacks_[index]; }
2390 
2391 #if !defined(SWIGPYTHON)
2394  const std::vector<IntVar*>& cumuls() const { return cumuls_; }
2395  const std::vector<IntVar*>& fixed_transits() const { return fixed_transits_; }
2396  const std::vector<IntVar*>& transits() const { return transits_; }
2397  const std::vector<IntVar*>& slacks() const { return slacks_; }
2398 #if !defined(SWIGCSHARP) && !defined(SWIGJAVA)
2400  const std::vector<SortedDisjointIntervalList>& forbidden_intervals() const {
2401  return forbidden_intervals_;
2402  }
2404  SortedDisjointIntervalList GetAllowedIntervalsInRange(int64 index,
2405  int64 min_value,
2406  int64 max_value) const;
2410  int64 min_value) const {
2411  DCHECK_LT(index, forbidden_intervals_.size());
2412  const SortedDisjointIntervalList& forbidden_intervals =
2413  forbidden_intervals_[index];
2414  const auto first_forbidden_interval_it =
2415  forbidden_intervals.FirstIntervalGreaterOrEqual(min_value);
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);
2420  }
2422  return min_value;
2423  }
2429  int64 max_value) const {
2430  DCHECK_LT(index, forbidden_intervals_.size());
2431  const SortedDisjointIntervalList& forbidden_intervals =
2432  forbidden_intervals_[index];
2433  const auto last_forbidden_interval_it =
2434  forbidden_intervals.LastIntervalLessOrEqual(max_value);
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);
2439  }
2441  return max_value;
2442  }
2444  const std::vector<int64>& vehicle_capacities() const {
2445  return vehicle_capacities_;
2446  }
2450  return model_->TransitCallback(
2451  class_evaluators_[vehicle_to_class_[vehicle]]);
2452  }
2457  int vehicle) const {
2458  return model_->UnaryTransitCallbackOrNull(
2459  class_evaluators_[vehicle_to_class_[vehicle]]);
2460  }
2463  bool AreVehicleTransitsPositive(int vehicle) const {
2464  return model()->is_transit_evaluator_positive_
2465  [class_evaluators_[vehicle_to_class_[vehicle]]];
2466  }
2467  int vehicle_to_class(int vehicle) const { return vehicle_to_class_[vehicle]; }
2468 #endif
2469 #endif
2473  void SetSpanUpperBoundForVehicle(int64 upper_bound, int vehicle);
2480  void SetSpanCostCoefficientForVehicle(int64 coefficient, int vehicle);
2481  void SetSpanCostCoefficientForAllVehicles(int64 coefficient);
2488  void SetGlobalSpanCostCoefficient(int64 coefficient);
2489 
2490 #ifndef SWIG
2495  void SetCumulVarPiecewiseLinearCost(int64 index,
2496  const PiecewiseLinearFunction& cost);
2499  bool HasCumulVarPiecewiseLinearCost(int64 index) const;
2502  const PiecewiseLinearFunction* GetCumulVarPiecewiseLinearCost(
2503  int64 index) const;
2504 #endif
2505 
2514  void SetCumulVarSoftUpperBound(int64 index, int64 upper_bound,
2515  int64 coefficient);
2518  bool HasCumulVarSoftUpperBound(int64 index) const;
2522  int64 GetCumulVarSoftUpperBound(int64 index) const;
2526  int64 GetCumulVarSoftUpperBoundCoefficient(int64 index) const;
2527 
2537  void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound,
2538  int64 coefficient);
2541  bool HasCumulVarSoftLowerBound(int64 index) const;
2545  int64 GetCumulVarSoftLowerBound(int64 index) const;
2549  int64 GetCumulVarSoftLowerBoundCoefficient(int64 index) const;
2565  // TODO(user): Remove if !defined when routing.i is repaired.
2566 #if !defined(SWIGPYTHON)
2567  void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks, int vehicle,
2568  int pre_travel_evaluator,
2569  int post_travel_evaluator);
2570 #endif // !defined(SWIGPYTHON)
2571 
2573  void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks, int vehicle,
2574  std::vector<int64> node_visit_transits);
2575 
2580  void SetBreakDistanceDurationOfVehicle(int64 distance, int64 duration,
2581  int vehicle);
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,
2592  std::function<int64(int64, int64)> delays);
2593 
2595  const std::vector<IntervalVar*>& GetBreakIntervalsOfVehicle(
2596  int vehicle) const;
2599  // clang-format off
2600  const std::vector<std::pair<int64, int64> >&
2601  GetBreakDistanceDurationOfVehicle(int vehicle) const;
2602  // clang-format on
2603 #endif
2604  int GetPreTravelEvaluatorOfVehicle(int vehicle) const;
2605  int GetPostTravelEvaluatorOfVehicle(int vehicle) const;
2606 
2608  const RoutingDimension* base_dimension() const { return base_dimension_; }
2616  int64 ShortestTransitionSlack(int64 node) const;
2617 
2619  const std::string& name() const { return name_; }
2620 
2622 #ifndef SWIG
2624  return path_precedence_graph_;
2625  }
2626 #endif // SWIG
2627 
2637  typedef std::function<int64(int, int)> PickupToDeliveryLimitFunction;
2638 
2639  void SetPickupToDeliveryLimitFunctionForPair(
2640  PickupToDeliveryLimitFunction limit_function, int pair_index);
2641 
2642  bool HasPickupToDeliveryLimits() const;
2643 #ifndef SWIG
2644  int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup,
2645  int delivery) const;
2646 
2651  };
2652 
2654  node_precedences_.push_back(precedence);
2655  }
2656  const std::vector<NodePrecedence>& GetNodePrecedences() const {
2657  return node_precedences_;
2658  }
2659 #endif // SWIG
2660 
2661  void AddNodePrecedence(int64 first_node, int64 second_node, int64 offset) {
2662  AddNodePrecedence({first_node, second_node, offset});
2663  }
2664 
2665  int64 GetSpanUpperBoundForVehicle(int vehicle) const {
2666  return vehicle_span_upper_bounds_[vehicle];
2667  }
2668 #ifndef SWIG
2669  const std::vector<int64>& vehicle_span_upper_bounds() const {
2670  return vehicle_span_upper_bounds_;
2671  }
2672 #endif // SWIG
2674  return vehicle_span_cost_coefficients_[vehicle];
2675  }
2676 #ifndef SWIG
2677  const std::vector<int64>& vehicle_span_cost_coefficients() const {
2678  return vehicle_span_cost_coefficients_;
2679  }
2680 #endif // SWIG
2682  return global_span_cost_coefficient_;
2683  }
2684 
2686  DCHECK_GE(global_optimizer_offset_, 0);
2687  return global_optimizer_offset_;
2688  }
2690  if (vehicle >= local_optimizer_offset_for_vehicle_.size()) {
2691  return 0;
2692  }
2693  DCHECK_GE(local_optimizer_offset_for_vehicle_[vehicle], 0);
2694  return local_optimizer_offset_for_vehicle_[vehicle];
2695  }
2696 #if !defined SWIG
2700  int vehicle) {
2701  if (!HasSoftSpanUpperBounds()) {
2702  vehicle_soft_span_upper_bound_ = absl::make_unique<SimpleBoundCosts>(
2703  model_->vehicles(), SimpleBoundCosts::BoundCost{kint64max, 0});
2704  }
2705  vehicle_soft_span_upper_bound_->bound_cost(vehicle) = bound_cost;
2706  }
2707  bool HasSoftSpanUpperBounds() const {
2708  return vehicle_soft_span_upper_bound_ != nullptr;
2709  }
2711  int vehicle) const {
2712  DCHECK(HasSoftSpanUpperBounds());
2713  return vehicle_soft_span_upper_bound_->bound_cost(vehicle);
2714  }
2718  SimpleBoundCosts::BoundCost bound_cost, int vehicle) {
2719  if (!HasQuadraticCostSoftSpanUpperBounds()) {
2720  vehicle_quadratic_cost_soft_span_upper_bound_ =
2721  absl::make_unique<SimpleBoundCosts>(
2722  model_->vehicles(), SimpleBoundCosts::BoundCost{kint64max, 0});
2723  }
2724  vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle) =
2725  bound_cost;
2726  }
2728  return vehicle_quadratic_cost_soft_span_upper_bound_ != nullptr;
2729  }
2731  int vehicle) const {
2732  DCHECK(HasQuadraticCostSoftSpanUpperBounds());
2733  return vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle);
2734  }
2735 #endif
2736 
2737  private:
2738  struct SoftBound {
2739  IntVar* var;
2740  int64 bound;
2742  };
2743 
2744  struct PiecewiseLinearCost {
2745  PiecewiseLinearCost() : var(nullptr), cost(nullptr) {}
2746  IntVar* var;
2747  std::unique_ptr<PiecewiseLinearFunction> cost;
2748  };
2749 
2750  class SelfBased {};
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,
2758  int64 slack_max);
2759  void InitializeCumuls();
2760  void InitializeTransits(
2761  const std::vector<int>& transit_evaluators,
2762  const std::vector<int>& state_dependent_transit_evaluators,
2763  int64 slack_max);
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);
2779 
2780  void SetOffsetForGlobalOptimizer(int64 offset) {
2781  global_optimizer_offset_ = std::max(Zero(), offset);
2782  }
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);
2789  }
2790 
2791  std::vector<IntVar*> cumuls_;
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_;
2801 #ifndef SWIG
2802  ReverseArcListGraph<int, int> path_precedence_graph_;
2803 #endif
2804  // For every {first_node, second_node, offset} element in node_precedences_,
2805  // if both first_node and second_node are performed, then
2806  // cumuls_[second_node] must be greater than (or equal to)
2807  // cumuls_[first_node] + offset.
2808  std::vector<NodePrecedence> node_precedences_;
2809 
2810  // The transits of a dimension may depend on its cumuls or the cumuls of
2811  // another dimension. There can be no cycles, except for self loops, a
2812  // typical example for this is a time dimension.
2813  const RoutingDimension* const base_dimension_;
2814 
2815  // Values in state_dependent_class_evaluators_ correspond to the evaluators
2816  // in RoutingModel::state_dependent_transit_evaluators_ for each vehicle
2817  // class.
2818  std::vector<int> state_dependent_class_evaluators_;
2819  std::vector<int64> state_dependent_vehicle_to_class_;
2820 
2821  // For each pickup/delivery pair_index for which limits have been set,
2822  // pickup_to_delivery_limits_per_pair_index_[pair_index] contains the
2823  // PickupToDeliveryLimitFunction for the pickup and deliveries in this pair.
2824  std::vector<PickupToDeliveryLimitFunction>
2825  pickup_to_delivery_limits_per_pair_index_;
2826 
2827  // Used if some vehicle has breaks in this dimension, typically time.
2828  bool break_constraints_are_initialized_ = false;
2829  // clang-format off
2830  std::vector<std::vector<IntervalVar*> > vehicle_break_intervals_;
2831  std::vector<std::vector<std::pair<int64, int64> > >
2832  vehicle_break_distance_duration_;
2833  // clang-format on
2834  // For each vehicle, stores the part of travel that is made directly
2835  // after (before) the departure (arrival) node of the travel.
2836  // These parts of the travel are non-interruptible, in particular by a break.
2837  std::vector<int> vehicle_pre_travel_evaluators_;
2838  std::vector<int> vehicle_post_travel_evaluators_;
2839 
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_;
2856  friend class RoutingModel;
2858  friend void AppendDimensionCumulFilters(
2859  const std::vector<RoutingDimension*>& dimensions,
2860  const RoutingSearchParameters& parameters, bool filter_objective_cost,
2861  std::vector<LocalSearchFilterManager::FilterEvent>* filters);
2862 
2864 };
2865 
2866 #ifndef SWIG
2870  public:
2871  explicit SweepArranger(const std::vector<std::pair<int64, int64>>& points);
2872  virtual ~SweepArranger() {}
2873  void ArrangeIndices(std::vector<int64>* indices);
2874  void SetSectors(int sectors) { sectors_ = sectors; }
2875 
2876  private:
2877  std::vector<int> coordinates_;
2878  int sectors_;
2879 
2881 };
2882 #endif
2883 
2886 DecisionBuilder* MakeSetValuesFromTargets(Solver* solver,
2887  std::vector<IntVar*> variables,
2888  std::vector<int64> targets);
2889 
2890 #ifndef SWIG
2895  public:
2897  const RoutingModel::VehicleTypeContainer& vehicle_type_container)
2898  : vehicle_type_container_(&vehicle_type_container) {}
2899 
2900  int NumTypes() const { return vehicle_type_container_->NumTypes(); }
2901 
2902  int Type(int vehicle) const { return vehicle_type_container_->Type(vehicle); }
2903 
2906  void Reset(const std::function<bool(int)>& store_vehicle);
2907 
2910  void Update(const std::function<bool(int)>& remove_vehicle);
2911 
2912  int GetLowestFixedCostVehicleOfType(int type) const {
2913  DCHECK_LT(type, NumTypes());
2914  const std::set<VehicleClassEntry>& vehicle_classes =
2915  sorted_vehicle_classes_per_type_[type];
2916  if (vehicle_classes.empty()) {
2917  return -1;
2918  }
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];
2922  }
2923 
2924  void ReinjectVehicleOfClass(int vehicle, int vehicle_class,
2925  int64 fixed_cost) {
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);
2935  }
2936  vehicles.push_back(vehicle);
2937  }
2938 
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);
2950 
2951  private:
2952  using VehicleClassEntry =
2954  const RoutingModel::VehicleTypeContainer* const vehicle_type_container_;
2955  // clang-format off
2956  std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;
2957  std::vector<std::vector<int> > vehicles_per_vehicle_class_;
2958  // clang-format on
2959 };
2960 
2973 
2975 // TODO(user): Eventually move this to the core CP solver library
2978  public:
2980  std::unique_ptr<IntVarFilteredHeuristic> heuristic);
2981 
2983 
2984  Decision* Next(Solver* solver) override;
2985 
2986  std::string DebugString() const override;
2987 
2989  int64 number_of_decisions() const;
2990  int64 number_of_rejects() const;
2991 
2992  private:
2993  const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;
2994 };
2995 
2998  public:
2999  IntVarFilteredHeuristic(Solver* solver, const std::vector<IntVar*>& vars,
3000  LocalSearchFilterManager* filter_manager);
3001 
3003 
3006  Assignment* const BuildSolution();
3007 
3010  int64 number_of_decisions() const { return number_of_decisions_; }
3011  int64 number_of_rejects() const { return number_of_rejects_; }
3012 
3013  virtual std::string DebugString() const { return "IntVarFilteredHeuristic"; }
3014 
3015  protected:
3017  void ResetSolution();
3019  virtual bool InitializeSolution() { return true; }
3021  virtual bool BuildSolutionInternal() = 0;
3025  bool Commit();
3027  virtual bool StopSearch() { return false; }
3031  if (!is_in_delta_[index]) {
3032  delta_->FastAdd(vars_[index])->SetValue(value);
3033  delta_indices_.push_back(index);
3034  is_in_delta_[index] = true;
3035  } else {
3036  delta_->SetValue(vars_[index], value);
3037  }
3038  }
3042  return assignment_->IntVarContainer().Element(index).Value();
3043  }
3045  bool Contains(int64 index) const {
3046  return assignment_->IntVarContainer().Element(index).Var() != nullptr;
3047  }
3050  int Size() const { return vars_.size(); }
3052  IntVar* Var(int64 index) const { return vars_[index]; }
3054  void SynchronizeFilters();
3055 
3057 
3058  private:
3061  bool FilterAccept();
3062 
3063  Solver* solver_;
3064  const std::vector<IntVar*> vars_;
3065  Assignment* const delta_;
3066  std::vector<int> delta_indices_;
3067  std::vector<bool> is_in_delta_;
3068  Assignment* const empty_;
3069  LocalSearchFilterManager* filter_manager_;
3071  int64 number_of_decisions_;
3072  int64 number_of_rejects_;
3073 };
3074 
3077  public:
3079  LocalSearchFilterManager* filter_manager);
3082  const Assignment* BuildSolutionFromRoutes(
3083  const std::function<int64(int64)>& next_accessor);
3084  RoutingModel* model() const { return model_; }
3086  int GetStartChainEnd(int vehicle) const { return start_chain_ends_[vehicle]; }
3088  int GetEndChainStart(int vehicle) const { return end_chain_starts_[vehicle]; }
3091  void MakeDisjunctionNodesUnperformed(int64 node);
3093  void MakeUnassignedNodesUnperformed();
3098  void MakePartiallyPerformedPairsUnperformed();
3099 
3100  protected:
3101  bool StopSearch() override { return model_->CheckLimit(); }
3102  virtual void SetVehicleIndex(int64 node, int vehicle) {}
3103  virtual void ResetVehicleIndices() {}
3104  bool VehicleIsEmpty(int vehicle) const {
3105  return Value(model()->Start(vehicle)) == model()->End(vehicle);
3106  }
3107 
3108  private:
3110  bool InitializeSolution() override;
3111 
3112  RoutingModel* const model_;
3113  std::vector<int64> start_chain_ends_;
3114  std::vector<int64> end_chain_starts_;
3115 };
3116 
3118  public:
3121  RoutingModel* model, std::function<int64(int64, int64, int64)> evaluator,
3122  std::function<int64(int64)> penalty_evaluator,
3123  LocalSearchFilterManager* filter_manager);
3125 
3126  protected:
3127  typedef std::pair<int64, int64> ValuedPosition;
3128  struct StartEndValue {
3130  int vehicle;
3131 
3132  bool operator<(const StartEndValue& other) const {
3133  return std::tie(distance, vehicle) <
3134  std::tie(other.distance, other.vehicle);
3135  }
3136  };
3137  typedef std::pair<StartEndValue, /*seed_node*/ int> Seed;
3138 
3144  // clang-format off
3145  std::vector<std::vector<StartEndValue> >
3146  ComputeStartEndDistanceForVehicles(const std::vector<int>& vehicles);
3147 
3152  template <class Queue>
3154  std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
3155  Queue* priority_queue);
3156  // clang-format on
3157 
3162  void InsertBetween(int64 node, int64 predecessor, int64 successor);
3167  void AppendEvaluatedPositionsAfter(
3168  int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle,
3169  std::vector<ValuedPosition>* valued_positions);
3174  // TODO(user): Replace 'insert_before' and 'insert_after' by 'predecessor'
3175  // and 'successor' in the code.
3176  int64 GetInsertionCostForNodeAtPosition(int64 node_to_insert,
3177  int64 insert_after,
3178  int64 insert_before,
3179  int vehicle) const;
3182  int64 GetUnperformedValue(int64 node_to_insert) const;
3183 
3184  std::function<int64(int64, int64, int64)> evaluator_;
3185  std::function<int64(int64)> penalty_evaluator_;
3186 };
3187 
3197  public:
3220  };
3221 
3224  RoutingModel* model, std::function<int64(int64, int64, int64)> evaluator,
3225  std::function<int64(int64)> penalty_evaluator,
3226  LocalSearchFilterManager* filter_manager,
3229  bool BuildSolutionInternal() override;
3230  std::string DebugString() const override {
3231  return "GlobalCheapestInsertionFilteredHeuristic";
3232  }
3233 
3234  private:
3235  class PairEntry;
3236  class NodeEntry;
3237  typedef absl::flat_hash_set<PairEntry*> PairEntries;
3238  typedef absl::flat_hash_set<NodeEntry*> NodeEntries;
3239 
3246  void InsertPairsAndNodesByRequirementTopologicalOrder();
3247 
3254  void InsertPairs(const std::vector<int>& pair_indices);
3255 
3262  bool InsertPairEntryUsingEmptyVehicleTypeCurator(
3263  const std::vector<int>& pair_indices, PairEntry* const pair_entry,
3264  AdjustablePriorityQueue<PairEntry>* priority_queue,
3265  std::vector<PairEntries>* pickup_to_entries,
3266  std::vector<PairEntries>* delivery_to_entries);
3267 
3275  void InsertNodesOnRoutes(const std::vector<int>& nodes,
3276  const absl::flat_hash_set<int>& vehicles);
3277 
3285  bool InsertNodeEntryUsingEmptyVehicleTypeCurator(
3286  const std::vector<int>& nodes, bool all_vehicles,
3287  NodeEntry* const node_entry,
3288  AdjustablePriorityQueue<NodeEntry>* priority_queue,
3289  std::vector<NodeEntries>* position_to_node_entries);
3290 
3296  void SequentialInsertNodes(const std::vector<int>& nodes);
3297 
3301  void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,
3302  std::vector<int>* unused_vehicles,
3303  absl::flat_hash_set<int>* used_vehicles);
3304 
3308  void InsertFarthestNodesAsSeeds();
3309 
3318  template <class Queue>
3319  int InsertSeedNode(
3320  std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
3321  Queue* priority_queue, std::vector<bool>* is_vehicle_used);
3322  // clang-format on
3323 
3326  void InitializePairPositions(
3327  const std::vector<int>& pair_indices,
3328  AdjustablePriorityQueue<PairEntry>* priority_queue,
3329  std::vector<PairEntries>* pickup_to_entries,
3330  std::vector<PairEntries>* delivery_to_entries);
3336  void InitializeInsertionEntriesPerformingPair(
3337  int64 pickup, int64 delivery,
3338  AdjustablePriorityQueue<PairEntry>* priority_queue,
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,
3346  int64 pickup_position, int64 delivery, int64 delivery_position,
3347  AdjustablePriorityQueue<PairEntry>* priority_queue,
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,
3353  int64 insert_after,
3354  AdjustablePriorityQueue<PairEntry>* priority_queue,
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);
3361  }
3364  void UpdatePickupPositions(const std::vector<int>& pair_indices, int vehicle,
3365  int64 pickup_insert_after,
3366  AdjustablePriorityQueue<PairEntry>* priority_queue,
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,
3374  AdjustablePriorityQueue<PairEntry>* priority_queue,
3375  std::vector<PairEntries>* pickup_to_entries,
3376  std::vector<PairEntries>* delivery_to_entries);
3379  void DeletePairEntry(PairEntry* entry,
3380  AdjustablePriorityQueue<PairEntry>* priority_queue,
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,
3389  AdjustablePriorityQueue<PairEntry>* priority_queue,
3390  std::vector<PairEntries>* pickup_entries,
3391  std::vector<PairEntries>* delivery_entries) const;
3394  void UpdatePairEntry(
3395  PairEntry* const pair_entry,
3396  AdjustablePriorityQueue<PairEntry>* priority_queue) const;
3400  int64 GetInsertionValueForPairAtPositions(int64 pickup,
3401  int64 pickup_insert_after,
3402  int64 delivery,
3403  int64 delivery_insert_after,
3404  int vehicle) const;
3405 
3408  void InitializePositions(const std::vector<int>& nodes,
3409  const absl::flat_hash_set<int>& vehicles,
3410  AdjustablePriorityQueue<NodeEntry>* priority_queue,
3411  std::vector<NodeEntries>* position_to_node_entries);
3417  void InitializeInsertionEntriesPerformingNode(
3418  int64 node, const absl::flat_hash_set<int>& vehicles,
3419  AdjustablePriorityQueue<NodeEntry>* priority_queue,
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,
3425  AdjustablePriorityQueue<NodeEntry>* priority_queue,
3426  std::vector<NodeEntries>* node_entries);
3429  void DeleteNodeEntry(NodeEntry* entry,
3430  AdjustablePriorityQueue<NodeEntry>* priority_queue,
3431  std::vector<NodeEntries>* node_entries);
3432 
3436  void AddNodeEntry(int64 node, int64 insert_after, int vehicle,
3437  bool all_vehicles,
3438  AdjustablePriorityQueue<NodeEntry>* priority_queue,
3439  std::vector<NodeEntries>* node_entries) const;
3442  void UpdateNodeEntry(
3443  NodeEntry* const node_entry,
3444  AdjustablePriorityQueue<NodeEntry>* priority_queue) const;
3445 
3448  void ComputeNeighborhoods();
3449 
3452  bool IsNeighborForCostClass(int cost_class, int64 node_index,
3453  int64 neighbor_index) const;
3454 
3456  const std::vector<int64>& GetNeighborsOfNodeForCostClass(
3457  int cost_class, int64 node_index) const {
3458  return gci_params_.neighbors_ratio == 1
3459  ? all_nodes_
3460  : node_index_to_neighbors_by_cost_class_[node_index][cost_class]
3461  ->PositionsSetAtLeastOnce();
3462  }
3463 
3464  int64 NumNonStartEndNodes() const {
3465  return model()->Size() - model()->vehicles();
3466  }
3467 
3468  int64 NumNeighbors() const {
3469  return std::max(gci_params_.min_neighbors,
3470  MathUtil::FastInt64Round(gci_params_.neighbors_ratio *
3471  NumNonStartEndNodes()));
3472  }
3473 
3474  void ResetVehicleIndices() override {
3475  node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);
3476  }
3477 
3478  void SetVehicleIndex(int64 node, int vehicle) override {
3479  DCHECK_LT(node, node_index_to_vehicle_.size());
3480  node_index_to_vehicle_[node] = vehicle;
3481  }
3482 
3485  bool CheckVehicleIndices() const;
3486 
3487  GlobalCheapestInsertionParameters gci_params_;
3489  std::vector<int> node_index_to_vehicle_;
3490 
3491  // clang-format off
3492  std::vector<std::vector<std::unique_ptr<SparseBitset<int64> > > >
3493  node_index_to_neighbors_by_cost_class_;
3494  // clang-format on
3495 
3496  std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;
3497 
3501  std::vector<int64> all_nodes_;
3502 };
3503 
3511  public:
3514  RoutingModel* model, std::function<int64(int64, int64, int64)> evaluator,
3515  LocalSearchFilterManager* filter_manager);
3517  bool BuildSolutionInternal() override;
3518  std::string DebugString() const override {
3519  return "LocalCheapestInsertionFilteredHeuristic";
3520  }
3521 
3522  private:
3528  void ComputeEvaluatorSortedPositions(int64 node,
3529  std::vector<int64>* sorted_positions);
3534  void ComputeEvaluatorSortedPositionsOnRouteAfter(
3535  int64 node, int64 start, int64 next_after_start,
3536  std::vector<int64>* sorted_positions);
3537 
3538  std::vector<std::vector<StartEndValue>> start_end_distances_per_node_;
3539 };
3540 
3544  public:
3546  LocalSearchFilterManager* filter_manager);
3548  bool BuildSolutionInternal() override;
3549 
3550  private:
3551  class PartialRoutesAndLargeVehicleIndicesFirst {
3552  public:
3553  explicit PartialRoutesAndLargeVehicleIndicesFirst(
3554  const CheapestAdditionFilteredHeuristic& builder)
3555  : builder_(builder) {}
3556  bool operator()(int vehicle1, int vehicle2) const;
3557 
3558  private:
3559  const CheapestAdditionFilteredHeuristic& builder_;
3560  };
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) {
3568  const int64 next = *it;
3569  if (next != node && (next >= size || !Contains(next))) {
3570  nexts.push_back(next);
3571  }
3572  }
3573  return nexts;
3574  }
3576  virtual void SortSuccessors(int64 node, std::vector<int64>* successors) = 0;
3577  virtual int64 FindTopSuccessor(int64 node,
3578  const std::vector<int64>& successors) = 0;
3579 };
3580 
3585  public:
3588  RoutingModel* model, std::function<int64(int64, int64)> evaluator,
3589  LocalSearchFilterManager* filter_manager);
3591  std::string DebugString() const override {
3592  return "EvaluatorCheapestAdditionFilteredHeuristic";
3593  }
3594 
3595  private:
3597  void SortSuccessors(int64 node, std::vector<int64>* successors) override;
3598  int64 FindTopSuccessor(int64 node,
3599  const std::vector<int64>& successors) override;
3600 
3601  std::function<int64(int64, int64)> evaluator_;
3602 };
3603 
3608  public:
3612  LocalSearchFilterManager* filter_manager);
3614  std::string DebugString() const override {
3615  return "ComparatorCheapestAdditionFilteredHeuristic";
3616  }
3617 
3618  private:
3620  void SortSuccessors(int64 node, std::vector<int64>* successors) override;
3621  int64 FindTopSuccessor(int64 node,
3622  const std::vector<int64>& successors) override;
3623 
3624  Solver::VariableValueComparator comparator_;
3625 };
3626 
3636  public:
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;
3650  };
3651 
3653  const RoutingIndexManager* manager,
3655  LocalSearchFilterManager* filter_manager);
3656  ~SavingsFilteredHeuristic() override;
3657  bool BuildSolutionInternal() override;
3658 
3659  protected:
3660  typedef std::pair</*saving*/ int64, /*saving index*/ int64> Saving;
3661 
3662  template <typename S>
3663  class SavingsContainer;
3664 
3665  virtual double ExtraSavingsMemoryMultiplicativeFactor() const = 0;
3666 
3667  virtual void BuildRoutesFromSavings() = 0;
3668 
3670  int64 GetVehicleTypeFromSaving(const Saving& saving) const {
3671  return saving.second / size_squared_;
3672  }
3674  int64 GetBeforeNodeFromSaving(const Saving& saving) const {
3675  return (saving.second % size_squared_) / Size();
3676  }
3678  int64 GetAfterNodeFromSaving(const Saving& saving) const {
3679  return (saving.second % size_squared_) % Size();
3680  }
3682  int64 GetSavingValue(const Saving& saving) const { return saving.first; }
3683 
3693  int StartNewRouteWithBestVehicleOfType(int type, int64 before_node,
3694  int64 after_node);
3695 
3696  // clang-format off
3697  std::unique_ptr<SavingsContainer<Saving> > savings_container_;
3698  // clang-format on
3699  std::unique_ptr<VehicleTypeCurator> vehicle_type_curator_;
3700 
3701  private:
3706  // clang-format off
3707  void AddSymmetricArcsToAdjacencyLists(
3708  std::vector<std::vector<int64> >* adjacency_lists);
3709  // clang-format on
3710 
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);
3723  }
3724 
3728  int64 MaxNumNeighborsPerNode(int num_vehicle_types) const;
3729 
3730  const RoutingIndexManager* const manager_;
3731  const SavingsParameters savings_params_;
3732  int64 size_squared_;
3733 
3734  friend class SavingsFilteredHeuristicTestPeer;
3735 };
3736 
3738  public:
3740  const RoutingIndexManager* manager,
3742  LocalSearchFilterManager* filter_manager)
3743  : SavingsFilteredHeuristic(model, manager, parameters, filter_manager) {}
3745  std::string DebugString() const override {
3746  return "SequentialSavingsFilteredHeuristic";
3747  }
3748 
3749  private:
3754  void BuildRoutesFromSavings() override;
3755  double ExtraSavingsMemoryMultiplicativeFactor() const override { return 1.0; }
3756 };
3757 
3759  public:
3761  const RoutingIndexManager* manager,
3763  LocalSearchFilterManager* filter_manager)
3764  : SavingsFilteredHeuristic(model, manager, parameters, filter_manager) {}
3766  std::string DebugString() const override {
3767  return "ParallelSavingsFilteredHeuristic";
3768  }
3769 
3770  private:
3781  void BuildRoutesFromSavings() override;
3782 
3783  double ExtraSavingsMemoryMultiplicativeFactor() const override { return 2.0; }
3784 
3789  void MergeRoutes(int first_vehicle, int second_vehicle, int64 before_node,
3790  int64 after_node);
3791 
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_;
3799 };
3800 
3804 
3806  public:
3808  LocalSearchFilterManager* filter_manager,
3809  bool use_minimum_matching);
3811  bool BuildSolutionInternal() override;
3812  std::string DebugString() const override {
3813  return "ChristofidesFilteredHeuristic";
3814  }
3815 
3816  private:
3817  const bool use_minimum_matching_;
3818 };
3819 #endif // SWIG
3820 
3825 bool SolveModelWithSat(const RoutingModel& model,
3826  const RoutingSearchParameters& search_parameters,
3827  const Assignment* initial_solution,
3828  Assignment* solution);
3829 
3831 
3833  public:
3834  BasePathFilter(const std::vector<IntVar*>& nexts, int next_domain_size);
3835  ~BasePathFilter() override {}
3836  bool Accept(const Assignment* delta, const Assignment* deltadelta,
3837  int64 objective_min, int64 objective_max) override;
3838  void OnSynchronize(const Assignment* delta) override;
3839 
3840  protected:
3841  static const int64 kUnassigned;
3842 
3843  int64 GetNext(int64 node) const {
3844  return (new_nexts_[node] == kUnassigned)
3845  ? (IsVarSynced(node) ? Value(node) : kUnassigned)
3846  : new_nexts_[node];
3847  }
3848  int NumPaths() const { return starts_.size(); }
3849  int64 Start(int i) const { return starts_[i]; }
3850  int GetPath(int64 node) const { return paths_[node]; }
3851  int Rank(int64 node) const { return ranks_[node]; }
3852  bool IsDisabled() const { return status_ == DISABLED; }
3853  const std::vector<int64>& GetTouchedPathStarts() const {
3854  return touched_paths_.PositionsSetAtLeastOnce();
3855  }
3856  const std::vector<int64>& GetNewSynchronizedUnperformedNodes() const {
3857  return new_synchronized_unperformed_nodes_.PositionsSetAtLeastOnce();
3858  }
3859 
3860  private:
3861  enum Status { UNKNOWN, ENABLED, DISABLED };
3862 
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) {
3872  return true;
3873  }
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);
3881 
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_;
3889  // clang-format off
3890  std::vector<std::pair<int64, int64> > touched_path_chain_start_ends_;
3891  // clang-format on
3892  std::vector<int> ranks_;
3893 
3894  Status status_;
3895 };
3896 
3901 // TODO(user): Also call the solution finalizer on variables, with the
3907 // TODO(user): Avoid such false negatives.
3909  public:
3910  explicit CPFeasibilityFilter(RoutingModel* routing_model);
3911  ~CPFeasibilityFilter() override {}
3912  std::string DebugString() const override { return "CPFeasibilityFilter"; }
3913  bool Accept(const Assignment* delta, const Assignment* deltadelta,
3914  int64 objective_min, int64 objective_max) override;
3915  void OnSynchronize(const Assignment* delta) override;
3916 
3917  private:
3918  void AddDeltaToAssignment(const Assignment* delta, Assignment* assignment);
3919 
3920  static const int64 kUnassigned;
3921  const RoutingModel* const model_;
3922  Solver* const solver_;
3923  Assignment* const assignment_;
3924  Assignment* const temp_assignment_;
3925  DecisionBuilder* const restore_;
3926  SearchLimit* const limit_;
3927 };
3928 
3929 #if !defined(SWIG)
3930 IntVarLocalSearchFilter* MakeMaxActiveVehiclesFilter(
3931  const RoutingModel& routing_model);
3932 IntVarLocalSearchFilter* MakeNodeDisjunctionFilter(
3933  const RoutingModel& routing_model);
3934 IntVarLocalSearchFilter* MakeVehicleAmortizedCostFilter(
3935  const RoutingModel& routing_model);
3936 IntVarLocalSearchFilter* MakeTypeRegulationsFilter(
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);
3946 IntVarLocalSearchFilter* MakePathCumulFilter(
3947  const RoutingDimension& dimension,
3948  const RoutingSearchParameters& parameters,
3949  bool propagate_own_objective_value, bool filter_objective_cost,
3950  bool can_use_lp = true);
3951 IntVarLocalSearchFilter* MakeCumulBoundsPropagatorFilter(
3952  const RoutingDimension& dimension);
3953 IntVarLocalSearchFilter* MakeGlobalLPCumulFilter(
3954  GlobalDimensionCumulOptimizer* optimizer, bool filter_objective_cost);
3955 IntVarLocalSearchFilter* MakePickupDeliveryFilter(
3956  const RoutingModel& routing_model, const RoutingModel::IndexPairs& pairs,
3957  const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies);
3958 IntVarLocalSearchFilter* MakeVehicleVarFilter(
3959  const RoutingModel& routing_model);
3960 IntVarLocalSearchFilter* MakeVehicleBreaksFilter(
3961  const RoutingModel& routing_model, const RoutingDimension& dimension);
3962 IntVarLocalSearchFilter* MakeCPFeasibilityFilter(RoutingModel* routing_model);
3963 #endif
3964 
3965 } // namespace operations_research
3966 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
const std::vector< IntVar * > vars_
Definition: alldiff_cst.cc:43
int64 max
Definition: alldiff_cst.cc:139
#define CHECK(condition)
Definition: base/logging.h:495
#define CHECK_LT(val1, val2)
Definition: base/logging.h:700
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define LOG(severity)
Definition: base/logging.h:420
#define DCHECK(condition)
Definition: base/logging.h:884
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.
Definition: routing.h:3832
const std::vector< int64 > & GetTouchedPathStarts() const
Definition: routing.h:3853
static const int64 kUnassigned
Definition: routing.h:3841
const std::vector< int64 > & GetNewSynchronizedUnperformedNodes() const
Definition: routing.h:3856
int Rank(int64 node) const
Definition: routing.h:3851
int64 GetNext(int64 node) const
Definition: routing.h:3843
int GetPath(int64 node) const
Definition: routing.h:3850
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
Definition: routing.h:3908
std::string DebugString() const override
Definition: routing.h:3912
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
Definition: routing.h:3543
std::function< int64(int64, int64, int64)> evaluator_
Definition: routing.h:3184
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,...
Christofides addition heuristic.
Definition: routing.h:3805
std::string DebugString() const override
Definition: routing.h:3812
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc comparator.
Definition: routing.h:3607
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...
Definition: routing.h:1954
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc evaluator.
Definition: routing.h:3584
Filter-based decision builder which builds a solution by inserting nodes at their cheapest position o...
Definition: routing.h:3196
GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimensio...
Definition: routing.h:2062
std::string DebugString() const override
Definition: routing.h:2065
Decision builder building a solution using heuristics with local search filters to evaluate its feasi...
Definition: routing.h:2977
Generic filter-based heuristic applied to IntVars.
Definition: routing.h:2997
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.
Definition: routing.h:3050
bool Contains(int64 index) const
Returns true if the variable of index 'index' is in the current solution.
Definition: routing.h:3045
int64 Value(int64 index) const
Returns the value of the variable of index 'index' in the last committed solution.
Definition: routing.h:3041
IntVar * Var(int64 index) const
Returns the variable of index 'index'.
Definition: routing.h:3052
virtual bool StopSearch()
Returns true if the search must be stopped.
Definition: routing.h:3027
virtual std::string DebugString() const
Definition: routing.h:3013
virtual bool InitializeSolution()
Virtual method to initialize the solution.
Definition: routing.h:3019
int64 number_of_decisions() const
Returns statistics on search, number of decisions sent to filters, number of decisions rejected by fi...
Definition: routing.h:3010
void SetValue(int64 index, int64 value)
Modifies the current solution by setting the variable of index 'index' to value 'value'.
Definition: routing.h:3030
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.
Definition: routing.h:3510
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)
Definition: routing.h:3760
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
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 * (...
Definition: routing.h:2717
SimpleBoundCosts::BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2710
void AddNodePrecedence(int64 first_node, int64 second_node, int64 offset)
Definition: routing.h:2661
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...
Definition: routing.h:2379
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
Definition: routing.h:2394
int64 global_span_cost_coefficient() const
Definition: routing.h:2681
int64 GetSpanCostCoefficientForVehicle(int vehicle) const
Definition: routing.h:2673
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 * (...
Definition: routing.h:2699
RoutingModel * model() const
Returns the model on which the dimension was created.
Definition: routing.h:2372
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
Definition: routing.h:2386
const RoutingModel::TransitCallback1 & GetUnaryTransitEvaluator(int vehicle) const
Returns the unary callback evaluating the transit value between two node indices for a given vehicle.
Definition: routing.h:2456
IntVar * FixedTransitVar(int64 index) const
Definition: routing.h:2388
const std::vector< int64 > & vehicle_capacities() const
Returns the capacities for all vehicles.
Definition: routing.h:2444
std::function< int64(int, int)> PickupToDeliveryLimitFunction
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery a...
Definition: routing.h:2637
bool AreVehicleTransitsPositive(int vehicle) const
Returns true iff the transit evaluator of 'vehicle' is positive for all arcs.
Definition: routing.h:2463
const std::vector< IntVar * > & fixed_transits() const
Definition: routing.h:2395
const std::vector< IntVar * > & transits() const
Definition: routing.h:2396
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
Definition: routing.h:2608
void AddNodePrecedence(NodePrecedence precedence)
Definition: routing.h:2653
int64 GetLocalOptimizerOffsetForVehicle(int vehicle) const
Definition: routing.h:2689
const std::vector< int64 > & vehicle_span_upper_bounds() const
Definition: routing.h:2669
bool HasQuadraticCostSoftSpanUpperBounds() const
Definition: routing.h:2727
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...
Definition: routing.h:2409
int vehicle_to_class(int vehicle) const
Definition: routing.h:2467
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
Definition: routing.h:2449
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 ...
Definition: routing.h:2428
IntVar * TransitVar(int64 index) const
Definition: routing.h:2387
IntVar * SlackVar(int64 index) const
Definition: routing.h:2389
const std::vector< int64 > & vehicle_span_cost_coefficients() const
Definition: routing.h:2677
const ReverseArcListGraph< int, int > & GetPathPrecedenceGraph() const
Accessors.
Definition: routing.h:2623
const std::string & name() const
Returns the name of the dimension.
Definition: routing.h:2619
const std::vector< IntVar * > & slacks() const
Definition: routing.h:2397
const std::vector< NodePrecedence > & GetNodePrecedences() const
Definition: routing.h:2656
SimpleBoundCosts::BoundCost GetQuadraticCostSoftSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2730
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
Definition: routing.h:2400
int64 GetSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2665
Filter-based heuristic dedicated to routing.
Definition: routing.h:3076
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
Definition: routing.h:3086
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
Definition: routing.h:3088
virtual void SetVehicleIndex(int64 node, int vehicle)
Definition: routing.h:3102
bool StopSearch() override
Returns true if the search must be stopped.
Definition: routing.h:3101
bool VehicleIsEmpty(int vehicle) const
Definition: routing.h:3104
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)
Definition: routing.cc:903
std::pair< int, bool > AddConstantDimension(int64 value, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Definition: routing.h:473
const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > & GetPickupAndDeliveryDisjunctions() const
Definition: routing.h:750
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
Definition: routing.h:608
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...
Definition: routing.cc:952
std::function< std::vector< operations_research::IntVar * >(RoutingModel *)> GetTabuVarsCallback
Sets the callback returning the variable to use for the Tabu Search metaheuristic.
Definition: routing.h:1368
int nodes() const
Sizes and indices Returns the number of nodes in the model.
Definition: routing.h:1343
const std::vector< int > & GetSameVehicleIndicesOfIndex(int node) const
Returns variable indices of nodes constrained to be on the same route.
Definition: routing.h:1280
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
Definition: routing.h:663
RoutingIndexPair IndexPair
Definition: routing.h:247
IntVar * ActiveVehicleVar(int vehicle) const
Returns the active variable of the vehicle.
Definition: routing.h:1212
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:242
const std::vector< std::vector< int > > & GetTopologicallySortedVisitTypes() const
Definition: routing.h:803
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 ...
Definition: routing.h:639
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
Definition: routing.h:1251
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
Definition: routing.h:1278
int64 Size() const
Returns the number of next variables in the model.
Definition: routing.h:1347
Assignment * MutablePreAssignment()
Definition: routing.h:1067
bool CheckLimit()
Returns true if the search limit has been crossed.
Definition: routing.h:1330
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
Definition: routing.cc:851
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
Definition: routing.h:694
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulOptimizers() const
Definition: routing.h:572
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
Definition: routing.h:417
VisitTypePolicy
Set the node visit types and incompatibilities/requirements between the types (see below).
Definition: routing.h:773
@ TYPE_ADDED_TO_VEHICLE
When visited, the number of types 'T' on the vehicle increases by one.
Definition: routing.h:775
@ ADDED_TYPE_REMOVED_FROM_VEHICLE
When visited, one instance of type 'T' previously added to the route (TYPE_ADDED_TO_VEHICLE),...
Definition: routing.h:780
@ TYPE_ON_VEHICLE_UP_TO_VISIT
With the following policy, the visit enforces that type 'T' is considered on the route from its start...
Definition: routing.h:783
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.
Definition: routing.h:510
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
Creates a cached StateDependentTransit from an std::function.
Definition: routing.cc:1111
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
For every vehicle of the routing model:
Definition: routing.cc:5927
LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer(const RoutingDimension &dimension) const
Definition: routing.cc:1142
void AddLocalSearchFilter(LocalSearchFilter *filter)
Adds a custom local search filter to the list of filters used to speed up local search by pruning unf...
Definition: routing.h:1169
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
Definition: routing.cc:1181
bool HasTemporalTypeRequirements() const
Definition: routing.h:870
Solver * solver() const
Returns the underlying constraint solver.
Definition: routing.h:1327
RoutingTransitCallback2 TransitCallback2
Definition: routing.h:243
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
Definition: routing.h:559
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
Definition: routing.cc:1121
const Solver::IndexEvaluator2 & first_solution_evaluator() const
Gets/sets the evaluator used during the search.
Definition: routing.h:963
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Definition: routing.cc:885
IntVar * NextVar(int64 index) const
!defined(SWIGPYTHON)
Definition: routing.h:1207
std::function< StateDependentTransit(int64, int64)> VariableIndexEvaluator2
Definition: routing.h:269
Status
Status of the search.
Definition: routing.h:216
@ ROUTING_SUCCESS
Problem solved successfully after calling RoutingModel::Solve().
Definition: routing.h:220
@ ROUTING_FAIL
No solution found to the problem after calling RoutingModel::Solve().
Definition: routing.h:222
@ ROUTING_NOT_SOLVED
Problem not solved yet (before calling RoutingModel::Solve()).
Definition: routing.h:218
@ ROUTING_INVALID
Model, model parameters or flags are not valid.
Definition: routing.h:226
@ ROUTING_FAIL_TIMEOUT
Time limit reached before finding a solution with RoutingModel::Solve().
Definition: routing.h:224
bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const
Returns true iff the model contains a vehicle with the given cost_class_index.
Definition: routing.h:1260
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
Definition: routing.cc:4996
void SetSweepArranger(SweepArranger *sweep_arranger)
Definition: routing.h:1158
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
Definition: routing.h:1162
RoutingIndexPairs IndexPairs
Definition: routing.h:248
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
Definition: routing.h:1273
IntVar * VehicleCostsConsideredVar(int vehicle) const
Returns the variable specifying whether or not costs are considered for vehicle.
Definition: routing.h:1217
void ConsiderEmptyRouteCostsForVehicle(bool consider_costs, int vehicle)
Definition: routing.h:950
int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback)
Definition: routing.cc:810
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
Definition: routing.h:1203
void SetMaximumNumberOfActiveVehicles(int max_active_vehicles)
Constrains the maximum number of active vehicles, aka the number of vehicles which do not have an emp...
Definition: routing.h:900
const IndexPairs & GetImplicitUniquePickupAndDeliveryPairs() const
Returns implicit pickup and delivery pairs currently in the model.
Definition: routing.h:757
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; ...
Definition: routing.cc:963
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
Definition: routing.h:631
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
Definition: routing.h:384
int RegisterTransitCallback(TransitCallback2 callback)
Definition: routing.cc:818
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
Definition: routing.h:1222
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulMPOptimizers() const
Definition: routing.h:576
int GetMaximumNumberOfActiveVehicles() const
Returns the maximum number of active vehicles.
Definition: routing.h:904
RoutingDimensionIndex DimensionIndex
Definition: routing.h:239
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...
Definition: routing.cc:972
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.
Definition: routing.cc:1575
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
Definition: routing.cc:1154
bool HasHardTypeIncompatibilities() const
Returns true iff any hard (resp.
Definition: routing.h:822
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:746
const std::vector< int64 > & GetAmortizedLinearCostFactorOfVehicles() const
Definition: routing.h:943
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...
Definition: routing.h:1236
int RegisterPositiveTransitCallback(TransitCallback2 callback)
Definition: routing.cc:844
PickupAndDeliveryPolicy
Types of precedence policy applied to pickup and delivery pairs.
Definition: routing.h:230
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
Definition: routing.h:234
@ PICKUP_AND_DELIVERY_NO_ORDER
Any precedence is accepted.
Definition: routing.h:232
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
Definition: routing.h:236
int vehicles() const
Returns the number of vehicle routes in the model.
Definition: routing.h:1345
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
Definition: routing.h:667
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...
Definition: routing.h:1200
const std::vector< int64 > & GetAmortizedQuadraticCostFactorOfVehicles() const
Definition: routing.h:946
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...
Definition: routing.h:1189
bool HasTypeRegulations() const
Returns true iff the model has any incompatibilities or requirements set on node types.
Definition: routing.h:876
void SetFirstSolutionEvaluator(Solver::IndexEvaluator2 evaluator)
Takes ownership of evaluator.
Definition: routing.h:968
RoutingVehicleClassIndex VehicleClassIndex
Definition: routing.h:241
int RegisterUnaryTransitVector(std::vector< int64 > values)
Registers 'callback' and returns its index.
Definition: routing.cc:772
bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
Definition: routing.cc:875
int GetNonZeroCostClassesCount() const
Ditto, minus the 'always zero', built-in cost class.
Definition: routing.h:1270
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
Definition: routing.cc:1130
bool HasSameVehicleTypeRequirements() const
Returns true iff any same-route (resp.
Definition: routing.h:867
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
Definition: routing.h:1224
void SetPrimaryConstrainedDimension(const std::string &dimension_name)
Set the given dimension as "primary constrained".
Definition: routing.h:603
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
Definition: routing.h:421
int RegisterTransitMatrix(std::vector< std::vector< int64 > > values)
Definition: routing.cc:791
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
Definition: routing.cc:894
int RegisterUnaryTransitCallback(TransitCallback1 callback)
Definition: routing.cc:783
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
RoutingCostClassIndex CostClassIndex
Definition: routing.h:238
bool HasTemporalTypeIncompatibilities() const
Definition: routing.h:825
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
Definition: routing.h:1268
const TransitCallback2 & TransitCallback(int callback_index) const
Definition: routing.h:413
const std::vector< std::unique_ptr< GlobalDimensionCumulOptimizer > > & GetGlobalDimensionCumulOptimizers() const
Returns [global|local]_dimension_optimizers_, which are empty if the model has not been closed.
Definition: routing.h:568
operations_research::FirstSolutionStrategy::Value GetAutomaticFirstSolutionStrategy() const
Returns the automatic first solution strategy selected.
Definition: routing.h:1357
absl::Duration RemainingTime() const
Returns the time left in the search limit.
Definition: routing.h:1336
Status status() const
Returns the current status of the routing model.
Definition: routing.h:1042
const std::vector< int64 > & GetDisjunctionIndices(DisjunctionIndex index) const
Returns the variable indices of the nodes in the disjunction of index 'index'.
Definition: routing.h:652
static const DimensionIndex kNoDimension
Constant used to express the "no dimension" index, returned when a dimension name does not correspond...
Definition: routing.h:392
const Assignment *const PreAssignment() const
Returns an assignment used to fix some of the variables of the problem.
Definition: routing.h:1066
bool CostsAreHomogeneousAcrossVehicles() const
Whether costs are homogeneous across all vehicles.
Definition: routing.h:1231
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
const VehicleTypeContainer & GetVehicleTypeContainer() const
Definition: routing.h:1285
static const DisjunctionIndex kNoDisjunction
Constant used to express the "no disjunction" index, returned when a node does not appear in any disj...
Definition: routing.h:388
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
Definition: routing.cc:1166
bool AreEmptyRouteCostsConsideredForVehicle(int vehicle) const
Definition: routing.h:955
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
Definition: routing.cc:645
RoutingDisjunctionIndex DisjunctionIndex
Definition: routing.h:240
IntVar * ActiveVar(int64 index) const
Returns the active variable of the node corresponding to index.
Definition: routing.h:1209
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
Definition: routing.cc:1176
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
Definition: routing.h:3635
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
Definition: routing.h:3699
int64 GetVehicleTypeFromSaving(const Saving &saving) const
Returns the cost class from a saving.
Definition: routing.h:3670
std::unique_ptr< SavingsContainer< Saving > > savings_container_
Definition: routing.h:3697
int64 GetSavingValue(const Saving &saving) const
Returns the saving value from a saving.
Definition: routing.h:3682
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int64 GetBeforeNodeFromSaving(const Saving &saving) const
Returns the "before node" from a saving.
Definition: routing.h:3674
int64 GetAfterNodeFromSaving(const Saving &saving) const
Returns the "after node" from a saving.
Definition: routing.h:3678
Base class of all search limits.
A search monitor is a simple set of callbacks to monitor all search events.
SequentialSavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
Definition: routing.h:3739
A structure meant to store soft bounds and associated violation constants.
Definition: routing.h:2329
BoundCost & bound_cost(int element)
Definition: routing.h:2337
SimpleBoundCosts(int num_bounds, BoundCost default_bound_cost)
Definition: routing.h:2335
BoundCost bound_cost(int element) const
Definition: routing.h:2338
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 FirstIntervalGreaterOrEqual(int64 value) const
Returns an iterator to either:
Class to arrange indices by by their distance and their angles from the depot.
Definition: routing.h:2869
void SetSectors(int sectors)
Definition: routing.h:2874
Checker for type incompatibilities.
Definition: routing.h:2220
virtual bool HasRegulationsToCheck() const =0
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
The following constraint ensures that incompatibilities and requirements between types are respected.
Definition: routing.h:2300
Checker for type requirements.
Definition: routing.h:2236
TypeRequirementChecker(const RoutingModel &model)
Definition: routing.h:2238
Helper class that manages vehicles.
Definition: routing.h:2894
VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)
Definition: routing.h:2896
void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64 fixed_cost)
Definition: routing.h:2924
int GetLowestFixedCostVehicleOfType(int type) const
Definition: routing.h:2912
Block * next
SatParameters parameters
const std::string name
int64 value
IntVar * var
Definition: expr_array.cc:1858
const int64 limit_
const std::vector< IntVar * > cumuls_
GRBmodel * model
MPCallback * callback
static const int64 kint64max
int64_t int64
uint64_t uint64
const int WARNING
Definition: log_severity.h:31
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
Definition: macros.h:29
std::function< int64(const Model &)> Value(IntegerVariable v)
Definition: integer.h:1487
CpSolverResponse SolveWithParameters(const CpModelProto &model_proto, const SatParameters &params)
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.
Definition: routing_sat.cc:505
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
std::pair< std::vector< int64 >, std::vector< int64 > > RoutingIndexPair
Definition: routing_types.h:44
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters &parameters, 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
Definition: routing_types.h:42
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
std::function< int64(int64)> RoutingTransitCallback1
Definition: routing_types.h:41
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)
Definition: routing.cc:6215
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
static const int kUnassigned
Definition: routing.cc:638
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
Definition: routing_types.h:45
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...
Definition: routing.cc:143
int index
Definition: pack.cc:508
int64 delta
Definition: resource.cc:1684
IntervalVar * interval
Definition: resource.cc:98
int64 cost
int64 capacity
int64 bound
int64 coefficient
Rev< int64 > end_min
Rev< int64 > end_max
Rev< int64 > start_max
Rev< int64 > start_min
std::function< int64(int64, int64)> evaluator_
Definition: search.cc:1361
A structure to hold tasks described by their features.
Definition: routing.h:1961
std::vector< const SortedDisjointIntervalList * > forbidden_intervals
Definition: routing.h:1970
std::vector< std::pair< int64, int64 > > distance_duration
Definition: routing.h:1971
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
Definition: routing.h:3209
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
Definition: routing.h:3200
double farthest_seeds_ratio
The ratio of routes on which to insert farthest nodes as seeds before starting the cheapest insertion...
Definition: routing.h:3203
bool use_neighbors_ratio_for_initialization
If true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion p...
Definition: routing.h:3214
bool add_unperformed_entries
If true, entries are created for making the nodes/pairs unperformed, and when the cost of making a no...
Definition: routing.h:3219
SUBTLE: The vehicle's fixed cost is skipped on purpose here, because we can afford to do so:
Definition: routing.h:297
bool operator<(const DimensionCost &cost) const
Definition: routing.h:301
int evaluator_index
Index of the arc cost evaluator, registered in the RoutingModel class.
Definition: routing.h:275
static bool LessThan(const CostClass &a, const CostClass &b)
Comparator for STL containers and algorithms.
Definition: routing.h:315
std::vector< DimensionCost > dimension_transit_evaluator_class_and_cost_coefficient
Definition: routing.h:309
What follows is relevant for models with time/state dependent transits.
Definition: routing.h:264
RangeMinMaxIndexFunction * transit_plus_identity
f(x)
Definition: routing.h:266
int64 fixed_cost
Contrarily to CostClass, here we need strict equivalence.
Definition: routing.h:328
absl::StrongVector< DimensionIndex, int64 > dimension_capacities
Definition: routing.h:343
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.
Definition: routing.h:346
int start_equivalence_class
Vehicle start and end equivalence classes.
Definition: routing.h:335
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_min
Bounds of cumul variables at start and end vehicle nodes.
Definition: routing.h:339
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_min
Definition: routing.h:341
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_max
Definition: routing.h:342
uint64 unvisitable_nodes_fprint
Fingerprint of unvisitable non-start/end nodes.
Definition: routing.h:348
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
Definition: routing.cc:1324
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_max
Definition: routing.h:340
CostClassIndex cost_class_index
The cost class of the vehicle.
Definition: routing.h:326
Definition: routing.h:359
int64 fixed_cost
Definition: routing.h:361
bool operator<(const VehicleClassEntry &other) const
Definition: routing.h:363
int vehicle_class
Definition: routing.h:360
Struct used to sort and store vehicles by their type.
Definition: routing.h:358
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
Definition: routing.h:378
std::vector< std::deque< int > > vehicles_per_vehicle_class
Definition: routing.h:379
std::vector< int64 > max_travels
Definition: routing.h:2033
std::vector< int64 > min_travels
Definition: routing.h:2032
std::vector< int64 > post_travels
Definition: routing.h:2035
std::vector< int64 > pre_travels
Definition: routing.h:2034