不同訂單分配和算法下的揀貨路徑優(yōu)化組合

孟 鑫，楊 琴 ，4，郝婷婷，張 潔，曹策俊

1.四川師范大學(xué) 商學(xué)院，成都 610101

2.長安大學(xué) 經(jīng)濟(jì)與管理學(xué)院，西安 710054

3.重慶工商大學(xué) 商務(wù)策劃學(xué)院，重慶 400067

4.四川工商學(xué)院 經(jīng)濟(jì)管理學(xué)院，成都 611745

1 引言

隨著網(wǎng)絡(luò)購物的現(xiàn)象日益普遍，人們對物流配送行業(yè)倍加關(guān)注。配送中心的揀貨作業(yè)過程是典型的勞動密集型，據(jù)了解，單件產(chǎn)品的揀貨作業(yè)成本占配送成本的30%～40%之多，揀貨作業(yè)勞動量占倉庫總作業(yè)量60%，并且作業(yè)時間占到總時間的40%[1]。雖然倉庫揀貨作業(yè)趨向于無人化，但無人化技術(shù)的推廣需要投入大量資金，現(xiàn)階段無人倉還未完全普及，所以絕大部分的倉庫仍處于人工倉。倉庫揀貨作業(yè)一般分為兩個步驟：一是分配客戶訂單，產(chǎn)生揀貨單計劃；二是由揀貨員進(jìn)行商品揀取任務(wù)。前一個步驟執(zhí)行過程中，不合理的訂單分配方式會引發(fā)訂單周期較長、商品錯誤率高等問題；后一個步驟中，不合理的路徑規(guī)劃會產(chǎn)生較多不必要的重復(fù)行走路線，導(dǎo)致搬運(yùn)成本增加。因此，合理規(guī)劃倉庫中的揀貨作業(yè)環(huán)節(jié)，提高揀貨作業(yè)效率具有研究價值。

目前已有國內(nèi)外學(xué)者針對倉庫揀貨作業(yè)中存在的問題進(jìn)行了大量的研究和分析。從訂單分配層次，Khojasteh 等[2]就如何在最短時間內(nèi)完成客戶訂單檢索這一問題描述成一個非線性規(guī)劃模型，討論了一個多通道自動化倉庫中的訂單揀配問題。Bozer 等[3]運(yùn)用兩種訂單揀選系統(tǒng)（Miniload 系統(tǒng)和Kiva 系統(tǒng)）處理同一組客戶訂單，得出預(yù)期的檢索時間。王旭坪等[4]構(gòu)建以總服務(wù)時間最短和分區(qū)均衡度最優(yōu)的雙目標(biāo)訂單合并優(yōu)化模型，研究如何合理進(jìn)行訂單合并優(yōu)化。盧燁彬等[5]創(chuàng)新性地將引力模型應(yīng)用到波次劃分模型中，以波次內(nèi)不同儲位商品之間的引力大小衡量訂單之間的相似度，從而進(jìn)行訂單的波次劃分。揀貨作業(yè)路徑規(guī)劃是否合理直接影響揀貨作業(yè)的效率和人工成本，因此，研究者致力于優(yōu)化揀貨作業(yè)路線。Lu 等[6]任務(wù)訂單的揀選是影響倉庫業(yè)績的關(guān)鍵因素，并提出了一種干預(yù)路由算法來解決動態(tài)路徑規(guī)劃問題。Hong等[7]介紹了一種采用S形路由方法并行-過道訂單揀選（SRSB）的路徑選擇訂單批量模型。郭興海等[8]提出了一種兩階段的全局路徑規(guī)劃方法，促進(jìn)了無人倉庫高效運(yùn)轉(zhuǎn)。孫軍艷等[9]提出并設(shè)計動態(tài)貨位調(diào)整與人工揀貨協(xié)同作業(yè)的動態(tài)揀貨策略，針對雙區(qū)型倉庫，以揀貨時間最短為目標(biāo)函數(shù)構(gòu)建數(shù)學(xué)模型，進(jìn)一步提高揀貨效率。王轉(zhuǎn)等[10]構(gòu)建基于節(jié)約里程的訂單分批模型，有效地減少了揀貨行走總距離和平均行走距離。

然而，少有學(xué)者同時從訂單分配方式和路徑規(guī)劃兩個層次對揀貨作業(yè)規(guī)劃進(jìn)行研究。所幸，已有學(xué)者注意到上述差距。Giannikas 等[11]介紹了一種動態(tài)的揀貨策略，在揀貨周期中更新揀貨路線和訂單分配。王華東等[12]采用訂單動態(tài)時間窗分揀策略，倉庫揀貨路徑優(yōu)化算法，重點(diǎn)對跨境電商保稅倉庫揀貨流程進(jìn)行分析與優(yōu)化?；诖?，本文的主要工作有：（1）針對不同訂單分配方式下的揀貨路徑規(guī)劃問題，以京東典型的雙區(qū)型倉庫為例，建立與之相適應(yīng)的路徑規(guī)劃模型，并設(shè)計了算法——S型啟發(fā)算法和遺傳算法。（2）通過算例仿真，將不同訂單分配方式下的結(jié)果進(jìn)行對比，并比較分析兩種算法下的仿真結(jié)果。（3）選擇最優(yōu)的訂單分配方式和算法，組合形成較優(yōu)的倉庫揀貨作業(yè)規(guī)劃。

2 問題描述

如圖1所示，首先確定了兩種揀貨方式，即單一揀貨與批量揀貨。其次，運(yùn)用三元組α/β/γ 方法分析揀貨路徑規(guī)劃問題特征與布局特點(diǎn)。然后根據(jù)雙區(qū)型倉庫的布局特點(diǎn)，建立以最小化揀貨路徑為目標(biāo)的路徑規(guī)劃模型。最后，設(shè)計兩種算法（S型啟發(fā)式算法與遺傳算法）進(jìn)行算例仿真，對比兩種算法下的路徑，得出最優(yōu)解。

圖1 倉庫揀貨作業(yè)設(shè)計過程圖

2.1 兩種揀貨方式

單一揀取即在同一時間，一名揀貨員只揀取一個客戶訂單，一個客戶訂單相應(yīng)形成一個揀貨單，揀貨員揀取完成后，可直接打包配送至客戶。本文假設(shè)每一個訂單中商品總量都小于或等于揀貨車的最大裝載商品數(shù)量，即一個訂單只能夠用一輛揀貨車揀取。

批量揀取是將一些客戶訂單中的待揀商品集中起來在一張揀貨單上呈現(xiàn)，并只由一名揀貨員揀取，這減少了很多不必要的重復(fù)行走路線。由于揀貨車的最大裝載商品數(shù)量有限，且假設(shè)每一客戶的訂單不允許分割，若總訂單中商品數(shù)量較大，則需要進(jìn)行訂單分批，使得每批訂單中的商品總量都小于或等于揀貨車的最大裝載商品數(shù)量。本文采用訂單包絡(luò)算法[13]對總訂單進(jìn)行分批處理。

2.2 揀貨路徑規(guī)劃問題與布局特征分析

（1）資源環(huán)境（α域）：揀貨員從倉庫的進(jìn)/出口出發(fā)，按照揀貨單去各個不同的貨位揀取商品，直到揀貨單上的所有商品揀取完成，回到倉庫的進(jìn)出口位置，意味著一次揀貨作業(yè)的完成。結(jié)合調(diào)度理論在服務(wù)業(yè)中的應(yīng)用，在這種情形下，倉庫中的商品是資源，而對揀貨員的路徑規(guī)劃服務(wù)是任務(wù)。（2）任務(wù)特征和約束（β域）：揀貨員從倉庫進(jìn)出口出發(fā)，揀取完商品后，返回倉庫進(jìn)出口，具有再循環(huán)的特征。在問題中，存在一系列約束條件：揀貨車有容量限制，一張揀貨單的商品數(shù)量不能超過揀貨車容量；任意兩個待揀商品之間只有一條路線等。（3）調(diào)度目標(biāo)（γ 域）：本模型的主要目標(biāo)為最小化揀貨路徑。

3 揀貨作業(yè)路徑規(guī)劃模型

在對客戶訂單的處理過程后列出相應(yīng)的揀貨單，揀貨員拿著揀貨單推著揀貨車從倉庫進(jìn)/出口到各個待揀商品的儲位揀取相應(yīng)的商品，直到將揀貨單上的所有貨品揀取完，返回倉庫進(jìn)/出口。本文根據(jù)京東典型的雙區(qū)型倉庫布局的特點(diǎn)，建立以最小化揀貨路徑為目標(biāo)的路徑規(guī)劃模型。

3.1 基本假設(shè)

假設(shè)1N為倉庫中的總儲位數(shù)，每個儲位只能存放一種商品，一種商品只能放在一個倉庫儲位上。

假設(shè)2每一張揀貨單最少有一種商品，最多包含Q種商品（Q為一輛揀貨車的最大裝載商品數(shù)量）。

假設(shè)3每位揀貨員在同一時間內(nèi)只負(fù)責(zé)揀取一張揀貨單，每個揀貨單中的商品數(shù)量不得超過揀貨車的最大裝載商品數(shù)量Q。

假設(shè)4在同一條巷道中揀貨時從一邊的儲位轉(zhuǎn)身另一邊儲位的距離忽略不計。

假設(shè)5揀貨單上的待揀商品在倉庫中均不缺貨。

3.2 參數(shù)設(shè)置

建立數(shù)學(xué)模型的部分主要相關(guān)參數(shù)如表1所示。

表1 符號說明表

3.3 路徑分析

對客戶提供的商品訂單進(jìn)行處理后，形成多張揀貨單，一張揀貨單只能由一名揀貨員進(jìn)行揀取任務(wù)。一張揀貨單內(nèi)有n種商品(n∈[1,Q]) ，每種商品需揀取qi個，且一張揀貨單的商品總數(shù)量不能超過揀貨車最大裝載商品數(shù)量Q。

在本文的倉庫設(shè)定中，倉庫被分為東、西兩個半?yún)^(qū)，有一條主通道、兩條邊通道，巷道垂直于三條通道，在巷道的兩側(cè)是裝載商品的貨架，未開封的商品放在高層貨架上，需揀取的商品全部放在底層貨架的儲位上。揀貨員憑借揀貨單在巷道內(nèi)對商品進(jìn)行揀取，沿著每條通道都可以進(jìn)入任意巷道內(nèi)。倉庫只有一個進(jìn)/出口，揀貨員從該口出發(fā)，揀貨完成后需返回該口。進(jìn)/出口正對西半?yún)^(qū)的邊通道，巷道從離進(jìn)/出口由近到遠(yuǎn)一次為巷道1至巷道10，商品的儲位寬度為D1、巷道的寬度為D2、儲位深度為D3、主通道的寬度為D4。設(shè)用[x,y,z]來表示每個商品的儲位位置，商品所在的巷道數(shù)用x來表示；y表示商品儲位序號，yi∈[1,b],1 → 0.5b表示商品在倉庫西半?yún)^(qū)范圍，0.5b→b表示商品在倉庫東半?yún)^(qū)范圍；z表示巷道兩側(cè)商品，z∈( 0,1) ，z為1 時，揀取巷道內(nèi)距離進(jìn)/出口較遠(yuǎn)儲位的商品，z為0 時，揀取距離進(jìn)/出口較近儲位的商品。因為揀貨員在同一條巷道中揀貨時從一邊的儲位轉(zhuǎn)身揀另一邊儲位的距離忽略不計，商品儲位坐標(biāo)可以用[x,y]表示。該倉庫基本結(jié)構(gòu)如圖2。

圖2 雙區(qū)型倉庫基本結(jié)構(gòu)圖

倉庫內(nèi)任意商品儲位用坐標(biāo)表示為：

根據(jù)商品所在位置有所不同，分情況寫出了任意兩個商品之間的最短距離dij的表達(dá)公式（i、j表示揀貨單上任意兩個揀貨商品）。

（1）當(dāng)揀貨單上任意兩個待揀商品儲位分布在同一半?yún)^(qū)時，即，則求解dij可分為以下三種情況：

①當(dāng)揀貨區(qū)的任意兩個商品的儲位都在同一半?yún)^(qū)、同一巷道內(nèi)時，即xi=xj，y1,y2∈[1 , 0.5b]ory1,y2∈[0.5b,b]，則dij可表示為：

②當(dāng)揀貨區(qū)的任意兩個商品儲位位于倉庫西半?yún)^(qū)、不同巷道內(nèi)時，即xi≠xj，y1,y2∈[1,0.5b]，則dij可表示為：

③當(dāng)揀貨區(qū)的任意兩個商品儲位位于倉庫東半?yún)^(qū)、不同巷道內(nèi)時，即xi≠xj，y1,y2∈[0.5b,b]，則dij可表示為：

由倉庫進(jìn)/出口到達(dá)任意商品儲位點(diǎn)的距離d0i的求取公式可表示為：

則揀貨作業(yè)過程的總路徑D的函數(shù)可表示為：

決策變量：

d01與dn0分別表示在一次揀貨作業(yè)過程中，揀貨員從倉庫進(jìn)/出口到揀取的第一個商品的距離；從揀取的最后一個商品到倉庫進(jìn)/出口的距離。

3.4 模型建立

綜上所述，揀貨作業(yè)路徑規(guī)劃模型如下所示：

在模型中，公式（9）為目標(biāo)函數(shù)，求解在一次揀貨作業(yè)過程中揀貨員行走的最短總路徑；公式（10）和公式（11）分別表示揀貨員揀貨過程中從商品i到商品j和從商品j到商品i的總次數(shù)都為1，也就是說：任意兩個待揀商品之間只有一條路線；公式（12）表示在一次揀貨作業(yè)時商品總量不能超過Q；公式（13）為分段函數(shù)，分別表示任意兩個商品的儲位“位于同一半?yún)^(qū)、同一巷道內(nèi)時”“位于倉庫西半?yún)^(qū)、不同巷道內(nèi)時”“位于倉庫東半?yún)^(qū)、不同巷道內(nèi)時”“位于在不同半?yún)^(qū)時”這四種情況下倉庫中兩個待揀商品儲位之間的最短距離；公式（14）為分段函數(shù)，分別表示由倉庫進(jìn)/出口到達(dá)位于西半?yún)^(qū)和東半?yún)^(qū)中任意商品儲位點(diǎn)的最短距離。

4 算法設(shè)計

在一個調(diào)度問題中當(dāng)機(jī)器和任務(wù)人多時，求解一個最優(yōu)解的計算時間是難以估算的，因此尋找一個能在比較短的時間內(nèi)找到較好調(diào)度的啟發(fā)式算法是非常有必要的[14]。因此，本文采用了兩種啟發(fā)式算法求解路徑規(guī)劃模型，即S型啟發(fā)式算法和遺傳算法。其中S型啟發(fā)式算法是一種較簡單基礎(chǔ)的尋找較優(yōu)可行路徑的方法，操作簡單，容易實現(xiàn)，在許多倉庫管理系統(tǒng)中得到了廣泛的應(yīng)用，而遺傳算法的基本思想是模擬自然界遺傳機(jī)制和生物進(jìn)化論而形成的一種過程搜索最優(yōu)解的算法，是應(yīng)用領(lǐng)域廣泛、計算能力較強(qiáng)的全局優(yōu)化算法[15]，由此，將S型啟發(fā)式算法得出的結(jié)果與遺傳算法的結(jié)果相比較，從而可驗證遺傳算法的有效性。

4.1 S型啟發(fā)式算法

此算法在揀貨過程中行走路線的思路是：從距離進(jìn)/出口最近的通道出發(fā)進(jìn)入存在待揀商品的巷道，（1）當(dāng)存在商品在該巷道中的儲位離所在通道的距離大于巷道的一半長度時，則揀貨員從所在通道由近及遠(yuǎn)揀取該巷道內(nèi)的待揀商品然后走過該巷道，從另一端巷道接著進(jìn)入下一巷道繼續(xù)揀貨；（2）當(dāng)不存在商品在該巷道中的儲位離所在通道的距離大于巷道長度的一半時，則先揀取離所在通道距離最遠(yuǎn)的商品，再由遠(yuǎn)及近揀取該巷道內(nèi)的商品并返回到原來通道進(jìn)入下一巷道繼續(xù)揀貨；（3）如果該巷道上沒有商品可揀取，則跳過此巷道進(jìn)入下一巷道繼續(xù)揀貨。重復(fù)以上三個規(guī)則，直到完成對揀貨單上的商品的揀取。

本文以雙區(qū)型倉庫為例，提出了S 型啟發(fā)式算法的具體操作，如圖3 所示：從最接近進(jìn)/出口的西邊通道出發(fā)，按離進(jìn)/出口由近及遠(yuǎn)的巷道順序依次揀取西半?yún)^(qū)的待揀商品，揀取完西半?yún)^(qū)的所有商品后，然后再從主通道開始按離進(jìn)/出口由遠(yuǎn)到近的巷道順序一次揀取東半?yún)^(qū)的待揀商品，揀取完東半?yún)^(qū)的所有商品后返回進(jìn)/出口。因S 型啟發(fā)式算法的操作簡單容易實現(xiàn)，所以在算例仿真中采用手動計算規(guī)劃出的揀貨總路徑。

4.2 遺傳算法

（1）染色體編碼。將染色體定義為由揀貨單中的待揀商品種類基因組成，根據(jù)揀貨單整理出待揀商品種數(shù)，在進(jìn)行數(shù)值仿真之前首先為其進(jìn)行編號，設(shè)n為揀貨單上的待揀商品的種數(shù)，且每一種待揀商品編號唯一，待揀商品編號由兩位十進(jìn)制數(shù)表示，對每一商品都有其對應(yīng)的揀貨次序，如染色體“01，03，05，02，04”代表該揀貨單有5 種待揀商品，對于編號03 的商品，它對應(yīng)的揀貨次序是2，也就是說揀貨員第2 個揀取的商品是03。

（2）種群初始化。根據(jù)揀貨單可知待揀商品上的種類、數(shù)量及位置編號，設(shè)計代碼程序求商品儲位點(diǎn)到進(jìn)/出口的距離以及倉庫中任意兩個商品儲位點(diǎn)的最短距離。在生成揀貨作業(yè)路徑規(guī)劃方案時，隨機(jī)生成一組m個包含n個待揀商品儲位編碼號的初始方案，并且分別計算目標(biāo)函數(shù)值。

圖3 S型啟發(fā)式算法揀貨流程圖

（3）適應(yīng)度函數(shù)。本研究問題中目標(biāo)為最小化揀貨作業(yè)總路徑，據(jù)此適應(yīng)度函數(shù)為minD。

（4）遺傳算子。

①選擇。首先將初始種群進(jìn)行適應(yīng)度的評估，產(chǎn)生新種群后，以概率ps舍棄劣勢個體，將適應(yīng)度高的種群保留進(jìn)入下一輪的自我復(fù)制。

②交叉。交叉運(yùn)算在遺傳算法中起著核心的作用，其有利于組合之間傳遞新的信息，通過信息的交換和組合，有利于快速得到最優(yōu)解。本文根據(jù)交叉概率pc=0.85，從生成的種群中選擇交叉的個體。例如，選取兩個染色體A、B進(jìn)行操作，使得生產(chǎn)的新染色體A′、B′。

式中，“|”為交叉點(diǎn)；“*”的填入方式為（以染色體A為例）：從染色體B的第1位開始向后依次比較，其若與染色體A的前2位數(shù)不同則填入染色體A的“*”中，若相同則跳過，將染色體A的“*”一一補(bǔ)齊，從而產(chǎn)生新的染色體。

③變異。根據(jù)變異率pm=0.02篩選出需要變異的個體。從每個被選擇的個體中隨機(jī)選擇兩個變異點(diǎn)，并交換兩個變異點(diǎn)的信息以獲得新的個體。

5 算例仿真

本文以雙區(qū)型倉庫環(huán)境為例，其中包含400個商品儲位，由1條主通道、2條邊通道和10條揀貨巷道組成。假設(shè)每次的揀貨量不超過30 件商品；儲位寬度D1=2 m、深度D3=2 m；揀貨巷道寬度D2=2 m；主通道寬度D4=4 m。假設(shè)在某一段時間內(nèi)某倉庫共收到了6個客戶訂單，訂單中商品的位置及數(shù)量如表2所示。

5.1 單一揀取方式下的仿真結(jié)果

在一輛揀貨車只揀取一個客戶訂單的情況下，6 個客戶訂單生成了6 個揀貨單，運(yùn)用遺傳算法和S 型啟發(fā)算法的仿真結(jié)果如表3所示。

5.2 批量揀取方式下的仿真結(jié)果

根據(jù)訂單包絡(luò)算法對6個客戶訂單進(jìn)行分批，共分為三批，分別是[1，2]、[3]、[4，5，6]，即訂單1 和2 在一張揀貨單上，訂單4、5和6在一張揀貨單上，訂單3在一張揀貨單上，如表4所示。

3張揀貨單運(yùn)用遺傳算法和S型啟發(fā)式算法的仿真結(jié)果如圖4和表5所示。

5.3 仿真結(jié)果

總訂單的具體改善數(shù)據(jù)如表6所示。

仿真結(jié)果表明，訂單分批后的總揀貨路徑比不分批的總路徑改善了很多，說明訂單分批策略能有效提升揀貨效率；根據(jù)路徑規(guī)劃仿真結(jié)果將兩種算法進(jìn)行對比，不同的算法對揀貨單上的商品的揀取次序有些不同，且遺傳算法下的揀貨路徑規(guī)劃較優(yōu)，從而驗證了遺傳算法的有效性。因此將訂單分批策略與遺傳算法下的揀貨路徑規(guī)劃相結(jié)合能得到較為合理的揀貨作業(yè)規(guī)劃。

表2 訂單中商品的位置及數(shù)量

表3 單一揀取路徑規(guī)劃匯總表

表4 分批后揀貨單中商品的位置及數(shù)量

圖4 三張揀貨單在兩種算法下的路線圖

表5 批量揀取路徑規(guī)劃匯總表

表6 總訂單匯總表

6 結(jié)語

設(shè)計較為合理的揀貨作業(yè)規(guī)劃，不但能夠解決目前物流配送效率低下的嚴(yán)峻問題，還能降低倉庫的成本。因此，為了提升揀貨作業(yè)效率，減少揀貨成本，本文以雙區(qū)型倉庫為對象，討論了不同訂單分配方式和揀貨路徑規(guī)劃，構(gòu)建相應(yīng)的模型，設(shè)計兩種啟發(fā)式算法進(jìn)行求解，以實現(xiàn)較為合理的揀貨作業(yè)規(guī)劃。但是本文研究的不足之處是只考慮了訂單分配的兩種基本方法，沒有深入考慮結(jié)合揀貨策略后的多種分配方式；同時在對路徑規(guī)劃的過程中只研究了進(jìn)行一次揀貨作業(yè)過程中的路徑規(guī)劃，沒有考慮多名揀貨員同時進(jìn)行揀貨作業(yè)時的路徑規(guī)劃情況。因此，如何結(jié)合實際揀貨作業(yè)情況選擇更為合適的訂單分配方式，并在路徑規(guī)劃模型之中添加多人的揀貨路徑規(guī)劃將是下一步主要的研究方向。