貨到人揀選系統(tǒng)訂單分配問題研究

□ 范繼東

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

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

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

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

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

1 問題分析

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

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

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

2 問題描述

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

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

>每個揀選臺需要揀選的訂單已知；

>一種SKU只存儲在一個料箱中；

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

>不同SKU揀選一個或揀選一次的時間為固定值tpick；

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

Ttj：表示SKUj在揀選臺t的揀選完成時間，將同一個揀選臺揀選順序為最后的SKU的揀選完成時間作為該揀選臺的揀選完成時間，即Tt=Ttk，其中rtk=maxrtj，?j=1,…,M；

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

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

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

(3)

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

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

min maxTt=TPt+TWt

(4)

(5)

(6)

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

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

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

本文對標準遺傳算法在以下兩方面做出了改進：

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

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

針對上述問題，設(shè)想了兩個改進策略。策略一是在每次交叉和變異操作時，直至生成合法子代，交叉和變異操作才會終止，采用這種策略可以提高種群的多樣性，從而提高算法的局部搜索能力，但是這種方式在系統(tǒng)規(guī)模比較大的情況下算法易陷入交叉和變異的死循環(huán)，導(dǎo)致算法運行時間過長。策略二是交叉和變異概率不取定值，而是根據(jù)種群特征自適應(yīng)變化。在算法運行初期，對適應(yīng)度高的個體，應(yīng)減少交叉和變異的概率，以避免破壞優(yōu)秀個體，在算法運行后期，因為種群多樣性減少，應(yīng)提高交叉和變異的概率，以增加種群的多樣性。不同個體的交叉和變異概率如式(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表示個體的適應(yīng)度，fmax表示該代的最大適應(yīng)度，favg表示該代的平均適應(yīng)度，k3，k4為常數(shù)，且k3,k4≤1。本文改進遺傳算法中采用第二種策略，即采用自適應(yīng)的交叉和變異概率。

4.2 鄰域搜索

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

改進遺傳算法步驟如圖1所示：

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

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

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

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

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

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

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

5 仿真實驗驗證

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

(13)

(14)

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

5.1 非聚類訂單分配策略仿真實例驗證

非聚類訂單分配策略是指訂單按照到達的先后順序或者隨機分配到揀選臺，而訂單對應(yīng)的SKU所在的貨箱也隨機到達揀選臺，所以可以通過編寫程序來隨機生成貨箱到達序列矩陣來模擬實際系統(tǒng)中的隨機到達。在中小規(guī)模系統(tǒng)中，分別在低耦合、中度耦合、高度耦合三種情況下進行實驗。基礎(chǔ)參數(shù)設(shè)置為：程序運行次數(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)中，隨著耦合度的增加，非聚類訂單分配策略的平均偏離距、偏離距標準差和平均求解時間都呈現(xiàn)上升趨勢，即求解性能逐漸降低。

5.2 標準遺傳算法仿真實例驗證

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

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

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

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

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

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

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

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

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

6 結(jié)論

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