組合旋轉(zhuǎn)貨架揀選路徑規(guī)劃研究

（北京信息科技大學 機電工程學院，北京 100192）

0 引言

垂直循環(huán)式藥柜對藥品包裝適應(yīng)性強，是一種自動化的儲存設(shè)備，主要用于異形包裝、處方量少的盒裝藥品發(fā)放，是斜槽式全自動盒裝發(fā)藥機的主要輔助設(shè)備[1,2]。單垂直循環(huán)式藥柜在醫(yī)院藥房使用過程中，存在運行速率慢，處方處理效率低，患者等候時間長等缺點。為克服上述不足，研制出了多垂直循環(huán)式智能存取藥柜。組合智能存取系統(tǒng)是多個單獨的回轉(zhuǎn)單元組成，其處理處方的原理和單回轉(zhuǎn)體智能存取系統(tǒng)相同。當處方中的藥品分布在不同的回轉(zhuǎn)單元中時，多個回轉(zhuǎn)單元同時動作，這樣就節(jié)約了醫(yī)師等待藥品回轉(zhuǎn)到工作臺的時間，提高了處方的執(zhí)行效率。

組合智能存取系統(tǒng)作為旋轉(zhuǎn)貨架的一種形式，它的路徑優(yōu)化問題和旋轉(zhuǎn)貨架路徑優(yōu)化問題相同。文獻[3]應(yīng)用兩級遺傳算法對雙揀選臺多層旋轉(zhuǎn)貨架的揀選路徑進行了優(yōu)化，取得了一定的成果。該算法不能排除每一層的貨架的方向次數(shù)過多這種情況，所以不能保證每一層的貨架的揀選順序是最優(yōu)的。文獻[4,5]給出了一個兩層水平旋轉(zhuǎn)貨架的幾個啟發(fā)式求解過程。過程敘述比較簡單，也沒有給出具體選擇路徑操作過程。文獻[6]提出了用蟻群算法求解旋轉(zhuǎn)貨架揀選路徑優(yōu)化問題。

旋轉(zhuǎn)貨架揀選路徑優(yōu)化問題非常復雜，它同旅行商問題（TSP）一樣，屬于NP難題[1,2,4]，現(xiàn)在多數(shù)論文研究還是在路徑規(guī)劃上面，如何實現(xiàn)這個路徑還沒有深入研究。本文在總結(jié)前人研究結(jié)果的基礎(chǔ)上，提出了一種求出揀選路徑的一種方法。該方法能很好的求出最優(yōu)路徑。

1 組合智能存取系統(tǒng)揀選路徑數(shù)學模型

組合智能存取系統(tǒng)的揀選路徑要比單回轉(zhuǎn)體智能存取系統(tǒng)的揀選路徑問題復雜很多，將藥品清單上的藥品從不同的回轉(zhuǎn)單元中選出來，然后將各個回轉(zhuǎn)單元中的藥品進行排序，生成各個回轉(zhuǎn)單元的子貨單。最后根據(jù)每個回轉(zhuǎn)單元中的藥品序列控制組合智能存取系統(tǒng)進行運動。

1.1 組合智能存取系統(tǒng)揀選藥品流程

醫(yī)院將劃過價的電子處方由HIS系統(tǒng)發(fā)給藥房的服務(wù)器，然后將這些儲位編號通過上位機發(fā)送給控制器和底層PLC，實現(xiàn)藥品的揀選。具體操作流程如下：揀選開始時，所有回轉(zhuǎn)單元都處在初始零位置，當上層發(fā)送至指令時，所有的回轉(zhuǎn)單元同時運動，藥劑師準備揀選藥品。當有回轉(zhuǎn)單元運動到位時，藥劑師移動到該回轉(zhuǎn)單元，開始揀選藥品；當藥劑師揀選完畢后，點擊確認按鈕，該回轉(zhuǎn)單元接著運動到下一個藥品儲位，同時藥劑師移動到離得最近的已經(jīng)運動到位的回轉(zhuǎn)單元進行下一次揀選，如果沒有回轉(zhuǎn)單元運動完成，則藥劑師等待回轉(zhuǎn)單元運動完成，然后運動到離自己最近的回轉(zhuǎn)藥柜進行揀選藥品。以此類推，直到所有的藥品揀選完成，整個揀選過程完畢。

顯然，對于組合回轉(zhuǎn)藥柜的揀選路徑優(yōu)化，就是尋找具有最短揀選作業(yè)時間的若干個子貨單問題。最短作業(yè)時間就是揀選路徑優(yōu)化的目標。

1.2 組合智能存取系統(tǒng)揀選路徑的數(shù)學模型

組合智能存取系統(tǒng)的最短路徑問題，就是求最短作業(yè)時間的問題。假設(shè)回轉(zhuǎn)單元運行一層的時間設(shè)為Tmove；藥劑師移動一個回轉(zhuǎn)單元所需時間為Tmalk；每個儲位只存放一種藥品；藥師開始時在1號回轉(zhuǎn)單元處；垂直多回轉(zhuǎn)智能存取系統(tǒng)由n個垂直旋轉(zhuǎn)貨架組成；貨架與貨架之間的距離為L；每個貨架有m層貨位；每層貨位的高度為h。因此，垂直旋轉(zhuǎn)貨架在頂點處展開的圖形如圖1所示。

圖1 多回轉(zhuǎn)智能存取系統(tǒng)頂點展開原理圖

假設(shè)x表示水平方向，即揀選人員的運行方向或多回轉(zhuǎn)智能存取系統(tǒng)擺放方向，y表示垂直方向，即多回轉(zhuǎn)智能存取系統(tǒng)的垂直旋轉(zhuǎn)方向。揀選設(shè)備從初始點出發(fā)，揀選完所有貨物后，再返回至初始揀貨點。所有儲位點的坐標由集合表示。多回轉(zhuǎn)智能存取系統(tǒng)在進行y方向上旋轉(zhuǎn)時，貨品位置坐標隨著任務(wù)運行而進行動態(tài)變化，在完成某一貨架位置為(x,y)的物品后，需要更新該垂直旋轉(zhuǎn)貨架上的位置坐標，對于初始位置為(x,y')更新后的坐標為(x,y'')，其中：

從揀選完貨位[i-1]至貨位[i]，揀選人員等待旋轉(zhuǎn)貨架[i]貨位旋轉(zhuǎn)所用的時間為t0(i-1,i)。

揀選完第[i-1]個貨位到揀選完[i]個貨位所需要的時間為：

貨架揀選完全部M個貨位點所用的時間為：

揀選路徑的優(yōu)化目標為：求取最優(yōu)揀選序列，使得總的揀選時間最小，即：

求總揀選時間最短。

多垂直旋轉(zhuǎn)貨架系統(tǒng)的配貨順序優(yōu)化問題為：在給定的n個揀選貨位點，在可行解的集合F∈{n個待揀選的所有排列｝找出一個排列f1，使得對一切f∈F，Ttotal(f1)≤Ttotal(f)，則稱f1為該問題的最優(yōu)解，也即揀選貨位點的所有排列中找到一種排列順序，使得完成任務(wù)單中所有揀選點所需要的時間最短。則問題化簡為求解單源最短路徑問題。

在多回轉(zhuǎn)智能存取系統(tǒng)問題的最優(yōu)解中，各組層序所含貨物的排列是相應(yīng)單層旋轉(zhuǎn)貨架中待揀選貨物的最優(yōu)揀選排序。

2 改進的離散粒子群算法對多回轉(zhuǎn)智能存取系統(tǒng)建模

粒子群算法模型如下：

其中w稱為慣性權(quán)重，設(shè)為w=0.96-int eration/max int eration，其中int eration是當前迭代次數(shù)，max int eration為最大迭代次數(shù)，代表的是速度的改變概率；c1是粒子個體最優(yōu)值的加速系數(shù)，c2是粒子全局最優(yōu)值的加速系數(shù)；r1和r2是介于[0，1]之間的隨機數(shù)；和分別是粒子在第k周期和第k+1周期速度；分別是粒子在第k周期和第k+1周期的位置；代表粒子在第k周期個體所達到過的最佳位置；代表粒子在第k周期整個粒子群體所達到過的最佳位置。

以式(6)為評價函數(shù)，構(gòu)造基于改進的離散粒子群的算法模型。步驟為：

2）速度取值：對于粒子xid，初始速度的取值。設(shè)貨位數(shù)為m，粒子數(shù)為n，對m×n的二維矩陣的每一列，用1到n這m個數(shù)進行整數(shù)隨機排列，得到一個速度矩陣，獲得的速度vid是隨機的一個交換序；

3）最優(yōu)粒子的選擇：個體和全局最優(yōu)粒子的選擇是根據(jù)粒子位置向量排序生成有效揀選作業(yè)路徑后計算m個目標城市之間的距離來確定的，即選擇花費的距離代價最小的粒子作為個體和全局最優(yōu)粒子；

4）初始化各參數(shù)。隨機初始化粒子種群，將每個粒子的位置值代入目標函數(shù)，得到對應(yīng)的適應(yīng)值；

5）評價適應(yīng)度函數(shù)，更新粒子個體最優(yōu)解 和整個種群的全局最優(yōu)解；

6）更新每一個粒子的速度與位置；

7）評價種群中的各個粒子；

8）更新粒子局部最優(yōu)解和全局最優(yōu)解；

9）評價粒子群是否滿足迭代條件，若滿足迭代條件，則停止，選擇最佳個體作為改進離散粒子群算法的結(jié)果，否則，轉(zhuǎn)到第6）步，重復剛才的步驟。

3 多回轉(zhuǎn)智能存取系統(tǒng)的實驗結(jié)果和分析

改進的離散粒子群算法應(yīng)用于山西某兒童醫(yī)院的多回轉(zhuǎn)智能存取系統(tǒng)上，該系統(tǒng)中共有4組旋轉(zhuǎn)貨架，每個旋轉(zhuǎn)貨架系統(tǒng)共有10層貨架；垂直旋轉(zhuǎn)貨架旋轉(zhuǎn)速度0.2m/s，儲位斗高度為0.4m；藥師行進速度為0.5米/秒，兩貨架間距為1米。所需要揀選的藥品在貨架中的儲位均為隨機選取。表4為隨機產(chǎn)生的待揀選的20個儲位點的數(shù)據(jù)信息。為檢驗算法求解多垂直旋轉(zhuǎn)貨架動態(tài)路徑規(guī)劃問題的有效性，運用Matlab語言對上述算法編程，設(shè)計大量算例進行模擬運算，測試算法的性能。路徑優(yōu)化結(jié)果以及適應(yīng)度變化曲線分別如圖2、3所示。其中，種群規(guī)模均為50，100，200，500，最大迭代次數(shù)為2000次。最小的權(quán)重系數(shù)wmin=0.01，最大權(quán)重系數(shù)wmax=0.96。對貨位坐標做歸一化處理，貨架轉(zhuǎn)過1層的時間為0.4/0.2=2秒，相鄰兩個貨架醫(yī)師行進時間為1/0.5=2秒。因此第1個智能存取單元的第1層地址坐標可以表示為（2,0），第3個智能存取單元的第7層可以表示為（14,4）。

表1 20個藥品揀選儲位信息

首先初始停靠坐標為（4，0），以隨機選取儲位的方式，對任意1～5，1～20個不同儲位進行出藥，分別通過改進的離散粒子群算法驗證其出藥最短路徑和正確性，表2、表3記錄了分別?？?個、20個儲藥位置的最優(yōu)揀選時間、最差揀選時間、平均揀選時間、最優(yōu)揀選時間到達率以及每次揀選算法運行所需要的CPU時間。圖2～圖3分別表示在種群規(guī)模為500時，從藥師自多回轉(zhuǎn)智能存取系統(tǒng)（4組回轉(zhuǎn)體）原點出發(fā)分別揀選5個、20個儲藥位，獲得最優(yōu)揀選路徑時的迭代進化曲線和最優(yōu)路徑路線圖。

表2 5個儲位時算法性能

表3 20個儲位時算法性能

圖2 5個儲位時的最優(yōu)揀選路徑及其進化曲線

圖3 20個儲位時的最優(yōu)揀選路徑及其進化曲線

改進的交換離散粒子群算法在求解單源最短路徑問題時具有如下特點：

1）算法在揀選點較少時（如10個以內(nèi)）優(yōu)化效果很好。根據(jù)表2，當遍歷點較少的時候，算法效果很好，當揀選儲位數(shù)量為5個時，算法能夠100%到達最優(yōu)揀選路徑。由圖2發(fā)現(xiàn)粒子群迭代發(fā)現(xiàn)最優(yōu)解的速度很快，迭代次數(shù)少于30次就獲得了最優(yōu)解；粒子種群規(guī)模達到200時，CPU運行時間僅需要0.13秒。

2）算法在?？奎c數(shù)較多的時候，效果較差。如表3，當儲藥槽數(shù)量上升到一定程度，到達20個點時，算法在單源最短路徑問題是時的效率顯著下降，能夠到達最優(yōu)揀選路徑的能力下降，即使種群規(guī)模達到500，最優(yōu)揀選路徑到達率也只有2.0%，且算法CPU運行時間達到1.8秒，可以認為算法基本失效。

3）算法的收斂速度很快。根據(jù)圖2、圖3的進化曲線圖發(fā)現(xiàn)，即使在?？奎c數(shù)達到20，種群規(guī)模達到500，粒子群發(fā)現(xiàn)最優(yōu)揀選路徑的迭代次數(shù)小于100。

因為每次揀選都是藥師都是從多回轉(zhuǎn)智能存取系統(tǒng)默認的初始點（1號柜）出發(fā)，按照處方需要出藥的種類對應(yīng)藥品儲位進行取藥，所以該問題中的停靠點數(shù)量應(yīng)該是需要出藥的藥品儲位數(shù)加1，如遍歷1-5號儲位時，實際?？奎c為6個，以此類推。表4為改進的離散粒子群算法揀選路徑優(yōu)化結(jié)果。

表4 改進的離散粒子群算法揀選路徑優(yōu)化結(jié)果

4 結(jié)論

垂直循環(huán)式藥柜是一種實用的自動化儲存設(shè)備，用作醫(yī)院盒裝藥品的智能存取。本文重點介紹了求解多回轉(zhuǎn)智能存取系統(tǒng)揀選時間優(yōu)化問題的一種解決思路。對路徑問題建立數(shù)學模型，把問題抽象成單源最短路徑問題，目標函數(shù)是求解揀選所需時間最小值。用圖論的方法對問題進行分析，在Matlab上利用改進的離散粒子群算法，針對山西某兒童醫(yī)院實際情況進行建模。結(jié)果表明，算法具有可行性，優(yōu)化效果良好，為實現(xiàn)組合垂直循環(huán)式藥柜控制算法提供了有價值的參考。