基于遺傳算法的自動(dòng)醫(yī)藥冷庫倉位分配

任薈穎，鄒 鯤，孫 濤

（東華大學(xué) 機(jī)械工程學(xué)院，上海 201620）

0 引言

根據(jù)數(shù)據(jù)分析結(jié)果，2020年我國醫(yī)藥市場的估值將達(dá)到1200億美元，屆時(shí)我國將成為全球第一大醫(yī)藥消費(fèi)國[1]。雖然醫(yī)藥市場前景廣闊，但在物流方面尤其是倉庫管理上仍存在一系列問題，對這方面的改進(jìn)迫在眉睫[2]。在自動(dòng)化倉庫管理方面一些學(xué)者進(jìn)行了相關(guān)的研究。例如：文獻(xiàn)[3]針對自動(dòng)化立體倉庫以出入庫效率和貨架穩(wěn)定性為目標(biāo)進(jìn)行建模并通過遺傳算法仿真求解；文獻(xiàn)[4]針對智能立體倉庫考慮了重量均勻分布、就近貨位選擇、備件品種均勻分布等因素提出了入庫貨位分配的優(yōu)化策略并編碼求解；文獻(xiàn)[5]將RFID技術(shù)結(jié)合改進(jìn)遺傳算法應(yīng)用于數(shù)字化倉儲的出入庫貨位優(yōu)先分配中；文獻(xiàn)[6]以工業(yè)生產(chǎn)型立體倉庫為研究對象，針對其出入庫口多、存儲貨物重量差異大和出入庫頻率高等問題進(jìn)行研究。

但大多數(shù)研究均未考慮被分配貨物之間的相互關(guān)聯(lián)。在醫(yī)藥冷庫中，不僅要求出入庫效率能夠得到提高，而且藥品相互關(guān)聯(lián)。具體表現(xiàn)為藥品可分為抗生素類藥品、注射劑類藥品等各個(gè)種類，同一類別的藥品在醫(yī)院中有較大的概率存在于同一張藥方中，即需要一起分配給患者。在本文的自動(dòng)冷庫中存在機(jī)器故障或檢修等極端情況需要進(jìn)行人工取藥，若藥品散亂放置，將大大增加人工取藥的勞動(dòng)量，降低出庫效率。

1 醫(yī)療冷庫的結(jié)構(gòu)

醫(yī)療冷庫的整體結(jié)構(gòu)示意圖如圖1所示。整個(gè)冷庫由機(jī)械手、貨架、操作平臺構(gòu)成，機(jī)械手位于兩組智能貨架中間，可以進(jìn)行X、Y、Z三個(gè)方向的運(yùn)動(dòng)，在Z方向上有三組貨架。每組貨架在X方向有20個(gè)倉位，Y方向有10個(gè)倉位。每個(gè)倉位中都配備一個(gè)規(guī)格統(tǒng)一的存儲箱，每個(gè)存儲箱中只能放置一種藥品，即每組貨架能容納20×10個(gè)存儲箱，目前冷庫中共有三組貨架能容納600個(gè)存儲箱。

冷庫的工作時(shí)，機(jī)器人收到藥品入庫的指令后，從傳送帶位置出發(fā)運(yùn)動(dòng)至該藥品應(yīng)存的倉位取出存儲箱，送回傳送帶進(jìn)行藥品的存取，最后再由機(jī)器人將存儲箱運(yùn)回原倉位，完成一個(gè)存取過程。

2 醫(yī)療冷庫入庫倉位分配優(yōu)化策略

2.1 系統(tǒng)數(shù)學(xué)模型

倉位分配問題實(shí)質(zhì)上是一個(gè)優(yōu)化問題，常見優(yōu)化目標(biāo)主要有存取時(shí)間短、成本低、倉位利用率高等[7]。由于醫(yī)療冷庫結(jié)構(gòu)已經(jīng)確定，冷庫運(yùn)行的主要成本耗費(fèi)在溫度控制上，存取藥品耗費(fèi)的成本較低，這里不再考慮。冷庫的倉位數(shù)量也已經(jīng)確定，不對倉位數(shù)量進(jìn)行優(yōu)化，即不考慮倉位利用率的問題。根據(jù)上文所述的優(yōu)化需求分析，本文主要考慮藥品相關(guān)性和藥品出庫效率，提出了兩個(gè)自動(dòng)分配倉位時(shí)的分配原則：1）周轉(zhuǎn)率高的藥品放在靠近醫(yī)療冷庫出入口的倉位；2）相關(guān)藥品放在相近位置。

圖1 冷庫整體結(jié)構(gòu)示意圖

結(jié)合冷庫的實(shí)際工作流程，本文做出如下假設(shè)：

1）機(jī)器人起點(diǎn)即為出入庫點(diǎn)；

2）機(jī)器人在兩排貨架中心線運(yùn)動(dòng)；

3）每個(gè)倉位中只能放置一個(gè)存儲箱，每個(gè)存儲箱中只能放同一種藥品，機(jī)器人每次只搬運(yùn)一個(gè)存儲箱；

4）機(jī)器人伸縮裝置叉取和釋放存儲箱的時(shí)間均較短，忽略不計(jì)。

根據(jù)以上條件對原則1）進(jìn)行建模。藥品的周轉(zhuǎn)率Trmk可以通過某一時(shí)段內(nèi)藥品出入庫的數(shù)量與藥品總庫存量的比值來表示。機(jī)器人與倉位之間的位置關(guān)系如圖2所示，機(jī)器人在水平方向距離貨架的初始距離是s，貨架共ny層、nx列，每個(gè)倉位的高為ly、長為lx。

圖2 冷庫布局示意圖

假設(shè)藥品要入庫的倉位坐標(biāo)為（m，k），那么機(jī)器人從起點(diǎn)運(yùn)動(dòng)到此倉位，在水平方向的移動(dòng)運(yùn)行距離為X，垂直方向的移動(dòng)距離為Y，水平方向的移動(dòng)速度為vx，垂直方向的移動(dòng)速度為vy，移動(dòng)所需的總時(shí)間為tmk。

所以針對第一個(gè)原則，本文建立目標(biāo)函數(shù)式(4)：

Trmk表示在第m層、第k列的藥品周轉(zhuǎn)率，T1表示藥品周轉(zhuǎn)率和機(jī)器人到達(dá)該倉位的時(shí)間的乘積之和。

針對原則2），設(shè)要入庫的藥品有W組，其中P組藥品具有相關(guān)性。在P組藥品中設(shè)任意兩個(gè)存儲箱的編號為SS1、SS2，其目標(biāo)倉位坐標(biāo)分別為（k1，m1）、（k2，m2）?；谠瓌t2）需將具有相關(guān)性的存儲箱放在相近位置，即使P組存儲箱的兩兩之間距離最小。由此可建立目標(biāo)函數(shù)2）為式(6)。約束條件為式(5)。

其中P表示這一批入庫藥品中的相關(guān)藥品的總組數(shù)，b為相關(guān)藥品的組序號，L2表示相關(guān)藥品間距離之和。這里的k1、k2、m1、m2為坐標(biāo)序列。

在分配倉位時(shí)，要同時(shí)滿足目標(biāo)函數(shù)1）和2），本文使用權(quán)重系數(shù)法，將多目標(biāo)函數(shù)轉(zhuǎn)換成單目標(biāo)函數(shù)求解。給目標(biāo)1）分配的權(quán)重為v1，目標(biāo)2）分配權(quán)重v2。則最終多目標(biāo)倉位分配模型可以表示為：

2.2 遺傳算法的設(shè)計(jì)與實(shí)現(xiàn)

遺傳算法用生物進(jìn)化模擬解決問題的過程，通過交叉、變異等操作產(chǎn)生下一代的解，并逐步淘汰適應(yīng)度函數(shù)值低的解，進(jìn)化多代之后產(chǎn)生近似最優(yōu)解[8]。

1）染色體編碼與解碼

把問題可行解從解空間轉(zhuǎn)化到搜索空間的方法稱為編碼，從遺傳算法解空間向問題空間轉(zhuǎn)換稱為解碼。編碼是設(shè)計(jì)遺傳算法的關(guān)鍵步驟，它的合理性會影響到遺傳運(yùn)算的效果。目前常用編碼方式有二進(jìn)制編碼、實(shí)數(shù)編碼和浮點(diǎn)數(shù)編碼等。

本問題若采用實(shí)數(shù)編碼，將要入庫的存儲箱放置的倉位編號作為一條染色體，如G1：[2,4,9,11,3,7]，表示1號存儲箱放置在2號倉位，2號存儲箱放置在4號倉位，以此類推。這種編碼方式簡潔明了，但是在后續(xù)的交叉、變異中會使種群中產(chǎn)生不合理的個(gè)體，如G2：[2,4,9,11,11,7]，此染色體對應(yīng)的表現(xiàn)型中，4號存儲箱和5號存儲箱都放置在11號倉位中，顯然這是無意義的解，如需避免無意義解，就需要設(shè)計(jì)特定的交叉和變異方式，增加了算法的設(shè)計(jì)難度。因此本文采用浮點(diǎn)數(shù)編碼的方式如下所述。

假設(shè)有N個(gè)空閑倉位和M個(gè)待入庫的存儲箱，隨機(jī)生成N個(gè)0到1之間的數(shù)字，即βi（i=1，2，3，…，N），組成向量（β1，β2，β3，…，βN）作為一條染色體。用βi在染色體中的位置表示空閑倉位的編號，并在染色體中按照βi的數(shù)值從小到大排序，前M個(gè)序號值就是待入庫的存儲箱需要進(jìn)入的倉位編號，這樣就避免在遺傳運(yùn)算中出現(xiàn)不合法個(gè)體。舉例說明：此時(shí)共有6個(gè)空閑倉位和5個(gè)要入庫的存儲箱，產(chǎn)生一條染色體G：G=[0.4,0.7,0.03,0.1,0.21,0.66]即基因0.4對應(yīng)倉位編號為1、0.7對應(yīng)倉位編號為2，以此類推。

將此染色體轉(zhuǎn)換為存儲箱在倉位中的擺放情況需要相應(yīng)的解碼操作：利用冒泡排序法對染色體G的基因進(jìn)行升序排列，獲取每個(gè)基因?qū)?yīng)的倉位編號索引序列F：F=[3,4,5,1,6,2]。

取序列中前5個(gè)值[3,4,5,1,6]即為待入庫的5個(gè)存儲箱的倉位分配方案。

2）種群初始化和適應(yīng)度評價(jià)

種群初始化方法是隨機(jī)生成一定數(shù)目的個(gè)體作為遺傳算法的初始種群。初始種群中每個(gè)個(gè)體都是一條染色體，代表一種倉位分配的方案，染色體中的基因數(shù)目是空閑倉位數(shù)。個(gè)體的數(shù)量代表種群的規(guī)模，對遺傳算法的計(jì)算結(jié)果和速度有重要影響。在根據(jù)實(shí)際情況多次試驗(yàn)后，設(shè)置種群中個(gè)體數(shù)目NIND為70。

個(gè)體的適應(yīng)度能夠體現(xiàn)個(gè)體的優(yōu)劣程度，適應(yīng)度高遺傳到下一代的概率就越大。本模型是求函數(shù)的極小值問題，所以將個(gè)體的目標(biāo)函數(shù)值通過MATLAB中的ranking函數(shù)排序，返回個(gè)體的適應(yīng)度值FitnV，來評價(jià)個(gè)體的優(yōu)劣程度。

3）遺傳運(yùn)算

本文采用MATLAB的遺傳算法優(yōu)化工具箱，下面簡單介紹工具箱中的選擇、交叉、變異操作及相關(guān)的參數(shù)選取。

選擇運(yùn)算是通過適應(yīng)度評價(jià)選擇優(yōu)質(zhì)的個(gè)體，本文選用輪盤賭選擇法，個(gè)體進(jìn)入下一代的概率就等于適應(yīng)度值和所有個(gè)體適應(yīng)度和的比值。設(shè)代溝GGAP=0.9，代溝保證子代與父代之間存在差異。編碼如下：

交叉是兩個(gè)個(gè)體交換部分基因生成新個(gè)體的主要方法。本文選用單點(diǎn)交叉的方式，在兩個(gè)個(gè)體中隨機(jī)設(shè)置交叉點(diǎn)互相交換部分基因，產(chǎn)生新個(gè)體。編碼如下：

變異屬于產(chǎn)生新個(gè)體的輔助手段，是將個(gè)體中的某些基因突變?yōu)榱硗獾幕?。本文采用基本位變異法，為每一個(gè)基因隨機(jī)生成一個(gè)0到1之間的數(shù)，如果該值小于變異概率，則對該基因執(zhí)行變異操作，設(shè)變異概率為0.05。

本文給定最大遺傳代數(shù)Maxgen，當(dāng)遺傳運(yùn)算次數(shù)等于Maxgen后，停止運(yùn)算并輸出適應(yīng)度最優(yōu)的個(gè)體，通過多次的運(yùn)算發(fā)現(xiàn)，設(shè)最大遺傳代數(shù)為30代完全能夠得到系統(tǒng)的最優(yōu)解，這里為留有一定的余量設(shè)最大遺傳代數(shù)為50代。

3 優(yōu)化結(jié)果分析

下面將使用本文優(yōu)化方法進(jìn)行入庫時(shí)的倉位分配計(jì)算，再通過計(jì)算倉庫藥品出庫總時(shí)間與順序分配方法對比驗(yàn)證優(yōu)化結(jié)果。采用MATLAB編程實(shí)現(xiàn)遺傳算法，在主頻為2.70GHz，內(nèi)存為6G的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。

由于實(shí)際倉庫中有600個(gè)倉位，計(jì)算數(shù)據(jù)量大，本文為驗(yàn)證該優(yōu)化方法的有效性僅選取36個(gè)倉位進(jìn)行優(yōu)化驗(yàn)證。具體相關(guān)仿真數(shù)據(jù)設(shè)定如表1、表2所示。

表2中藥品周轉(zhuǎn)率為某星期32種藥品的周轉(zhuǎn)率，每種藥品放在一個(gè)存儲箱中，其中1～5、6～11、12～18、19～22、23～26、27～32存儲箱中藥品各自相關(guān)。

首先根據(jù)以上數(shù)據(jù)進(jìn)行順序分配，倉位分配結(jié)果如圖2所示。然后驗(yàn)證本文的優(yōu)化目標(biāo)。

1）相關(guān)藥品就近原則驗(yàn)證

此時(shí)只考慮原則2），即同一組的相關(guān)藥品放在相近的倉位。由圖3可以看出，目標(biāo)函數(shù)隨著遺傳代數(shù)增減而趨于穩(wěn)定，經(jīng)過多次仿真運(yùn)算將遺傳代數(shù)定為50代。最終輸出最后一代最優(yōu)解的結(jié)果為：17 21 23 15 11 26 14 8 4 3 9 27 34 28 22 25 32 33 12 5 18 10 35 36 24 6 19 2 1 20 13 7。

表1 基本仿真數(shù)據(jù)設(shè)定

表2 藥品編號及其周轉(zhuǎn)率

圖3 v1=1，v2=0時(shí)遺傳代數(shù)和目標(biāo)函數(shù)值

將優(yōu)化后的分配方案用圖4來表示，可以看出各組具有相關(guān)性的藥品都相鄰放置，符合原則2），但是一些周轉(zhuǎn)率大的藥品如6號、12號離出入庫口距離較遠(yuǎn)。

圖4 v1=0優(yōu)化后的倉位分配結(jié)果

圖5 v1=0.2優(yōu)化后的倉位分配結(jié)果

2）v1=0.2，v2=0.8

如重點(diǎn)考慮方便人工盤點(diǎn)，可將倉位分配的控制權(quán)重分別設(shè)為20%和80%，輸出最優(yōu)解的結(jié)果為：8 26 7 19 13 36 16 24 35 17 30 18 34 15 22 21 28 27 29 20 32 14 9 5 23 6 1 11 3 4 10 2。將得到的最優(yōu)解用圖5來表示，具有相關(guān)性的藥品基本分配在相近倉位，周轉(zhuǎn)率較大的比如23號、28號也在距離出入庫口較近的倉位，所以這種分配方案在滿足相關(guān)藥品相近的基礎(chǔ)上符合周轉(zhuǎn)率較大的藥品離出入庫口近的要求。

通過上述求解方法，可以算出任意滿足式(8)的v1，v2的倉位分配最優(yōu)解，這里不再一一列出。經(jīng)多次倉位分配仿真，可以證明本文建立的模型，在目標(biāo)2）占目標(biāo)函數(shù)權(quán)重較大的情況下，求解的結(jié)果可以實(shí)現(xiàn)相關(guān)貨物就近放置的目標(biāo)。

3）提高出庫效率驗(yàn)證

下面對目標(biāo)1）進(jìn)行驗(yàn)證，為了驗(yàn)證優(yōu)化后結(jié)果提高了出庫效率，本文對采用順序分配倉位方法和采用優(yōu)化方法的貨物出庫時(shí)間進(jìn)行對比。

首先假設(shè)在該星期這32種藥品的庫存量均為50個(gè)，并且每次出庫時(shí)只取一種藥品，則根據(jù)表2周轉(zhuǎn)率，可以得出各個(gè)藥品出庫次數(shù)為各藥品周轉(zhuǎn)率與其庫存量之積。

根據(jù)式(4)該倉庫全部貨物本月完成出庫所需要的時(shí)間ts為：

設(shè)根據(jù)式(9)計(jì)算得到的順序分配倉位所用出庫時(shí)間為tsx、優(yōu)化后所用出庫時(shí)間為tcl，則優(yōu)化后能夠提高的出庫效率為：

出庫效率及每組權(quán)重對應(yīng)出庫時(shí)間如表3所示，出庫效率與權(quán)重分配的關(guān)系如圖6所示。

由綜上所述，按照本文所建模型在目標(biāo)1）目標(biāo)函數(shù)所占權(quán)重較大的情況下通過遺傳算法求解后的倉位分配能夠有效減少出庫所用的時(shí)間，提升出庫效率。

4 結(jié)束語

在實(shí)際情況中，權(quán)重可以由冷庫管理員根據(jù)冷庫實(shí)際情況設(shè)定，冷庫建成初期故障較多，可提高v2的比重以使倉位分配結(jié)果方便人工取藥等工作，冷庫運(yùn)行穩(wěn)定后，可提高v1比重，提高藥品出庫效率。通過上述運(yùn)算結(jié)果可以看出：

表3 優(yōu)化后出庫所需的時(shí)間

圖6 隨權(quán)重v1的變化趨勢

1）在提高出庫效率目標(biāo)函數(shù)所占權(quán)重較大時(shí)，與順序分配倉位相比，本文提出的倉位規(guī)劃方法在搜索最優(yōu)入庫倉位時(shí)具有明顯的效果，能夠合理分配倉位，提高冷庫的運(yùn)行效率；

2）在相關(guān)藥品就近放置目標(biāo)函數(shù)所占權(quán)重較大時(shí)，本文提出的倉位規(guī)劃方法能夠有效實(shí)現(xiàn)將相關(guān)藥品就近放置的目標(biāo)，由于相關(guān)藥品通常一起出庫，就近放置有利于在機(jī)器人故障或檢修期間進(jìn)行人工取藥。

針對本文機(jī)械系統(tǒng)的特點(diǎn)，機(jī)器人一次只能取一種藥品到出庫口，相關(guān)藥品就近放置對提高出庫效率無明顯的效果，但對于另外一種帶有緩存區(qū)的機(jī)械系統(tǒng)來說，機(jī)器人可以取多種藥品放置在緩存區(qū)，然后一次全部出庫，相關(guān)藥品就近放置能在一定程度上提高出庫效率，相關(guān)學(xué)者也可針對本文目標(biāo)2）對帶有緩存區(qū)的機(jī)械系統(tǒng)做相關(guān)探索。