车辆与无人机混合编队的路径优化问题模型构建

摘  要

为保证人们可以在一些特大突发事件正常生活，在5G技术的基础上，采用“配送车辆+无人机”的配送模式将应急物资及时准确地配送到位。本文通过贪心算法、Dijkstra算法以及最小生成树Kruskal算法，运用C++编程，就题目所给条件进行综合分析，针对不同的要求给出相对应的数学模型和求解算法，求得了各点之间的最短单元路径及最优路线。

针对问题一，根据附件1的各地点之间的距离，运用C++编程，利用各地点之间的距离邻接表建立带权值无向图，结合Dijkstra算法以及最小生成树Kruskal算法求得各地点之间的最短单元路径以及路线，同时对比深度优先周游（DFS）算法和广度优先周游（BFS）算法的各点之间最短路径之和，制定最优的一次配送方案。

针对问题二，在问题一的基础上，根据附件2所给出的各地点之间的距离，运用C++编程，针对配送车辆和无人机分别通过各地点之间的距离邻接表建立带权值无向图，通过贪心算法，寻找满足在无人机单次最长飞行时间内完成折返更换电池的点位，以减轻配送车辆的路程任务为目的，确定无人机的最终配送路线，配送车辆在问题一的配送路线基础上，去除无人机配送的点位，确定最终配送路线。

针对问题三，在问题二的基础上，配送车辆的最大承重量变为500kg，由原本承重量大于各点当日物资需求数之和转变为小于，所以无人机的配送路线也随之做出改变，建立以减轻配送车辆的物资运送总重量为主，减轻配送车辆运送路程为辅的模型，运用贪心算法和穷举法，确定无人机的最优配送方案，结合题目的约束条件分析与单元最短路径分析，配送车辆需折返一次才能满足一趟配送任务的需求，最终确定最优的一趟配送任务路线。

针对问题四，根据题目所给示意图与附件3所给出的各地点之间的距离，结合特征工程对附件3的数据进行预处理，以题目的示意图为准，去除点位15与点位12间的距离数据，运用C++编程，针对配送车辆和无人机分别通过各地点之间的距离邻接表建立带权值无向图，并结合Dijkstra算法以及最小生成树Kruskal算法求得各地点之间的最短单元路径以及路线，得到配送车辆在18号点位无通路，需在与18号点位连通的且满足无人机一次折返更换电池的无人机路线点位中，选取一点作为其中的一个应急物资点。建立多约束条件的目标规划模型，通过贪心算法与穷举法，确定最优的两个应急物资点。

关键词 最小生成树Kruskal算法、Dijkstra算法、贪心算法、带权值无向图、C++

• 问题重述

在突发事件的应急事件中，配送应急物资是最为重要的任务之一。当突然发生严重自然灾害、突发性公共卫生事件时候，应急物资及时送达有物资需求的地点可以很大程度提高重特大事件后救援工作的效率，避免次生灾害进一步对生命和财产造成损失。科技水平的进步和5G网络的普及使得无人机应用范围变得广阔，为我们配送物质提供了更多的便利，“配送车辆+无人机”逐渐成为一种有效的配送方式，为了研究其如何尽快地完成物资配送任务，我们需要根据附件解决以下有关问题：

问题一：结合附件1，图中有14个地点，根据各地点之间的路线情况，目前所有的物资集中在第9个地点且配送车辆最大载重量为1000千克，只采取配送车辆，无人机不参加完成一次整体配送，求出完成一次整体配送的时间与周期，寻找最优的配送路线；

问题二：在问题一的基础上，再考虑实线是车辆和无人机都可以走的路线，虚线是只有无人机可以走的路线的限制条件，结合附件2，求出满足所有的约束条件且配送使用时间和路径最短的最优配送方案。

问题三：只改变配送车辆的最大载重量为500千克，其他条件与问题二不变，求出完成一次整体配送的最优配送方案。

问题四：结合附件3，图中有30个地点，计划设置两个应急物资集中地点且配送车辆最大载重量为500千克，采取“配送车辆+无人机”的配送模式，完成一次整体配送，确定两个应急物资集中地点的最佳位置。

• 问题分析

 2.1问题一的分析

根据附件1的各地点之间的距离，运用C++编程，利用各地点之间的距离邻接表建立带权值无向图，利用Dijkstra算法[1]和最小生成树Kruskal算法[2]-[4]求得各地点之间的最短单元路径以及路线，同时使用深度优先搜索算法和广度优先优先搜索算法[5]求解的各点之间最短路径之和，得到其对应的累加值，选择并确定配送车的最优路线，找出配送车最大承重量是否大于各地物资需求量之和，如果配送车最大承重量没有大于当日各地物资需求量之和，即可完成一次完整配送，求出完成一次整体配送的时间；否则，通过起始点的最短路径，考虑一次或多次折返而满足一次整体配送任务，给出对应的最优方案。

 2.2问题二的分析

在问题一的基础上，再考虑实线是车辆和无人机都可以走的路线，虚线是只有无人机可以走的路线的限制条件，此时，配送车辆的最大载重量为1000千克，根据附件2所给出的各地点之间的距离，运用C++编程，针对配送车辆和无人机分别通过各地点之间的距离邻接表建立带权值无向图，并结合Dijkstra算法以及最小生成树Kruskal算法求得各地点之间的最短单元路径以及路线，在满足配送车辆的最大载重量为1000千克和无人机完成一次飞行后可返回配送车辆换装电池，然后再次进行配送的条件下，提出最优方案。

 利用穷举法[6]求出无人机所有的满足约束条件（单次最长飞行时间、平均速度、单次最长飞行距离、最大承重量）且满足从起始点一趟折返条件的出度点位，从这些出度点位中，选取能够减轻配送车的路程任务且所能配送的总物资需求量尽量大的点位，并利用贪心算法确定无人机的配送路线。再对配送车最大承重量与无人机当日所配送的物资量是否大于当日各地物资需求量之和进行判断，如果配送车最大承重量与无人机当日所配送的物资量大于当日各地物资需求量之和，在问题一DFS的周游路线的基础上，去除无人机的配送点位，最终确定配送车的最终配送路线，求出完成一次整体配送的周期与时间，给出最优方案；

如果配送车最大承重量没有大于当日各地物资需求量之和，从这些出度点位中，选取能够减轻配送车的路程任务的点位，并利用贪心算法确定无人机的配送路线，再对配送车最大承重量与无人机当日所配送的物资量是否大于当日各地物资需求量之和进行判断，如果是在问题一DFS的周游路线的基础上，去除无人机的配送点位，最终确定配送车的最终配送路线，求出完成一次整体配送的周期与时间，给出最优方案；否则通过起始点位的最短路径，考虑一次或多次折返而满足一次整体配送任务，确定配送车的最终配送路线，求出完成一次整体配送的周期与时间，给出最优方案。

2.3问题三的分析

在问题二的基础上，再考虑配送车辆的最大载重量为500千克，其他条件不变，结合附件2，采取与问题二相同的分析思路，重复对应的步骤，对该问题进行求解。

  车辆的最大载重量从原本的1000kg转变为500kg，且无人车配送物资需求数状态从配送车辆的最大载重量小于各地点当日物资需求量总和转变为配送车辆的最大载重量小于各地点当日物资需求量总和，所以无人机所分配的出度应最多且运送的物资总量应达到最大，又无人机单次最长飞行距离的限制条件，每完成一次飞行后可返回配送车辆换装电池，所以满足起始点9号折返一次，建立合理的模型，对其满足要求的起始点进行选择，并计算其起始点的距离，找出各点当日物资需求数，通过贪心算法与穷举法并综合9号点位的最短路以及无人车的配送时间，确定无人机的路线。计算无人机每日最大分担物资配送需求量和配送车当日所需配送的总物资需求量，判断配送车一趟是否能完成全程的物资配送任务，计算其差额，并且从起始点9号位到其配送路线中距离权值尽量最小和各地点当日物资需求数大于差额。再结合问题二的深度优先周游DFS路线，可得最优符合该约束条件的点位，确认配送车最终的配送路线。计算无人机分担的配送重量、 总路程、配送时间，以及计算配送车当日所需的总物资需求量，进而确定最终配送总耗时。

2.4问题四的分析

根据题目所给示意图与附件3所给出的各地点之间的距离，结合特征工程对附件3的数据进行预处理，以题目的示意图为准，去除点位15与点位12间的距离数据，运用C++编程，针对配送车辆和无人机分别通过各地点之间的距离邻接表建立带权值无向图，并结合Dijkstra算法以及最小生成树Kruskal算法求得各地点之间的最短单元路径以及路线。

通过贪心算法与及穷举法，选择的两个点位应满足出度最多，且满足无人机折返条件（单次最长飞行时间、平均时速、最大承重量）的出度应最多，并且满足约束的出度的当日运送物资需求数之和应达到最大，且由于无人车到18号点位无通路，所以18号点位的满足无人机折返条件的相邻点位必须要有一个为应急物资调度点。在满足满足无人机折返条件（单次最长飞行时间、平均时速、最大承重量）的出度应最多，无人机的最大可承受物资运送量等约束条件下，寻找满足无人机折返条件出度数最多和无人机所能配送的物资总重量尽量最大的情况下，最终确定两个应急物资集中地点的最佳位置。

全文私聊！！！