基于GA算法解决绿化喷洒车作业任务优化问题

2020-09-10 12:15席禹唐健

新教育论坛 2020年10期

席禹　唐健

摘要：本文研究的是喷洒车的最短喷洒时间问题，主要采用基于Floyd算法的GA模型。在任务一中，我们计算出每辆喷洒车完成一个作业点所需要的最短时间。首先，对D1一直到F60的节点进行编号，利用附件一计算出各个节点之间的距离，并利用MATLAB得出地图。接着，利用各个节点的连接关系得出连接矩阵。由于A、B两类车在不同类型的路径的速度不同，因而对距离进行加权，统一处理。以A车通过普通道路的速度作为权重1，计算出A在主干道;B在普通道路、主干道上对应的权重分别为3/4;9/10;3/2"最后，通过Floyd算法，寻找各自10条最短路径，并得出其中的最长作业完成时间，即为最终的完成任务最短用时。通过计算，得出最短时长为2.83h。在任务二中，我们计算出每辆车完成两个作业点所需要的最短时间。首先，通过分析所有点的排列情况，发现数据过于庞大，不能进行遍历处理，因而只能选用局部最优解。接着，把喷洒车的全部路程分）为三个阶段，从七点到第一个作业点，第一个作业点到给水点，给水点到第二个作业点。最后，通过建立目标函数：完成两个作业点所需要的最短时间，和相应的约束条件：（1）每辆喷洒车在第一次喷洒作业完成后一定要到补水站;（2）起点的喷洒车的数量、型号一定。最后，通过GA算法，交叉变异等一系列的操作，计算出喷洒车完成两个作业点所需的最短时长7.25h"在任务三中，我们计算完成所有作业点所需要的最短时间"首先，我们判断只有当每辆喷洒车都执行三次作业任务时，所达到的利用率和效率是最高的。之后，把喷洒车的全部路程分成6个阶段。最后，以求完成最远路程距离点的最小值为目标函数，同时确定相应的约束条件：补水站最多只能给车辆补水8次，其他与任务二一样"最后，通过GA算法，计算出喷洒车完成作业所需的最短时长：13.54h"在任務四中，在道路节点J中增设2个给水站，重新完成第三问的喷洒任务，并计算所需时间。由于喷洒任务的最终目标是用最短的时间不重复的完成作业任务，因而给水站选点的影响因素为F节点的位置"首先列出均匀度函数，通过F点的位置，利用方差最小计算出理想情况下最优的一个J点。并通过选取随机的两个Z点，使得各个Z点到节点F的距离方差最小。确定给水点后，利用任务三的模型，即可得出喷洒车完成作业的时间。最短时长为12.15h。

关键词：GA算法;Floyd模型;平均度

1问题重述

某城市共有绿化喷洒车20台，分为A、B两类。其中A、B类喷洒车分别有12辆、8辆，执行喷洒任务前平均部署在2个停靠点（D1，D2）。所属域内有6个给水站（Z01Z06）、60个喷洒作业点（F01F60），每一个喷洒作业点只需一台喷洒车进行一次作业。各给水站最多可以给八台喷洒车加水，不计加水时间。喷洒车装满水停，在停，点，接到喷洒任务后驶向喷洒作业点喷洒作业。一次喷洒作业A、B两类喷洒车分别需要用时20分钟、15分钟。每辆喷洒车完成一次喷洒任务后，需要到给水站加水再进行下次喷洒作业。

B两类喷洒车在主干道路上的平均行驶速度分别是60公里/小时、50公里/小时，在其他道路上的平均行驶速度分别是45公里/小时、30公里/小时。喷洒车装满水停，在停，点，接到喷洒任务后驶向喷洒作业点喷洒作业。一次喷洒作业A、B两类喷洒车分别需要用时20分钟、15分钟。每辆喷洒车完成一次喷洒任务后，需要到给水站加水再进行下次喷洒作业。

1、任务一：每辆喷洒车只执行一次喷洒作业。请给出完成任务一的最短时间及相应的最优喷洒作业方案。

2、任务二：每辆喷洒车执行两次次喷洒作业。请给出完成任务二的最短时间及相应的最优喷洒作业方案。

3、任务三：完成所有60个喷洒作业点（F01F60）的喷洒任务。请给出完成任务三的最短时间及相应的最优喷洒作业方案。

4、如果在道路节点J01J62中的某两个节点？分别增建一个给水站，请重新考虑问题3。并给出增建给水站的最佳位置。

2问题分析

2.1问题1的分析

任务一要求找出每辆车只执行一次喷洒任务时的最短时间和及其对应的作业方案。

这道题的核心是最优解问题。题目最终的目标的求出完成喷洒任务所需的最短时间，而由于A、B两类车的速度固定，则可以把问题转换为路径最短问题。首先，通过图论的最短路问题的思想，筛选出十个最短的路径，之后比较A、B辆车的速度，将四条最近的路径分配给B车，其余分配给A车，计算十条线路完成的最长用时，得出的即为完成任务的最短时间。

2.2问题2的分析

任务二要求计算每辆喷洒车完成两次喷洒任务时的最短时间。由题意得，每辆喷洒车在完成一次喷洒作业时，必须要到Z点给水站补水，之后才能向下一个洒水作业点前进。同时，每个给水点只能完成8次补水，补水的时间忽略不计。题目的意思可以转换为先找出10个最短路径，分别分配给A、B车，并计算出其中的最长作业完成时间，即为完成任务的最短用时。其中，车辆在进行两个作业之间必须经过一个Z点进行补水。那么该题可以在第一问的基础上改为三段路径进行分析。分别分成起点到第一个作业点，第一个作业点到给水点，给水点到第二个作业点。需要注意的是，当三段路径一起考虑后，由于组合的情况过于复杂，则不可能进行遍历，因而寻找局部最优解是本题的关键。

2.3问题3的分析

任务三要求计算喷洒车完成所有喷洒任务时的最短时间。对于该题，思路和任务二基本一致。不同在于以下几点：（1）每辆车都要保证自己的喷洒任务充分利用，即每辆喷洒车都完成三次喷洒任务;（2）每个补水站只能为8辆喷洒车进行补水，当大于8辆喷洒车时，补水站就变为普通的节点。

2.4问题4的分析

任务四中找出平均度的定义是问题的关键。由于Z点的取点规则是与F点有着密切联系的，当Z点在图上分布的越均匀，则最终用时越短。当确定Z点的分布后，步骤和任务三基本一致。

3模型的优缺点

优点：

1、Floyd算法可以精确的计算出各点之间沿路线的最短距离;

2、用Ga算法进行上千万次的运算求出的解，可以较为准确的接近最优解;

3、引入均匀度函数，可以衡量布置点的均匀性。

缺点：

1、GA算法得出结果存在误差;

2、GA算法计算时间过长，效率较低;