routing_neighborhoods.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 OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
#define OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_
 
#include <stdbool.h>
 
#include <cstdint>
#include <functional>
#include <string>
#include <utility>
#include <vector>
 
#include "absl/log/check.h"
#include "absl/types/span.h"
#include "ortools/constraint_solver/constraint_solver.h"
#include "ortools/constraint_solver/constraint_solveri.h"
#include "ortools/constraint_solver/routing_types.h"
#include "ortools/util/bitset.h"
 
namespace operations_research {

// TODO(user): Consider merging with standard Relocate in local_search.cc.
 
template <bool ignore_path_vars>
class MakeRelocateNeighborsOperator : public PathOperator<ignore_path_vars> {
 public:
  MakeRelocateNeighborsOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      RoutingTransitCallback2 arc_evaluator);
  ~MakeRelocateNeighborsOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "RelocateNeighbors"; }
 
 private:
  bool MoveChainAndRepair(int64_t before_chain, int64_t chain_end,
                          int64_t destination);

  int64_t Reposition(int64_t before_to_move, int64_t up_to);
 
  RoutingTransitCallback2 arc_evaluator_;
};
 
LocalSearchOperator* MakeRelocateNeighbors(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    RoutingTransitCallback2 arc_evaluator);
 
LocalSearchOperator* MakeRelocateNeighbors(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    RoutingTransitCallback2 arc_evaluator);
 
// Class used to compute shortest paths on DAGs formed by chains of alternative
// node sets.
class ShortestPathOnAlternatives {
 public:
  ShortestPathOnAlternatives(int num_nodes,
                             std::vector<std::vector<int64_t>> alternative_sets,
                             RoutingTransitCallback2 arc_evaluator);
  bool HasAlternatives(int node) const;
  // Returns the shortest path between source and sink, going through the DAG
  // formed by the alternative nodes of the chain. The path omits source and
  // sink.
  absl::Span<const int64_t> GetShortestPath(int64_t source, int64_t sink,
                                            absl::Span<const int64_t> chain);
 
 private:
  RoutingTransitCallback2 arc_evaluator_;
  std::vector<std::vector<int64_t>> alternative_sets_;
  std::vector<int> to_alternative_set_;
  std::vector<int64_t> path_predecessor_;
  std::vector<int64_t> path_;
  std::vector<int64_t> current_values_;
  SparseBitset<int64_t> touched_;
};
 
// Reverses a sub-chain of a path and then replaces it with the shortest path on
// the DAG formed by the sequence of its node alternatives. This operator will
// only reverse chains with at least a node with multiple alternatives.
template <bool ignore_path_vars>
class TwoOptWithShortestPathOperator : public PathOperator<ignore_path_vars> {
 public:
  TwoOptWithShortestPathOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::vector<std::vector<int64_t>> alternative_sets,
      RoutingTransitCallback2 arc_evaluator);
  ~TwoOptWithShortestPathOperator() override = default;
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "TwoOptWithShortestPath"; }
 
 protected:
  bool OnSamePathAsPreviousBase(int64_t /*base_index*/) override {
    // Both base nodes have to be on the same path.
    return true;
  }
  int64_t GetBaseNodeRestartPosition(int base_index) override {
    return (base_index == 0) ? this->StartNode(0) : this->BaseNode(0);
  }
  // Necessary to have proper information about alternatives of current path.
  bool RestartAtPathStartOnSynchronize() override { return true; }
 
 private:
  void ResetIncrementalism() override { ResetChainStatus(); }
  void OnNodeInitialization() override { ResetChainStatus(); }
  void ResetChainStatus() {
    chain_status_.start = -1;
    chain_status_.end = -1;
    chain_status_.has_alternatives = false;
  }
 
  struct ChainStatus {
    int64_t start = -1;
    int64_t end = -1;
    bool has_alternatives = false;
  };
  ChainStatus chain_status_;
  ShortestPathOnAlternatives shortest_path_manager_;
  std::vector<int64_t> chain_;
};
 
LocalSearchOperator* MakeTwoOptWithShortestPath(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::vector<std::vector<int64_t>> alternative_sets,
    RoutingTransitCallback2 arc_evaluator);
 
// Swaps active nodes from node alternatives in sequence. Considers chains of
// nodes with alternatives, builds a DAG from the chain, each "layer" of the DAG
// being composed of the set of alternatives of the node at a given rank in the
// chain, fully connected to the next layer. A neighbor is built from the
// shortest path starting from the node before the chain (source), through the
// DAG to the node following the chain. The path is valued with a given
// callback.
// Example:
// Alternative sets: {1,2} and {3,4}
// Current path: 0 -> 1 -> 3 -> 5
// DAG + source and sink:  -> 1 ---> 3 --
//                        |    \ /       v
//                        0     X        5
//                        |    / \       ^
//                         -> 2 ---> 4 --
// Supposing the shortest path from 0 to 5 is 0, 2, 3, 5, the neighbor for the
// chain will be: 0 -> 2 -> 3 -> 5.
// TODO(user): Support vehicle-class-dependent arc_evaluators.
template <bool ignore_path_vars>
class SwapActiveToShortestPathOperator : public PathOperator<ignore_path_vars> {
 public:
  SwapActiveToShortestPathOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::vector<std::vector<int64_t>> alternative_sets,
      RoutingTransitCallback2 arc_evaluator);
  ~SwapActiveToShortestPathOperator() override = default;
  bool MakeNeighbor() override;
  std::string DebugString() const override {
    return "SwapActiveToShortestPath";
  }
 
 private:
  ShortestPathOnAlternatives shortest_path_manager_;
  std::vector<int64_t> chain_;
};
 
LocalSearchOperator* MakeSwapActiveToShortestPath(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::vector<std::vector<int64_t>> alternative_sets,
    RoutingTransitCallback2 arc_evaluator);

// TODO(user): Add option to prune neighbors where the order of node pairs
//                is violated (ie precedence between pickup and delivery nodes).
// TODO(user): Move this to local_search.cc if it's generic enough.
// TODO(user): Detect pairs automatically by parsing the constraint model;
//                we could then get rid of the pair API in the RoutingModel
//                class.

template <bool ignore_path_vars>
class MakePairActiveOperator : public PathOperator<ignore_path_vars> {
 public:
  MakePairActiveOperator(const std::vector<IntVar*>& vars,
                         const std::vector<IntVar*>& secondary_vars,
                         std::function<int(int64_t)> start_empty_path_class,
                         const std::vector<PickupDeliveryPair>& pairs);
  ~MakePairActiveOperator() override = default;
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "MakePairActive"; }
 
 protected:
  bool MakeOneNeighbor() override;
  bool OnSamePathAsPreviousBase(int64_t /*base_index*/) override {
    return true;
  }
 
  int64_t GetBaseNodeRestartPosition(int base_index) override;

  bool RestartAtPathStartOnSynchronize() override { return true; }
 
 private:
  void OnNodeInitialization() override;
  int FindNextInactivePair(int pair_index) const;
  bool ContainsActiveNodes(absl::Span<const int64_t> nodes) const;
 
  int inactive_pair_;
  int inactive_pair_first_index_;
  int inactive_pair_second_index_;
  const std::vector<PickupDeliveryPair> pairs_;
};
 
LocalSearchOperator* MakePairActive(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

template <bool ignore_path_vars>
class MakePairInactiveOperator : public PathOperator<ignore_path_vars> {
 public:
  MakePairInactiveOperator(const std::vector<IntVar*>& vars,
                           const std::vector<IntVar*>& secondary_vars,
                           std::function<int(int64_t)> start_empty_path_class,
                           const std::vector<PickupDeliveryPair>& pairs);
 
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "MakePairInActive"; }
};
 
LocalSearchOperator* MakePairInactive(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

template <bool ignore_path_vars>
class PairRelocateOperator : public PathOperator<ignore_path_vars> {
 public:
  PairRelocateOperator(const std::vector<IntVar*>& vars,
                       const std::vector<IntVar*>& secondary_vars,
                       std::function<int(int64_t)> start_empty_path_class,
                       const std::vector<PickupDeliveryPair>& pairs);
  ~PairRelocateOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "PairRelocateOperator"; }
 
 protected:
  bool OnSamePathAsPreviousBase(int64_t base_index) override {
    return base_index == kPairSecondNodeDestination;
  }
  int64_t GetBaseNodeRestartPosition(int base_index) override;
 
  bool ConsiderAlternatives(int64_t base_index) const override {
    return base_index == kPairFirstNode;
  }
 
 private:
  bool RestartAtPathStartOnSynchronize() override { return true; }
 
  static constexpr int kPairFirstNode = 0;
  static constexpr int kPairFirstNodeDestination = 1;
  static constexpr int kPairSecondNodeDestination = 2;
};
 
LocalSearchOperator* MakePairRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

template <bool ignore_path_vars>
class GroupPairAndRelocateOperator : public PathOperator<ignore_path_vars> {
 public:
  GroupPairAndRelocateOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      const std::vector<PickupDeliveryPair>& pairs);
  ~GroupPairAndRelocateOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "GroupPairAndRelocate"; }
};
 
LocalSearchOperator* MakeGroupPairAndRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    const std::vector<PickupDeliveryPair>& pairs);
 
LocalSearchOperator* MakeGroupPairAndRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

// TODO(user): Add a version which inserts the first node before the other
// pair's first node; there are many redundant neighbors if done blindly.
template <bool ignore_path_vars>
class LightPairRelocateOperator : public PathOperator<ignore_path_vars> {
 public:
  LightPairRelocateOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      const std::vector<PickupDeliveryPair>& pairs,
      std::function<bool(int64_t)> force_lifo = nullptr);
  ~LightPairRelocateOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override {
    return "LightPairRelocateOperator";
  }
 
 private:
  std::function<bool(int64_t)> force_lifo_;
};
 
LocalSearchOperator* MakeLightPairRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    const std::vector<PickupDeliveryPair>& pairs,
    std::function<bool(int64_t)> force_lifo = nullptr);
 
LocalSearchOperator* MakeLightPairRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs,
    std::function<bool(int64_t)> force_lifo = nullptr);

template <bool ignore_path_vars>
class PairExchangeOperator : public PathOperator<ignore_path_vars> {
 public:
  PairExchangeOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      const std::vector<PickupDeliveryPair>& pairs);
  ~PairExchangeOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override { return "PairExchangeOperator"; }
 
 private:
  bool RestartAtPathStartOnSynchronize() override { return true; }
  bool ConsiderAlternatives(int64_t /*base_index*/) const override {
    return true;
  }
  bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,
                             int64_t* sibling_previous) const;
};
 
LocalSearchOperator* MakePairExchange(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    const std::vector<PickupDeliveryPair>& pairs);
 
LocalSearchOperator* MakePairExchange(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

template <bool ignore_path_vars>
class PairExchangeRelocateOperator : public PathOperator<ignore_path_vars> {
 public:
  PairExchangeRelocateOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      const std::vector<PickupDeliveryPair>& pairs);
  ~PairExchangeRelocateOperator() override = default;
 
  bool MakeNeighbor() override;
  std::string DebugString() const override {
    return "PairExchangeRelocateOperator";
  }
 
 protected:
  bool OnSamePathAsPreviousBase(int64_t base_index) override;
  int64_t GetBaseNodeRestartPosition(int base_index) override;
 
 private:
  bool RestartAtPathStartOnSynchronize() override { return true; }
  bool GetPreviousAndSibling(int64_t node, int64_t* previous, int64_t* sibling,
                             int64_t* sibling_previous) const;
  bool MoveNode(int pair, int node, int64_t nodes[2][2], int64_t dest[2][2],
                int64_t prev[2][2]);
  bool LoadAndCheckDest(int pair, int node, int64_t base_node,
                        int64_t nodes[2][2], int64_t dest[2][2]) const;
 
  static constexpr int kFirstPairFirstNode = 0;
  static constexpr int kSecondPairFirstNode = 1;
  static constexpr int kFirstPairFirstNodeDestination = 2;
  static constexpr int kFirstPairSecondNodeDestination = 3;
  static constexpr int kSecondPairFirstNodeDestination = 4;
  static constexpr int kSecondPairSecondNodeDestination = 5;
};
 
LocalSearchOperator* MakePairExchangeRelocate(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

class SwapIndexPairOperator : public IntVarLocalSearchOperator {
 public:
  SwapIndexPairOperator(const std::vector<IntVar*>& vars,
                        const std::vector<IntVar*>& path_vars,
                        const std::vector<PickupDeliveryPair>& pairs);
  ~SwapIndexPairOperator() override = default;
 
  bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
  void OnStart() override;
  std::string DebugString() const override { return "SwapIndexPairOperator"; }
 
 private:
  bool UpdateActiveNodes();
  void SetNext(int64_t from, int64_t to, int64_t path) {
    DCHECK_LT(from, number_of_nexts_);
    SetValue(from, to);
    if (!ignore_path_vars_) {
      DCHECK_LT(from + number_of_nexts_, Size());
      SetValue(from + number_of_nexts_, path);
    }
  }
 
  const std::vector<PickupDeliveryPair> pairs_;
  int pair_index_;
  int first_index_;
  int second_index_;
  int64_t first_active_;
  int64_t second_active_;
  std::vector<int64_t> prevs_;
  const int number_of_nexts_;
  const bool ignore_path_vars_;
};

template <bool ignore_path_vars>
class IndexPairSwapActiveOperator : public PathOperator<ignore_path_vars> {
 public:
  IndexPairSwapActiveOperator(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      const std::vector<PickupDeliveryPair>& pairs);
  ~IndexPairSwapActiveOperator() override = default;
 
  bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
  bool MakeNeighbor() override;
  std::string DebugString() const override {
    return "IndexPairSwapActiveOperator";
  }
 
 private:
  void OnNodeInitialization() override;
 
  int inactive_node_;
};
 
LocalSearchOperator* MakeIndexPairSwapActive(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs);

template <bool ignore_path_vars>
class RelocateExpensiveChain : public PathOperator<ignore_path_vars> {
 public:
  RelocateExpensiveChain(const std::vector<IntVar*>& vars,
                         const std::vector<IntVar*>& secondary_vars,
                         std::function<int(int64_t)> start_empty_path_class,
                         int num_arcs_to_consider,
                         std::function<int64_t(int64_t, int64_t, int64_t)>
                             arc_cost_for_path_start);
  ~RelocateExpensiveChain() override = default;
 
  bool MakeNeighbor() override;
  bool MakeOneNeighbor() override;
 
  std::string DebugString() const override { return "RelocateExpensiveChain"; }
 
 private:
  void OnNodeInitialization() override;
  void IncrementCurrentPath();
  bool IncrementCurrentArcIndices();
  bool FindMostExpensiveChainsOnRemainingPaths();
 
  int num_arcs_to_consider_;
  int current_path_;
  std::vector<std::pair<int64_t, int>> most_expensive_arc_starts_and_ranks_;
  std::pair</*first_arc_index*/ int, /*second_arc_index*/ int>
      current_expensive_arc_indices_;
  std::function<int64_t(/*before_node*/ int64_t, /*after_node*/ int64_t,
                        /*path_start*/ int64_t)>
      arc_cost_for_path_start_;
  int end_path_;
  bool has_non_empty_paths_to_explore_;
};
 
LocalSearchOperator* MakeRelocateExpensiveChain(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    int num_arcs_to_consider,
    std::function<int64_t(int64_t, int64_t, int64_t)> arc_cost_for_path_start);

template <bool swap_first, bool ignore_path_vars>
class PairNodeSwapActiveOperator : public PathOperator<ignore_path_vars> {
 public:
  PairNodeSwapActiveOperator(const std::vector<IntVar*>& vars,
                             const std::vector<IntVar*>& secondary_vars,
                             std::function<int(int64_t)> start_empty_path_class,
                             const std::vector<PickupDeliveryPair>& pairs);
  ~PairNodeSwapActiveOperator() override = default;
 
  bool MakeNextNeighbor(Assignment* delta, Assignment* deltadelta) override;
  bool MakeNeighbor() override;
  std::string DebugString() const override {
    return "PairNodeSwapActiveOperator";
  }
 
 protected:
  bool OnSamePathAsPreviousBase(int64_t /*base_index*/) override {
    /// nodes after which unactive node pairs will be moved.
    return true;
  }
 
  int64_t GetBaseNodeRestartPosition(int base_index) override;

  bool RestartAtPathStartOnSynchronize() override { return true; }
 
 private:
  void OnNodeInitialization() override;
 
  int inactive_pair_;
  std::vector<PickupDeliveryPair> pairs_;
};
 
// ==========================================================================
// Section: Implementations of the template classes declared above.
 
template <bool swap_first, bool ignore_path_vars>
PairNodeSwapActiveOperator<swap_first, ignore_path_vars>::
    PairNodeSwapActiveOperator(
    const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs)
    : PathOperator<ignore_path_vars>(vars, secondary_vars, 2, false, false,
                                     std::move(start_empty_path_class), nullptr,
                                     nullptr),
      inactive_pair_(0),
      pairs_(pairs) {}
 
template <bool swap_first, bool ignore_path_vars>
int64_t PairNodeSwapActiveOperator<
    swap_first, ignore_path_vars>::GetBaseNodeRestartPosition(int base_index) {
  // Base node 1 must be after base node 0 if they are both on the same path.
  if (base_index == 0 ||
      this->StartNode(base_index) != this->StartNode(base_index - 1)) {
    return this->StartNode(base_index);
  } else {
    return this->BaseNode(base_index - 1);
  }
}
 
template <bool swap_first, bool ignore_path_vars>
void PairNodeSwapActiveOperator<swap_first,
                                ignore_path_vars>::OnNodeInitialization() {
  for (int i = 0; i < pairs_.size(); ++i) {
    if (this->IsInactive(pairs_[i].pickup_alternatives[0]) &&
        this->IsInactive(pairs_[i].delivery_alternatives[0])) {
      inactive_pair_ = i;
      return;
    }
  }
  inactive_pair_ = pairs_.size();
}
 
template <bool swap_first, bool ignore_path_vars>
bool PairNodeSwapActiveOperator<swap_first, ignore_path_vars>::MakeNextNeighbor(
    Assignment* delta, Assignment* deltadelta) {
  while (inactive_pair_ < pairs_.size()) {
    if (!this->IsInactive(pairs_[inactive_pair_].pickup_alternatives[0]) ||
        !this->IsInactive(pairs_[inactive_pair_].delivery_alternatives[0]) ||
        !PathOperator<ignore_path_vars>::MakeNextNeighbor(delta, deltadelta)) {
      this->ResetPosition();
      ++inactive_pair_;
    } else {
      return true;
    }
  }
  return false;
}
 
template <bool swap_first, bool ignore_path_vars>
bool PairNodeSwapActiveOperator<swap_first, ignore_path_vars>::MakeNeighbor() {
  const int64_t base = this->BaseNode(0);
  if (this->IsPathEnd(base)) {
    return false;
  }
  const int64_t pair_first = pairs_[inactive_pair_].pickup_alternatives[0];
  const int64_t pair_second = pairs_[inactive_pair_].delivery_alternatives[0];
  if (swap_first) {
    return this->MakeActive(pair_second, this->BaseNode(1)) &&
           this->MakeActive(pair_first, base) &&
           this->MakeChainInactive(pair_first, this->Next(pair_first));
  } else {
    return this->MakeActive(pair_second, this->BaseNode(1)) &&
           this->MakeActive(pair_first, base) &&
           this->MakeChainInactive(pair_second, this->Next(pair_second));
  }
}
 
template <bool swap_first>
LocalSearchOperator* MakePairNodeSwapActive(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    const std::vector<PickupDeliveryPair>& pairs) {
  if (secondary_vars.empty()) {
    return solver->RevAlloc(new PairNodeSwapActiveOperator<swap_first, true>(
        vars, secondary_vars, std::move(start_empty_path_class), pairs));
  }
  return solver->RevAlloc(new PairNodeSwapActiveOperator<swap_first, false>(
      vars, secondary_vars, std::move(start_empty_path_class), pairs));
}

class PickupAndDeliveryData {
 public:
  PickupAndDeliveryData(int num_nodes,
                        absl::Span<const PickupDeliveryPair> pairs);
  bool IsPickupNode(int64_t node) const {
    DCHECK_LT(node, is_pickup_node_.size());
    return is_pickup_node_[node];
  }
  bool IsDeliveryNode(int64_t node) const {
    DCHECK_LT(node, is_delivery_node_.size());
    return is_delivery_node_[node];
  }
  int GetPairOfNode(int64_t node) const {
    DCHECK_LT(node, pair_of_node_.size());
    return pair_of_node_[node];
  }
 
 private:
  std::vector<bool> is_pickup_node_;
  std::vector<bool> is_delivery_node_;
  std::vector<int> pair_of_node_;
};


template <bool ignore_path_vars>
class RelocateSubtrip : public PathOperator<ignore_path_vars> {
 public:
  RelocateSubtrip(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      absl::Span<const PickupDeliveryPair> pairs);
 
  std::string DebugString() const override { return "RelocateSubtrip"; }
  bool MakeNeighbor() override;
 
 private:
  // Relocates the subtrip starting at chain_first_node. It must be a pickup.
  bool RelocateSubTripFromPickup(int64_t chain_first_node,
                                 int64_t insertion_node);
  bool RelocateSubTripFromDelivery(int64_t chain_last_node,
                                   int64_t insertion_node);
  void SetPath(absl::Span<const int64_t> path, int path_id);
 
  const PickupAndDeliveryData pd_data_;
  // Represents the set of pairs that have been opened during a call to
  // MakeNeighbor(). This vector must be all false before and after calling
  // RelocateSubTripFromPickup() and RelocateSubTripFromDelivery().
  std::vector<bool> opened_pairs_set_;
 
  std::vector<int64_t> rejected_nodes_;
  std::vector<int64_t> subtrip_nodes_;
};
 
LocalSearchOperator* MakeRelocateSubtrip(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    absl::Span<const PickupDeliveryPair> pairs);
 
LocalSearchOperator* MakeRelocateSubtrip(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    absl::Span<const PickupDeliveryPair> pairs);
 
template <bool ignore_path_vars>
class ExchangeSubtrip : public PathOperator<ignore_path_vars> {
 public:
  ExchangeSubtrip(
      const std::vector<IntVar*>& vars,
      const std::vector<IntVar*>& secondary_vars,
      std::function<int(int64_t)> start_empty_path_class,
      std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
      std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
      absl::Span<const PickupDeliveryPair> pairs);
 
  std::string DebugString() const override { return "ExchangeSubtrip"; }
  bool MakeNeighbor() override;
 
 private:
  // Try to extract a subtrip from base_node (see below) and check that the move
  // will be canonical.
  // Given a pickup/delivery pair, this operator could generate the same move
  // twice, the first time with base_node == pickup, the second time with
  // base_node == delivery. This happens only when no nodes in the subtrip
  // remain in the original path, i.e. when rejects is empty after
  // chain extraction. In that case, we keep only a canonical move out of the
  // two possibilities, the move where base_node is a pickup.
  bool ExtractChainsAndCheckCanonical(int64_t base_node,
                                      std::vector<int64_t>* rejects,
                                      std::vector<int64_t>* subtrip);
  // Reads the path from base_node forward, collecting subtrip nodes in
  // subtrip and non-subtrip nodes in rejects.
  // Non-subtrip nodes will be unmatched delivery nodes.
  // base_node must be a pickup, and remaining/extracted_nodes must be empty.
  // Returns true if such chains could be extracted.
  bool ExtractChainsFromPickup(int64_t base_node, std::vector<int64_t>* rejects,
                               std::vector<int64_t>* subtrip);
  // Reads the path from base_node backward, collecting subtrip nodes in
  // subtrip and non-subtrip nodes in rejects.
  // Non-subtrip nodes will be unmatched pickup nodes.
  // base_node must be a delivery, and remaining/extracted_nodes must be empty.
  // Returns true if such chains could be extracted.
  bool ExtractChainsFromDelivery(int64_t base_node,
                                 std::vector<int64_t>* rejects,
                                 std::vector<int64_t>* subtrip);
  void SetPath(absl::Span<const int64_t> path, int path_id);
 
  const PickupAndDeliveryData pd_data_;
  // Represents the set of opened pairs during ExtractChainsFromXXX().
  std::vector<bool> opened_pairs_set_;
  // Keep internal structures under hand to avoid reallocation.
  std::vector<int64_t> rejects0_;
  std::vector<int64_t> subtrip0_;
  std::vector<int64_t> rejects1_;
  std::vector<int64_t> subtrip1_;
  std::vector<int64_t> path0_;
  std::vector<int64_t> path1_;
};
 
LocalSearchOperator* MakeExchangeSubtrip(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    std::function<const std::vector<int>&(int, int)> get_incoming_neighbors,
    std::function<const std::vector<int>&(int, int)> get_outgoing_neighbors,
    absl::Span<const PickupDeliveryPair> pairs);
 
LocalSearchOperator* MakeExchangeSubtrip(
    Solver* solver, const std::vector<IntVar*>& vars,
    const std::vector<IntVar*>& secondary_vars,
    std::function<int(int64_t)> start_empty_path_class,
    absl::Span<const PickupDeliveryPair> pairs);
 
}  // namespace operations_research
 
#endif  // OR_TOOLS_CONSTRAINT_SOLVER_ROUTING_NEIGHBORHOODS_H_