含批處理和多訂單任務(wù)的配送中心調(diào)度問題

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

（云南財經(jīng)大學(xué) 物流學(xué)院，云南 昆明 650221）

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

1 國內(nèi)外文獻綜述

1.1 訂單分批處理

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

1.2 訂單分揀

基于自動化分揀系統(tǒng)（如圖1）的自動化分揀設(shè)備通過恰當?shù)姆謷鳂I(yè)，最后可以節(jié)省相當大的人工成本，而在傳統(tǒng)的物流配送行業(yè)里，平均訂單分揀一項就占運營成本的62.5%。

圖1 訂單分揀系統(tǒng)

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

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

2 基于含批處理和多訂單任務(wù)的物流中心調(diào)度建模

2.1 問題描述

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

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

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

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

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

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

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

圖2 帶有批處理機制和多訂單任務(wù)的3階物流中心調(diào)度問題

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

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

2.2 數(shù)學(xué)模型

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

（1） 基礎(chǔ)符號

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

（2） 決策變量

若Ois在設(shè)備m進行操作，那么Xism=1，反之Xism=0；若Ois和Ojs在同一設(shè)備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的作業(yè)時間；Ris是Ois和Ojs之間的計劃時間（Ojs為Ois的緊后操作）；Tis表示Ois最初的處理時間。

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

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

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

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

公式（10） 依據(jù)xism和xjsm來定義yjsm；

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

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

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

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

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

公式（16）定義了和設(shè)備與順序有關(guān)的處理時間；

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

公式（18）定義與設(shè)備及順序有關(guān)的計劃時間；

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

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

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

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

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

3 模型求解以及案例分析

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

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

綜上所述，基于設(shè)備狀態(tài)變化的協(xié)同算法如算法1和算法2所示。涉及的符號如下：

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

S是處于空車狀態(tài)的設(shè)備（物料搬運車）集。

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

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

圖3 “設(shè)備/物料搬運車”狀態(tài)變遷

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

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

3.1 算法1 基于“設(shè)備/物料搬運車”狀態(tài)變化的協(xié)同算法

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

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

調(diào)用算法2，獲取i相應(yīng)的工作j和路線

若S=φ，則轉(zhuǎn)（2），反之轉(zhuǎn)（3）。

（3）基于時間調(diào)度法運行仿真程序。

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

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

③若S=φ，那么轉(zhuǎn)向（2）。

④若D=φ，那么轉(zhuǎn)向（3）， 反之轉(zhuǎn)向（4）。

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

算法1中牽涉到算法2，它根據(jù)設(shè)備的平均操作進行任務(wù)分配，以并行機的效率優(yōu)先，即先滿足并行機的要求，以防并行機出現(xiàn)長時間等待。

3.2 算法2任務(wù)分配子程序

（1） 根據(jù)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）上的設(shè)備種類。

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

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

①使l為現(xiàn)在需確定的設(shè)備，根據(jù)l的所屬關(guān)系定義設(shè)備集M1。

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

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

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

（4） 基于設(shè)備l1確定任務(wù)k。

3.3 案例分析

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

表1 案例及其仿真結(jié)果

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

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

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

4 結(jié)束語

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

圖4 算法比較

圖5 不同方式下的Makespan比較

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