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

1、隨著我國(guó)經(jīng)濟(jì)的不斷發(fā)展，配送中心的商品揀選日益呈現(xiàn)小批量、多品種、高時(shí)效的發(fā)展趨勢(shì)，對(duì)訂單處理時(shí)間提出了更高的要求。揀選系統(tǒng)是處理客戶(hù)訂單的關(guān)鍵環(huán)節(jié)，其工作效率往往成為制約配送中心吞吐能力的瓶頸。據(jù)統(tǒng)計(jì)，訂單揀選成本可占到配送中心總作業(yè)成本的60％，訂單處理總時(shí)間可占到總作業(yè)時(shí)間的40％左右。為有效降低訂單處理總時(shí)間，越來(lái)越多的行業(yè)采用自動(dòng)揀選系統(tǒng)，如卷煙、藥品行業(yè)配送中心的分揀機(jī)系統(tǒng)。
　　 在各種自動(dò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)化問(wèn)題，對(duì)于降低訂單處理總時(shí)間，節(jié)約物流成本具有重要意義。
　　 然而，目前國(guó)內(nèi)外學(xué)者關(guān)于此領(lǐng)域的研究存在若干問(wèn)題。一是研究對(duì)象多集中在人工揀選系統(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)化與改造方面，較少涉及對(duì)揀選策略和方法的優(yōu)化。
　　 基于此，本文提出分區(qū)揀選策略下的分揀機(jī)系統(tǒng)綜合優(yōu)化問(wèn)題。該問(wèn)題以訂單處理總時(shí)間最小為優(yōu)化目標(biāo)，研究?jī)?nèi)容包括該策略下影響訂單處理總時(shí)間的各主要因素：揀貨區(qū)數(shù)量、貨物合流模式、品項(xiàng)分配、品項(xiàng)拆分。相

4、比對(duì)單一因素的優(yōu)化分析，本文研究問(wèn)題更為復(fù)雜。
　　 在研究該問(wèn)題過(guò)程中，本文主要內(nèi)容與成果如下：
　　 (1)通過(guò)設(shè)計(jì)排隊(duì)系統(tǒng)描述分揀機(jī)系統(tǒng)在分區(qū)揀選策略下的工作流程，建立了綜合優(yōu)化問(wèn)題模型。
　　 設(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)化問(wèn)題模型，優(yōu)化目標(biāo)為訂單處理總時(shí)間最小，涉及變量包括各主要影響因素，該模型屬于復(fù)雜整數(shù)規(guī)劃問(wèn)題。
　　 (2)為降低模型求解難度，將優(yōu)化目標(biāo)轉(zhuǎn)化為實(shí)現(xiàn)最佳訂單揀選量分配結(jié)果，并將綜合優(yōu)化問(wèn)題拆分為兩大子問(wèn)題，采取先獨(dú)立討論再綜合求解的思路。
　　 通過(guò)線性規(guī)劃松弛與代理松弛模型約束條件，得到訂單處理總時(shí)間下界函數(shù)和最佳訂單揀選量分配結(jié)果：各訂單揀選量均勻分配到各揀貨區(qū)。將該結(jié)果作為新的優(yōu)化目標(biāo)，降低了模型

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

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

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

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