当前位置:   article > 正文

数学-建模———A 农村公交与异构无人机协同配送优化_只考虑使用a类无人机,请给出公交与无人机协同配送方案,使总费用最小;要求给出

只考虑使用a类无人机,请给出公交与无人机协同配送方案,使总费用最小;要求给出

8b6ec98daa3b4fe2b8e64d38abff958c.gif

目录

1.题目

1.总体分析

1.模型目标

2.模型变量

1.公交车路线变量:

2.无人机变量:

3.需求点变量:

3.约束条件

公交车的容量限制:

无人机的容量限制:

公交车的站点覆盖:

无人机的任务分配:

任务完成后返回起始站:

时间约束:

4.目标函数

5.模型求解方法

3.问题1:只考虑使用A类无人机的协同配送方案

1.目标函数

2.约束条件

无人机的容量限制:

2.无人机的飞行距离限制:

3.需求点的覆盖:

4.公交车站点是否有无人机任务:

5.任务分配的二元约束

4.问题2:三种类型无人机均可使用时的最小费用协同配送方案

1.目标函数

2.约束条件:

每个需求点的需求必须满足:

​编辑

无人机的飞行距离不超过最大飞行距离:

无人机的载重不超过最大载重:

无人机必须返回到起始站:

5.问题3

距离矩阵计算

无人机任务分配

总费用计算

6.代码实现


1.题目

A题 农村公交与异构无人机协同配送优化

农村地区因其复杂多变的地形、稀疏的道路网络以及分散的配送点,传统配送方式效率低下,成本高昂,难以满足日益增长的配送需求。随着无人机技术迅猛发展和在物流领域的广泛应用,一种全新的配送模式应运而生——农村公交与异构无人机协同配送模式。

农村公交作为地面交通系统的重要组成部分,其覆盖范围广、定时定点运行且成本相对较低,为无人机提供了理想的地面支撑。通过将无人机与农村公交相结合,可以充分利用两者的优势,实现高效协同配送。具体而言,农村公交负责将无人机和货物运送至各个公交站点,这些站点既是无人机的起降点,也是货物的转运中心。无人机则利用自身的空中优势,从公交站点起飞,快速准确地完成到具体配送点的配送任务。

187e13b4ebeb4c7a9ffc298c58f4a58b.png    1e4d824e0861439b8522b4780e3f3153.png

为提升配送效率和灵活性,异构无人机的使用显得尤为重要。异构无人机具有不同的飞行特性、载荷能力和速度,能够根据不同配送需求进行灵活的任务分配。通过合理搭配和调度不同类型的异构无人机,可以实现对复杂多变配送需求的精准应对,提高整体配送效率。

实施同时取送货服务也更能体现农村物流的独特需求。在一次飞行中,无人机能够兼顾多个配送点的送货与取货任务,从而显著提升配送效率,减少周转时间。通过精心策划飞行路径和合理分配任务,能够有效减少无人机的使用次数和飞行频率。

农村公交装载货物和无人机,从配送中心出发,按公交固定路线及公交站点行驶。根据客户需求和无人机性能,精准分配无人机类型及配送任务。无人机在接近客户点的公交站点起飞,按优化路径执行取送货任务,确保高效完成。完成任务后,无人机返回最近站点,搭乘下一次经过该站点的公交进行迅速换电后继续服务该站点附近客户需求点或搭载公交到达其他站点服务其周围需求点,无人机没有任务后搭载公交回到配送中心。整个过程中,无人机与农村公交紧密协作,循环执行配送任务,直至所有任务完成。通过这种模式,能够充分利用地面和空中的优势,提高配送效率,降低成本,满足农村地区日益增长的配送需求。

假设无人机可以在公交站点等待下一班次的公交车,若公交站点处有返回的无人机需要装货,公交车在该站点逗留5分钟时间用于更换无人机电池(不需要充电)及装载货物。无人机产生的费用包括两部分,一是固定费用,只要使用就会产生,与无人机类型有关,二是运输费用,取决于无人机类型及运输过程的飞行里程(从站点起飞至回到站点的飞行里程)。此外,需求点的任务不能拆分,一辆公交车最多可携带两架无人机,每天任务完成后无人机必须回到起始站,不考虑客户点的时间窗,不考虑道路的随机性堵车,公交车的行驶速度为35公里/小时。

请根据附件所给数据解决以下几个问题:

问题1 只考虑使用A类无人机,请给出公交与无人机协同配送方案,使总费用最小;要求给出具体的飞行路径及时刻表。

问题2 三种类型无人机均可使用时,请给出最小费用的协同配送方案。

问题3 在问题2的基础上,如果每个需求点有取货的需求,且取货能获得一定的收入(每公斤0.5元),请给出最佳配送方案。

1.总体分析

1.模型目标

  1. 最小化配送总成本:包括无人机的固定费用和运输费用。
  2. 最小化配送总时间:包括公交车运输时间和无人机飞行时间。

2.模型变量

1.公交车路线变量

6e427252bd10403295fd60460c626ff7.png

2.无人机变量

  • b34efd7fcf8a4731b43ee7d6a35f1659.png

3.需求点变量

f3e898e97cc84a4c99e31cd7390c8667.png

3.约束条件

  1. 公交车的容量限制

    ece7c5ab050d40338538af1c9b0f20b9.png

  2. 无人机的容量限制

    7be72c1850b741258ba99d8545accb2e.png

  3. 公交车的站点覆盖

    a058fb9c67054d8e99df1c1786443259.png

  4. 无人机的任务分配

    bb72b991bccc4b3d9f2c127f10b62dea.png

  5. 任务完成后返回起始站

    91d6a256c005422d891bd9495d488c5b.png

  6. 时间约束

    2dd1acb2bff8437e93bbd684c6a115d0.png

4.目标函数

890c2a0feccc4419833fbaa8c34cca5e.png

5.模型求解方法

  1. 混合整数线性规划(MILP):可以通过MILP来求解该优化问题,适合于中小规模问题。
  2. 启发式算法:如遗传算法、模拟退火算法等,适合于大规模问题。

3.问题1:只考虑使用A类无人机的协同配送方案

1.目标函数

最小化总费用:包括无人机的固定费用和运输费用。

设:84b939e2de634741aad16f12f19db037.png

2.约束条件

  1. 无人机的容量限制

3e73d0d3d7274368886055d732b6f1d3.png

2.无人机的飞行距离限制

092441b615fc4dc28a08f90562fe290b.png

3.需求点的覆盖

acb4e8e0ae57452f989f0c04d5796796.png

4.公交车站点是否有无人机任务

807bdb7a20784c25adaa9892fe3da861.png

5.任务分配的二元约束

b11bec6633bb4bac8e532b5586cf8680.png

4.问题2:三种类型无人机均可使用时的最小费用协同配送方案

1.目标函数

最小化总费用:包括各类无人机的固定费用和运输费用。

设:56cec9b2341a4d6383c5a36e3bbaeb18.png

2.约束条件:

  1. 每个需求点的需求必须满足:

    982914e65e2b4eada0f249cdef0766c2.png

  2. 无人机的飞行距离不超过最大飞行距离:

    fd1d5bf12e4343898d12b781a119665b.png

  3. 无人机的载重不超过最大载重:

    9aed3bd900b44624830d19b24c0f1f94.png

  4. 无人机必须返回到起始站:

    f4b35b0a3e7642b99bfaf7e9317443ce.png

5.问题3

8c744440d5bd41aca3894458553f2a06.png

78a08846c3da413fb18b8168c5fd3454.png

距离矩阵计算

使用Haversine公式计算每个公交站点和每个需求点之间的距离,并存储在距离矩阵中。

无人机任务分配

根据无人机的参数和需求点的需求量,选择最合适的无人机完成每个需求点的配送任务,具体步骤如下:

  1. 遍历每个需求点
    • 初始化最小成本为无穷大。
    • 遍历每个站点,计算站点与需求点之间的距离。
    • 遍历每种无人机,检查该无人机是否能满足需求点的需求量和最大飞行距离。
    • 计算配送成本,选择成本最小的无人机和站点。
  2. 记录分配结果:将每个需求点的最佳无人机选择、起飞站点和总成本记录下来。

总费用计算

计算所有配送任务的总费用,输出最小总费用。

6.代码实现

  1. import pandas as pd
  2. import numpy as np
  3. import matplotlib.pyplot as plt
  4. from matplotlib.font_manager import FontProperties
  5. from itertools import combinations
  6. # 设置中文字体路径(请根据实际情况修改路径)
  7. font_path = 'C:/Windows/Fonts/simhei.ttf' # 请替换为实际的字体路径
  8. font = FontProperties(fname=font_path)
  9. # 更新无人机信息
  10. D_max_A = 27 # 最大飞行距离 (km)
  11. Q_max_A = 9 # 最大载重 (kg)
  12. C_fixed_A = 80 # 固定费用 (元/天)
  13. C_per_km_A = 0.8 # 每公里费用 (元/km)
  14. drone_speed = 16.7 / 3.6 # 无人机速度 (km/h), 由 m/s 转为 km/h
  15. # 公交站点数据
  16. stations_data = pd.DataFrame({
  17. 'Station_ID': [1, 2, 3, 4, 5, 6, 7, 8, 9],
  18. 'Longitude': [110.125713, 110.08442, 110.029866, 109.962839, 109.956003, 109.920425, 109.839046, 109.823329, 109.767127],
  19. 'Latitude': [32.815024, 32.771676, 32.748994, 32.743622, 32.812194, 32.856136, 32.860495, 32.847468, 32.807855]
  20. })
  21. # 需求点数据
  22. demands_data = pd.DataFrame({
  23. 'Demand_ID': range(1, 51),
  24. 'Longitude': [
  25. 110.1053385, 110.1147032, 110.0862574, 110.0435344, 110.0575508,
  26. 110.0386243, 110.0115086, 110.0390602, 110.0246454, 110.0575847,
  27. 109.9456331, 109.9612274, 109.94592, 109.9316682, 109.9245376,
  28. 109.7087533, 109.7748005, 109.7475891, 109.7534532, 109.783015,
  29. 109.7410728, 109.7554844, 109.7147417, 109.8807093, 109.8070677,
  30. 109.9054481, 109.8954509, 109.8979229, 109.8942179, 109.8610985,
  31. 109.8744682, 109.8338804, 109.870924, 109.8292467, 109.8711312,
  32. 109.8813363, 109.978788, 109.8166563, 109.8151216, 109.885638,
  33. 109.9890984, 109.9647812, 109.9303732, 109.9401099, 109.944496,
  34. 109.979708, 109.976757, 109.94999, 109.973673, 109.967765
  35. ],
  36. 'Latitude': [
  37. 32.77881526, 32.75599834, 32.74905239, 32.74275416, 32.76712584,
  38. 32.70855831, 32.72619993, 32.73965997, 32.72360718, 32.76553658,
  39. 32.7526657, 32.72286471, 32.70899877, 32.73848444, 32.70740885,
  40. 32.7815564, 32.80016336, 32.80903496, 32.85129032, 32.82296929,
  41. 32.82914197, 32.80581363, 32.79995734, 32.89696579, 32.79622985,
  42. 32.89437141, 32.86724756, 32.83444574, 32.83224374, 32.90687042,
  43. 32.89939698, 32.85616627, 32.848223, 32.83825122, 32.88979101,
  44. 32.8642824, 32.75943454, 32.8096699, 32.82822489, 32.84032485,
  45. 32.80854774, 32.80993619, 32.78956582, 32.85264625, 32.802178,
  46. 32.817449, 32.811064, 32.795207, 32.746858, 32.820998
  47. ],
  48. 'Demand_kg': [3, 4, 2, 0, 8, 7, 4, 9, 10, 6, 7, 12, 3, 5, 6, 5, 3, 13, 12, 3,
  49. 14, 10, 4, 34, 6, 6, 3, 4, 20, 5, 6, 5, 3, 15, 2, 6, 3, 4, 3, 2,
  50. 6, 5, 9, 3, 3, 4, 6, 4, 4, 0]
  51. })
  52. # 计算两个点之间的距离(Haversine公式)
  53. def haversine(lon1, lat1, lon2, lat2):
  54. lon1, lat1, lon2, lat2 = map(np.radians, [lon1, lat1, lon2, lat2])
  55. dlon = lon2 - lon1
  56. dlat = lat2 - lat1
  57. a = np.sin(dlat / 2) ** 2 + np.cos(lat1) * np.cos(lat2) * np.sin(dlon / 2) ** 2
  58. c = 2 * np.arcsin(np.sqrt(a))
  59. r = 6371 # 地球平均半径(公里)
  60. return c * r
  61. # 将公交站点和需求点的经纬度转换为NumPy数组
  62. stations_lons = stations_data['Longitude'].values
  63. stations_lats = stations_data['Latitude'].values
  64. demands_lons = demands_data['Longitude'].values
  65. demands_lats = demands_data['Latitude'].values
  66. # 利用广播机制计算所有公交站点到所有需求点的距离
  67. stations_lons_matrix, demands_lons_matrix = np.meshgrid(stations_lons, demands_lons)
  68. stations_lats_matrix, demands_lats_matrix = np.meshgrid(stations_lats, demands_lats)
  69. distances_matrix = haversine(stations_lons_matrix, stations_lats_matrix, demands_lons_matrix, demands_lats_matrix)
  70. # 将距离矩阵转换为字典形式
  71. distances = {(stations_data['Station_ID'][i], demands_data['Demand_ID'][j]): distances_matrix[j, i]
  72. for i in range(len(stations_data)) for j in range(len(demands_data))}
  73. # 发车时间表
  74. bus_schedule = {
  75. '白河至仓上': [6.67, 8.5, 9, 11, 14, 16.5],
  76. '仓上至白河': [6, 7.33, 8.83, 11, 14, 15.83]
  77. }
  78. # 贪心算法优化无人机使用量
  79. def optimize_drone_usage():
  80. total_cost = 0
  81. drone_tasks = []
  82. remaining_demands = set(demands_data['Demand_ID'])
  83. while remaining_demands:
  84. best_station = None
  85. best_combination = None
  86. best_combination_cost = float('inf')
  87. for station_id in stations_data['Station_ID']:
  88. valid_demands = [d for d in remaining_demands if distances[(station_id, d)] <= D_max_A and demands_data.loc[demands_data['Demand_ID'] == d, 'Demand_kg'].values[0] <= Q_max_A]
  89. for i in range(1, len(valid_demands) + 1):
  90. for combination in combinations(valid_demands, i):
  91. total_weight = sum(demands_data.loc[demands_data['Demand_ID'].isin(combination), 'Demand_kg'])
  92. if total_weight > Q_max_A:
  93. continue
  94. combination_cost = C_fixed_A + 2 * C_per_km_A * sum(distances[(station_id, d)] for d in combination)
  95. if combination_cost < best_combination_cost:
  96. best_combination = combination
  97. best_station = station_id
  98. best_combination_cost = combination_cost
  99. if best_combination is None:
  100. break
  101. drone_tasks.append((best_station, best_combination, best_combination_cost))
  102. total_cost += best_combination_cost
  103. remaining_demands -= set(best_combination)
  104. return total_cost, drone_tasks
  105. total_cost, drone_tasks = optimize_drone_usage()
  106. # 打印最优结果
  107. print(f"最小总费用:{total_cost:.2f} 元")
  108. print("无人机任务分配:")
  109. for i, (station, tasks, cost) in enumerate(drone_tasks):
  110. print(f"无人机 {i + 1}:")
  111. print(f" 从站点 {station} 起飞")
  112. for demand_id in tasks:
  113. demand_weight = demands_data.loc[demands_data['Demand_ID'] == demand_id, 'Demand_kg'].values[0]
  114. print(f" 需求点 {demand_id},需求重量: {demand_weight} kg")
  115. print(f" 总费用: {cost:.2f} 元")
  116. print("-----")
  117. # 可视化飞行路径
  118. def visualize_flight_paths():
  119. fig, ax = plt.subplots()
  120. # 绘制公交站点
  121. ax.scatter(stations_data['Longitude'], stations_data['Latitude'], c='blue', label='公交站点')
  122. # 绘制需求点
  123. ax.scatter(demands_data['Longitude'], demands_data['Latitude'], c='red', label='需求点')
  124. # 绘制飞行路径
  125. for station, tasks, cost in drone_tasks:
  126. station_coords = stations_data[stations_data['Station_ID'] == station][['Longitude', 'Latitude']].values[0]
  127. for demand_id in tasks:
  128. demand_coords = demands_data[demands_data['Demand_ID'] == demand_id][['Longitude', 'Latitude']].values[0]
  129. ax.plot([station_coords[0], demand_coords[0]], [station_coords[1], demand_coords[1]], c='green')
  130. ax.legend(prop=font)
  131. ax.set_xlabel('经度', fontproperties=font)
  132. ax.set_ylabel('纬度', fontproperties=font)
  133. ax.set_title('飞行路径', fontproperties=font)
  134. plt.show()
  135. visualize_flight_paths()

 8fd0b8c145c64e64b7a574c535696158.png

飞行路径和时刻表:
从公交站点(110.08442, 32.771676)到需求点(110.1053385, 32.77881526)的飞行距离为2.45km,费用为1.96元
从公交站点(110.08442, 32.771676)到需求点(110.1147032, 32.75599834)的飞行距离为3.79km,费用为3.03元
从公交站点(110.08442, 32.771676)到需求点(110.0862574, 32.74905239)的飞行距离为2.52km,费用为2.02元
从公交站点(110.08442, 32.771676)到需求点(110.0575508, 32.76712584)的飞行距离为3.02km,费用为2.42元
从公交站点(110.029866, 32.748994)到需求点(110.0386243, 32.70855831)的飞行距离为4.59km,费用为3.67元
从公交站点(110.029866, 32.748994)到需求点(110.0115086, 32.72619993)的飞行距离为3.25km,费用为2.60元
从公交站点(110.029866, 32.748994)到需求点(110.0390602, 32.73965997)的飞行距离为1.45km,费用为1.16元
从公交站点(110.029866, 32.748994)到需求点(110.0246454, 32.72360718)的飞行距离为2.88km,费用为2.30元
从公交站点(110.08442, 32.771676)到需求点(110.0575847, 32.76553658)的飞行距离为3.06km,费用为2.44元
从公交站点(109.962839, 32.743622)到需求点(109.9456331, 32.7526657)的飞行距离为2.16km,费用为1.73元
从公交站点(109.962839, 32.743622)到需求点(109.9612274, 32.72286471)的飞行距离为2.31km,费用为1.85元
从公交站点(109.962839, 32.743622)到需求点(109.94592, 32.70899877)的飞行距离为4.28km,费用为3.42元
从公交站点(109.962839, 32.743622)到需求点(109.9316682, 32.73848444)的飞行距离为3.51km,费用为2.81元
从公交站点(109.962839, 32.743622)到需求点(109.9245376, 32.70740885)的飞行距离为5.85km,费用为4.68元
从公交站点(109.767127, 32.807855)到需求点(109.7087533, 32.7815564)的飞行距离为7.11km,费用为5.69元
从公交站点(109.767127, 32.807855)到需求点(109.7748005, 32.80016336)的飞行距离为1.21km,费用为0.96元
从公交站点(109.767127, 32.807855)到需求点(109.7475891, 32.80903496)的飞行距离为2.17km,费用为1.74元
从公交站点(109.767127, 32.807855)到需求点(109.7534532, 32.85129032)的飞行距离为5.05km,费用为4.04元
从公交站点(109.767127, 32.807855)到需求点(109.783015, 32.82296929)的飞行距离为2.43km,费用为1.95元
从公交站点(109.767127, 32.807855)到需求点(109.7410728, 32.82914197)的飞行距离为3.73km,费用为2.99元
从公交站点(109.767127, 32.807855)到需求点(109.7554844, 32.80581363)的飞行距离为1.31km,费用为1.05元
从公交站点(109.767127, 32.807855)到需求点(109.7147417, 32.79995734)的飞行距离为5.88km,费用为4.70元
从公交站点(109.839046, 32.860495)到需求点(109.8807093, 32.89696579)的飞行距离为6.15km,费用为4.92元
从公交站点(109.767127, 32.807855)到需求点(109.8070677, 32.79622985)的飞行距离为4.62km,费用为3.69元
从公交站点(109.920425, 32.856136)到需求点(109.9054481, 32.89437141)的飞行距离为4.56km,费用为3.65元
从公交站点(109.920425, 32.856136)到需求点(109.8954509, 32.86724756)的飞行距离为3.03km,费用为2.43元
从公交站点(109.920425, 32.856136)到需求点(109.8979229, 32.83444574)的飞行距离为3.47km,费用为2.78元
从公交站点(109.920425, 32.856136)到需求点(109.8942179, 32.83224374)的飞行距离为3.94km,费用为3.15元
从公交站点(109.839046, 32.860495)到需求点(109.8610985, 32.90687042)的飞行距离为5.70km,费用为4.56元
从公交站点(109.839046, 32.860495)到需求点(109.8744682, 32.89939698)的飞行距离为5.84km,费用为4.67元
从公交站点(109.839046, 32.860495)到需求点(109.8338804, 32.85616627)的飞行距离为0.75km,费用为0.60元
从公交站点(109.839046, 32.860495)到需求点(109.870924, 32.848223)的飞行距离为3.79km,费用为3.03元
从公交站点(109.823329, 32.847468)到需求点(109.8292467, 32.83825122)的飞行距离为1.22km,费用为0.97元
从公交站点(109.839046, 32.860495)到需求点(109.8711312, 32.88979101)的飞行距离为4.82km,费用为3.86元
从公交站点(109.920425, 32.856136)到需求点(109.8813363, 32.8642824)的飞行距离为4.43km,费用为3.55元
从公交站点(109.962839, 32.743622)到需求点(109.978788, 32.75943454)的飞行距离为2.49km,费用为1.99元
从公交站点(109.823329, 32.847468)到需求点(109.8166563, 32.8096699)的飞行距离为4.26km,费用为3.41元
从公交站点(109.823329, 32.847468)到需求点(109.8151216, 32.82822489)的飞行距离为2.32km,费用为1.86元
从公交站点(109.920425, 32.856136)到需求点(109.885638, 32.84032485)的飞行距离为4.24km,费用为3.39元
从公交站点(109.956003, 32.812194)到需求点(109.9890984, 32.80854774)的飞行距离为3.70km,费用为2.96元
从公交站点(109.956003, 32.812194)到需求点(109.9647812, 32.80993619)的飞行距离为1.01km,费用为0.80元
从公交站点(109.956003, 32.812194)到需求点(109.9303732, 32.78956582)的飞行距离为3.80km,费用为3.04元
从公交站点(109.920425, 32.856136)到需求点(109.9401099, 32.85264625)的飞行距离为2.22km,费用为1.78元
从公交站点(109.956003, 32.812194)到需求点(109.944496, 32.802178)的飞行距离为1.69km,费用为1.35元
从公交站点(109.956003, 32.812194)到需求点(109.979708, 32.817449)的飞行距离为2.70km,费用为2.16元
从公交站点(109.956003, 32.812194)到需求点(109.976757, 32.811064)的飞行距离为2.31km,费用为1.85元
从公交站点(109.956003, 32.812194)到需求点(109.94999, 32.795207)的飞行距离为2.00km,费用为1.60元
从公交站点(109.962839, 32.743622)到需求点(109.973673, 32.746858)的飞行距离为1.26km,费用为1.00元

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/673296
推荐阅读
相关标签
  

闽ICP备14008679号