.. _program_listing_file_src_local_search_intra.cpp: Program Listing for File local_search_intra.cpp =============================================== |exhale_lsh| :ref:`Return to documentation for file ` (``src/local_search_intra.cpp``) .. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS .. code-block:: cpp #include "cvrp/local_search_intra.hpp" #include #include constexpr double margin_of_error = 0.00001; LocalSearchIntraSolution::LocalSearchIntraSolution( const std::vector& nodes, const std::vector& vehicles, const std::vector>& distanceMatrix) : Solution(nodes, vehicles, distanceMatrix) { CreateInitialSolution(); } LocalSearchIntraSolution::LocalSearchIntraSolution(const Problem& p) : Solution(p.nodes_, p.vehicles_, p.distanceMatrix_) { CreateInitialSolution(); } LocalSearchIntraSolution::LocalSearchIntraSolution(const Solution& s) : Solution(s) { if (!s.CheckSolutionValid()) { std::cout << "The input solution is invalid. Exiting." << '\n'; exit(0); } } void LocalSearchIntraSolution::Solve() { for (auto& v : vehicles_) { while (true) { double delta = 0; int best_c = -1; int best_r = -1; for (size_t cur = 1; cur < v.nodes_.size() - 1; cur++) { const int v_cur = v.nodes_[cur]; const int v_prev = v.nodes_[cur - 1]; const int v_next_c = v.nodes_[cur + 1]; const double cost_reduction = distanceMatrix_[v_prev][v_next_c] - distanceMatrix_[v_prev][v_cur] - distanceMatrix_[v_cur][v_next_c]; for (size_t rep = 1; rep < v.nodes_.size() - 1; rep++) { if (rep != cur && rep != cur - 1) { const int v_rep = v.nodes_[rep]; const int v_next_r = v.nodes_[rep + 1]; const double cost_increase = distanceMatrix_[v_rep][v_cur] + distanceMatrix_[v_cur][v_next_r] - distanceMatrix_[v_rep][v_next_r]; if (cost_increase + cost_reduction < delta) { delta = cost_increase + cost_reduction; best_c = cur; best_r = rep; } } } } if (delta > -margin_of_error) { break; } const int val_best_c = *std::next(v.nodes_.begin(), best_c); v.nodes_.erase(std::next(v.nodes_.begin(), best_c)); if (best_c < best_r) { v.nodes_.insert(std::next(v.nodes_.begin(), best_r), val_best_c); } else { v.nodes_.insert(std::next(v.nodes_.begin(), best_r + 1), val_best_c); } v.CalculateCost(distanceMatrix_); } } double cost = std::accumulate( std::begin(vehicles_), std::end(vehicles_), 0.0, [](const double sum, const Vehicle& v) { return sum + v.cost_; }); std::cout << "Cost: " << cost << '\n'; for (const auto& i : nodes_) { if (!i.is_routed_) { std::cout << "Unreached node: " << '\n'; std::cout << i << '\n'; } } std::cout << "Solution valid: " << CheckSolutionValid() << '\n'; }