紀佳溥，岳秀江，趙劍道，蔡 苗，王欣旋

（1.北京機械工業(yè)自動化研究所，北京 100120；2.北自所（北京）科技發(fā)展有限公司，北京 100120；3.北京機械工業(yè)自動化研究所有限公司，北京 100120）

0 引言

隨著物流行業(yè)的發(fā)展,訂單揀選已成為物流系統(tǒng)中的關(guān)鍵環(huán)節(jié)之一,是影響作業(yè)效率的重要因素。高效的訂單揀選不但能在最短的時間內(nèi)使用最少的成本完成揀選作業(yè),還能提高客戶滿意度、提高整個供應鏈的服務水平。

傳統(tǒng)分揀系統(tǒng)按下單時間來分配分揀任務,忽視了訂單之間的耦合和各分揀工位的布局,容易造成各工位分揀任務不均衡現(xiàn)象,導致不同工位在不同的時間段任務量差別過大。分揀量大的工位揀選人員忙不過來,積壓大量任務；分揀量小的工位揀選人員無事可做,只能等待?？臻e時間的增加,導致系統(tǒng)揀選完成時間過長,不但浪費了人力與設(shè)備利用率,還降低了系統(tǒng)的整體性能。嚴重的話更會導致現(xiàn)場物流堵塞,影響客戶滿意度。

分揀環(huán)節(jié)已成為提高物流系統(tǒng)整體運行效率的主要瓶頸,企業(yè)生產(chǎn)方式已由傳統(tǒng)的面向庫存生產(chǎn)轉(zhuǎn)變?yōu)槊嫦蛴唵紊a(chǎn),如何提高訂單揀選的準確性和時效性,是物流系統(tǒng)亟待解決的問題。國內(nèi)外學者對該問題展開了廣泛的研究,主要集中在倉儲布局、路徑策略、揀貨策略等方面。Prata[1]等以最小化最大完工時間為目標研究客戶訂單調(diào)度問題,提出了基于混合整數(shù)線性規(guī)劃模型的FVLA和CSA算法。Jason[2]等提出了一種基于整數(shù)規(guī)劃的松弛算法,通過將算法下界轉(zhuǎn)換為模型可行解來對問題進行求解。吳穎穎[3]等以耦合因子為參數(shù)、訂單揀選順序為決策變量構(gòu)建訂單排序優(yōu)化模型,并用改進的K-Means算法進行求解。

本文從物流系統(tǒng)實際出發(fā),采用訂單揀貨策略,研究訂單排序?qū)x完成時間及效率的影響,用周轉(zhuǎn)箱代表訂單,以訂單上線順序為決策變量、揀選等待時間為限制條件,建立訂單排序優(yōu)化模型,并用遺傳算法進行求解,將結(jié)果與先到先服務（FCFS）規(guī)則進行比較,驗證遺傳算法在優(yōu)化訂單揀選順序問題上的有效性。

1 問題描述

以某分揀中心的分揀系統(tǒng)為例,揀貨區(qū)由n個分揀工位組成,每個工位由1名分揀人員負責,每個工位對應固定的分揀貨物。系統(tǒng)分揀方式為摘果式分揀：訂單揀選時,訂單對應到每個周轉(zhuǎn)箱,訂單順序即為周轉(zhuǎn)箱上線順序。周轉(zhuǎn)箱按指定順序上到輸送線,以順時針方向移動到指定工位。分揀人員根據(jù)提示從貨架取出貨物,完成分揀任務,隨后周裝箱流向下一工位,不斷重復此過程,直至該周轉(zhuǎn)箱對應的訂單分揀完成,此時周轉(zhuǎn)箱從分揀區(qū)域流出。訂單揀選完成時間隨訂單的內(nèi)容和訂單順序的不同而有所差異,任務分配不均衡也會拖慢分揀速度,導致分揀完成時間增長。因此,調(diào)度的主要目標在于合理安排各個訂單對應的周裝箱在各工位的揀選順序,使得各分揀工位任務量均衡,完成所有訂單的時間最短,提高按時交單率。

對于要研究的物流系統(tǒng),有如下假設(shè)：

1）揀選的貨物充足,不需要補貨。

2）揀選貨物單位時間一致,不考慮貨物在貨架上位置的影響。

3）每個周裝箱只能對應一個訂單。

4）一個訂單對應一個或多個周轉(zhuǎn)箱。

5）輸送系統(tǒng)速度穩(wěn)定。

6）空周裝箱充足。

7）模型為靜態(tài)揀選系統(tǒng),訂單信息在分揀開始前已知。

2 訂單排序優(yōu)化模型

訂單排序問題的目標是訂單揀選完成時間最短,而揀選完成時間分為二部分：揀選時間、等待時間。其中,揀選時間指揀選人員揀選貨物的時間,一般與揀選次數(shù)（揀選量）成正比；等待時間是指訂單上線后,由于上一訂單尚未結(jié)束、占用揀選工位而產(chǎn)生的空閑時間。

構(gòu)建n維向量V表示n個訂單分揀順序向量如式(1)所示。

其中,λi(1≤i≤n)是兩兩不同且位于[1,n]的自然數(shù),表示分揀順序為i的訂單號。傳統(tǒng)訂單揀選順序遵循FCFS原則,按照下單時間來分配訂單任務,相應的揀選順序為V=(1,2,3,…,n-1,n)。

構(gòu)建m維向量Xi表示第i個訂單在各工位需要分揀的任務量如式(2)所示：

其中,m表示分揀工位的個數(shù),xij(1≤i≤n,1≤j≤m)表示訂單i在工位j所需的揀選數(shù)量。如果不需要,則取值為0。

假設(shè)揀貨員揀選一個商品或者做一次揀選工作所需要的時間恒定,用tv表示,可以得到第i個訂單在第j個分揀工位消耗的時間tij如式(3)所示：

假設(shè)輸送系統(tǒng)速度穩(wěn)定,則周轉(zhuǎn)箱從i-1工位到i工位所用時間的時間恒定,用tw表示。

周轉(zhuǎn)箱到達指定工位后,若上一訂單對應的周轉(zhuǎn)箱若還未完成分揀任務,則本次周轉(zhuǎn)箱需要在緩存區(qū)等待,相應的等待時間用表示。由兩部分組成,一是線體上移動所用時間,即tw；二是上一周轉(zhuǎn)箱分揀所耗時間t(i-1)j。理想情況下,本次周轉(zhuǎn)箱到達時,上一周轉(zhuǎn)箱已經(jīng)離開,此時不存在等待時間,取值為0。考慮到上述兩種情況,

由式(4)表示：

綜上,本文討論的訂單排序優(yōu)化模型如下所示：

目標函數(shù)如式(5)所示：

約束條件如式(6)～式(11)所示：

目標函數(shù)式(5)表示最小化訂單揀選完成的總時間；式(6)表示訂單在各工位揀選工作消耗的時間之和；式(7)表示由于分揀任務不均衡導致的等待時間之和；式(8)表示第i個訂單在第j個分揀工位分揀所用時間；式(9)表示第i、j個訂單由于揀選順序引起的等待時間；式(10)和式(11)分別代表需要分揀的訂單總數(shù)、分揀工位數(shù)量。

3 算法設(shè)計與實現(xiàn)

訂單排序問題可視為旅行商問題（Travelling salesman problem,TSP）的變種,求解過程屬于NPHard難題,通常難以在多項式時間內(nèi)得到最優(yōu)的訂單揀選序列,因此,在參考前人相關(guān)研究的基礎(chǔ)上,本文采用遺傳算法進行求解,具體過程設(shè)計如下：

3.1 編碼

編碼方式是遺傳算法的基礎(chǔ),合理的編碼對算法質(zhì)量和求解效率有很大影響。工程中常用的編碼方式有二進制編碼、十進制編碼、實數(shù)編碼等。在訂單排序時,把訂單揀選順序向量作為單個染色體進行處理,向量由從1開始的整數(shù)組成,同時考慮到訂單對貨物的需求量都是從0開始的整數(shù),且二進制編碼有其明顯的局限性,所以編碼方式選擇實數(shù)編碼。通過選擇實數(shù)編碼,不但省去了解碼這一繁瑣步驟,還能有效避免海明距離這一問題。

3.2 種群初始化

傳統(tǒng)的遺傳算法中,初始種群中的個體是隨機產(chǎn)生的,這很可能導致結(jié)果陷入局部最優(yōu),不利于問題求解。為了避免這種情況,使得初始種群中的個體均勻分布在解空間,本文以海明距離為優(yōu)化方向,來對隨機生成的初始種群進行選擇。

1）隨機生成3n個染色體個體；

2）通過FCFS方式生成初始訂單序列,作為初始種群中第一個個體；

3）計算未被選中個體與初始種群中染色體個體之間的海明距離之和,選取距離最大值對應的個體加入初始種群；

4）重復3)中操作,逐漸增加初始種群規(guī)模,直到初始種群包含n個染色體個體。

3.3 適應度函數(shù)

適應度函數(shù)用于對個體進行評價,體現(xiàn)了目標函數(shù)的變化趨勢,是進化過程中個體選擇的唯一依據(jù)。訂單揀選順序優(yōu)化問題的目標是最小化揀選完成時間,屬于最值問題,適宜采用目標函數(shù)映射法,即將目標函數(shù)變換成適配值函數(shù),因此,適應度函數(shù)設(shè)計為目標函數(shù)的倒數(shù)如式(12)所示：

3.4 選擇操作

選擇是從群體中選擇適應度高的個體、淘汰適應度低的個體的操作。目前常用的方法主要有：比例選擇、排序選擇和聯(lián)賽選擇等。本文采用比例選擇法（也稱輪盤賭）對個體進行選擇,這是目前遺傳算法中最常用的選擇方法,其基本原理是根據(jù)每個染色體適應度值的比例來確定被選中的概率,將適應度按從小到大的規(guī)則排序,個體適應度越大,被選中的概率就越大,反之亦然。設(shè)種群大小為N,個體i的適應度為fi,則個體i被選中的概率如式(13)所示：

3.5 交叉操作

交叉是將兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過組合出的新個體,提高了遺傳算法在在解空間的全局搜索能力,降低了對有效基因的破壞概率,是遺傳算法區(qū)別于其他啟發(fā)式算法的重要特征。

實數(shù)編碼遺傳算法與二進制遺傳算法相比,可用的變異算子種類更多,常用的算子有離散重組、算術(shù)交叉、部分匹配交叉（PMX）和循環(huán)交叉（CX）等。對于訂單排序優(yōu)化問題,每條染色體個體代表了一種分揀順序,交叉操作可能會產(chǎn)生不符合實際情況的序列,如同一訂單出現(xiàn)多次、缺少某個訂單等。從編碼-交叉設(shè)計原則出發(fā),本文選擇順序交叉(Order crossover,OX),該算子的優(yōu)點是交叉后不會出現(xiàn)重復的訂單序號、不需要進行沖突檢測,因而在實數(shù)編碼的遺傳算法中得到廣泛應用。順序交叉算子的具體操作過程如下所示：

對于兩個包含9個訂單的父代個體P1、P2,隨機選擇兩個交叉點“|”,交叉前的父代染色體為：

順序交叉后,最終得到的子代染色體情況如下所示：

3.6 變異操作

變異是在染色體個體上產(chǎn)生微小擾動來維持種群多樣性的操作。通過變異操作,遺傳算法的局部搜索能力得到加強,選擇、交叉過程中丟失的基因得到修復和補充,有利于增加種群的多樣性,在一定程度上預防了早熟收斂現(xiàn)象。

常用的變異算子有：位點變異、逆轉(zhuǎn)變異、對換變異等。由于染色體基因值的固定范圍且兩兩不同的自然數(shù),不宜采用位點變異、對換變異等算子。本文選擇了兩點法,即在一個個體中隨機選擇兩個點,使兩點的位置互換,基因值互換,代表相應的訂單分揀順序互換,達到了變異的目的。對于一個染色體p,隨機選擇兩個變異點“|”,變異前染色體為：

變異后子代染色體情況為：

3.7 算法終止條件

實際應用時,不允許遺傳算法無休止的計算下去,因此需要設(shè)定收斂準則來終止算法。本文設(shè)計的終止條件為最大迭代次數(shù)：當?shù)螖?shù)等于最大迭代次數(shù)時,算法停止搜索過程,輸出最優(yōu)解。

4 實例分析

交叉概率范圍一般是0.6～1,變異概率通常是0.1或者更小。經(jīng)過多次仿真計算,本文實現(xiàn)的遺傳算法相關(guān)參數(shù)設(shè)定為：交叉概率Pc=0.8,變異概率Pm=0.003,最大“停滯”次數(shù)為10,最大迭代次數(shù)設(shè)為500,種群規(guī)模為N=100。

需要分揀的訂單總數(shù)n取值范圍為50、100、200,分揀工位數(shù)量m取值為6,各訂單在不同工位的分揀量取值范圍為[0,20]。

多次迭代,取較優(yōu)結(jié)果,并計算不同訂單數(shù)量下的訂單揀選時間、訂單等待時間,繪制分揀時間時間趨勢圖,實驗具體結(jié)果如表1所示。

表1 訂單揀選時間 （單位：s）

表1為遺傳算法對模型求解之后得到的結(jié)果。從實驗結(jié)果可看出,訂單排序揀選可有效縮短訂單揀選時間。相比于訂單順序揀選,總的揀選完成時間分別縮短了7.1%、7.9%和3.8%,說明本文實現(xiàn)的算法對不同的訂單規(guī)模均有一定的優(yōu)化效果。

表2為優(yōu)化前后系統(tǒng)分揀等待時間對比。從表中可看出,訂單排序后系統(tǒng)分揀等待時間大幅度縮短,表明訂單排序可有效均衡不同工位工作量,減少了堵塞現(xiàn)象,進而縮短了系統(tǒng)整體分揀完成時間,為提高分揀效率提供了合理性指導。

表2 分揀等待時間 （單位：s）

圖1、圖2和圖3為訂單規(guī)模為50、100和200時的訂單分揀總時間。從趨勢可以看出,隨著迭代次數(shù)的增加,訂單總分揀時間在逐漸縮短,最后趨于穩(wěn)定,證明了訂單排序這一策略的有效性。

圖1 訂單數(shù)量N=50時分揀時間隨迭代次數(shù)增加而變化的趨勢圖

圖2 訂單數(shù)量N=100時分揀時間隨迭代次數(shù)增加而變化的趨勢圖

圖3 訂單數(shù)量N=200時分揀時間隨迭代次數(shù)增加而變化的趨勢圖

5 結(jié)語

本文對分揀系統(tǒng)調(diào)度優(yōu)化問題進行了研究,指出了訂單排序問題的必要性。從訂單的揀選順序入手,以訂單分揀完成時間最短為目標建立了相應的訂單排序優(yōu)化模型,利用基于實數(shù)編碼的遺傳算法對模型進行求解,獲得了較優(yōu)的訂單揀選順序。與訂單順序揀選相比,本文提出的算法可有效均衡各工位工作量、縮短工人等待時間,進而縮短系統(tǒng)分揀完成時間,對于提高分揀系統(tǒng)運行效率具有一定的指導意義。

單一目標函數(shù)的模型往往難以滿足各種系統(tǒng)的實際需求,沖突性的多目標或眾目標是未來的研究方向。因此,對于目標函數(shù)的更細化考量,還有待進一步完善,這也是本文未來工作之一。