routing_search.h

Go to the documentation of this file.

// Copyright 2010-2024 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 OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_
 
#include <sys/types.h>
 
#include <algorithm>
#include <cstdint>
#include <deque>
#include <functional>
#include <initializer_list>
#include <limits>
#include <map>
#include <memory>
#include <optional>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "absl/container/flat_hash_map.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/types/span.h"
#include "ortools/base/adjustable_priority_queue.h"
#include "ortools/constraint_solver/constraint_solver.h"
#include "ortools/constraint_solver/constraint_solveri.h"
#include "ortools/constraint_solver/routing.h"
#include "ortools/constraint_solver/routing_enums.pb.h"
#include "ortools/constraint_solver/routing_parameters.pb.h"
#include "ortools/constraint_solver/routing_types.h"
#include "ortools/constraint_solver/routing_utils.h"
 
namespace operations_research {
 
class IntVarFilteredHeuristic;
#ifndef SWIG
class VehicleTypeCurator {
 public:
  explicit VehicleTypeCurator(
      const RoutingModel::VehicleTypeContainer& vehicle_type_container)
      : vehicle_type_container_(&vehicle_type_container) {}
 
  int NumTypes() const { return vehicle_type_container_->NumTypes(); }
 
  int Type(int vehicle) const { return vehicle_type_container_->Type(vehicle); }
 
  void Reset(const std::function<bool(int)>& store_vehicle);
 
  void Update(const std::function<bool(int)>& remove_vehicle);
 
  int GetLowestFixedCostVehicleOfType(int type) const {
    DCHECK_LT(type, NumTypes());
    const std::set<VehicleClassEntry>& vehicle_classes =
        sorted_vehicle_classes_per_type_[type];
    if (vehicle_classes.empty()) {
      return -1;
    }
    const int vehicle_class = (vehicle_classes.begin())->vehicle_class;
    DCHECK(!vehicles_per_vehicle_class_[vehicle_class].empty());
    return vehicles_per_vehicle_class_[vehicle_class][0];
  }
 
  void ReinjectVehicleOfClass(int vehicle, int vehicle_class,
                              int64_t fixed_cost) {
    std::vector<int>& vehicles = vehicles_per_vehicle_class_[vehicle_class];
    if (vehicles.empty()) {
      std::set<VehicleClassEntry>& vehicle_classes =
          sorted_vehicle_classes_per_type_[Type(vehicle)];
      const auto& insertion =
          vehicle_classes.insert({vehicle_class, fixed_cost});
      DCHECK(insertion.second);
    }
    vehicles.push_back(vehicle);
  }
 
  bool HasCompatibleVehicleOfType(
      int type, const std::function<bool(int)>& vehicle_is_compatible) const;
  std::pair<int, int> GetCompatibleVehicleOfType(
      int type, const std::function<bool(int)>& vehicle_is_compatible,
      const std::function<bool(int)>& stop_and_return_vehicle);
 
 private:
  using VehicleClassEntry =
      RoutingModel::VehicleTypeContainer::VehicleClassEntry;
  const RoutingModel::VehicleTypeContainer* const vehicle_type_container_;
  // clang-format off
  std::vector<std::set<VehicleClassEntry> > sorted_vehicle_classes_per_type_;
  std::vector<std::vector<int> > vehicles_per_vehicle_class_;
  // clang-format on
};
 
operations_research::FirstSolutionStrategy::Value
AutomaticFirstSolutionStrategy(bool has_pickup_deliveries,
                               bool has_node_precedences,
                               bool has_single_vehicle_node);
 
std::vector<int64_t> ComputeVehicleEndChainStarts(const RoutingModel& model);
 
 
// TODO(user): Eventually move this to the core CP solver library
class IntVarFilteredDecisionBuilder : public DecisionBuilder {
 public:
  explicit IntVarFilteredDecisionBuilder(
      std::unique_ptr<IntVarFilteredHeuristic> heuristic);
 
  ~IntVarFilteredDecisionBuilder() override {}
 
  Decision* Next(Solver* solver) override;
 
  std::string DebugString() const override;
 
  int64_t number_of_decisions() const;
  int64_t number_of_rejects() const;
 
 private:
  const std::unique_ptr<IntVarFilteredHeuristic> heuristic_;
};
 
class IntVarFilteredHeuristic {
 public:
  IntVarFilteredHeuristic(Solver* solver, const std::vector<IntVar*>& vars,
                          const std::vector<IntVar*>& secondary_vars,
                          LocalSearchFilterManager* filter_manager);
 
  virtual ~IntVarFilteredHeuristic() {}
 
  Assignment* BuildSolution();
 
  int64_t number_of_decisions() const { return number_of_decisions_; }
  int64_t number_of_rejects() const { return number_of_rejects_; }
 
  virtual std::string DebugString() const { return "IntVarFilteredHeuristic"; }
 
 protected:
  void ResetSolution();
  virtual void Initialize() {}
  virtual bool InitializeSolution() { return true; }
  virtual bool BuildSolutionInternal() = 0;
  std::optional<int64_t> Evaluate(bool commit);
  virtual bool StopSearch() { return false; }
  void SetValue(int64_t index, int64_t value) {
    DCHECK_LT(index, is_in_delta_.size());
    if (!is_in_delta_[index]) {
      delta_->FastAdd(vars_[index])->SetValue(value);
      delta_indices_.push_back(index);
      is_in_delta_[index] = true;
    } else {
      delta_->SetValue(vars_[index], value);
    }
  }
  const std::vector<int>& delta_indices() const { return delta_indices_; }
  int64_t Value(int64_t index) const {
    return assignment_->IntVarContainer().Element(index).Value();
  }
  bool Contains(int64_t index) const {
    return assignment_->IntVarContainer().Element(index).Var() != nullptr;
  }
  IntVar* Var(int64_t index) const { return vars_[index]; }
  int64_t SecondaryVarIndex(int64_t index) const {
    DCHECK(HasSecondaryVars());
    return index + base_vars_size_;
  }
  bool HasSecondaryVars() const { return base_vars_size_ != vars_.size(); }
  bool IsSecondaryVar(int64_t index) const { return index >= base_vars_size_; }
  void SynchronizeFilters();
 
  Assignment* const assignment_;
 
 private:
  bool FilterAccept();
 
  Solver* solver_;
  std::vector<IntVar*> vars_;
  const int base_vars_size_;
  Assignment* const delta_;
  std::vector<int> delta_indices_;
  std::vector<bool> is_in_delta_;
  Assignment* const empty_;
  LocalSearchFilterManager* filter_manager_;
  int64_t objective_upper_bound_;
  int64_t number_of_decisions_;
  int64_t number_of_rejects_;
};
 
class RoutingFilteredHeuristic : public IntVarFilteredHeuristic {
 public:
  RoutingFilteredHeuristic(RoutingModel* model,
                           std::function<bool()> stop_search,
                           LocalSearchFilterManager* filter_manager);
  ~RoutingFilteredHeuristic() override {}
  Assignment* BuildSolutionFromRoutes(
      const std::function<int64_t(int64_t)>& next_accessor);
  RoutingModel* model() const { return model_; }
  int GetStartChainEnd(int vehicle) const { return start_chain_ends_[vehicle]; }
  int GetEndChainStart(int vehicle) const { return end_chain_starts_[vehicle]; }
  void MakeDisjunctionNodesUnperformed(int64_t node);
  bool MakeUnassignedNodesUnperformed();
  void MakePartiallyPerformedPairsUnperformed();
 
 protected:
  bool StopSearch() override { return stop_search_(); }
  virtual void SetVehicleIndex(int64_t /*node*/, int /*vehicle*/) {}
  virtual void ResetVehicleIndices() {}
  bool VehicleIsEmpty(int vehicle) const {
    return Value(model()->Start(vehicle)) == model()->End(vehicle);
  }
  void SetNext(int64_t node, int64_t next, int vehicle) {
    SetValue(node, next);
    if (HasSecondaryVars()) SetValue(SecondaryVarIndex(node), vehicle);
  }
 
 private:
  bool InitializeSolution() override;
 
  RoutingModel* const model_;
  std::function<bool()> stop_search_;
  std::vector<int64_t> start_chain_ends_;
  std::vector<int64_t> end_chain_starts_;
};
 
class CheapestInsertionFilteredHeuristic : public RoutingFilteredHeuristic {
 public:
  CheapestInsertionFilteredHeuristic(
      RoutingModel* model, std::function<bool()> stop_search,
      std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
      std::function<int64_t(int64_t)> penalty_evaluator,
      LocalSearchFilterManager* filter_manager);
  ~CheapestInsertionFilteredHeuristic() override {}
 
 protected:
  struct NodeInsertion {
    int64_t insert_after;
    int vehicle;
    int64_t value;
 
    bool operator<(const NodeInsertion& other) const {
      return std::tie(value, insert_after, vehicle) <
             std::tie(other.value, other.insert_after, other.vehicle);
    }
  };
  struct StartEndValue {
    int64_t distance;
    int vehicle;
 
    bool operator<(const StartEndValue& other) const {
      return std::tie(distance, vehicle) <
             std::tie(other.distance, other.vehicle);
    }
  };
  struct Seed {
    uint64_t num_allowed_vehicles;
    int64_t neg_penalty;
    StartEndValue start_end_value;
    bool is_node_index = true;
    int index;
 
    bool operator>(const Seed& other) const {
      return std::tie(num_allowed_vehicles, neg_penalty, start_end_value,
                      is_node_index, index) >
             std::tie(other.num_allowed_vehicles, other.neg_penalty,
                      other.start_end_value, other.is_node_index, other.index);
    }
  };
  // clang-format off
  struct SeedQueue {
    explicit SeedQueue(bool prioritize_farthest_nodes) :
      prioritize_farthest_nodes(prioritize_farthest_nodes) {}
 
    std::priority_queue<Seed, std::vector<Seed>, std::greater<Seed> >
        priority_queue;
    const bool prioritize_farthest_nodes;
  };
 
  std::vector<std::vector<StartEndValue> >
      ComputeStartEndDistanceForVehicles(const std::vector<int>& vehicles);
 
  void InitializeSeedQueue(
      std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
      SeedQueue* sq);
  // clang-format on
 
  void AddSeedNodeToQueue(int node,
                          std::vector<StartEndValue>* start_end_distances,
                          SeedQueue* sq);
 
  void InsertBetween(int64_t node, int64_t predecessor, int64_t successor,
                     int vehicle = -1);
  void AppendInsertionPositionsAfter(
      int64_t node_to_insert, int64_t start, int64_t next_after_start,
      int vehicle, bool ignore_cost,
      std::vector<NodeInsertion>* node_insertions);
  // TODO(user): Replace 'insert_before' and 'insert_after' by 'predecessor'
  // and 'successor' in the code.
  int64_t GetInsertionCostForNodeAtPosition(int64_t node_to_insert,
                                            int64_t insert_after,
                                            int64_t insert_before,
                                            int vehicle) const;
  int64_t GetUnperformedValue(int64_t node_to_insert) const;
 
  std::function<int64_t(int64_t, int64_t, int64_t)> evaluator_;
  std::function<int64_t(int64_t)> penalty_evaluator_;
};
 
class GlobalCheapestInsertionFilteredHeuristic
    : public CheapestInsertionFilteredHeuristic {
 public:
  struct GlobalCheapestInsertionParameters {
    bool is_sequential;
    double farthest_seeds_ratio;
    double neighbors_ratio;
    int64_t min_neighbors;
    bool use_neighbors_ratio_for_initialization;
    bool add_unperformed_entries;
  };
 
  GlobalCheapestInsertionFilteredHeuristic(
      RoutingModel* model, std::function<bool()> stop_search,
      std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
      std::function<int64_t(int64_t)> penalty_evaluator,
      LocalSearchFilterManager* filter_manager,
      GlobalCheapestInsertionParameters parameters);
  ~GlobalCheapestInsertionFilteredHeuristic() override {}
  bool BuildSolutionInternal() override;
  std::string DebugString() const override {
    return "GlobalCheapestInsertionFilteredHeuristic";
  }
 
 private:
  class NodeEntryQueue;
 
  class PairEntry {
   public:
    PairEntry(int pickup_to_insert, int pickup_insert_after,
              int delivery_to_insert, int delivery_insert_after, int vehicle,
              int64_t bucket)
        : value_(std::numeric_limits<int64_t>::max()),
          heap_index_(-1),
          pickup_to_insert_(pickup_to_insert),
          pickup_insert_after_(pickup_insert_after),
          delivery_to_insert_(delivery_to_insert),
          delivery_insert_after_(delivery_insert_after),
          vehicle_(vehicle),
          bucket_(bucket) {}
    // Note: for compatibility reasons, comparator follows tie-breaking rules
    // used in the first version of GlobalCheapestInsertion.
    bool operator<(const PairEntry& other) const {
      // We give higher priority to insertions from lower buckets.
      if (bucket_ != other.bucket_) {
        return bucket_ > other.bucket_;
      }
      // We then compare by value, then we favor insertions (vehicle != -1).
      // The rest of the tie-breaking is done with std::tie.
      if (value_ != other.value_) {
        return value_ > other.value_;
      }
      if ((vehicle_ == -1) ^ (other.vehicle_ == -1)) {
        return vehicle_ == -1;
      }
      return std::tie(pickup_insert_after_, pickup_to_insert_,
                      delivery_insert_after_, delivery_to_insert_, vehicle_) >
             std::tie(other.pickup_insert_after_, other.pickup_to_insert_,
                      other.delivery_insert_after_, other.delivery_to_insert_,
                      other.vehicle_);
    }
    void SetHeapIndex(int h) { heap_index_ = h; }
    int GetHeapIndex() const { return heap_index_; }
    void set_value(int64_t value) { value_ = value; }
    int pickup_to_insert() const { return pickup_to_insert_; }
    int pickup_insert_after() const { return pickup_insert_after_; }
    void set_pickup_insert_after(int pickup_insert_after) {
      pickup_insert_after_ = pickup_insert_after;
    }
    int delivery_to_insert() const { return delivery_to_insert_; }
    int delivery_insert_after() const { return delivery_insert_after_; }
    int vehicle() const { return vehicle_; }
    void set_vehicle(int vehicle) { vehicle_ = vehicle; }
 
   private:
    int64_t value_;
    int heap_index_;
    int pickup_to_insert_;
    int pickup_insert_after_;
    int delivery_to_insert_;
    int delivery_insert_after_;
    int vehicle_;
    int64_t bucket_;
  };
 
  typedef absl::flat_hash_set<PairEntry*> PairEntries;
 
  template <typename T>
  class EntryAllocator {
   public:
    EntryAllocator() {}
    void Clear() {
      entries_.clear();
      free_entries_.clear();
    }
    template <typename... Args>
    T* NewEntry(const Args&... args) {
      if (!free_entries_.empty()) {
        auto* entry = free_entries_.back();
        free_entries_.pop_back();
        *entry = T(args...);
        return entry;
      } else {
        entries_.emplace_back(args...);
        return &entries_.back();
      }
    }
    void FreeEntry(T* entry) { free_entries_.push_back(entry); }
 
   private:
    std::deque<T> entries_;
    std::vector<T*> free_entries_;
  };
 
  bool InsertPairsAndNodesByRequirementTopologicalOrder();
 
  bool InsertPairs(
      const std::map<int64_t, std::vector<int>>& pair_indices_by_bucket);
 
  bool UseEmptyVehicleTypeCuratorForVehicle(int vehicle,
                                            bool all_vehicles = true) {
    return vehicle >= 0 && VehicleIsEmpty(vehicle) && all_vehicles;
  }
 
  bool InsertPairEntryUsingEmptyVehicleTypeCurator(
      const absl::flat_hash_set<int>& pair_indices, PairEntry* pair_entry,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
 
  bool InsertNodesOnRoutes(
      const std::map<int64_t, std::vector<int>>& nodes_by_bucket,
      const absl::flat_hash_set<int>& vehicles);
 
  bool InsertNodeEntryUsingEmptyVehicleTypeCurator(
      const std::vector<bool>& nodes, bool all_vehicles, NodeEntryQueue* queue);
 
  bool SequentialInsertNodes(
      const std::map<int64_t, std::vector<int>>& nodes_by_bucket);
 
  void DetectUsedVehicles(std::vector<bool>* is_vehicle_used,
                          std::vector<int>* unused_vehicles,
                          absl::flat_hash_set<int>* used_vehicles);
 
  bool IsCheapestClassRepresentative(int vehicle) const;
 
  void InsertFarthestNodesAsSeeds();
 
  int InsertSeedNode(
      std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
      SeedQueue* sq, std::vector<bool>* is_vehicle_used);
  // clang-format on
 
  bool InitializePairPositions(
      const absl::flat_hash_set<int>& pair_indices,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  void InitializeInsertionEntriesPerformingPair(
      int64_t pickup, int64_t delivery,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  bool UpdateAfterPairInsertion(
      const absl::flat_hash_set<int>& pair_indices, int vehicle, int64_t pickup,
      int64_t pickup_position, int64_t delivery, int64_t delivery_position,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  bool UpdateExistingPairEntriesOnChain(
      int64_t insert_after_start, int64_t insert_after_end,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  bool AddPairEntriesAfter(const absl::flat_hash_set<int>& pair_indices,
                           int vehicle, int64_t insert_after,
                           int64_t skip_entries_inserting_delivery_after,
                           AdjustablePriorityQueue<PairEntry>* priority_queue,
                           std::vector<PairEntries>* pickup_to_entries,
                           std::vector<PairEntries>* delivery_to_entries) {
    return AddPairEntriesWithDeliveryAfter(pair_indices, vehicle, insert_after,
                                           priority_queue, pickup_to_entries,
                                           delivery_to_entries) &&
           AddPairEntriesWithPickupAfter(pair_indices, vehicle, insert_after,
                                         skip_entries_inserting_delivery_after,
                                         priority_queue, pickup_to_entries,
                                         delivery_to_entries);
  }
  bool AddPairEntriesWithPickupAfter(
      const absl::flat_hash_set<int>& pair_indices, int vehicle,
      int64_t insert_after, int64_t skip_entries_inserting_delivery_after,
      AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  bool AddPairEntriesWithDeliveryAfter(
      const absl::flat_hash_set<int>& pair_indices, int vehicle,
      int64_t insert_after, AdjustablePriorityQueue<PairEntry>* priority_queue,
      std::vector<PairEntries>* pickup_to_entries,
      std::vector<PairEntries>* delivery_to_entries);
  void DeletePairEntry(PairEntry* entry,
                       AdjustablePriorityQueue<PairEntry>* priority_queue,
                       std::vector<PairEntries>* pickup_to_entries,
                       std::vector<PairEntries>* delivery_to_entries);
  void AddPairEntry(int64_t pickup, int64_t pickup_insert_after,
                    int64_t delivery, int64_t delivery_insert_after,
                    int vehicle,
                    AdjustablePriorityQueue<PairEntry>* priority_queue,
                    std::vector<PairEntries>* pickup_entries,
                    std::vector<PairEntries>* delivery_entries) const;
  void UpdatePairEntry(
      PairEntry* pair_entry,
      AdjustablePriorityQueue<PairEntry>* priority_queue) const;
  int64_t GetInsertionValueForPairAtPositions(int64_t pickup,
                                              int64_t pickup_insert_after,
                                              int64_t delivery,
                                              int64_t delivery_insert_after,
                                              int vehicle) const;
 
  bool InitializePositions(const std::vector<bool>& nodes,
                           const absl::flat_hash_set<int>& vehicles,
                           NodeEntryQueue* queue);
  void InitializeInsertionEntriesPerformingNode(
      int64_t node, const absl::flat_hash_set<int>& vehicles,
      NodeEntryQueue* queue);
  bool UpdateAfterNodeInsertion(const std::vector<bool>& nodes, int vehicle,
                                int64_t node, int64_t insert_after,
                                bool all_vehicles, NodeEntryQueue* queue);
  bool UpdateExistingNodeEntriesOnChain(const std::vector<bool>& nodes,
                                        int vehicle, int64_t insert_after_start,
                                        int64_t insert_after_end,
                                        bool all_vehicles,
                                        NodeEntryQueue* queue);
  bool AddNodeEntriesAfter(const std::vector<bool>& nodes, int vehicle,
                           int64_t insert_after, bool all_vehicles,
                           NodeEntryQueue* queue);
 
  void AddNodeEntry(int64_t node, int64_t insert_after, int vehicle,
                    bool all_vehicles, NodeEntryQueue* queue) const;
 
  void ResetVehicleIndices() override {
    node_index_to_vehicle_.assign(node_index_to_vehicle_.size(), -1);
  }
 
  void SetVehicleIndex(int64_t node, int vehicle) override {
    DCHECK_LT(node, node_index_to_vehicle_.size());
    node_index_to_vehicle_[node] = vehicle;
  }
 
  bool CheckVehicleIndices() const;
 
  int64_t GetBucketOfNode(int node) const {
    return model()->VehicleVar(node)->Size();
  }
 
  int64_t GetBucketOfPair(const PickupDeliveryPair& pair) const {
    int64_t max_pickup_bucket = 0;
    for (int64_t pickup : pair.pickup_alternatives) {
      max_pickup_bucket = std::max(max_pickup_bucket, GetBucketOfNode(pickup));
    }
    int64_t max_delivery_bucket = 0;
    for (int64_t delivery : pair.delivery_alternatives) {
      max_delivery_bucket =
          std::max(max_delivery_bucket, GetBucketOfNode(delivery));
    }
    return std::min(max_pickup_bucket, max_delivery_bucket);
  }
 
  template <typename T>
  bool StopSearchAndCleanup(AdjustablePriorityQueue<T>* priority_queue) {
    if (!StopSearch()) return false;
    if constexpr (std::is_same_v<T, PairEntry>) {
      pair_entry_allocator_.Clear();
    }
    priority_queue->Clear();
    return true;
  }
 
  GlobalCheapestInsertionParameters gci_params_;
  std::vector<int> node_index_to_vehicle_;
 
  const RoutingModel::NodeNeighborsByCostClass*
      node_index_to_neighbors_by_cost_class_;
 
  std::unique_ptr<VehicleTypeCurator> empty_vehicle_type_curator_;
 
  mutable EntryAllocator<PairEntry> pair_entry_allocator_;
};
 
// Holds sequences of insertions.
// A sequence of insertions must be in the same path, each insertion must
// take place either after the previously inserted node or further down the
// path, never before.
class InsertionSequenceContainer {
 private:
  // InsertionSequenceContainer holds all insertion sequences in the same vector
  // contiguously, each insertion sequence is defined by a pair of bounds.
  // Using Insertion* directly to delimit bounds would cause out-of-memory reads
  // when the underlying vector<Insertion> is extended and reallocated,
  // so this stores integer bounds in InsertionBounds to delimit sequences,
  // and InsertionSequenceIterator translates those bounds to
  // Insertion*-based ranges (InsertionSequence) on-the-fly when iterating over
  // all sequences.
  struct InsertionBounds {
    size_t begin;
    size_t end;
    int vehicle;
    int64_t cost;
    bool operator<(const InsertionBounds& other) const {
      return std::tie(cost, vehicle, begin) <
             std::tie(other.cost, other.vehicle, other.begin);
    }
    size_t Size() const { return end - begin; }
  };
 
 public:
  struct Insertion {
    int pred;
    int node;
    bool operator==(const Insertion& other) const {
      return pred == other.pred && node == other.node;
    }
  };
 
  // Represents an insertion sequence as passed to AddInsertionSequence.
  // This only allows to modify the cost, as a means to reorder sequences.
  class InsertionSequence {
   public:
    InsertionSequence(Insertion* data, InsertionBounds* bounds)
        : data_(data), bounds_(bounds) {}
 
    bool operator!=(const InsertionSequence& other) const {
      DCHECK_NE(data_, other.data_);
      return bounds_ != other.bounds_;
    }
 
    const Insertion* begin() const { return data_ + bounds_->begin; }
    const Insertion* end() const { return data_ + bounds_->end; }
    size_t Size() const { return bounds_->Size(); }
    int Vehicle() const { return bounds_->vehicle; }
    int64_t Cost() const { return bounds_->cost; }
    int64_t& Cost() { return bounds_->cost; }
 
   private:
    const Insertion* const data_;
    InsertionBounds* const bounds_;
  };
  class InsertionSequenceIterator {
   public:
    InsertionSequenceIterator(Insertion* data, InsertionBounds* bounds)
        : data_(data), bounds_(bounds) {}
    bool operator!=(const InsertionSequenceIterator& other) const {
      DCHECK_EQ(data_, other.data_);
      return bounds_ != other.bounds_;
    }
    InsertionSequenceIterator& operator++() {
      ++bounds_;
      return *this;
    }
    InsertionSequence operator*() const { return {data_, bounds_}; }
 
   private:
    Insertion* data_;
    InsertionBounds* bounds_;
  };
 
  // InsertionSequenceContainer is a range over insertion sequences.
  InsertionSequenceIterator begin() {
    return {insertions_.data(), insertion_bounds_.data()};
  }
  InsertionSequenceIterator end() {
    return {insertions_.data(),
            insertion_bounds_.data() + insertion_bounds_.size()};
  }
  // Returns the number of sequences of this container.
  size_t Size() const { return insertion_bounds_.size(); }
 
  // Adds an insertion sequence to the container.
  // Passing an initializer_list allows deeper optimizations by the compiler
  // for cases where the sequence has a compile-time fixed size.
  void AddInsertionSequence(
      int vehicle, std::initializer_list<Insertion> insertion_sequence) {
    insertion_bounds_.push_back(
        {.begin = insertions_.size(),
         .end = insertions_.size() + insertion_sequence.size(),
         .vehicle = vehicle,
         .cost = 0});
    insertions_.insert(insertions_.end(), insertion_sequence.begin(),
                       insertion_sequence.end());
  }
 
  // Adds an insertion sequence to the container.
  void AddInsertionSequence(int vehicle,
                            absl::Span<const Insertion> insertion_sequence) {
    insertion_bounds_.push_back(
        {.begin = insertions_.size(),
         .end = insertions_.size() + insertion_sequence.size(),
         .vehicle = vehicle,
         .cost = 0});
    insertions_.insert(insertions_.end(), insertion_sequence.begin(),
                       insertion_sequence.end());
  }
 
  // Similar to std::remove_if(), removes all sequences that match a predicate.
  // This keeps original order, and removes selected sequences.
  void RemoveIf(const std::function<bool(const InsertionSequence&)>& p) {
    size_t from = 0;
    size_t to = 0;
    for (const InsertionSequence& sequence : *this) {
      // TODO(user): Benchmark this against std::swap().
      if (!p(sequence)) insertion_bounds_[to++] = insertion_bounds_[from];
      ++from;
    }
    insertion_bounds_.resize(to);
  }
 
  // Sorts sequences according to (cost, vehicle).
  // TODO(user): benchmark this against other ways to get insertion
  // sequence in order, for instance sorting by index, separating {cost, index},
  // making a heap.
  void Sort() { std::sort(insertion_bounds_.begin(), insertion_bounds_.end()); }
 
  // Removes all sequences.
  void Clear() {
    insertions_.clear();
    insertion_bounds_.clear();
  }
 
 private:
  std::vector<Insertion> insertions_;
  std::vector<InsertionBounds> insertion_bounds_;
};
 
// Generates insertion positions respecting structural constraints.
class InsertionSequenceGenerator {
 public:
  InsertionSequenceGenerator() {}
 
  void AppendPickupDeliveryMultitourInsertions(
      int pickup, int delivery, int vehicle, const std::vector<int>& path,
      const std::vector<bool>& path_node_is_pickup,
      const std::vector<bool>& path_node_is_delivery,
      InsertionSequenceContainer& insertions);
 
 private:
  // Information[i] describes the insertion between path[i] and path[i+1].
  std::vector<int> next_decrease_;  // next position after a delivery.
  std::vector<int> next_increase_;  // next position after a pickup.
  std::vector<int> prev_decrease_;  // previous position after delivery.
  std::vector<int> prev_increase_;  // previous position after pickup.
};
 
struct PickupDeliveryInsertion {
  int64_t insert_pickup_after;
  int64_t insert_delivery_after;
  int64_t value;
  int vehicle;
 
  bool operator<(const PickupDeliveryInsertion& other) const {
    return std::tie(value, insert_pickup_after, insert_delivery_after,
                    vehicle) < std::tie(other.value, other.insert_pickup_after,
                                        other.insert_delivery_after,
                                        other.vehicle);
  }
};
 
class LocalCheapestInsertionFilteredHeuristic
    : public CheapestInsertionFilteredHeuristic {
 public:
  LocalCheapestInsertionFilteredHeuristic(
      RoutingModel* model, std::function<bool()> stop_search,
      std::function<int64_t(int64_t, int64_t, int64_t)> evaluator,
      RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy,
      LocalSearchFilterManager* filter_manager,
      BinCapacities* bin_capacities = nullptr,
      std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,
                         std::vector<RoutingModel::VariableValuePair>*)>
          optimize_on_insertion = nullptr);
  ~LocalCheapestInsertionFilteredHeuristic() override {}
  bool BuildSolutionInternal() override;
  std::string DebugString() const override {
    return "LocalCheapestInsertionFilteredHeuristic";
  }
 
 protected:
  void Initialize() override;
 
 private:
  void ComputeInsertionOrder();
  std::vector<NodeInsertion> ComputeEvaluatorSortedPositions(int64_t node);
  std::vector<NodeInsertion> ComputeEvaluatorSortedPositionsOnRouteAfter(
      int64_t node, int64_t start, int64_t next_after_start, int vehicle);
 
  std::vector<PickupDeliveryInsertion> ComputeEvaluatorSortedPairPositions(
      int pickup, int delivery);
 
  // Tries to insert any alternative of the given pair,
  // ordered by cost of pickup insertion, then by cost of delivery insertion.
  void InsertBestPickupThenDelivery(const PickupDeliveryPair& pair);
  // Tries to insert any alternative of the given pair,
  // ordered by the sum of pickup and delivery insertion.
  void InsertBestPair(const PickupDeliveryPair& pair);
  // Tries to insert any alternative of the given pair,
  // at a position that preserves the multitour property,
  // ordered by the sum of pickup and delivery insertion.
  void InsertBestPairMultitour(const PickupDeliveryPair& pair);
  // Tries to insert a pair at the given location. Returns true iff inserted.
  bool InsertPair(int64_t pickup, int64_t insert_pickup_after, int64_t delivery,
                  int64_t insert_delivery_after, int vehicle);
 
  // Runs an internal optimization. Returns true if the solution was changed.
  bool OptimizeOnInsertion(std::vector<int> delta_indices);
 
  // Returns true if bin capacities should be updated.
  // TODO(user): Allow updating bin capacities when we do internal
  // optimizations.
  bool MustUpdateBinCapacities() const {
    return bin_capacities_ != nullptr && optimize_on_insertion_ == nullptr;
  }
 
  std::vector<Seed> insertion_order_;
  const RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy_;
  InsertionSequenceContainer insertion_container_;
  InsertionSequenceGenerator insertion_generator_;
 
  BinCapacities* const bin_capacities_;
 
  std::function<bool(const std::vector<RoutingModel::VariableValuePair>&,
                     std::vector<RoutingModel::VariableValuePair>*)>
      optimize_on_insertion_;
  bool synchronize_insertion_optimizer_ = true;
};
 
class CheapestAdditionFilteredHeuristic : public RoutingFilteredHeuristic {
 public:
  CheapestAdditionFilteredHeuristic(RoutingModel* model,
                                    std::function<bool()> stop_search,
                                    LocalSearchFilterManager* filter_manager);
  ~CheapestAdditionFilteredHeuristic() override {}
  bool BuildSolutionInternal() override;
 
 private:
  class PartialRoutesAndLargeVehicleIndicesFirst {
   public:
    explicit PartialRoutesAndLargeVehicleIndicesFirst(
        const CheapestAdditionFilteredHeuristic& builder)
        : builder_(builder) {}
    bool operator()(int vehicle1, int vehicle2) const;
 
   private:
    const CheapestAdditionFilteredHeuristic& builder_;
  };
  template <typename Iterator>
  std::vector<int64_t> GetPossibleNextsFromIterator(int64_t node,
                                                    Iterator start,
                                                    Iterator end) const {
    const int size = model()->Size();
    std::vector<int64_t> nexts;
    for (Iterator it = start; it != end; ++it) {
      const int64_t next = *it;
      if (next != node && (next >= size || !Contains(next))) {
        nexts.push_back(next);
      }
    }
    return nexts;
  }
  virtual void SortSuccessors(int64_t node,
                              std::vector<int64_t>* successors) = 0;
  virtual int64_t FindTopSuccessor(int64_t node,
                                   const std::vector<int64_t>& successors) = 0;
};
 
class EvaluatorCheapestAdditionFilteredHeuristic
    : public CheapestAdditionFilteredHeuristic {
 public:
  EvaluatorCheapestAdditionFilteredHeuristic(
      RoutingModel* model, std::function<bool()> stop_search,
      std::function<int64_t(int64_t, int64_t)> evaluator,
      LocalSearchFilterManager* filter_manager);
  ~EvaluatorCheapestAdditionFilteredHeuristic() override {}
  std::string DebugString() const override {
    return "EvaluatorCheapestAdditionFilteredHeuristic";
  }
 
 private:
  void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override;
  int64_t FindTopSuccessor(int64_t node,
                           const std::vector<int64_t>& successors) override;
 
  std::function<int64_t(int64_t, int64_t)> evaluator_;
};
 
class ComparatorCheapestAdditionFilteredHeuristic
    : public CheapestAdditionFilteredHeuristic {
 public:
  ComparatorCheapestAdditionFilteredHeuristic(
      RoutingModel* model, std::function<bool()> stop_search,
      Solver::VariableValueComparator comparator,
      LocalSearchFilterManager* filter_manager);
  ~ComparatorCheapestAdditionFilteredHeuristic() override {}
  std::string DebugString() const override {
    return "ComparatorCheapestAdditionFilteredHeuristic";
  }
 
 private:
  void SortSuccessors(int64_t node, std::vector<int64_t>* successors) override;
  int64_t FindTopSuccessor(int64_t node,
                           const std::vector<int64_t>& successors) override;
 
  Solver::VariableValueComparator comparator_;
};
 
class SavingsFilteredHeuristic : public RoutingFilteredHeuristic {
 public:
  struct SavingsParameters {
    double neighbors_ratio = 1.0;
    double max_memory_usage_bytes = 6e9;
    bool add_reverse_arcs = false;
    double arc_coefficient = 1.0;
  };
 
  SavingsFilteredHeuristic(RoutingModel* model,
                           std::function<bool()> stop_search,
                           SavingsParameters parameters,
                           LocalSearchFilterManager* filter_manager);
  ~SavingsFilteredHeuristic() override;
  bool BuildSolutionInternal() override;
 
 protected:
  struct Saving {
    int64_t saving;
    unsigned int vehicle_type : 20;
    unsigned int before_node : 22;
    unsigned int after_node : 22;
    bool operator<(const Saving& other) const {
      return std::tie(saving, vehicle_type, before_node, after_node) <
             std::tie(other.saving, other.vehicle_type, other.before_node,
                      other.after_node);
    }
  };
 
  template <typename S>
  class SavingsContainer;
 
  virtual double ExtraSavingsMemoryMultiplicativeFactor() const = 0;
 
  virtual void BuildRoutesFromSavings() = 0;
 
  int StartNewRouteWithBestVehicleOfType(int type, int64_t before_node,
                                         int64_t after_node);
 
  // clang-format off
  std::unique_ptr<SavingsContainer<Saving> > savings_container_;
  // clang-format on
  std::unique_ptr<VehicleTypeCurator> vehicle_type_curator_;
 
 private:
  // clang-format off
  void AddSymmetricArcsToAdjacencyLists(
      std::vector<std::vector<int64_t> >* adjacency_lists);
  // clang-format on
 
  bool ComputeSavings();
  Saving BuildSaving(int64_t saving, int vehicle_type, int before_node,
                     int after_node) const {
    return {saving, static_cast<unsigned int>(vehicle_type),
            static_cast<unsigned int>(before_node),
            static_cast<unsigned int>(after_node)};
  }
 
  int64_t MaxNumNeighborsPerNode(int num_vehicle_types) const;
 
  const SavingsParameters savings_params_;
 
  friend class SavingsFilteredHeuristicTestPeer;
};
 
class SequentialSavingsFilteredHeuristic : public SavingsFilteredHeuristic {
 public:
  SequentialSavingsFilteredHeuristic(RoutingModel* model,
                                     std::function<bool()> stop_search,
                                     SavingsParameters parameters,
                                     LocalSearchFilterManager* filter_manager)
      : SavingsFilteredHeuristic(model, std::move(stop_search), parameters,
                                 filter_manager) {}
  ~SequentialSavingsFilteredHeuristic() override {}
  std::string DebugString() const override {
    return "SequentialSavingsFilteredHeuristic";
  }
 
 private:
  void BuildRoutesFromSavings() override;
  double ExtraSavingsMemoryMultiplicativeFactor() const override { return 1.0; }
};
 
class ParallelSavingsFilteredHeuristic : public SavingsFilteredHeuristic {
 public:
  ParallelSavingsFilteredHeuristic(RoutingModel* model,
                                   std::function<bool()> stop_search,
                                   SavingsParameters parameters,
                                   LocalSearchFilterManager* filter_manager)
      : SavingsFilteredHeuristic(model, std::move(stop_search), parameters,
                                 filter_manager) {}
  ~ParallelSavingsFilteredHeuristic() override {}
  std::string DebugString() const override {
    return "ParallelSavingsFilteredHeuristic";
  }
 
 private:
  void BuildRoutesFromSavings() override;
 
  double ExtraSavingsMemoryMultiplicativeFactor() const override { return 2.0; }
 
  void MergeRoutes(int first_vehicle, int second_vehicle, int64_t before_node,
                   int64_t after_node);
 
  std::vector<int64_t> first_node_on_route_;
  std::vector<int64_t> last_node_on_route_;
  std::vector<int> vehicle_of_first_or_last_node_;
};
 
 
class ChristofidesFilteredHeuristic : public RoutingFilteredHeuristic {
 public:
  ChristofidesFilteredHeuristic(RoutingModel* model,
                                std::function<bool()> stop_search,
                                LocalSearchFilterManager* filter_manager,
                                bool use_minimum_matching);
  ~ChristofidesFilteredHeuristic() override {}
  bool BuildSolutionInternal() override;
  std::string DebugString() const override {
    return "ChristofidesFilteredHeuristic";
  }
 
 private:
  const bool use_minimum_matching_;
};
 
class SweepArranger {
 public:
  explicit SweepArranger(
      const std::vector<std::pair<int64_t, int64_t>>& points);
 
  // This type is neither copyable nor movable.
  SweepArranger(const SweepArranger&) = delete;
  SweepArranger& operator=(const SweepArranger&) = delete;
 
  virtual ~SweepArranger() {}
  void ArrangeIndices(std::vector<int64_t>* indices);
  void SetSectors(int sectors) { sectors_ = sectors; }
 
 private:
  std::vector<int> coordinates_;
  int sectors_;
};
#endif  // SWIG
 
// Returns a DecisionBuilder building a first solution based on the Sweep
// heuristic. Mostly suitable when cost is proportional to distance.
DecisionBuilder* MakeSweepDecisionBuilder(RoutingModel* model,
                                          bool check_assignment);
 
// Returns a DecisionBuilder making all nodes unperformed.
DecisionBuilder* MakeAllUnperformed(RoutingModel* model);
 
}  // namespace operations_research
 
#endif  // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_SEARCH_H_