.. _program_listing_file_src_utils.cpp: Program Listing for File utils.cpp ================================== |exhale_lsh| :ref:`Return to documentation for file ` (``src/utils.cpp``) .. |exhale_lsh| unicode:: U+021B0 .. UPWARDS ARROW WITH TIP LEFTWARDS .. code-block:: cpp #include "cvrp/utils.hpp" #include #include #include #include #include #include std::ostream &operator<<(std::ostream &os, const Node &node) { os << "Node Status" << '\n'; os << "ID : " << node.id_ << '\n'; os << "X : " << node.x_ << '\n'; os << "Y : " << node.y_ << '\n'; os << "Demand: " << node.demand_ << '\n'; os << '\n'; return os; } void Vehicle::CalculateCost( const std::vector> &distanceMatrix) { cost_ = 0; for (size_t i = 0; i < nodes_.size() - 1; i++) { cost_ += distanceMatrix[nodes_[i]][nodes_[i + 1]]; } } std::ostream &operator<<(std::ostream &os, const Vehicle &v) { os << "Vehicle Status" << '\n'; os << "Cost : " << v.cost_ << '\n'; os << "ID : " << v.id_ << '\n'; os << "Load : " << v.load_ << '\n'; os << "Capacity: " << v.capacity_ << '\n'; os << "Path : "; // the nodes_.size()-1 limit is only added to ensure that there isnt a ---> // after the last node, which is always the depot, ie node 0. for (size_t i = 0; i < v.nodes_.size() - 1; ++i) { os << v.nodes_[i] << " ---> "; } os << "0"; os << '\n' << '\n'; return os; } void PrintVehicleRoute(const Vehicle &v) { for (size_t i = 0; i < v.nodes_.size() - 1; ++i) { std::cout << v.nodes_[i] << " ---> "; } std::cout << "0"; std::cout << '\n' << '\n'; } Solution::Solution(std::vector nodes, const std::vector &vehicles, std::vector> distanceMatrix) : nodes_(std::move(nodes)), vehicles_(vehicles), distanceMatrix_(std::move(distanceMatrix)) { depot_ = nodes_[0]; capacity_ = vehicles[0].load_; } Solution::Solution(const Problem &p) : nodes_(p.nodes_), vehicles_(p.vehicles_), distanceMatrix_(p.distanceMatrix_), capacity_(p.capacity_) { depot_ = nodes_[0]; } void Solution::CreateInitialSolution() { for (auto &v : vehicles_) { while (true) { const auto [found, closest_node] = find_closest(v); if (found && v.load_ - closest_node.demand_ >= 0) { // }.2*capacity){ v.load_ -= closest_node.demand_; v.cost_ += distanceMatrix_[v.nodes_.back()][closest_node.id_]; v.nodes_.push_back(closest_node.id_); nodes_[closest_node.id_].is_routed_ = true; } else { v.cost_ += distanceMatrix_[v.nodes_.back()][depot_.id_]; v.nodes_.push_back(depot_.id_); break; } } } } std::tuple Solution::find_closest(const Vehicle &v) const { double cost = std::numeric_limits::max(); size_t id = 0; bool found = false; for (size_t j = 0; j < distanceMatrix_[0].size(); j++) { if (!nodes_[j].is_routed_ && nodes_[j].demand_ <= v.load_ && distanceMatrix_[v.nodes_.back()][j] < cost) { cost = distanceMatrix_[v.nodes_.back()][j]; id = j; found = true; } } if (found) { return {true, nodes_[id]}; } return {false, Node()}; } bool Solution::CheckSolutionValid() const { // double cost = 0; std::vector check_nodes(nodes_.size(), false); check_nodes[0] = true; for (const auto &v : vehicles_) { int load = capacity_; for (const auto &n : v.nodes_) { load -= nodes_[n].demand_; check_nodes[n] = true; } if (load < 0) { return false; } } return std::all_of(std::begin(check_nodes), std::end(check_nodes), [](const bool b) { return b; }); } Problem::Problem(const int noc, const int demand_range, const int nov, const int capacity, const int grid_range, std::string distribution, const int n_clusters, const int cluster_range) { std::random_device rd; // obtain a random number from hardware std::mt19937 eng(rd()); // seed the generator std::uniform_int_distribution ran(-grid_range, grid_range); // define the range std::uniform_int_distribution ran_d(0, demand_range); // define the range std::uniform_int_distribution ran_c(-cluster_range, cluster_range); Node depot(0, 0, 0, 0, true); this->capacity_ = capacity; nodes_.push_back(depot); if (distribution != "uniform" && distribution != "cluster") { distribution = "uniform"; } if (distribution == "uniform") { for (int i = 1; i <= noc; ++i) { nodes_.emplace_back(ran(eng), ran(eng), i, ran_d(eng), false); } } else if (distribution == "cluster") { int id = 1; int n_p_c = noc / n_clusters; int remain = noc % n_clusters; for (int i = 0; i < n_clusters; i++) { int x = ran(eng); int y = ran(eng); for (int j = 0; j < n_p_c; j++) { nodes_.emplace_back(x + ran_c(eng), y + ran_c(eng), id, ran_d(eng), false); id++; } } int x = ran(eng); int y = ran(eng); for (int j = 0; j < remain; j++) { nodes_.emplace_back(x + ran_c(eng), y + ran_c(eng), id, ran_d(eng), false); id++; } } // for(const auto& n:nodes) std::cout << n << '\n'; std::vector tmp(nodes_.size()); for (size_t i = 0; i < nodes_.size(); ++i) { distanceMatrix_.push_back(tmp); } for (size_t i = 0; i < nodes_.size(); ++i) { for (size_t j = i; j < nodes_.size(); ++j) { distanceMatrix_[i][j] = sqrt(pow((nodes_[i].x_ - nodes_[j].x_), 2) + pow((nodes_[i].y_ - nodes_[j].y_), 2)); distanceMatrix_[j][i] = distanceMatrix_[i][j]; } } int load = capacity_; for (int i = 0; i < nov; ++i) { vehicles_.emplace_back(i, load, capacity_); vehicles_[i].nodes_.push_back(0); } } void Solution::PrintSolution(const std::string &option) const { double total_cost = 0; for (const auto &v : vehicles_) { total_cost += v.cost_; if (option == "status") { PrintVehicleRoute(v); } else if (option == "route") { std::cout << "Vehicle ID: " << v.id_ << " | "; PrintVehicleRoute(v); } } bool valid = CheckSolutionValid(); std::cout << "Total solution cost: " << total_cost << '\n'; std::cout << "Solution validity : " << valid << '\n'; if (!valid) { for (const auto &i : nodes_) { if (!i.is_routed_) { std::cout << "Unreached node: " << '\n'; std::cout << i << '\n'; } } } }