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

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

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

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

1.1 訂單分批處理

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

1.2 訂單分揀

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

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

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

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

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

2.1 問題描述

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

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

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

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

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

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

（5） 在階段2中，任意訂單i的作業(yè)時間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的設備與之協(xié)同配合，當前設備才能釋放。

2.2 數(shù)學模型

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

（1） 基礎符號

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

（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的作業(yè)時間；Ris是Ois和Ojs之間的計劃時間（Ojs為Ois的緊后操作）；Tis表示Ois最初的處理時間。

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

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

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

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

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

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

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

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

公式（14） 定義了當Ois為Ojs的前一作業(yè)時，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階配送中心調度問題屬于大規(guī)模的組合優(yōu)化問題，在多項式時間內(nèi)不可能精準地解決此問題，所以必須對該3階配送中心的調度問題的每個子空間的每個子系統(tǒng)進行設計優(yōu)化。本文設計了一種協(xié)同優(yōu)化算法來解決基于階段2的物料搬運車狀態(tài)變化，如圖3。其得到的解的質量通過下面的仿真案例進行評估。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法2任務分配子程序

（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）上的設備種類。

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

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

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

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

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

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

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

3.3 案例分析

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

表1 案例及其仿真結果

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

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

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

4 結束語

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

圖4 算法比較

圖5 不同方式下的Makespan比較

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