分區(qū)自動(dòng)揀選系統(tǒng)揀策略優(yōu)化研究.pdf

1、隨著客戶訂單的逐漸多樣化和客戶服務(wù)要求的逐步提高，現(xiàn)代物流配送中心對(duì)訂單處理時(shí)間提出了更高的要求。揀選作業(yè)作為訂單處理過(guò)程中的重要環(huán)節(jié)，其作業(yè)效率是衡量配送中心整體效率的關(guān)鍵。據(jù)統(tǒng)計(jì)，揀選作業(yè)時(shí)間占物流配送中心作業(yè)總時(shí)間的35％左右。為有效減少揀選作業(yè)時(shí)間，越來(lái)越多行業(yè)采用自動(dòng)揀選系統(tǒng)代替人工揀選系統(tǒng)。相對(duì)人工揀選系統(tǒng)，自動(dòng)揀選系統(tǒng)作業(yè)效率高、差錯(cuò)率低，適用于小批量、多品種的貨物揀選。
　　 分揀機(jī)系統(tǒng)因其高時(shí)效、占地面積小等特

2、點(diǎn)成為應(yīng)用最廣泛的一種自動(dòng)揀選系統(tǒng)。多臺(tái)分揀機(jī)通常被劃分至多個(gè)揀選區(qū)內(nèi)，各揀選區(qū)可以同時(shí)對(duì)同一訂單并行揀選，有效減少訂單處理時(shí)間。因此，分區(qū)劃分后的自動(dòng)揀選系統(tǒng)即分區(qū)自動(dòng)揀選系統(tǒng)應(yīng)用越來(lái)越普遍，而系統(tǒng)優(yōu)化問(wèn)題，成為提高配送中心作業(yè)效率的關(guān)鍵因素。
　　 目前國(guó)內(nèi)外對(duì)于揀選系統(tǒng)的研究大多集中在人工揀選領(lǐng)域，與自動(dòng)揀選系統(tǒng)相關(guān)的文獻(xiàn)較少。為數(shù)不多的自動(dòng)揀選系統(tǒng)領(lǐng)域的文獻(xiàn)，也多集中在分揀機(jī)的改造和設(shè)備選型方面，較少涉及揀選策略優(yōu)化。基

3、于此，本文總結(jié)對(duì)分區(qū)自動(dòng)揀選系統(tǒng)作業(yè)效率影響較大的三大揀選策略：品項(xiàng)分配策略、分區(qū)合流順序分配策略和訂單揀選順序分配策略。以訂單處理總時(shí)間最小化為目標(biāo)，運(yùn)用禁忌搜索法、動(dòng)態(tài)聚類法、貪婪算法、動(dòng)態(tài)規(guī)劃法、遺傳算法等方法對(duì)以上三大揀選策略進(jìn)行優(yōu)化。本文的主要研究?jī)?nèi)容和成果如下：
　　 (1)分析分區(qū)自動(dòng)揀選系統(tǒng)工作流程，建立并行揀選、串行合流模式下揀選系統(tǒng)的數(shù)學(xué)模型。
　　 在分區(qū)自動(dòng)揀選系統(tǒng)數(shù)學(xué)模型中，將訂單處理總時(shí)間分為

4、兩部分：合流時(shí)間和延遲時(shí)間。其中，合流時(shí)間由設(shè)備性能及客戶訂單決定，在設(shè)備穩(wěn)定的情況下為常量；延遲時(shí)間由當(dāng)前訂單及前一訂單的訂單結(jié)構(gòu)決定，為變量。在分析系統(tǒng)模型的基礎(chǔ)上，總結(jié)訂單處理總時(shí)間的影響因素。
　　 (2)品項(xiàng)分配子問(wèn)題中，將優(yōu)化目標(biāo)由訂單處理總時(shí)間最小轉(zhuǎn)化為延遲因子總和最小，設(shè)計(jì)兩種算法對(duì)模型進(jìn)行求解。
　　 首先提出延遲因子表示當(dāng)前訂單某一揀選區(qū)在某一特殊情況下的延遲時(shí)間。特殊情況的表現(xiàn)為前一訂單各揀選區(qū)和當(dāng)

5、前訂單前面揀選區(qū)延遲時(shí)間均為零。通過(guò)理論證明，揀選區(qū)延遲因子與延遲時(shí)間具有相同的變化趨勢(shì)，因此可利用延遲因子對(duì)模型進(jìn)行求解，降低模型求解難度。
　　 根據(jù)各揀選區(qū)品項(xiàng)數(shù)量是否固定，分別提出基于品項(xiàng)交換的禁忌搜索算法和基于品項(xiàng)轉(zhuǎn)移的動(dòng)態(tài)聚類算法。最后通過(guò)實(shí)例仿真證明兩種算法的有效性。
　　 (3)分區(qū)合流順序優(yōu)化子問(wèn)題中，分析分區(qū)合流順序變化必要條件，并以此提出貪婪啟發(fā)式算法求解模型。
　　 首先分析分區(qū)合流順序?qū)?/p>

6、訂單處理總時(shí)間的影響，以訂單處理總時(shí)間最小為目標(biāo)，建立以分區(qū)合流順序?yàn)樽兞康南到y(tǒng)模型。將此模型抽象為一般系統(tǒng)模型1(分組)|rij=c(i-1)j+tij|Cmax，并運(yùn)用集合劃分理論證明該問(wèn)題為NP-hard問(wèn)題。
　　 提出分區(qū)合流順序變化而使訂單處理總時(shí)間減少的必要條件，并以此為基礎(chǔ)，設(shè)計(jì)貪婪啟發(fā)式算法與動(dòng)態(tài)規(guī)劃法相結(jié)合對(duì)模型進(jìn)行求解。仿真顯示算法可大幅減小系統(tǒng)訂單處理總時(shí)間，提高作業(yè)效率。
　　 (4)訂單揀選順

7、序優(yōu)化子問(wèn)題中，運(yùn)用自適應(yīng)遺傳算法進(jìn)行模型求解，并對(duì)算法進(jìn)行改進(jìn)。
　　 首先從理論、實(shí)例兩方面分析訂單揀選順序?qū)τ唵翁幚砜倳r(shí)間的影響，以訂單揀選順序?yàn)樽兞?、訂單處理總時(shí)間最小為目標(biāo)建立系統(tǒng)模型，并將模型簡(jiǎn)化為TSP問(wèn)題。提出改進(jìn)的自適應(yīng)遺傳算法對(duì)模型進(jìn)行求解。其中，算法的改進(jìn)部分體現(xiàn)在兩個(gè)方面：一、初始種群的生成過(guò)程中：引進(jìn)海明距離表示種群中兩個(gè)個(gè)體的差異，并選取海明距離較大的個(gè)體生成初始種群，以防止陷入局部最優(yōu)解。二、改進(jìn)交