棋牌平台排行榜|rmb棋牌平台

蔬果商品B2C直銷的揀貨包裝序列優化研究

  • 投稿
  • 更新時間2019-11-09
  • 閱讀量18次
  • 評分0
  • 0
  • 0

  摘要:針對蔬果類商品B2C直銷模式揀貨包裝環節存在的揀貨節拍柔性、訂單個性化強、配送時間性要求高、需滿足裝車時間窗和裝車順序等問題,引入JIT(justintime)準時制生產思想,基于流水作業和生產作業調度原理,以“準時揀貨、準時裝車”為目標,建立考慮裝車時間窗、裝車鏈順序的揀貨包裝序列優化模型。基于定性定量相結合的思想,以降低搜索空間范圍和提高算法計算速度為突破口,引入人工經驗設計了以優先規則算法生成初始種群和修訂遞推式算法求解適應度的混合遺傳算法。最后,通過應用實例分析和算法比較證明模型和算法的有效性。結果表明,本文的模型和算法比作業順序有鏈優先約束模型和不考慮人工經驗的遺傳算法,能大大降低揀貨包裝時間和提早延遲成本,為B2C直銷模式下的揀貨包裝方案生成提供了新手段。


  關鍵詞:蔬菜B2C直銷;揀貨包裝序列優化;混合遺傳算法;交貨期窗口;鏈優先約束


  作者:馮曉春,胡祥培(大連理工大學系統工程研究所,遼寧大連116023)


  0引言


  近年來,電子商務的迅猛發展已經改變了產業結構,改變了人民的生活,并對我國的經濟和社會發展產生重大影響。目前我國已經成為世界頭號電子商務大國(2013年電子商務交易突破了十萬億),1號店等大型網上超市的崛起,開辟了電子商務的新領域和新模式,也大大方便了百姓的日常生活。與此同時,蔬菜B2C網上直銷模式2010年以來相繼在北京、上海等地出現,又開啟了我國蔬果類商品B2C電子商務模式的新篇章。然而,電子商務在發展進程中創造一個個奇跡的同時,又給物流配送作業提出了前所未有的挑戰。物流配送中心的加工和配送是蔬菜B2C網上直銷模式的關鍵作業環節。為了滿足“當日訂購當日送達”或“當日訂購次日凌晨送達”的配送需求,讓客戶吃到當天采摘的新鮮蔬菜,在每天訂單截止之后,企業要在非常短暫的時間內(約6小時)通過配送中心的最小銷售單元包裝、按單揀貨包裝和裝車,將訂單配送到客戶手中。揀貨包裝作業作為最核心的環節,需在十分短暫的時間內完成大量訂單的揀貨包裝任務。然而,蔬菜較易腐爛,訂單個性化強,時間性極強的配送要求,給蔬菜的揀貨包裝和配送帶來重重困難,傳統的人工作坊揀貨包裝模式已不能滿足B2C直銷模式下的作業要求。因此,揀貨包裝作業已經成為限制蔬菜網上直銷和配送的瓶頸。解決這一難題的一種思路是:引入JIT思想,建立流水作業的揀貨包裝模式,將揀貨包裝與物流配送作業相關聯,以滿足下游裝車時間窗和裝車順序,以達到減少蔬菜訂單緩存、降低蔬菜腐爛率、提高客戶滿意度等目的,這就給制定訂單的揀貨包裝作業序列提出新挑戰。因此,如何生成揀貨包裝序列,滿足后續的裝車配送要求,是目前蔬菜配送中心急切需要解決的難題。


  關于揀貨序列優化的研究,國內外學者已有大量研究。Klaus以減少揀貨穿行時間為目標,對每一批中揀貨順序進行優化,并設計了相應的啟發式算法進行求解[1]。Liu基于聚類技術對重力流架插槽的品項成組和客戶揀貨單順序進行研究[2]。Van對圓盤傳送帶的多重揀貨順序進行了優化[3]。Zhang等以存儲和檢索變量為決策變量,以最小化完成時間為目標,對旋轉架S/R系統的揀貨順序進行了研究,并基于對系統特性的分析設計了有局部搜索策略的混合遺傳算法[4]。李曉春、鐘雪靈、王雄志、王國慶等針對配送中心動態分區揀貨系統,通過對按單揀貨順序優化及揀貨員所在分區動態分配,使分區間等待時間減少,同時提高揀貨效率[5]。李曉春等同樣對雙旋轉貨架系統提出了啟發式算法以得到最優揀貨順序,并對相關模型及算法進行模擬測試以證明其有效性[6]。李艷茹根據配送中心按單揀貨問題特點,以訂單客戶的滿意度為目標,建立數學模型,并設計了相應的遺傳算法來求解該問題[7]。綜上可知,揀貨序列與揀貨效率息息相關,滿意的揀貨序列可以減少揀貨人員的行走距離,節約揀貨時間,提高揀貨作業效率。揀貨序列優化又與揀貨模式類型密切關聯。上述的揀貨模式都是特定工業環境下的揀貨模式,并不適用于蔬菜揀貨。若將JIT的思想引入揀貨包裝作業,形成流水作業的揀貨包裝模式,其布局如圖1。由圖可知,蔬菜的揀貨和包裝在同一條流水線上,揀貨包裝同序,因而本文是對蔬菜揀貨包裝序列優化進行研究。可將每條揀貨包裝線看作平行機,將揀貨任務看作工序,考慮裝車時間窗和裝車順序的蔬菜揀貨包裝序列優化可以看作是同時有交貨期窗口和鏈優先約束的平行機調度問題。因此,本文研究的蔬果網上直銷的流水揀貨包裝作業序列問題可以歸結為有交貨期窗口和鏈優先約束的平行機生產調度問題。下面將從交貨期窗口和鏈優先約束兩個方面對平行機生產調度問題進行綜述。


  關于有鏈優先約束的生產調度問題,代表性的學術成果有:Chu研究了不僅有鏈優先約束,而且同一鏈中工序有差異時間窗的單機問題[8]。Brucker等對有鏈優先約束的相同工序的兩同質機的調度問題進行了研究。Yuan等[10]對有鏈約束的相同長度的工序在兩個機器上的調度問題提出了在線算法[9]。Agnetis等對有鏈約束的平行機問題進行了證明,對最小化總的完工時間問題和最小化延遲工序數量問題給出了有效的算法[11]。關于有交貨期窗口的生產調度問題,代表性的學術成果有:Behnamian等對有時間窗約束和序列相關的準備時間的平行機問題進行了研究,提出了三個元啟發式算法。Yin等[13]對有公共交貨期約束的單機批送貨問題進行了研究[12]。Chen對有公共時間窗的機器調度問題進行建模,并改進了分枝定界方法用于求解該問題[14]。Mosheiov等對有共同時間窗約束的機器調度問題中可用多項式求解的算例進行了研究[15]。Gerstl等對有限制的和無限制的時間窗的同質平行機調度問題的最優解的特性進行了數學證明[16]。王莉等提出了求解不同交貨期窗口的并行機調度問題的混合遺傳算法[17]。趙傳立等研究任務間具有鏈約束的平行機調度問題,對于一般情況給出了最優解的必要條件,對于特殊情況給出了問題的最優解算法[18]。上述基于時間窗約束或基于鏈優先約束的機器生產調度相關研究,國內外學者已經取得了豐碩的成果,為求解這一NP難問題進行有益探索,豐富了機器生產調度理論,對實際應用有很大的借鑒意義。但是蔬菜B2C直銷模式下的揀貨包裝作業問題由于具有訂單量大、個性化強,且需考慮下游裝車需求等特點,使得上述從數學模型及其啟發式算法方面得到的相關成果難以適用本文的揀貨包裝序列優化問題,其原因是本文的揀貨包裝序列優化問題需要同時考慮裝車時間窗和裝車順序這兩種約束條件,且揀貨包裝流水線的作業節拍是柔性的,這些特點使得蔬果的揀貨包裝序列優化更加復雜。另外,本文欲研究的問題與鏈優先約束的機器生產調度問題的區別在于,本文需滿足的裝車順序是揀貨包裝環節下游的裝車鏈優先順序,而目前學術上的鏈優先約束是當前生產加工時間需遵循某種優先約束,前者更復雜、解空間更大。因此,B2C直銷模式下的蔬果揀貨包裝序列優化問題有待進一步的研究。


  width=198.2,height=91.35


  圖1蔬菜揀貨模式布局圖


  綜上所述,本文基于前人的研究基礎,首先分析蔬果類商品揀貨作業的特點,引入JIT生產作業原理,建立滿足裝車時間窗和裝車順序的揀貨包裝序列優化模型;針對問題的復雜性,基于定性定量相結合的思想,以降低搜索空間范圍和提高算法計算速度為突破口,引入人工經驗設計混合遺傳算法對模型進行求解;通過對不同規模算例的數值實驗分析和算法比較,以證明該算法的有效性。本文的研究為解決B2C直銷模式下蔬果揀貨包裝作業問題提供了科學有效的模型和算法,并豐富了現有的機器生產調度理論,具有重要的理論意義和實際意義。


  1問題描述


  在蔬果類商品網上直銷近5年的發展進程中,實踐證明蔬菜網上直銷的物流配送成本以及顧客簽收貨品模式已經成為影響“農—宅”配送作業的兩大關鍵環節,成為影響蔬果商品B2C電子商務模式生存和發展的關鍵要素。對于蔬菜配送的顧客簽收貨品模式,當前上下班高峰時段都市交通高度擁堵的現狀以及居民一日三餐對蔬菜的需求,促使蔬菜的物流配送必須在道路較為通暢的凌晨時段實施,這就出現“為熟睡居民送菜”的擾民問題。為了解決送貨時間與顧客簽收貨品時間不匹配的難題,作者所在團隊與北京昊宇神鷹農業科技有限公司合作,通過建立社區蔬菜智能配送柜,實現了“客戶用手機上網定菜→物流配送蔬菜到小區樓下→送貨員將蔬菜放入社區蔬菜智能配送柜→向用戶手機發送短信通知開箱密碼”這一從農場到家庭的物流配送過程,消除了蔬菜公司早晨送菜到家產生的擾民煩惱,解決了蔬果類商品電子商務“最后一公里”的難題,并使我國蔬果類商品的銷售進入了移動電子商務的新時代。


  B2C直銷模式下的蔬菜配送中心作業流程如圖2所示,白天,市民在網上下單;下午5點,銷售網站將當天的訂單匯總并進行預處理,將需采摘的品種和數量信息傳送給蔬菜大棚基地;下午6點,大棚將當天所需的所有蔬菜運輸到配送中心;在配送中心,先對蔬菜進行最小銷售單元包裝(最小銷售單元通常為一斤左右),然后按照訂單進行揀貨包裝,最后是裝車配送,運輸到每個社區的智能配送柜;凌晨5點,完成所有配送任務。揀貨包裝作業一直是整個配送中心作業系統的核心。由于蔬菜易腐性,日訂單量大,訂單多品種、小批量的特點,本文引入JIT的作業思想,提出基于JIT的揀貨包裝作業模式,其物流與信息流如圖3所示。


  width=211.9,height=25.15


  圖2蔬菜配送中心作業流程


  width=180.2,height=58


  圖3基于JIT揀貨包裝作業的物流與信息流


  由圖3可知,基于JIT作業思想的揀貨包裝模式,揀貨包裝和配送之間聯系緊密,揀貨包裝序列(方案)需滿足裝車配送計劃,降低中間庫存,避免了再次按照裝車順序進行排序等環節,減少蔬菜腐敗,提高客戶滿意度。


  由于每天有上千的訂單,同時調度每一個訂單將導致編碼困難,計算時間長,甚至得不到計算結果。為了減少調度單位,降低求解復雜性,基于同一小區訂單一同裝車、一同配送這一現狀,本文將同一小區的訂單聚在一起,看作一個整體。對揀貨包裝序列優化就轉變為對配送小區之間揀貨包裝順序優化。


  由圖1可知,基于JIT作業思想的揀貨包裝流水線是柔性節拍,訂單的揀貨包裝時間由訂單所包含的最小銷售單元數量和工人的揀貨數量程度有關。因此,本文將揀貨包裝時間定義如下:


  width=68.15,height=15.8(1)


  其中,width=13,height=15.65為第v條揀貨包裝線的揀貨人員效率值,width=13.95,height=15.8為第j個小區中需揀貨包裝的最小銷售單元數量;該函數是分別關于width=13,height=15.65的減函數和width=13.95,height=15.8的增函數。


  基于JIT的蔬菜配送中心揀貨包裝作業,需要滿足裝車時間窗要求,同時希望揀貨包裝成本盡可能的少。揀貨包裝成本與所有揀貨流水線上最大揀貨包裝時間的長短呈正比關系,為了平衡任務分配,充分利用揀貨資源,本文的目標之一是最小化各揀貨線中的最大揀貨包裝時間。為了使揀貨任務盡可能地在時間窗內完成,目標之二是最小化提前和超出時間窗的時間成本,若未超出時間窗,則這部分的成本為0。因此,目標函數的第一項是最大揀貨包裝時間,第二項是訂單提早時間窗完成揀貨的成本和晚于時間窗完成揀貨的成本之和。目標函數總體是對最大揀貨包裝時間成本與提早和延遲時間窗成本總和求最小。


  width=226.4,height=118.8


  圖4B2C直銷模式下的蔬菜揀貨事例圖


  因此,本文所研究的問題可界定為:假設配送車輛數量不限,某一配送中心需要對J輛車的配送任務進行揀貨包裝裝車,每輛車都包含若干個需要配送的小區,每小區的訂單容量都小于配送車輛的容量。根據配送小區的先后順序,每輛車都遵循某一固定裝車順序。蔬菜配送中心有M(M<J)條基于電子看板的蔬菜揀貨包裝線,每條蔬菜揀貨包裝線都包含所需的所有商品種類,即任何一小區任務都可在任一揀貨包裝線上完成,且最多只能在一條揀貨包裝線上揀貨。由于雇傭的揀貨人員的文化程度和熟練程度不同,每條揀貨包裝線上的作業效率存在差異。當揀貨人員對某一小區的任務進行揀貨包裝時,是對該小區的訂單逐一進行揀貨,小區內部的訂單不存在揀貨順序。配送中心需要根據裝車計劃制定揀貨包裝序列,使得揀貨包裝同時既要滿足車輛的裝車時間窗,又要滿足裝車順序,以避免按照裝車計劃再次排序的多余作業環節。如圖4所示。


  2模型構建


  2.1基本假設


  (1)每個小區最多只能在一條揀貨包裝線上作業;


  (2)一條揀貨包裝線在一個時間內只能作業一個小區的訂單;


  (3)同一小區內的訂單不能分割在多條揀貨包裝線上;


  (4)不同小區揀貨包裝任務可在不同揀貨包裝線上進行作業;


  (5)當前小區的揀貨包裝完工時間需大于緊前小區的揀貨包裝完工時間;


  (6)一旦一個小區的揀貨包裝作業開始,就必須連續完成,不能中斷;


  (7)揀貨包裝線與揀貨包裝線之間是獨立的;


  (8)小區在不同揀貨包裝線上的揀貨包裝時間由所包含的最小銷售單元數量和該流水線的人員效率有關;


  (9)揀貨包裝流水線不會發生故障中斷且總是可用;


  (10)裝車時間忽略不計;


  (11)配送車輛的裝車時間窗和裝車順序已知。


  2.2參數及變量表示


  J:所需配送的小區集,width=51.6,height=14.05;


  Z:配送車的數量,width=51.6,height=14.05;


  M:揀貨包裝流水線集,width=56.1,height=14.05;


  width=8.1,height=13.1:小區占用每個流水線位置的最大數量width=46.75,height=13.1,保證流水線最大的利用率,使得所有揀貨包裝流水線都得到利用;


  R:位置集,width=48.85,height=14.05;


  width=16.65,height=17.05:小區j在揀貨包裝流水線v上的揀貨包裝時間;


  width=37.1,height=13.75,width=21.5,height=10.35:配送車輛width=9,height=9.8的裝車時間窗;


  width=11.1,height=17.05:小區j的緊前小區;


  width=10.15,height=13:一個常數;


  該模型的決策變量如下:


  width=18.1,height=17.05:當小區j在揀貨包裝流水線v上的r位置上生產時其值為1,否則為0;


  width=15.3,height=16:車輛i中小區j的揀貨完工時間;


  width=14.65,height=14.55:流水線v的終止揀貨包裝時間;


  width=10,height=11.8:揀貨成本的權重值;


  width=7.8,height=9.8:提早延遲成本的權重值。


  2.3數學模型構建


  該問題可以描述為如下的數學模型:


  Minwidth=276.9,height=28.9(2)


  St.width=82.5,height=29.8(3)


  width=111.65,height=28.9(4)


  width=186,height=28.9(5)


  width=179,height=30.35(6)


  width=135.4,height=26.8(7)


  width=102.05,height=16.2(8)


  width=113.35,height=14.8(9)


  width=186.4,height=16(10)


  目標函數(2)是揀貨包裝成本與提前延期成本之和最小;約束(3)保證每個小區都能分配到某個揀貨包裝流水線的某個位置上;(4)保證每個小區最多分配到某個揀貨包裝流水線的一個位置上;(5)保證只有當揀貨包裝流水線的占用位置被釋放,才能再分配小區;(6)保證某揀貨包裝流水線的加工子序列中一個小區的完工時間至少大于前一小區的完工時間;(7)保證一個小區的揀貨包裝完工時間不少于其揀貨包裝時間;(8)保證鏈優先約束;(9)定義每條揀貨包裝線上終止揀貨包裝時間等于在該流水線上任務最大揀貨包裝完工時間;(10)決策變量的取值范圍。


  當機器數大于2時,單獨考慮交貨期和鏈優先約束其中一項的機器數量兩個以上的調度問題都是NP-難問題[10][14],當同時考慮兩類約束時,其復雜性更大。通過對計算復雜性分析,本文問題的復雜性是width=28.35,height=13.1,m為揀貨包裝線條數,n為小區數。同時,本文的模型具有約束多樣性,當配送小區數很大時,解空間很大。若用精確算法在短時間內難以求出最優解。本文求解的B2C直銷模式下蔬菜配送中心揀貨包裝序列問題,從訂單截止到蔬菜采摘—揀貨包裝—配送只有短短的12小時,從訂單截止到生成揀貨包裝方案需要在1小時之內最好是在線實時生成蔬菜的揀貨包裝方案。因此,對求解上述模型的時間要求較高,若求解時間很長,無法滿足實際快速的作業計劃生成。由于啟發式算法盡可能挖掘利用了調度問題本身的啟發式信息,能夠找到次優或較好的作業排序方案,并有計算量小、計算速度快的特點,實際調度中對時間性要求強,傳統精確算法難以在有限時間求解,因此文本采用啟發式算法進行求解。在過去的幾十年里,遺傳算法在求解組合優化問題方面獲得了極大的關注和研究[19]。因此,本文以此為基礎開展算法的改進工作,提出基于優先規則的混合遺傳算法。


  3基于優先規則的混合遺傳算法


  在現實中,當某工序的交貨期很緊迫時,人們會優先安排該工序進行生產;另外,為了充分利用現有的機器資源,人們會盡可能平衡機器的使用效率,這樣可以同時減少所有工序的最大完工時間。基于這些人工經驗,本文開發了基于優先規則的啟發式算法(PRHA,PriorityRule-basedHeuristicAlgorithm),用于初始種群的生成,一方面產生更接近現實的可行解,避免盲目搜索,另一方面減少整個遺傳算法求解時間。為了快速地求解適應度,基于工人從前往后推的常規計算思維,本文設計了修訂遞推式算法(RRA,RevisedRecursiveAlgorithm)。將PRHA、RRA與遺傳算法融合,從而得到基于優先規則的混合遺傳算法。其算法流程如圖5所示。


  該混合遺傳算法的主要步驟如下:


  步驟1:編碼


  本文采用實數編碼。設有n個小區需要分配到m條揀貨包裝流水線上,染色體用一個長為n+m的實數鏈進行表示。1到n的實數代表n個工序,m個帶*的基因代表揀貨包裝流水線。因此,每條染色體可以劃分成m個子染色體,每條子染色體表示分配到一個機器上的加工工序順序。以9個小區4條揀貨包裝線為例,染色體的長度為13,設(7*3915*2862*134*4)表示一個染色體,則第7個小區被分配到第3條揀貨包裝線上,9、1、5這三個小區被分配到第2條揀貨包裝線上,且以9-1-5的順序進行揀貨包裝,以此類推。如圖6所示。


  width=170.1,height=247.95


  圖5基于優先規則混合遺傳算法流程圖


  width=198.2,height=49.1


  圖6染色體編碼事例


  步驟2:初始種群的生成


  在本混合遺傳算法中,初始種群的生成來自兩個子種群,其中一個子種群通過PRHA生成,另一個子種群是將所有的小區在滿足約束的情況下隨機地分配到揀貨包裝線上,以保持種群的多樣性。


  在現實中,當某小區的裝車時間窗很緊迫時,人們會優先安排該小區進行揀貨包裝;另外,為了充分利用現有的揀貨包裝流水線資源,人們會盡可能平衡揀貨包裝流水線之間的使用效率,這樣可以同時減少所有揀貨包裝任務的最大完工時間。基于這一現實加工中的人工經驗,本文開發了基于優先規則的啟發式算法用于初始種群的生成。PRHA在每次迭代中,在滿足優先約束的條件下選擇優先小區和優先揀貨包裝線,優先小區基于裝車的緊迫性進行選擇,同時保持已調度小區的開始時間不變,為了平衡揀貨包裝流水線的使用效率,最先完成已分配小區的流水線優先選為下次作業的揀貨包裝線。小區的揀貨包裝緊迫性與裝車時間窗的開始時間width=12,height=12.8和裝車時間窗的跨度width=34.7,height=12.8有關,且是它們的減函數。本文將工序的緊迫性定義如下:


  width=89.9,height=14.25(11)


  width=14.65,height=14.1分別是width=12,height=12.8和width=34.7,height=12.8的減函數。


  本文給出了PRHA的偽代碼如表1所示。


  表1基于優先規則的啟發式算法偽代碼


  表1(續)基于優先規則的啟發式算法偽代碼


  表2修訂遞推式算法偽代碼


  如表1所示,步驟1是初始變量,當迭代次數沒有達到小區總數時,進入步驟2;2.1是求解第u次迭代時最小的揀貨包裝流水線釋放時間和調度時間點t,2.2和2.3是求解已開始加工和完工小區集width=11,height=12.5;2.4表示選擇緊迫性最大的那個小區作為優先小區;2.5是計算優先小區的緊前小區的完工時間;2.6到2.7是根據能最早完成已分配小區的流水線作為優先流水線,2.8到3是更新相關變量值。


  該算法的目的是一方面產生更接近現實的可行解,避免盲目搜索;另一方面減少整個遺傳算法求解時間。


  步驟3:適應度求解


  該算法的偽代碼如表2所示。該算法總體思路是對每條流水線上的小區,由前一小區的完工時間,在滿足鏈優先約束的前提下,計算當前完成小區的時間,進而得出適應度ff。該算法與文獻[19]中的修訂遞歸式算法相比,避免了基因的隨機選擇。


  步驟4:選擇


  本文采用的選擇算子是“保留精英的輪盤賭策略”。輪盤賭選擇表現比較穩定,但是卻可能失去上一代最佳個體,所以本文在輪盤賭策略中引入簡單精英策略(即復制最佳個體直接進入新一代種群),用來防止通過遺傳操作而導致種群中的最優個體消失。


  步驟5:交叉


  為了防止交叉過程中對重復的基因進行修復,本文的交叉策略采用文獻[19]。其步驟如下:


  (1)從父種群的選取的兩個染色體,命名為父染色體1和父染色體2;


  (2)隨機生成一個n+m的字符串,其值為0或1;


  (3)字符串首先匹配父染色體1,保留字符串對應位置值為1的基因且位置不變,保留為選擇1;


  (4)從父染色體2中提出選擇1中基因,剩下的基因命名為選擇2;


  (5)從選擇2填補選擇1,生成新的子染色體;


  圖7為交叉事例說明。


  步驟6:變異


  本文采用的是交換變異算子,交換變異根據給定的變異概率選取染色體,隨機對染色體中的兩個基因進行交換。該變異機理是隨機選取染色體中不同子染色體的兩個基因進行交換。圖8是變異的說明事例。


  width=198.1,height=105.55


  圖7交叉算子事例


  width=198.5,height=63.2


  圖8變異算子事例


  交叉和變異會使得染色體不滿足鏈優先約束,本文采用文獻[20]的修補策略進行調整。


  步驟7:終止條件


  本文的終止條件有兩個:(1)當前的迭代次數超過事先給定的最大迭代次數;(2)在最大迭代次數范圍內,當某迭代次數的種群的最小適應度值和平均適應度值相差小于給定的可接受值時。其中,平均值的定義如下:


  width=116.8,height=22.6。


  4應用實例


  作者及其研究團隊成員2010年開始,與北京昊宇神鷹農業科技有限公司合作在北京及河北省廊坊市開展了蔬菜B2C網上直銷的示范工程建設,已取得了顯著的社會效益和經濟效益,中央電視臺進行了專題報道,開啟了我國蔬果類商品B2C電子商務模式的新篇章。該公司的蔬菜加工配送中心坐落于廊坊境內的蔬菜生產基地,毗鄰北京城郊,主要服務于北京的相關小區。公司每日下午5點截止當日訂單,由于北京早晚高峰期交通車輛行駛擁堵,車輛每日配送時間為凌晨。在每日下午5點至次日凌晨公司需完成采摘、標準銷售單元包裝、訂單分揀與裝車配送等一系列工作。為提高配送效率,先對所面對的數十個小區進行地區上的聚類,生成配送順序和裝車時間窗,基于“先上(車)后下(車)”原理,得到裝車順序。在揀貨包裝環節,揀貨包裝方案需滿足后續的配送需求。


  公司現有蔬菜種類40種,日處理訂單約4000個,其中一個訂單平均重量4公斤、包含8種蔬菜(日采摘蔬菜近16000公斤,標準銷售單元32000個)。為了貼近實際同時有利于數值實驗,本文設蔬菜種類為30種,每個訂單所包含的蔬菜種類在1-10之間生成且服從泊松分布;每種蔬菜對應的最小銷售單元份數在1-10之間,所有蔬菜對應的最小銷售單元為1斤左右,訂單的平均重量為5公斤。每一小區的訂單數在30-80之間隨機生成。配送車的容量為200個訂單。裝車時間窗的兩個時間點分別在[100-170]和[200-300]之間隨機生成。


  揀貨人員的熟練程度和認真態度決定揀貨包裝效率,揀貨人員效率越低,則揀貨包裝時間越長,每個小區包含的最小銷售單元越多,則揀貨包裝時間越長,因此,揀貨包裝時間定義如下:


  width=55.3,height=16.4(12)


  其中,width=13,height=14.55為第v條流水線的效率值(大于0),width=15.4,height=16.2為第j個小區包含的最小銷售單元數量,T為每揀選一個最小銷售單元的平均時間。根據對北京昊宇公司配送中心揀貨包裝模式的跟蹤統計,得出揀貨人員每揀一個最小銷售單元的平均時間T:width=29.05,height=11.6。由于人的揀貨效率很難實際測量,為了便于進行數值實驗,本文的效率E值是在0-1之間隨機生成,不同揀貨線的E值不同。更進一步,目標函數中設置各成本的權值均設置為1,這是因為,本文提出的基于優先規則的啟發式算法,能盡可能的利用流水線進行揀貨,對同一算例的揀貨包裝成本差異不是很大,因而揀貨包裝成本和提早延遲成本之間的沖突并不明顯。文章最后會對各成本的權重進行靈敏度分析,以驗證本文的初期分析的正確性。


  表3是本文混合遺傳算法(以下圖表中簡稱HGA)的相關參數列表。同時,算例采用的緊迫性函數如下:


  width=108.85,height=16.2(13)


  表3混合遺傳算法的相關參數


  算例分析是在Intel(R)Core(TM)DueCPU2.10GHz機器上進行,HGA和GA都是采用matlab2012b進行編寫,同時算例在windows732位操作系統下進行。


  本文欲通過數值實驗對以下問題進行探討:


  (1)揀貨包裝完成時間有鏈優先約束和揀貨包裝時間有鏈優先約束有何區別?


  (2)本文混合遺傳算法的有效性如何?


  4.1完成時間有鏈優先約束和加工時間有鏈優先約束的對比分析


  本文以J=15,M=5(J為配送小區數,M為流水線條數)為例進行詳細分析。設共需要3輛車配送,即有3條裝車順序,其相關數據如表4所示,2-4-7-10-13小區以此順序裝車,且裝車時間窗為[130-210],3-5-8-11-14小區以此順序裝車,且裝車時間窗為[150-210],以此類推。


  表4J=15、M=5事例的相關數據


  本文的模型和算法是基于揀貨包裝完工時間服從裝車順序(以下圖表中簡稱為FTCP,FinishTimebasedonChainPrecedence),而企業一般所采用的是揀貨包裝時間服從鏈優先約束(以下圖標中簡稱PTCP,Pick-packingTimebasedonChainPrecedence),不考慮裝車順序之間小區作業時間長短關系。因此,本文將對兩者進行比較分析。將算法程序運行50次,剔除異常結果,取其中總成本最低的解進行比較。表5是本文方法與加工順序服從鏈優先約束的求解比較。


  由表5可以看出,本文的方法相比PTCP,在揀貨包裝成本、提早延遲成本以及總成本上都有很大的改進。具體來說,本文得到的揀貨包裝序列,同一裝車順序上的揀貨包裝任務,緊后任務可以在緊前任務揀貨包裝同時,在其他流水線上進行作業,只需晚于緊前任務完成即可。而對于PTCP,當緊前任務還未完成時,緊后揀貨任務都不能在任何流水線上進行揀貨包裝,這就導致揀貨包裝時間極大地拉長,從而導致揀貨包裝成本和提早延遲成本增大。


  表5FTCP與PTCP的計算結果比較


  圖9和圖10分別給出了本文方法與PTCP方法結果甘特圖,縱軸表示流水線條數,橫軸表示揀貨包裝時間,矩形條表示小區任務。從圖對比可知,本文的方法得到的揀貨包裝序列比PTCP方法得到的結果,流水線作業分配能更均衡些,而PTCP得到的結果,揀貨人員有時很忙,有時空閑,即存在很大的“閑忙不均”現象;其次,PTCP會盡可能的將任務安排在揀貨包裝時間相對較小的揀貨線上,而本文的方法會權衡整個裝車順序的約束來安排揀貨順序,不一定將揀貨任務安排在對應的揀貨時間較小的揀貨線上;另外,本文方法得到的結果會盡可能安排裝車更緊迫的任務,甚至多條流水線線同時對一輛車的配送任務進行揀貨,比如一開始所有揀貨線都對鏈3的任務進行作業,而PTCP方法得到的結果在這一方面并不敏感。總之,本文的方法相比PTCP方法,能更好地均衡作業頻率,降低資源浪費,減少作業中間的空閑,避免裝車過程中產生更多的等待,導致蔬菜新鮮度降低,從而影響客戶的滿意度。


  width=141.65,height=93.55


  圖9FTCP得到的揀貨包裝序列甘特圖


  width=141.6,height=99


  圖10PTCP得到的揀貨包裝序列甘特圖


  4.2靈敏度分析


  如在引言所說,目前國內外大部分的相關文獻都是從數學分析角度,證明特殊算例的復雜性和問題性質,并提出在多項式內可解的啟發式算法。少部分做模型算法的文獻,或考慮交貨期,或考慮加工有鏈優先約束,本文是同時考慮裝車時間窗和裝車順序的揀貨包裝序列優化研究,因而與本文的研究內容不同。由于本文基于人工經驗設計了基于優先規則的啟發式算法,將本文混合遺傳算法(HGA)與常規遺傳算法(GA)進行比較,以驗證本文設計的啟發式算法的可行性以及對參數靈敏度的反應。本部分主要分析小區數變化、揀貨線條數變化、以及緊迫性變化時,本文方法與常規遺傳算法的可行性,最后也對各目標的權值變化進行靈敏度分析。


  首先是小區數量變化結果和比較分析,分為較小規模的算例和較大規模算例兩種,結果如表6所示。


  表6揀貨包裝線相同、小區數量變化所得的結果比較


  表7小區數相同、揀貨包裝線數量變化所得的結果比較


  由此看出,當小區數是9的時候,本文產生的揀貨包裝成本和提早延遲成本雖比GA較小但是相差不是很大;隨著小區數的增加,本文產生的提早延遲成本的減少幅度呈增加趨勢,但是揀貨包裝成本的減少幅度差異不大,總成本的減少幅度總體呈增加趨勢。計算時間方面,隨著問題規模的增加,計算時間減少的幅度隨著問題規模的增大呈減少趨勢。證明本文算法較常規遺傳算法相比,在小區數量較少時,效果不是很突出,但是隨著小區數量的增加,無論在提早延遲成本上,還是在計算時間上,都比常規遺傳算法有很大的提升。本文的算法在求解較大規模的揀貨包裝序列調度上相比常規算法更有優勢。


  其次是揀貨包裝線條數變化結果和比較分析,如表7所示。


  由表7可以看出,當小區數不變時,隨著揀貨包裝線條數的增加,揀貨包裝成本和提早延遲成本會相對降低,即當任務量較大時,企業可以通過增加流水線條數來降低揀貨包裝成本和提早延遲成本,但是這會額外帶來人工設備成本,所以企業需要權衡各方面利益。計算時間方面,隨著問題規模的增加,計算時間減少的幅度趨勢不是很明顯。圖11給出了HGA算法和GA求解15臺機器和48個工序的收斂性情況,從圖對比可以看出,HGA比GA能更快達到收斂,且適應度值更優。


  width=142.2,height=92.6


  圖11收斂性情況對比


  width=148.5,height=100.4


  圖12第一時間點相同、時間窗跨度規律變化情形下算例結果


  通過對上述結果總結可知,本文設計的啟發式算法,結合人工經驗,一方面能產生更接近現實的可行解,避免盲目搜索,盡快達到收斂,另一方面減少整個遺傳算法求解時間。


  再者,本文對緊迫性進行了靈敏度分析。靈敏度分析是以3條揀貨包裝線、9個配送小區為例。表8和圖12分別是裝車時間窗跨度規律變化,第一時間點相同情形下各小區的時間窗算例及其求解結果,表9和圖13分別是第一時間點不同,裝車時間窗跨度相同情形下各小區的時間窗算例及其求解結果,表10和圖14分別是裝車時間窗相同、緊迫性參數a規律變化情形下各小區的時間窗a值算例及其求解結果。從三圖可以看出,在第一時間點相同的情況下,HGA優先安排了時間窗跨度小的2號小區和4號小區,接著是7號小區,即HGA能優先安排時間窗跨度小的小區;在時間窗跨度相同的情況下,HGA優先安排了第一時間點近的2號、4號和7號小區,即HGA能優先安排第一時間點近的小區進行揀貨包裝;當時間窗相同時,HGA能優先安排a較小的小區(即較緊迫的小區),如2號、4號和7號小區。表明本文的算法能優先響應緊迫性較高的揀貨包裝需求,比如實際中的重點客戶或者需提早揀貨包裝的客戶訂單。企業可對客戶訂單的重要性程度進行分類以確定訂單的緊迫性順序,優先滿足特殊客戶的訂單揀貨包裝需求。


  表8第一時間點相同,時間窗跨度規律變化情形下算例情況


  表9時間窗跨度相同,第一時間點不同情形下算例情況


  表10時間窗相同、緊迫性參數a規律變化情形下算例情況


  width=141.65,height=96.4


  圖13時間窗跨度相同,第一時間點不同情形下算例結果


  width=141.6,height=92.45


  圖14時間窗相同、緊迫性參數a規律變化情形下算例結果


  width=170,height=97


  圖15權值比較分析


  上述的算例,都是基于揀貨包裝成本和提早延遲成本權值都為1的結果,文章最后對兩個成本之間的均衡關系進行研究。如圖15所示,橫坐標為提早延遲成本的權值變化,兩成本的權值之和為1,縱坐標為揀貨包裝成本、提早延遲成本以及總成本的相對值變化。有圖可知,將提早延遲成本的權值從0.1增至0.5,可以看到揀貨包裝成本和總成本沒有較大幅度的增加。當提早延遲成本的權值超過0.5,提早延遲成本相對略有增加且幅度不大,總成本也相對略有增加且幅度不大,但揀貨包裝成本變化不大。由此看出,揀貨包裝成本和提早延遲成本之間的沖突不大,這是因為本文提出的基于優先規則的啟發式算法在每次的計算中都盡可能充分利用揀貨流水線資源,以減少流水線空閑,從而揀貨包裝成本相對變化不大;當提早延遲成本權值超過0.5,該成本在總成本中的占有比例增大,從而導致總成本的相對增大。


  綜上數值實驗分析結果,當揀貨包裝采用流水作業模式時,首先需要考慮下游裝車的時間窗和裝車順序,滿足下游作業需求,保證揀貨包裝裝車配送作業能夠順利進行,而不至于因中間環節斷裂導致整個流水作業被停滯,同時使揀貨包裝成本盡可能的減少。揀貨包裝序列不應該局限于裝車順序,揀貨包裝完成時間只需滿足裝車順序即可,這樣可以減少作業中間的空閑時間,節約揀貨包裝時間,使揀貨包裝作業更加均衡。揀貨包裝作業中結合人工經驗,這種定性定量相結合的方式,能夠使生成的解盡可能的接近現實,降低運算時間,盡快達到收斂。考慮緊迫性,能夠及時處理揀貨包裝中的特殊客戶,響應不同類型客戶的揀貨包裝需求。


  5結論


  本文基于JIT和流水作業思想對B2C直銷模式下考慮下游裝車順序和裝車時間窗的蔬菜揀貨包裝序列優化問題進行建模,設計啟發式算法進行求解,最后通過算例驗證,將得到的算例結果與加工順序有鏈優先順序進行比較,同時將本文算法與沒有考慮優先規則的常規遺傳算法進行比較。結果表明本文模型和算法比加工順序有鏈優先順序以及沒有考慮優先規則的遺傳算法在蔬菜揀貨包裝序列的揀貨包裝成本和提早延遲成本方面都有很明顯的改善。


  本文的模型和算法為求解B2C直銷模式下蔬菜流水揀貨包裝作業難題提供了新的手段,它合理銜接了蔬菜的揀貨包裝和裝車配送作業,并大大降低了作業過程中的揀貨包裝時間和提早延遲成本,減少蔬菜的腐敗率,提高了客戶的滿意度,為企業大規模的揀貨包裝配送奠定基礎,具有重要的實際意義;此外,本文將揀貨包裝流水作業抽象為機器調度問題,針對考慮裝車時間窗和裝車順序的特點,建立了考慮揀貨包裝完工時間有鏈先后約束和裝車時間窗的揀貨包裝序列優化模型,比現有的加工順序有鏈優先約束問題,能減少揀貨包裝過程中的空閑時間,平衡作業效率;同時,本文基于定性定量相結合的思想,將人工經驗加入到遺傳算法中,設計了混合遺傳算法,該算法能在較短時間內得到優化調度方案,且對求解大規模揀貨包裝調度問題極具優勢,有助于豐富生產調度相關理論。


  未來的研究將探索:配送車輛有容量和數量限制,以及考慮配送、裝車以及揀貨包裝的聯合優化調度等問題。

上一篇: “四維一體”建設市場營銷專業
下一篇:
棋牌平台排行榜 澳洲幸运10走势图 广西快乐10分官方网 排列三走势图专业版 球探体育比分下载 好运彩3d试机号 青海十一选五开奖结果 生肖时时彩走势图 经纬彩票苹果 今晚福建31选7走势图 广东十一选五开奖记录500