基于蚁群算法的智能生产物流体系构建研究∗

2018-11-28潘胜

计算机与数字工程 2018年11期

潘胜

（台州职业技术学院管理学院台州 318000）

1 引言

随着科学技术的高速发展，市场需求变化越来越来快，产品生命周期越来越短，客户需求呈现多样化和个性化的特征。如何快速响应客户的需求，确保较高的客户服务水平已经成为企业赢得市场，获取核心竞争力的重要手段。为了降低成本，提高物流服务水平，以及满足顾客的多样化、个性化需求，物流企业对仓储系统的要求越来越高［1］。与此同时，随着计算机算法的不断应用，现有的算法求解智能生产物流体系更多的关注在配送路径优化［2～4］，而对智能生产物流的仓储式货物管理研究较少［5］。已有智能生产物流的仓储研究主要包括仓储布局设计和算法设计改进两方面［6］。其中在仓储算法设计方面，针对需求不确定的情况，通过建立鲁棒优化模型可以优化存取货物的期望成本［7］。

本文将智能仓储货架运用到智能生产物流系统中，在配货机执行交叉存取指令的基础上，同时考虑配货机的运行时间和配货机在货位的停留时间，建立了交叉存取时间模型。为提高模型求解效率，首先提出运用指派算法解决货位的指派问题，配货机进行批量存、取货物，使总的时间最短。其次，设计蚁群算法对存、取货物进行优化存储，并与随机算法对比。仿真实验结果表明，蚁群算法提高了智能生产物流系统的效率。

2 智能生产物流体系建模

2.1 问题提出

与传统物流仓储系统相比，智能生产物流的仓储系统最大的不同，主要有两个方面：1）服务时间即时化，智能生产物流的仓储系统对存取、分拣、配送等环节的运作流程和运作时间进行协调和优化，以快速满足客户的多样性、个性化需求［8］；2）存取空间紧致化，智能生产物流的仓储系统减少了传统仓储系统各货架之间的通道，将这些通道合并起来作为存储空间，提高了空间利用率［9］。具体的智能生产物流的仓储货架如图1所示。

图1 智能生产物流的仓储货架

2.2 工作原理

智能生产物流系统的工作原理：首先，配货机在I/O点处待命，接受到出、入库物品信息指令时，开始将物品装载到托盘上，可能不止一个物品装载到同一个托盘上；然后，电脑指派配货机将托盘运送到货架的存放位置并且将所在位置记录到电脑系统中，配货机将托盘存放到货位中，完成存储指令任务；电脑通过储存的信息获取出库的货物托盘的具体位置，直接命令配货机搜索出库的货物托盘，托盘重新回到仓储的进库位置，完成取货指令任务；最后，经过分拣后，托盘被整理后再使用。

以I/O点作为坐标原点(0，0)，x轴表示配货机水平行驶，y轴表示配货机垂直行驶，配货机的行驶速度为单位时间每秒；设外层货位的配货机取货所需时间为t1秒，内层货位的取货时间为t2，且t2=2t1，货架数（R）为巷道数（A）的4倍，即R=4A。为简化描述，不失一般性，用二维代替三维，智能生产物流货架摆放平面图如图2所示。其中出/入库点位于左下角，每列有12个货位，有16列，则每一层的总货位(N)是192个货位。

图2 智能生产物流的仓储货架摆放平面图

单一存取指令和交叉存取指令分别如图3和图4所示，当配货机执行单一指令时，在行驶的过程中会出现空程现象。即配货机从I/O点出发，装载物品，前往存货位，最后从存货位空载返回到I/O点；或者是从I/O点出发，空载到取货位，再装载物品从取货位返回到I/O点。配货机执行单一指令，无论存操作还是取操作都会存在空程现象。因此，本文考虑配货机执行交叉存取命令，避免空程现象。

图3 单一存取指令

图4 交叉存取指令

2.3 货物存取时间模型

本文考虑的是将智能生产物流的仓储体系运用到智能生产物流中，配货机执行交叉式存取指令。因此，对系统提出如下假设：

1）配货机每次只能对单位货物进行存、取操作；

2）忽略配货机在I/O点装卸货物的时间；

3）所有货位的大小相同；

4）配货机服务为多条两边都有巷道的货架提供服务，且从I/O点开始运输；

5）配货机行驶的水平速度和垂直速度相等：VH=VV=1；

6）配货机将货物存放到货位和从货位取货的时间相等，记为t。

假设 Si∈{1，2，…，I}表示存储i货物的货位集合；Rm∈{1，2，…，M}表示取出 m 货物的货位集合；TIS表示从I/O点到货位S的行驶时间；TSR表示从货位S到货位R的行驶时间；TRO表示从取货位R返回到I/O点；W表示配货机在货位的停留时间。则决策变量：

当指令不均衡时，多台配货机执行交叉存取命令，一部分配货机会出现闲置状态，而另一部分配货机处在繁忙状态。因此，为了使配货机得到合理利用，建立了一台配货机在多巷道行驶的交叉存取时间模型，如下：

同时，一台配货机在多巷道中执行交叉存取指令，从I/O点到存储位置，再从存储位置到检索位置，最后从检索位置返回到I/O点的运行时间以及在货位上进行装卸时间之和；每个存、取货物只能占用一个货位；在一个交叉存取作业中至多只包含一个存操作；在一个交叉存取作业中至多只包含一个取操作。则满足的约束条件如下：

3 蚁群算法求解

3.1 算法比较

指派算法［10］从静态层面出发，批量存、取物品，目的是配货机执行完所有的交叉存取指令所需的总时间最短。首先寻找第一货位中所有空货位的最小运行时间进行物品存放；如果第一货位存满了，再寻找第二货位中所有空货位的最小运行时间进行物品存放。同时，还要考虑存、取货位在同一巷道和在不同巷道时配货机的运行情况。

随机算法（Random storage）［11］是确定取货位置，优先随机存储在第一货位，若第一货位存满了，将第一货位的物品移到第二货位，再将被存放的物品放置在第一货位。目的是配货机执行每一次的交叉存取循环指令时间最短，同时配货机每一次执行完存、取货指令时，系统会对仓储的存储状态进行更新。

蚁群算法［12］是基于随机算法的基础上进行改进的，该算法是确定取货位置，在一系列空货位中选择离I/O点近的货位存储物品，目的是配货机寻找最近的空货位，使每一次执行的交叉存取循环指令时间最短。同时配货机每一次执行完存、取货指令时，系统会对仓储的存储状态进行更新。

表1 算法比较

从表1可以看出，S→R表示配货机执行先存后取的交叉存取指令。指派算法与随机法和蚁群算法比较，指派算法的不同之处在于批量考虑存、取物品的问题，批量进行存取，随机寻找空货位，使总的时间最短；随机算法和蚁群算法比较，随机算法的不同之处在于只考虑了配货机进行货物的随机存、取问题。

3.2 算法思路

配货机执行交叉存取命令时，考虑的时间有配货机的运行时间、在货位的装卸时间和翻箱时间，这里将在货位的装卸时间和翻箱时间概括为在货位的停留时间（W）。R表示取货位，S表示存货位，E表示空货位，O表示已占用的货位。TR表示Random Storage存储方法的运行时间，TC表示蚁群算法存储方法的运行时间。运行时间是配货机从I/O点到达存货位，再从存货位前往取货位，最后从取货位返回到I/O点。表2主要是比较了配货机采用Random Storage存储方法和蚁群算法存储方法在货位的停留时间，货位的存取状态分为七种类型。

第1种存、取状态类型：当取货物品位于第一货位，取货物品的第二货位是空货位或非空货位；存货物品存放在第一货位，存货物品的第二货位是空货位或非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都不存在翻箱操作，配货机在货位的装卸时间是2t。

第2种存、取状态类型：当取货物品位于第二货位，取货物品的第一货位是空货位；存货物品存放在第一货位，存货物品的第二货位是空货位或非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都不存在翻箱操作，配货机在货位的装卸时间是3t。

表2 停留时间比较

第3种存、取状态类型：当取货物品位于第二货位，取货物品的第一货位是非空货位；存货物品存放在第一货位，存货物品的第二货位是空货位或非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都不存在翻箱操作，配货机在货位的装卸时间是5t。

第4种存、取状态类型：当取货物品位于第一货位，取货物品的第二货位是空货位或非空货位；存货物品存放在第二货位，存货物品的第一货位是空货位。这种情况不符合Random Storage存储方法，因为Random Storage存储方法是优先存放在第一货位。因此，这种情况符合蚁群算法存储方法且不存在翻箱操作，配货机在货位的装卸时间是3t。

第5种存、取状态类型：当取货物品位于第一货位，取货物品的第二货位是空货位或非空货位；存货物品存放在第二货位，存货物品的第一货位是非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都存在翻箱操作，这种情况如果运用Random Storage存储方法，配货机在货位的停留时间是3t；如果运用蚁群算法存储方法，配货机在货位的停留时间是5t。

第6种存、取状态类型：当取货物品位于第二货位，取货物品的第一货位是空货位；存货物品存放在第二货位，存货物品的第一货位是非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都存在翻箱操作，这种情况如果运用Ran⁃dom Storage存储方法，配货机在货位的停留时间是4t；如果运用蚁群算法存储方法，配货机在货位的停留时间是6t。

第7种存、取状态类型：当取货物品位于第二货位，取货物品的第一货位是非空货位；存货物品存放在第二货位，存货物品的第一货位是非空货位。这种情况Random Storage存储方法和蚁群算法存储方法都存在翻箱操作，如果运用Random Storage存储方法，配货机在货位的停留时间是6t；如果运用蚁群算法存储方法，配货机在货位的停留时间是8t。

3.3 算法公式

配货机只能在巷道行驶，执行交叉存取命令。如果仓储用矩阵表示，那么巷道占用一列，第一货位和第二货位的列坐标不同，在计算距离时，需要将外层货位和内层货位的坐标转换到巷道坐标求解，即纵坐标不变，横坐标进行改变［13］。记(R，C)表示存或取的货物的货位的坐标位置，第i个物品存放在R行C列的位置，第m个物品从 R行C列的位置取出。Gi，m(R，C)表示配货机行驶在巷道的坐标位置，如图2的智能生产物流货架平面图，配货机行驶在两边都有货架的巷道，并且巷道占一列，则

当配货机在同一条巷道执行交叉存取指令时，即配货机进行存、取操作指令时在同一条巷道中完成。计算公式如下：

当配货机在不同的巷道执行交叉存取指令时，即配货机进行存、取操作指令时在不同的巷道内完成。计算公式如下：

3.4 模型优化

配货机在执行一次交叉存取指令时，已知检索物品的位置，需要在一系列空货位中寻找货位存储物品，因此，假设模型中的配货机从I/O点行驶到每个货位所耗费的时间是已知的［14］。L表示为货位的总数量，N表示为货物的总数量，til表示i物品存储到l货位所耗费的时间。则决策变量为

建立一个整数规划的时间模型：

若每个物品只分配一个货位，则约束条件为

将矩形仓储用一个12*16的矩阵表示仓储的存储情况，剔除巷道所占的列，则矩阵表示为

假设 til=1，“0”表示空货位，“1”表示货位已占用，随机生成空货位和已占用的货位，将第一货位和第二货位的存储情况用公式表示如下：

配货机执行完一次交叉存取指令，系统会对第一货位和第二货位的存储情况进行更新，这样能够更加真实地反映仓储的进出入库物品的存储情况。

4 仿真实验

通过计算机Matlab软件编程［15］，模拟现实生活中的仓储货位情况，仓储货位存储状态的数据是随机生成的，具体操作如下。

4.1 数据采集

Step 1：随机生成数据。随机生成二维数据12*16的表示矩阵仓储的货位分布，如图2所示，此时巷道所占的列分别为3、8、13和18，因此，矩阵仓储矩阵赋值如下：

第一巷道负责存、取货位矩阵列为1、2、3、4；

第二巷道负责存、取货位矩阵列为5、6、7、8；

第三巷道负责存、取货位矩阵列为9、10、11、12；

第四巷道负责存、取货位矩阵列为13、14、15、16。

Step 2：定义第一货位和第二货位：

第一货位是矩阵列为2、3、6、7、10、11、14、15；

第二货位是矩阵列为1、4、5、8、9、12、13、16。

第一货位和第二货位的信息表分别是矩阵12*8，信息表中，“0”表示空货位，“1”表示已占用的货位。

Step 3：求期望值：

随机生成存、取货物数量分别为（10，20，30和40）；实验次数为1500次，最终求期望值。

4.2 实验分析

本文对指派算法、随机算法和蚁群算法进行仿真实验，通过仿真图直观地比较存、取时间。横坐标表示配货机执行交叉存取的次数，纵坐标表示配货机执行完存取操作时所耗费的期望时间。

指派算法在实验过程中，通过随机生成位于第一货位、第二货位的取货物，计算每一个取货物到相应的空货位的时间。考虑了两种情况：当取货位于第一货位时，寻找位于第一货位、第二货位中所有空货位的最小运行时间；当取货位于第一货位时，寻找位于第一货位、第二货位中所有空货位的最小运行时间。另外，还考虑了存、取货在同一巷道和不同巷道的情况。

从图5可以看出，当存储密度为65%时，随着存、取货数量的增加，配货机执行命令时，所需的时间呈缓慢上升趋势；当存储密度为80%时，随着存、取货数量的增加，配货机执行命令时，所需的时间呈急剧上升趋势。原因是存储密度由65%～80%时，随着存储密度的增加，空货位的数量随之减少，存在翻箱的可能性增大。配货机在进行存、取货物时，需要翻箱的概率增加，因此，配货机所消耗的时间也随之增加。

图5 指派算法仿真

随机算法在实验过程中，优先寻找第一货位的空货位随机进行存储；若第一货位已占用满了，再寻找第二货位的空货位随机进行存储。蚁群算法在实验过程中，循环第一货位、第二货位中所有空货位寻找最少运行时间的空货位。

从图6可以看出，当存储密度为85%时，随机算法和蚁群算法呈平滑上升趋势。随着存、取次数的增加，配货机执行命令的时间也增加。对比随机算法，蚁群算法所需的时间更短，效率更高。

图6 存储算法仿真

对于仓储企业而言，在智能生产物流中运用倍深式货架，意味着对存储密度要求较高，实验考虑了存储密度为80%、85%和90%，分别比较了随机算法和蚁群算法的效率。智能生产物流中采用蚁群算法，更适用于对存储密度要求高的仓储企业。

从表3可以看出，当存储密度为80%时，蚁群算法比随机存储算法的效率提高了21.76%；当存储密度为85%时，蚁群算法比随机存储算法的效率提高了27.39%；当存储密度为90%时，蚁群算法比随机存储算法的效率提高了31.47%。可以看出，当存储密度较高时，与传统的随机存储算法相比，所设计的蚁群算法具有明显的优越性。