【摘要】：隨著產品生命周期的逐漸縮短,以批量為特征的市場逐漸細化,小批量、多品種、高時效的貨物需求不斷增加,這種趨勢導致配送中心的分揀作業(yè)成本逐漸增加。為有效降低分揀作業(yè)成本,適合處理多品種、小批量訂單的自動分揀系統(tǒng)逐漸代替人工揀選系統(tǒng),大大縮短了貨物揀選時間,降低了作業(yè)勞動強度,提高了貨物揀選準確率和作業(yè)效率,目前越來越多行業(yè)的配送中心開始采用自動分揀系統(tǒng),如：卷煙、醫(yī)藥等。 隨著自動分揀技術的發(fā)展,為了減少其它作業(yè)工序對分揀效率的影響,降低各作業(yè)工序之間的耦合性,出現了具有預分揀功能的復合式并行自動分揀系統(tǒng)。該系統(tǒng)利用單個分揀機不分揀的時間,提前把下個訂單的貨物預分揀完畢,當分揀到該訂單時,快速把貨物分揀到輸送系統(tǒng)上。 目前并行自動分揀系統(tǒng)同一品項分揀量拆分時廣泛采用均分法,此方法快速有效、便于實施,但同一分揀線上分揀機間會出現大量的等待時間,降低分揀作業(yè)效率；分揀調度常采用以配送線路為基本分配單位的總量均分法,增加了分揀機品項停機調換次數,大大延長了分揀作業(yè)時間。因此,研究并行自動分揀系統(tǒng)的優(yōu)化問題,對減少分揀作業(yè)總時間、節(jié)約物流成本、提高配送中心的服務效率具有重要的意義。 然而,國內外學者關于貨物分揀(揀選)領域的研究主要針對人工揀選系統(tǒng),而人工揀選系統(tǒng)的作業(yè)模式與自動分揀系統(tǒng)的作業(yè)模式差別很大。目前針對自動分揀系統(tǒng)的研究,主要集中在分揀機設備的改造、多種形式的分揀機選型及配置優(yōu)化方面,很少涉及自動分揀系統(tǒng)的分揀策略和分揀作業(yè)任務分配方法的優(yōu)化研究；針對分揀系統(tǒng)中補貨的研究主要是在其固定補貨設備下的補貨路徑優(yōu)化,很少涉及指導自動補貨系統(tǒng)相關設備設計規(guī)劃的優(yōu)化研究。 基于此,本文綜合利用迭代優(yōu)化、聚類分析等工具對訂單進行分析,針對并行自動分揀系統(tǒng)品項分揀量拆分優(yōu)化、分揀作業(yè)調度優(yōu)化、補貨緩存優(yōu)化三個重要子問題進行深入研究。本文的主要研究內容與成果如下： (1)并行自動分揀系統(tǒng)建模。 在研究并行自動分揀系統(tǒng)作業(yè)流程的基礎上,建立了并行自動分揀系統(tǒng)分揀作業(yè)總時間的數學模型。首先,利用虛擬視窗理論描述了并行自動分揀系統(tǒng)的作業(yè)流程,建立了貨物分揀作業(yè)時間模型；其次,對影響分揀作業(yè)時間的關鍵因素——分揀延遲時間進行深入分析,建立總分揀延遲時間最短的分揀量分配目標模型。 (2)并行自動分揀系統(tǒng)分揀量拆分優(yōu)化。 在品項拆分問題中,拆分的品項數量越多,分揀系統(tǒng)的作業(yè)效率越高,但是分揀機的數量會大幅度增加,進而增加了配送中心投入設備的成本。本文研究了在較少品項拆分條件下,優(yōu)化所拆分品項對應分揀機的分揀量,減少分揀作業(yè)總時間,提高分揀作業(yè)效率。首先,在分揀量拆分優(yōu)化前,通過EIQ (Entry, Item, Quantity,訂單品項數量)方法確定訂單中的拆分品項；其次,針對需要拆分的品項,依據拆分前后分揀延遲時間的改變,建立了基于延遲時間的分揀量拆分優(yōu)化模型；最后,鑒于訂單個數比較多以及拆分品項的分揀量相對比較大的特點,提出了品項拆分優(yōu)化的三個必要條件并予以證明,設計了啟發(fā)式自適應遺傳(Heuristic Adaptive Genetic Algorithm, HAGA)算法對分揀量拆分優(yōu)化模型求解,仿真實例結果表明了分揀量拆分優(yōu)化比均量拆分方法減少9%左右的分揀作業(yè)時間。 (3)并行自動分揀系統(tǒng)分揀調度優(yōu)化。 本文將分揀調度優(yōu)化問題歸結為訂單分批聚類問題,設計了復合式聚類求解算法。首先,根據分揀調度的特點,提出了按照訂單品項結構相似度并以配送線路為基本單位進行聚類的方法,其步驟為：將各品項描述為多維向量空間中的向量,空間維數等于拆分品項的個數,向量在各維的值等于各品項在配送線路訂單中的分揀量標準轉化后的數量,利用歐氏距離,建立了各個簇之間均方差最小的聚類目標模型,從而將分揀調度問題轉化為訂單分批聚類問題；然后,針對層次聚類法遍歷范圍廣和K-均值聚類法初值敏感等缺陷,提出了基于層次和劃分的復合聚類算法,其步驟為：通過簡化的層次聚類法得到初始可行解,進而利用改進的基于劃分的動態(tài)聚類算法對初始解進行優(yōu)化,較好平衡了擴展搜索空間與提高求解速度的關系；最后,用實例驗證了基于均方差最小的聚類目標模型與復合聚類算法的優(yōu)越性。 (4)自動補貨系統(tǒng)中補貨緩存長度優(yōu)化。 在自動分揀線的自動補貨系統(tǒng)中,補貨緩存過短,將影響分揀系統(tǒng)的作業(yè)效率,補貨緩存過長,則會增加設備投入成本。本文針對補貨緩存長度的優(yōu)化問題深入研究。首先,在全面分析自動分揀系統(tǒng)中的自動補貨作業(yè)基礎上,建立了貨物在輸送設備上達到輸入輸出平衡的數學模型,提出了補貨緩存的長度滿足分揀作業(yè)的最優(yōu)條件及臨界條件并予以證明；然后,根據備貨系統(tǒng)與分揀系統(tǒng)之間的布局關系,建立了補貨緩存中貨物到達過程的數學模型和補貨緩存長度優(yōu)化模型；最后,以補貨任務序列中兩品項出庫時刻的平均差值作為品項相關度值,設計了“先聚類,后排序”的啟發(fā)式聚類方法,得到備貨系統(tǒng)品項分配的優(yōu)化方案,縮短了貨物從備貨區(qū)到補貨緩存區(qū)的到達時間,從而縮短了補貨緩存長度。 為驗證所提方法及算法的有效性,本文以某物流科技有限公司為煙草行業(yè)設計的瀑布式自動分揀系統(tǒng)為研究對象,采用多個地市級卷煙物流配送中心的客戶真實訂單數據,進行實例驗證。計算結果表明,本文提出的優(yōu)化模型及求解算法很好地解決大規(guī)模訂單的自動分揀系統(tǒng)作業(yè)任務優(yōu)化及補貨緩存長度的設計優(yōu)化問題。
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2012
【分類號】：TP273;TH69

【引證文獻】

相關期刊論文 前1條

1 李曉春;鐘雪靈;王雄志;王國慶;;并行分區(qū)揀貨系統(tǒng)儲位優(yōu)化設計[J];計算機工程與應用;2013年19期

，

本文編號：2630963