基于遗传算法的物流无人机控制矫正研究

范鲁娜 （河南艺术职业学院 文化传播学院，河南 郑州 450002）

0 引 言

目前，自主事物被认为是最重要的战略技术之一。无人航空载具作为自主事物的一个分类，已经应用于物流、通信中继、救灾和环境监测等多个民用领域。其中，无人机在物流中的许多潜在应用被评估为技术上合理、操作上可行，并且比其他选择更具成本效益。亚马逊、达尔、京东等知名公司对物流无人机进行了系统的研究，旨在为包装运输提供可行、高效的无人机解决方案。在此类方案中，多架无人机能够在转运站装载包裹并将其运送到目标站点。为了得到一个无人机的解决方案，需要做出三个主要决策:无人机将飞行多少次；无人机将在飞行中携带什么包裹；飞行路线是什么。文章考虑了物流系统中的无人机调度问题，以最小化包裹运送任务的最大完成时间。在所考虑的问题中，有一组软件包和一组异构无人机可在转运站转运。异质无人机具有不同的飞行速度、载荷能力和最大飞行时间。包裹会被送到附近的目的地。所考虑的问题可以归结为一个特殊的车辆路径问题，可以被表述为混合整数线性规划。由于无人机的承载能力限制了它在一次飞行中运送包裹的数量，最大飞行时间限制了一次飞行的长度，因此无人机调度面临着新的挑战:无人机是异构的；装载在一架无人机上的包裹可能有不同的目的地，必须确定飞行中的停站顺序；由于包裹数量庞大，每架无人机可执行多次飞行，需要决定每架无人机的飞行顺序。由于无人机解决方案需要做出多种决策，所以为大规模的包裹递送任务开发更快的算法至关重要。之所以选择遗传算法来解决这个问题，是因为它能够很好地适应物流无人机的调度问题，并且具有全局优势搜索能力。证明了它对于可以作为所考虑问题的子问题是非常有效的。针对异构无人机的任务调度问题，建立了一种新的无人机调度问题模型；继承遗传算法的主要框架，集成了多个组件或策略，提出了新的编码/解码方法，开发了局部搜索算法以生成初始种群，并对遗传操作进行了精细设计；引入轮盘赌轮选择策略来分配包裹任务，减少算法的搜索空间。因此，该算法能较好地处理大规模包裹的调度问题；提出了合理的包装装载策略，以最大限度地发挥无人机的作用。这样，算法的效率也可以得到进一步的提高。

1 问题描述

文章研究了一个物流系统的无人机调度问题，操作一组无人机在一个社区中运送包裹。此处使用的表示法见表1。有一个车站作为转运站和站，，...，s作为配送柜分布在一个社区。任意两站之间的距离s用（s，s′）（，′=0，...，，≠′）表示。最初，所有需要交付的包={，，...，p}都放置在。分别用w和l（l∈{，...，s}）标记包裹p(=1，...，)的权和目的。这些包裹将通过一组传递到它们的目的地。所有无人机最初在0时可用。这些细胞是不均匀的。负载能力、飞行速度和最大飞行时间分别表示。物流系统负责为这些任务生成调度解决方案。所有任务交付的解决方案可以将某一区域物流无人机系统的工作流程表示为每架无人机的一组解决方案。执行的解决方案由f飞行组成，即S={S，=1，...，f}。在每次飞行中，无人机S，，u可能会在几个站点停留，并在每个站点卸下一些包裹。因此，飞行，也可以表示为一组止点，即S，={S，，|=1，...，γ，}。在u的第五次飞行中的停止s，，表示为一个三重，其中b，，是在t，，时在站点l卸下的包裹的集合。

表1 总承包裹和每日平均成本以及节约成本的百分比

在一个解决方案中，每个包裹p都应该分配给一个具有一定的完成时间(在文中也称为交付时间)，这个时间由装入的停止时间和卸载的停止时间决定。物流系统的目标是找到一个可行的解决方案，以最小的完成时间为所有任务。目的地有四个站点，分别为，，，，两架无人机u，u，负载能力=2kg，=5kg，平均速度=60km/h，v=48km/h，最大飞行时间=0.5h，=0.67h。最初保存在，kg，=1.1kg，=0.7kg，=2kg，=2.5kg。它们的目的地分别是=，=，=，=和=。五个站之间的距离矩阵(单位:公里)由方程(1)给出。其中项d(，′=0，...，4，≠′)表示两者之间的距离。

生成了两个可行的解和。在中，通过两个飞行传递和，在一个飞行中依次传递、和。描述是如何执行的。给出了解决方案是甘特表1，其中在两次飞行中提供、和，在一次飞行中提供和。的总完成时间为3.5分钟，而完成所有任务需要6分钟。因此，优于。根据上述描述和假设，问题被数学表述如下:

在这个模型中，，，，是一个二元决策变量，如果在的次飞行中的停止处传递，则取值为1，否则取0。目标函数(2)被定义为最小化交付任务的最大完成时间。给定飞行次数和传递的卸载停止，可以由方程(3)计算出来。方程(3)是计算，，的递推公式。，，0表示飞行的开始时间，它是由方程递归计算的。方程(1)表示无人机飞行的最后一站是转运站，即每架无人机都应该返回。约束(3)意味着没有包裹重量超过任何数值。约束(2)为保证包裹可以顺利抵达目的地。约束(1)限制一次飞行中装载的包裹总重量不能超过无人机的装载容量。约束(1)限制一次飞行的总时间不能超过无人机的最大飞行时间。最后，约束(1)确保每个包裹都被交付。

2 研究方法

基于遗传算法的目标的遗传算法框架是将最小化所有交付任务的完成时间作为主要考虑的问题。可以看出，其由三个主要组成部分组成:初始种群生成、适应性评估和遗传操作(选择、交叉和突变)。在介绍这些重要组成部分之前，可以详细地说明了染色体的编码方法。编码方法很重要，因为它能够使用一种简单的方法来给出问题的潜在解决方案。一个通用而简单的概念是用一系列的包裹来表示染色体。然而，它将导致一个巨大的搜索空间的产生，即！因此，采用二维矩阵表示染色体，该染色体由一系列组成，每个队列是一系列具有相同目的地的包裹。例如，下面是两个染色体1和2，其中同一行上的包裹具有相同的目的地。

矩阵中有行对应于个目的站。行的大小等于相应目的地的包裹数。为了进一步简化表示，染色体由一系列队列表示，也就是=[-1]，其中每个队列[]都指定了一个目的地和该目的地的一系列包裹。

2.1 解码方法和适应度

为了给出可行的解决方案，解码方法根据染色体建议的优先级分配包裹给无人机。给定一个染色体，解码方法排列优先级，其中无人机的优先级是由返回时间和载荷能力两个值组成的双重优先级。无人机的返回时间是无人机完成当前分配的任务并返回到0的时，最初设置为零。如果两架无人机有相同的载荷能力，则返回时间较早的那架优先级较高。轮盘赌轮选择策略迭代执行，直到所有任务都分配完毕。在迭代中，如果包裹队列不是空的，则选择它，然后中的一些包裹将被分配给具有最高优先级的无，要装载的包裹装由特定的装载方法决定。如果中的所有包裹都被分配给无人机，并且无人机中还有空间，则在下一个队列，直到没有更多的包裹可以装载到该无人机上。无人机的优先级在一次飞行满载后立即更新。本文探讨了三种加载方法:随机加载法；基于重量的加载法；基于背包的加载法。给定负载容量和包裹队列，从队列中随机选择包裹，直到不能再加载任何包裹，否则将超出负载容量。按照重量的递减顺序选择包裹，直到无法加载更多的包裹为止。执行两个步骤来加载包裹:选择顶部最重的包裹；根据给定的加载能力对这些包裹执行0-1的背包算法。在第二步中，将无人机作为背包并找到最重的一组包装在固定容量的背包中。

2.2 初始群体

每个染色体表示为一个包裹队列序列。实际上，当染色体被解码时，队列中包裹的顺序是由相应的解码方法决定的。因此，染色体可以简单地表示为一个目的站序列，其中每个站根据解码方法对应于一个特定的包裹序列。为了获得一个多样性和高质量的初始种群，采用了三种生成方法，即基于方法、局部搜索方法和随机方法。这些方法分别贡献了初始人口的20%，40%和40%。在={，，...，s}和距离矩阵的情况下，基于方法获得了访问每个站点一次的最短可能路径。该方法通过模拟退火过程从一个随机序列开始生成最短路径(第5～16行)。获得了最短路径上的站序列称为染色体。初始种群的20%是染色体的复制体初始种群方法用于生成初始总体的40%。在初始种群中，染色体被用作初始序列(第1行)。然后对进行解码，产生初始解(第6行)。以贪婪的方式迭代改进初始解(第4～10行)。当找不到更好的解决方案或迭代次数超过预定义的阈值4时，初始种群停止染色体操作的目标是找到最短完成时间的解，这个解与气体的完成时间相同，对应于初始种群得到的最佳解的序列称为染色体。每次独立运行的染色体操作将生成一个染色体。随机方法随机生成站点序列。

2.3 遗传操作

遗传操作包括选择、交叉和突变操作三种。在选择操作中，从当前群体中随机选择两条染色体，适应性越好，选择染色体的概率越高。假设（）是∈的适应值，是中最差的适应值。染色体被选中的概率是按公式来计算的。

3 结 论

文章提出了可以在现有资源上更便利地部署物流无人机分配系统，建立了多异构无人机调度问题的模型，针对该问题，提出了基于遗传算法的算法框架，是该算法框架的组成，并分别比较了两种方法。通过比较两种包裹的加载方法和现有的两种算法，说明基于遗传算法的算法框架在统计上优于其他比较算法。对于未来的研究，应该考虑到其他目标，评估调度算法，而不仅仅是总任务的完成时间，可以使最终的解决方案更加实用。