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