routing.h

Go to the documentation of this file.

// Copyright 2010-2025 Google LLC
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

 
#ifndef ORTOOLS_CONSTRAINT_SOLVER_ROUTING_H_
#define ORTOOLS_CONSTRAINT_SOLVER_ROUTING_H_
 
#include <algorithm>
#include <atomic>
#include <cstdint>
#include <deque>
#include <functional>
#include <limits>
#include <memory>
#include <optional>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
 
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/functional/any_invocable.h"
#include "absl/hash/hash.h"
#include "absl/log/check.h"
#include "absl/strings/string_view.h"
#include "absl/time/time.h"
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/base/strong_vector.h"
#include "ortools/base/types.h"
#include "ortools/constraint_solver/constraint_solver.h"
#include "ortools/constraint_solver/constraint_solveri.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_heuristic_parameters.pb.h"
#include "ortools/constraint_solver/routing_index_manager.h"
#include "ortools/constraint_solver/routing_parameters.pb.h"
#include "ortools/constraint_solver/routing_types.h"
#include "ortools/constraint_solver/routing_utils.h"
#include "ortools/graph/graph.h"
#include "ortools/util/piecewise_linear_function.h"
#include "ortools/util/range_query_function.h"
#include "ortools/util/saturated_arithmetic.h"
#include "ortools/util/sorted_interval_list.h"
 
namespace operations_research {
 
class FinalizerVariables;
class GlobalDimensionCumulOptimizer;
class LocalDimensionCumulOptimizer;
#ifndef SWIG
class IntVarFilteredDecisionBuilder;
#endif
class RoutingDimension;
#ifndef SWIG
using util::ReverseArcListGraph;
class SweepArranger;
#endif
 
class PathsMetadata {
 public:
  explicit PathsMetadata(const RoutingIndexManager& manager) {
    const int num_indices = manager.num_indices();
    const int num_paths = manager.num_vehicles();
    path_of_node_.resize(num_indices, -1);
    is_start_.resize(num_indices, false);
    is_end_.resize(num_indices, false);
    start_of_path_.resize(num_paths);
    end_of_path_.resize(num_paths);
    for (int v = 0; v < num_paths; ++v) {
      const int64_t start = manager.GetStartIndex(v);
      start_of_path_[v] = start;
      path_of_node_[start] = v;
      is_start_[start] = true;
      const int64_t end = manager.GetEndIndex(v);
      end_of_path_[v] = end;
      path_of_node_[end] = v;
      is_end_[end] = true;
    }
  }
 
  bool IsStart(int64_t node) const { return is_start_[node]; }
  bool IsEnd(int64_t node) const { return is_end_[node]; }
  int GetPath(int64_t start_or_end_node) const {
    return path_of_node_[start_or_end_node];
  }
  int NumPaths() const { return start_of_path_.size(); }
  const std::vector<int64_t>& Paths() const { return path_of_node_; }
  const std::vector<int64_t>& Starts() const { return start_of_path_; }
  int64_t Start(int path) const { return start_of_path_[path]; }
  int64_t End(int path) const { return end_of_path_[path]; }
  const std::vector<int64_t>& Ends() const { return end_of_path_; }
 
 private:
  std::vector<bool> is_start_;
  std::vector<bool> is_end_;
  std::vector<int64_t> start_of_path_;
  std::vector<int64_t> end_of_path_;
  std::vector<int64_t> path_of_node_;
};
 
struct RoutingSearchStats {
  int64_t num_cp_sat_calls_in_lp_scheduling = 0;
  int64_t num_glop_calls_in_lp_scheduling = 0;
  int64_t num_min_cost_flow_calls = 0;
  int64_t num_cp_sat_calls_in_routing = 0;
  int64_t num_generalized_cp_sat_calls_in_routing = 0;
};
 
class OR_DLL RoutingModel {
 public:
  enum PickupAndDeliveryPolicy {
    PICKUP_AND_DELIVERY_NO_ORDER,
    PICKUP_AND_DELIVERY_LIFO,
    PICKUP_AND_DELIVERY_FIFO
  };
  typedef RoutingCostClassIndex CostClassIndex;
  typedef RoutingDimensionIndex DimensionIndex;
  typedef RoutingDisjunctionIndex DisjunctionIndex;
  typedef RoutingVehicleClassIndex VehicleClassIndex;
  typedef RoutingResourceClassIndex ResourceClassIndex;
  typedef RoutingTransitCallback1 TransitCallback1;
  typedef RoutingTransitCallback2 TransitCallback2;
  typedef RoutingCumulDependentTransitCallback2 CumulDependentTransitCallback2;
 
#if !defined(SWIG)
  struct StateDependentTransit {
    RangeIntToIntFunction* transit;                   
    RangeMinMaxIndexFunction* transit_plus_identity;  
  };
  typedef std::function<StateDependentTransit(int64_t, int64_t)>
      VariableIndexEvaluator2;
#endif  // SWIG
 
#if !defined(SWIG)
  struct CostClass {
    int evaluator_index = 0;


    struct DimensionCost {
      int64_t transit_evaluator_class;
      // TODO(user): replace span_cost_coefficient by
      // transit_cost_coefficient and add the span coefficient to the slack one.
      int64_t span_cost_coefficient;
      int64_t slack_cost_coefficient;
      const RoutingDimension* dimension;
      bool operator<(const DimensionCost& cost) const {
        return std::tie(transit_evaluator_class, span_cost_coefficient,
                        slack_cost_coefficient) <
               std::tie(cost.transit_evaluator_class,
                        cost.span_cost_coefficient,
                        cost.slack_cost_coefficient);
      }
 
      friend bool operator==(const DimensionCost& c1, const DimensionCost& c2) {
        return c1.transit_evaluator_class == c2.transit_evaluator_class &&
               c1.span_cost_coefficient == c2.span_cost_coefficient &&
               c1.slack_cost_coefficient == c2.slack_cost_coefficient;
      }
      template <typename H>
      friend H AbslHashValue(H h, const DimensionCost& cost) {
        return H::combine(std::move(h), cost.transit_evaluator_class,
                          cost.span_cost_coefficient,
                          cost.slack_cost_coefficient);
      }
    };
    std::vector<DimensionCost>
        dimension_transit_evaluator_class_and_cost_coefficient;
 
    explicit CostClass(int evaluator_index)
        : evaluator_index(evaluator_index) {}
 
    friend bool operator==(const CostClass& c1, const CostClass& c2) {
      return c1.evaluator_index == c2.evaluator_index &&
             c1.dimension_transit_evaluator_class_and_cost_coefficient ==
                 c2.dimension_transit_evaluator_class_and_cost_coefficient;
    }
    template <typename H>
    friend H AbslHashValue(H h, const CostClass& c) {
      return H::combine(
          std::move(h), c.evaluator_index,
          c.dimension_transit_evaluator_class_and_cost_coefficient);
    }
  };
#endif  // defined(SWIG)

  struct VehicleTypeContainer {
    struct VehicleClassEntry {
      int vehicle_class;
      int64_t fixed_cost;
 
      bool operator<(const VehicleClassEntry& other) const {
        return std::tie(fixed_cost, vehicle_class) <
               std::tie(other.fixed_cost, other.vehicle_class);
      }
    };
 
    int NumTypes() const { return sorted_vehicle_classes_per_type.size(); }
 
    int Type(int vehicle) const {
      DCHECK_LT(vehicle, type_index_of_vehicle.size());
      return type_index_of_vehicle[vehicle];
    }
 
    std::vector<int> type_index_of_vehicle;
    // clang-format off
    std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type;
    std::vector<std::deque<int> > vehicles_per_vehicle_class;
    // clang-format on
  };

  class ResourceGroup {
   public:
    class Attributes {
     public:
      Attributes();
      Attributes(Domain start_domain, Domain end_domain);
 
      const Domain& start_domain() const { return start_domain_; }
      const Domain& end_domain() const { return end_domain_; }
 
      friend bool operator==(const Attributes& a, const Attributes& b) {
        return a.start_domain_ == b.start_domain_ &&
               a.end_domain_ == b.end_domain_;
      }
      template <typename H>
      friend H AbslHashValue(H h, const Attributes& attributes) {
        return H::combine(std::move(h), attributes.start_domain_,
                          attributes.end_domain_);
      }
 
     private:
      Domain start_domain_;
      Domain end_domain_;
    };

    class Resource {
     public:
      const ResourceGroup::Attributes& GetDimensionAttributes(
          DimensionIndex index) const {
        return index < dimension_attributes_per_index_.size()
                   ? attributes_[dimension_attributes_per_index_[index]]
                   : GetDefaultAttributes();
      }
 
     private:
      Resource(ResourceGroup::Attributes attributes,
               const RoutingDimension* dimension) {
        SetDimensionAttributes(std::move(attributes), dimension);
      }
 
      void SetDimensionAttributes(ResourceGroup::Attributes attributes,
                                  const RoutingDimension* dimension);
      const ResourceGroup::Attributes& GetDefaultAttributes() const;
 
      absl::flat_hash_map<DimensionIndex, int> dimension_attributes_;
      util_intops::StrongVector<DimensionIndex, int>
          dimension_attributes_per_index_;
      std::vector<ResourceGroup::Attributes> attributes_;
 
      friend class ResourceGroup;
    };

    int AddResource(Attributes attributes, const RoutingDimension* dimension);

    void NotifyVehicleRequiresAResource(int vehicle);
 
    const std::vector<int>& GetVehiclesRequiringAResource() const {
      return vehicles_requiring_resource_;
    }
 
    bool VehicleRequiresAResource(int vehicle) const {
      return vehicle_requires_resource_[vehicle];
    }
 
    void SetAllowedResourcesForVehicle(
        int vehicle, const std::vector<int>& allowed_resource_indices) {
      DCHECK(!model_->closed_);
      // NOTE: As of 12/2023, an empty set of allowed resources means "all
      // resources allowed", so we make sure the empty set isn't used here
      // explicitly by the user to mark a vehicle as "unusable".
      DCHECK(!allowed_resource_indices.empty());
      DCHECK(vehicle_requires_resource_[vehicle]);
      DCHECK_LT(vehicle, vehicle_allowed_resources_.size());
      vehicle_allowed_resources_[vehicle].clear();
      vehicle_allowed_resources_[vehicle].insert(
          allowed_resource_indices.begin(), allowed_resource_indices.end());
    }
    void ClearAllowedResourcesForVehicle(int vehicle) {
      DCHECK_LT(vehicle, vehicle_allowed_resources_.size());
      vehicle_allowed_resources_[vehicle].clear();
    }
    const absl::flat_hash_set<int>& GetResourcesMarkedAllowedForVehicle(
        int vehicle) const {
      DCHECK_LT(vehicle, vehicle_allowed_resources_.size());
      return vehicle_allowed_resources_[vehicle];
    }
    bool IsResourceAllowedForVehicle(int resource, int vehicle) const {
      DCHECK_LT(vehicle, vehicle_allowed_resources_.size());
      return vehicle_allowed_resources_[vehicle].empty() ||
             vehicle_allowed_resources_[vehicle].contains(resource);
    }
 
    const std::vector<Resource>& GetResources() const { return resources_; }
    const Resource& GetResource(int resource_index) const {
      DCHECK_LT(resource_index, resources_.size());
      return resources_[resource_index];
    }
    const absl::flat_hash_set<DimensionIndex>& GetAffectedDimensionIndices()
        const {
      return affected_dimension_indices_;
    }
 
    int GetResourceClassesCount() const {
      return resource_indices_per_class_.size();
    }
    const std::vector<int>& GetResourceIndicesInClass(
        ResourceClassIndex resource_class) const {
      DCHECK_LT(resource_class, resource_indices_per_class_.size());
      return resource_indices_per_class_[resource_class];
    }
    // clang-format off
    const util_intops::StrongVector<ResourceClassIndex, std::vector<int> >&
        GetResourceIndicesPerClass() const {
      return resource_indices_per_class_;
    }
    // clang-format on
    ResourceClassIndex GetResourceClassIndex(int resource_index) const {
      DCHECK_LT(resource_index, resource_class_indices_.size());
      return resource_class_indices_[resource_index];
    }
    const Attributes& GetDimensionAttributesForClass(
        DimensionIndex dimension_index, ResourceClassIndex rc_index) const {
      DCHECK_LT(rc_index, resource_indices_per_class_.size());
      const std::vector<int>& resource_indices =
          resource_indices_per_class_[rc_index];
      DCHECK(!resource_indices.empty());
      return resources_[resource_indices[0]].GetDimensionAttributes(
          dimension_index);
    }
 
    int Size() const { return resources_.size(); }
    int Index() const { return index_; }
 
   private:
    explicit ResourceGroup(const RoutingModel* model)
        : index_(model->GetResourceGroups().size()),
          model_(model),
          vehicle_requires_resource_(model->vehicles(), false),
          vehicle_allowed_resources_(model->vehicles()) {}
 
    void ComputeResourceClasses();
 
    const int index_;
    const RoutingModel* const model_;
    std::vector<Resource> resources_;
    // Stores the ResourceClassIndex of each resource (See implementation of
    // ComputeResourceClasses()).
    std::vector<ResourceClassIndex> resource_class_indices_;
    // clang-format off
    util_intops::StrongVector<ResourceClassIndex, std::vector<int> >
        resource_indices_per_class_;
    // clang-format on
 
    std::vector<bool> vehicle_requires_resource_;
    std::vector<int> vehicles_requiring_resource_;
    // For each vehicle, stores the set of allowed resource indices if it's
    // restricted for that vehicle. If the set is empty for a vehicle, then any
    // resource from this group can be assigned to it.
    // clang-format off
    std::vector<absl::flat_hash_set<int> > vehicle_allowed_resources_;
    // clang-format on
    absl::flat_hash_set<DimensionIndex> affected_dimension_indices_;
 
    friend class RoutingModel;
  };

  struct VariableValuePair {
    int var_index;
    int64_t value;
  };

  class SecondaryOptimizer {
   public:
    SecondaryOptimizer(RoutingModel* model,
                       RoutingSearchParameters* search_parameters,
                       int64_t solve_period);
    bool Solve(const std::vector<RoutingModel::VariableValuePair>& in_state,
               std::vector<RoutingModel::VariableValuePair>* out_state);
 
   private:
    RoutingModel* const model_;
    const RoutingSearchParameters* const search_parameters_;
    const int64_t solve_period_ = 0;
    int64_t call_count_ = 0;
    operations_research::Assignment* state_ = nullptr;
    absl::flat_hash_map<operations_research::IntVar*, int> var_to_index_;
  };

  static const int64_t kNoPenalty;

  static const DisjunctionIndex kNoDisjunction;

  static const DimensionIndex kNoDimension;

  explicit RoutingModel(const RoutingIndexManager& index_manager);
  RoutingModel(const RoutingIndexManager& index_manager,
               const RoutingModelParameters& parameters);
 
  // This type is neither copyable nor movable.
  RoutingModel(const RoutingModel&) = delete;
  RoutingModel& operator=(const RoutingModel&) = delete;
 
  ~RoutingModel();

  enum TransitEvaluatorSign {
    kTransitEvaluatorSignUnknown = 0,
    kTransitEvaluatorSignPositiveOrZero = 1,
    kTransitEvaluatorSignNegativeOrZero = 2,
  };

  int RegisterUnaryTransitVector(std::vector<int64_t> values);
  int RegisterUnaryTransitCallback(
      TransitCallback1 callback,
      TransitEvaluatorSign sign = kTransitEvaluatorSignUnknown);
 
  int RegisterTransitMatrix(
      std::vector<std::vector<int64_t> /*needed_for_swig*/> values);
  int RegisterTransitCallback(
      TransitCallback2 callback,
      TransitEvaluatorSign sign = kTransitEvaluatorSignUnknown);
  int RegisterCumulDependentTransitCallback(
      CumulDependentTransitCallback2 callback);
  int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback);
 
  const TransitCallback2& TransitCallback(int callback_index) const {
    CHECK_LT(callback_index, transit_evaluators_.size());
    return transit_evaluators_[callback_index];
  }
  const TransitCallback1& UnaryTransitCallbackOrNull(int callback_index) const {
    CHECK_LT(callback_index, unary_transit_evaluators_.size());
    return unary_transit_evaluators_[callback_index];
  }
  const CumulDependentTransitCallback2& CumulDependentTransitCallback(
      int callback_index) const {
    CHECK_LT(callback_index, cumul_dependent_transit_evaluators_.size());
    return cumul_dependent_transit_evaluators_[callback_index];
  }
  const VariableIndexEvaluator2& StateDependentTransitCallback(
      int callback_index) const {
    CHECK_LT(callback_index, state_dependent_transit_evaluators_.size());
    return state_dependent_transit_evaluators_[callback_index];
  }



  bool AddDimension(int evaluator_index, int64_t slack_max, int64_t capacity,
                    bool fix_start_cumul_to_zero, const std::string& name);
  bool AddDimensionWithVehicleTransits(
      const std::vector<int>& evaluator_indices, int64_t slack_max,
      int64_t capacity, bool fix_start_cumul_to_zero, const std::string& name);
  bool AddDimensionWithVehicleCapacity(int evaluator_index, int64_t slack_max,
                                       std::vector<int64_t> vehicle_capacities,
                                       bool fix_start_cumul_to_zero,
                                       const std::string& name);
  bool AddDimensionWithVehicleTransitAndCapacity(
      const std::vector<int>& evaluator_indices, int64_t slack_max,
      std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,
      const std::string& name);
  bool AddDimensionWithCumulDependentVehicleTransitAndCapacity(
      const std::vector<int>& fixed_evaluator_indices,
      const std::vector<int>& cumul_dependent_evaluator_indices,
      int64_t slack_max, std::vector<int64_t> vehicle_capacities,
      bool fix_start_cumul_to_zero, const std::string& name);

  std::pair<int, bool> AddConstantDimensionWithSlack(
      int64_t value, int64_t capacity, int64_t slack_max,
      bool fix_start_cumul_to_zero, const std::string& name);
  std::pair<int, bool> AddConstantDimension(int64_t value, int64_t capacity,
                                            bool fix_start_cumul_to_zero,
                                            const std::string& name) {
    return AddConstantDimensionWithSlack(value, capacity, 0,
                                         fix_start_cumul_to_zero, name);
  }

  std::pair<int, bool> AddVectorDimension(std::vector<int64_t> values,
                                          int64_t capacity,
                                          bool fix_start_cumul_to_zero,
                                          const std::string& name);
  std::pair<int, bool> AddMatrixDimension(
      std::vector<std::vector<int64_t> /*needed_for_swig*/> values,
      int64_t capacity, bool fix_start_cumul_to_zero, const std::string& name);
  bool AddDimensionDependentDimensionWithVehicleCapacity(
      const std::vector<int>& pure_transits,
      const std::vector<int>& dependent_transits,
      const RoutingDimension* base_dimension, int64_t slack_max,
      std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,
      const std::string& name) {
    return AddDimensionDependentDimensionWithVehicleCapacityInternal(
        pure_transits, dependent_transits, base_dimension, slack_max,
        std::move(vehicle_capacities), fix_start_cumul_to_zero, name);
  }

  bool AddDimensionDependentDimensionWithVehicleCapacity(
      const std::vector<int>& transits, const RoutingDimension* base_dimension,
      int64_t slack_max, std::vector<int64_t> vehicle_capacities,
      bool fix_start_cumul_to_zero, const std::string& name);
  bool AddDimensionDependentDimensionWithVehicleCapacity(
      int transit, const RoutingDimension* base_dimension, int64_t slack_max,
      int64_t vehicle_capacity, bool fix_start_cumul_to_zero,
      const std::string& name);
  bool AddDimensionDependentDimensionWithVehicleCapacity(
      int pure_transit, int dependent_transit,
      const RoutingDimension* base_dimension, int64_t slack_max,
      int64_t vehicle_capacity, bool fix_start_cumul_to_zero,
      const std::string& name);

  static RoutingModel::StateDependentTransit MakeStateDependentTransit(
      const std::function<int64_t(int64_t)>& f, int64_t domain_start,
      int64_t domain_end);

  // TODO(user): rename.
  std::vector<std::string> GetAllDimensionNames() const;
  const std::vector<RoutingDimension*>& GetDimensions() const {
    return dimensions_.get();
  }

  std::vector<RoutingDimension*> GetDimensionsWithSoftOrSpanCosts() const;
  std::vector<RoutingDimension*> GetUnaryDimensions() const;

  std::vector<const RoutingDimension*> GetDimensionsWithGlobalCumulOptimizers()
      const;
  std::vector<const RoutingDimension*> GetDimensionsWithLocalCumulOptimizers()
      const;

  bool HasGlobalCumulOptimizer(const RoutingDimension& dimension) const {
    return GetGlobalCumulOptimizerIndex(dimension) >= 0;
  }
  bool HasLocalCumulOptimizer(const RoutingDimension& dimension) const {
    return GetLocalCumulOptimizerIndex(dimension) >= 0;
  }

  GlobalDimensionCumulOptimizer* GetMutableGlobalCumulLPOptimizer(
      const RoutingDimension& dimension) const;
  GlobalDimensionCumulOptimizer* GetMutableGlobalCumulMPOptimizer(
      const RoutingDimension& dimension) const;
  LocalDimensionCumulOptimizer* GetMutableLocalCumulLPOptimizer(
      const RoutingDimension& dimension) const;
  LocalDimensionCumulOptimizer* GetMutableLocalCumulMPOptimizer(
      const RoutingDimension& dimension) const;

  bool HasDimension(absl::string_view dimension_name) const;
  const RoutingDimension& GetDimensionOrDie(
      const std::string& dimension_name) const;
  RoutingDimension* GetMutableDimension(
      const std::string& dimension_name) const;
  void SetPrimaryConstrainedDimension(absl::string_view dimension_name) {
    DCHECK(dimension_name.empty() || HasDimension(dimension_name));
    primary_constrained_dimension_ = dimension_name;
  }

  const std::string& GetPrimaryConstrainedDimension() const {
    return primary_constrained_dimension_;
  }

  ResourceGroup* AddResourceGroup();
  // clang-format off
  const std::vector<std::unique_ptr<ResourceGroup> >& GetResourceGroups()
      const {
    return resource_groups_;
  }
  // clang-format on
  ResourceGroup* GetResourceGroup(int rg_index) const {
    DCHECK_LT(rg_index, resource_groups_.size());
    return resource_groups_[rg_index].get();
  }

  const std::vector<int>& GetDimensionResourceGroupIndices(
      const RoutingDimension* dimension) const;

  int GetDimensionResourceGroupIndex(const RoutingDimension* dimension) const {
    DCHECK_EQ(GetDimensionResourceGroupIndices(dimension).size(), 1);
    return GetDimensionResourceGroupIndices(dimension)[0];
  }

  enum PenaltyCostBehavior { PENALIZE_ONCE, PENALIZE_PER_INACTIVE };

  DisjunctionIndex AddDisjunction(const std::vector<int64_t>& indices,
                                  int64_t penalty = kNoPenalty,
                                  int64_t max_cardinality = 1,
                                  PenaltyCostBehavior penalty_cost_behavior =
                                      PenaltyCostBehavior::PENALIZE_ONCE);
  const std::vector<DisjunctionIndex>& GetDisjunctionIndices(
      int64_t index) const {
    return index_to_disjunctions_[index];
  }

  template <typename F>
  void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(
      int64_t index, int64_t max_cardinality, F f) const {
    for (const DisjunctionIndex disjunction : GetDisjunctionIndices(index)) {
      if (disjunctions_[disjunction].value.max_cardinality == max_cardinality) {
        for (const int64_t d_index : disjunctions_[disjunction].indices) {
          f(d_index);
        }
      }
    }
  }
#if !defined(SWIGPYTHON)

  const std::vector<int64_t>& GetDisjunctionNodeIndices(
      DisjunctionIndex index) const {
    return disjunctions_[index].indices;
  }
#endif  // !defined(SWIGPYTHON)

  int64_t GetDisjunctionPenalty(DisjunctionIndex index) const {
    return disjunctions_[index].value.penalty;
  }

  int64_t GetDisjunctionMaxCardinality(DisjunctionIndex index) const {
    return disjunctions_[index].value.max_cardinality;
  }

  PenaltyCostBehavior GetDisjunctionPenaltyCostBehavior(
      DisjunctionIndex index) const {
    return disjunctions_[index].value.penalty_cost_behavior;
  }
  int GetNumberOfDisjunctions() const { return disjunctions_.size(); }
  bool HasMandatoryDisjunctions() const;
  bool HasMaxCardinalityConstrainedDisjunctions() const;
  std::vector<std::pair<int64_t, int64_t>> GetPerfectBinaryDisjunctions() const;
  void IgnoreDisjunctionsAlreadyForcedToZero();

  void AddSoftSameVehicleConstraint(std::vector<int64_t> indices, int64_t cost);
  int GetNumberOfSoftSameVehicleConstraints() const {
    return same_vehicle_costs_.size();
  }

  const std::vector<int64_t>& GetSoftSameVehicleIndices(int index) const {
    return same_vehicle_costs_[index].indices;
  }
  int64_t GetSoftSameVehicleCost(int index) const {
    return same_vehicle_costs_[index].value;
  }


  void SetAllowedVehiclesForIndex(absl::Span<const int> vehicles,
                                  int64_t index);

  bool IsVehicleAllowedForIndex(int vehicle, int64_t index) const {
    return allowed_vehicles_[index].empty() ||
           allowed_vehicles_[index].contains(vehicle);
  }


  // TODO(user): Remove this when model introspection detects linked nodes.
  void AddPickupAndDelivery(int64_t pickup, int64_t delivery);
  void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction,
                                DisjunctionIndex delivery_disjunction);

  struct PickupDeliveryPosition {
    int pd_pair_index = -1;
    int alternative_index = -1;
  };
  std::optional<PickupDeliveryPosition> GetPickupPosition(
      int64_t node_index) const;
  std::optional<PickupDeliveryPosition> GetDeliveryPosition(
      int64_t node_index) const;
  bool IsPickup(int64_t node_index) const {
    return index_to_pickup_position_[node_index].pd_pair_index != -1;
  }
  bool IsDelivery(int64_t node_index) const {
    return index_to_delivery_position_[node_index].pd_pair_index != -1;
  }


  void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy);
  void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy,
                                           int vehicle);
  PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(
      int vehicle) const;
 
  int GetNumOfSingletonNodes() const;
 
#ifndef SWIG
  const std::vector<PickupDeliveryPair>& GetPickupAndDeliveryPairs() const {
    return pickup_delivery_pairs_;
  }
  const std::vector<std::pair<DisjunctionIndex, DisjunctionIndex>>&
  GetPickupAndDeliveryDisjunctions() const {
    return pickup_delivery_disjunctions_;
  }

  const std::vector<PickupDeliveryPair>&
  GetImplicitUniquePickupAndDeliveryPairs() const {
    DCHECK(closed_);
    return implicit_pickup_delivery_pairs_without_alternatives_;
  }
#endif  // SWIG
 
  // Returns the first pickup or delivery sibling of the given node matching
  // the given predicate.
  std::optional<int64_t> GetFirstMatchingPickupDeliverySibling(
      int64_t node, const std::function<bool(int64_t)>& is_match) const;

  enum VisitTypePolicy {
    TYPE_ADDED_TO_VEHICLE,
    /// (TYPE_ADDED_TO_VEHICLE), if any, is removed from the vehicle.
    /// If the type was not previously added to the route or all added instances
    /// have already been removed, this visit has no effect on the types.
    ADDED_TYPE_REMOVED_FROM_VEHICLE,
    TYPE_ON_VEHICLE_UP_TO_VISIT,
    TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED
  };
  // TODO(user): Support multiple visit types per node?
  void SetVisitType(int64_t index, int type, VisitTypePolicy type_policy);
  int GetVisitType(int64_t index) const;
  const std::vector<int>& GetSingleNodesOfType(int type) const;
  const std::vector<int>& GetPairIndicesOfType(int type) const;
  VisitTypePolicy GetVisitTypePolicy(int64_t index) const;
#ifndef SWIG
  const std::vector<std::vector<int>>& GetVisitTypeComponents() const {
    return visit_type_components_;
  }
#endif  // SWIG
  int GetNumberOfVisitTypes() const { return num_visit_types_; }
#ifndef SWIG
  const std::vector<std::vector<int>>& GetTopologicallySortedVisitTypes()
      const {
    DCHECK(closed_);
    return topologically_sorted_visit_types_;
  }
  const std::vector<std::vector<std::vector<int>>>&
  GetTopologicallySortedNodePrecedences() const {
    DCHECK(closed_);
    return topologically_sorted_node_precedences_;
  }
#endif  // SWIG

  void AddHardTypeIncompatibility(int type1, int type2);
  void AddTemporalTypeIncompatibility(int type1, int type2);
  const absl::flat_hash_set<int>& GetHardTypeIncompatibilitiesOfType(
      int type) const;
  const absl::flat_hash_set<int>& GetTemporalTypeIncompatibilitiesOfType(
      int type) const;
  bool HasHardTypeIncompatibilities() const {
    return !hard_incompatible_types_per_type_index_.empty();
  }
  bool HasTemporalTypeIncompatibilities() const {
    return !temporal_incompatible_types_per_type_index_.empty();
  }

  /// NOTE: As of 2019-04, cycles in the requirement graph are not supported,
  /// and lead to the dependent nodes being skipped if possible (otherwise
  /// the model is considered infeasible).
  /// The following functions specify that "dependent_type" requires at least
  /// one of the types in "required_type_alternatives".
  ///
  /// For same-vehicle requirements, a node of dependent type type_D requires at
  /// least one node of type type_R among the required alternatives on the same
  /// route.
  /// NOTE: To avoid unnecessary memory reallocations, it is recommended to only
  /// add requirements once all the existing types have been set with
  /// SetVisitType().
  void AddSameVehicleRequiredTypeAlternatives(
      int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
  void AddRequiredTypeAlternativesWhenAddingType(
      int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
  void AddRequiredTypeAlternativesWhenRemovingType(
      int dependent_type, absl::flat_hash_set<int> required_type_alternatives);
  // clang-format off
  const std::vector<absl::flat_hash_set<int> >&
      GetSameVehicleRequiredTypeAlternativesOfType(int type) const;
  const std::vector<absl::flat_hash_set<int> >&
      GetRequiredTypeAlternativesWhenAddingType(int type) const;
  const std::vector<absl::flat_hash_set<int> >&
      GetRequiredTypeAlternativesWhenRemovingType(int type) const;
  // clang-format on
  bool HasSameVehicleTypeRequirements() const {
    return !same_vehicle_required_type_alternatives_per_type_index_.empty();
  }
  bool HasTemporalTypeRequirements() const {
    return !required_type_alternatives_when_adding_type_index_.empty() ||
           !required_type_alternatives_when_removing_type_index_.empty();
  }


  /// Returns true iff the model has any incompatibilities or requirements set
  /// on node types.
  bool HasTypeRegulations() const {
    return HasTemporalTypeIncompatibilities() ||
           HasHardTypeIncompatibilities() || HasSameVehicleTypeRequirements() ||
           HasTemporalTypeRequirements();
  }

  int64_t UnperformedPenalty(int64_t var_index) const;
  int64_t UnperformedPenaltyOrValue(int64_t default_value,
                                    int64_t var_index) const;
  int64_t GetDepot() const;

  void SetMaximumNumberOfActiveVehicles(int max_active_vehicles) {
    max_active_vehicles_ = max_active_vehicles;
  }
  int GetMaximumNumberOfActiveVehicles() const { return max_active_vehicles_; }
  /// Sets the cost function of the model such that the cost of a segment of a
  /// route between node 'from' and 'to' is evaluator(from, to), whatever the
  /// route or vehicle performing the route.
  void SetArcCostEvaluatorOfAllVehicles(int evaluator_index);
  void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle);
  void SetFixedCostOfAllVehicles(int64_t cost);
  void SetFixedCostOfVehicle(int64_t cost, int vehicle);
  int64_t GetFixedCostOfVehicle(int vehicle) const;
  // Sets the energy cost of a vehicle.
  // The energy used by a vehicle is defined as the integral of the
  // force dimension over the distance dimension:
  // it is the sum over nodes visited by the vehicle of
  // force.CumulVar(Next(node)) * distance.TransitVar(node).
  // The energy cost of a vehicle is linear in the energy used by the vehicle,
  // this call sets the coefficient to cost_per_unit. The cost is zero if unset.
  void SetPathEnergyCostOfVehicle(const std::string& force,
                                  const std::string& distance,
                                  int64_t cost_per_unit, int vehicle);
  // Sets the energy cost of a vehicle, relative to a threshold.
  // The cost per unit of energy is cost_per_unit_below_threshold until the
  // force reaches the threshold, then it is cost_per_unit_above_threshold:
  // min(threshold, force.CumulVar(Next(node))) * distance.TransitVar(node) *
  // cost_per_unit_below_threshold + max(0, force.CumulVar(Next(node)) -
  // threshold) * distance.TransitVar(node) * cost_per_unit_above_threshold.
  void SetPathEnergyCostsOfVehicle(const std::string& force,
                                   const std::string& distance,
                                   int64_t threshold,
                                   int64_t cost_per_unit_below_threshold,
                                   int64_t cost_per_unit_above_threshold,
                                   int vehicle);

  void SetAmortizedCostFactorsOfAllVehicles(int64_t linear_cost_factor,
                                            int64_t quadratic_cost_factor);
  void SetAmortizedCostFactorsOfVehicle(int64_t linear_cost_factor,
                                        int64_t quadratic_cost_factor,
                                        int vehicle);
 
  const std::vector<int64_t>& GetAmortizedLinearCostFactorOfVehicles() const {
    return linear_cost_factor_of_vehicle_;
  }
  const std::vector<int64_t>& GetAmortizedQuadraticCostFactorOfVehicles()
      const {
    return quadratic_cost_factor_of_vehicle_;
  }
 
  // Adds a custom route constraint based on a route evaluation callback. The
  // callback must not return a value if the route vector is invalid, and
  // returns the value of the route otherwise.
  // The callback must always return the same value for a given route.
#ifndef SWIG
  void AddRouteConstraint(
      absl::AnyInvocable<std::optional<int64_t>(const std::vector<int64_t>&)>
          route_evaluator,
      bool costs_are_homogeneous_across_vehicles = false);
#endif
  std::optional<int64_t> GetRouteCost(const std::vector<int64_t>& route) const {
    int64_t route_cost = 0;
    for (auto& evaluator : route_evaluators_) {
      std::optional<int64_t> cost = evaluator(route);
      if (!cost.has_value()) return std::nullopt;
      CapAddTo(cost.value(), &route_cost);
    }
    return route_cost;
  }
 
  void SetVehicleUsedWhenEmpty(bool is_used, int vehicle) {
    DCHECK_LT(vehicle, vehicles_);
    vehicle_used_when_empty_[vehicle] = is_used;
  }
 
  bool IsVehicleUsedWhenEmpty(int vehicle) const {
    DCHECK_LT(vehicle, vehicles_);
    return vehicle_used_when_empty_[vehicle];
  }


#ifndef SWIG
  const Solver::IndexEvaluator2& first_solution_evaluator() const {
    return first_solution_evaluator_;
  }
#endif
  void SetFirstSolutionEvaluator(Solver::IndexEvaluator2 evaluator) {
    first_solution_evaluator_ = std::move(evaluator);
  }

  void SetFirstSolutionHint(const operations_research::Assignment* hint) {
    hint_ = hint;
  }

  const operations_research::Assignment* GetFirstSolutionHint() const {
    return hint_;
  }
  /// Adds a local search operator to the set of operators used to solve the
  /// vehicle routing problem.
  void AddLocalSearchOperator(LocalSearchOperator* ls_operator);

  void AddSearchMonitor(SearchMonitor* monitor);
  // Adds a callback called at the beginning of the search.
  void AddEnterSearchCallback(std::function<void()> callback);

  void AddAtSolutionCallback(std::function<void()> callback,
                             bool track_unchecked_neighbors = false);
  // Internal-only: Adds a callback to reset
  // RestoreDimensionValuesForUnchangedRoutes at the beginning of the search.
  void AddRestoreDimensionValuesResetCallback(std::function<void()> callback);
  void AddVariableMinimizedByFinalizer(operations_research::IntVar* var);
  void AddVariableMaximizedByFinalizer(operations_research::IntVar* var);
  void AddWeightedVariableMinimizedByFinalizer(operations_research::IntVar* var,
                                               int64_t cost);
  void AddWeightedVariableMaximizedByFinalizer(operations_research::IntVar* var,
                                               int64_t cost);
  void AddVariableTargetToFinalizer(operations_research::IntVar* var,
                                    int64_t target);
  void AddWeightedVariableTargetToFinalizer(operations_research::IntVar* var,
                                            int64_t target, int64_t cost);
  void CloseModel();
  void CloseModelWithParameters(
      const RoutingSearchParameters& search_parameters);
  const operations_research::Assignment* Solve(
      const operations_research::Assignment* assignment = nullptr);
  const operations_research::Assignment* SolveWithParameters(
      const RoutingSearchParameters& search_parameters,
      std::vector<const operations_research::Assignment*>* solutions = nullptr);
  const operations_research::Assignment* SolveFromAssignmentWithParameters(
      const operations_research::Assignment* assignment,
      const RoutingSearchParameters& search_parameters,
      std::vector<const operations_research::Assignment*>* solutions = nullptr);
  const operations_research::Assignment* FastSolveFromAssignmentWithParameters(
      const operations_research::Assignment* assignment,
      const RoutingSearchParameters& search_parameters,
      bool check_solution_in_cp,
      absl::flat_hash_set<operations_research::IntVar*>* touched = nullptr);
  const operations_research::Assignment* SolveFromAssignmentsWithParameters(
      const std::vector<const operations_research::Assignment*>& assignments,
      const RoutingSearchParameters& search_parameters,
      std::vector<const operations_research::Assignment*>* solutions = nullptr);
  const operations_research::Assignment* SolveWithIteratedLocalSearch(
      const RoutingSearchParameters& search_parameters);
  void SetAssignmentFromOtherModelAssignment(
      operations_research::Assignment* target_assignment,
      const RoutingModel* source_model,
      const operations_research::Assignment* source_assignment);
  operations_research::SubSolverStatistics GetSubSolverStatistics() const;
  // TODO(user): Add support for non-homogeneous costs and disjunctions.
  int64_t ComputeLowerBound();
  int64_t objective_lower_bound() const { return objective_lower_bound_; }
  RoutingSearchStatus::Value status() const { return status_; }
  const RoutingSearchStats& search_stats() const { return search_stats_; }
  bool enable_deep_serialization() const { return enable_deep_serialization_; }
  operations_research::IntVar* ApplyLocks(absl::Span<const int64_t> locks);
  bool ApplyLocksToAllVehicles(const std::vector<std::vector<int64_t>>& locks,
                               bool close_routes);
  const operations_research::Assignment* PreAssignment() const {
    return preassignment_;
  }
  operations_research::Assignment* MutablePreAssignment() {
    return preassignment_;
  }
  /// solution.
  bool WriteAssignment(const std::string& file_name) const;

  /// Returns nullptr if the file cannot be opened or if the assignment is not
  /// valid.
  operations_research::Assignment* ReadAssignment(const std::string& file_name);

  operations_research::Assignment* RestoreAssignment(
      const operations_research::Assignment& solution);
  operations_research::Assignment* ReadAssignmentFromRoutes(
      const std::vector<std::vector<int64_t>>& routes,
      bool ignore_inactive_indices);
  bool RoutesToAssignment(const std::vector<std::vector<int64_t>>& routes,
                          bool ignore_inactive_indices, bool close_routes,
                          operations_research::Assignment* assignment) const;
  void AssignmentToRoutes(const operations_research::Assignment& assignment,
                          std::vector<std::vector<int64_t>>* routes) const;
#ifndef SWIG
  std::vector<std::vector<int64_t>> GetRoutesFromAssignment(
      const operations_research::Assignment& assignment);
#endif
  operations_research::Assignment* CompactAssignment(
      const operations_research::Assignment& assignment) const;
  operations_research::Assignment* CompactAndCheckAssignment(
      const operations_research::Assignment& assignment) const;
  void AddToAssignment(operations_research::IntVar* var);
  void AddIntervalToAssignment(IntervalVar* interval);
  const operations_research::Assignment*
  PackCumulsOfOptimizerDimensionsFromAssignment(
      const operations_research::Assignment* original_assignment,
      absl::Duration duration_limit, bool* time_limit_was_reached = nullptr);
 
#ifndef SWIG
  struct RouteDimensionTravelInfo {
    struct TransitionInfo {
      FloatSlopePiecewiseLinearFunction travel_start_dependent_travel;

      /// (real) travel value Tᵣ given by travel_start_dependent_travel and the
      /// compressed travel value considered in the scheduling.
      FloatSlopePiecewiseLinearFunction travel_compression_cost;

      int64_t pre_travel_transit_value;
      int64_t post_travel_transit_value;

      int64_t compressed_travel_value_lower_bound;

      int64_t travel_value_upper_bound;
 
      std::string DebugString(std::string line_prefix = "") const;
    };

    std::vector<TransitionInfo> transition_info;
    int64_t travel_cost_coefficient;
 
    std::string DebugString(std::string line_prefix = "") const;
  };
 
#endif  // SWIG
 
#ifndef SWIG
  // TODO(user): Revisit if coordinates are added to the RoutingModel class.
  void SetSweepArranger(SweepArranger* sweep_arranger);
  SweepArranger* sweep_arranger() const;
#endif
  struct NodeNeighborsParameters {
    int num_neighbors;
    bool add_vehicle_starts_to_neighbors = true;
    bool add_vehicle_ends_to_neighbors = false;
    // In NodeNeighborsByCostClass, neighbors for each node are sorted by
    // increasing "cost" for each node. The following parameter determines if
    // neighbors are sorted based on distance only when the neighborhood is
    // partial, i.e. when num_neighbors entails that not all nodes are
    // neighbors.
    bool only_sort_neighbors_for_partial_neighborhoods = true;
 
    bool operator==(const NodeNeighborsParameters& other) const {
      return num_neighbors == other.num_neighbors &&
             add_vehicle_starts_to_neighbors ==
                 other.add_vehicle_starts_to_neighbors &&
             add_vehicle_ends_to_neighbors ==
                 other.add_vehicle_ends_to_neighbors &&
             only_sort_neighbors_for_partial_neighborhoods ==
                 other.only_sort_neighbors_for_partial_neighborhoods;
    }
    template <typename H>
    friend H AbslHashValue(H h, const NodeNeighborsParameters& params) {
      return H::combine(std::move(h), params.num_neighbors,
                        params.add_vehicle_starts_to_neighbors,
                        params.add_vehicle_ends_to_neighbors,
                        params.only_sort_neighbors_for_partial_neighborhoods);
    }
  };
  class NodeNeighborsByCostClass {
   public:
    explicit NodeNeighborsByCostClass(const RoutingModel* routing_model)
        : routing_model_(*routing_model) {};

    void ComputeNeighbors(const NodeNeighborsParameters& params);

    /// Returns the incoming neighbors of the given node for the given
    /// cost_class, i.e. all 'neighbor' indices such that neighbor -> node_index
    /// is a neighborhood arc for 'cost_class'.
    const std::vector<int>& GetIncomingNeighborsOfNodeForCostClass(
        int cost_class, int node_index) const {
      if (routing_model_.IsStart(node_index)) return empty_neighbors_;
 
      if (node_index_to_incoming_neighbors_by_cost_class_.empty()) {
        DCHECK(IsFullNeighborhood());
        return all_incoming_nodes_;
      }
      const std::vector<std::vector<int>>& node_index_to_incoming_neighbors =
          node_index_to_incoming_neighbors_by_cost_class_[cost_class];
      if (node_index_to_incoming_neighbors.empty()) {
        return empty_neighbors_;
      }
      return node_index_to_incoming_neighbors[node_index];
    }

    const std::vector<int>& GetOutgoingNeighborsOfNodeForCostClass(
        int cost_class, int node_index) const {
      if (routing_model_.IsEnd(node_index)) return empty_neighbors_;
 
      if (node_index_to_outgoing_neighbors_by_cost_class_.empty()) {
        DCHECK(IsFullNeighborhood());
        return all_outgoing_nodes_;
      }
      const std::vector<std::vector<int>>& node_index_to_outgoing_neighbors =
          node_index_to_outgoing_neighbors_by_cost_class_[cost_class];
      if (node_index_to_outgoing_neighbors.empty()) {
        return empty_neighbors_;
      }
      return node_index_to_outgoing_neighbors[node_index];
    }
    bool IsNeighborhoodArcForCostClass(int cost_class, int64_t from,
                                       int64_t to) const {
      if (node_index_to_outgoing_neighbor_indicator_by_cost_class_.empty()) {
        DCHECK(full_neighborhood_);
        return true;
      }
      if (routing_model_.IsEnd(from)) {
        return false;
      }
      return node_index_to_outgoing_neighbor_indicator_by_cost_class_
          [cost_class][from][to];
    }
 
    bool IsFullNeighborhood() const { return full_neighborhood_; }
 
   private:
    const RoutingModel& routing_model_;
#if __cplusplus >= 202002L
    static constexpr std::vector<int> empty_neighbors_ = {};
#else
    inline static const std::vector<int> empty_neighbors_ = {};
#endif
 
    std::vector<std::vector<std::vector<int>>>
        node_index_to_incoming_neighbors_by_cost_class_;
    std::vector<std::vector<std::vector<int>>>
        node_index_to_outgoing_neighbors_by_cost_class_;
    std::vector<std::vector<std::vector<bool>>>
        node_index_to_outgoing_neighbor_indicator_by_cost_class_;
 
    std::vector<int> all_outgoing_nodes_;
    std::vector<int> all_incoming_nodes_;
 
    bool full_neighborhood_ = false;
  };

  const NodeNeighborsByCostClass* GetOrCreateNodeNeighborsByCostClass(
      double neighbors_ratio, int64_t min_neighbors,
      double& neighbors_ratio_used, bool add_vehicle_starts_to_neighbors = true,
      bool add_vehicle_ends_to_neighbors = false,
      bool only_sort_neighbors_for_partial_neighborhoods = true);
  const NodeNeighborsByCostClass* GetOrCreateNodeNeighborsByCostClass(
      const NodeNeighborsParameters& params);
  void AddLocalSearchFilter(LocalSearchFilter* filter) {
    CHECK(filter != nullptr);
    if (closed_) {
      LOG(WARNING) << "Model is closed, filter addition will be ignored.";
    }
    extra_filters_.push_back({filter, LocalSearchFilterManager::kRelax});
    extra_filters_.push_back({filter, LocalSearchFilterManager::kAccept});
  }

  int64_t Start(int vehicle) const { return paths_metadata_.Starts()[vehicle]; }
  int64_t End(int vehicle) const { return paths_metadata_.Ends()[vehicle]; }
  bool IsStart(int64_t index) const { return paths_metadata_.IsStart(index); }

  bool IsEnd(int64_t index) const { return paths_metadata_.IsEnd(index); }
  int VehicleIndex(int64_t index) const {
    return paths_metadata_.GetPath(index);
  }
  int64_t Next(const operations_research::Assignment& assignment,
               int64_t index) const;
  /// Returns true if the route of 'vehicle' is non empty in 'assignment'.
  bool IsVehicleUsed(const operations_research::Assignment& assignment,
                     int vehicle) const;
 
#if !defined(SWIGPYTHON)
  const std::vector<operations_research::IntVar*>& Nexts() const {
    return nexts_;
  }
  const std::vector<operations_research::IntVar*>& VehicleVars() const {
    return vehicle_vars_;
  }
  /// Returns vehicle resource variables for a given resource group, such that
  /// ResourceVars(r_g)[v] is the resource variable for vehicle 'v' in resource
  /// group 'r_g'.
  const std::vector<operations_research::IntVar*>& ResourceVars(
      int resource_group) const {
    return resource_vars_[resource_group];
  }
#endif  

  operations_research::IntVar* NextVar(int64_t index) const {
    return nexts_[index];
  }
  operations_research::IntVar* ActiveVar(int64_t index) const {
    return active_[index];
  }
  /// route of the vehicle is not empty, 0 otherwise.
  operations_research::IntVar* ActiveVehicleVar(int vehicle) const {
    return vehicle_active_[vehicle];
  }
  /// Returns the variable specifying whether or not the given vehicle route is
  /// considered for costs and constraints. It will be equal to 1 iff the route
  /// of the vehicle is not empty OR vehicle_used_when_empty_[vehicle] is true.
  operations_research::IntVar* VehicleRouteConsideredVar(int vehicle) const {
    return vehicle_route_considered_[vehicle];
  }
  operations_research::IntVar* VehicleVar(int64_t index) const {
    return vehicle_vars_[index];
  }
  /// Returns the resource variable for the given vehicle index in the given
  /// resource group. If a vehicle doesn't require a resource from the
  /// corresponding resource group, then ResourceVar(v, r_g) == -1.
  operations_research::IntVar* ResourceVar(int vehicle,
                                           int resource_group) const {
    DCHECK_LT(resource_group, resource_vars_.size());
    DCHECK_LT(vehicle, resource_vars_[resource_group].size());
    return resource_vars_[resource_group][vehicle];
  }
  operations_research::IntVar* CostVar() const { return cost_; }

  int64_t GetArcCostForVehicle(int64_t from_index, int64_t to_index,
                               int64_t vehicle) const;
  bool CostsAreHomogeneousAcrossVehicles() const {
    return costs_are_homogeneous_across_vehicles_;
  }
  int64_t GetHomogeneousCost(int64_t from_index, int64_t to_index) const {
    return GetArcCostForVehicle(from_index, to_index, /*vehicle=*/0);
  }
  /// Returns the cost of the arc in the context of the first solution strategy.
  /// This is typically a simplification of the actual cost; see the .cc.
  int64_t GetArcCostForFirstSolution(int64_t from_index,
                                     int64_t to_index) const;
  /// class. Input are variable indices of nodes and the cost class.
  /// Unlike GetArcCostForVehicle(), if cost_class is kNoCost, then the
  /// returned cost won't necessarily be zero: only some of the components
  /// of the cost that depend on the cost class will be omited. See the code
  /// for details.
  int64_t GetArcCostForClass(int64_t from_index, int64_t to_index,
                             int64_t /*CostClassIndex*/ cost_class_index) const;
  CostClassIndex GetCostClassIndexOfVehicle(int64_t vehicle) const {
    DCHECK(closed_);
    DCHECK_GE(vehicle, 0);
    DCHECK_LT(vehicle, cost_class_index_of_vehicle_.size());
    DCHECK_GE(cost_class_index_of_vehicle_[vehicle], 0);
    return cost_class_index_of_vehicle_[vehicle];
  }
  /// cost_class_index.
  bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const {
    DCHECK(closed_);
    if (cost_class_index == kCostClassIndexOfZeroCost) {
      return has_vehicle_with_zero_cost_class_;
    }
    return cost_class_index < cost_classes_.size();
  }
  int GetCostClassesCount() const { return cost_classes_.size(); }
  int GetNonZeroCostClassesCount() const {
    return std::max(0, GetCostClassesCount() - 1);
  }
  VehicleClassIndex GetVehicleClassIndexOfVehicle(int64_t vehicle) const {
    DCHECK(closed_);
    return vehicle_class_index_of_vehicle_[vehicle];
  }
  /// vehicles for this class.
  int GetVehicleOfClass(VehicleClassIndex vehicle_class) const {
    DCHECK(closed_);
    const RoutingModel::VehicleTypeContainer& vehicle_type_container =
        GetVehicleTypeContainer();
    if (vehicle_class.value() >= GetVehicleClassesCount() ||
        vehicle_type_container.vehicles_per_vehicle_class[vehicle_class.value()]
            .empty()) {
      return -1;
    }
    return vehicle_type_container
        .vehicles_per_vehicle_class[vehicle_class.value()]
        .front();
  }
  int GetVehicleClassesCount() const { return num_vehicle_classes_; }
  const std::vector<int>& GetSameVehicleIndicesOfIndex(int node) const {
    DCHECK(closed_);
    return same_vehicle_groups_[same_vehicle_group_[node]];
  }
  void AddSameActivityGroup(absl::Span<const int> nodes) {
    DCHECK(!closed_);
    if (nodes.size() <= 1) return;
    for (auto it = nodes.begin() + 1; it != nodes.end(); ++it) {
      solver_->AddConstraint(
          solver_->MakeEquality(ActiveVar(*it), ActiveVar(*(it - 1))));
    }
  }

  /// Returns variable indices of nodes constrained to have the same activity.
  const std::vector<int>& GetSameActivityIndicesOfIndex(int node) const {
    DCHECK(closed_);
    return same_active_var_groups_[same_active_var_group_[node]];
  }
  int GetSameActivityGroupOfIndex(int node) const {
    DCHECK(closed_);
    return same_active_var_group_[node];
  }
  const std::vector<int>& GetSameActivityGroups() const {
    DCHECK(closed_);
    return same_active_var_group_;
  }
  int GetSameActivityGroupsCount() const {
    DCHECK(closed_);
    return same_active_var_groups_.size();
  }
  const std::vector<int>& GetSameActivityIndicesOfGroup(int group) const {
    DCHECK(closed_);
    return same_active_var_groups_[group];
  }
#ifndef SWIG
  void AddOrderedActivityGroup(std::vector<DisjunctionIndex> disjunctions) {
    DCHECK(!closed_);
    if (disjunctions.size() <= 1) return;
    ordered_activity_groups_.push_back(std::move(disjunctions));
  }

  const std::vector<std::vector<DisjunctionIndex>>& GetOrderedActivityGroups()
      const {
    return ordered_activity_groups_;
  }
#endif  // SWIG
  const VehicleTypeContainer& GetVehicleTypeContainer() const {
    DCHECK(closed_);
    return vehicle_type_container_;
  }


  /// - whether the destination node is mandatory
  /// - whether the destination node is bound to the same vehicle as the source
  /// - the "primary constrained" dimension (see SetPrimaryConstrainedDimension)
  /// It then breaks ties using, in order:
  /// - the arc cost (taking unperformed penalties into account)
  /// - the size of the vehicle vars of "to1" and "to2" (lowest size wins)
  /// - the value: the lowest value of the indices to1 and to2 wins.
  /// See the .cc for details.
  /// The more constrained arc is typically preferable when building a
  /// first solution. This method is intended to be used as a callback for the
  /// BestValueByComparisonSelector value selector.
  /// Args:
  ///   from: the variable index of the source node
  ///   to1: the variable index of the first candidate destination node.
  ///   to2: the variable index of the second candidate destination node.
  bool ArcIsMoreConstrainedThanArc(int64_t from, int64_t to1, int64_t to2);
  std::string DebugOutputAssignment(
      const operations_research::Assignment& solution_assignment,
      const std::string& dimension_to_print) const;
#ifndef SWIG
  std::vector<std::vector<std::pair<int64_t, int64_t>>> GetCumulBounds(
      const operations_research::Assignment& solution_assignment,
      const RoutingDimension& dimension);
#endif
  bool CheckIfAssignmentIsFeasible(
      const operations_research::Assignment& assignment,
      bool call_at_solution_monitors);
  Solver* solver() const { return solver_.get(); }

  bool CheckLimit(absl::Duration offset = absl::ZeroDuration()) {
    DCHECK(limit_ != nullptr);
    return limit_->CheckWithOffset(offset);
  }

  absl::Duration RemainingTime() const {
    DCHECK(limit_ != nullptr);
    return limit_->AbsoluteSolverDeadline() - solver_->Now();
  }

  void UpdateTimeLimit(absl::Duration time_limit) {
    RegularLimit* limit = GetOrCreateLimit();
    limit->UpdateLimits(time_limit, std::numeric_limits<int64_t>::max(),
                        std::numeric_limits<int64_t>::max(),
                        limit->solutions());
  }

  absl::Duration TimeBuffer() const { return time_buffer_; }

  std::atomic<bool>* GetMutableCPSatInterrupt() { return &interrupt_cp_sat_; }
  std::atomic<bool>* GetMutableCPInterrupt() { return &interrupt_cp_; }

  void CancelSearch() {
    interrupt_cp_sat_ = true;
    interrupt_cp_ = true;
  }

  int nodes() const { return nodes_; }
  /// Returns the number of vehicle routes in the model.
  int vehicles() const { return vehicles_; }
  int64_t Size() const { return nodes_ + vehicles_ - start_end_count_; }

  int64_t GetNumberOfDecisionsInFirstSolution(
      const RoutingSearchParameters& search_parameters) const;
  int64_t GetNumberOfRejectsInFirstSolution(
      const RoutingSearchParameters& search_parameters) const;
  operations_research::FirstSolutionStrategy::Value
  GetAutomaticFirstSolutionStrategy() const {
    return automatic_first_solution_strategy_;
  }

  bool IsMatchingModel() const;

  /// modification to a route might impact another.
  bool AreRoutesInterdependent(const RoutingSearchParameters& parameters) const;
 
#ifndef SWIG
  using GetTabuVarsCallback =
      std::function<std::vector<operations_research::IntVar*>(RoutingModel*)>;
 
  void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback);
#endif  // SWIG

  // TODO(user): Find a way to test and restrict the access at the same time.
  DecisionBuilder* MakeGuidedSlackFinalizer(
      const RoutingDimension* dimension,
      std::function<int64_t(int64_t)> initializer);
#ifndef SWIG
  // TODO(user): MakeGreedyDescentLSOperator is too general for routing.h.
  static std::unique_ptr<LocalSearchOperator> MakeGreedyDescentLSOperator(
      std::vector<operations_research::IntVar*> variables);
  // Read access to currently registered search monitors.
  const std::vector<SearchMonitor*>& GetSearchMonitors() const {
    return monitors_;
  }
#endif  
  /// of the start of each route and a guided slack finalizer. Provided there
  /// are no time windows and the maximum slacks are large enough, once the
  /// cumul of the start of route is fixed, the guided finalizer can find
  /// optimal values of the slacks for the rest of the route in time
  /// proportional to the length of the route. Therefore the composed finalizer
  /// generally works in time O(log(t)*n*m), where t is the latest possible
  /// departute time, n is the number of nodes in the network and m is the
  /// number of vehicles.
  DecisionBuilder* MakeSelfDependentDimensionFinalizer(
      const RoutingDimension* dimension);
 
  const PathsMetadata& GetPathsMetadata() const { return paths_metadata_; }
#ifndef SWIG
  BinCapacities* GetBinCapacities() { return bin_capacities_.get(); }

  void SetSecondaryModel(RoutingModel* secondary_model,
                         RoutingSearchParameters secondary_parameters) {
    DCHECK(!closed_);
    secondary_model_ = secondary_model;
    secondary_parameters_ = std::move(secondary_parameters);
  }
#endif  // SWIG

  /// vehicle starting or ending at start_end_index.
  const std::deque<int>& GetVehiclesOfSameClass(int64_t start_end_index) const;


  std::vector<std::pair<int64_t, int64_t>> GetSameVehicleClassArcs(
      int64_t from_index, int64_t to_index) const;
 
 private:
  enum RoutingLocalSearchOperator {
    RELOCATE = 0,
    RELOCATE_PAIR,
    LIGHT_RELOCATE_PAIR,
    RELOCATE_NEIGHBORS,
    EXCHANGE,
    EXCHANGE_PAIR,
    CROSS,
    CROSS_EXCHANGE,
    TWO_OPT,
    OR_OPT,
    GLOBAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS,
    LOCAL_CHEAPEST_INSERTION_VISIT_TYPES_LNS,
    GLOBAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,
    LOCAL_CHEAPEST_INSERTION_CLOSE_NODES_LNS,
    GLOBAL_CHEAPEST_INSERTION_PATH_LNS,
    LOCAL_CHEAPEST_INSERTION_PATH_LNS,
    RELOCATE_PATH_GLOBAL_CHEAPEST_INSERTION_INSERT_UNPERFORMED,
    GLOBAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,
    LOCAL_CHEAPEST_INSERTION_EXPENSIVE_CHAIN_LNS,
    RELOCATE_EXPENSIVE_CHAIN,
    LIN_KERNIGHAN,
    TSP_OPT,
    MAKE_ACTIVE,
    RELOCATE_AND_MAKE_ACTIVE,
    MAKE_ACTIVE_AND_RELOCATE,
    EXCHANGE_AND_MAKE_ACTIVE,
    EXCHANGE_PATH_START_ENDS_AND_MAKE_ACTIVE,
    MAKE_INACTIVE,
    MAKE_CHAIN_INACTIVE,
    SWAP_ACTIVE,
    SWAP_ACTIVE_CHAIN,
    EXTENDED_SWAP_ACTIVE,
    SHORTEST_PATH_SWAP_ACTIVE,
    SHORTEST_PATH_TWO_OPT,
    NODE_PAIR_SWAP,
    PATH_LNS,
    FULL_PATH_LNS,
    TSP_LNS,
    INACTIVE_LNS,
    EXCHANGE_RELOCATE_PAIR,
    RELOCATE_SUBTRIP,
    EXCHANGE_SUBTRIP,
    LOCAL_SEARCH_OPERATOR_COUNTER
  };

  template <typename T>
  struct ValuedNodes {
    std::vector<int64_t> indices;
    T value;
  };
  struct DisjunctionValues {
    int64_t penalty;
    int64_t max_cardinality;
    PenaltyCostBehavior penalty_cost_behavior;
  };
  typedef ValuedNodes<DisjunctionValues> Disjunction;

  struct CostCacheElement {
    int index;
    CostClassIndex cost_class_index;
    int64_t cost;
  };

  template <class DimensionCumulOptimizer>
  struct DimensionCumulOptimizers {
    std::unique_ptr<DimensionCumulOptimizer> lp_optimizer;
    std::unique_ptr<DimensionCumulOptimizer> mp_optimizer;
  };

  void Initialize();
  void AddNoCycleConstraintInternal();
  bool AddDimensionWithCapacityInternal(
      const std::vector<int>& evaluator_indices,
      const std::vector<int>& cumul_dependent_evaluator_indices,
      int64_t slack_max, std::vector<int64_t> vehicle_capacities,
      bool fix_start_cumul_to_zero, const std::string& name);
  bool AddDimensionDependentDimensionWithVehicleCapacityInternal(
      const std::vector<int>& pure_transits,
      const std::vector<int>& dependent_transits,
      const RoutingDimension* base_dimension, int64_t slack_max,
      std::vector<int64_t> vehicle_capacities, bool fix_start_cumul_to_zero,
      const std::string& name);
  bool InitializeDimensionInternal(
      const std::vector<int>& evaluator_indices,
      const std::vector<int>& cumul_dependent_evaluator_indices,
      const std::vector<int>& state_dependent_evaluator_indices,
      int64_t slack_max, bool fix_start_cumul_to_zero,
      RoutingDimension* dimension);
  DimensionIndex GetDimensionIndex(absl::string_view dimension_name) const;

  void StoreDimensionCumulOptimizers(const RoutingSearchParameters& parameters);

  void FinalizeAllowedVehicles();
 
  void ComputeCostClasses(const RoutingSearchParameters& parameters);
  void ComputeVehicleClasses();
  void ComputeVehicleTypes();
  void ComputeResourceClasses();
  void FinalizeVisitTypes();
  void ComputeVisitTypesConnectedComponents();
  // Called by FinalizeVisitTypes() to setup topologically_sorted_visit_types_.
  void TopologicallySortVisitTypes();
  // This method updates topologically_sorted_node_precedences_ which contains
  // nodes in topological order based on precedence constraints for
  // dimensions of the model.
  void FinalizePrecedences();
  int64_t GetArcCostForClassInternal(int64_t from_index, int64_t to_index,
                                     CostClassIndex cost_class_index) const;
  int64_t GetArcCostWithGuidedLocalSearchPenalties(int64_t from_index,
                                                   int64_t to_index,
                                                   int64_t vehicle) const {
    return CapAdd(
        GetArcCostForVehicle(from_index, to_index, vehicle),
        solver()->GetGuidedLocalSearchPenalty(from_index, to_index, vehicle));
  }
  std::function<int64_t(int64_t, int64_t, int64_t)>
  GetLocalSearchArcCostCallback(
      const RoutingSearchParameters& parameters) const;
  int64_t GetHomogeneousArcCostWithGuidedLocalSearchPenalties(
      int64_t from_index, int64_t to_index) const {
    return GetArcCostWithGuidedLocalSearchPenalties(from_index, to_index,
                                                    /*vehicle=*/0);
  }
  std::function<int64_t(int64_t, int64_t)>
  GetLocalSearchHomogeneousArcCostCallback(
      const RoutingSearchParameters& parameters) const;
  void AppendHomogeneousArcCosts(
      const RoutingSearchParameters& parameters, int node_index,
      std::vector<operations_research::IntVar*>* cost_elements);
  void AppendArcCosts(const RoutingSearchParameters& parameters, int node_index,
                      std::vector<operations_research::IntVar*>* cost_elements);
  operations_research::Assignment* DoRestoreAssignment();
  static const CostClassIndex kCostClassIndexOfZeroCost;
  int64_t SafeGetCostClassInt64OfVehicle(int64_t vehicle) const {
    DCHECK_LT(0, vehicles_);
    return (vehicle >= 0 ? GetCostClassIndexOfVehicle(vehicle)
                         : kCostClassIndexOfZeroCost)
        .value();
  }
  int64_t GetDimensionTransitCostSum(int64_t i, int64_t j,
                                     const CostClass& cost_class) const;
  operations_research::IntVar* CreateDisjunction(DisjunctionIndex disjunction);
  void AddPickupAndDeliverySetsInternal(const std::vector<int64_t>& pickups,
                                        const std::vector<int64_t>& deliveries);
  operations_research::IntVar* CreateSameVehicleCost(int vehicle_index);
  int FindNextActive(int index, absl::Span<const int64_t> indices) const;

  bool RouteCanBeUsedByVehicle(
      const operations_research::Assignment& assignment, int start_index,
      int vehicle) const;
  bool ReplaceUnusedVehicle(
      int unused_vehicle, int active_vehicle,
      operations_research::Assignment* compact_assignment) const;
 
  void QuietCloseModel();
  void QuietCloseModelWithParameters(
      const RoutingSearchParameters& parameters) {
    if (!closed_) {
      CloseModelWithParameters(parameters);
    }
  }

  bool SolveMatchingModel(operations_research::Assignment* assignment,
                          const RoutingSearchParameters& parameters);
#ifndef SWIG
  bool AppendAssignmentIfFeasible(
      const operations_research::Assignment& assignment,
      std::vector<std::unique_ptr<operations_research::Assignment>>*
          assignments,
      bool call_at_solution_monitors = true);
#endif
  void LogSolution(const RoutingSearchParameters& parameters,
                   absl::string_view description, int64_t solution_cost,
                   int64_t start_time_ms);
  operations_research::Assignment* CompactAssignmentInternal(
      const operations_research::Assignment& assignment,
      bool check_compact_assignment) const;
  std::string FindErrorInSearchParametersForModel(
      const RoutingSearchParameters& search_parameters) const;
  void SetupSearch(const RoutingSearchParameters& search_parameters);
  void UpdateSearchFromParametersIfNeeded(
      const RoutingSearchParameters& search_parameters);
  // TODO(user): Document each auxiliary method.
  operations_research::Assignment* GetOrCreateAssignment();
  operations_research::Assignment* GetOrCreateTmpAssignment();
  RegularLimit* GetOrCreateLimit();
  RegularLimit* GetOrCreateCumulativeLimit();
  RegularLimit* GetOrCreateLocalSearchLimit();
  RegularLimit* GetOrCreateLargeNeighborhoodSearchLimit();
  RegularLimit* GetOrCreateFirstSolutionLargeNeighborhoodSearchLimit();
  LocalSearchOperator* CreateInsertionOperator();
  LocalSearchOperator* CreateMakeInactiveOperator();
  void CreateNeighborhoodOperators(const RoutingSearchParameters& parameters);
  LocalSearchOperator* ConcatenateOperators(
      const RoutingSearchParameters& search_parameters,
      const std::vector<LocalSearchOperator*>& operators) const;
  LocalSearchOperator* GetNeighborhoodOperators(
      const RoutingSearchParameters& search_parameters,
      const absl::flat_hash_set<RoutingLocalSearchOperator>&
          operators_to_consider) const;
 
  struct FilterOptions {
    bool filter_objective;
    bool filter_with_cp_solver;
 
    bool operator==(const FilterOptions& other) const {
      return other.filter_objective == filter_objective &&
             other.filter_with_cp_solver == filter_with_cp_solver;
    }
    template <typename H>
    friend H AbslHashValue(H h, const FilterOptions& options) {
      return H::combine(std::move(h), options.filter_objective,
                        options.filter_with_cp_solver);
    }
  };
  std::vector<LocalSearchFilterManager::FilterEvent> CreateLocalSearchFilters(
      const RoutingSearchParameters& parameters, const FilterOptions& options);
  LocalSearchFilterManager* GetOrCreateLocalSearchFilterManager(
      const RoutingSearchParameters& parameters, const FilterOptions& options);
  DecisionBuilder* CreateSolutionFinalizer(
      const RoutingSearchParameters& parameters);
  void CreateFirstSolutionDecisionBuilders(
      const RoutingSearchParameters& search_parameters);
  DecisionBuilder* GetFirstSolutionDecisionBuilder(
      const RoutingSearchParameters& search_parameters) const;
  IntVarFilteredDecisionBuilder* GetFilteredFirstSolutionDecisionBuilderOrNull(
      const RoutingSearchParameters& parameters) const;
#ifndef SWIG
  template <typename Heuristic, typename... Args>
  IntVarFilteredDecisionBuilder* CreateIntVarFilteredDecisionBuilder(
      const Args&... args);
#endif
  LocalSearchPhaseParameters* CreateLocalSearchParameters(
      const RoutingSearchParameters& search_parameters, bool secondary_ls);
  DecisionBuilder* CreatePrimaryLocalSearchDecisionBuilder(
      const RoutingSearchParameters& search_parameters);
  void SetupDecisionBuilders(const RoutingSearchParameters& search_parameters);
  void SetupMetaheuristics(const RoutingSearchParameters& search_parameters);
  void SetupAssignmentCollector(
      const RoutingSearchParameters& search_parameters);
  void SetupTrace(const RoutingSearchParameters& search_parameters);
  void SetupImprovementLimit(const RoutingSearchParameters& search_parameters);
  void SetupSearchMonitors(const RoutingSearchParameters& search_parameters);
  bool UsesLightPropagation(
      const RoutingSearchParameters& search_parameters) const;
  GetTabuVarsCallback tabu_var_callback_;
 
  // Detects implicit pickup delivery pairs. These pairs are
  // non-pickup/delivery pairs for which there exists a unary dimension such
  // that the demand d of the implicit pickup is positive and the demand of the
  // implicit delivery is equal to -d.
  void DetectImplicitPickupAndDeliveries();
 
  int GetVehicleStartClass(int64_t start) const;
 
  void InitSameVehicleGroups(int number_of_groups) {
    same_vehicle_group_.assign(Size(), 0);
    same_vehicle_groups_.assign(number_of_groups, {});
  }
  void SetSameVehicleGroup(int index, int group) {
    same_vehicle_group_[index] = group;
    same_vehicle_groups_[group].push_back(index);
  }
 
  void InitSameActiveVarGroups(int number_of_groups) {
    same_active_var_group_.assign(Size(), 0);
    same_active_var_groups_.assign(number_of_groups, {});
  }
  void SetSameActiveVarGroup(int index, int group) {
    same_active_var_group_[index] = group;
    same_active_var_groups_[group].push_back(index);
  }

  int GetGlobalCumulOptimizerIndex(const RoutingDimension& dimension) const;
  int GetLocalCumulOptimizerIndex(const RoutingDimension& dimension) const;

  std::unique_ptr<Solver> solver_;
  int nodes_;
  int vehicles_;
  int max_active_vehicles_;
  Constraint* no_cycle_constraint_ = nullptr;
  std::vector<operations_research::IntVar*> nexts_;
  std::vector<operations_research::IntVar*> vehicle_vars_;
  std::vector<operations_research::IntVar*> active_;
  // clang-format off
  std::vector<std::vector<operations_research::IntVar*> > resource_vars_;
  // clang-format on
  // The following vectors are indexed by vehicle index.
  std::vector<operations_research::IntVar*> vehicle_active_;
  std::vector<operations_research::IntVar*> vehicle_route_considered_;
  std::vector<operations_research::IntVar*> is_bound_to_end_;
  mutable RevSwitch is_bound_to_end_ct_added_;
  absl::flat_hash_map<std::string, DimensionIndex> dimension_name_to_index_;
  util_intops::StrongVector<DimensionIndex, RoutingDimension*> dimensions_;
  // clang-format off
  std::vector<std::unique_ptr<ResourceGroup> > resource_groups_;
  util_intops::StrongVector<DimensionIndex, std::vector<int> >
      dimension_resource_group_indices_;

  std::vector<DimensionCumulOptimizers<GlobalDimensionCumulOptimizer> >
      global_dimension_optimizers_;
  util_intops::StrongVector<DimensionIndex, int> global_optimizer_index_;
  std::vector<DimensionCumulOptimizers<LocalDimensionCumulOptimizer> >
      local_dimension_optimizers_;
  util_intops::StrongVector<DimensionIndex, int> local_optimizer_index_;
  // clang-format on
  std::string primary_constrained_dimension_;
  operations_research::IntVar* cost_ = nullptr;
  std::vector<int> vehicle_to_transit_cost_;
  std::vector<int64_t> fixed_cost_of_vehicle_;
  std::vector<CostClassIndex> cost_class_index_of_vehicle_;
  bool has_vehicle_with_zero_cost_class_;
  std::vector<int64_t> linear_cost_factor_of_vehicle_;
  std::vector<int64_t> quadratic_cost_factor_of_vehicle_;
  bool vehicle_amortized_cost_factors_set_;
  mutable std::vector<
      absl::AnyInvocable<std::optional<int64_t>(const std::vector<int64_t>&)>>
      route_evaluators_;
  std::vector<bool> vehicle_used_when_empty_;
#ifndef SWIG
  absl::flat_hash_map<
      std::pair<std::string, std::string>,
      std::vector<Solver::PathEnergyCostConstraintSpecification::EnergyCost>,
      absl::Hash<std::pair<std::string, std::string>>>
      force_distance_to_energy_costs_;
  util_intops::StrongVector<CostClassIndex, CostClass> cost_classes_;
#endif  // SWIG
  bool costs_are_homogeneous_across_vehicles_;
  bool cache_callbacks_;
  mutable std::vector<CostCacheElement> cost_cache_;  
  std::vector<VehicleClassIndex> vehicle_class_index_of_vehicle_;
  int num_vehicle_classes_;
 
  VehicleTypeContainer vehicle_type_container_;
  std::function<int(int64_t)> vehicle_start_class_callback_;
  util_intops::StrongVector<DisjunctionIndex, Disjunction> disjunctions_;
  // clang-format off
  std::vector<std::vector<DisjunctionIndex> > index_to_disjunctions_;
  std::vector<ValuedNodes<int64_t> > same_vehicle_costs_;
#ifndef SWIG
  std::vector<absl::flat_hash_set<int>> allowed_vehicles_;
#endif  // SWIG
  std::vector<PickupDeliveryPair> pickup_delivery_pairs_;
  std::vector<PickupDeliveryPair>
      implicit_pickup_delivery_pairs_without_alternatives_;
  std::vector<std::pair<DisjunctionIndex, DisjunctionIndex> >
      pickup_delivery_disjunctions_;
  // If node_index is a pickup, index_to_pickup_position_[node_index] contains
  // the PickupDeliveryPosition {pickup_delivery_index, alternative_index}
  // such that (pickup_delivery_pairs_[pickup_delivery_index]
  //               .pickup_alternatives)[alternative_index] == node_index
  std::vector<PickupDeliveryPosition> index_to_pickup_position_;
  // Same as above for deliveries.
  std::vector<PickupDeliveryPosition> index_to_delivery_position_;
  // clang-format on
  std::vector<PickupAndDeliveryPolicy> vehicle_pickup_delivery_policy_;
  // Same vehicle group to which a node belongs.
  std::vector<int> same_vehicle_group_;
  // Same vehicle node groups.
  std::vector<std::vector<int>> same_vehicle_groups_;
  // Same active var group to which a node belongs.
  std::vector<int> same_active_var_group_;
  // Same active var groups.
  std::vector<std::vector<int>> same_active_var_groups_;
  // Ordered activity groups.
  std::vector<std::vector<DisjunctionIndex>> ordered_activity_groups_;
  // Node visit types
  // Variable index to visit type index.
  std::vector<int> index_to_visit_type_;
  // Variable index to VisitTypePolicy.
  std::vector<VisitTypePolicy> index_to_type_policy_;
  // clang-format off
  std::vector<std::vector<int> > single_nodes_of_type_;
  std::vector<std::vector<int> > pair_indices_of_type_;
 
  std::vector<absl::flat_hash_set<int> >
      hard_incompatible_types_per_type_index_;
  std::vector<absl::flat_hash_set<int> >
      temporal_incompatible_types_per_type_index_;
  const absl::flat_hash_set<int> empty_incompatibility_set_;
 
  std::vector<std::vector<absl::flat_hash_set<int> > >
      same_vehicle_required_type_alternatives_per_type_index_;
  std::vector<std::vector<absl::flat_hash_set<int> > >
      required_type_alternatives_when_adding_type_index_;
  std::vector<std::vector<absl::flat_hash_set<int> > >
      required_type_alternatives_when_removing_type_index_;
  const std::vector<absl::flat_hash_set<int>> empty_required_type_alternatives_;
  absl::flat_hash_map</*type*/int, absl::flat_hash_set<VisitTypePolicy> >
      trivially_infeasible_visit_types_to_policies_;
 
  // Visit types sorted topologically based on required-->dependent requirement
  // arcs between the types (if the requirement/dependency graph is acyclic).
  // Visit types of the same topological level are sorted in each sub-vector
  // by decreasing requirement "tightness", computed as the pair of the two
  // following criteria:
  //
  // 1) How highly *dependent* this type is, determined by
  //    (total number of required alternative sets for that type)
  //        / (average number of types in the required alternative sets)
  // 2) How highly *required* this type t is, computed as
  //    SUM_{S required set containing t} ( 1 / |S| ),
  //    i.e. the sum of reverse number of elements of all required sets
  //    containing the type t.
  //
  // The higher these two numbers, the tighter the type is wrt requirements.
  std::vector<std::vector<int> > topologically_sorted_visit_types_;
  std::vector<std::vector<int>> visit_type_components_;
  // clang-format on
  int num_visit_types_;
  std::vector<std::vector<std::vector<int>>>
      topologically_sorted_node_precedences_;
  // Two indices are equivalent if they correspond to the same node (as given
  // to the constructors taking a RoutingIndexManager).
  std::vector<int> index_to_equivalence_class_;
  const PathsMetadata paths_metadata_;
  // TODO(user): b/62478706 Once the port is done, this shouldn't be needed
  //                  anymore.
  RoutingIndexManager manager_;
  int start_end_count_;
  // Model status
  bool closed_ = false;
  RoutingSearchStatus::Value status_ = RoutingSearchStatus::ROUTING_NOT_SOLVED;
  bool enable_deep_serialization_ = true;
 
  // Secondary routing solver
  RoutingModel* secondary_model_ = nullptr;
  RoutingSearchParameters secondary_parameters_;
  std::unique_ptr<SecondaryOptimizer> secondary_optimizer_;
 
  // Search data
  std::vector<DecisionBuilder*> first_solution_decision_builders_;
  std::vector<IntVarFilteredDecisionBuilder*>
      first_solution_filtered_decision_builders_;
  Solver::IndexEvaluator2 first_solution_evaluator_;
  FirstSolutionStrategy::Value automatic_first_solution_strategy_ =
      FirstSolutionStrategy::UNSET;
  const operations_research::Assignment* hint_ = nullptr;
  std::vector<LocalSearchOperator*> local_search_operators_;
  std::vector<SearchMonitor*> monitors_;
  std::vector<SearchMonitor*> secondary_ls_monitors_;
  std::vector<SearchMonitor*> at_solution_monitors_;
  std::vector<std::function<void()>> restore_dimension_values_reset_callbacks_;
  int monitors_before_setup_ = 0;
  int monitors_after_setup_ = 0;
  SearchMonitor* metaheuristic_ = nullptr;
  SearchMonitor* search_log_ = nullptr;
  bool local_optimum_reached_ = false;
  // Best lower bound found during the search.
  int64_t objective_lower_bound_ = kint64min;
  SolutionCollector* collect_assignments_ = nullptr;
  SolutionCollector* collect_secondary_ls_assignments_ = nullptr;
  SolutionCollector* collect_one_assignment_ = nullptr;
  SolutionCollector* optimized_dimensions_assignment_collector_ = nullptr;
  RoutingSearchParameters search_parameters_;
  DecisionBuilder* solve_db_ = nullptr;
  DecisionBuilder* improve_db_ = nullptr;
  DecisionBuilder* secondary_ls_db_ = nullptr;
  DecisionBuilder* restore_assignment_ = nullptr;
  DecisionBuilder* restore_tmp_assignment_ = nullptr;
  operations_research::Assignment* assignment_ = nullptr;
  operations_research::Assignment* preassignment_ = nullptr;
  operations_research::Assignment* tmp_assignment_ = nullptr;
  LocalSearchOperator* primary_ls_operator_ = nullptr;
  LocalSearchOperator* secondary_ls_operator_ = nullptr;
  std::vector<operations_research::IntVar*> extra_vars_;
  std::vector<IntervalVar*> extra_intervals_;
  std::vector<LocalSearchOperator*> extra_operators_;
  absl::flat_hash_map<FilterOptions, LocalSearchFilterManager*>
      local_search_filter_managers_;
  std::vector<LocalSearchFilterManager::FilterEvent> extra_filters_;
  absl::flat_hash_map<NodeNeighborsParameters,
                      std::unique_ptr<NodeNeighborsByCostClass>>
      node_neighbors_by_cost_class_per_size_;
  std::unique_ptr<FinalizerVariables> finalizer_variables_;
#ifndef SWIG
  std::unique_ptr<SweepArranger> sweep_arranger_;
#endif
 
  RegularLimit* limit_ = nullptr;
  RegularLimit* cumulative_limit_ = nullptr;
  RegularLimit* ls_limit_ = nullptr;
  RegularLimit* lns_limit_ = nullptr;
  RegularLimit* first_solution_lns_limit_ = nullptr;
  absl::Duration time_buffer_;
 
  RoutingSearchStats search_stats_;
 
  std::atomic<bool> interrupt_cp_sat_;
  std::atomic<bool> interrupt_cp_;
 
  typedef std::pair<int64_t, int64_t> CacheKey;
  typedef absl::flat_hash_map<CacheKey, int64_t> TransitCallbackCache;
  typedef absl::flat_hash_map<CacheKey, StateDependentTransit>
      StateDependentTransitCallbackCache;
 
  // All transit callbacks are stored in transit_evaluators_,
  // we refer to callbacks by the index in this vector.
  // We maintain unary_transit_evaluators_[] (with the same size) to store
  // callbacks that are unary:
  // - if a callback is unary, it is in unary_transit_evaluators_[i],
  //   and a binary version is stored at transit_evaluators_[i].
  // - if a callback is binary, it is stored at transit_evaluators_[i],
  //   and unary_transit_evaluators_[i] is nullptr.
  std::vector<TransitCallback1> unary_transit_evaluators_;
  std::vector<TransitCallback2> transit_evaluators_;
  std::vector<TransitEvaluatorSign> transit_evaluator_sign_;
 
  std::vector<VariableIndexEvaluator2> state_dependent_transit_evaluators_;
  std::vector<std::unique_ptr<StateDependentTransitCallbackCache>>
      state_dependent_transit_evaluators_cache_;
 
  std::vector<CumulDependentTransitCallback2>
      cumul_dependent_transit_evaluators_;
 
  // Returns global BinCapacities state, may be nullptr.
  std::unique_ptr<BinCapacities> bin_capacities_;
 
  friend class RoutingDimension;
  friend class RoutingModelInspector;
  friend class ResourceGroup::Resource;
};

class OR_DLL RoutingModelVisitor : public operations_research::BaseObject {
 public:
  static const char kLightElement[];
  static const char kLightElement2[];
  static const char kRemoveValues[];
};
 
#if !defined(SWIG)
void FillPathEvaluation(absl::Span<const int64_t> path,
                        const RoutingModel::TransitCallback2& evaluator,
                        std::vector<int64_t>* values);
#endif  // !defined(SWIG)
 
class TypeRegulationsChecker {
 public:
  explicit TypeRegulationsChecker(const RoutingModel& model);
  virtual ~TypeRegulationsChecker() = default;
 
  bool CheckVehicle(int vehicle,
                    const std::function<int64_t(int64_t)>& next_accessor);
 
 protected:
#ifndef SWIG
  using VisitTypePolicy = RoutingModel::VisitTypePolicy;
#endif  // SWIG
 
  struct TypePolicyOccurrence {
    int num_type_added_to_vehicle = 0;
    int num_type_removed_from_vehicle = 0;
    /// If positive, the type is considered on the vehicle from the start of the
    /// route until this position.
    int position_of_last_type_on_vehicle_up_to_visit = -1;
  };

  bool TypeOccursOnRoute(int type) const;
  bool TypeCurrentlyOnRoute(int type, int pos) const;
 
  void InitializeCheck(int vehicle,
                       const std::function<int64_t(int64_t)>& next_accessor);
  virtual void OnInitializeCheck() {}
  virtual bool HasRegulationsToCheck() const = 0;
  virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy,
                                    int pos) = 0;
  virtual bool FinalizeCheck() const { return true; }
 
  const RoutingModel& model_;
 
 private:
  std::vector<TypePolicyOccurrence> occurrences_of_type_;
  std::vector<int64_t> current_route_visits_;
};

class TypeIncompatibilityChecker : public TypeRegulationsChecker {
 public:
  TypeIncompatibilityChecker(const RoutingModel& model,
                             bool check_hard_incompatibilities);
  ~TypeIncompatibilityChecker() override = default;
 
 private:
  bool HasRegulationsToCheck() const override;
  bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos) override;

  bool check_hard_incompatibilities_;
};

class TypeRequirementChecker : public TypeRegulationsChecker {
 public:
  explicit TypeRequirementChecker(const RoutingModel& model)
      : TypeRegulationsChecker(model) {}
  ~TypeRequirementChecker() override = default;
 
 private:
  bool HasRegulationsToCheck() const override;
  void OnInitializeCheck() override {
    types_with_same_vehicle_requirements_on_route_.clear();
  }
  // clang-format off
  /// the required types is on the route at position 'pos'.
  bool CheckRequiredTypesCurrentlyOnRoute(
      absl::Span<const absl::flat_hash_set<int>>  required_type_alternatives,
      int pos);
  // clang-format on
  bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos) override;
  bool FinalizeCheck() const override;
 
  absl::flat_hash_set<int> types_with_same_vehicle_requirements_on_route_;
};


class TypeRegulationsConstraint : public operations_research::Constraint {
 public:
  explicit TypeRegulationsConstraint(const RoutingModel& model);
 
  void Post() override;
  void InitialPropagate() override;
 
 private:
  void PropagateNodeRegulations(int node);
  void CheckRegulationsOnVehicle(int vehicle);
 
  const RoutingModel& model_;
  TypeIncompatibilityChecker incompatibility_checker_;
  TypeRequirementChecker requirement_checker_;
  std::vector<Demon*> vehicle_demons_;
};

struct BoundCost {
  int64_t bound;
  int64_t cost;
  BoundCost() : bound(0), cost(0) {}
  BoundCost(int64_t bound, int64_t cost) : bound(bound), cost(cost) {}
};
 
class SimpleBoundCosts {
 public:
  SimpleBoundCosts(int num_bounds, BoundCost default_bound_cost)
      : bound_costs_(num_bounds, default_bound_cost) {}
#ifndef SWIG
  BoundCost& bound_cost(int element) { return bound_costs_[element]; }
#endif
  BoundCost bound_cost(int element) const { return bound_costs_[element]; }
  int Size() { return bound_costs_.size(); }
  SimpleBoundCosts(const SimpleBoundCosts&) = delete;
  SimpleBoundCosts operator=(const SimpleBoundCosts&) = delete;
 
 private:
  std::vector<BoundCost> bound_costs_;
};

/// Dimensions represent quantities accumulated at nodes along the routes. They
/// represent quantities such as weights or volumes carried along the route, or
/// distance or times.
///
/// Quantities at a node are represented by "cumul" variables and the increase
/// or decrease of quantities between nodes are represented by "transit"
/// variables. These variables are linked as follows:
///
/// if j == next(i),
/// cumuls(j) = cumuls(i) + transits(i) + slacks(i) +
///             state_dependent_transits(i)
///
/// where slack is a positive slack variable (can represent waiting times for
/// a time dimension), and state_dependent_transits is a non-purely functional
/// version of transits_. Favour transits over state_dependent_transits when
/// possible, because purely functional callbacks allow more optimisations and
/// make the model faster and easier to solve.
// TODO(user): Break constraints need to know the service time of nodes
class RoutingDimension {
 public:
  // This type is neither copyable nor movable.
  RoutingDimension(const RoutingDimension&) = delete;
  RoutingDimension& operator=(const RoutingDimension&) = delete;
 
  ~RoutingDimension();
  RoutingModel* model() const { return model_; }
  int64_t GetTransitValue(int64_t from_index, int64_t to_index,
                          int64_t vehicle) const;
  int64_t GetTransitValueFromClass(int64_t from_index, int64_t to_index,
                                   int64_t vehicle_class) const {
    return model_->TransitCallback(class_evaluators_[vehicle_class])(from_index,
                                                                     to_index);
  }
  operations_research::IntVar* CumulVar(int64_t index) const {
    return cumuls_[index];
  }
  operations_research::IntVar* TransitVar(int64_t index) const {
    return transits_[index];
  }
  operations_research::IntVar* FixedTransitVar(int64_t index) const {
    return fixed_transits_[index];
  }
  operations_research::IntVar* SlackVar(int64_t index) const {
    return slacks_[index];
  }

  // TODO(user): Routing should not store its data in a CP model.


  void SetCumulVarRange(int64_t index, int64_t min, int64_t max) {
    CumulVar(index)->SetRange(min, max);
  }
  int64_t GetCumulVarMin(int64_t index) const { return CumulVar(index)->Min(); }
  int64_t GetCumulVarMax(int64_t index) const { return CumulVar(index)->Max(); }
 
#if !defined(SWIGPYTHON)

  /// vectors instead (indexed by int64_t var index).
  const std::vector<operations_research::IntVar*>& cumuls() const {
    return cumuls_;
  }
  const std::vector<operations_research::IntVar*>& fixed_transits() const {
    return fixed_transits_;
  }
  const std::vector<operations_research::IntVar*>& transits() const {
    return transits_;
  }
  const std::vector<operations_research::IntVar*>& slacks() const {
    return slacks_;
  }
#if !defined(SWIGCSHARP) && !defined(SWIGJAVA)
  const std::vector<SortedDisjointIntervalList>& forbidden_intervals() const {
    return forbidden_intervals_;
  }
  SortedDisjointIntervalList GetAllowedIntervalsInRange(
      int64_t index, int64_t min_value, int64_t max_value) const;
  int64_t GetFirstPossibleGreaterOrEqualValueForNode(int64_t index,
                                                     int64_t min_value) const {
    DCHECK_LT(index, forbidden_intervals_.size());
    const SortedDisjointIntervalList& forbidden_intervals =
        forbidden_intervals_[index];
    const auto first_forbidden_interval_it =
        forbidden_intervals.FirstIntervalGreaterOrEqual(min_value);
    if (first_forbidden_interval_it != forbidden_intervals.end() &&
        min_value >= first_forbidden_interval_it->start) {

      return CapAdd(first_forbidden_interval_it->end, 1);
    }
    return min_value;
  }
  int64_t GetLastPossibleLessOrEqualValueForNode(int64_t index,
                                                 int64_t max_value) const {
    DCHECK_LT(index, forbidden_intervals_.size());
    const SortedDisjointIntervalList& forbidden_intervals =
        forbidden_intervals_[index];
    const auto last_forbidden_interval_it =
        forbidden_intervals.LastIntervalLessOrEqual(max_value);
    if (last_forbidden_interval_it != forbidden_intervals.end() &&
        max_value <= last_forbidden_interval_it->end) {
      return CapSub(last_forbidden_interval_it->start, 1);
    }
    return max_value;
  }

  const std::vector<int64_t>& vehicle_capacities() const {
    return vehicle_capacities_;
  }
  /// Returns the callback evaluating the transit value between two node indices
  /// for a given vehicle.
  const RoutingModel::TransitCallback2& transit_evaluator(int vehicle) const {
    return model_->TransitCallback(
        class_evaluators_[vehicle_to_class_[vehicle]]);
  }

  const RoutingModel::TransitCallback2& class_transit_evaluator(
      RoutingVehicleClassIndex vehicle_class) const {
    const int vehicle = model_->GetVehicleOfClass(vehicle_class);
    DCHECK_NE(vehicle, -1);
    return transit_evaluator(vehicle);
  }

  /// Returns true iff all transit evaluators for this dimension are unary.
  bool IsUnary() const {
    for (int evaluator_index : class_evaluators_) {
      if (model_->UnaryTransitCallbackOrNull(evaluator_index) == nullptr) {
        return false;
      }
    }
    return true;
  }

  /// returns a null callback.
  const RoutingModel::TransitCallback1& GetUnaryTransitEvaluator(
      int vehicle) const {
    return model_->UnaryTransitCallbackOrNull(
        class_evaluators_[vehicle_to_class_[vehicle]]);
  }
  const RoutingModel::TransitCallback2& GetBinaryTransitEvaluator(
      int vehicle) const {
    return model_->TransitCallback(
        class_evaluators_[vehicle_to_class_[vehicle]]);
  }
  bool AreVehicleTransitsPositive(int vehicle) const {
    const int evaluator_index = class_evaluators_[vehicle_to_class_[vehicle]];
    return model()->transit_evaluator_sign_[evaluator_index] ==
           RoutingModel::kTransitEvaluatorSignPositiveOrZero;
  }
  bool AllTransitEvaluatorSignsAreUnknown() const;
  RoutingModel::TransitEvaluatorSign GetTransitEvaluatorSign(
      int vehicle) const {
    const int evaluator_index = class_evaluators_[vehicle_to_class_[vehicle]];
    return model()->transit_evaluator_sign_[evaluator_index];
  }
  int vehicle_to_class(int vehicle) const { return vehicle_to_class_[vehicle]; }
  int vehicle_to_cumul_dependent_class(int vehicle) const {
    if (vehicle_to_cumul_dependent_class_.empty()) {
      return -1;
    }
    DCHECK_LT(vehicle, vehicle_to_cumul_dependent_class_.size());
    return vehicle_to_cumul_dependent_class_[vehicle];
  }
#endif  
#endif  
  void SetSpanUpperBoundForVehicle(int64_t upper_bound, int vehicle);
  /// Sets a cost proportional to the dimension span on a given vehicle,
  /// or on all vehicles at once. "coefficient" must be nonnegative.
  /// This is handy to model costs proportional to idle time when the dimension
  /// represents time.
  /// The cost for a vehicle is
  ///   span_cost = coefficient * (dimension end value - dimension start value).
  void SetSpanCostCoefficientForVehicle(int64_t coefficient, int vehicle);
  void SetSpanCostCoefficientForAllVehicles(int64_t coefficient);

  void SetSlackCostCoefficientForVehicle(int64_t coefficient, int vehicle);
  void SetSlackCostCoefficientForAllVehicles(int64_t coefficient);
  void SetGlobalSpanCostCoefficient(int64_t coefficient);
 
#ifndef SWIG
  void SetCumulVarPiecewiseLinearCost(int64_t index,
                                      const PiecewiseLinearFunction& cost);
  bool HasCumulVarPiecewiseLinearCost(int64_t index) const;
  const PiecewiseLinearFunction* GetCumulVarPiecewiseLinearCost(
      int64_t index) const;
#endif

  void SetCumulVarSoftUpperBound(int64_t index, int64_t upper_bound,
                                 int64_t coefficient);
  bool HasCumulVarSoftUpperBound(int64_t index) const;
  int64_t GetCumulVarSoftUpperBound(int64_t index) const;
  int64_t GetCumulVarSoftUpperBoundCoefficient(int64_t index) const;

  void SetCumulVarSoftLowerBound(int64_t index, int64_t lower_bound,
                                 int64_t coefficient);
  bool HasCumulVarSoftLowerBound(int64_t index) const;
  int64_t GetCumulVarSoftLowerBound(int64_t index) const;
  int64_t GetCumulVarSoftLowerBoundCoefficient(int64_t index) const;
  // TODO(user): Remove if !defined when routing.swig is repaired.
#if !defined(SWIGPYTHON)
  void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks, int vehicle,
                                  int pre_travel_evaluator,
                                  int post_travel_evaluator);
#endif  // !defined(SWIGPYTHON)

  void SetBreakIntervalsOfVehicle(std::vector<IntervalVar*> breaks, int vehicle,
                                  std::vector<int64_t> node_visit_transits);

  void SetBreakDistanceDurationOfVehicle(int64_t distance, int64_t duration,
                                         int vehicle);
  void InitializeBreaks();
  bool HasBreakConstraints() const;
#if !defined(SWIGPYTHON)
  void SetBreakIntervalsOfVehicle(
      std::vector<IntervalVar*> breaks, int vehicle,
      std::vector<int64_t> node_visit_transits,
      std::function<int64_t(int64_t, int64_t)> delays);

  const std::vector<IntervalVar*>& GetBreakIntervalsOfVehicle(
      int vehicle) const;
  // clang-format off
  const std::vector<std::pair<int64_t, int64_t> >&
      GetBreakDistanceDurationOfVehicle(int vehicle) const;
  // clang-format on
#endif  
  int GetPreTravelEvaluatorOfVehicle(int vehicle) const;
  int GetPostTravelEvaluatorOfVehicle(int vehicle) const;

  const RoutingDimension* base_dimension() const { return base_dimension_; }
  int64_t ShortestTransitionSlack(int64_t node) const;

  operations_research::RoutingDimensionIndex index() const {
    return index_;
  }
  const std::string& name() const { return name_; }

#ifndef SWIG
  const ReverseArcListGraph<int, int>& GetPathPrecedenceGraph() const {
    return path_precedence_graph_;
  }
#endif  // SWIG

  /// each pickup (delivery) index is in a single pickup/delivery pair.first
  /// (pair.second).
  typedef std::function<int64_t(int, int)> PickupToDeliveryLimitFunction;
 
  void SetPickupToDeliveryLimitFunctionForPair(
      PickupToDeliveryLimitFunction limit_function, int pair_index);
 
  bool HasPickupToDeliveryLimits() const;
#ifndef SWIG
  int64_t GetPickupToDeliveryLimitForPair(int pair_index,
                                          int pickup_alternative_index,
                                          int delivery_alternative_index) const;
 
  struct NodePrecedence {
    int64_t first_node;
    int64_t second_node;
    int64_t offset;
    enum class PerformedConstraint {
      // first_node and/or second_node can be unperformed.
      kFirstAndSecondIndependent,
      // if second_node is performed, first_node must be performed.
      kSecondImpliesFirst,
      // if first_node is performed, second_node must be performed.
      kFirstImpliesSecond,
      // first_node is performed iff second_node is performed.
      kFirstAndSecondEqual,
    };
    PerformedConstraint performed_constraint;
  };
 
  void AddNodePrecedence(NodePrecedence precedence) {
    node_precedences_.push_back(precedence);
  }
  const std::vector<NodePrecedence>& GetNodePrecedences() const {
    return node_precedences_;
  }
  /// the performed status of the first and second node of a precedence.
  enum class PrecedenceStatus {
    kActive,
    kInactive,
    kInvalid,
  };
  static PrecedenceStatus GetPrecedenceStatus(
      bool first_unperformed, bool second_unperformed,
      NodePrecedence::PerformedConstraint performed_constraint) {
    switch (performed_constraint) {
      case NodePrecedence::PerformedConstraint::kFirstAndSecondIndependent:
        if (first_unperformed || second_unperformed) {
          return PrecedenceStatus::kInactive;
        }
        break;
      case NodePrecedence::PerformedConstraint::kSecondImpliesFirst:
        if (first_unperformed) {
          if (!second_unperformed) return PrecedenceStatus::kInvalid;
          return PrecedenceStatus::kInactive;
        }
        if (second_unperformed) return PrecedenceStatus::kInactive;
        break;
      case NodePrecedence::PerformedConstraint::kFirstImpliesSecond:
        if (second_unperformed) {
          if (!first_unperformed) return PrecedenceStatus::kInvalid;
          return PrecedenceStatus::kInactive;
        }
        if (first_unperformed) return PrecedenceStatus::kInactive;
        break;
      case NodePrecedence::PerformedConstraint::kFirstAndSecondEqual:
        if (first_unperformed != second_unperformed) {
          return PrecedenceStatus::kInvalid;
        }
        if (first_unperformed) return PrecedenceStatus::kInactive;
        break;
    }
    return PrecedenceStatus::kActive;
  }
  void AddNodePrecedence(
      int64_t first_node, int64_t second_node, int64_t offset,
      NodePrecedence::PerformedConstraint performed_constraint =
          NodePrecedence::PerformedConstraint::kFirstAndSecondIndependent) {
    AddNodePrecedence({first_node, second_node, offset, performed_constraint});
  }
#else
  void AddNodePrecedence(int64_t first_node, int64_t second_node,
                         int64_t offset) {
    AddNodePrecedence(
        {first_node, second_node, offset,
         NodePrecedence::PerformedConstraint::kFirstAndSecondIndependent});
  }
#endif  // SWIG
 
  int64_t GetSpanUpperBoundForVehicle(int vehicle) const {
    return vehicle_span_upper_bounds_[vehicle];
  }
#ifndef SWIG
  const std::vector<int64_t>& vehicle_span_upper_bounds() const {
    return vehicle_span_upper_bounds_;
  }
#endif  // SWIG
  int64_t GetSpanCostCoefficientForVehicle(int vehicle) const {
    return vehicle_span_cost_coefficients_[vehicle];
  }
#ifndef SWIG
  int64_t GetSpanCostCoefficientForVehicleClass(
      RoutingVehicleClassIndex vehicle_class) const {
    const int vehicle = model_->GetVehicleOfClass(vehicle_class);
    DCHECK_NE(vehicle, -1);
    return GetSpanCostCoefficientForVehicle(vehicle);
  }
#endif  // SWIG
#ifndef SWIG
  const std::vector<int64_t>& vehicle_span_cost_coefficients() const {
    return vehicle_span_cost_coefficients_;
  }
#endif  // SWIG
#ifndef SWIG
  const std::vector<int64_t>& vehicle_slack_cost_coefficients() const {
    return vehicle_slack_cost_coefficients_;
  }
#endif  // SWIG
  int64_t GetSlackCostCoefficientForVehicle(int vehicle) const {
    return vehicle_slack_cost_coefficients_[vehicle];
  }
#ifndef SWIG
  int64_t GetSlackCostCoefficientForVehicleClass(
      RoutingVehicleClassIndex vehicle_class) const {
    const int vehicle = model_->GetVehicleOfClass(vehicle_class);
    DCHECK_NE(vehicle, -1);
    return GetSlackCostCoefficientForVehicle(vehicle);
  }
#endif  // SWIG
  int64_t global_span_cost_coefficient() const {
    return global_span_cost_coefficient_;
  }
 
  int64_t GetGlobalOptimizerOffset() const {
    DCHECK_GE(global_optimizer_offset_, 0);
    return global_optimizer_offset_;
  }
  int64_t GetLocalOptimizerOffsetForVehicle(int vehicle) const {
    if (vehicle >= local_optimizer_offset_for_vehicle_.size()) {
      return 0;
    }
    DCHECK_GE(local_optimizer_offset_for_vehicle_[vehicle], 0);
    return local_optimizer_offset_for_vehicle_[vehicle];
  }

  void SetSoftSpanUpperBoundForVehicle(BoundCost bound_cost, int vehicle) {
    if (!HasSoftSpanUpperBounds()) {
      vehicle_soft_span_upper_bound_ = std::make_unique<SimpleBoundCosts>(
          model_->vehicles(), BoundCost{kint64max, 0});
    }
    vehicle_soft_span_upper_bound_->bound_cost(vehicle) = bound_cost;
  }
  bool HasSoftSpanUpperBounds() const {
    return vehicle_soft_span_upper_bound_ != nullptr;
  }
  BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const {
    DCHECK(HasSoftSpanUpperBounds());
    return vehicle_soft_span_upper_bound_->bound_cost(vehicle);
  }
  void SetQuadraticCostSoftSpanUpperBoundForVehicle(BoundCost bound_cost,
                                                    int vehicle) {
    if (!HasQuadraticCostSoftSpanUpperBounds()) {
      vehicle_quadratic_cost_soft_span_upper_bound_ =
          std::make_unique<SimpleBoundCosts>(model_->vehicles(),
                                             BoundCost{kint64max, 0});
    }
    vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle) =
        bound_cost;
  }
  bool HasQuadraticCostSoftSpanUpperBounds() const {
    return vehicle_quadratic_cost_soft_span_upper_bound_ != nullptr;
  }
  BoundCost GetQuadraticCostSoftSpanUpperBoundForVehicle(int vehicle) const {
    DCHECK(HasQuadraticCostSoftSpanUpperBounds());
    return vehicle_quadratic_cost_soft_span_upper_bound_->bound_cost(vehicle);
  }
 
 private:
  struct SoftBound {
    operations_research::IntVar* var;
    int64_t bound;
    int64_t coefficient;
  };
 
  struct PiecewiseLinearCost {
    PiecewiseLinearCost() : var(nullptr), cost(nullptr) {}
    operations_research::IntVar* var;
    std::unique_ptr<PiecewiseLinearFunction> cost;
  };
 
  class SelfBased {};
  RoutingDimension(RoutingModel* model, std::vector<int64_t> vehicle_capacities,
                   const std::string& name,
                   const RoutingDimension* base_dimension);
  RoutingDimension(RoutingModel* model, std::vector<int64_t> vehicle_capacities,
                   const std::string& name, SelfBased);
  void Initialize(absl::Span<const int> transit_evaluators,
                  absl::Span<const int> cumul_dependent_transit_evaluators,
                  absl::Span<const int> state_dependent_transit_evaluators,
                  int64_t slack_max);
  void InitializeCumuls();
  void InitializeTransits(
      absl::Span<const int> transit_evaluators,
      absl::Span<const int> cumul_dependent_transit_evaluators,
      absl::Span<const int> state_dependent_transit_evaluators,
      int64_t slack_max);
  void InitializeTransitVariables(int64_t slack_max);
  void SetupCumulVarSoftUpperBoundCosts(
      std::vector<operations_research::IntVar*>* cost_elements) const;
  void SetupCumulVarSoftLowerBoundCosts(
      std::vector<operations_research::IntVar*>* cost_elements) const;
  void SetupCumulVarPiecewiseLinearCosts(
      std::vector<operations_research::IntVar*>* cost_elements) const;
  void SetupGlobalSpanCost(
      std::vector<operations_research::IntVar*>* cost_elements) const;
  void SetupSlackAndDependentTransitCosts() const;
  void CloseModel(bool use_light_propagation);
 
  void SetOffsetForGlobalOptimizer(int64_t offset) {
    global_optimizer_offset_ = std::max(Zero(), offset);
  }
  void SetVehicleOffsetsForLocalOptimizer(std::vector<int64_t> offsets) {
    std::transform(offsets.begin(), offsets.end(), offsets.begin(),
                   [](int64_t offset) { return std::max(Zero(), offset); });
    local_optimizer_offset_for_vehicle_ = std::move(offsets);
  }
 
  std::vector<operations_research::IntVar*> cumuls_;
  std::vector<SortedDisjointIntervalList> forbidden_intervals_;
  std::vector<operations_research::IntVar*> capacity_vars_;
  const std::vector<int64_t> vehicle_capacities_;
  std::vector<operations_research::IntVar*> transits_;
  std::vector<operations_research::IntVar*> fixed_transits_;
  std::vector<int> class_evaluators_;
  std::vector<int> vehicle_to_class_;

  std::vector<int> cumul_dependent_class_evaluators_;
  std::vector<int> vehicle_to_cumul_dependent_class_;
#ifndef SWIG
  ReverseArcListGraph<int, int> path_precedence_graph_;
#endif
  // For every {first_node, second_node, offset} element in node_precedences_,
  // if both first_node and second_node are performed, then
  // cumuls_[second_node] must be greater than (or equal to)
  // cumuls_[first_node] + offset.
  std::vector<NodePrecedence> node_precedences_;
 
  // The transits of a dimension may depend on its cumuls or the cumuls of
  // another dimension. There can be no cycles, except for self loops, a
  // typical example for this is a time dimension.
  const RoutingDimension* const base_dimension_;
  // Values in state_dependent_class_evaluators_ correspond to the evaluators
  // in RoutingModel::state_dependent_transit_evaluators_ for each vehicle
  // class.
  std::vector<int> state_dependent_class_evaluators_;
  std::vector<int> state_dependent_vehicle_to_class_;
 
  // For each pickup/delivery pair_index for which limits have been set,
  // pickup_to_delivery_limits_per_pair_index_[pair_index] contains the
  // PickupToDeliveryLimitFunction for the pickup and deliveries in this pair.
  std::vector<PickupToDeliveryLimitFunction>
      pickup_to_delivery_limits_per_pair_index_;
 
  // Used if some vehicle has breaks in this dimension, typically time.
  bool break_constraints_are_initialized_ = false;
  // clang-format off
  std::vector<std::vector<IntervalVar*> > vehicle_break_intervals_;
  std::vector<std::vector<std::pair<int64_t, int64_t> > >
      vehicle_break_distance_duration_;
  // clang-format on
  // For each vehicle, stores the part of travel that is made directly
  // after (before) the departure (arrival) node of the travel.
  // These parts of the travel are non-interruptible, in particular by a break.
  std::vector<int> vehicle_pre_travel_evaluators_;
  std::vector<int> vehicle_post_travel_evaluators_;
 
  std::vector<operations_research::IntVar*> slacks_;
  std::vector<operations_research::IntVar*> dependent_transits_;
  std::vector<int64_t> vehicle_span_upper_bounds_;
  int64_t global_span_cost_coefficient_;
  std::vector<int64_t> vehicle_span_cost_coefficients_;
  std::vector<int64_t> vehicle_slack_cost_coefficients_;
  std::vector<SoftBound> cumul_var_soft_upper_bound_;
  std::vector<SoftBound> cumul_var_soft_lower_bound_;
  std::vector<PiecewiseLinearCost> cumul_var_piecewise_linear_cost_;
  RoutingModel* const model_;
  const operations_research::RoutingDimensionIndex index_;
  const std::string name_;
  int64_t global_optimizer_offset_;
  std::vector<int64_t> local_optimizer_offset_for_vehicle_;
  std::unique_ptr<SimpleBoundCosts> vehicle_soft_span_upper_bound_;
  std::unique_ptr<SimpleBoundCosts>
      vehicle_quadratic_cost_soft_span_upper_bound_;
  friend class RoutingModel;
  friend class RoutingModelInspector;
};

bool SolveModelWithSat(RoutingModel* model, RoutingSearchStats* search_stats,
                       const RoutingSearchParameters& search_parameters,
                       const operations_research::Assignment* initial_solution,
                       operations_research::Assignment* solution);
 
}  // namespace operations_research
#endif  // ORTOOLS_CONSTRAINT_SOLVER_ROUTING_H_