穷举-混沌蚁群算法环形穿梭车模型研究

刘绪川，王 龙，梅英杰，张孟建

（1.中科芯集成电路有限公司，无锡214072；2 哈尔滨工业大学 仪器科学与工程学院，哈尔滨150001；3.贵州大学 电气工程学院，贵阳550025）

近年来，自动化物流系统[1-2]日益广泛地应用于烟草、机电、医药、食品、军队等领域，相关物流装备趋于多元化，其水平和技术性能不断提高。自动化仓库作为物流系统中一个重要的组成部分，其不仅具有传统仓库的存储功能，还具有拣选、盘点、理货等功能，而且其设备自身及物料存取操作都能自动进行，这大大提高了仓储效率，同时节省劳动力，受到了广泛的关注。立体仓库系统在食品、医药、烟草、玻纤、家具等行业应用日渐广泛，以立体仓库系统为核心的相关物流设备愈加多元化，技术水平和性能也得到不断提高。

穿梭车又称为轨道式自动导引车RGV[4-6]，是集多种高新技术于一体的自动搬运设备，因行驶和输送速度快、灵活性好、自动化程度高而被广泛应用。经过长期的发展，环形RGV 系统代替了多台直行RGV 系统或者大量的普通输送设备，实现物料运送目的地的自由变动，提高了输送的效率和灵活性。环形RGV 系统其最主要的应用是作为连接立体仓库入库作业区站台、出库作业区站台和立体仓库站台的纽带，起搬运物料的作用，是立体仓库系统主要且重要的子系统。由于环形RGV 系统采用封闭的环形轨道，RGV 单向环轨绕圈行驶，相邻两车之间存在防止碰撞的安全距离，针对不同项目系统的轨道数据 （直道长度、弯道长度和转弯半径等）、RGV 运行参数（直道行驶速度、弯道行驶速度和加速度等）、装卸载站台数量及位置分布、物流的需求量等参数的不同，RGV 的数量有着很大的差异[3，7-8]。

穿梭车在整个工作系统中，其效率受到出进货口停留时间、车身长度、穿梭车数、运行速度等影响。若穿梭车过多，会造成拥堵，甚至会系统瘫痪，大大降低了工作运行效率。若穿梭车较少，虽然不会造成系统拥堵，但是会使得货物运输时间较长，货物运输的效率降低。因此合理的穿梭车调度，在合适的运行速度下，减少拥堵时间，会使得整个工作系统效率提高。

1 模型假设

假设1：为方便货物的搬运，假设每侧的进、出货口均匀分布在轨道的直线上。

假设2：假设每辆穿梭车每次只能运送1 件货物。

假设3：假设穿梭车装、卸货物的时间相同，分别为tL、tU，一个周期为T s。

假设4：假设穿梭车的货运轨道为单轨道设计，穿梭车不能超车，只能进行停车和前进。

假设5：假设穿梭车在环形轨道上逆时针匀速运行，其速度为v。

假设6：假设每侧的进、出货口均匀地分布在轨道的起点中线两侧，其间隔为3 m。

A 侧进货口待进的货物量为200 件，B 侧总的待进货数量为322 件。从B 侧进货、A 侧出货时，所对应的进货口和出货口之间的距离，其值如表1所示。

表1 B 侧进货A 侧出货对应的进货口距离（考虑车长，m）Tab.1 Distance of the receiving port corresponding to the B-side purchasing and A-side shipping（considering the vehicle length，m）

表2 所示为一些主要符号含义。

表2 符号说明Tab.2 Symbol description

2 模型建立

考虑系统的运行效率，使得穿梭车运送货物能够得到高效运行，在穿梭车数量合适情况下，尽可能保证不拥堵，提高系统效率。

2.1 模型1

基于以上对问题的分析和理解，建立单个穿梭车的装、卸货物和运行的耗时模型，其公式如下：

式中：T1为小车在环形轨道上运行的时间；T2为小车装、卸货物所需的时间；T3为运行过程中等待的时间。

式中：S 为小车完成1 次装、卸货物在环形轨道上所通过的路程；v 为小车的行驶速度。

此外，小车装、卸货物所需的时间为

式中：tL为小车装货所需要的时间；tU为小车卸货所需要的时间；n 为装卸货物的次数。

2.2 模型2

本文为了清楚地描述穿梭车的数量变化对系统的拥堵次数、完成工作量所需要的时间之间的关系。采用最小二乘多项式拟合，建立n 次多项式模型：

2.3 起点中线规则

为了方便后续算法分析，穿梭车轨道L=100 m，穿梭车运行速度v=1.5 m/s，装卸货一个周期T=10 s，轨道上出货口7 个，进货口6 个，考虑实际穿梭车车长约1.3 m，进出货口宽度1 m。设计环形轨道如图1 所示。

图1 考虑车长的环形轨道示意图Fig.1 Schematic diagram of circular track considering vehicle length

3 模型设计分析

3.1 穷举式算法

穷举式算法在小车数量少的情况下，可以比较精确地得到最优调度，所占用的资源也不多，其在本文的流程是：在满足约束的情况下，保证排队最少的情况下，小车行驶的最短距离即可当做目标最短时间。当A、B 侧均有货物时，小车优先载运B 侧的货物，并从最远的进货口进行装货，到达A 侧卸货时，以最远的出货口为优先出货口；当B 侧的有货进货口数目少于小车数量时，小车开始对A 侧的进货口进行载运，由于A 侧的货物有固定的出货口，本文选择dA1k和dA2k（dAjk表示A 侧进货口j 中的第k 个货物在B 侧的目标出货口）中货号口更大的进行载运。假设系统中N 量穿梭车Ci（i 表示从0～N），每辆车到进货口的距离为dQjCi，则组成的矩阵为

当有t 个任务时，每一辆穿梭车到对应的进货口都有对应的距离，通过这些值可以穷举出穿梭车的行径组合有种；对于这些组合可以选取矩阵中不同列和不同行对应的距离之和最短的数值，因为小车排队最少，所以该值即可当做最优解。

3.2 基于混沌蚁群算法的穿梭车处理货物的调度规划

由于蚁群算法[9-10]在进行穿梭车调度时存在操作时间长、收敛效率低、易陷入局部最优等缺陷。而混沌理论利用混沌运动特有的内在遍历性、规律性和随机性可以在一定范围内不重复地遍寻所有状态，跳出局部最优解，具有良好的计算精度和全局寻优能力。因此将混沌理论加入到基本蚁群算法中可有效改善基本蚁群算法的弊端，得到较优的算法，从而规划出全局最优。因此我们建立了混沌蚁群算法模型。

混沌蚁群算法的穿梭车规划算法流程如图2所示。

3.3 基于蒙特卡洛的出货口选择算法

根据问题背景可以得到，此环形穿梭车系统共有两侧，分别为A、B 侧，两侧均有进货口，亦有出货口。B 侧的进、出口数量相等，均为4 个，将进货口的编号 设为I，其中I＝1，2，3，4； 出货口设 为J，J＝1，2，3，4。

而对应的A 侧出货只有3 个，因此，针对B侧作为进货口时，其出货口位于A 侧，但是出货口的选择是随机的，基于这一特点，本文设计了基于蒙特卡洛的出货口选择算法，该算法的核心为代码如下：

3.4 算法分析

步骤1使用蒙特卡洛的出货口选择算法计算出B 侧作为进货口的情况下，单辆穿梭车完成对应进货口的工作任务所需要的时间；B 侧4 个进货口分别完成工作量所需时间。

步骤2由于A 侧的进货口有待货出口时，每个进货口均指定了B 对应的出货口。因此，在计算完成货物量所需要的时间前，应根据起点中线规则（考虑车长）计算出进货口和出货口之间的距离，如图3 所示。

图3 A 侧进货口与B 侧各出货口之间的距离Fig.3 Distance between A-side inlet and B-side outlet

步骤3根据穿梭车运动规则和各进、出货口之间距离关系，使用蒙特卡洛方法进行模拟，分别取N＝1，3，6，7，9 进行计算，模拟了4 组结果，所得结果如图4 所示。

图4 穿梭车数量与完成工作的耗时关系图Fig.4 Relationship between the number of shuttle cars and the time taken to complete the work

从图4 中可以明显地看出，完成一定数量的工作量的情况下，即系统能够接受的范围内，完工的时间与穿梭车的数量成反比。

步骤4对环形穿梭车系统效率，我们考虑穿梭车的拥堵时间以及在单位时间内系统最大货物吞吐量来评价系统效率。在N≤5 时，用穷举式算法求取穿梭车拥堵时间、货物处理总耗时以及单位时间内系统最大货物吞吐量。在N＞5 时，用混沌蚁群算法找到最优穿梭车拥堵时间、货物处理总耗时以及单位时间内系统最大货物吞吐量。其拟合结果如图5 所示。

图5 拟合结果Fig.5 Fitting results

结果表明系统的拥堵次数和拥堵时间会随小车数目增加而明显增加；系统的总完工时间在与穿梭车数目之间是一个先减少后增加的关系，系统在单位时间内的最大货物吞吐量与穿梭车之间是一个先增加后减少的关系，可以得知穿梭车后期的拥堵会造成系统运行效率的降低。故为保证穿梭车系统的效率，需要选择合适的小车数目。

4 结语

根据本文建立的模型和使用的算法，不同数量的穿梭车情况下，对单位时间货物吞吐量、处理货物的耗时情况、拥堵时间以及拥堵次数进行分析，找到最合适的小车数，保证系统的效率。本模型可用于工厂环形穿梭车系统的构建，实际运用中对参数的优化存在一定的实际价值，对自动化物流系统有重要意义。