无人机送药问题（用Python求解）_数学建模无人机配送问题

目录

        题目

        问题分析

        变量说明

        模型建立

        用python代码实现模型求解

题目

问题分析

这是一个旅行商问题。一架无人机，从起点出发，需要依次经过50个不同的地点，最后返回起点。每个地点分别位于不同的坐标位置，无人机有且仅能经过一次。需要求得最短的遍历路径。

给公司编号为 0，目标依次编号为 1，2，…，50。

距离矩阵，其中表示表示两点的距离， = 0,1,…,50这里D为实对称矩阵。则问题是求一个从点0出发，走遍所有中间点，到达点0的一个最短路径。

变量说明

模型建立

用python代码实现模型求解

import numpy as np
import pandas as pd
from scipy import spatial
from matplotlib.ticker import FormatStrFormatter
import matplotlib.pyplot as plt
from sko.GA import GA_TSP
from sko.SA import SA_TSP
from sko.PSO import PSO_TSP
 
 
plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
 
 
def cal_total_distance(routine):
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])
# 目标函数
 
 
num_points = 51  # 地点个数 算上起点总共51个点
 
data = pd.read_excel("data.xlsx")
df_0 = pd.DataFrame({'x坐标': [0], 'y坐标': [0]})
data = pd.concat([df_0, data], axis=0, ignore_index=True)
 
points_coordinate = np.zeros((51, 2))
for i in range(0, 51):
    points_coordinate[i][0] = data.loc[i][0]
    points_coordinate[i][1] = data.loc[i][1]
 
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')
 
# 遗传算法
 
ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
 
best_points, best_distance = ga_tsp.run()
 
print('遗传算法求解的结果:')
print('最优路线:', best_points)
print('最短距离', best_distance)
 
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(ga_tsp.generation_best_Y)
ax[0].set_xlabel("迭代次数")
ax[0].set_ylabel("距离")
ax[0].set_title("遗传算法最优距离收敛图示")
ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
           marker='o', markerfacecolor='b', color='c', linestyle='-')
ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].set_xlabel("x坐标")
ax[1].set_ylabel("y坐标")
ax[1].set_title("遗传算法结果路线图示")
plt.tight_layout()
plt.show()
 
# 模拟退火算法
 
sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)
 
best_points, best_distance = sa_tsp.run()
 
print('模拟退火算法求解的结果:')
print('最优路线:', best_points)
print('最短距离', best_distance)
 
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
 
ax[0].plot(sa_tsp.best_y_history)
ax[0].set_xlabel("迭代次数")
ax[0].set_ylabel("距离")
ax[0].set_title("模拟退火算法最优距离收敛图示")
ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
           marker='o', markerfacecolor='b', color='c', linestyle='-')
ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].set_xlabel("x坐标")
ax[1].set_ylabel("y坐标")
ax[1].set_title("模拟退火算法结果路线图示")
plt.tight_layout()
plt.show()
 
# 粒子群算法
 
pso_tsp = PSO_TSP(func=cal_total_distance, n_dim=num_points, size_pop=200, max_iter=800, w=0.8, c1=0.1, c2=0.1)
 
best_points, best_distance = pso_tsp.run()
 
print('粒子群算法求解的结果:')
print('最优路线:', best_points)
print('最短距离', best_distance)
 
fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(pso_tsp.gbest_y_hist)
ax[0].set_xlabel("迭代次数")
ax[0].set_ylabel("距离")
ax[0].set_title("粒子群算法最优距离收敛图示")
ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
           marker='o', markerfacecolor='b', color='c', linestyle='-')
ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].set_xlabel("x坐标")
ax[1].set_ylabel("y坐标")
ax[1].set_title("粒子群算法结果路线图示")
plt.tight_layout()
plt.show()