Program Listing for File tabu_search.hpp

↰ Return to documentation for file (include/cvrp/tabu_search.hpp)

#ifndef TS_HPP
#define TS_HPP

#include <queue>
#include <unordered_set>
#include <utility>

#include "cvrp/utils.hpp"

struct PairHash {
  template <typename T1, typename T2>
  size_t operator()(const std::pair<T1, T2>& p) const {
    auto hash1 = std::hash<T1>{}(p.first);
    auto hash2 = std::hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};

class TabuSearchSolution : public Solution {
 public:
  TabuSearchSolution(const std::vector<Node>& nodes,
                     const std::vector<Vehicle>& vehicles,
                     const std::vector<std::vector<double>>& distanceMatrix,
                     const int n_tabu = 50, const int max_it = 500);
  explicit TabuSearchSolution(const Problem& p, const int n_tabu = 50,
                              const int max_it = 500);

  explicit TabuSearchSolution(const Solution& s, const int n_tabu = 50,
                              const int max_it = 500);

  void Solve() override;

 private:
  int n_tabu_;
  const int max_it_;
  double best_cost_ = std::numeric_limits<double>::max();
  double new_cost_ = std::numeric_limits<double>::max();

  // invert order of v1, v2 and cur, rep+1
  std::unordered_set<std::pair<int, int>, PairHash> tabu_list_set_;
  std::queue<std::pair<int, int>> tabu_list_queue_;

  inline bool IsTabu(const std::pair<int, int>& p) const;

  inline bool Aspiration(double cost_increase, double cost_reduction) const;
};

#endif  // TS_HPP