C++ Reference

C++ Reference: Routing

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"
174 #include "ortools/base/adjustable_priority_queue-inl.h"
175 #include "ortools/base/adjustable_priority_queue.h"
176 #include "ortools/base/commandlineflags.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"
191 #include "ortools/lp_data/lp_types.h"
192 #include "ortools/sat/theta_tree.h"
193 #include "ortools/util/range_query_function.h"
194 #include "ortools/util/sorted_interval_list.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
208 using util::ReverseArcListGraph;
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)
265  RangeIntToIntFunction* transit;
266  RangeMinMaxIndexFunction* transit_plus_identity;
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 {
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  }
321  }
322  };
323 
324  struct VehicleClass {
328  int64 fixed_cost;
333  // TODO(user): Find equivalent start/end nodes wrt dimensions and
334  // callbacks.
339  absl::StrongVector<DimensionIndex, int64> dimension_start_cumuls_min;
340  absl::StrongVector<DimensionIndex, int64> dimension_start_cumuls_max;
341  absl::StrongVector<DimensionIndex, int64> dimension_end_cumuls_min;
342  absl::StrongVector<DimensionIndex, int64> dimension_end_cumuls_max;
343  absl::StrongVector<DimensionIndex, int64> dimension_capacities;
346  absl::StrongVector<DimensionIndex, int64> dimension_evaluator_classes;
349 
351  static bool LessThan(const VehicleClass& a, const VehicleClass& b);
352  };
353 #endif // defined(SWIG)
354 
361  int64 fixed_cost;
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);
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);
473  std::pair<int, bool> AddConstantDimension(int64 value, int64 capacity,
474  bool fix_start_cumul_to_zero,
475  const std::string& name) {
476  return AddConstantDimensionWithSlack(value, capacity, 0,
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;
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);
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 
736  int vehicle);
738  int vehicle) const;
741 
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;
798  // TODO(user): Reconsider the logic and potentially remove the need to
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  }
839  int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
845  int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
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> >&
859  const std::vector<absl::flat_hash_set<int> >&
862  const std::vector<absl::flat_hash_set<int> >&
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  }
975  void AddSearchMonitor(SearchMonitor* const monitor);
979  void AddAtSolutionCallback(std::function<void()> callback);
993  void AddVariableTargetToFinalizer(IntVar* var, int64 target);
1000  void CloseModel();
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);
1023  const Assignment* assignment,
1024  const RoutingSearchParameters& search_parameters,
1025  std::vector<const Assignment*>* solutions = nullptr);
1032  Assignment* target_assignment, const RoutingModel* source_model,
1033  const Assignment* source_assignment);
1039  // TODO(user): Add support for non-homogeneous costs and disjunctions.
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);
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;
1142  void AddToAssignment(IntVar* const var);
1143  void AddIntervalToAssignment(IntervalVar* const interval);
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);
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 
1352  const RoutingSearchParameters& search_parameters) const;
1354  const RoutingSearchParameters& search_parameters) const;
1356  operations_research::FirstSolutionStrategy::Value
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.
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
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_;
1740  absl::StrongVector<DimensionIndex, RoutingDimension*> dimensions_;
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
1776  absl::StrongVector<CostClassIndex, CostClass> cost_classes_;
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
1783  absl::StrongVector<VehicleClassIndex, VehicleClass> vehicle_classes_;
1784 #endif // SWIG
1785  VehicleTypeContainer vehicle_type_container_;
1786  std::function<int(int64)> vehicle_start_class_callback_;
1788  absl::StrongVector<DisjunctionIndex, Disjunction> disjunctions_;
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;
1937  friend class RoutingModelInspector;
1938 
1939  DISALLOW_COPY_AND_ASSIGN(RoutingModel);
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);
2008  bool DistanceDuration(Tasks* tasks);
2011  bool ChainSpanMin(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:
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:
2238  explicit TypeRequirementChecker(const RoutingModel& model)
2239  : TypeRegulationsChecker(model) {}
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 {
2332  int64 bound;
2333  int64 cost;
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:
2372  RoutingModel* model() const { return model_; }
2376  int64 GetTransitValue(int64 from_index, int64 to_index, int64 vehicle) const;
2379  int64 GetTransitValueFromClass(int64 from_index, int64 to_index,
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
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);
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> >&
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
2623  const ReverseArcListGraph<int, int>& GetPathPrecedenceGraph() const {
2624  return path_precedence_graph_;
2625  }
2626 #endif // SWIG
2627 
2637  typedef std::function<int64(int, int)> PickupToDeliveryLimitFunction;
2638 
2640  PickupToDeliveryLimitFunction limit_function, int pair_index);
2641 
2643 #ifndef SWIG
2644  int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup,
2645  int delivery) const;
2646 
2648  int64 first_node;
2650  int64 offset;
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
2673  int64 GetSpanCostCoefficientForVehicle(int vehicle) const {
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  }
2689  int64 GetLocalOptimizerOffsetForVehicle(int vehicle) const {
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;
2741  int64 coefficient;
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;
2857  friend class RoutingModelInspector;
2859  const std::vector<RoutingDimension*>& dimensions,
2860  const RoutingSearchParameters& parameters, bool filter_objective_cost,
2861  std::vector<LocalSearchFilterManager::FilterEvent>* filters);
2862 
2863  DISALLOW_COPY_AND_ASSIGN(RoutingDimension);
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 
2880  DISALLOW_COPY_AND_ASSIGN(SweepArranger);
2881 };
2882 #endif
2883 
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 
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:
3019  virtual bool InitializeSolution() { return true; }
3021  virtual bool BuildSolutionInternal() = 0;
3025  bool Commit();
3027  virtual bool StopSearch() { return false; }
3030  void SetValue(int64 index, int64 value) {
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  }
3041  int64 Value(int64 index) const {
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]; }
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);
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]; }
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 {
3129  int64 distance;
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);
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:
3611  RoutingModel* model, Solver::VariableValueComparator comparator,
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,
3654  SavingsParameters parameters,
3655  LocalSearchFilterManager* filter_manager);
3657  bool BuildSolutionInternal() override;
3658 
3659  protected:
3660  typedef std::pair</*saving*/ int64, /*saving index*/ int64> Saving;
3661 
3662  template <typename S>
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,
3741  SavingsParameters parameters,
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,
3762  SavingsParameters parameters,
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 
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)
3931  const RoutingModel& routing_model);
3933  const RoutingModel& routing_model);
3935  const RoutingModel& routing_model);
3937  const RoutingModel& routing_model);
3939  const std::vector<RoutingDimension*>& dimensions,
3940  const RoutingSearchParameters& parameters, bool filter_objective_cost,
3941  std::vector<LocalSearchFilterManager::FilterEvent>* filters);
3943  const PathState* path_state,
3944  const std::vector<RoutingDimension*>& dimensions,
3945  std::vector<LocalSearchFilterManager::FilterEvent>* filters);
3947  const RoutingDimension& dimension,
3948  const RoutingSearchParameters& parameters,
3949  bool propagate_own_objective_value, bool filter_objective_cost,
3950  bool can_use_lp = true);
3952  const RoutingDimension& dimension);
3954  GlobalDimensionCumulOptimizer* optimizer, bool filter_objective_cost);
3956  const RoutingModel& routing_model, const RoutingModel::IndexPairs& pairs,
3957  const std::vector<RoutingModel::PickupAndDeliveryPolicy>& vehicle_policies);
3959  const RoutingModel& routing_model);
3961  const RoutingModel& routing_model, const RoutingDimension& dimension);
3963 #endif
3964 
3965 } // namespace operations_research
3966 #endif // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_H_
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
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
const std::vector< int64 > & GetNewSynchronizedUnperformedNodes() const
Definition: routing.h:3856
BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size)
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
void OnSynchronize(const Assignment *delta) override
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
Definition: routing.h:3908
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
CPFeasibilityFilter(RoutingModel *routing_model)
std::string DebugString() const override
Definition: routing.h:3912
void OnSynchronize(const Assignment *delta) override
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
Definition: routing.h:3543
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
CheapestAdditionFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(const std::vector< int > &vehicles)
Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::ve...
std::function< int64(int64, int64, int64)> evaluator_
Definition: routing.h:3184
void InsertBetween(int64 node, int64 predecessor, int64 successor)
Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subs...
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,...
void AppendEvaluatedPositionsAfter(int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle, std::vector< ValuedPosition > *valued_positions)
Helper method to the ComputeEvaluatorSortedPositions* methods.
int64 GetUnperformedValue(int64 node_to_insert) const
Returns the cost of unperforming node 'node_to_insert'.
int64 GetInsertionCostForNodeAtPosition(int64 node_to_insert, int64 insert_after, int64 insert_before, int vehicle) const
Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'veh...
Christofides addition heuristic.
Definition: routing.h:3805
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
std::string DebugString() const override
Definition: routing.h:3812
ChristofidesFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc comparator.
Definition: routing.h:3607
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
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
bool EdgeFinding(Tasks *tasks)
Does edge-finding deductions on all tasks.
bool Precedences(Tasks *tasks)
Propagates the deductions from the chain of precedences, if there is one.
bool DistanceDuration(Tasks *tasks)
Propagates distance_duration constraints, if any.
bool MirrorTasks(Tasks *tasks)
Transforms the problem with a time symmetry centered in 0.
bool ForbiddenIntervals(Tasks *tasks)
Tasks might have holes in their domain, this enforces such holes.
bool Propagate(Tasks *tasks)
Computes new bounds for all tasks, returns false if infeasible.
bool DetectablePrecedencesWithChain(Tasks *tasks)
Does detectable precedences deductions on tasks in the chain precedence, taking the time windows of n...
bool ChainSpanMinDynamic(Tasks *tasks)
Computes a lower bound of the span of the chain, taking into account only the first nonchain task.
bool ChainSpanMin(Tasks *tasks)
Propagates a lower bound of the chain span, end[num_chain_tasks] - start[0], to span_min.
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc evaluator.
Definition: routing.h:3584
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
Filter-based decision builder which builds a solution by inserting nodes at their cheapest position o...
Definition: routing.h:3196
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimensio...
Definition: routing.h:2062
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
GlobalVehicleBreaksConstraint(const RoutingDimension *dimension)
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
Decision * Next(Solver *solver) override
This is the main method of the decision builder class.
int64 number_of_decisions() const
Returns statistics from its underlying heuristic.
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
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
bool Commit()
Commits the modifications to the current solution if these modifications are "filter-feasible",...
Assignment *const BuildSolution()
Builds a solution.
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
void ResetSolution()
Resets the data members for a new solution.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
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
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, LocalSearchFilterManager *filter_manager)
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
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
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
void SetCumulVarPiecewiseLinearCost(int64 index, const PiecewiseLinearFunction &cost)
Sets a piecewise linear cost on the cumul variable of a given variable index.
SimpleBoundCosts::BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2710
friend void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
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
void SetSpanUpperBoundForVehicle(int64 upper_bound, int vehicle)
!defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON)
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
int64 GetCumulVarSoftLowerBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
bool HasCumulVarSoftLowerBound(int64 index) const
Returns true if a soft lower bound has been set for a given variable index.
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
void SetSpanCostCoefficientForAllVehicles(int64 coefficient)
int64 GetCumulVarSoftLowerBound(int64 index) const
Returns the soft lower bound of a cumul variable for a given variable index.
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
void SetBreakDistanceDurationOfVehicle(int64 distance, int64 duration, int vehicle)
With breaks supposed to be consecutive, this forces the distance between breaks of size at least mini...
const std::vector< IntVar * > & fixed_transits() const
Definition: routing.h:2395
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
const std::vector< IntVar * > & transits() const
Definition: routing.h:2396
const PiecewiseLinearFunction * GetCumulVarPiecewiseLinearCost(int64 index) const
Returns the piecewise linear cost of a cumul variable for a given variable index.
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
Definition: routing.h:2608
void InitializeBreaks()
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_tr...
int64 GetTransitValue(int64 from_index, int64 to_index, int64 vehicle) const
Returns the transition value for a given pair of nodes (as var index); this value is the one taken by...
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
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
bool HasQuadraticCostSoftSpanUpperBounds() const
Definition: routing.h:2727
void SetPickupToDeliveryLimitFunctionForPair(PickupToDeliveryLimitFunction limit_function, int pair_index)
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
int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup, int delivery) const
void SetSpanCostCoefficientForVehicle(int64 coefficient, int vehicle)
Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once.
int64 GetCumulVarSoftUpperBound(int64 index) const
Returns the soft upper bound of a cumul variable for a given variable index.
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
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits, std::function< int64(int64, int64)> delays)
Deprecated, sets pre_travel(i, j) = node_visit_transit[i] and post_travel(i, j) = delays(i,...
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
int64 ShortestTransitionSlack(int64 node) const
It makes sense to use the function only for self-dependent dimension.
void SetCumulVarSoftUpperBound(int64 index, int64 upper_bound, int64 coefficient)
Sets a soft upper bound to the cumul variable of a given variable index.
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 std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64 index, int64 min_value, int64 max_value) const
Returns allowed intervals for a given node in a given interval.
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
void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound, int64 coefficient)
Sets a soft lower bound to the cumul variable of a given variable index.
const std::vector< IntVar * > & slacks() const
Definition: routing.h:2397
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits)
Deprecated, sets pre_travel(i, j) = node_visit_transit[i].
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator)
Sets the breaks for a given vehicle.
const std::vector< NodePrecedence > & GetNodePrecedences() const
Definition: routing.h:2656
bool HasCumulVarPiecewiseLinearCost(int64 index) const
Returns true if a piecewise linear cost has been set for a given variable index.
void SetGlobalSpanCostCoefficient(int64 coefficient)
Sets a cost proportional to the global dimension span, that is the difference between the largest val...
bool HasCumulVarSoftUpperBound(int64 index) const
Returns true if a soft upper bound has been set for a given variable index.
int64 GetCumulVarSoftUpperBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
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
void MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed.
void MakeDisjunctionNodesUnperformed(int64 node)
Make nodes in the same disjunction as 'node' unperformed.
const Assignment * BuildSolutionFromRoutes(const std::function< int64(int64)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
void MakePartiallyPerformedPairsUnperformed()
Make all partially performed pickup and delivery pairs unperformed.
bool VehicleIsEmpty(int vehicle) const
Definition: routing.h:3104
RoutingFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
Manager for any NodeIndex <-> variable index conversion.
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...
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)
int64 GetNumberOfDecisionsInFirstSolution(const RoutingSearchParameters &search_parameters) const
Returns statistics on first solution search, number of decisions sent to filters, number of decisions...
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
void SetFixedCostOfAllVehicles(int64 cost)
Sets the fixed cost of all vehicle routes.
void AddAtSolutionCallback(std::function< void()> callback)
Adds a callback called each time a solution is found during the search.
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
Definition: routing.h:608
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
void AddSearchMonitor(SearchMonitor *const monitor)
Adds a search monitor to the search used to solve the routing model.
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
bool ArcIsMoreConstrainedThanArc(int64 from, int64 to1, int64 to2)
Returns whether the arc from->to1 is more constrained than from->to2, taking into account,...
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
Definition: routing.h:663
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType(int type) const
Returns the set of requirement alternatives when removing the given type.
void AddLocalSearchOperator(LocalSearchOperator *ls_operator)
Adds a local search operator to the set of operators used to solve the vehicle routing problem.
RoutingIndexPair IndexPair
Definition: routing.h:247
void AddVariableTargetToFinalizer(IntVar *var, int64 target)
Add a variable to set the closest possible to the target value in the solution finalizer.
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
Assignment * CompactAssignment(const Assignment &assignment) const
Returns a compacted version of the given assignment, in which all vehicles with id lower or equal to ...
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
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType(int type) const
Returns the set of requirement alternatives when adding the given type.
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:242
DecisionBuilder * MakeGuidedSlackFinalizer(const RoutingDimension *dimension, std::function< int64(int64)> initializer)
The next few members are in the public section only for testing purposes.
void AddPickupAndDelivery(int64 pickup, int64 delivery)
Notifies that index1 and index2 form a pair of nodes which should belong to the same route.
std::string DebugOutputAssignment(const Assignment &solution_assignment, const std::string &dimension_to_print) const
Print some debugging information about an assignment, including the feasible intervals of the CumulVa...
std::vector< std::vector< int64 > > GetRoutesFromAssignment(const Assignment &assignment)
Converts the solution in the given assignment to routes for all vehicles.
std::vector< std::pair< int64, int64 > > GetPerfectBinaryDisjunctions() const
Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "...
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
RoutingModel(const RoutingIndexManager &index_manager, const RoutingModelParameters &parameters)
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
int64 UnperformedPenalty(int64 var_index) const
Get the "unperformed" penalty of a node.
void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy)
Sets the Pickup and delivery policy of all vehicles.
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...
Assignment * MutablePreAssignment()
Definition: routing.h:1067
Assignment * CompactAndCheckAssignment(const Assignment &assignment) const
Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not ...
bool CheckLimit()
Returns true if the search limit has been crossed.
Definition: routing.h:1330
bool ApplyLocksToAllVehicles(const std::vector< std::vector< int64 >> &locks, bool close_routes)
Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for rout...
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
Creates a cached StateDependentTransit from an std::function.
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
void AddToAssignment(IntVar *const var)
Adds an extra variable to the vehicle routing assignment.
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
int64 Next(const Assignment &assignment, int64 index) const
Assignment inspection Returns the variable index of the node directly after the node corresponding to...
void AddVariableMinimizedByFinalizer(IntVar *var)
Adds a variable to minimize in the solution finalizer.
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
int64 GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
void SetFixedCostOfVehicle(int64 cost, int vehicle)
Sets the fixed cost of one vehicle route.
int64 GetArcCostForVehicle(int64 from_index, int64 to_index, int64 vehicle) const
Returns the cost of the transit arc between two nodes for a given vehicle.
LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer(const RoutingDimension &dimension) const
const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType(int type) const
Returns visit types incompatible with a given type.
const Assignment * Solve(const Assignment *assignment=nullptr)
Solves the current routing model; closes the current model.
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
Assignment * RestoreAssignment(const Assignment &solution)
Restores an assignment as a solution in the routing model and returns the new solution.
DecisionBuilder * MakeSelfDependentDimensionFinalizer(const RoutingDimension *dimension)
SWIG
const Assignment * SolveFromAssignmentWithParameters(const Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
const Assignment * PackCumulsOfOptimizerDimensionsFromAssignment(const Assignment *original_assignment, absl::Duration duration_limit)
For every dimension in the model with an optimizer in local/global_dimension_optimizers_,...
bool HasTemporalTypeRequirements() const
Definition: routing.h:870
Solver * solver() const
Returns the underlying constraint solver.
Definition: routing.h:1327
void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
Same as AddPickupAndDelivery but notifying that the performed node from the disjunction of index 'pic...
RoutingTransitCallback2 TransitCallback2
Definition: routing.h:243
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
Definition: routing.h:559
int64 GetArcCostForFirstSolution(int64 from_index, int64 to_index) const
Returns the cost of the arc in the context of the first solution strategy.
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)
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
void SetSweepArranger(SweepArranger *sweep_arranger)
Definition: routing.h:1158
void AddTemporalTypeIncompatibility(int type1, int type2)
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
Definition: routing.h:1162
Assignment * ReadAssignment(const std::string &file_name)
Reads an assignment from a file and returns the current solution.
RoutingIndexPairs IndexPairs
Definition: routing.h:248
void SetVisitType(int64 index, int type, VisitTypePolicy type_policy)
bool RoutesToAssignment(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices, bool close_routes, Assignment *const assignment) const
Fills an assignment from a specification of the routes of the vehicles.
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)
void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback)
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
Definition: routing.h:1203
void CloseVisitTypes()
This function should be called once all node visit types have been set and prior to adding any incomp...
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
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
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
void IgnoreDisjunctionsAlreadyForcedToZero()
SPECIAL: Makes the solver ignore all the disjunctions whose active variables are all trivially zero (...
void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy, int vehicle)
int RegisterTransitCallback(TransitCallback2 callback)
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
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
void AddWeightedVariableMinimizedByFinalizer(IntVar *var, int64 cost)
Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more ...
int GetMaximumNumberOfActiveVehicles() const
Returns the maximum number of active vehicles.
Definition: routing.h:904
int GetVisitType(int64 index) const
RoutingDimensionIndex DimensionIndex
Definition: routing.h:239
bool AddDimensionDependentDimensionWithVehicleCapacity(int transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
Homogeneous versions of the functions above.
void AssignmentToRoutes(const Assignment &assignment, std::vector< std::vector< int64 >> *const routes) const
Converts the solution in the given assignment to routes for all vehicles.
Assignment * ReadAssignmentFromRoutes(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices)
Restores the routes as the current solution.
void AddSoftSameVehicleConstraint(const std::vector< int64 > &indices, int64 cost)
Adds a soft constraint to force a set of variable indices to be on the same vehicle.
bool HasHardTypeIncompatibilities() const
Returns true iff any hard (resp.
Definition: routing.h:822
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType(int type) const
const std::vector< int > & GetPairIndicesOfType(int type) const
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
void AddRequiredTypeAlternativesWhenRemovingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
The following requirements apply when visiting dependent nodes that remove their type from the route,...
static std::unique_ptr< LocalSearchOperator > MakeGreedyDescentLSOperator(std::vector< IntVar * > variables)
Perhaps move it to constraint_solver.h.
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
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
As above, but pure_transits are taken to be zero evaluators.
int RegisterPositiveTransitCallback(TransitCallback2 callback)
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
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.
void CloseModelWithParameters(const RoutingSearchParameters &search_parameters)
Same as above taking search parameters (as of 10/2015 some the parameters have to be set when closing...
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
void AddVariableMaximizedByFinalizer(IntVar *var)
Adds a variable to maximize in the solution finalizer (see above for information on the solution fina...
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
IntVar * ApplyLocks(const std::vector< int64 > &locks)
Applies a lock chain to the next search.
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.
bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
void AddIntervalToAssignment(IntervalVar *const interval)
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
Sets the cost function of the model such that the cost of a segment of a route between node 'from' an...
void SetAmortizedCostFactorsOfAllVehicles(int64 linear_cost_factor, int64 quadratic_cost_factor)
The following methods set the linear and quadratic cost factors of vehicles (must be positive values)...
int GetNonZeroCostClassesCount() const
Ditto, minus the 'always zero', built-in cost class.
Definition: routing.h:1270
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
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
For every vehicle of the routing model:
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
Definition: routing.h:421
VisitTypePolicy GetVisitTypePolicy(int64 index) const
void SetAssignmentFromOtherModelAssignment(Assignment *target_assignment, const RoutingModel *source_model, const Assignment *source_assignment)
Given a "source_model" and its "source_assignment", resets "target_assignment" with the IntVar variab...
void AddSameVehicleRequiredTypeAlternatives(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
Requirements: NOTE: As of 2019-04, cycles in the requirement graph are not supported,...
int RegisterTransitMatrix(std::vector< std::vector< int64 > > values)
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int RegisterUnaryTransitCallback(TransitCallback1 callback)
int64 Start(int vehicle) const
Model inspection.
Definition: routing.h:1180
int64 GetDepot() const
Returns the variable index of the first starting or ending node of all routes.
bool WriteAssignment(const std::string &file_name) const
Writes the current solution to a file containing an AssignmentProto.
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
int GetNumOfSingletonNodes() const
Returns the number of non-start/end nodes which do not appear in a pickup/delivery pair.
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
void AddRequiredTypeAlternativesWhenAddingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
If type_D depends on type_R when adding type_D, any node_D of type_D and VisitTypePolicy TYPE_ADDED_T...
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
void CloseModel()
Closes the current routing model; after this method is called, no modification to the model can be do...
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
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(int vehicle) const
void SetAmortizedCostFactorsOfVehicle(int64 linear_cost_factor, int64 quadratic_cost_factor, int vehicle)
Sets the linear and quadratic cost factor of the given vehicle.
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType(int type) const
Returns the set of same-vehicle requirement alternatives for the given type.
bool AddDimensionDependentDimensionWithVehicleCapacity(int pure_transit, int dependent_transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
const VehicleTypeContainer & GetVehicleTypeContainer() const
Definition: routing.h:1285
void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle)
Sets the cost function for a given vehicle route.
int64 UnperformedPenaltyOrValue(int64 default_value, int64 var_index) const
Same as above except that it returns default_value instead of 0 when penalty is not well defined (def...
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; ...
int64 ComputeLowerBound()
Computes a lower bound to the routing problem solving a linear assignment problem.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
bool AreEmptyRouteCostsConsideredForVehicle(int vehicle) const
Definition: routing.h:955
bool IsVehicleUsed(const Assignment &assignment, int vehicle) const
Returns true if the route of 'vehicle' is non empty in 'assignment'.
int64 GetNumberOfRejectsInFirstSolution(const RoutingSearchParameters &search_parameters) const
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
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
const Assignment * SolveWithParameters(const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
Solves the current routing model with the given parameters.
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
std::vector< std::vector< std::pair< int64, int64 > > > GetCumulBounds(const Assignment &solution_assignment, const RoutingDimension &dimension)
Returns a vector cumul_bounds, for which cumul_bounds[i][j] is a pair containing the minimum and maxi...
const std::vector< int > & GetSingleNodesOfType(int type) const
void SetAllowedVehiclesForIndex(const std::vector< int > &vehicles, int64 index)
Sets the vehicles which can visit a given node.
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
Definition: routing.h:3635
int StartNewRouteWithBestVehicleOfType(int type, int64 before_node, int64 after_node)
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->a...
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
Definition: routing.h:3699
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
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
SavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
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
Class to arrange indices by by their distance and their angles from the depot.
Definition: routing.h:2869
void ArrangeIndices(std::vector< int64 > *indices)
SweepArranger(const std::vector< std::pair< int64, int64 >> &points)
void SetSectors(int sectors)
Definition: routing.h:2874
Checker for type incompatibilities.
Definition: routing.h:2220
TypeIncompatibilityChecker(const RoutingModel &model, bool check_hard_incompatibilities)
virtual bool HasRegulationsToCheck() const =0
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
bool CheckVehicle(int vehicle, const std::function< int64(int64)> &next_accessor)
TypeRegulationsChecker(const RoutingModel &model)
bool TypeCurrentlyOnRoute(int type, int pos) const
Returns true iff there's at least one instance of the given type on the route when scanning the route...
void InitializeCheck(int vehicle, const std::function< int64(int64)> &next_accessor)
bool TypeOccursOnRoute(int type) const
Returns true iff any occurrence of the given type was seen on the route, i.e.
The following constraint ensures that incompatibilities and requirements between types are respected.
Definition: routing.h:2300
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
TypeRegulationsConstraint(const RoutingModel &model)
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
void Update(const std::function< bool(int)> &remove_vehicle)
Goes through all the currently stored vehicles and removes vehicles for which remove_vehicle() return...
std::pair< int, int > GetCompatibleVehicleOfType(int type, std::function< bool(int)> vehicle_is_compatible, std::function< bool(int)> stop_and_return_vehicle)
Searches for the best compatible vehicle of the given type, i.e.
VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)
Definition: routing.h:2896
void Reset(const std::function< bool(int)> &store_vehicle)
Resets the vehicles stored, storing only vehicles from the vehicle_type_container_ for which store_ve...
void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64 fixed_cost)
Definition: routing.h:2924
int GetLowestFixedCostVehicleOfType(int type) const
Definition: routing.h:2912
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::pair< std::vector< int64 >, std::vector< int64 > > RoutingIndexPair
Definition: routing_types.h:44
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
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...
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters &parameters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
void FillTravelBoundsOfVehicle(int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
void AppendTasksFromPath(const std::vector< int64 > &path, const TravelBounds &travel_bounds, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
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.
std::function< int64(int64, int64)> RoutingTransitCallback2
Definition: routing_types.h:42
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
std::function< int64(int64)> RoutingTransitCallback1
Definition: routing_types.h:41
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
void AppendTasksFromIntervals(const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)
std::vector< RoutingIndexPair > RoutingIndexPairs
Definition: routing_types.h:45
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
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
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
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