訂單尋倉與分批揀選聯合調度問題研究

（上海海事大學 物流科學與工程研究院，上海 201306）

0 引言

隨著電商的發展，網購已經成為大眾主要的購物消費方式之一。企業為了吸引客戶流量，提高商品銷量，頻繁開展促銷活動，訂單的數量和規模都急劇增加。當庫存水平降低，單個倉庫越來越難以滿足訂單需求，導致訂單拆分情況頻繁發生。大量的訂單分配到倉庫后，導致倉庫揀選作業量繁重，訂單履行時間變長。訂單的拆分和訂單履行時間的延長不僅增加了物流成本也降低了客戶滿意度。倉庫作業是訂單履行的主要落地場景，訂單揀選又是最耗費人力和時間的環節，影響到整個倉庫的作業效率以及作業成本。目前，倉庫訂單揀選普遍采用的方法之一為分批揀選。因此，將訂單尋倉和訂單分批問題聯合優化能夠提升倉庫作業效率，降低訂單履行成本，從而提升訂單履行整體效果。

針對電商訂單履行中的訂單尋倉問題，國外學者對降低訂單履行過程中的拆單率做了較多研究。Xu[1]等利用訂單下達到發貨之間的延遲時間，對客戶訂單進行重新分配，降低了訂單的拆單率。Liu[2]等建立了兩級物流模型，目的是將在線訂單分配至配送中心，同時能滿足區域內的門店銷售需求，運用拉格朗日松弛法求解模型，降低了物流成本。Mahar和Wright[3]提出了一種動態訂單履行策略，通過對訂單的積累和庫存信息的充分利用，以減少訂單履行的等待、庫存和運輸成本。Acimovic和Graves[4]通過對未來訂單履行成本進行估計，以當前訂單履行成本和未來預估成本之和為目標建立模型，并設計了啟發式算法降低了運輸成本。Jasin and Sinha[5]未來訂單考慮在內，用一個確定的模型來近似考慮往后不確定的銷售機會的多商品在線訂單分配問題的模型，設計了啟發式算法降低包裹數量和運輸成本。Ardjmanda[6]等在訂單履行問題中考慮了運輸過程中的包裝問題，以最小運輸成本和時間為目標建立數學模型，設計了多目標遺傳算法，最終降低了運輸成本以及運輸時間。Ishfaq[7]研究了全渠道下在線零售商的訂單履行問題，考慮了供應商、區域倉庫、電商倉、門店聯合發貨下的訂單履行成本，設計了啟發式算法最終降低了總成本。

國內學者更傾向于聯合倉儲、配送問題進行綜合研究。張源凱[8]研究了一地多倉環境下網上超市訂單分配問題，將訂單尋倉和車輛調度問題結合建立模型，設計了能夠快速生成較優解的啟發式算法。李建斌[9]等通過在銷售初期對商品在各倉庫中的數量進行優化分配，減少了銷售過程中的拆單率。徐浩軒[10]研究了電商在預判發貨背景下雙模式運輸的動態批量配送優化問題，為三級供應鏈系統建立數學規劃模型，并設計了動態規劃算法求解，算例證明了該算法的有效性。師嘉欣[11]研究了城市物流配送訂單履行問題，設計啟發式算法優化整體履行效率。

另外，針對電商倉庫的倉庫揀選問題，也有學者進行了大量的研究。對于訂單分批問題，Wang[12]研究了在線訂單情況下的訂單分批問題，考慮了訂單批次的完成時間，以最小化所有批次揀選時間為目標建立數學模型，基于啟發式算法中提出的新的規則求解，提高了訂單的交付效率，平衡了工作量。王旭坪[13]研究了訂單動態到達情況下，考慮揀選員工數量、揀選設備容量的電商倉庫訂單分批揀選問題，采用改進的固定時間窗訂單分批啟發式規則求解，降低了訂單揀選時間。針對新零售情景下的訂單揀選作業優化問題，張寧[14]考慮了新零售揀選時效、揀選策略以及分區揀選工作量均衡等因素，以訂單揀選完成時間和各批次訂單的分區揀選完成時間標準差之和最小為目標函數建立模型，并采用帶精英策略的非支配排序遺傳算法求解。王迪[15]研究了訂單分批和批次分配的聯合問題，以最小化批次揀選延時時間為目標建立了數學模型，并提出了一種基于一定規則的混合算法，減少了訂單處理延時時間。王轉[16]考慮揀選器具和商品包裝體積,構造以最大化里程節約量為目標的訂單分批模型，提出基于啟發式揀選路徑下節約里程的訂單分批算法，降低了揀選路徑。王華東[17]針對跨境電商客戶訂單的多品類且數量不穩定的特點，采用訂單動態時間窗分揀策略,并在倉庫揀貨路徑優化的基礎上,建立了跨境電商保稅倉庫揀貨模型，提出了適用于跨境電商保稅倉庫的波次分揀策略，降低了揀選路徑長度。另外，楊宏燕[18]構建了以作業時間最短、成本最小為目標，滿足交貨期限制、等約束下電商企業倉庫出庫作業計劃編制優化模型，并設計了遺傳算法求解，提高了倉庫作業效率，降低了成本。

目前學者對訂單履行過程中的訂單尋倉問題已進行了充分研究，主要研究內容是通過對訂單的延時處理，即積累一定量的訂單，再充分利用庫存信息或者對未來的銷售機會進行評估，調整訂單分配的倉庫從而減少訂單的拆單率，降低物流成本。然而，隨著電商發展，電商訂單趨于多批量，小規模的特點，日常銷售過程中拆單率日益降低，只有在電商促銷場景下，訂單尋倉問題才更具有優化空間。并且，電商訂單履行過程還包括倉庫作業和配送等環節，訂單揀選是倉庫作業中占用人力、時間最多的環節，訂單量的上升也加大了倉庫的作業量。對于電商倉庫揀選的研究，學者們的研究集中在如何將倉庫已接受在線訂單在滿足發貨時間約束下進行分批處理。然而，訂單分配到不同倉庫直接決定倉庫的揀選作業，因此，在訂單尋倉的成本和揀選作業效率二者之間尋找到一個平衡點能夠提高訂單履行的整體效率。

本文以最小化訂單履行總成本和揀選路徑長度為目標，建里多目標數學模型，并設計了三階段啟發式算法：首先將訂單分配到合適的倉庫，目標是總成本最小，再以一定規則生成初始訂單批次。同時，調整訂單批次，使得所有批次的巷道數量和減少，從而提高揀貨效率。實驗結果證明，三階段啟發式算法能夠有效提高訂單履行的整體效果。

1 問題描述與模型建立

1.1 問題描述

本文研究的問題包括電商訂單履行的兩個階段，如圖1所示，第一階段為訂單尋倉，客戶訂單到達后，電商首先要決定該訂單由哪些倉庫發貨，傳統電商發貨策略為先就全，再就近，即優先單倉發貨，單倉不能滿足發貨則由最近的倉庫聯合發貨。訂單到達倉庫后，為了提升揀貨效率，需要對訂單進行分批操作，每個揀貨員每次揀選一個批次訂單，針對訂單分批問題，本文采用遍歷策略，即揀貨員從入口出發，遍歷每個含有批次中商品的巷道并取走商品，然后再返回入口處。訂單批次的巷道數越少，揀貨員的行走距離越短，揀貨效率越高。

表1列出了兩個倉庫的庫存信息以及分別到兩個訂單接收地的運輸費用，假設倉庫固定處理費用為5元。當訂單1先到達時，根據先就全，再就近的原則，倉庫1距離訂單1的收貨地址最近，且滿足需求，則將訂單1分配給倉庫1，同時更新倉庫的庫存信息，庫存剩余為1和1，訂單1產生的履行成本為固定費用5元和運輸費用10元，共計15元。之后，訂單2到達，根據就全原則，沒有單個倉庫能夠滿足商品A的數量需求，而倉庫1和倉庫2距離訂單1的收貨地址較近，且總庫存滿足需求，則將訂單2分配給倉庫1和倉庫2，產生固定成本10元和運輸成本26元，共計36元。該業務場景下將產生倉庫固定費用和運輸費用共計51元。

圖1 訂單履行流程

表1 倉庫庫存和運費

表2 訂單需求

現在對這一場景做一個優化，如果訂單1和訂單2先后到達，優先處理訂單2，那么訂單2將被分配給倉庫1，倉庫1剩余庫存變為0和1，那么訂單2的成本為16元，當訂單1到達后，倉庫1庫存不能滿足，則分配給倉庫2，倉庫2剩余庫存變為0和1，成本為18。可見，與原始策略相比，倉庫剩余庫存并沒有變化，然而總成本變為34，成本減少了17元。

表3 倉庫訂單

對于第二階段的訂單分批問題，表3展示了第一階段的分配結果，以及每個訂單所處的巷道，假設有3個巷道，每個訂單在不同倉庫中的巷道情況相同。可知，倉庫1和2都需要揀選2個巷道，倉庫3的揀選作業只要經過1個巷道，將訂單3重新分配給倉庫1，成本上升了2元，但是總的揀選路徑長度減少了一個巷道的距離。訂單履行過程中不僅要考慮運輸成本，倉庫作業效率的提升也將減少倉庫作業成本，提高發貨速度。

1.2 基本假設

本文提出了如下假設。所有訂單需求能夠被滿足保證了算法運行的順暢；倉庫配置相同為模型提供了理想化的業務場景，本文提出的算法依然能夠處理倉庫配置不同的情況；為了突出核心問題，不考慮堵塞情況。此外，假設訂單能夠一次揀選完成。

假設1：所有訂單都能被履行，不存在倉庫缺貨情況；

假設2：所有倉庫除庫存余量信息以外的內部基礎設施、人員配置相同；

假設3：訂單揀貨過程中不考慮堵塞情況；假設4：同一批次訂單能夠一次揀選完成。

1.3 模型建立

首先對本文模型的變量做出以下定義：

I：表示倉庫集合，I={i|i=1，2，…，m}；

J：表示訂單集合，J={j|j=1，2，…，n}；

K：表示商品種類集合，K={k|k=1，2，…，v}；

S：所有批次集合，S={s|s=1，2，…，u}；

ls：批次u的揀選路徑長度；

q：揀選批次最大容量；

c1：倉庫固定發貨成本；

訂單履行問題的模型定義如下：

約束條件：

式(1)和式(2)為目標函數，式(1)為最小化訂單履行成本，即倉庫固定處理成本和運輸成本的總合，式(2)為最小化倉庫揀選路徑長度。式(3)表示倉庫總發貨量不能超過庫存量。式(4)表示倉庫發貨量滿足每個訂單的需求。式(5)和式(6)確定了yij的值，yij用來計算倉庫的固定成本以及包裹數量。式(7)確保一個訂單只能分配至一個批次中，不能重復揀選。式(8)表示每個批次訂單商品數量不能超過批次上限。

2 基于聯合調度的三階段啟發式算法

2.1 算法基本思路

本文研究的是訂單履行過程中的訂單尋倉和訂單分批聯合調度問題，設計了三階段啟發式算法求解。第一階段是求解訂單尋倉問題，基于目前電商訂單的特點，訂單數量多，規模小，訂單拆分集中在多商品訂單中，所以將多商品訂單和單商品訂單分開處理，優先處理多商品訂單。第二階段訂單已經被分配到了合適倉庫，在種子算法的基礎上做一些調整為每個倉庫生成訂單分批問題的初始解。第三階段通過一定規則讓初始解在鄰域內擾動來減少所有批次包含的總數巷道，從而優化訂單分批問題。

2.2 三階段啟發式算法具體步驟

2.2.1 求解訂單尋倉問題

訂單尋倉問題的解與訂單處理順序有關，所以通過交換每個多商品訂單和它的關聯訂單的處理順序優化訂單尋倉問題的解，圖2為第一階段求解訂單尋倉算法流程。

Step1：生成訂單集合O。

Step2：將O中的訂單按照商品種類數量降序排列，優先處理多商品訂單。

Step3：為多訂單生成關聯訂單集合。對于任意多商品訂單，只要其余的多商品訂單中與該訂單有重合商品，則認為是該訂單的關聯訂單。

Step4：按照先就全，再就近的原則以訂單集合T中的順序處理訂單，并計算訂單履行成本。

Step5：令i=2。

Step6：將第i個訂單與前i-1個訂單中的關聯訂單交換位置，計算訂單履行成本F1，若F1＜F，則更新訂單處理順序；否則，轉step7。

Step7：檢查i是否為最后一個訂單，如果是，則結束；否則，令i=i+1，轉step6。

圖2 第一階段流程

2.2.2 生成初始訂單批次

對于一個倉庫中的訂單分批問題，將該倉庫的訂單分為多商品訂單任務集合T1和單商品訂單任務集合T2，再使用傳統種子算法分別生成初始批次。生成初始批次的規則是取一訂單作為種子批次，按照最大相同巷道數量為優先級，不斷加入訂單直到到達批次容量上限，并且加入的訂單與種子批次的相同巷道數量必須大于0，這有助于第三階段的解的改進。下面說明多商品訂單任務集合的分批過程，單訂單的批次生成方式與之相同，圖3為第二階段多商品訂單生成初始訂單批次流程。

Step1：將T1中的訂單按照巷道數量降序排列。

Step2：檢查T1是否為空，若為空，則結束；否則，轉step3。

Step3：取T1中第一個訂單，視一個批次，將剩余訂單與之對比，以相同巷道數量降序排列，將同巷道數大于0的訂單依次加入該批次中，直到到達批次容量上限或者無訂單可加入，轉step2。

圖3 第二階段流程

2.2.3 優化訂單分批

本階段將每個批次中的訂單按照一定規則在所有倉庫中進行搜索，選擇加入更加合適的批次，從而減少總批次數量和所有批次總巷道數，每個訂單只能重新分配一次。搜索停止條件為批次信息不再發生改變，圖4為第三階段優化訂單批次流程。

Step1：將所有倉庫中的種子批次按照批次中訂單數量升序排列，生成批次集合S，s表示第s個訂單批次。

Step2：令s=1。

Step3：對第s個批次中每一個訂單在所有倉庫的訂單批次中搜索，倉庫搜索的優先級是較近的倉庫優先搜索，若訂單能加入某一批次中，且加入后該批次的揀選巷道總數不變，滿足該倉庫庫存限制和該批次容量約束，則將該訂單加入該批次，從s中刪除該訂單；否則，保留該訂單。

Step4：若第s個批次是多巷道訂單批次，即該批次包含多個巷道，轉step5；否則，轉step6。

Step5：更新批次信息，轉step7。

Step6：若第s個批次為空，轉step1；否則，還原該批次，轉step7。

Step7：檢查是s否為最后一個批次，若是，則結束；否則，令s=s+1，轉step3。

圖4 第三階段流程

3 實驗分析

本文用python語言編寫程序代碼，實驗環境為windows10系統，Inter（R）Cor（TM）i3-8100 CPU@3.50GHz處理器，4GB內存。算例中訂單信息來源于某公司促銷活動當天產生的訂單、倉庫數據。實驗共設計了10個算例，在訂單600～1500的不同訂單數量下進行實驗。

模型中參數包括倉庫14個，庫存信息包含1000個sku，訂單1500條。倉庫共有8個巷道，巷道長度為60米，巷道間寬度為1.5米，揀選容量上限為15。倉庫地址和訂單地址在1500×1500km的范圍內隨機生成，倉庫固定費用為5元/訂單，運輸費用如表4所示。

表4 運輸費用

表5 實驗對比結果

本實驗對比的算法為FCFS-種子策略下的傳統訂單履行算法和遺傳算法。FCFS-種子算法即訂單按照到達順序以傳統訂單尋倉算法分配到倉庫，再由種子算法[19]生成訂單批次，種子算法的優先規則是最大相同巷道數量。由于本問題研究內容較新，所以設計經典智能優化算法遺傳算法（GA）作為對比，證明啟發式算法的有效性。表5列出了10個算例的實驗對比結果。

圖5為揀選路徑在三種算法下的對比圖。實驗結果表明，GA算法和本文提出的啟發式算法都能夠降低倉庫訂單揀選路徑長度。圖6為GA算法和啟發式算法對比FCFS-算法結果的路徑長度降低量，看出本文提出的啟發式算法在揀選路徑的優化上明顯優于GA算法。經過計算，啟發式算法平均提升了揀選效率7.6%。圖7為對比FCFS-種子算法下，訂單履行成本的降低量，GA算法優化效果非常不穩定，當訂單量增多時，將會增加訂單履行成本；而啟發式算法隨著訂單量增加，訂單履行成本優化效果越明顯，綜合能力優于GA算法。圖8顯示了啟發式算法所得訂單總包裹數的降低量，可以看出隨著問題規模上升，訂單的總包裹數量也隨之下降。綜上所述，啟發式算法能夠有效提升訂單履行整體效率，并且性能上優于遺傳算法，證明了算法求解該問題的有效性。

圖5 揀選路徑長度對比

圖6 揀選路徑降低量對比

圖7 成本降低量對比

圖8 包裹數量減少量

4 結語

本文研究了電商訂單履行過程中訂單尋倉和分批揀選的聯合問題，針對電商訂單的特點設計了三階段啟發式算法，將多商品訂單和單商品訂單分開處理，通過交換關聯訂單的處理順序，降低訂單履行成本和包裹數量；生成初始訂單分批解后，以一定規則使得解在領域內搜索，改進訂單分批問題的解。實驗結果表明，提出的算法能夠提升訂單履行的整體效率。然而，本文也存在一些不足，比如未考慮到倉庫揀選中的人員安排問題以及積累訂單將會影響到訂單履行過程的整個作業時間，所以下一步將對在揀選人員的安排以及考慮訂單積累量的影響做進一步的研究。