摘要
综合考虑相对位移量和相对旋转角的约束，建立TSP模型，由于数据量较小，故而用贪心算法遍历所有路径暴力求解，找到每个点访问且仅访问一次的情况下总距离最短的路径，从而使总位移量和总旋转角度最小，进而找到打孔的次序。
构建加权无向图
将孔视为节点，$K$为节点的集合，建立加权无向图$G = (K,W)$，找到一条路径C使得C的总权$w(C) = \sum_{C_{ij},Kj \in C} w(C_{ij},S_{ij})$最小；
其中$C_{ij} = |A_{ij}| + |B_{ij}|, S_{ij} = |X_{ij}| + |Y_{ij}| + |Z_{ij}|$
将$C_{ij}$和$S_{ij}$整合为参量$D_{ij}$，即
$D_{ij} = \alpha\cdot C_{ij} + \beta \cdot S_{ij}$
本题中$\alpha = \beta = 1$（表示两个约束条件的相对重要程度相同）
从而将问题转化为求 $\min \sum_{Ki,Kj \in K} D_{ij}$
贪心算法求解
- 任意选择一个起始节点，标记为已访问，将路径长度初始化为0 #创建空访问列表
- 从当前已访问的节点出发，选择距离当前点最近且未被访问过的点作为下一个访问点（如果存在多个距离相同的未访问节点，任意选择其中之一），将选定的下一个节点添加到路径中，更新路径和访问标记；重复执行直到所有点都被访问； #循环主体内容，找到一个局部最优解的方法
- 更新起始节点 #新循环起始
- 整合所有局部最优解，得到近似最优路径
结果
- 打孔次序为： K1, K3, K8, K7, K5, K6, K2, K12, K11, K4, K9, K10
- 总位移量为： 3731.02
- 总旋转角度为：478.04
模型分析
- 优点：对于本题数据量较小的情景适应度较高
- 缺点：对于数据量较大的情况，可能仅求解出局部最优的结果；因而在数据量更大的情况下，可以使用遗传算法等其他求解方法。
完整代码
import pandas as pd
import numpy as np
from scipy.spatial.distance import squareform
# 加载位移量和旋转角度数据
displacement_df = pd.read_excel('相对位移量.xlsx', sheet_name=3)
rotation_angle_df = pd.read_excel('相对旋转角.xlsx', header=None)
rotation_angle_df.columns = displacement_df.columns[1:] # 从第二列开始复制列名，避免"Unnamed: 0"
rotation_angle_df.insert(0, 'Unnamed: 0', displacement_df['Unnamed: 0']) # 明确插入"Unnamed: 0"列
# 计算总距离、总位移量和总旋转角度
total_distance_df = displacement_df.set_index('Unnamed: 0') + rotation_angle_df.set_index('Unnamed: 0')
total_displacement = displacement_df.set_index('Unnamed: 0').sum(axis=1)
total_rotation_angle = rotation_angle_df.set_index('Unnamed: 0').sum(axis=1)
# 准备距离矩阵
distance_matrix = total_distance_df.to_numpy()
np.fill_diagonal(distance_matrix, np.inf)
# 定义贪心算法
def find_greedy_path(distance_matrix):
n = distance_matrix.shape[0]
current_hole = 0
path = [current_hole]
visited = set(path)
while len(visited) < n:
distances = np.copy(distance_matrix[current_hole])
distances[list(visited)] = np.inf
next_hole = np.argmin(distances)
path.append(next_hole)
visited.add(next_hole)
current_hole = next_hole
return path
# 执行贪心算法
greedy_path_indices = find_greedy_path(distance_matrix)
greedy_hole_sequence = [total_distance_df.index[i] for i in greedy_path_indices]
# 计算总距离
def calculate_total_distance_fixed(distance_matrix, hole_sequence, hole_to_index):
total_distance = 0
for i in range(len(hole_sequence) - 1):
total_distance += distance_matrix[hole_to_index[hole_sequence[i]], hole_to_index[hole_sequence[i+1]]]
total_distance += distance_matrix[hole_to_index[hole_sequence[-1]], hole_to_index[hole_sequence[0]]]
return total_distance
hole_to_index = {hole: index for index, hole in enumerate(total_distance_df.index)}
greedy_total_distance_fixed = calculate_total_distance_fixed(distance_matrix, greedy_hole_sequence, hole_to_index)
# 输出结果
print("打孔次序为：", greedy_hole_sequence)
#print("此路径总距离为：", greedy_total_distance_fixed)
print("总位移量为：", total_displacement.sum())
print("总旋转角度为：", total_rotation_angle.sum())
import numpy as np
from scipy.spatial.distance import squareform
# 加载位移量和旋转角度数据
displacement_df = pd.read_excel('相对位移量.xlsx', sheet_name=3)
rotation_angle_df = pd.read_excel('相对旋转角.xlsx', header=None)
rotation_angle_df.columns = displacement_df.columns[1:] # 从第二列开始复制列名，避免"Unnamed: 0"
rotation_angle_df.insert(0, 'Unnamed: 0', displacement_df['Unnamed: 0']) # 明确插入"Unnamed: 0"列
# 计算总距离、总位移量和总旋转角度
total_distance_df = displacement_df.set_index('Unnamed: 0') + rotation_angle_df.set_index('Unnamed: 0')
total_displacement = displacement_df.set_index('Unnamed: 0').sum(axis=1)
total_rotation_angle = rotation_angle_df.set_index('Unnamed: 0').sum(axis=1)
# 准备距离矩阵
distance_matrix = total_distance_df.to_numpy()
np.fill_diagonal(distance_matrix, np.inf)
# 定义贪心算法
def find_greedy_path(distance_matrix):
n = distance_matrix.shape[0]
current_hole = 0
path = [current_hole]
visited = set(path)
while len(visited) < n:
distances = np.copy(distance_matrix[current_hole])
distances[list(visited)] = np.inf
next_hole = np.argmin(distances)
path.append(next_hole)
visited.add(next_hole)
current_hole = next_hole
return path
# 执行贪心算法
greedy_path_indices = find_greedy_path(distance_matrix)
greedy_hole_sequence = [total_distance_df.index[i] for i in greedy_path_indices]
# 计算总距离
def calculate_total_distance_fixed(distance_matrix, hole_sequence, hole_to_index):
total_distance = 0
for i in range(len(hole_sequence) - 1):
total_distance += distance_matrix[hole_to_index[hole_sequence[i]], hole_to_index[hole_sequence[i+1]]]
total_distance += distance_matrix[hole_to_index[hole_sequence[-1]], hole_to_index[hole_sequence[0]]]
return total_distance
hole_to_index = {hole: index for index, hole in enumerate(total_distance_df.index)}
greedy_total_distance_fixed = calculate_total_distance_fixed(distance_matrix, greedy_hole_sequence, hole_to_index)
# 输出结果
print("打孔次序为：", greedy_hole_sequence)
#print("此路径总距离为：", greedy_total_distance_fixed)
print("总位移量为：", total_displacement.sum())
print("总旋转角度为：", total_rotation_angle.sum())
0 条评论