摻配車間的雙中心物流路徑規(guī)劃

余晗琳 羅亞波

武漢理工大學機電工程學院，武漢，430070

0 引言

許多領域都存在路徑規(guī)劃問題[1-2]。對路徑規(guī)劃的研究歷史悠久[3-5]，如AKTER等[6]引入一個新的交叉算子來求解旅行商問題(TSP)；LIN等[7]提出一種基于單簇特征的改進蟻群算法，論述了其在解決單簇、節(jié)點規(guī)模較大的TSP上的優(yōu)勢；FALLAH等[8]研究了一個包含供應點服務不明確的單中心車輛路徑規(guī)劃模型，發(fā)現(xiàn)用粒子群算法求解該問題可得到較優(yōu)的求解時間；TAO等[9]采用新的編碼方法改進粒子群優(yōu)化算法并將其用于求解最優(yōu)路徑；鄒裕吉等[10]針對柔性作業(yè)車間AGV與設備集成調度的問題，提出一種多目標自適應聚類遺傳算法；CHEN等[11]針對多目標多路徑規(guī)劃問題，提出一種利用不同種群間存在相互抑制作用的信息素來避免“跟隨”現(xiàn)象的多蟻群優(yōu)化算法；FADDA等[12]以隨機多路徑旅行商問題為研究對象，提出一種確定性近似方法進行路徑優(yōu)化。

迄今為止的研究集中在單路徑優(yōu)化[13-14]?，F(xiàn)實的車間調度對先進算法的應用還非常少的原因在于：元啟發(fā)式算法雖然可以得到更優(yōu)的解[15-16]，但該算法并不是精確方法[17]，每一次求解不一定能得到可行解。

摻配車間的物流規(guī)劃是典型的雙路徑并行實時規(guī)劃問題。為確保調度的可靠性，摻配車間主要以雙配送中心配送負荷平衡為依據(jù)來確定物流方案，物流效率比較低。針對這一現(xiàn)實問題，本研究從經(jīng)驗出發(fā)，先采用合理的方法并依據(jù)聚集度對節(jié)點進行歸類，再采用蟻群算法求解最優(yōu)路徑；然后，針對負荷平衡，以最大化綜合滿意度為目標，采用遺傳算法對邊緣點進行重歸類，得到相應的最優(yōu)路徑，從而得到既有較優(yōu)的路徑長度、又有較高負荷平衡率的物流規(guī)劃方案。

1 摻配車間物流的特征分析

摻配車間的主要工藝是摻配，即將多種原材料混合、獲得需要的生成物。摻配車間的工藝與物流具有以下特征：

(1)摻配車間的布局往往不規(guī)則。圖1所示的摻配車間包括2個配送中心和20個摻配站，其中，六邊形表示配送中心，圓形表示摻配站。摻配站依據(jù)不同容量而占用不同的空間，其布局并不是規(guī)則的布局形式。

圖1 摻配車間布局示例

(2)同啟同停的工藝特征。摻配工藝的一個特點是摻配量并不顯著影響摻配時間，即不同容量的摻配站完成一次摻配的時間是大致相同的。因此摻配車間的物料配送采用周期性集中配送模式，即當一個階段的摻配任務完成后，由配送中心為所有摻配站配送下一個階段的物料。

(3)摻配車間一般有服務于部分摻配站的2個配送中心，它們同時工作，共同完成所有摻配站的配送任務。

(4)典型的多品種小批量生產模式。不同的物料成分摻配生成不同性質的生成物，因而摻配車間往往采用訂單式生產模式，即依據(jù)訂單編制摻配車間的生產方案，為不同的摻配站分配摻配方案，因此不同摻配站的物料需求種類及數(shù)量是動態(tài)的。

由于摻配車間工藝的特殊性，較長的配送路徑產生以下問題：①車間物流路徑配送成本增加；②雙中心配送存在從不同中心出發(fā)的配送路徑交叉問題，導致配送秩序混亂；③摻配生產有其特定的流程，任一工序拖期會導致后續(xù)工序無法正常進行；④摻配工藝存在摻配過時或不及時導致藥性失效的問題，造成材料浪費與生產停滯。

2 求解可靠性分析與經(jīng)驗策略

多配送中心的物流路徑規(guī)劃問題是包含“節(jié)點歸類”和“路徑規(guī)劃”的多路徑并行規(guī)劃問題。這兩個子問題分別屬于“資源配置類”和“路徑優(yōu)化類”的問題，且均為NP-hard問題，因此目前均沒有一種能確保其收斂的求解方法。由這兩類子問題形成的強耦合問題求解陷入局部最優(yōu)，甚至不收斂，求解的可靠性較低。

摻配車間的生產是多品種、小批量的生產模式，各摻配點的物料需求也是動態(tài)的，且需考慮2條物流路徑的負荷平衡問題，因而摻配車間的物流規(guī)劃問題成為動態(tài)節(jié)點歸類、動態(tài)負荷、動態(tài)路徑的復雜動態(tài)耦合的實時調度問題，幾乎無法找到一個必然收斂的求解方法。對摻配車間實時調度來說，一個求解優(yōu)化程度很高但收斂可靠性不高的方法沒有實用性。

由圖2所示的經(jīng)驗策略框架可以看出，雖然該策略將“節(jié)點歸類”和“路徑規(guī)劃”兩個相互耦合的子問題分解成了兩階段問題，但從經(jīng)驗出發(fā)，節(jié)點聚集度越高，往往對應的路徑越短，因而，分解成兩階段問題得到的解的優(yōu)化程度可能會下降，但大概率仍有較高的滿意度。圖2中，E為敏感度，H為平衡滿意度提升率，P為路徑滿意度下降率。

圖2 經(jīng)驗策略流程圖

3 考慮負荷平衡的鄰接三點聚類方法

3.1 基本原理

雙配送中心的運輸節(jié)點分類問題可以描述為：配送中心d1、d2向n個運輸節(jié)點配送，需要找到運輸節(jié)點集合{i|i=1，2，…，n}的2個獨立子集，在由d1和d2進行配送并滿足供需量約束的情況下，使配送總路徑長度最小，即將每個運輸節(jié)點分配到最合適的配送中心，以縮短配送路徑長度和等待時間。

雙配送中心配送的路徑長度并不完全取決于節(jié)點與配送中心之間的距離，節(jié)點集合的聚集程度也是一個重要的影響因素。分配節(jié)點后，節(jié)點聚集度越高，總路徑越短，待配送的節(jié)點較多時，分配到2個配送中心的節(jié)點子集的聚集度對全局配送路徑優(yōu)化的影響更大。

目前，面向路徑優(yōu)化的最常用節(jié)點分類方法是整數(shù)規(guī)劃方法。如圖3所示，2個實心節(jié)點離配送中心A更近，但將其與三角形節(jié)點一起歸類到配送中心B卻有更高的聚集度，總物流路徑將更短。因而，采用整數(shù)規(guī)劃方法進行歸類的優(yōu)化還有提升的空間。

圖3 聚集度與距離關系的不一致情況

本研究以整數(shù)規(guī)劃所得的解為基礎，提出一種同時考慮節(jié)點與配送中心距離和節(jié)點之間聚集度的鄰接三點聚類方法，具體步驟如下：

(1)運用整數(shù)規(guī)劃的方法對所有運輸節(jié)點進行預分類；

(2)對每個節(jié)點進行鄰接三點聚集度評價；

(3)參考節(jié)點聚集度評價結果對全局分類方案進行調整。

步驟(2)中，基于二維平面上形心到所有頂點距離的平方和最小，提出基于鄰接三點聚類分析的分類規(guī)則(圖4)：點i為進行聚集度評價的目標節(jié)點，在規(guī)定平面內離該點最近的3個節(jié)點設為j1、j2、j3，點Ci為上述4個點的形心。4個運輸節(jié)點到形心的距離之和為

(1)

式中，l(i，Ci)為待考察點i與形心點Ci的距離；l(jk，Ci)為點i的第k個鄰接點jk到形心點Ci的距離。

由圖4可見，Ai越小，節(jié)點i的聚集度越高。

(a)Ai較小 (b)Ai較大

如圖5所示，采用一個運輸節(jié)點分類的例子來描述基于鄰接三點聚類分析的分類規(guī)則：設d1、d2為配送中心，其余圓點為運輸節(jié)點。根據(jù)距離進行整數(shù)規(guī)劃預分類后，得到運輸節(jié)點集合D1={j4，j5，j6，j11，j12，j14，j15，j17，j19，j20，j23}，D2={j1，j2，j3，j7，j8，j9，j10，j13，j16，j18，j21，j22}。

圖5 一個簡單運輸節(jié)點分類問題

對于運輸節(jié)點jA，先找到平面內距離jA最近的節(jié)點j1、j2、j3，上述三點均屬于D2，則jA由d2配送可以使車輛以更短的路程完成配送，因此jA歸類于子集D2更加合理。

對于運輸節(jié)點jB，先找到距離jB最近的節(jié)點j4、j5、j7，其中，j4、j5屬于D1，j7屬于D2。本研究將鄰接三點分屬于2個配送中心的節(jié)點定義為“邊緣點”，此時，應分別求出運輸節(jié)點集合D1中距離jB最近的點j4、j5、j6，以及D2中距離jB最近的點j7、j8、j9，再進行集聚集度評價。分別求出待歸類節(jié)點jB對于子集D1和D2的聚集度A(jB，D1)與A(jB，D2)，可以發(fā)現(xiàn)A(jB，D1)>A(jB，D2)，即節(jié)點jB、j4、j5、j6的分布更集中，則jB由d1配送可使車輛以更短的路程完成配送，因此jB分屬于D1更加合理。

從分類機制和實現(xiàn)步驟可以看出，鄰接三點聚類方法具有以下優(yōu)勢：①重分類是在以整數(shù)規(guī)劃所得解的基礎上進行的，保證了分類方案更優(yōu)；②多鄰接節(jié)點之間的位置關系比節(jié)點到配送中心的距離能更客觀地評價聚集度。

3.2 考慮負荷平衡的“邊緣點”重歸類

鄰接三點聚類方法以總路徑最短為目標對配送節(jié)點進行分類，但摻配車間物流規(guī)劃需考慮路徑優(yōu)化和配送負荷平衡。路徑優(yōu)化是NP-hard問題，目前還沒有高效可靠的求解方法，因而在現(xiàn)實操作中，主要是以配送負荷平衡為依據(jù)進行物流規(guī)劃。這種方式規(guī)劃的路徑長度還能進一步優(yōu)化，但方法簡單可靠、能確保車間的正常運行。因此對配送負荷平衡的要求重于對減小物流路徑總長度的要求。

可行解范圍內，僅就配送負荷平衡的角度而言，不平衡率越低越好。滿意解范圍內，由于各摻配站對物料的需求是離散的，無法強求2個配送中心的配送負荷絕對相等，因而方案的可接受程度對不平衡率的差異敏感度顯著下降，即在滿意解的范圍內，不平衡率存在差異的方案沒有顯著的優(yōu)劣之分。

每一輪配送都有時間要求，摻配車間對配送總路徑長度也有基本限制：總路徑長度L超過路徑許可長度閾值γ(即L>γ)時，L為不可行解；設δ為解的路徑長度滿意度閾值，γ≥L>δ時，L為可行解；δ≥L時，L為滿意解。

鑒于摻配車間的以上特征，為兼顧物流路徑優(yōu)化和配送負荷平衡，本研究采用以下策略：

(1)邊緣點重歸類策略。兼顧物流路徑優(yōu)化和配送負荷平衡方法是：選擇對物流路徑長度敏感度不高、但對負荷平衡敏感度較高的點，改變其歸類結果，使其在不顯著影響物流路徑總長度的前提下，顯著提高配送負荷平衡率。

(2)基于滿意度的量綱歸一化策略。物流路徑和配送負荷具有不同的量綱，同時考慮物流路徑和配送負荷的優(yōu)化需對2個因素的評價指標進行歸一化，本研究以滿意度為指標來評價這兩個因素，實現(xiàn)歸一化。負荷平衡的滿意度為

(2)

對邊緣點重歸類后，得到相應的最優(yōu)總路徑長度L1，則重歸類后的路徑優(yōu)化程度的滿意度為

(3)

考慮負荷平衡滿意度和路徑優(yōu)化程度滿意度的綜合滿意度為

(4)

其中，ε為一極小數(shù)，以確保分母不為0。

(3)面向敏度的重歸類優(yōu)化策略。重歸類迭代過程中，P和H的變化可以反映節(jié)點重歸類對2個指標的敏感度。重歸類對于指標的敏感度定義為

(5)

其中，E為敏感度；ΔH、ΔP分別為重歸類后負荷平衡率的變化和路徑長度的變化。邊緣點重歸類的目標是尋找對物流路徑長度敏感度低、對負荷平衡敏感度高的邊緣點并對其進行重歸類，從而在不顯著影響物流路徑長度的前提下顯著提高負荷平衡率，進而得到比較滿意的解。

采用遺傳算法可以實現(xiàn)以上改進策略。鄰接三點聚類分析后，若存在c個邊緣點，則將c個邊緣點隨機重新歸類，其基于遺傳算法的實現(xiàn)方法如下：編碼0表示歸類到配送中心A，編碼1表示歸類到配送中心B，如編碼0 1 0 0 1表示編號1、3、4的邊緣點歸類到配送中心A，編號2、5的邊緣點歸類到配送中心B。每一次迭代中，可采用蟻群算法計算遺傳算法重歸類后的兩條最優(yōu)路徑長度，從而在不顯著降低路徑優(yōu)化程度的前提下，得到顯著提高負荷平衡率的方案。

4 標桿問題測試

為論述以上方法的有效性，選用通用標準算例Gaskell 67-21-5數(shù)據(jù)集進行比對實驗，分別采用整數(shù)規(guī)劃方法、鄰接三點聚類方法、考慮負荷平衡的鄰接三點聚類方法進行求解比對。標桿問題的配送中心與運輸節(jié)點信息如表1、表2所示，平面分布如圖6所示。

表1 Gaskell 67-21-5配送中心信息(部分)

表2 Gaskell 67-21-5運輸節(jié)點信息

圖6 標桿問題數(shù)據(jù)集平面分布圖

表3所示為采用整數(shù)規(guī)劃方法得到的分類結果。表4所示為采用鄰接三點聚類方法對整數(shù)規(guī)劃預分類方案調整的結果。表5所示為鄰接三點聚類方法得到的方案。

表3 整數(shù)規(guī)劃方法分類結果

表4 鄰接三點聚類方法對預分類方案的調整內容

表5 鄰接三點聚類方法所得方案

在鄰接三點聚類方法所得方案的基礎上，考慮負荷平衡，對邊緣點重歸類，得到使E最大化的調整方案：邊緣點13和邊緣點15歸于D1，邊緣點12歸于D2，其他節(jié)點歸類不變。表6所示為考慮負荷平衡的鄰接三點聚類方法所得方案。

表6 考慮負荷平衡的鄰接三點聚類方法所得方案

相比整數(shù)規(guī)劃方法，考慮負荷平衡的鄰接三點聚類方法所求得的路徑總長降低了3.40%，負荷比降低了7.14%。相比鄰接三點聚類方法，考慮負荷平衡的鄰接三點聚類方法所求得的路徑總長增加了0.11%，負荷比降低了14.05%。

考慮負荷平衡的鄰接三點聚類方法求得的相應的路徑如圖7所示。

圖7 考慮負荷平衡的鄰接三點聚類方法所得方案路徑

5 摻配車間物流規(guī)劃案例研究

某摻配車間包含2個配送中心、20個摻配站，配送中心位置為d1(20，49)，d2(51，19)，摻配站位置及某一輪配送需求量如表7所示。

表7 摻配站信息

現(xiàn)實運作中，傳統(tǒng)方法直接依據(jù)負荷平衡對節(jié)點進行歸類，然后由近及遠依次進行配送，即方案1。方案2采用鄰接三點聚類方法進行歸類，然后用蟻群算法得到最優(yōu)路徑。方案3在方案2的基礎上，面向負荷平衡對邊緣點進行重歸類，再用蟻群算法得到最優(yōu)路徑。

方案1得到的分類方案如表8所示，2個配送中心的負荷相同，但配送路徑總長高達399.47。較長的物料配送時間和摻配站等待時間降低了車間運作效率。

表8 僅考慮負荷平衡的分類方案

方案2通過整數(shù)規(guī)劃對節(jié)點進行預分類，得到表9所示的預分類結果，然后采用鄰接三點聚類方法得到表10所示的調整方案，最終得到表11所示的分類方案。采用蟻群算法得到與表11的運輸節(jié)點分類結果對應的最優(yōu)路徑，如圖8所示。

表9 整數(shù)規(guī)劃預分類結果

表10 基于鄰接三點聚類方法的調整方案

表11 鄰接三點聚類方法所得方案

圖8 鄰接三點聚類方法得到的方案路徑圖

方案3在方案2的基礎上對邊緣點進行重歸類，依據(jù)車間運作經(jīng)驗數(shù)據(jù)，令α、β、γ、δ分別為0.2、0.01、400和325，結合遺傳算法與蟻群算法得到最優(yōu)解，相應的最大敏感度Emax= 8.99。重歸類后，邊緣點2、3的歸類結果不變，邊緣點9、19由D1重歸類到D2。方案3最終結果如表12所示，對應的最優(yōu)路徑如圖9所示。

表12 考慮負荷平衡的鄰接三點聚類方法所得分類方案

圖9 考慮負荷平衡的鄰接三點聚類方法所得分類方案路徑

表13所示為以上3種方案的關鍵指標，僅就路徑長度而言，方案1的399.47顯著大于方案2的325.97、方案3的332.31。更長的路徑導致更長的配送周期，導致車間運作效率也相應降低。相較方案1，方案3的負荷平衡率減小了2.60%，路徑長度減小了16.81%，解的綜合滿意度提高80.24%。相較方案2，方案3的負荷平衡率提高了20.42%，路徑長度增大了1.94%，解的綜合滿意度提高75.70%。

表13 三種方案關鍵指標比對

6 結論

本文綜合考慮負荷平衡和路徑優(yōu)化兩方面指標，提出了一種解決運輸節(jié)點分類問題的考慮負荷平衡的鄰接三點聚類方法：

(1)可靠性優(yōu)先的節(jié)點預分類策略。先以節(jié)點聚集度為依據(jù)對節(jié)點進行預分類，再采用蟻群算法求解最優(yōu)路徑。該策略既能確保調度可靠性，又能確保解具有較高的滿意度。

(2)支持以上策略的鄰接三點聚類方法。以節(jié)點與鄰接三點的幾何關系為依據(jù)，對節(jié)點進行歸類，從而得到聚集度較高的歸類方案，將雙路徑并行規(guī)劃問題分解為兩條獨立的單路徑問題。

(3)考慮負荷平衡的邊緣點重歸類方法。尋找對物流路徑敏感度不高但對負荷平衡敏感度較高的邊緣點，對其進行重歸類，從而得到綜合滿意度最高的解。

標桿問題比對實驗和現(xiàn)實案例研究證明了以上策略與方法的可靠性、有效性與實用性。