基于嵌套遺傳算法的揀貨作業(yè)聯(lián)合優(yōu)化

孫軍艷，陳智瑞，牛亞儒，張媛媛，韓 昉

（陜西科技大學(xué)機電工程學(xué)院，西安 710021）

（?通信作者電子郵箱390722942@qq.com）

0 引言

揀選作業(yè)活動是配送中心在庫作業(yè)中勞動力最密集和資金占用成本最大的環(huán)節(jié)［1］。揀選作業(yè)優(yōu)化主要包括訂單分批、路徑優(yōu)化等［2］，其中訂單分批是前提，路徑優(yōu)化是關(guān)鍵，揀選作業(yè)優(yōu)化可以有效地提高揀貨效率。

在訂單分批方面，Chen 等［3］提出了一種基于關(guān)聯(lián)規(guī)則挖掘和整數(shù)規(guī)劃的訂單分批方法，將關(guān)聯(lián)性較大的訂單歸為一批。建立了訂單分批和排序數(shù)學(xué)模型，可變鄰域搜索、種子算法等求解方法多被用于求解該模型，實驗結(jié)果表明該方法可得出最佳解決方案，減少總揀選時間［4-6］。邵澤熠等［7］采用密度和最小距離作為參數(shù)確定初始聚類中心，再用改進遺傳K-均值算法確定K值，以求得更優(yōu)的分批結(jié)果。在路徑優(yōu)化方面，改進蟻群算法、改進遺傳算法和混合蟻群算法等多用于對大型倉儲揀選系統(tǒng)進行路徑優(yōu)化［8-11］。劉建勝等［12］、王永波等［13］采用蟻群算法、混合蟻群算法求解最短揀貨路徑，結(jié)果表明，該算法適合于大型倉儲揀貨路徑優(yōu)化。李棟棟［14］以最小化揀貨車行走路程為目標建立模型，采用貪心遺傳算法求解最短揀貨路徑。

也有學(xué)者將訂單分批和揀貨路徑結(jié)合起來進行分步優(yōu)化，即通過不同訂單分批算法得到最優(yōu)的分批結(jié)果，然后對分批的最優(yōu)結(jié)果進行路徑優(yōu)化。Chen 等［15］、Ardjmand 等［16］采用智能算法針對訂單分批和批次排序求解最優(yōu)解，再求出最短揀貨路徑。Kulak等［17］以總揀選距離最短為目標，通過聚類算法得到分批結(jié)果，再用禁忌搜索算法求解最佳揀選路徑。馬飛［18］以訂單相似度最大為目標對訂單進行分批，然后以揀選路徑最短為目標建立模型，設(shè)計混合粒子群算法求解最優(yōu)路徑。王占磊［19］以總的揀選距離最短為目標函數(shù)建立模型，先求解出文中設(shè)計的訂單分批結(jié)果，再進行路徑優(yōu)化。劉云峰等［20］以總路徑最短為目標建立數(shù)學(xué)模型，對比不同訂單分批策略和路徑策略組合下總行走距離，得出距離最小的方案。

顯然，這種分階段的優(yōu)化思路難以得到所有訂單總的揀貨距離或揀貨時間的全局最優(yōu)，因此，訂單分批和揀貨路徑聯(lián)合優(yōu)化具有重要的研究意義。聯(lián)合優(yōu)化的模型之間相互關(guān)聯(lián)，需要考慮兩者之間相互優(yōu)化、不斷變動的要求。目前建立訂單分批和揀貨路徑聯(lián)合優(yōu)化模型的研究較少。

在現(xiàn)有的研究中，Cheng 等［21］建立了以揀選距離最短為總目標的數(shù)學(xué)模型，采用粒子群與蟻群算法的混合方法求解訂單分批與揀選路徑聯(lián)合優(yōu)化問題。但該模型中未考慮揀取貨物的數(shù)量、體積和時間，研究區(qū)域限于小型單區(qū)型倉庫，并且訂單初始的分批大小隨機，文中設(shè)計的方法未與傳統(tǒng)揀選方法進行對比分析，無法驗證文中方法的有效性。

在算法方面，受劉云飛等［22］采用雙層遺傳算法求解混合整數(shù)規(guī)劃模型，鄭永前等［23］設(shè)計雙層嵌套式混合遺傳算法求解多級供應(yīng)鏈中混合車間生產(chǎn)、采購和產(chǎn)品運送的決策問題的啟發(fā)，本文提出了一種基于嵌套遺傳算法的訂單分批和路徑優(yōu)化的聯(lián)合揀貨策略。本文的主要工作如下：

1）以總揀貨時間最小為總目標建立訂單分批和揀貨路徑的聯(lián)合優(yōu)化模型，考慮了揀選貨物數(shù)量對揀選時間的影響，揀選貨物的體積對分批的影響。

2）在聚類算法得出初始分批種群的前提下，設(shè)計嵌套遺傳算法求解聯(lián)合優(yōu)化問題，實現(xiàn)訂單分批和路徑優(yōu)化的整體最優(yōu)。

3）將聯(lián)合優(yōu)化與現(xiàn)有的按單揀選方法、分批分步揀選方法進行對比，并分別在10、20、50 張不同訂單規(guī)模條件下驗證本文所設(shè)計揀選方法的有效性，為研究訂單分批和路徑聯(lián)合優(yōu)化提供了新的思路。

1 問題描述及模型建立

1.1 問題描述

雙重優(yōu)化問題難以獲得最優(yōu)解，容易陷入局部最優(yōu)，具有雙重復(fù)雜性。已知條件為一個周期內(nèi)多張訂單的訂單分批和揀貨路徑聯(lián)合優(yōu)化問題，屬于NP（Non-deterministic Polynomial）難問題，即有N個訂單R（｛r=1，2，…，N｝）需要揀取，每個訂單中包含若干品項，每個品項i的體積為vi，訂單r中包含的品項集合為Xr={xr1，xr2，…，xrn}。需求解的結(jié)果是對N個訂單進行分批揀取，每批訂單的揀取在一條線路上一次完成，使所有訂單的總揀貨時間最少。本文考慮每張訂單中需要揀取的品項的數(shù)量不同，則所需的揀選時間不同，總揀貨時間包括所有訂單揀選的路徑行走的時間和揀取品項所需的時間，建立了以總揀貨時間最小為目標函數(shù)的訂單分批和路徑優(yōu)化聯(lián)合模型。

1.2 訂單分批與路徑聯(lián)合優(yōu)化模型建立

1.2.1 條件假設(shè)及參數(shù)定義

假設(shè)條件如下：

1）采用摘果式，訂單分批揀取貨物，其中空閑等待時間忽略不計。

2）揀貨區(qū)分布主要為：貨架層數(shù)為1，每個儲位的大小相同，每個儲位只存儲一種庫存量單位（Stock Keeping Unit，SKU），同時每個貨位最多只能存放一種SKU。

3）揀貨過程中不存在缺貨現(xiàn)象，即補貨時間忽略不計。

4）訂單的各品項及其存儲位置是已知的。

5）訂單不允許進行分割，保證一個訂單一次揀完。

6）分批后的每批訂單要在一條路徑上完成揀貨。

模型相應(yīng)的參數(shù)和變量定義如下：R為訂單集（｛r=1，2，…，N｝）；H為分批集（｛h=1，2，…，M｝）；M為訂單分批的個數(shù)；N為訂單的個數(shù)；i，j為訂單中的揀貨位（｛i=1，2，…，n；j=1，2，…，n｝）；n為揀貨位（品項）的個數(shù)；vi為揀貨位i的品項的體積；dij為揀貨位i，j之間的距離；v為揀貨人員平均行走速度；Q為揀貨車的容量；Xri為第r張訂單的第i個揀貨位的品項的數(shù)量；xr為訂單r的品項集合；Gh為第h批訂單品項的集合；Ghi為第h批訂單的品項集合中是否包含揀貨位i；yrh為訂單r被分到第h批中；Sh為第h批訂單揀貨路徑的距離；T為訂單分批后總的揀貨時間；tu為揀取每單位品項所需的時間。

1.2.2 目標函數(shù)建立

聯(lián)合優(yōu)化模型總目標是，每批訂單的揀取在一條線路上一次完成，使所有訂單的總揀貨時間最少，建立聯(lián)合優(yōu)化模型目標函數(shù)（1）表示訂單分批后，所有批次訂單總的揀貨時間；目標函數(shù)（2）表示將所有訂單分批后，第h批訂單中所有品項的集合；目標函數(shù)（3）表示第h批訂單揀貨的距離。

1.2.3 約束條件建立

揀貨過程中訂單不允許分割，一張訂單只能分配到一個批次中建立約束條件（4）；式（5）表示每張揀貨單的路徑只能走一次，同時應(yīng)該對揀貨車的揀貨能力做出約束；式（6）表示每批訂單中所包含的品項數(shù)總體積不能超過揀貨車的容量。

1.2.4 決策變量建立

聯(lián)合優(yōu)化模型關(guān)鍵決策變量在于判斷訂單分配批次、揀貨位i，j順序，均采用0-1 變量建立聯(lián)合優(yōu)化模型性決策變量，式（7）表示訂單r是否被分配到h批揀貨單中；式（8）表示揀貨位i，j是否為揀貨路徑中相鄰的點；式（9）表示第h批訂單的品項集合中是否包含揀貨位i；式（10）表示第h批訂單的品項集合中是否包含揀貨位j。

2 嵌套遺傳算法設(shè)計

2.1 嵌套遺傳算法設(shè)計思路

訂單分批和路徑優(yōu)化兩者相互關(guān)聯(lián)，一變俱變，每一個符合約束條件的分批結(jié)果對應(yīng)一個總揀貨時間，分批結(jié)果變化，揀貨總時間也隨之改變，直到找出一種分批結(jié)果使得總揀貨時間最短。因此，一般的遺傳算法難以求解聯(lián)合優(yōu)化模型，基于聯(lián)合優(yōu)化問題的復(fù)雜性設(shè)計一種嵌套式遺傳算法，總體框架如圖1所示。

圖1 嵌套遺傳算法流程Fig.1 Flowchart of nested genetic algorithm

首先，以巷道間相似度最大為準則的聚類算法得出初始的聚類結(jié)果和聚類個數(shù)形成初始種群，外層遺傳算法根據(jù)揀貨車容量限制條件計算出滿足條件的分批小種群，將其作為內(nèi)層遺傳算法的輸入，內(nèi)層遺傳算法根據(jù)外層遺傳算法輸出的分批結(jié)果計算出每張揀貨單的揀貨路徑和距離以及總的揀貨時間，即揀貨路徑優(yōu)化。同時，內(nèi)層遺傳算法將目標函數(shù)值反饋到外層，目標函數(shù)在內(nèi)外層遺傳算法的不斷反饋中達到最優(yōu)。

2.2 算法具體步驟

嵌套遺傳算法的具體步驟如下：

1）初始聚類。根據(jù)訂單相似系數(shù)Sij的聚類算法得到訂單分批結(jié)果，確定初始聚類個數(shù)h。

2）編碼設(shè)計和初始種群。根據(jù)聚類結(jié)果生成外層染色體C1，建立初始種群K。

3）生成揀貨單。在一代種群中，根據(jù)式（6）判斷分批結(jié)果C1是否滿足揀貨車容量，若滿足則生成分批小種群，種群規(guī)模為n，對每一分批結(jié)果Cj通過式（1）對屬于同一批次h的所有訂單r的品項集合Xr進行合并，生成揀貨單h的集合Gh，然后確定每張揀貨單需要揀取的揀貨位i，從而得到需要揀取的揀貨位編號集合C2，生成路徑優(yōu)化初始種群。

4）路徑優(yōu)化。通過內(nèi)層遺傳算法對每張揀貨單進行路徑優(yōu)化，染色體C2表示每張揀貨單的揀貨路徑。適應(yīng)度函數(shù)為，即為揀貨單h的距離Sh的倒數(shù)，表示揀貨時間越短，個體的適應(yīng)度越高。通過選擇算子Pi、交叉算子Pc和變異算子Pm產(chǎn)生新種群C2，判斷是否達到最大迭代次數(shù)maxgen2，若沒有達到，則計算適應(yīng)度值，繼續(xù)循環(huán)；若達到，則終止循環(huán)，得到一個分批結(jié)果的所有揀貨單的最優(yōu)揀貨路徑和揀貨距離Sh。

5）適應(yīng)度值。計算一個種群中每一個分批結(jié)果的適應(yīng)度值，適應(yīng)度函數(shù)為，判斷一個種群中所有分批個數(shù)n是否都完成內(nèi)層路徑優(yōu)化，若沒有都完成，則返回步驟3）；若都完成則繼續(xù)步驟6）。

6）產(chǎn)生新個體。通過選擇算子Pi、交叉算子Pc和變異算子Pm產(chǎn)生新種群C1。

7）判斷是否達到最大迭代次數(shù)maxgen1，若達到，則生成最優(yōu)分批結(jié)果和總揀貨時間T；若沒達到，則返回步驟3）判斷新種群的新個體C1是否滿足揀貨車容量，若滿足繼續(xù)步驟4），若不滿足則適應(yīng)度值f1=0，返回步驟6）。

2.3 嵌套遺傳算法優(yōu)化過程

2.3.1 外層訂單分批優(yōu)化

1）初始聚類個數(shù)的產(chǎn)生。

根據(jù)聚類算法得到初始的分批結(jié)果，獲得初始分批的個數(shù)為h（h=1，2，…，M），該聚類算法是通過多巷道倉庫中計算兩個訂單擁有的相同巷道數(shù)的多少作為聚類準則［24］，計算訂單間的距離衡量公式、衡量相似系數(shù)。

①分別計算兩兩訂單i，j間的相似系數(shù)Sij。

②將相似系數(shù)Sij按照降序排列。

③將Sij最大的兩個訂單作為一批，如果有相同的Sij，則選擇品項數(shù)最多的組合，判斷是否滿足Vi+Vj≤Q，若不滿足則選擇下一個Sij，將已合成一批的訂單i，j看作一個新的訂單，對新的訂單的集合重新計算相似系數(shù)Sij，返回步驟②；若所有的Sij都不可行，則將未分批的訂單單獨作為一批，得到分批結(jié)果。

訂單間的距離衡量公式為：

其中：Ai表示訂單i中揀貨位分布的通道集合向量；Sij為非中心點訂單i與中心點訂單j的相似系數(shù)，用來表示兩個訂單間的距離。訂單間的相似系數(shù)結(jié)果越小，則訂單間重合的通道越多，兩個訂單間的距離越短。作為相似系數(shù)的歸一化常數(shù)，使得相似系數(shù)值域在［0，1］。

2）編碼設(shè)計和初始種群。

外層染色體C1采用實數(shù)編碼的方式，C1的表達式為C1=[h1，h2，…，hr]，其中，基因位數(shù)對應(yīng)訂單的編號，基因值為訂單所屬的分批編號。如C1=[2，1，3，1，2，3]，表示訂單1 屬于第2 批，訂單2 屬于第1 批，訂單3 屬于第3 批，訂單4 屬于第1批，…，以此類推。即形成初始種群K。

3）適應(yīng)度值計算。

在一代種群中，首先根據(jù)式（6）判斷一個染色體中屬于同一批次的訂單的體積和是否滿足揀貨車容量，若滿足則生成小種群，根據(jù)式（1）對屬于同一批次的所有訂單的品項進行合并，生成揀貨單，每張揀貨單中包含同一批次的所有訂單的品項的數(shù)量集合Gh，Gh={xh1，xh2，…，xhi，…，xhm}，得到揀貨單品項的數(shù)量的集合確定需要揀取的揀貨位，從而得到需要揀取的揀貨位編號集合C2，進入內(nèi)層揀貨路徑優(yōu)化步驟。根據(jù)內(nèi)層遺傳算法得出的最優(yōu)揀貨路徑計算適應(yīng)度值，適應(yīng)度函數(shù)表示揀貨完成的總時間T的倒數(shù)，揀貨的時間越短，個體的適應(yīng)度值越高，計算式為：

4）遺傳操作。

①選擇算子。采用經(jīng)典的輪盤賭法，每個個體被選為父代的概率與其適應(yīng)度是成正比的，適應(yīng)度越高，被選中的概率越大，設(shè)Pi為第i個個體被選中的概率，則，其中Fi為第i個個體的適應(yīng)度值。

②交叉算子。交叉概率為Pc，根據(jù)選擇操作選擇兩個父代染色體和進行交叉。隨機選擇兩個點，那么將兩個點之間的位置進行交叉。例如，兩個父代個體A=［2 1 3 1 2 3］，B=［1 2 3 3 2 1］，交叉位置數(shù)的兩個點為3 和4，則子代個體為A'=［2 1 3 3 2 3］，B'=［1 2 3 1 2 1］。

③變異算子。變異概率為Pm，變異操作時產(chǎn)生一個隨機數(shù)，例如染色體編碼［2，1，3，1，2，3］中將3 變成2 時，那么2 也會變成3，變異后的個體為［3，1，2，1，3，2］。

5）終止條件。

判斷是否達到最大迭代次數(shù)maxgen1，若達到，則生成最優(yōu)分批結(jié)果和總揀貨時間T；若未達到，則判斷新種群的新個體是否滿足揀貨車容量，若滿足則重復(fù)上述過程，若不滿足則適應(yīng)度值f1進入遺傳操作產(chǎn)生新種群。

2.3.2 內(nèi)層訂單路徑優(yōu)化

1）編碼設(shè)計和適應(yīng)度值計算。

本文中采用自然數(shù)編碼，染色體C2=[i1，i2，…，in]，其中元素（基因）in為［1，n］（n為揀貨位個數(shù)）的一個互不重復(fù)的自然數(shù)，其中基因位數(shù)對應(yīng)揀貨位的排序，基因值為需要揀取的揀貨位編號。如C2=[0，1，2，3，4，0]表示每張揀貨單的揀貨路徑是出入口0-揀貨位1-揀貨位2-揀貨位3-揀貨位4-出入口0，生成初始種群。

適應(yīng)度函數(shù)表示揀貨單總路程的倒數(shù)，揀貨的路程越短，個體的適應(yīng)度值越高，其計算式為：

2）遺傳操作。

①選擇算子。選擇輪盤賭法，其扇面的角度和個體的適應(yīng)度值成正比，適應(yīng)度越高，被選中的概率越大。

②交叉算子。采用部分匹配交叉法，根據(jù)選擇操作從父代中選擇兩個進行交叉，交叉概率為Pc。例如兩個父代個體A=［1 2 3 4 5 6 7 8］，B=［2 4 6 8 7 5 3 1］，隨機選擇兩個交叉的貨位點，第一個交叉點為位置4，第二個交叉點為位置6，那么在兩個點之間的位置將進行交叉，其他的位置進行復(fù)制或者用相匹配的數(shù)進行替換。第一個父代交叉的部分是4 5 6，第二個父代交叉的部分是8 7 5，則4 與8、5 與7、6 與5 相匹配，則子代個體為A'=［1 2 3 8 7 5 6 4］，B'=［2 8 7 4 5 6 3 1］。

③變異算子。變異概率為Pm，變異操作時產(chǎn)生一個隨機數(shù)，例如染色體編碼［1，3，2，6，4，7，5］中將3 變成4 時，那么4也會變成3，變異后的個體為［1，4，2，6，3，7，5］。

3）終止條件。

按照以上步驟循環(huán)操作，當達到最大遺傳代數(shù)maxgen2時終止算法，得到每張揀貨單的最優(yōu)揀貨路徑和揀貨距離Sh。

3 實例分析

3.1 倉庫模型

以雙區(qū)型倉庫為實例，該倉庫由3 條平行的橫向通道和若干條縱向通道構(gòu)成，每條通道的寬度相等，每條巷道寬度也相等，縱向巷道除了第一列和最后一列的貨架是單排貨架，其他貨架均為背靠背式貨架，如圖2所示。

圖2 雙區(qū)型倉庫布局Fig.2 Layout of two-zone warehouse

倉庫尺寸符號說明如下：

1）a（a=1，2，…，A）為貨位所在的巷道編號；

2）b為同一巷道中左右兩側(cè)的貨架，左側(cè)貨架即b=0，右側(cè)貨架即b=1；

3）c（c=1，2，…，C）為同一排貨架中貨位的標號；

如圖2 所示，設(shè)有10 條縱向通道，每個巷道的寬度為1 m，每個橫向通道的寬度為2 m，兩個橫向通道間每一列貨架的個數(shù)為20，貨架的長為2 m，寬為1 m。任意兩個貨位i，j之間的最短距離dij取值情況如下：

1）兩個貨位點在同一條揀貨巷道中，在中間通道的同側(cè)：

2）兩個貨位點在同一條揀貨巷道中，分散在中間通道兩側(cè)：

3）兩個貨位點在不同揀貨巷道中，在中間通道的同側(cè)：

4）兩個貨位點在不同揀貨巷道中，分散在中間通道兩側(cè)：

5）貨位點i與出入口之間：

3.2 聯(lián)合優(yōu)化結(jié)果對比分析

模型的參數(shù)設(shè)置如下：揀貨人員的平均行走速度為1 m/s，揀貨人員揀取單個貨物所需的時間為2 s，揀貨車容量為80。通過查閱相關(guān)文獻和大量實驗可得算法的參數(shù)設(shè)置如下：外層遺傳算法的初始種群為65，迭代次數(shù)為70，變異概率為Pm=0.4，交叉概率Pc=0.9；內(nèi)層遺傳算法的初始種群為80，迭代次數(shù)為1 000，變異概率為Pm=0.08，交叉概率Pc=0.4。實驗數(shù)據(jù)來源于某電商的訂單數(shù)據(jù)，每張訂單數(shù)據(jù)中包含了客戶購買的不同貨物信息，包括貨物序號、儲位坐標、貨物數(shù)量和體積。首先以10 張訂單的揀選為例進行分析，由表1 可得，10張訂單聯(lián)合優(yōu)化共分為3批，第一批結(jié)果是訂單1、4、8，需要揀取品項數(shù)量為15，最優(yōu)路徑揀貨順序為：36-26-64-125-450-695-652-579-333-251-297-392-355-356-114，總揀貨時間為274 s，總揀貨距離為210 m，路徑示意圖見圖3，揀貨路徑見圖4。其中，橫縱坐標為倉庫模型的儲位坐標，黑色標記為貨物序號。

表1 聯(lián)合優(yōu)化計算結(jié)果Tab.1 Joint optimization results

第二批結(jié)果是訂單2、7、9，需要揀取品項數(shù)量為16，最優(yōu)路徑揀貨順序為：109-24-61-140-254-249-365-444-450-410-579-657-774-788-708-275，總揀貨時間為292 s，總揀貨距離為218 m，路徑示意圖見圖5，揀貨路徑見圖6。

第三批結(jié)果是訂單3、5、6、10，需要揀取品項數(shù)量為18，最優(yōu)路徑揀貨順序為36-52-105-115-186-129-87-251-361-651-732-579-548-709-635-472-356-240，總揀貨時間為398 s，總揀貨距離為308 m，路徑示意圖見圖7，揀貨路徑見圖8。

表1對比了聯(lián)合優(yōu)化與分步優(yōu)化的計算結(jié)果，由表1可以看出，聯(lián)合優(yōu)化的結(jié)果最優(yōu)，分批分步優(yōu)化次之，按訂單分步優(yōu)化結(jié)果最差。其中，分批分步優(yōu)化指的是對同一周期的訂單進行訂單分批后求解其最優(yōu)路徑及揀貨時間，按訂單分布優(yōu)化指的是不對訂單進行分批處理，直接求解每張訂單的最短路徑及揀貨時間；與按訂單分步優(yōu)化相比，聯(lián)合優(yōu)化的揀貨路徑減少了824 m，相當于減少了52.8%，時間減少了810 s，相當于減少了45.6%；與按分批分步優(yōu)化相比，聯(lián)合優(yōu)化的揀貨路徑減少了108 m，相當于減少了6.9%，時間減少了108 s，相當于減少了6%。因此，聯(lián)合優(yōu)化的結(jié)果更優(yōu)，對于揀貨效率有明顯的提高，進一步減少了揀貨時間。

圖3 第一批訂單揀貨路徑示意圖Fig.3 Schematic diagram of picking path of first batch of orders

圖4 第一批訂單揀貨路徑Fig.4 Picking path of first batch of orders

圖5 第二批訂單揀貨路徑示意圖Fig.5 Schematic diagram of picking path of second batch of orders

以上為10 張訂單的分析結(jié)果，為驗證該算法對不同規(guī)模訂單均具有較好的性能，再分別以20 張、50 張訂單為算例進行驗證，表2為求解10、20、50張訂單分別采用聯(lián)合優(yōu)化、分批分步優(yōu)化和按訂單分步優(yōu)化的結(jié)果對比?？梢钥闯觯瑢τ诓煌唵瘟?，聯(lián)合優(yōu)化的結(jié)果相較于分步優(yōu)化結(jié)果更優(yōu)，并且隨著訂單量的增加，節(jié)約的時間和距離越多，揀選時間減少百分比從6%增加到7.2%。因此，隨著訂單量的增加，揀貨效率提高越明顯。

圖6 第二批訂單揀貨路徑Fig.6 Picking path of second batch of orders

圖7 第三批訂單揀貨路徑示意圖Fig.7 Schematic diagram of picking path of third batch of orders

圖8 第三批訂單揀貨路徑Fig.8 Picking path of third batch of orders

3.3 嵌套遺傳算法的可靠性分析

在算法的收斂性方面，圖9 為嵌套遺傳算法運算過程中訂單揀選總時間隨迭代次數(shù)增加而逐漸收斂的過程。圖9 結(jié)果表明，隨著迭代次數(shù)的增加，揀選總時間呈遞減趨勢。當?shù)螖?shù)大于40 后，揀選總時間趨于某一穩(wěn)定值，表明該算法具有很好的收斂性。

表2 不同訂單量算例的對比結(jié)果Tab.2 Comparison results of examples with different orders

穩(wěn)定性方面，由于嵌套遺傳算法的內(nèi)外兩層遺傳算法將會導(dǎo)致最優(yōu)結(jié)果在趨于穩(wěn)定時出現(xiàn)一定的波動。文獻［22］運用嵌套遺傳算法進行10 次運算，收斂后的目標值波動在±10%之內(nèi)。為了驗證本文設(shè)計的嵌套遺傳算法的可靠性，進行了15 次運算，最短揀貨總時間的平均值為1 064 s，其波動情況如圖10 所示。圖10 結(jié)果表明，在15 次運算中，目標值的波動在±5%之間，可見本文設(shè)計的嵌套遺傳算法具有很好的可靠性。

圖9 嵌套遺傳算法迭代圖Fig.9 Nested genetic algorithm iteration graph

圖10 目標函數(shù)波動比Fig.10 Fluctuation ratio of objective function

算法時效性方面，在Intel CoreTM i56300-HQ CPU，Matlab R2014a 環(huán)境下，針對10 張、20 張、50 張訂單分別采用分批分布優(yōu)化、按訂單分布優(yōu)化及基于嵌套遺傳算法的聯(lián)合優(yōu)化的CPU 運行時間如表3 所示。表3 結(jié)果表明，按訂單分布優(yōu)化CPU 運行時間最長，時效性較差，而嵌套遺傳算法解決訂單分批和揀貨路徑聯(lián)合優(yōu)化具有較好的時效性。

表3 不同優(yōu)化策略下CPU運行時間Tab.3 CPU running time under different optimization strategies

4 結(jié)語

本文設(shè)計了以揀貨時間最短為目標函數(shù)的訂單分批和揀貨路徑聯(lián)合優(yōu)化模型，采用嵌套遺傳算法對模型進行求解。仿真結(jié)果表明：相較于分步優(yōu)化策略，采用本文設(shè)計的嵌套遺傳算法求解聯(lián)合優(yōu)化模型穩(wěn)定可靠，且得到的結(jié)果更理想，揀貨時間和揀貨距離更優(yōu)，可以進一步減少揀貨時間，提高了整個物流配送中心的揀貨效率。本文中所提的模型和算法及其仿真結(jié)論可為配送中心揀貨系統(tǒng)優(yōu)化提供決策參考。