□ 范繼東

(南京醫(yī)藥股份有限公司，江蘇 南京 210000)

近些年，國家出臺了一系列政策對醫(yī)藥行業(yè)進(jìn)行改革，如“兩票制”、“分級診療”、“處方藥外流”和“處方藥網(wǎng)上銷售”等，這些政策對醫(yī)藥流通行業(yè)的影響不容小覷。我國推行的醫(yī)藥政策對醫(yī)藥流通行業(yè)的影響主要體現(xiàn)在行業(yè)集中度提升、藥企銷售渠道下沉和醫(yī)藥零售終端崛起三方面，其在物流系統(tǒng)中主要表現(xiàn)為訂單總量增加、訂單碎片化明顯、拆零揀選需求增加等。

相比于其他行業(yè)，醫(yī)藥物流更加注重時(shí)效性。如何在有限的揀選作業(yè)時(shí)間內(nèi)，完成大量拆零訂單的揀選作業(yè)成為醫(yī)藥流通行業(yè)普遍面臨的重大難題。目前的訂單揀選系統(tǒng)主要分為三類：“人到貨”揀選系統(tǒng)、“貨到人”揀選系統(tǒng)和全自動化揀選系統(tǒng)。

現(xiàn)有的基于多層穿梭車的“貨到人”揀選系統(tǒng)存在瓶頸環(huán)節(jié)，首先是庫端出入庫料箱提升機(jī)的效率無法與多層穿梭車每層小車的料箱搬運(yùn)出入庫效率進(jìn)行匹配，導(dǎo)致多層穿梭車的出入庫能力受限；其次是訂單分批策略和訂單分配策略匹配不當(dāng)，容易導(dǎo)致各個(gè)揀選臺之間的訂單耦合問題，一旦任務(wù)料箱被占用，受影響的其他揀選臺無法進(jìn)行揀選作業(yè)，導(dǎo)致整個(gè)系統(tǒng)不能達(dá)到最優(yōu)的揀選效率。相比于其他行業(yè)，醫(yī)藥流通行業(yè)的訂單耦合問題尤為突出，這是由其行業(yè)特點(diǎn)所決定的。藥品作為一種特殊商品，在流通過程中有專門的規(guī)范來對其進(jìn)行約束，即《藥品經(jīng)營質(zhì)量管理規(guī)范》(GSP)。根據(jù)GSP的相關(guān)規(guī)定，藥品出入庫需要基于批號先進(jìn)先出，某種藥品某批次的尾箱儲存在一個(gè)料箱中的情況在醫(yī)藥物流中心較為常見，相比于其他行業(yè)同一種商品的不同批次可以同時(shí)出庫進(jìn)行揀選作業(yè)，醫(yī)藥流通行業(yè)的這種特點(diǎn)會使訂單耦合問題更加嚴(yán)重。

所以，本文針對多層穿梭車的“貨到人”揀選系統(tǒng)的訂單分配問題進(jìn)行研究，求解得出訂單揀選完成時(shí)間最短的貨箱到達(dá)順序，既能夠滿足醫(yī)藥物流中心迫切需要提高揀選效率的需求，也可以為行業(yè)應(yīng)用提供一些參考。

1 問題分析

訂單分配是指按照一定的分配規(guī)則將某一波次的訂單分配到揀選臺，不同的訂單分配結(jié)果對應(yīng)不同的揀選完成時(shí)間。通過合理的訂單分配，可以增加揀選臺內(nèi)部的訂單任務(wù)耦合，降低揀選臺之間的訂單任務(wù)耦合，減少不必要的等待時(shí)間，從而提高揀選效率。劉明等人將訂單排序問題建模為多屬性決策問題，并根據(jù)拓展的理想解法(TOPSIS)選擇出最合適的訂單排序方案[1]。王旭坪等人以總服務(wù)時(shí)間最小和分區(qū)任務(wù)量均衡為目標(biāo)，建立了雙目標(biāo)訂單合并優(yōu)化模型，并采用雙目標(biāo)遺傳算法進(jìn)行求解。結(jié)果表明并行分區(qū)訂單合并優(yōu)化尤其適用于小批量訂單的分區(qū)揀選[2]。吳思沛研究了制造業(yè)B2C模式下的基于多層穿梭車的自動分揀系統(tǒng)設(shè)計(jì)與訂單分配優(yōu)化，以出入庫次數(shù)最少為目標(biāo)，建立數(shù)學(xué)模型，并利用聚類算法求解該模型[3]。Claeys等人對“貨到人”揀選系統(tǒng)的訂單流動時(shí)間進(jìn)行研究，利用公式求解出了訂單流動時(shí)間的界限，結(jié)果對于料箱到達(dá)率的選擇具有重大意義[4]。

在基于多層穿梭車的“貨到人”揀選系統(tǒng)中，訂單分配是影響系統(tǒng)揀選效率的重要問題。傳統(tǒng)的訂單分配策略是非聚類訂單分配策略，現(xiàn)有的研究的訂單分配問題在醫(yī)藥行業(yè)的研究幾乎是空白，而且現(xiàn)有的算法基本無特定應(yīng)用場景，皆為普適型的算法。在醫(yī)藥物流中心，因其特殊的批次批號管理規(guī)定，訂單耦合問題會比其他行業(yè)更突出。

本文將對訂單分配問題進(jìn)行優(yōu)化，在揀選臺訂單確定的情況下，建立訂單解耦模型，并采用自適應(yīng)鄰域搜索遺傳算法求解訂單分配問題求解出優(yōu)化后的每個(gè)揀選臺任務(wù)料箱的揀選順序，通過合理分配任務(wù)料箱到達(dá)每個(gè)揀選臺的順序，來盡量減少因訂單耦合而產(chǎn)生的等待時(shí)間，從而最小化訂單揀選時(shí)間，提升系統(tǒng)處理能力。

2 問題描述

在基于多層穿梭車的“貨到人”揀選系統(tǒng)中，料箱由多層穿梭車和料箱提升機(jī)相互配合搬運(yùn)出庫，再經(jīng)輸送輥道傳送至揀選臺。這種“貨到人”系統(tǒng)的瓶頸主要在于兩點(diǎn)，一是多層穿梭車和出入庫料箱提升機(jī)的配合問題；二是因訂單分配產(chǎn)生的訂單耦合問題。后者是本文研究的主要問題。

訂單分配問題的目標(biāo)是該批次訂單的揀選完成時(shí)間最短，而揀選完成時(shí)間包括三部分，任務(wù)料箱出庫時(shí)間、揀選時(shí)間和等待時(shí)間。任務(wù)料箱出庫時(shí)間是指揀選臺需要的任務(wù)料箱從倉庫中出庫到達(dá)揀選臺的時(shí)間；揀選時(shí)間是指揀選人員揀選任務(wù)貨箱的時(shí)間，一般與揀選次數(shù)成正比；等待時(shí)間是指因任務(wù)料箱被其他揀選臺鎖定，揀選人員等待料箱到達(dá)而產(chǎn)生的空閑時(shí)間，這部分時(shí)間是由于訂單耦合產(chǎn)生的。由于任務(wù)料箱出庫時(shí)間對揀選完成時(shí)間的趨勢影響不大，并且還涉及多層穿梭車和料箱提升機(jī)的配合問題，所以本文忽略這部分時(shí)間，在研究過程中，只考慮揀選時(shí)間和等待時(shí)間之和作為揀選完成時(shí)間。系統(tǒng)假設(shè)條件如下：

>每個(gè)揀選臺需要揀選的訂單已知；

>一種SKU只存儲在一個(gè)料箱中；

>單個(gè)揀選臺的揀選完成時(shí)間為揀選時(shí)間和等待時(shí)間之和，任務(wù)料箱出庫時(shí)間忽略不計(jì)；

>不同SKU揀選一個(gè)或揀選一次的時(shí)間為固定值tpick；

>揀選臺不存在緩存區(qū)。

3 訂單分配優(yōu)化模型

本文提出的訂單分配優(yōu)化模型存在以下變量，模型中所有變量均為非負(fù)整數(shù)：

S：系統(tǒng)中工作站的數(shù)目，t=1,…,S；

M：系統(tǒng)中SKU的數(shù)目，j=1,…,M；

xtj：表示揀選臺t是否需要揀選SKUj，需要揀選則賦值為1，不需要?jiǎng)t賦值為0；

weighttj：表示揀選臺t中SKUj所需的揀選數(shù)量或揀選次數(shù)，如果需要揀選則為需要揀選的次數(shù)或數(shù)量，如果不需要揀選則賦值為0；

mtj：輔助變量，用于尋找下一個(gè)揀選位置：

(1)

式(1)為mtj的初始化矩陣，其中Max為一個(gè)很大的數(shù)，當(dāng)所對應(yīng)的揀選位置揀選完成后，將該揀選位置對應(yīng)的mtj賦值為Max。

ntj：輔助變量，用于尋找下一個(gè)揀選位置：

(2)

式(2)為ntj的初始化矩陣，其中Max為一個(gè)很大的數(shù)，當(dāng)所對應(yīng)的揀選位置揀選完成后，將該揀選位置對應(yīng)的ntj賦值為Max。

Ttj：表示SKUj在揀選臺t的揀選完成時(shí)間，將同一個(gè)揀選臺揀選順序?yàn)樽詈蟮腟KU的揀選完成時(shí)間作為該揀選臺的揀選完成時(shí)間，即Tt=Ttk，其中rtk=maxrtj，?j=1,…,M；

twtj：表示當(dāng)揀選臺t需要揀選SKUj時(shí)的等待時(shí)間；

tpick：揀貨員揀選一個(gè)商品或做一次揀選動作所需要的平均時(shí)間；

tptt′：任務(wù)料箱從揀選臺t到達(dá)揀選臺t′的路程時(shí)間。tptt′分為兩種情況，一種是順序移動，例如從1號揀選臺移動到2號揀選臺，另一種是逆序移動，例如從2號揀選臺移動到1號揀選臺：

(3)

其中，t為當(dāng)前揀選工作站，t′為目標(biāo)揀選工作站，S為系統(tǒng)揀選工作站總數(shù)量，tp為任務(wù)料箱在兩個(gè)相鄰工作站之間流轉(zhuǎn)的時(shí)間，tfix為第S個(gè)工作站到第1個(gè)工作站的折返路程時(shí)間。

由上述可知，本文旨在最小化訂單揀選完成時(shí)間，最后一個(gè)完成揀選任務(wù)的揀選臺的揀選完成時(shí)間即為該批訂單的揀選完成時(shí)間，所以本文目標(biāo)函數(shù)為最小化各個(gè)揀選臺中最大的揀選完成時(shí)間。

min maxTt=TPt+TWt

(4)

(5)

(6)

其中，TPt表示揀選臺t所需的揀選時(shí)間；TWt表示因訂單耦合，揀選臺t的等待時(shí)間，其中rtj′=rtj-1，ct′j=ctj-1。

本文約束條件如下：

rtj≠rtj′

(7)

ctj≠ct′j

(8)

ctj=rtj=1

(9)

mt′j′=minmt′j,nt′j′=minntj′

(10)

其中，式(7)表示同一個(gè)揀選臺，任意兩個(gè)任務(wù)料箱的揀選順序不能相同，對?j,j′=1,…,M,j≠j′,rtj,rtj′∈N*,weighttj,weighttj′≠0成立；式(8)表示同一個(gè)任務(wù)料箱在不同揀選臺的揀選順序不能相同，對?t,t′=1,…,S,t≠t′,ctj,ct′j∈N*,weighttj,weightt′j≠0成立；式(9)表示個(gè)體必須存在揀選起始點(diǎn)，即?t=1,…,S,J=1,…,M，使得某一個(gè)SKU在某揀選臺的揀選順序?yàn)?，并且該SKU在不同的揀選臺之中到達(dá)該揀選臺的順序也為1；式(10)表示必須存在下一個(gè)揀選位置可供揀選，以防死鎖的情況出現(xiàn)，即每次揀選完成之后，必須存在一個(gè)位置，該位置在mtj中為其對應(yīng)行的最小值，在ntj中為其對應(yīng)列的最小值。

4 自適應(yīng)鄰域搜索遺傳算法求解訂單分配問題

雖然遺傳算法具有潛在的并行性及問題領(lǐng)域無關(guān)性等優(yōu)點(diǎn)，但是，遺傳算法也存在一些眾所周知的缺點(diǎn)，如隨著種群規(guī)模的增加，交叉操作生成合法個(gè)體的概率逐漸降低，致使交叉操作不能將父代的價(jià)值遺傳到子代，即編碼不具有拉馬克性質(zhì)；整數(shù)編碼方式中，交叉和變異操作大概率會生成不合法個(gè)體，導(dǎo)致種群多樣性無明顯提升，算法易陷入“早熟”；某些參數(shù)的選擇一般依靠經(jīng)驗(yàn)，如種群規(guī)模，迭代次數(shù)，交叉和變異概率等參數(shù)的選擇可能也會使算法陷入局部最優(yōu)解。

本文對標(biāo)準(zhǔn)遺傳算法在以下兩方面做出了改進(jìn)：

4.1 自適應(yīng)交叉和變異概率

在標(biāo)準(zhǔn)遺傳算法中，根據(jù)經(jīng)驗(yàn)將交叉和變異概率設(shè)為定值。在每次交叉操作后，會存在四個(gè)個(gè)體，即兩個(gè)父代和新生成的兩個(gè)子代，計(jì)算這四個(gè)個(gè)體的適應(yīng)度，如果交叉生成的子代不合法，則直接剔除該子代，在剩下的個(gè)體中，選擇適應(yīng)度值最優(yōu)的兩個(gè)個(gè)體遺傳到下一代。變異操作與交叉操作類似，如果變異后個(gè)體不合法，則直接剔除，保留變異前個(gè)體到下一代，如果變異后個(gè)體合法，則計(jì)算兩者適應(yīng)度的值，保留其中最優(yōu)的個(gè)體到下一代。但是，隨著系統(tǒng)規(guī)模的增大，交叉和變異之后生成不合法個(gè)體的概率增加，致使保留到下一代種群中的個(gè)體幾乎皆為父代個(gè)體，導(dǎo)致種群多樣性降低，易在中大規(guī)模系統(tǒng)中陷入局部最優(yōu)解。

針對上述問題，設(shè)想了兩個(gè)改進(jìn)策略。策略一是在每次交叉和變異操作時(shí)，直至生成合法子代，交叉和變異操作才會終止，采用這種策略可以提高種群的多樣性，從而提高算法的局部搜索能力，但是這種方式在系統(tǒng)規(guī)模比較大的情況下算法易陷入交叉和變異的死循環(huán)，導(dǎo)致算法運(yùn)行時(shí)間過長。策略二是交叉和變異概率不取定值，而是根據(jù)種群特征自適應(yīng)變化。在算法運(yùn)行初期，對適應(yīng)度高的個(gè)體，應(yīng)減少交叉和變異的概率，以避免破壞優(yōu)秀個(gè)體，在算法運(yùn)行后期，因?yàn)榉N群多樣性減少，應(yīng)提高交叉和變異的概率，以增加種群的多樣性。不同個(gè)體的交叉和變異概率如式(11)和式(12)所示：

(11)

(12)

式(11)表示自適應(yīng)的交叉概率，其中f表示父代中適應(yīng)度的較大值，fmax表示該代的最大適應(yīng)度，favg表示該代的平均適應(yīng)度，k1，k2為常數(shù)，且k1,k2≤1。式(12)表示自適應(yīng)的變異概率，其中f表示個(gè)體的適應(yīng)度，fmax表示該代的最大適應(yīng)度，favg表示該代的平均適應(yīng)度，k3，k4為常數(shù)，且k3,k4≤1。本文改進(jìn)遺傳算法中采用第二種策略，即采用自適應(yīng)的交叉和變異概率。

4.2 鄰域搜索

在標(biāo)準(zhǔn)遺傳算法中，正是由于算法的局部搜索能力不夠，才會導(dǎo)致算法易陷入局部最優(yōu)解。為了解決這個(gè)問題，在算法中引入了鄰域搜索，采用局部搜索算法來提高算法的局部搜索能力。鄰域搜索有很多種方法，如爬山法、貪心算法、模擬退火算法和禁忌搜索算法等。在本文中采用貪心算法對每個(gè)個(gè)體進(jìn)行局部搜索，即在局部搜索過程中，保留其中適應(yīng)度最高的個(gè)體。

改進(jìn)遺傳算法步驟如圖1所示：

①在算法搜索空間內(nèi)隨機(jī)生成初始種群。在種群生成過程中，如果生成的個(gè)體不合法，則重新生成新個(gè)體，直到生成的個(gè)體合法，以保證初始種群均為合法個(gè)體。

②對種群進(jìn)行選擇操作。首先，根據(jù)適應(yīng)度對種群進(jìn)行精英保留，將種群中最好的個(gè)體保留，其次，進(jìn)行輪盤賭選擇，最后，選擇種群中適應(yīng)度值最小的個(gè)體并將其從種群中剔除，將之前精英保留的個(gè)體加入到種群中。

③對種群進(jìn)行交叉操作。按照自適應(yīng)交叉概率的公式對個(gè)體進(jìn)行交叉操作。將選擇操作之后的個(gè)體按照順序兩兩進(jìn)行交叉操作，如果生成的子代個(gè)體不合法，則將其從中剔除，之后從兩個(gè)父代和生成的合法子代中選擇適應(yīng)度最高的兩個(gè)個(gè)體，并將其保留至下一代，以此類推，直至整個(gè)種群交叉完成。

④對種群進(jìn)行變異操作。按照自適應(yīng)變異概率的公式對個(gè)體進(jìn)行變異操作。將交叉操作之后的個(gè)體隨機(jī)選取兩個(gè)基因位置進(jìn)行互換，如果生成的個(gè)體不合法，則將其從種群中剔除，保留變異前個(gè)體到下一代，如果生成的個(gè)體合法，則比較變異前個(gè)體和變異后個(gè)體適應(yīng)度的值，選取適應(yīng)度較高的個(gè)體遺傳到下一代。

⑤對種群進(jìn)行鄰域搜索。對變異之后的每一個(gè)個(gè)體，在其鄰域進(jìn)行搜索，并計(jì)算其鄰域個(gè)體的適應(yīng)度，利用貪心策略保留其中適應(yīng)度最高的個(gè)體。

⑥終止條件判定。判斷算法是否滿足終止條件，對本文來說，即算法是否到達(dá)最大迭代次數(shù)，如果到達(dá)最大迭代次數(shù)，則終止運(yùn)算，如果未達(dá)到最大迭代次數(shù)，則返回步驟(2)。

圖1 自適應(yīng)鄰域搜索遺傳算法流程圖

5 仿真實(shí)驗(yàn)驗(yàn)證

對模型和算法進(jìn)行了仿真實(shí)驗(yàn)驗(yàn)證。分別驗(yàn)證了非聚類訂單分配策略、標(biāo)準(zhǔn)遺傳算法和自適應(yīng)鄰域搜索遺傳算法在中小規(guī)模訂單系統(tǒng)中的性能，包括其解的優(yōu)劣與運(yùn)算效率。為了公正地評價(jià)解的優(yōu)劣，本文引入了平均偏離距R(s,M)與偏離距標(biāo)準(zhǔn)差σ(s,M)兩個(gè)評價(jià)指標(biāo)，計(jì)算公式如下：

(13)

(14)

式(13)為平均偏離距的計(jì)算公式，是對解的平均評價(jià)，其中，M為算法的運(yùn)行次數(shù)，ri為第i次運(yùn)行算法求得的解，r*為模型的理論最優(yōu)解，‖ri-r*‖為(ri-r*)的2-范數(shù)。式(14)為偏離距標(biāo)準(zhǔn)差的計(jì)算公式，用于評價(jià)解的分散程度，參數(shù)含義與式(13)中相同。

5.1 非聚類訂單分配策略仿真實(shí)例驗(yàn)證

非聚類訂單分配策略是指訂單按照到達(dá)的先后順序或者隨機(jī)分配到揀選臺，而訂單對應(yīng)的SKU所在的貨箱也隨機(jī)到達(dá)揀選臺，所以可以通過編寫程序來隨機(jī)生成貨箱到達(dá)序列矩陣來模擬實(shí)際系統(tǒng)中的隨機(jī)到達(dá)。在中小規(guī)模系統(tǒng)中，分別在低耦合、中度耦合、高度耦合三種情況下進(jìn)行實(shí)驗(yàn)。基礎(chǔ)參數(shù)設(shè)置為：程序運(yùn)行次數(shù)為10次，中小規(guī)模系統(tǒng)的揀選臺數(shù)量為4，SKU數(shù)目為10。低耦合度為0.3，中等耦合為0.5，高度耦合為0.8。此處耦合度的概念是指揀選臺之間的耦合次數(shù)占系統(tǒng)最多耦合次數(shù)的比例。

表1 中小規(guī)模系統(tǒng)中非聚類訂單分配策略的求解性能

由表1可知，在中小規(guī)模系統(tǒng)中，隨著耦合度的增加，非聚類訂單分配策略的平均偏離距、偏離距標(biāo)準(zhǔn)差和平均求解時(shí)間都呈現(xiàn)上升趨勢，即求解性能逐漸降低。

5.2 標(biāo)準(zhǔn)遺傳算法仿真實(shí)例驗(yàn)證

采用標(biāo)準(zhǔn)遺傳算法來求解訂單分配優(yōu)化模型?；A(chǔ)參數(shù)設(shè)置為：種群規(guī)模為100，最大迭代次數(shù)為200，交叉概率為0.9，變異概率為0.1，程序運(yùn)行次數(shù)為10次。其余參數(shù)設(shè)置與第5.1節(jié)相同。

表2 中小規(guī)模系統(tǒng)中標(biāo)準(zhǔn)遺傳算法的求解性能

由表2可知，在中小規(guī)模的系統(tǒng)中，隨著耦合度的增加，標(biāo)準(zhǔn)遺傳算法的平均偏離距、偏離距標(biāo)準(zhǔn)差和平均求解時(shí)間都在增加，即隨著耦合度的增加，標(biāo)準(zhǔn)遺傳算法的求解結(jié)果與最優(yōu)解的偏差越來越大，分散程度越來越大，且算法求解時(shí)間越來越長。

5.3 自適應(yīng)鄰域搜索遺傳算法仿真實(shí)例驗(yàn)證

采用自適應(yīng)鄰域搜索遺傳算法來求解訂單分配優(yōu)化模型?；A(chǔ)參數(shù)設(shè)置與標(biāo)準(zhǔn)遺傳算法一致，其中交叉概率由式(11)決定，k1=0.9，k2=1，變異概率由式(12)決定，k3=0.1，k4=1。

表3 中小規(guī)模系統(tǒng)中自適應(yīng)鄰域搜索遺傳算法的求解性能

由表3可知，在中小規(guī)模系統(tǒng)中，隨著耦合度的增加，自適應(yīng)鄰域搜索遺傳算法的平均偏離距、偏離距標(biāo)準(zhǔn)差和平均求解時(shí)間均增加，即隨著系統(tǒng)耦合度的增加，算法的求解性能下降。

表4 標(biāo)準(zhǔn)遺傳算法與自適應(yīng)鄰域搜索遺傳算法性能對比

通過對比表1和表4可知，標(biāo)準(zhǔn)遺傳算法和自適應(yīng)鄰域搜索的平均偏離距和偏離距標(biāo)準(zhǔn)差均優(yōu)于非聚類訂單分配策略，只是在求解效率上劣于非聚類訂單分配策略。從表1可知，非聚類訂單分配策略的結(jié)果受隨機(jī)性影響較大，解的差異性和分散程度都太大，一旦求解不當(dāng)，還可能會出現(xiàn)死鎖情況，所以不適用于求解訂單分配模型。

6 結(jié)論

通過將標(biāo)準(zhǔn)遺傳算法與自適應(yīng)鄰域搜索遺傳算法兩者的求解性能進(jìn)行對比，可以看到，無論是求解小規(guī)模系統(tǒng)還是求解中小規(guī)模系統(tǒng)，無論是低耦合度、中耦合度還是高耦合度，自適應(yīng)鄰域搜索遺傳算法的平均偏離距和偏離距標(biāo)準(zhǔn)差都小于標(biāo)準(zhǔn)遺傳算法，即自適應(yīng)鄰域搜索遺傳算法求得的解普遍優(yōu)于標(biāo)準(zhǔn)遺傳算法，且系統(tǒng)規(guī)模越大，耦合度越高，這種優(yōu)勢表現(xiàn)得越明顯。因此，在醫(yī)藥物流中心的多層穿梭車的“貨到人”揀選系統(tǒng)中的訂單分配問題中采用鄰域搜索的自適應(yīng)遺傳算法有較好的應(yīng)用價(jià)值。