啟發式路徑下節約里程的訂單分批算法

王 轉，裴澤平

北京科技大學 機械工程學院，北京 100083

1 引言

隨著電商B2C業務的興起與發展，消費者的需求日益多樣化、個性化，電商配送中心訂單呈現出高頻次、小批量的特征。按單揀選的作業模式將大大降低揀貨效率，因此在電商配送中心內部多以批量揀選處理客戶訂單。人到貨批量揀選系統是電商物流中心中最普遍的揀貨系統，該系統下的揀貨時間主要受限于揀貨人員在揀貨途中的行走距離。因此，如何劃分揀貨批次以合并訂單，使揀貨人員行走距離最短成為提升揀貨效率的關鍵。

近年來，關于訂單分批策略的研究普遍集中在以不同方法求解分批問題上，例如先到先服務方法、排隊理論、種子算法及智能算法等。

先到先服務規則是最為常見的訂單優先級別劃分方法，依據訂單到達系統的時間先后進行合并，在不違反揀選設備容量的前提下，先到達的一批訂單首先成為一個批次被揀選出庫，因為先到先服務規則較為簡單，因此其優化結果也常被用來進行實驗對比[1-3]。Lam，Choy，Ho[4]等人借助排隊論思想，采用模糊邏輯方法對揀選系統中訂單設置優先級并以此為依據進而合并訂單，實驗結果表明，文中提出的計算方法生成的揀選任務序列使得揀選人員行走距離減少。Ho與Tseng[5]引入巷道指數權重這一概念，提出將巷道編號的指數作為巷道權重，并將完成訂單揀選所需經歷的巷道權重相加，訂單巷道權重最大的訂單作為種子訂單，利用種子算法對訂單合并問題進行求解。在運用智能算法方面，S?ren Koch，Gerhard W?sche[6]提出了一種結合局部搜索過程的分組遺傳算法求解訂單分批模型。Osman Kulak[7]采用禁忌搜索算法，并通過實驗證明該算法在求解訂單分批模型時表現效果優于先到先服務分批方法。Borja Menéndez，Eduardo G.Pardo，Antonio Alonso-Ayuso[8]等人提出了一個二階段的變鄰域搜索方法用于求解訂單分批模型，并且該方法可以找到一個較好的近優解及若干個保留下來的次優解。Soondo Hong，Youngjoo Kim[9]在考慮歷遍式揀選路徑的情況下提出了針對寬巷道物理模型的訂單分批模型求解方法。實驗選取了一個包含六個巷道的揀選系統和一批訂單，結果表明采用該方法后的總行走距離比按單揀選縮減少9.9%。此外，Ricardo Pérez-Rodríguez，Arturo Hernández-Aguirre，S.J?ns[10]用分布統計算法求解訂單信息未知的在線訂單分批問題。

同時，國內學者也熱衷于以新方法求解訂單分批模型，王旭坪[11]等人采用雙目標遺傳算法優化人工并行分區的揀選系統，結果表明該方法對小批量訂單的分區優化效果較為明顯。吳天行，郭鍵[12]通過構造基于圖論的訂單合并模型，通過基于圖論的合并算法求解模型，但圖論方法在求解大規模訂單數據時較為困難。馬廷偉，雷全勝，李軍[13]等人提出了一種利用改進二進制粒子群算法求解訂單分批模型的方法以求解小規模訂單分批問題。

綜上所述，當下國內外學者對于人到貨訂單揀選系統下的訂單分批問題的研究，主要集中于采用不同的方法求解訂單分批模型，如優先規則、排隊理論、智能算法（啟發式算法）等，并由其體現在對求解算法的創新上。然而，智能算法在求解較大規模的訂單分批問題時表現效果還有待探索，諸多研究中在算例驗證中采用的訂單規模數據較小[11-13]，無法確定算法是否在較大規模訂單數據下依舊表現優越。此外，電商環境下要求訂單履行中心盡快處理訂單，在較大規模下智能算法是否能夠高效的訂單分批操作也有待論證，小規模下的分批方法在面對大規模訂單數據的條件下很有可能失去造成訂單池淤塞癱瘓，進而降低揀選效率。

同時，對于人到貨揀選系統來說，能夠提供標準化的作業模式是重要的考慮因素，采用智能算法優化算法后生成的批量揀貨單行走路徑復雜多變，不易揀貨人員記憶，可行性差[14]。如果能在傳統的揀貨策略上研究較為可行的啟發式揀貨策略，將會對人到貨揀選過程的作業效率、服務水平以及降低物流成本具有重要價值。

因此，本文綜合考慮揀貨器具容積和商品包裝體積多樣化因素，以批次揀選單距離節約量最大化為目標，構建基于里程節約的訂單分批模型。結合啟發式路徑策略，構造距離節約量函數以合并訂單，提出基于訂單間節約里程量的訂單分批算法。最后將本文提出的D-eco算法（基于啟發式路徑下里程節約的訂單分批算法）與目前廣泛使用的FCFS方法（先到先服務方法）、SBBM方法（基于訂單相似度分批方法）進行性能分析對比，以探討D-eco算法在求解訂單分批問題時的優勢。

2 基于里程節約的訂單分批模型

2.1 問題描述

采用訂單合并的批量揀選策略可減少總的行走距離，提高揀選效率。通常情況下，訂單合并是將一組訂單集合分批為幾個小的訂單子集合，每個批次由一個揀選員工進行揀選。值得注意的是，每個合并批次都不能超過其揀選設備的容量，若超過容量，則應將超出部分的訂單分配到其他合并批次中。總的來說，訂單合并問題就是在揀選路徑策略、揀選設備、商品位置等信息已知的情況下，如何將一組訂單集合分為數組訂單批次，以最小化所有訂單批次的行走距離。

圖1至圖3證明了兩訂單合并揀選比分別進行揀選所行走的距離有所減少。圖1和圖2分別表示完成訂單1和訂單2在倉庫中需行走的路徑，假設訂單中所包含的商品在揀選貨架上的分布已知，且采用遍歷型揀選路徑策略。圖3則為訂單和合并后的行走路徑，從圖中可以看出合并后的路徑長度明顯要比單獨進行揀選所行走的距離短。訂單合并問題的特征與帶容量約束的車輛路徑問題相似，都是對客戶或商品訪問順序的優化。但不同的是，訂單合并問題需保持訂單的完整性，每個訂單的商品都必須在同一次揀選過程中完成，不得拆分。因此傳統的車輛路徑問題解決辦法無法應用到訂單合并問題上。

圖1 訂單1揀選路徑

圖2 訂單2揀選路徑

圖3 訂單1與訂單2合并后揀選路徑

2.2 模型假設

本文研究的對象是人到貨的訂單揀選系統，采用訂單合并策略來提高揀選作業效率。揀選區域布局如圖4所示，揀選區域中擺放若干組多層貨架，貨架中擺放不同的商品，假設貨架大小寬度相同，且每種商品能存放在貨架一處。揀選人員拿到揀選任務單后，依據訂單中商品位置和數量等信息開始揀選工作。員工駕駛叉車從入口出進入貨架間通道，依據事先規定好的揀選路徑策略在通道中行走，揀取任務單中的商品，并放置在叉車托盤中，當揀選完任務單中的所有商品后，員工回到入口等待接收下一批次的揀選任務。

圖4 揀選系統布置

本文研究對象為人到貨的整箱揀選系統，該系統采用P-C儲運模式，即以托盤（P）為單位存儲，以箱（C）為單位揀選，系統模型假設條件如下：

（1）揀選貨架為托盤貨架，一層用于揀選，二層以上用于存儲。

（2）貨架一層每個貨位為一個揀選點，每個揀選點唯一對應一個商品品規。

（3）采用托盤或籠車作為揀選器具，每次揀選可完成多個訂單的揀選（批量揀選）。

（4）每個訂單所訂商品的總體積不超過揀選器具的裝載體積。

（5）訂單不允許分割，即一個訂單只能分配給一個揀貨任務。

2.3 模型建立

以往研究者求解的傳統訂單分批模型[15]以分批后揀選距離最短為目標，在模型求解階段時還需考慮訂單合并依據（例如按訂單相似度合并），本文建立的訂單分批模型以批次揀選單距離節約量最大化為目標，配合距離節約函數，相比以往訂單分批模型更易求解。同時，以往訂單合并模型將全部商品體積視為相同的，均為“1”單位體積，本文引入商品堆碼數的概念，增加了對不同商品體積的考慮。

建立基于節約里程且考慮商品包裝體積的訂單分批模型，首先對模型中變量與常量做以下定義：

I：表示訂單集合，i∈I；

K：表示批次任務單集合，k∈K；

J：表示商品品規集合，j∈J；

Vmax：表示揀選設備最大容量；

qij：表示訂單i中品規 j的商品數量；

cj：表示訂單i中品規 j的商品堆碼數；

目標函數（1）表示訂單分批后，批次里程節約量之和最大；約束（2）為揀選設備裝載體積約束，表示每個批次商品總體積不超過揀選設備最大裝載體積；約束（3）表示一張訂單只能分配到一個批次任務中。該模型的解為向量Yk=(Y1k,Y2k,…,Ynk)，即第k個批次任務單的訂單組成。

3 基于里程節約的訂單分批算法

研究表明，訂單分批模型的求解屬于NP-hard難題[15]。且求解上述基于里程節約的訂單分批模型還需考慮路徑策略、商品包裝體積等因素，因此在面對大規模數據時求解難度較大，本章提出一種基于啟發式路徑策略下里程節約量的訂單分批算法對模型進行求解。

3.1 距離節約函數

圖5 “S&U”啟發式揀選路徑

3.2 “S&U”啟發式路徑里程算法

圖5為“S&U”型啟發式路徑策略，相比圖6中的歷遍式揀選路徑策略和返回式揀選路徑策略，“S&U”型路徑能夠有效減少揀貨行走距離。

在編寫揀貨路徑里程算法前，需對揀選區域特征參數進行定義，首先對揀貨任務單中各待揀巷道進行編號：例如某一揀貨單中涉及到3條待揀巷道，則按從左到右的順序3條待揀巷道的編號為A1、A2、A3，第i條待揀巷道編號為Ai，此外對算法流程中出現符號做如下介紹，符號示例如圖7所示。

P0：揀貨人員起點；

圖6 歷遍式揀選路徑與返回式揀選路徑

圖7 揀貨路徑算法參數示例

Tup：揀選區域上方通道；

Tdown：揀選區域下發通道；

Aleft：揀貨人員出發后距離其最近的待揀巷道；

Alast：揀貨任務單中最后一條待揀巷道；

L：巷道長度。

“S&U”型啟發式路徑里程算法流程如圖8所示，算法規則如下：

圖8 “S&U”型揀選路徑算法流程

（1）若巷道中所有待揀商品的位置距巷道入口的距離均小于巷道總長的1/2，則揀貨人員完成揀貨后折返至原通道并行走至下一條待揀巷道。

（2）若巷道中存在某待揀商品且其儲位距巷道入口的距離大于巷道總長1/2，揀貨人員并完成揀選并穿越巷道后到達倉庫另一端通道，行走至下一條待揀巷道。

（3）若巷道中不存在待揀商品，揀貨人員跳過該巷道行走至下一條待揀巷道。

（4）多次運用規則（1）～（3）至揀貨結束，并輸出揀貨人員行走總距離。

3.3 基于節約里程的啟發式訂單分批算法

在構造距離節約函數和確定揀貨路徑后，本文基于節約里程的改進式種子算法對訂單進行分批。該算法從全局角度入手，在不超過揀選設備容量的前提下，計算兩兩訂單的最大距離節約量，每次合并時均選取節約量最大的兩個訂單合并，直至訂單分批完成，算法流程如圖9所示。該算法主要步驟如下：

步驟1計算距離節約量。若訂單集合I中存在多個訂單，則計算各訂單間的距離節約；否則，執行步驟6。

步驟2訂單選擇。選擇距離節約量最大的訂單Im與In，訂單商品總體積分別為Vm與Vn。

步驟3合并訂單，判斷訂單容量是否滿足揀選設備體積約束。

若Vm+Vn≤Vmax，合并 {Im,In}后將{Im,In}加入I，并刪除Im與In，返回步驟1。

若Vm+Vn＞Vmax，違反體積約束，執行下一步。

步驟4選擇其余訂單合并。選擇Im與In中訂貨量更大的訂單（如Im），計算Im與其余訂單間的距離節約量。如果存在Il與訂單Im的距離節約量較大，且滿足Vm+Vl≤Vmax，則合并{Im,In}并刪除Im與Il，返回步驟1；否則，執行下一步。

步驟5直接生成揀選任務單。如果沒有訂單在滿足體積約束的情況下能合并Im，則Im直接生成揀選批次單，刪除I中的Im，返回步驟1。

步驟6 I中僅剩1張訂單，則其單獨成為一個批次揀貨任務單。

步驟7結束。

4 仿真分析與比較

基于MATLAB R2015a開發環境，設計不同訂單池規模的實驗方案，對前文提出的基于里程節約的訂單分批優化模型及算法進行仿真驗證。選取合適的評價指標，通過同FCFS、SBBM兩種方法的實驗對比，論證本文提出的D-eco分批算法在不同訂單規模下的有效性。

圖9 基于里程節約的訂單分批算法流程

4.1 參數設置

（1）揀選區域參數

實驗搭載的物理模型如圖10所示，其中托盤貨架一層用于揀貨作業，上層用于存儲，每個揀選點對應一種商品；揀選貨位尺寸與實際托盤式貨架相匹配；考慮到揀選設備作業空間面積，實驗中巷道寬度與實際托盤貨架揀選區中巷道尺寸相符；實際物流中心內部存儲品規較多，其中部分品規出庫次數頻繁，故往往對該類商品加以管理，專門設置揀選區以方便商品出庫，本仿真實驗設計的揀選區貨架共計10排8列，揀選點共計80個，揀貨人員從起點開始，沿巷道中心線行走，同時向左右兩邊揀貨。揀選區域詳細參數如表1所示。

（2）訂單池數據

圖10 實驗揀選系統布置

表1 揀選區域參數

實驗選取數據為某電商物流中心的真實訂單，鑒于一天中各時段下訂單處理系統的訂單池容量不同，因此本文設計選取5個容量不同的訂單池以代表不同規模的訂單數據進行實例驗證。訂單主要參數是通過EIQ數據分析后得到的訂單特征值：EN表示每張訂單的行數，EQ表示每張訂單的訂貨量，EIQ表示每張訂單每行訂貨量，實驗訂單池特征如表2所示。

表2 實驗訂單池參數

（3）評價指標

為衡量各訂單分批方法表現效果優劣，本文選取兩個指標對算法表現進行評價：

①揀貨總距離S：完成所有揀貨任務所行走的總距離，總行走距離是評價揀貨效率高低的直接標準，有效的分批方法可以減少路線迂回，大大減少揀貨距離。

②平均行走距離SK：完成每個揀貨任務單所走的距離，包含揀貨總距離和揀選任務單數量兩個維度，能夠更好地衡量揀選批次任務單的工作強度。

4.2 實驗方案

為研究本文所提出的D-eco分批算法的有效性，本文分別對FCFS、SBBM以及D-eco分批算法進行仿真程序設計，并生成揀貨路線圖用以指導揀貨人員按生成的批次揀選單及揀貨路徑進行作業。

FCFS算法由于其簡單性、快速性而被廣泛應用于現實生活中，FCFS方法的原理為按訂單到達時間順序排序后分批，直至不滿足揀選設備裝載體積約束時即形成一個批次。

SBBM算法包含兩個階段：第一階段選擇種子訂單，第二階段進行訂單合并。在訂單合并階段，首先選出的種子訂單作為訂單合并批次的初始訂單，再按照一定的標準將剩余的訂單加入到種子訂單中，SBBM算法以相同通道系數Simimn作為訂單間相似度的度量方式，即兩訂單相同待揀巷道數與兩訂單全部待揀巷道數的比值：

4.3 結果分析

三種分批方法的仿真實驗結果如表3與表4所示。其中表3為不同訂單池容量下三種方法輸出的揀貨任務單數K，表4為不同訂單池下三種方法輸出的總行走距離S和平均行走距離SK。

表3 不同訂單池下揀選批次數

表4 不同訂單池下平均行走距離和總行走距離

由表3中輸出的揀貨任務單結果可以看出，同一訂單池下，三種算法所得到的揀貨任務單數量K相差很小。分析可得，揀貨任務單數K受揀選設備裝載體積影響最大，其他因素對其影響很小。因此選擇其作為評價指標并不合適，本文僅用該輸出結果計算平均行走距離SK。

表4中的實驗結果表明，在各容量訂單池下，D-eco算法下的總行走距離最短，且實驗結果明顯優于FCFS算法；盡管在訂單規模較小（訂單池容量≤100）時，D-eco與SBBM算法所得的總行走距離S相差不大，但隨著訂單池容量增大，D-eco算法有效性愈發凸顯，當訂單池容量為250單時，D-eco算法下的總行走距離僅為1 983 m，其優化后揀貨總距離比FCFS多縮減了12.2%，比SBBM多縮減了2.1%。并且由圖11中的曲線斜率可以推斷：相比其他兩種算法，隨著訂單池規模增大，采用D-eco算法所節約的距離將更多。

圖11 三種算法下總行走距離S對比曲線

圖12 為三種算法下各揀貨任務單平均行走距離SK的對比圖。實驗結果表明，在各容量訂單池下D-eco的表現效果均優于FCFS和SBBM。由于FCFS忽略訂單間聯系，因此該算法下的揀貨任務單下的揀貨路徑將會有較多迂回，平均行走距離SK近乎于D-eco算法所得結果的2倍。SK同時包含揀貨總距離與批次任務單數量兩個維度，能夠更好地評價算法的有效性，因此說明本文提出的D-eco在各種訂單規模下的分批優化效果更好。

圖12 三種算法下平均行走距離Sk對比曲線

綜上所述，可得以下結論：

（1）D-eco所得的總行走距離S最短，且隨訂單數增加，其優化效果愈發明顯。

（2）D-eco所得的平均行走距離SK最短，揀貨人員完成D-eco生成的任務揀選單時將更迅速。

（3）三種算法中，隨著訂單規模的增大，D-eco能夠比FCFS和SBBM節約更多的行走距離。

圖13 某一揀貨任務單揀貨路徑圖

此外，為更好地指導揀貨人員持揀貨任務單進行揀貨，應對揀貨人員做出正確的路徑引導。圖13為仿真實驗生成的動態揀貨路線圖（該圖實際上為動態圖，揀貨順序和路線是動態可視的），揀貨人員需要揀選的貨位被標記在圖中，且揀貨人員行走路線符合“S&U”啟發式路徑策略，揀貨路徑圖的生成可以有效避免揀貨人員發生路線錯誤的情況，與僅顯示分批結果的單據相比，結合路徑動態圖的揀選任務單更適合于實際揀貨作業。

5 結束語

本文首先構建基于節約里程的訂單分批模型，模型中首次新增了商品堆碼數這一參數，將商品包裝體積多樣化納入考慮；采用“S&U”型啟發式路徑策略，并設計“S&U”型啟發式路徑算法以計算揀選訂單里程；構造距離節約函數計算訂單間里程節約量作為訂單合并依據；設計基于節約里程的訂單分批啟發式算法進行訂單合并；最后，在不同訂單池容量下對FCFS、SBBM、D-eco三種訂單分批方法進行仿真實驗。結果表明，D-eco算法表現效果最好，能夠有效減少揀貨行走總距離和平均行走距離。在5種不同訂單池容量下，采用D-eco算法進行分批優化后的揀貨總距離平均比FCFS多縮減了12.2%，比SBBM多縮減了2.1%。

綜上所述，本研究從物流中心存在的實際操作問題出發，綜合考慮不同商品體積、揀選設備裝載體積等條件和約束，提出了一套有效的訂單分批方法。該方法豐富了訂單分批算法，計算效率高，優化效果明顯，對于電商配送中心人到貨的揀選具有較高的應用價值。同時，該方法下的揀貨路徑更適合應用到實際揀選作業中，可為企業物流中心的運作管理提供決策支持。另外，本文的研究成果同樣可以應用到人到貨的零揀系統中。