组合旋转货架拣选路径规划研究

（北京信息科技大学 机电工程学院，北京 100192）

0 引言

垂直循环式药柜对药品包装适应性强，是一种自动化的储存设备，主要用于异形包装、处方量少的盒装药品发放，是斜槽式全自动盒装发药机的主要辅助设备[1,2]。单垂直循环式药柜在医院药房使用过程中，存在运行速率慢，处方处理效率低，患者等候时间长等缺点。为克服上述不足，研制出了多垂直循环式智能存取药柜。组合智能存取系统是多个单独的回转单元组成，其处理处方的原理和单回转体智能存取系统相同。当处方中的药品分布在不同的回转单元中时，多个回转单元同时动作，这样就节约了医师等待药品回转到工作台的时间，提高了处方的执行效率。

组合智能存取系统作为旋转货架的一种形式，它的路径优化问题和旋转货架路径优化问题相同。文献[3]应用两级遗传算法对双拣选台多层旋转货架的拣选路径进行了优化，取得了一定的成果。该算法不能排除每一层的货架的方向次数过多这种情况，所以不能保证每一层的货架的拣选顺序是最优的。文献[4,5]给出了一个两层水平旋转货架的几个启发式求解过程。过程叙述比较简单，也没有给出具体选择路径操作过程。文献[6]提出了用蚁群算法求解旋转货架拣选路径优化问题。

旋转货架拣选路径优化问题非常复杂，它同旅行商问题（TSP）一样，属于NP难题[1,2,4]，现在多数论文研究还是在路径规划上面，如何实现这个路径还没有深入研究。本文在总结前人研究结果的基础上，提出了一种求出拣选路径的一种方法。该方法能很好的求出最优路径。

1 组合智能存取系统拣选路径数学模型

组合智能存取系统的拣选路径要比单回转体智能存取系统的拣选路径问题复杂很多，将药品清单上的药品从不同的回转单元中选出来，然后将各个回转单元中的药品进行排序，生成各个回转单元的子货单。最后根据每个回转单元中的药品序列控制组合智能存取系统进行运动。

1.1 组合智能存取系统拣选药品流程

医院将划过价的电子处方由HIS系统发给药房的服务器，然后将这些储位编号通过上位机发送给控制器和底层PLC，实现药品的拣选。具体操作流程如下：拣选开始时，所有回转单元都处在初始零位置，当上层发送至指令时，所有的回转单元同时运动，药剂师准备拣选药品。当有回转单元运动到位时，药剂师移动到该回转单元，开始拣选药品；当药剂师拣选完毕后，点击确认按钮，该回转单元接着运动到下一个药品储位，同时药剂师移动到离得最近的已经运动到位的回转单元进行下一次拣选，如果没有回转单元运动完成，则药剂师等待回转单元运动完成，然后运动到离自己最近的回转药柜进行拣选药品。以此类推，直到所有的药品拣选完成，整个拣选过程完毕。

显然，对于组合回转药柜的拣选路径优化，就是寻找具有最短拣选作业时间的若干个子货单问题。最短作业时间就是拣选路径优化的目标。

1.2 组合智能存取系统拣选路径的数学模型

组合智能存取系统的最短路径问题，就是求最短作业时间的问题。假设回转单元运行一层的时间设为Tmove；药剂师移动一个回转单元所需时间为Tmalk；每个储位只存放一种药品；药师开始时在1号回转单元处；垂直多回转智能存取系统由n个垂直旋转货架组成；货架与货架之间的距离为L；每个货架有m层货位；每层货位的高度为h。因此，垂直旋转货架在顶点处展开的图形如图1所示。

图1 多回转智能存取系统顶点展开原理图

假设x表示水平方向，即拣选人员的运行方向或多回转智能存取系统摆放方向，y表示垂直方向，即多回转智能存取系统的垂直旋转方向。拣选设备从初始点出发，拣选完所有货物后，再返回至初始拣货点。所有储位点的坐标由集合表示。多回转智能存取系统在进行y方向上旋转时，货品位置坐标随着任务运行而进行动态变化，在完成某一货架位置为(x,y)的物品后，需要更新该垂直旋转货架上的位置坐标，对于初始位置为(x,y')更新后的坐标为(x,y'')，其中：

从拣选完货位[i-1]至货位[i]，拣选人员等待旋转货架[i]货位旋转所用的时间为t0(i-1,i)。

拣选完第[i-1]个货位到拣选完[i]个货位所需要的时间为：

货架拣选完全部M个货位点所用的时间为：

拣选路径的优化目标为：求取最优拣选序列，使得总的拣选时间最小，即：

求总拣选时间最短。

多垂直旋转货架系统的配货顺序优化问题为：在给定的n个拣选货位点，在可行解的集合F∈{n个待拣选的所有排列｝找出一个排列f1，使得对一切f∈F，Ttotal(f1)≤Ttotal(f)，则称f1为该问题的最优解，也即拣选货位点的所有排列中找到一种排列顺序，使得完成任务单中所有拣选点所需要的时间最短。则问题化简为求解单源最短路径问题。

在多回转智能存取系统问题的最优解中，各组层序所含货物的排列是相应单层旋转货架中待拣选货物的最优拣选排序。

2 改进的离散粒子群算法对多回转智能存取系统建模

粒子群算法模型如下：

其中w称为惯性权重，设为w=0.96-int eration/max int eration，其中int eration是当前迭代次数，max int eration为最大迭代次数，代表的是速度的改变概率；c1是粒子个体最优值的加速系数，c2是粒子全局最优值的加速系数；r1和r2是介于[0，1]之间的随机数；和分别是粒子在第k周期和第k+1周期速度；分别是粒子在第k周期和第k+1周期的位置；代表粒子在第k周期个体所达到过的最佳位置；代表粒子在第k周期整个粒子群体所达到过的最佳位置。

以式(6)为评价函数，构造基于改进的离散粒子群的算法模型。步骤为：

2）速度取值：对于粒子xid，初始速度的取值。设货位数为m，粒子数为n，对m×n的二维矩阵的每一列，用1到n这m个数进行整数随机排列，得到一个速度矩阵，获得的速度vid是随机的一个交换序；

3）最优粒子的选择：个体和全局最优粒子的选择是根据粒子位置向量排序生成有效拣选作业路径后计算m个目标城市之间的距离来确定的，即选择花费的距离代价最小的粒子作为个体和全局最优粒子；

4）初始化各参数。随机初始化粒子种群，将每个粒子的位置值代入目标函数，得到对应的适应值；

5）评价适应度函数，更新粒子个体最优解 和整个种群的全局最优解；

6）更新每一个粒子的速度与位置；

7）评价种群中的各个粒子；

8）更新粒子局部最优解和全局最优解；

9）评价粒子群是否满足迭代条件，若满足迭代条件，则停止，选择最佳个体作为改进离散粒子群算法的结果，否则，转到第6）步，重复刚才的步骤。

3 多回转智能存取系统的实验结果和分析

改进的离散粒子群算法应用于山西某儿童医院的多回转智能存取系统上，该系统中共有4组旋转货架，每个旋转货架系统共有10层货架；垂直旋转货架旋转速度0.2m/s，储位斗高度为0.4m；药师行进速度为0.5米/秒，两货架间距为1米。所需要拣选的药品在货架中的储位均为随机选取。表4为随机产生的待拣选的20个储位点的数据信息。为检验算法求解多垂直旋转货架动态路径规划问题的有效性，运用Matlab语言对上述算法编程，设计大量算例进行模拟运算，测试算法的性能。路径优化结果以及适应度变化曲线分别如图2、3所示。其中，种群规模均为50，100，200，500，最大迭代次数为2000次。最小的权重系数wmin=0.01，最大权重系数wmax=0.96。对货位坐标做归一化处理，货架转过1层的时间为0.4/0.2=2秒，相邻两个货架医师行进时间为1/0.5=2秒。因此第1个智能存取单元的第1层地址坐标可以表示为（2,0），第3个智能存取单元的第7层可以表示为（14,4）。

表1 20个药品拣选储位信息

首先初始停靠坐标为（4，0），以随机选取储位的方式，对任意1～5，1～20个不同储位进行出药，分别通过改进的离散粒子群算法验证其出药最短路径和正确性，表2、表3记录了分别停靠5个、20个储药位置的最优拣选时间、最差拣选时间、平均拣选时间、最优拣选时间到达率以及每次拣选算法运行所需要的CPU时间。图2～图3分别表示在种群规模为500时，从药师自多回转智能存取系统（4组回转体）原点出发分别拣选5个、20个储药位，获得最优拣选路径时的迭代进化曲线和最优路径路线图。

表2 5个储位时算法性能

表3 20个储位时算法性能

图2 5个储位时的最优拣选路径及其进化曲线

图3 20个储位时的最优拣选路径及其进化曲线

改进的交换离散粒子群算法在求解单源最短路径问题时具有如下特点：

1）算法在拣选点较少时（如10个以内）优化效果很好。根据表2，当遍历点较少的时候，算法效果很好，当拣选储位数量为5个时，算法能够100%到达最优拣选路径。由图2发现粒子群迭代发现最优解的速度很快，迭代次数少于30次就获得了最优解；粒子种群规模达到200时，CPU运行时间仅需要0.13秒。

2）算法在停靠点数较多的时候，效果较差。如表3，当储药槽数量上升到一定程度，到达20个点时，算法在单源最短路径问题是时的效率显著下降，能够到达最优拣选路径的能力下降，即使种群规模达到500，最优拣选路径到达率也只有2.0%，且算法CPU运行时间达到1.8秒，可以认为算法基本失效。

3）算法的收敛速度很快。根据图2、图3的进化曲线图发现，即使在停靠点数达到20，种群规模达到500，粒子群发现最优拣选路径的迭代次数小于100。

因为每次拣选都是药师都是从多回转智能存取系统默认的初始点（1号柜）出发，按照处方需要出药的种类对应药品储位进行取药，所以该问题中的停靠点数量应该是需要出药的药品储位数加1，如遍历1-5号储位时，实际停靠点为6个，以此类推。表4为改进的离散粒子群算法拣选路径优化结果。

表4 改进的离散粒子群算法拣选路径优化结果

4 结论

垂直循环式药柜是一种实用的自动化储存设备，用作医院盒装药品的智能存取。本文重点介绍了求解多回转智能存取系统拣选时间优化问题的一种解决思路。对路径问题建立数学模型，把问题抽象成单源最短路径问题，目标函数是求解拣选所需时间最小值。用图论的方法对问题进行分析，在Matlab上利用改进的离散粒子群算法，针对山西某儿童医院实际情况进行建模。结果表明，算法具有可行性，优化效果良好，为实现组合垂直循环式药柜控制算法提供了有价值的参考。