基于模拟退火法和Floyd优化算法的农村应急物流配送路径研究

主国娜，唐小平

(贵州大学经济学院，贵州 贵阳 550025)

1 引言(Introduction)

2017 年，党的十九大报告首次提出实施乡村振兴战略，预计到2050 年实现乡村全面振兴[1]，然而乡村振兴的实现不仅依靠社会各阶层的帮助，还需要稳定和谐的发展环境。我国大部分地区受到季风气候的影响，并且早期农村居民因农业生产多将村落选在依山傍水的地区。相较于城镇建设，我国农村地区的基础设施还不够完善，因此泥石流、洪涝灾害在农村地区频发，既带来了农民流离失所问题，又对农村发展环境造成严重破坏。2020 年暴发的新型冠状病毒肺炎疫情，让人们感受到生命的脆弱，对那一段物资短缺、物价上涨的日子仍然记忆犹新。郑江淮等人[2]的研究结果表明，新型冠状病毒肺炎疫情对我国整体消费冲击较大，由新型冠状病毒肺炎疫情引发的需求转变将重塑未来的商业模式。由此可见，人们如何应对突发灾害显得尤为重要。国家如何保障受灾地区人民的正常生活？如何将突发灾害带来的损失降到最低？对这些问题的深入探讨有利于促进我国农村应急治理能力的提升。本文从应急管理恢复的角度出发，对农村应急物流最优路径问题进行研究。由于突发性灾害会影响部分交通路线的畅通，导致通信和电力中断，因此在规划最优路线问题上采用Floyd优化算法和模拟退火法对模型进行求解并寻找最优路径，实现在最短时间内对物资、人员和资金等需求的紧急保障。

2 问题描述(Problem description)

一些重大的突发状况可能会造成严重的道路阻断、损坏、封闭等很多想不到的情况，由此会对农村居民的日常生活造成影响。因此，为了保障农村居民的正常生活，将农村居民所需要的应急物资及时地运输到指定的位置是非常重要的。随着社会和科学技术的发展，在偏远山区和农村，因为空域划设相对简单、通信及电磁环境较好、安全成本相对较低，所以无人机技术在运输领域的优势得以充分发挥，通常采用“无人机+配送车辆”的模式进行物资的分配运输。

“配送车辆+无人机”的配送模式是指：在物资配送过程中，配送车辆对某地方进行配送的同时，无人机也可向周围可行的地点进行配送，并于配送完成后返回配送车辆重新装载物资、更换电池，这种模式方便快捷，大大提升了配送效率。在农村应急物资配送过程中，配送车辆可在某地点施放无人机，再前往其他地点配送。配送车辆可先于无人机到达某地点等待接收无人机，也可比无人机晚到某地点再回收无人机。无人机在一次飞行过程中可对一个地点进行配送，也可根据实际情况对多个地点进行配送。无人机完成一次飞行后可返回配送车辆换装电池，然后再次进行配送。配送车辆和无人机合作完成所有地点的应急物资配送任务后，最后都返回出发地点，即完成一次整体配送。为了尽快完成物资配送任务，需要解决下面假设问题。

图1中实线代表车辆和无人机都可以走的路线，虚线代表只有无人机可以走的路线，各点之间路线的距离在图1中已标出。农村各应急地点所需应急物资需求量如表1所示，应急物资集中在第9 个地点，配送车辆的最大载重量为1,000 kg，采取“配送车辆+无人机”的配送模式。为将问题抽象为模型，提出以下对假设的约束。

表1 农村各应急地点所需应急物资需求量Tab.1 Demand for emergency materials at various emergency sites in rural areas

图1 各地点连接示意图Fig.1 Schematic diagram of connection of each location

(1)假设5 G网络可以覆盖整个配送区域。

(2)忽略无人机自身重量的影响，无人机的最大载重量为50 kg；配送车辆行驶平均速度为50 km/h，无人机飞行平均速度为75 km/h；无人机单次最长飞行时间为70 min。

(3)每个应急物资集中地点限一辆配送车辆，只能携带一架无人机。

3 模型建立与求解(Model building and solving)

3.1 Floyd优化算法

对图1中给出的14 个地点进行坐标的矩阵化，本文使用Floyd优化算法实现。Floyd优化算法也称插点法，是一种应用于寻求给定的加权图中顶点之间最短路径的算法，可以在具有正或负边缘权重(无负周期)的加权图中找到最短路径；其目的是为了找出从点i到点j之间的最短路径[3-4]。

该算法的具体内容如下：任意两节点i与j之间最短路径一般有两种可能，第一种是直接从i到j，第二种是从i经过多个节点k后到j。用Dis(i,j)表示顶点i与j之间的直接距离，通过插点法判断与发现顶点i与j之间最短的距离，插入点k以后，若有Dis(i,k) +Dis(k,j)

3.2 物资运输的数学模型

若是要对物资配送进行整体分析，则需要用到模拟退火算法。模拟退火算法来源于固体退火原理，即将固体加温至充分高的温度，再让其慢慢冷却。加温时，固体的内能增大；降温时，固体的内能减小。当降温到常温时，固体的内能达到最小，此时模拟退火算法结束[5-6]。

根据Metropolis准则描述退火过程，假设材料在状态i之下的能量为E(i),那么材料在温度T时从状态i进入状态j就遵循如下规律。

如果E(j) >E(i)，则状态转换为以下概率被接受：

式(1)中，K为物理学中的玻尔兹曼常数；T为材料温度。

为了找出运输物资最优的路径，即所需要的时间最短，将物理学中的模拟退火法的思想应用到物资运输中，可以得到模拟退火法的最优路径[7-9]。

在参数Ci下，经历过很多次转移之后，减小数值，从而得到C i

需要注意的是，在每一个Ci下，每一次得到新状态的x(k+1)都是完全依赖上一个x(k)的，与前面的x(0),…,x(k-1)都没有关系。在数值Ci下的平衡状态分布式如下：

当数值Ci减小到0时，xi的分布如下：

如果每一次的数值减小都很缓慢，在每一个数值下都有充足的状态转移，使之在每一个数值到达平衡，则全局的最优解就会以概率1被找出，所以采用模拟退火法可以找到全局最优[10]。应用于整个过程的算法流程图如图2所示。

图2 模拟退火算法流程图Fig.2 Flow chart of simulated annealing algorithm

3.2.1 无人机与车辆运输物资配送数学模型

当无人机的飞行速度明显优于车辆运输时，只要满足无人机的配送条件，就可以直接用无人机进行配送。我们将无人机的飞行路线之间的距离进行矩阵化，然后针对每一条路线中所需要的物资，判断无人机可以连续配送多少个地点。无人机配送完成一个地点之后就会达到下一个地点等待车辆，或运输物资车辆先到就地等待无人机，同时还需考虑无人机的航程和续航时间，无人机和运输物资车辆必须都到达地点后才可以转向下一个地点。

使用无人机配送的地点所需要的数学模型如下：

式(6)中，N表示所有地点的集合；xi,j表示车辆是否经过从i点到j点的路径；yi,j表示无人机是否从i点经过j点的路径。

其中，除去无人机配送的自循环公式如下：

判断是否由车辆配送物资的公式如下：

式(8)中，si表示i地点是否由车辆配送；O表示起始地点。

其中，除去子回路的公式：

无人机配送的流入点和流出点，要符合车辆路径先后关系的公式：

式(10)中，M表示可以用无人机配送物资的地点，k表示地点。

符合每一辆车只有一个无人机的条件公式：

最后的目标函数：

式(12)中，di,j表示地点i到地点j的距离；c表示无人机配送的距离成本系数。

3.2.2 模型运行结果

根据上文给出的数学模型及其分析，得到无人机与车辆运输物资的最优路径如图3所示。从图3可以得出，车辆运输的最优路径为从第9 个地点出发，先经过第8 个地点到第7 个地点，再到第5 个地点，由第5 个地点到第2 个地点再到第5 个地点，由第5 个地点到第6 个地点再到第10 个地点，最后回到原点第9 个地点，即地点9→地点8→地点7→地点5→地点2→地点5→地点6→地点10→地点9。同样，可以得出无人机的路径依次为地点9→地点13→地点8(无人机在该地点更换电池)→地点12→地点7(无人机在该地点更换电池)→地点11→地点1→地点2→地点6→地点3→地点4→地点10(无人机在该地点更换电池)→地点14→地点9。车辆的最优路径总路程为289 km，整个过程用的最少时间为6.32 h。

图3 模型运行结果的最优路径Fig.3 Optimal path of model running results

从模型的运行结果可以得出，最短配送时间为6.28 h。考虑无人机的续航问题，对路线进行解读：无人机单块电池续的最远飞行距离为87.5 km，所以运输途中需要更换电池，车辆从地点9→地点8的同时，无人机从地点9→地点13→地点8，无人机可以在地点8更换电池；车辆从地点8→地点7的同时，无人机从地点8→地点12→地点7，无人机可以在地点7更换电池；车辆从地点7→地点5→地点2的同时，无人机从地点7→地点11→地点1→地点2，无人机可以在地点2更换电池，然后车辆载着无人机一起从地点2→地点5→地点6；车辆从地点6→地点10的同时，无人机从地点6→地点3→地点4→地点10，无人机可以在地点10更换电池；车辆从地点10→地点9的同时，无人机从地点10→地点14→地点9。

由图4可以非常清楚地看出车辆和无人机运输物资的具体路径，从而为选择路径最短的配送方案提供支持。

图4 车辆、无人机运输最优路径Fig.4 Optimal transportation path of delivery vehicle and UAV

4 结论(Conclusion)

在应急的恢复方面，学术界认为保证物资的供应是关键，因此当农村地区突发灾害时，为了保证农村居民的正常生活，将应急物资及时准确地配送到位尤为重要。随着科学技术的迅猛发展，无人机的应用越来越广泛，“配送车辆+无人机”的配送模式逐渐成为一种便捷且高效的配送方式。本文旨在通过研究在不同约束条件下“配送车辆+无人机”的组合方案，侧重考虑物流效率选择最优路径进行应急物资配送，进一步保障受灾农民的人身、财产安全。