C++ Reference

C++ Reference: Routing

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