基于自适应量子遗传算法的环形穿梭车调度系统研究

2020-10-12张雪玉徐红博李赫肖爱梅

科学与信息化 2020年20期

张雪玉徐红博李赫肖爱梅

摘要环形穿梭车是一种智能的搬运设备，它有着很高的灵活性，而环形穿梭车系统已成为现如今工业生产中最重要的货物运输调度方式之一。如何合理设计系统的算法，为工业生产节省更多的时间成为人们需要解决的问题。本文运用排队论相关知识，结合C++编程，使用量子遗传算法自适应的确定个体交叉变异概率，为穿梭车系统的设计与调度过程进行了最优化的模拟。通过动态模拟穿梭车调度过程，对环形穿梭车系统进行了多角度的分析，建立了穿梭车动态调度模型，并给出了该系统最优化的货物处理方案，在实际应用中有较大的参考价值。

关键词排队论;动态调度;环形穿梭车;量子遗传算法

1问题背景

近年来，随着物流行业的高速发展与广泛应用，因全球经济飞速发展等原因，物流运输对物流作业能力、劳动生产率、物流作业差错、利润等方面的要求越来越高。物流运输已逐渐趋于自动化。环形穿梭车系统是一种智能的搬运设备。以其自动化控制、高速运输、线路控制、合理作业等特点而获得广大用户的认可和支持，现普遍应用于日用百货、烟草、机电、医药等领域，已成为工业生产中最重要的货物运输调度方式之一。如何合理的设计系统的算法，为工业生产节省更多的时间成为人们需要解决的问题。对于环形穿梭车系统的研究和开发，不仅意义重大，而且具有实际运用价值。

2问题描述

环形穿梭车系统[1]由两侧的进出货口、若干辆穿梭车以及一个环形轨道组成。它的工作流程如下：①穿梭车行至相应进货口。②若穿梭车前面有车，则等待装货;若无，则立即装载货物。③穿梭车行至相应出货口。④若穿梭车前面有车，则等待;若无，则立即卸载货物⑤循环过程1-4直至所有货物全部装卸完毕。

假设环形穿梭车在工作过程中不会出现故障，并且能够完整地跑完整个过程。环形穿梭车在到达进货口装载货物的时候，能够立即开始装货，即保证进货口能够及时供货侧进货口装载的货物只能运送到B指定的出货口，B侧进货口装载的货物可以运送到A侧任意出货口。每个进出货口都遵循先来先服务的原则，且A侧某个进货口运输到B侧的出货口的序号不是固定的。在不考虑穿梭车长度的情况下，目标为总完工时间最小[2]。整體流程示意图如图1所示。

3模型构建

排队论[3-4]是研究解决排队问题的一门学科，因为该系统中穿梭车的调度过程中不允许发生超车，即会出现排队的情况。在排队模型中，我们可以把穿梭车看成顾客，把服务机构看成货物口，排队服从于先来先服务的规则，当装卸完毕之后视为服务结束。

由此建立N辆穿梭车的货物调度模型，计算总完工时间，其可以描述为：

其中代表穿梭车处理第i个货物所需要的总时间，我们把某个任务的完成时间分为了三部分，空载运行的时间、装货运行的时间以及排队等待的时间，则的计算方式如下：

其中货物的等待时间为前面需要处理装卸货物的穿梭车的个数乘上装卸货所需要的时间，即

在穿梭车接收到指令到到达货物口的这段过程中，穿梭车处于空载状态，我们设这段距离所需要的时间为：

穿梭车装载货物完成后到达目的出货口的过程，所需要花费的时间为：

为了评定模型效率，建立评价模型，我们从以下三个方面来分析系统的花费时间。

系统完成整个任务的总过程中，穿梭车的空闲时间为：

（n 是需要处理的货物总数）

不考虑小车长度穿梭车总的拥堵时间：

系统 100 秒内的最大货物吞吐量：

β为在时间段中完成的货物个数。根据实际生活中的具体情况，我们对每个影响参数进行加权平均，获得系统总的效率评价模型：

其中为影响每个参数的权重因子。通过改变穿梭车数目，运行程序100次，测得α1，α2，α3的平均值为 0.1，0.3，0.6。因此采用此比例作为最终的评价权重因子。

4实验仿真

在系统中，由于穿梭车速度的原因，导致穿梭车装卸货物的时间内，后面的穿梭车只能处于等待状态而浪费了大量时间。因此我们利用问题模型结合遗传算法，对小车的运行速度进行了优化。

根据本问题的实际需求，本文使用自适应量子遗传算法[5-7]来对3穿梭车情况下的最优速度问题进行求解，受篇幅所限，自适应量子遗传算法原理在此不再赘述。算法在2.03s就跑出了结果，其进化代数与相应的调度总时间如图2所示。可以看出，算法的迭代次数和收敛效果都非常的不错。

图2 自适应量子遗传算法进化代数效果图

其中算法得到的最终结果与相应时间如图3所示。

从运行结果可以看出，小车速度并不是越快越好，由于会发生堵塞等原因，3 穿梭车在速度为 5.0m/s 时，总调度时间最短为13126s。

5结束语

本文给出了环形穿梭车的动态调度模型和时间最优化算法。为了能够实现动态调度最优化，首先把问题分解为多个子问题：环形车的物料运输问题、环形车的排队问题，环形车的分配派遣问题，根据不同的子问题建立总的的动态规划模型。并且将拥堵时间与理想时间的比值、单位时间货物的最大处理量作为评价依据，建立评价模型。利用自适应量子遗传算法，对环形穿梭车系统的穿梭车速度参数进行改进，得到了良好的实验效果。

图3 自适应量子遗传算法效果图

参考文献

[1] 邹佰翰，夏鑫，张吉懿.基于贪心策略的环形穿梭车调度算法设计[J].网络安全技术与应用，2020（4）：52-53.

[2] 向旺，吴双，张可义，等.基于排队论的环形穿梭车系统运行参数分析[J].制造业自动化，2018，40（6）：151-153.

[3] 杨少华，张家毅，赵立.基于排队论的环轨多车数量与能力分析[J].制造业自动化，2011，33（16）：102-104.

[4] 胡建伟，李东波，何非，童一飞.环形穿梭车调度系统设计与开发[J].物流技术，2015，34（9）：266-268.

[5] 余建坤，张文彬，陆玉昌. 遗传算法及其应用[J]. 云南民族学院学报（自然科学版），2002（4）：193-197.

[6] 曲志坚，张先伟，曹雁锋，等. 基于自适应机制的遗传算法研究[J]. 计算机应用研究，2015（11）：3222-3225.

[7] WangY，Feng XY，HuangYX，et al. Anovel quantumswarm evolutionary algorithm and its applications[J].Neurocomputing，2007，70（4-6）：633-640.

作者简介

张雪玉（1998-），女，山东省烟台市人;现就读学校：山东理工大学计算机科学与技术学院，本科在读，研究方向：智能优化算法。

徐红博（1998-），男，山东省聊城市人;现就读学校：山东理工大学计算机科学与技术学院，本科，研究方向：遗传算法与机器学习。