diff options
Diffstat (limited to 'vrptw_base.py')
| -rw-r--r-- | vrptw_base.py | 60 |
1 files changed, 54 insertions, 6 deletions
diff --git a/vrptw_base.py b/vrptw_base.py index 8de14ce..a4c92a1 100644 --- a/vrptw_base.py +++ b/vrptw_base.py @@ -13,7 +13,7 @@ class Node: self.service_time = service_time -class VPRTW_Graph: +class VrptwGraph: def __init__(self, file_path): super() # node_num 结点个数 @@ -45,7 +45,7 @@ class VPRTW_Graph: node_dist_mat[i][i] = np.inf for j in range(i+1, node_num): node_b = nodes[j] - node_dist_mat[i][j] = VPRTW_Graph.calculate_dist(node_a, node_b) + node_dist_mat[i][j] = VrptwGraph.calculate_dist(node_a, node_b) node_dist_mat[j][i] = node_dist_mat[i][j] return node_num, nodes, node_dist_mat, vehicle_num, vehicle_capacity @@ -60,7 +60,7 @@ class Ant: super() self.current_index = 0 self.vehicle_load = 0 - self.vehicle_travel_distance = 0 + self.vehicle_travel_time = 0 self.travel_path = [0] self.arrival_time = [0] self.index_to_visit = list(range(1, node_num)) @@ -69,21 +69,69 @@ class Ant: def move_to_next_index(self, graph, next_index): # 更新蚂蚁路径 self.travel_path.append(next_index) - self.arrival_time.append(self.vehicle_travel_distance) self.total_travel_distance += graph.node_dist_mat[self.current_index][next_index] + dist = graph.node_dist_mat[self.current_index][next_index] + self.arrival_time.append(self.vehicle_travel_time + dist) + if next_index == 0: # 如果一下个位置为服务器点，则要将车辆负载等清空 self.vehicle_load = 0 - self.vehicle_travel_distance = 0 + self.vehicle_travel_time = 0 else: # 更新车辆负载、行驶距离、时间 self.vehicle_load += graph.nodes[next_index].demand - self.vehicle_travel_distance += graph.node_dist_mat[self.current_index][next_index] + graph.nodes[next_index].service_time + # 如果早于客户要求的时间窗(ready_time)，则需要等待 + + self.vehicle_travel_time += dist + max(graph.nodes[next_index].ready_time - self.vehicle_travel_time - dist, 0) + graph.nodes[next_index].service_time self.index_to_visit.remove(next_index) self.current_index = next_index def index_to_visit_empty(self): return len(self.index_to_visit) == 0 + + +class NearestNeighborHeuristic: + def __init__(self, graph: VrptwGraph): + self.graph = graph + self.ant = Ant(graph.node_num) + + def cal_init_pheromone_val(self): + while not self.ant.index_to_visit_empty(): + customers_meet_constrains = self.cal_customers_meet_constrains() + if len(customers_meet_constrains) == 0: + next_index = 0 + else: + next_index = self.cal_nearest_customer(customers_meet_constrains) + + self.ant.move_to_next_index(self.graph, next_index) + self.ant.move_to_next_index(self.graph, 0) + + init_pheromone = (1 / (self.graph.node_num * self.ant.total_travel_distance)) + return init_pheromone + + def cal_customers_meet_constrains(self): + customers_meet_constrains = [] + current_ind = self.ant.current_index + for next_ind in self.ant.index_to_visit: + condition1 = self.ant.vehicle_travel_time + self.graph.node_dist_mat[current_ind][next_ind] <= self.graph.nodes[next_ind].due_time + condition2 = self.ant.vehicle_load + self.graph.nodes[next_ind].demand <= self.graph.vehicle_capacity + if condition1 and condition2: + customers_meet_constrains.append(next_ind) + return customers_meet_constrains + + def cal_nearest_customer(self, customers): + current_ind = self.ant.current_index + + nearest_ind = customers[0] + min_dist = self.graph.node_dist_mat[current_ind][customers[0]] + + for next_ind in customers[1:]: + dist = self.graph.node_dist_mat[current_ind][next_ind] + if dist < min_dist: + min_dist = dist + nearest_ind = next_ind + + return nearest_ind |