基于遺傳算法的自動醫藥冷庫倉位分配

任薈穎，鄒 鯤，孫 濤

（東華大學 機械工程學院，上海 201620）

0 引言

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

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

1 醫療冷庫的結構

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

冷庫的工作時，機器人收到藥品入庫的指令后，從傳送帶位置出發運動至該藥品應存的倉位取出存儲箱，送回傳送帶進行藥品的存取，最后再由機器人將存儲箱運回原倉位，完成一個存取過程。

2 醫療冷庫入庫倉位分配優化策略

2.1 系統數學模型

倉位分配問題實質上是一個優化問題，常見優化目標主要有存取時間短、成本低、倉位利用率高等[7]。由于醫療冷庫結構已經確定，冷庫運行的主要成本耗費在溫度控制上，存取藥品耗費的成本較低，這里不再考慮。冷庫的倉位數量也已經確定，不對倉位數量進行優化，即不考慮倉位利用率的問題。根據上文所述的優化需求分析，本文主要考慮藥品相關性和藥品出庫效率，提出了兩個自動分配倉位時的分配原則：1）周轉率高的藥品放在靠近醫療冷庫出入口的倉位；2）相關藥品放在相近位置。

圖1 冷庫整體結構示意圖

結合冷庫的實際工作流程，本文做出如下假設：

1）機器人起點即為出入庫點；

2）機器人在兩排貨架中心線運動；

3）每個倉位中只能放置一個存儲箱，每個存儲箱中只能放同一種藥品，機器人每次只搬運一個存儲箱；

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

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

圖2 冷庫布局示意圖

假設藥品要入庫的倉位坐標為（m，k），那么機器人從起點運動到此倉位，在水平方向的移動運行距離為X，垂直方向的移動距離為Y，水平方向的移動速度為vx，垂直方向的移動速度為vy，移動所需的總時間為tmk。

所以針對第一個原則，本文建立目標函數式(4)：

Trmk表示在第m層、第k列的藥品周轉率，T1表示藥品周轉率和機器人到達該倉位的時間的乘積之和。

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

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

在分配倉位時，要同時滿足目標函數1）和2），本文使用權重系數法，將多目標函數轉換成單目標函數求解。給目標1）分配的權重為v1，目標2）分配權重v2。則最終多目標倉位分配模型可以表示為：

2.2 遺傳算法的設計與實現

遺傳算法用生物進化模擬解決問題的過程，通過交叉、變異等操作產生下一代的解，并逐步淘汰適應度函數值低的解，進化多代之后產生近似最優解[8]。

1）染色體編碼與解碼

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

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

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

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

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

2）種群初始化和適應度評價

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

個體的適應度能夠體現個體的優劣程度，適應度高遺傳到下一代的概率就越大。本模型是求函數的極小值問題，所以將個體的目標函數值通過MATLAB中的ranking函數排序，返回個體的適應度值FitnV，來評價個體的優劣程度。

3）遺傳運算

本文采用MATLAB的遺傳算法優化工具箱，下面簡單介紹工具箱中的選擇、交叉、變異操作及相關的參數選取。

選擇運算是通過適應度評價選擇優質的個體，本文選用輪盤賭選擇法，個體進入下一代的概率就等于適應度值和所有個體適應度和的比值。設代溝GGAP=0.9，代溝保證子代與父代之間存在差異。編碼如下：

交叉是兩個個體交換部分基因生成新個體的主要方法。本文選用單點交叉的方式，在兩個個體中隨機設置交叉點互相交換部分基因，產生新個體。編碼如下：

變異屬于產生新個體的輔助手段，是將個體中的某些基因突變為另外的基因。本文采用基本位變異法，為每一個基因隨機生成一個0到1之間的數，如果該值小于變異概率，則對該基因執行變異操作，設變異概率為0.05。

本文給定最大遺傳代數Maxgen，當遺傳運算次數等于Maxgen后，停止運算并輸出適應度最優的個體，通過多次的運算發現，設最大遺傳代數為30代完全能夠得到系統的最優解，這里為留有一定的余量設最大遺傳代數為50代。

3 優化結果分析

下面將使用本文優化方法進行入庫時的倉位分配計算，再通過計算倉庫藥品出庫總時間與順序分配方法對比驗證優化結果。采用MATLAB編程實現遺傳算法，在主頻為2.70GHz，內存為6G的計算機上進行實驗。

由于實際倉庫中有600個倉位，計算數據量大，本文為驗證該優化方法的有效性僅選取36個倉位進行優化驗證。具體相關仿真數據設定如表1、表2所示。

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

首先根據以上數據進行順序分配，倉位分配結果如圖2所示。然后驗證本文的優化目標。

1）相關藥品就近原則驗證

此時只考慮原則2），即同一組的相關藥品放在相近的倉位。由圖3可以看出，目標函數隨著遺傳代數增減而趨于穩定，經過多次仿真運算將遺傳代數定為50代。最終輸出最后一代最優解的結果為：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 基本仿真數據設定

表2 藥品編號及其周轉率

圖3 v1=1，v2=0時遺傳代數和目標函數值

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

圖4 v1=0優化后的倉位分配結果

圖5 v1=0.2優化后的倉位分配結果

2）v1=0.2，v2=0.8

如重點考慮方便人工盤點，可將倉位分配的控制權重分別設為20%和80%，輸出最優解的結果為：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。將得到的最優解用圖5來表示，具有相關性的藥品基本分配在相近倉位，周轉率較大的比如23號、28號也在距離出入庫口較近的倉位，所以這種分配方案在滿足相關藥品相近的基礎上符合周轉率較大的藥品離出入庫口近的要求。

通過上述求解方法，可以算出任意滿足式(8)的v1，v2的倉位分配最優解，這里不再一一列出。經多次倉位分配仿真，可以證明本文建立的模型，在目標2）占目標函數權重較大的情況下，求解的結果可以實現相關貨物就近放置的目標。

3）提高出庫效率驗證

下面對目標1）進行驗證，為了驗證優化后結果提高了出庫效率，本文對采用順序分配倉位方法和采用優化方法的貨物出庫時間進行對比。

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

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

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

出庫效率及每組權重對應出庫時間如表3所示，出庫效率與權重分配的關系如圖6所示。

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

4 結束語

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

表3 優化后出庫所需的時間

圖6 隨權重v1的變化趨勢

1）在提高出庫效率目標函數所占權重較大時，與順序分配倉位相比，本文提出的倉位規劃方法在搜索最優入庫倉位時具有明顯的效果，能夠合理分配倉位，提高冷庫的運行效率；

2）在相關藥品就近放置目標函數所占權重較大時，本文提出的倉位規劃方法能夠有效實現將相關藥品就近放置的目標，由于相關藥品通常一起出庫，就近放置有利于在機器人故障或檢修期間進行人工取藥。

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