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

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

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

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

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

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

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

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

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

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