diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | main.py | 155 | ||||
| -rw-r--r-- | vrptw_base.py | 43 |
3 files changed, 199 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..62c8935 --- /dev/null +++ b/.gitignore @@ -0,0 +1 @@ +.idea/
\ No newline at end of file @@ -0,0 +1,155 @@ +import numpy as np +from vrptw_base import Graph + + +class VRPTW_ACO: + def __init__(self, graph: Graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1): + super() + self.graph = graph + self.ants_num = ants_num + self.max_iter = max_iter + self.alpha = alpha + self.beta = beta + # 信息素挥发速度 + self.rho = rho + # q0 表示直接选择概率最大的下一点的概率 + self.q0 = 0.1 + # Q 表示每辆车的最大载重 + self.max_load = 1 + # L 表示每辆车的最远行驶距离 + self.max_travel_distance = 100 + # 出车的单位成本 + self.car_cost = 1 + # 行驶的单位成本 + self.travel_cost = 1 + # 早到时间成本 + self.early_arrival_cost = 1 + # 晚到时间成本 + self.late_arrival_cost = 1 + # 信息素强度 + self.Q = 1 + # 创建信息素矩阵 + self.pheromone_mat = np.ones((graph.node_num, graph.node_num)) + self.eta_mat = 1 / graph.node_dist_mat + + def run(self): + # 最大迭代次数 + for iter in range(self.max_iter): + probability = np.zeros((self.graph.node_num, self.graph.node_num)) + vehicle_load = np.zeros(self.graph.node_num) + travel_distance = np.zeros(self.graph.node_num) + + # 遍历所有的蚂蚁 + ants_path = list([] for _ in range(self.ants_num)) + for k in range(self.ants_num): + index_to_visit = list(range(graph.node_num)) + + # 每只蚂蚁都从0位置出发，最终要回到0位置 + current_index = 0 + ants_path[k] = [current_index] + index_to_visit.remove(current_index) + + # 蚂蚁需要访问完所有的客户 + while len(index_to_visit) > 0: + next_index = self.select_next_index(probability, current_index, index_to_visit) + # 判断加入该位置后，是否还满足约束条件, 如果不满足，则再选择一次，然后再进行判断 + if not self.check_condition(current_index, next_index, vehicle_load[k], travel_distance[k]): + next_index = self.select_next_index(probability, current_index, index_to_visit) + if not self.check_condition(current_index, next_index, vehicle_load[k], travel_distance[k]): + next_index = 0 + + # 更新蚂蚁路径 + if next_index == 0: + ants_path[k].append(next_index) + vehicle_load[k] = 0 + travel_distance[k] = 0 + else: + ants_path[k].append(next_index) + index_to_visit.remove(next_index) + vehicle_load[k] += self.graph.nodes[next_index].demand + travel_distance[k] += self.graph.node_dist_mat[current_index][next_index] + + # 最终回到0位置 + ants_path[k].append(0) + + # 计算所有蚂蚁的路径长度 + paths_distance = self.calculate_all_path_distance(ants_path) + + # 记录当前的最佳路径 + paths_cost = self.calculate_all_path_cost(ants_path) + best_index = np.argmin(paths_cost) + + # 更新信息素表 + self.update_pheromone_mat(ants_path, paths_distance, ) + + def select_next_index(self, probability, current_index, index_to_visit): + probability[current_index][index_to_visit] = np.power(self.pheromone_mat[current_index][index_to_visit], self.alpha) * \ + np.power(self.eta_mat[current_index][index_to_visit], self.beta) + if np.random.rand() < self.q0: + # 这里的index不能这么写 + max_prob_index = np.argmax(probability[current_index][index_to_visit]) + next_index = index_to_visit[max_prob_index] + else: + # 使用轮盘度 + prob_sum = np.sum(probability[current_index][index_to_visit]) + next_index = np.random.choice(index_to_visit, probability[current_index][index_to_visit]/prob_sum) + return next_index + + def check_condition(self, current_index, next_index, vehicle_load, travel_distance) -> bool: + """ + 检查移动到下一个点是否满足约束条件 + :param current_index: + :param next_index: + :param vehicle_load: + :param travel_distance: + :return: + """ + if vehicle_load + self.graph.nodes[next_index].demand > self.max_load: + return False + if travel_distance + self.graph.node_dist_mat[current_index][next_index] + self.graph.node_dist_mat[next_index][0] > self.max_travel_distance: + return False + return True + + def update_pheromone_mat(self, paths, paths_distance): + """ + 更新信息素矩阵 + :return: + """ + self.pheromone_mat = (1 - self.rho) * self.pheromone_mat + for k in range(self.graph.node_num): + current_index = paths[k][0] + for index in paths[k][1:]: + self.pheromone_mat[current_index][index] += self.Q / paths_distance[k] + + def calculate_all_path_cost(self, paths): + # 注意路径是否是从0开始到0结束的 + costs = np.zeros(self.graph.node_num) + for k in range(self.graph.node_num): + current_index = paths[k][0] + for index in paths[k][1:]: + if index == 0: + costs[k] += self.car_cost + self.travel_cost * self.graph.node_dist_mat[current_index][index] + else: + costs[k] += self.travel_cost * self.graph.node_dist_mat[current_index][index] + # 这里如何计算是否是早到了，还是迟到了，我还没有记录时间 + costs[k] += 0 + current_index = index + + return costs + + def calculate_all_path_distance(self, paths): + distances = np.zeros(self.graph.node_num) + for k in range(self.graph.node_num): + current_index = paths[k][0] + for index in paths[k][1:]: + distances[k] += self.graph.node_dist_mat[current_index][index] + current_index = index + return distances + + +if __name__ == '__main__': + file_path = '' + graph = Graph(file_path) + + vrptw = VRPTW_ACO(graph, ants_num=50, max_iter=300, alpha=1, beta=1, rho=0.1) + vrptw.run() diff --git a/vrptw_base.py b/vrptw_base.py new file mode 100644 index 0000000..37b73d3 --- /dev/null +++ b/vrptw_base.py @@ -0,0 +1,43 @@ +import numpy as np + + +class Node: + def __init__(self, x, y, demand, earliest_time, latest_time, service_time): + super() + self.x = x + self.y = y + self.demand = demand + self.earliest_time = earliest_time + self.latest_time = latest_time + self.service_time = service_time + + +class Graph: + def __init__(self, file_path): + super() + # node_num 结点个数 + # node_dist_mat 节点之间的距离（矩阵） + # pheromone_mat 节点之间路径上的信息度浓度 + self.node_num, self.nodes, self.node_dist_mat = self.create_from_file(file_path) + + def create_from_file(self, file_path): + # 从文件中读取服务点、客户的位置 + with open(file_path, 'rt') as f: + node_list = list(line.split() for line in f) + node_num = len(node_list) + nodes = list(Node(float(item[0]), float(item[1]), float(item[2]), float(item[3]), float(item[4]), float(item[5])) for item in node_list) + + # 创建距离矩阵 + node_dist_mat = np.zeros((node_num, node_num)) + for i in range(node_num): + node_a = nodes[i] + for j in range(i, node_num): + node_b = nodes[j] + node_dist_mat[i][j] = Graph.calculate_dist(node_a, node_b) + node_dist_mat[j][i] = node_dist_mat[i][j] + + return node_num, nodes, node_dist_mat + + @staticmethod + def calculate_dist(node_a, node_b): + return np.linalg.norm((node_a.x - node_b.x, node_a.y - node_b.y))
\ No newline at end of file |