routing_search.h

Go to the documentation of this file.

// Copyright 2010-2022 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 <deque>
#include <functional>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <optional>
#include <set>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>
 
#include "absl/container/flat_hash_set.h"
#include "ortools/base/adjustable_priority_queue.h"
#include "ortools/base/integral_types.h"
#include "ortools/base/logging.h"
#include "ortools/base/macros.h"
#include "ortools/base/mathutil.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_index_manager.h"
#include "ortools/util/bitset.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() = default;
 
  Assignment* const 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) {
    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);
    }
  }
  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;
  }
  int Size() const { return vars_.size(); }
  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,
                           bool omit_secondary_vars = true);
  ~RoutingFilteredHeuristic() override = default;
  const 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);
  }
 
 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 = default;
 
 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 num_allowed_vehicles;
    int64_t distance;
    int vehicle;
 
    bool operator<(const StartEndValue& other) const {
      return std::tie(num_allowed_vehicles, distance, vehicle) <
             std::tie(other.num_allowed_vehicles, other.distance,
                      other.vehicle);
    }
  };
  typedef std::pair<StartEndValue, /*seed_node*/ int> Seed;
 
  // clang-format off
  std::vector<std::vector<StartEndValue> >
      ComputeStartEndDistanceForVehicles(const std::vector<int>& vehicles);
 
  template <class Queue>
  void InitializePriorityQueue(
      std::vector<std::vector<StartEndValue> >* start_end_distances_per_node,
      Queue* priority_queue);
  // clang-format on
 
  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 = default;
  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* const 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);
 
  void InsertFarthestNodesAsSeeds();
 
  template <class Queue>
  int InsertSeedNode(
      std::vector<std::vector<StartEndValue>>* start_end_distances_per_node,
      Queue* priority_queue, 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* const 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;
 
  int64_t NumNonStartEndNodes() const {
    return model()->Size() - model()->vehicles();
  }
 
  int64_t NumNeighbors() const {
    return std::max(gci_params_.min_neighbors,
                    MathUtil::FastInt64Round(gci_params_.neighbors_ratio *
                                             NumNonStartEndNodes()));
  }
 
  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 RoutingModel::IndexPair& index_pair) const {
    int64_t max_pickup_bucket = 0;
    for (int64_t pickup : index_pair.first) {
      max_pickup_bucket = std::max(max_pickup_bucket, GetBucketOfNode(pickup));
    }
    int64_t max_delivery_bucket = 0;
    for (int64_t delivery : index_pair.second) {
      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_;
};
 
// Generates insertion positions respecting structural constraints.
class InsertionGenerator {
 public:
  InsertionGenerator() = default;
 
  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);
    }
  };
  void AppendPickupDeliveryMultitourInsertions(
      int pickup, const std::vector<int>& path,
      const std::vector<bool>& node_is_pickup,
      const std::vector<bool>& node_is_delivery,
      std::vector<PickupDeliveryInsertion>& 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.
};
 
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);
  ~LocalCheapestInsertionFilteredHeuristic() override = default;
  bool BuildSolutionInternal() override;
  std::string DebugString() const override {
    return "LocalCheapestInsertionFilteredHeuristic";
  }
 
 protected:
  void Initialize() override;
 
 private:
  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::optional<std::vector<InsertionGenerator::PickupDeliveryInsertion>>
  ComputeEvaluatorSortedPairPositions(int64_t pickup, int64_t 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 RoutingModel::IndexPair& index_pair);
  // Tries to insert any alternative of the given pair,
  // ordered by the sum of pickup and delivery insertion.
  void InsertBestPair(const RoutingModel::IndexPair& index_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 RoutingModel::IndexPair& index_pair,
                               const std::vector<bool>& node_is_pickup,
                               const std::vector<bool>& node_is_delivery);
  // 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);
  // Sets all nodes of pair alternatives as visited.
  void SetIndexPairVisited(const RoutingModel::IndexPair& index_pair);
 
  bool update_start_end_distances_per_node_;
  std::vector<std::vector<StartEndValue>> start_end_distances_per_node_;
  const RoutingSearchParameters::PairInsertionStrategy pair_insertion_strategy_;
  InsertionGenerator insertion_generator_;
 
  // Marks whether a node has already been tried for insertion.
  std::vector<bool> visited_;
};
 
class CheapestAdditionFilteredHeuristic : public RoutingFilteredHeuristic {
 public:
  CheapestAdditionFilteredHeuristic(RoutingModel* model,
                                    std::function<bool()> stop_search,
                                    LocalSearchFilterManager* filter_manager);
  ~CheapestAdditionFilteredHeuristic() override = default;
  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 = default;
  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 = default;
  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:
  typedef std::pair</*saving*/ int64_t, /*saving index*/ int64_t> Saving;
 
  template <typename S>
  class SavingsContainer;
 
  virtual double ExtraSavingsMemoryMultiplicativeFactor() const = 0;
 
  virtual void BuildRoutesFromSavings() = 0;
 
  int64_t GetVehicleTypeFromSaving(const Saving& saving) const {
    return saving.second / size_squared_;
  }
  int64_t GetBeforeNodeFromSaving(const Saving& saving) const {
    return (saving.second % size_squared_) / Size();
  }
  int64_t GetAfterNodeFromSaving(const Saving& saving) const {
    return (saving.second % size_squared_) % Size();
  }
  int64_t GetSavingValue(const Saving& saving) const { return saving.first; }
 
  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 std::make_pair(saving, vehicle_type * size_squared_ +
                                      before_node * Size() + after_node);
  }
 
  int64_t MaxNumNeighborsPerNode(int num_vehicle_types) const;
 
  const SavingsParameters savings_params_;
  int64_t size_squared_;
 
  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 = default;
  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 = default;
  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 = default;
  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);
  virtual ~SweepArranger() {}
  void ArrangeIndices(std::vector<int64_t>* indices);
  void SetSectors(int sectors) { sectors_ = sectors; }
 
 private:
  std::vector<int> coordinates_;
  int sectors_;
 
  DISALLOW_COPY_AND_ASSIGN(SweepArranger);
};
#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_