基于分區(qū)揀選策略的分揀機系統(tǒng)綜合優(yōu)化研究.pdf

1、隨著我國經濟的不斷發(fā)展，配送中心的商品揀選日益呈現(xiàn)小批量、多品種、高時效的發(fā)展趨勢，對訂單處理時間提出了更高的要求。揀選系統(tǒng)是處理客戶訂單的關鍵環(huán)節(jié)，其工作效率往往成為制約配送中心吞吐能力的瓶頸。據(jù)統(tǒng)計，訂單揀選成本可占到配送中心總作業(yè)成本的60％，訂單處理總時間可占到總作業(yè)時間的40％左右。為有效降低訂單處理總時間，越來越多的行業(yè)采用自動揀選系統(tǒng)，如卷煙、藥品行業(yè)配送中心的分揀機系統(tǒng)。
　　 在各種自動揀選系統(tǒng)中，分揀機系統(tǒng)最

2、適合處理多品種、小批量的訂單貨物。在不顯著增加作業(yè)成本前提下，分揀機系統(tǒng)多采用分區(qū)揀選策略降低訂單處理總時間。該策略下分揀機系統(tǒng)劃分為若干揀貨區(qū)，各區(qū)分揀機共同揀選同一訂單貨物并送至緩沖區(qū)，然后在恰當?shù)臅r機合流貨物，完成訂單處理。因此，研究分區(qū)揀選策略下的分揀機系統(tǒng)優(yōu)化問題，對于降低訂單處理總時間，節(jié)約物流成本具有重要意義。
　　 然而，目前國內外學者關于此領域的研究存在若干問題。一是研究對象多集中在人工揀選系統(tǒng)，很少涉及到分揀

3、機系統(tǒng)，而人工揀選系統(tǒng)中訂單處理總時間構成與分揀機系統(tǒng)差別很大。二是關于分區(qū)揀選策略下的綜合優(yōu)化研究較少，多為單一影響因素優(yōu)化，如品項分配優(yōu)化。三是關于分揀機系統(tǒng)研究多集中在設備選型優(yōu)化與改造方面，較少涉及對揀選策略和方法的優(yōu)化。
　　 基于此，本文提出分區(qū)揀選策略下的分揀機系統(tǒng)綜合優(yōu)化問題。該問題以訂單處理總時間最小為優(yōu)化目標，研究內容包括該策略下影響訂單處理總時間的各主要因素：揀貨區(qū)數(shù)量、貨物合流模式、品項分配、品項拆分。相

4、比對單一因素的優(yōu)化分析，本文研究問題更為復雜。
　　 在研究該問題過程中，本文主要內容與成果如下：
　　 (1)通過設計排隊系統(tǒng)描述分揀機系統(tǒng)在分區(qū)揀選策略下的工作流程，建立了綜合優(yōu)化問題模型。
　　 設計了排隊系統(tǒng)描述分區(qū)揀選策略下分揀機系統(tǒng)工作流程，得到了訂單處理總時間的結構組成：貨物揀選時間、分揀機暫停時間、貨物合流時間；得到并分析了各主要影響因素：揀貨區(qū)數(shù)量、貨物合流模式、品項分配、品項拆分。以此建立了分

5、揀機系統(tǒng)綜合優(yōu)化問題模型，優(yōu)化目標為訂單處理總時間最小，涉及變量包括各主要影響因素，該模型屬于復雜整數(shù)規(guī)劃問題。
　　 (2)為降低模型求解難度，將優(yōu)化目標轉化為實現(xiàn)最佳訂單揀選量分配結果，并將綜合優(yōu)化問題拆分為兩大子問題，采取先獨立討論再綜合求解的思路。
　　 通過線性規(guī)劃松弛與代理松弛模型約束條件，得到訂單處理總時間下界函數(shù)和最佳訂單揀選量分配結果：各訂單揀選量均勻分配到各揀貨區(qū)。將該結果作為新的優(yōu)化目標，降低了模型

6、求解難度，擴展了求解方法。根據(jù)變量特點，將綜合優(yōu)化問題分解為品項分配與品項拆分子問題分別討論，以便最終確定綜合求解方法。
　　 此外，通過在不同合流模式下分析下界函數(shù)與揀貨區(qū)數(shù)量單調性關系，得到了更小的揀貨區(qū)數(shù)量范圍，降低了解的遍歷空間。
　　 (3)品項分配子問題中，提出了基于揀選量均分的品項聚類目標，設計了復合聚類算法求解。
　　 首先介紹了學者Jane的聚類目標，分析其缺陷后根據(jù)最佳揀選量分配結果，提出了基

7、于揀選量均分的聚類目標，并在向量空間中以曼哈頓距離描述。然后介紹了常用的層次聚類算法，分析其缺陷后提出了復合聚類算法。該算法通過改進最長處理時間優(yōu)先算法(Largest Processing Time，LPT)的靜態(tài)聚類算法得到良好初始解，再采用改進的K-means動態(tài)聚類算法優(yōu)化初始解。最后實例分析證明了基于揀選量均分的聚類目標與復合聚類算法優(yōu)越性。
　　 (4)品項拆分子問題中，通過EIQ分析方法初步拆分品項，并提出子品項揀

8、選量再分配問題，根據(jù)問題特點設計了回溯法求解。
　　 在初步拆分品項的EIQ分析中，將品項按揀選總量降序排序，并通過累加揀選量所占比例確定拆分品項。然后各選定品項都拆分為兩個子品項，將其在各訂單揀選量平均分配。
　　 為優(yōu)化初步品項拆分結果，提出子品項揀選量再分配問題。以最佳訂單揀選量分配結果為優(yōu)化目標，建立了數(shù)學模型并提出回溯法求解。根據(jù)問題特點，在組織和搜索解空間過程中兩次降低了解的搜索范圍。最后實例分析證明了回溯法

9、的有效性。
　　 (5)根據(jù)各子問題討論結果，提出分揀機系統(tǒng)綜合優(yōu)化問題的綜合求解方法。
　　 綜合求解方法結合了枚舉法與多種啟發(fā)式算法，首先初步拆分品項并確定揀貨區(qū)數(shù)量范圍，然后進行品項分配優(yōu)化與子品項揀選量再分配優(yōu)化，最后通過判斷算法結束條件迭代優(yōu)化，得到了兩種合流模式和揀貨區(qū)數(shù)量范圍內的有限組解，通過比較各解對應的訂單處理總時間確定最佳求解結果，既降低了綜合優(yōu)化問題的求解難度，又在較大空間中搜索了可行解。實例分析證