基于遺傳算法的揀選系統(tǒng)調(diào)度優(yōu)化研究

紀(jì)佳溥，岳秀江，趙劍道，蔡 苗，王欣旋

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

0 引言

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

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

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

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

1 問題描述

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

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

1）揀選的貨物充足,不需要補(bǔ)貨。

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

3）每個(gè)周裝箱只能對(duì)應(yīng)一個(gè)訂單。

4）一個(gè)訂單對(duì)應(yīng)一個(gè)或多個(gè)周轉(zhuǎn)箱。

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

6）空周裝箱充足。

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

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

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

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

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

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

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

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

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

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

由式(4)表示：

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

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

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

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

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

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

3.1 編碼

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

3.2 種群初始化

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

1）隨機(jī)生成3n個(gè)染色體個(gè)體；

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

3）計(jì)算未被選中個(gè)體與初始種群中染色體個(gè)體之間的海明距離之和,選取距離最大值對(duì)應(yīng)的個(gè)體加入初始種群；

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

3.3 適應(yīng)度函數(shù)

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

3.4 選擇操作

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

3.5 交叉操作

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

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

對(duì)于兩個(gè)包含9個(gè)訂單的父代個(gè)體P1、P2,隨機(jī)選擇兩個(gè)交叉點(diǎn)“|”,交叉前的父代染色體為：

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

3.6 變異操作

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

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

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

3.7 算法終止條件

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

4 實(shí)例分析

交叉概率范圍一般是0.6～1,變異概率通常是0.1或者更小。經(jīng)過多次仿真計(jì)算,本文實(shí)現(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é)果,并計(jì)算不同訂單數(shù)量下的訂單揀選時(shí)間、訂單等待時(shí)間,繪制分揀時(shí)間時(shí)間趨勢(shì)圖,實(shí)驗(yàn)具體結(jié)果如表1所示。

表1 訂單揀選時(shí)間 （單位：s）

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

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

表2 分揀等待時(shí)間 （單位：s）

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

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

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

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

5 結(jié)語

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

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