含批處理和多訂單任務的配送中心調度問題

冉文學，李子悅，焦香萍 RAN Wenxue,LI Ziyue,JIAO Xiangping

（云南財經大學 物流學院，云南 昆明 650221）

隨著商業的飛速發展，尤其是在電子商務環境下，訂單具有小批量、高頻次等特征，所以有必要對配送中心的訂單作業過程進行優化，提高揀選效率。而訂單分揀是配送中心作業的重要環節之一，傳統的倉儲操作中，訂單分揀是最耗費時間和勞力的一項工作，成本約占總倉儲費用的55%[1]。作為物流配送中心的重要組成部分，訂單分揀是整個訂單處理中最重要的環節，對整個物流配送中心的效率產生直接的影響。所以，如何對配送中心分揀系統進行優化一直是第三方物流企業非常關注的問題。

1 國內外文獻綜述

1.1 訂單分批處理

國內外學者對訂單揀選效率優化方法的研究主要集中在揀選路徑、訂單分批和分區揀選等方面，但Peterson[2]認為訂單分批策略更有利于揀選效率的提升。1990年Ackerman[3]首次提出了訂單分批的概念，之后陸續出現了相關研究。Bukchin[4]從最小化訂單延遲時間的角度決定訂單分批的開始時間。AH Azadnia[5]等人為了最小化訂單延遲提出了一種基于加權關聯算法和遺傳算法的混合算法來優化訂單的分批策略。孫洪華等（2014）[6]對訂單分批前后分別按照傳統穿越策略、S型策略和GA優化策略3種不同路徑方法進行分析，算例分析證明，采用訂單分批與GA路徑優化的策略組合，其揀貨路徑距離最短，節約量最大，效率可以提高40.33%。李曉杰（2016）[7]針對移動貨架倉庫系統中的貨位分配和訂單分批問題，分別設計了其相似度函數，并建立了聚類模型，提出了一種移動式貨架系統的策略評估模型，最后比較6種策略組合的效果，得出了具有現實指導意義的結論。胡小建等（2017）[8]提出了改進的Canopy-k-means算法，采用Canopy算法依據最大最小原則生成初始聚類中心，并使用k-means聚類算法對其進行優化獲取分批結果，針對不同規模的訂單數據集，比較了該算法和先來先服務、k-means以及Canopy-k-means算法的實際效果，結果表明：該算法可以避免k-means算法中k值選取的盲目性，同時可以有效地提高分揀效率以及降低分揀批次。

1.2 訂單分揀

基于自動化分揀系統（如圖1）的自動化分揀設備通過恰當的分揀作業，最后可以節省相當大的人工成本，而在傳統的物流配送行業里，平均訂單分揀一項就占運營成本的62.5%。

圖1 訂單分揀系統

Chen等[9]利用分揀系統流程多個訂單屬性之間的關聯提出一種數據挖掘方法，它基于整數規劃的聚類算法將訂單相關性作為目標變量0或1進行擬合，得到的模型經證明對解決問題具有一定的正向效應。邵劉霞等（2012）[10]考慮采取ABC存儲策略運用在客戶隨機到達的訂單中，將一些基礎的遺傳算法用在物品品類和數目隨機時的雙區型倉庫布局揀選路徑的優化，并以人工訂單系統為對象，建立了人工訂單揀選系統的優化路徑模型。冉文學等（2013）[11]為了提高分揀系統的效率將間歇停機考慮到自動化分揀線之間，研究出了一種新的物流設備一單元物料分揀訂單緩存器，實踐證明該研究可以將自動分揀線的間歇停機率優化了百分之二十，有效提高分揀線的分揀能力。李建明、雷斌等（2017）[12]在串行順序揀選策略的基礎之上提出了混合揀選策略，并建立了對應的時間模型，較大程度壓縮了訂單之間的間距，提高了分揀系統的揀選效率。

本文在現有研究的基礎上運用0-1混合整數規劃模型對3階物流中心調度問題建模，并且利用協同優化算法在不改變物流中心原本的硬件設備的基礎上對第2階段的一個子空間進行優化，從而達到提高物流中心作業效率的目的。

2 基于含批處理和多訂單任務的物流中心調度建模

2.1 問題描述

配送中心操作系統中存在有2種流向（到貨卸車流和裝車配送流）的訂單，其中任意一種流向的訂單都要歷經從到貨卸車到配送中心再到裝車配送3個階段，流向相同的訂單經歷的階段也相同；而對于任意一種流向的訂單，各個階段都有若干個無相關性的并行機可以供它選擇。在前沿作業環節，并行機屬于批處理機制，對應容納多臺輸送設備可以同時到貨卸車，即到貨卸車點。對于任意一種流向的訂單，每個階段都沒有緩沖區；對于任一種流向訂單的第2階段，即訂單在配送中心的分揀作業，有上游和下游設備以及訂單順序有關的準備和處理時間。綜上所述，本文將不同流向的訂單流歸納為2種訂單，即到貨訂單和配送訂單，并對含有批處理機制和多訂單任務特征的物流中心調度問題進行了簡潔的描述，如圖2：

在圖2中，含批處理機制和多訂單任務的物流中心調度問題具有下列特點：

（1）對于不同的訂單任務，階段1和階段3都有不同的專用機集合，它們分別為到貨訂單和配送訂單服務；

（2）對于配送中心的任何訂單，都歷經了3個階段，且每一個階段都有若干臺不相關的并行機供該種訂單選擇；

（3）相鄰兩個工序之間沒有緩沖區；

（4）階段1和階段3中，設備集合之間存在一部分的重合，這會使現有資源的競爭加劇；

（5） 在階段2中，任意訂單i的作業時間Hi2無法預知，但它與n（Oi1）和n（Oi3）之間的間隔路程成正比。n（Oi1）和n（Oi3）是訂單i在階段1和階段3的操作，因此Hi2與設備和順序呈正相關；

圖2 帶有批處理機制和多訂單任務的3階物流中心調度問題

（6） 階段2中，任意訂單i的準備時間pi2無法預知。若Oj2僅在Oi2之前，Oj2與Oi2間的計劃時間pj2i2也可用pi2表示，簡寫為pji2。那么pji2與n（Oj3）與n（Oi1）間的間距正相關，所以pi2和設備及順序有關；

（7）存在并行機，一次可以處理多個訂單。例如到貨卸車點的貨車，可以同時裝卸多個訂單。但是只有當階段2的設備與之協同配合，當前設備才能釋放。

2.2 數學模型

針對配送中心的調度問題，充分考慮到批處理、多訂單任務和無緩沖等特征，建立了0-1混合整數規劃模型，具體如下：

（1） 基礎符號

訂單索引i,j∈N=N-∪N+,i≠j,N-和N+分別為到貨訂單和配送訂單集；揀選流程索引L=1,2,3；S階段的設備索引mS∈MS，MS是S階段的設備集，是到貨訂單和配送訂單的設備集，存在分別表示物流中心的大門、混合分揀線、集貨卸車點和發貨裝車點的集合；分別表示非批處理機制和批處理機制的排序集合：表示訂單i在s階段的作業；分別表示屬于到貨訂單任務中的訂單i處于階段1和階段3的操作時間；表示屬于配送訂單任務中訂單i在階段1和階段3的作業時間；tab表示訂單從設備a到設備b的操作時間（已知）；H表示一個大數。

（2） 決策變量

若Ois在設備m進行操作，那么Xism=1，反之Xism=0；若Ois和Ojs在同一設備m上操作，那么Yijsm=1，反之Yijsm=0；若Ois是Ojs在m上的前一操作，則Zijsm=1，反之Zijsm=0；若Oi1和Oi3分別由m1和m3處理，那么Uim1m3=1，反之Uim1m3=0；若Oj2是Oi2的緊后操作，在m2處理，并且Oi3和Oj1分別由m1和m3處理，Vm2im3sm3=1，反之Vm2im3sm3=0；若OiS在PS處的順序索引為b，則，βiSb=1，反之βiSb=0；若OiS在PS的順序索引與Ojs一樣，則λijsb=1，否則λijsb=0；Pis為Ois的作業時間；Ris是Ois和Ojs之間的計劃時間（Ojs為Ois的緊后操作）；Tis表示Ois最初的處理時間。

假如只考慮階段2設備的準備時間，將其他階段設備的準備時間包括在操作時間里，混合整數規劃模型如下：

其中，目標函數（1）獲得最短的完成總時間；

公式 （2） 和公式 （3） 定義了3個元素（i,s,）m，擔保到貨訂單和配送訂單集合中的任意訂單的任何作業僅僅只能由一臺設備進行操作，并且強制定義了各項工序可以處理不同訂單任務中訂單的設備種類；公式（4） 定義了第1（3） 階段并行機的批處理能力（等于2）；

公式（5） 到公式（9） 定義了3個元素（i,k,b），確保任意Ois只占用Pk中的一個位置，同批訂單占用位置相同；

公式（10） 依據xism和xjsm來定義yjsm；

公式（11） 依據訂單是否同批定義λijsb；

公式（12）保證處于同一批的訂單絕對同機處理；

公式（13）保證處于同一批的訂單會被分配到相同的設備上，根據有關文獻，此非線性約束確定了4個元素（i,s,m,）b；

公式（14） 定義了當Ois為Ojs的前一作業時，zijsm=1；

公式（15） 表明只有當xi1m1和xi3m3的值都為1時，uim1m3的值才為1，反之為0；

公式（16）定義了和設備與順序有關的處理時間；

公式（17） 定義了當xi3m3,xj1m1和zij2m2的值都為1時，那么vm2im3km1=1，其他等于0；

公式（18）定義與設備及順序有關的計劃時間；

公式（19）保障所有訂單開始處理的時間都大于0；

公式（20）確保任意訂單在每個操作時間的順序；

公式（21）表示訂單要開始被處理時，它的時間必須滿足事先定義的順序限制；

公式（22）確保同批訂單在任意階段是同時開始處理的；

公式（23） 和公式（24） 表示只有訂單i的下一個操作Oi（s+1）開始，m才能被運行，且只有m做好準備，后一操作Ojs才能開始。

3 模型求解以及案例分析

含批處理機和多訂單任務特征的3階配送中心調度問題屬于大規模的組合優化問題，在多項式時間內不可能精準地解決此問題，所以必須對該3階配送中心的調度問題的每個子空間的每個子系統進行設計優化。本文設計了一種協同優化算法來解決基于階段2的物料搬運車狀態變化，如圖3。其得到的解的質量通過下面的仿真案例進行評估。

圖3中含批處理和多訂單任務的3階配送中心的調度問題的第2階段的設備—物料搬運車如果處于空車狀態，那么它將申請和獲取工作，此過程只發生在集貨卸車點X-或月臺Y，即處于空車狀態的搬運車在X-時，獲得到貨訂單工作（用工作1標記路線和任務種類）或配送訂單工作（用工作2標記路線和工作種類）；處于空車狀態的搬運車在Y時，獲取配送訂單工作（用工作3標記路線和任務種類）或到貨訂單工作（用工作4標記路線和任務種類）。當空的搬運車在獲取任務時，此搬運車明確了工作路線，并且按順序訪問路線上的設備。月臺、發貨裝車點、集貨卸車點的設備對應的是物料搬運車，設備對物料托盤倉庫群裝盤或卸盤，從而改變搬運車的狀態為實車或者空車。為了盡可能地讓搬運車不空跑，集貨卸車點發出的工作申請優先考慮“工作1”，同理可得月臺發出的工作申請優先考慮“工作3”。對任意搬運車而言，最佳組合應為“工作1”~“工作3”或“工作3”~“工作1”，這樣能減少搬運車空車及空跑次數。

綜上所述，基于設備狀態變化的協同算法如算法1和算法2所示。涉及的符號如下：

D=D-∪D+是到貨和配送訂單工作的并集。

S是處于空車狀態的設備（物料搬運車）集。

L（i）=（l1,l2）是設備i∈M2實行下個工作的路線，l1和l2為裝和卸i的設備。

針對m∈M1∪M3，φ（m）是和m搭配的在途和排隊的空搬運車之和；ω（m）為m裝卸訂單的數量；Q（m）?C是m∈Mm的任務排序集合，根據裝卸盤的順序要求，事先已知。

圖3 “設備/物料搬運車”狀態變遷

Y和X-為月臺和集貨卸車點的地點集。

其他符號請參照本文前面的基本符號說明。

3.1 算法1 基于“設備/物料搬運車”狀態變化的協同算法

（1） 已知任務集D≠φ，令S=φ，判定階段2中的設備狀態，若i∈M2空車，則S=S∪｛｝i。

（2） 若S≠φ，獲取首元素i及其方位P（i）；反之轉（3）。

調用算法2，獲取i相應的工作j和路線

若S=φ，則轉（2），反之轉（3）。

（3）基于時間調度法運行仿真程序。

①i∈M2，更新i的狀態和地點P（i）；若i是空車，那么

②?m∈M1∪M3更新φ（m）。

③若S=φ，那么轉向（2）。

④若D=φ，那么轉向（3）， 反之轉向（4）。

（4）得出仿真數據，利用下界理論對解進行評估。

算法1中牽涉到算法2，它根據設備的平均操作進行任務分配，以并行機的效率優先，即先滿足并行機的要求，以防并行機出現長時間等待。

3.2 算法2任務分配子程序

（1） 根據P（i），明確i請求的工作類別 τ（i）。

P（i）∈X-且D+≠φ，τ（i）=工作1；P（i）∈X-、D+≠φ，D≠φ，τ（i）=工作2；P（i）∈Y且D-≠φ，τ（i）=工作3；P（i）∈Y、

（2） 基于 τ（i）確定L（i）=（l1,l2）上的設備種類。

若τ（i）=工作1或工作4，那么若 τ（i）=工作2或工作3，有且

（3） 重復以下①～④，直至確定l1和l2。

①使l為現在需確定的設備，根據l的所屬關系定義設備集M1。

②在Ml中，?m∈Ml，依據φ（m）的值對設備排序；根據ω（m）非減，對φ（m）相同的設備排序。

③若M1?GQ，把φ（m）值為偶數的設備排在φ（m）值為奇數的設備之后。

④得到M1的第一個元素k，使l=k，φ（k）（ω（k））=S*D。

（4） 基于設備l1確定任務k。

3.3 案例分析

本文利用與文獻[1]（Chen L et al,2010）一樣的下界理論對配送中心的調度問題進行評估。仿真案例與設備的運行參數選用文獻[1]的數據進行設置，如表1。

表1 案例及其仿真結果

為了確定“對于任意物料搬運車，最佳工作搭配應是①～③或③～①”的假想，本文分別對邊裝邊卸和先卸后裝進行仿真，結果如圖5所示。邊裝邊卸的Makespan值顯然更小，原因是它運用“①～③”或“③～①”的組合減少了搬運車的空車狀態，縮短了空跑時間，從而使搬運車的等待時間得到優化。此仿真證實了上述設想，保證本文算法的合理。

為了評估本文的算法1，使表1中的10個仿真案例都運行100次。算法性能評估采用下界理論，仿真結果如表1所示，算法間隙結果比較如圖4。協同算法與TA1算法相比，其gap在案例1至案例3中較好，但每秒托盤數在所有案例中全小于1s；TAl算法每秒托盤數含有非延遲多重插入特征，其每秒托盤數在例1中最短（26s），在例10最長（94s）。

在圖5中，而協同算法與TA1相比，其gap在例1至例3中相比較，結果較差，其他都優于TA1算法。原因如下：①例1至例3的工作量相對較少，仿真正在準備階段；②協同算法的核心是操作平衡，它要求一定的設備和工作來反映其性能優勢。因此，在案例問題中，協同算法可以實現比TAl算法更好的間隙性能。

4 結束語

隨著社會的不斷網絡化，物流信息化和自動化建設越來越受到重視，分揀作為物流配送的關鍵環節，在整個物流系統中不可或缺，研制符合我國訂單分揀特點又經濟實用的自動化分揀系統是物流研究人員面臨的一個重要課題。本文在進一步深入分析國內外訂單分揀現狀的基礎上，利用0-1混合整數規劃模型對含批處理和多訂單任務的配送中心調度問題進行建模分析，提出了面向多訂單分揀的自動化分揀作業系統模型，并在該模型基礎上運用協同優化算法在一定程度上訂單的自動分揀效率得到了提高。

圖4 算法比較

圖5 不同方式下的Makespan比較

如果自動分揀系統能夠符合訂單分揀的特點，就可以大幅地提高訂單分揀的效率，同時降低工人的勞動強度。該領域還存在許多問題需要更進一步的完善和研究，例如，分揀系統的建模仍然需要調整，協同算法需要更深入的優化等，這些都需要以后進行不斷深入的研究。