VRPSPDTW问题（具有同时配送和时间窗的车辆路径问题），算法具有高效的局部搜索和扩展邻域的功能

#include "operator.h" // for preventing memory allocation Move tmp_move; // map from string to opt; std::map<std::string, std::function<void(int, int, Solution&, Data&, Move&)>> small_opt_map = { {"2opt", two_opt}, {"2opt*", two_opt_star}, {"oropt_single", or_opt_single}, {"oropt_double", or_opt_double}, {"2exchange", two_exchange}}; std::map<std::string, std::function<void(Solution &, Data &)>> destroy_opt_map = {{"random_removal", random_removal}, {"related_removal", related_removal}}; std::map<std::string, std::function<void(Solution &, Data &)>> repair_opt_map = {{"regret_insertion", regret_insertion}, {"greedy_insertion", greedy_insertion}}; void maintain_unrouted(int i, int node, int &index, std::vector<std::tuple<int, int>> &unrouted, double &unrouted_d, double &unrouted_p, Data &data) { unrouted[i] = unrouted[index-1]; index--; unrouted_d -= data.node[node].delivery; unrouted_p -= data.node[node].pickup; } double cal_tc(std::vector<int> &nl, int inserted_node, int pos, double unrouted_d, double unrouted_p, Data &data) { int ori_len = int(nl.size()); int new_len = ori_len + 1; double capacity = data.vehicle.capacity; // RDT and RPT for route double rdt = 0.0; double rpt = 0.0; double route_d = 0.0; double route_p = 0.0; for (int i = 1; i < ori_len; i++) { route_d += data.node[nl[i]].delivery; route_p += data.node[nl[i]].pickup; } route_d += data.node[inserted_node].delivery; route_p += data.node[inserted_node].pickup; static std::vector<double> rd(MAX_NODE_IN_ROUTE); static std::vector<double> rp(MAX_NODE_IN_ROUTE); static std::vector<double> load(MAX_NODE_IN_ROUTE); static std::vector<double> cd(MAX_NODE_IN_ROUTE); static std::vector<double> cp(MAX_NODE_IN_ROUTE); load[0] = route_d; cd[0] = 0.0; cp[new_len - 1] = 0.0; int index = 1; bool checked = false; int pre_node = nl[0]; for (int i = 1; i < ori_len; i++) { int node = nl[i]; if (i == pos && !checked) { node = inserted_node; i--; checked = true; } load[index] = load[index - 1] - data.node[node].delivery + data.node[node].pickup; cd[index] = cd[index - 1] + data.dist[pre_node][node]; pre_node = node; index++; } checked = false; int after_node = nl[ori_len - 1]; index = new_len-1; for (int i = ori_len - 1; i > 0; i--) { int node = nl[i - 1]; if (i == pos && !checked) { node = inserted_node; i++; checked = true; } cp[index - 1] = cp[index] + data.dist[node][after_node]; after_node = node; index--; } rd[0] = capacity - route_d; rp[new_len - 2] = capacity - route_p; for (int i = 1; i < new_len - 1; i++) { rd[i] = std::min(rd[i - 1], capacity - load[i]); rp[new_len - 2 - i] = std::min(rp[new_len - 1 - i], capacity - load[new_len - 2 - i]); } double rdt_u = 0.0; double rdt_d = 0.0; double rpt_u = 0.0; double rpt_d = 0.0; for (int i = 0; i < new_len - 1; i++) { rdt_u += rd[i] * cd[i + 1]; rdt_d += cd[i + 1]; rpt_u += rp[i] * cp[i]; rpt_d += cp[i]; } rdt = rdt_u / rdt_d; rpt = rpt_u / rpt_d; // TC double tc = (unrouted_d / data.all_delivery) * (1 - rdt / capacity) + (unrouted_p / data.all_pickup) * (1 - rpt / capacity); return tc; } double criterion(Route &r, Data &data, int node, int pos, double unrouted_d, double unrouted_p) { std::vector<int> &nl = r.node_list; // TD int pre = nl[pos-1]; int suc = nl[pos]; double td = data.dist[pre][node] + data.dist[node][suc] - data.dist[pre][suc]; if (data.n_insert == TD) return td; // TC // std::vector<int> tmp_nl = r.node_list; // tmp_nl.insert(tmp_nl.begin() + pos, node); double tc = cal_tc(r.node_list, node, pos, unrouted_d, unrouted_p, data); // RS double rs = data.dist[data.DC][node] + data.dist[node][data.DC]; // RCRS double rcrs = td + std::get<0>(data.lambda_gamma) * tc * (2 * data.max_dist - data.min_dist) - std::get<1>(data.lambda_gamma) * rs; return rcrs; } bool cal_score(std::vector<bool> &feasible_pos, std::vector<std::tuple<int, int>> &unrouted, std::vector<double> &score, int index, Route &r, double unrouted_d, double unrouted_p, Data &data) { /* calculate insertion criterion for each node in unrouted, return false if no feasible insertion exists */ if (index == 0) return false; int r_len = int(r.node_list.size()); // filter all infeasible positions int count = 0; for (int i = 0; i < index; i++) { int node = std::get<0>(unrouted[i]); for (int pos = 1; pos < r_len; pos++) { bool flag = false; double cost = -1.0; chk_nl_node_pos_O_n(r.node_list, node, pos, data, flag, cost); if (!flag) feasible_pos[i*MAX_NODE_IN_ROUTE+pos] = false; else { feasible_pos[i*MAX_NODE_IN_ROUTE+pos] = true; count++; } } } if (count == 0) return false; // insertion criterion for (int i = 0; i < index; i++) { int node = std::get<0>(unrouted[i]); double best_score = double(INFINITY); int best_pos = -1; for (int pos = 1; pos < r_len; pos++) { if (!feasible_pos[i*MAX_NODE_IN_ROUTE+pos]) continue; double utility = criterion(r, data, node, pos, unrouted_d,\ unrouted_p); if (utility - best_score < -PRECISION) { best_score = utility; best_pos = pos; } } std::get<1>(unrouted[i]) = best_pos; score[i] = best_score; } return true; } void find_unrouted(Solution &s, std::vector<int> &record) { int len = s.len(); for (int i = 0; i < len; i++) { Route &r = s.get(i); for (auto node : r.node_list) { record[node] = 1; } } } void update_nodes_pm_cost(Solution &s, std::vector<std::vector<int>> &nodes_pm_pos, std::vector<std::vector<double>> &nodes_pm_cost, std::vector<int> &unrouted_nodes, Data &data) { for (int i = 0; i < int(unrouted_nodes.size()); i++) { auto &single_node_pm_pos = nodes_pm_pos[i]; auto &single_node_pm_cost = nodes_pm_cost[i]; int node = unrouted_nodes[i]; // build a new route with node {DC, node, DC} std::vector<int> tmp_nl = make_tmp_nl(data); bool flag = false; double cost = -1.0; chk_nl_node_pos_O_n(tmp_nl, node, 1, data, flag, cost); if (!flag) { printf("Error: Detect not feasible 1-customer route: "); for (auto &node : tmp_nl) { std::cout << node; } exit(-1); } single_node_pm_pos[0] = 1; single_node_pm_cost[0] = cost; // insert into existing routes, one by one for (int r_index = 0; r_index < s.len(); r_index++) { Route &r = s.get(r_index); double ori_cost = r.cal_cost(data); double best_incur_cost = double(INFINITY); int best_pos = -1; for (int pos = 1; pos < int(r.node_list.size()); pos++) { bool flag = false; double cost = -1.0; chk_nl_node_pos_O_n(r.node_list, node, pos, data, flag, cost); if (flag)