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

余晗琳 羅亞波

武漢理工大學(xué)機(jī)電工程學(xué)院，武漢，430070

0 引言

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

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

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

1 摻配車(chē)間物流的特征分析

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

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

圖1 摻配車(chē)間布局示例

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

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

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

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

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

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

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

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

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

3 考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法

3.1 基本原理

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

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

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

圖3 聚集度與距離關(guān)系的不一致情況

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

(1)運(yùn)用整數(shù)規(guī)劃的方法對(duì)所有運(yùn)輸節(jié)點(diǎn)進(jìn)行預(yù)分類(lèi)；

(2)對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行鄰接三點(diǎn)聚集度評(píng)價(jià)；

(3)參考節(jié)點(diǎn)聚集度評(píng)價(jià)結(jié)果對(duì)全局分類(lèi)方案進(jìn)行調(diào)整。

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

(1)

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

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

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

如圖5所示，采用一個(gè)運(yùn)輸節(jié)點(diǎn)分類(lèi)的例子來(lái)描述基于鄰接三點(diǎn)聚類(lèi)分析的分類(lèi)規(guī)則：設(shè)d1、d2為配送中心，其余圓點(diǎn)為運(yùn)輸節(jié)點(diǎn)。根據(jù)距離進(jìn)行整數(shù)規(guī)劃預(yù)分類(lèi)后，得到運(yùn)輸節(jié)點(diǎn)集合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 一個(gè)簡(jiǎn)單運(yùn)輸節(jié)點(diǎn)分類(lèi)問(wèn)題

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

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

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

3.2 考慮負(fù)荷平衡的“邊緣點(diǎn)”重歸類(lèi)

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

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

每一輪配送都有時(shí)間要求，摻配車(chē)間對(duì)配送總路徑長(zhǎng)度也有基本限制：總路徑長(zhǎng)度L超過(guò)路徑許可長(zhǎng)度閾值γ(即L>γ)時(shí)，L為不可行解；設(shè)δ為解的路徑長(zhǎng)度滿(mǎn)意度閾值，γ≥L>δ時(shí)，L為可行解；δ≥L時(shí)，L為滿(mǎn)意解。

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

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

(2)基于滿(mǎn)意度的量綱歸一化策略。物流路徑和配送負(fù)荷具有不同的量綱，同時(shí)考慮物流路徑和配送負(fù)荷的優(yōu)化需對(duì)2個(gè)因素的評(píng)價(jià)指標(biāo)進(jìn)行歸一化，本研究以滿(mǎn)意度為指標(biāo)來(lái)評(píng)價(jià)這兩個(gè)因素，實(shí)現(xiàn)歸一化。負(fù)荷平衡的滿(mǎn)意度為

(2)

對(duì)邊緣點(diǎn)重歸類(lèi)后，得到相應(yīng)的最優(yōu)總路徑長(zhǎng)度L1，則重歸類(lèi)后的路徑優(yōu)化程度的滿(mǎn)意度為

(3)

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

(4)

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

(3)面向敏度的重歸類(lèi)優(yōu)化策略。重歸類(lèi)迭代過(guò)程中，P和H的變化可以反映節(jié)點(diǎn)重歸類(lèi)對(duì)2個(gè)指標(biāo)的敏感度。重歸類(lèi)對(duì)于指標(biāo)的敏感度定義為

(5)

其中，E為敏感度；ΔH、ΔP分別為重歸類(lèi)后負(fù)荷平衡率的變化和路徑長(zhǎng)度的變化。邊緣點(diǎn)重歸類(lèi)的目標(biāo)是尋找對(duì)物流路徑長(zhǎng)度敏感度低、對(duì)負(fù)荷平衡敏感度高的邊緣點(diǎn)并對(duì)其進(jìn)行重歸類(lèi)，從而在不顯著影響物流路徑長(zhǎng)度的前提下顯著提高負(fù)荷平衡率，進(jìn)而得到比較滿(mǎn)意的解。

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

4 標(biāo)桿問(wèn)題測(cè)試

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

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

表2 Gaskell 67-21-5運(yùn)輸節(jié)點(diǎn)信息

圖6 標(biāo)桿問(wèn)題數(shù)據(jù)集平面分布圖

表3所示為采用整數(shù)規(guī)劃方法得到的分類(lèi)結(jié)果。表4所示為采用鄰接三點(diǎn)聚類(lèi)方法對(duì)整數(shù)規(guī)劃預(yù)分類(lèi)方案調(diào)整的結(jié)果。表5所示為鄰接三點(diǎn)聚類(lèi)方法得到的方案。

表3 整數(shù)規(guī)劃方法分類(lèi)結(jié)果

表4 鄰接三點(diǎn)聚類(lèi)方法對(duì)預(yù)分類(lèi)方案的調(diào)整內(nèi)容

表5 鄰接三點(diǎn)聚類(lèi)方法所得方案

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

表6 考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法所得方案

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

考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法求得的相應(yīng)的路徑如圖7所示。

圖7 考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法所得方案路徑

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

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

表7 摻配站信息

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

方案1得到的分類(lèi)方案如表8所示，2個(gè)配送中心的負(fù)荷相同，但配送路徑總長(zhǎng)高達(dá)399.47。較長(zhǎng)的物料配送時(shí)間和摻配站等待時(shí)間降低了車(chē)間運(yùn)作效率。

表8 僅考慮負(fù)荷平衡的分類(lèi)方案

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

表9 整數(shù)規(guī)劃預(yù)分類(lèi)結(jié)果

表10 基于鄰接三點(diǎn)聚類(lèi)方法的調(diào)整方案

表11 鄰接三點(diǎn)聚類(lèi)方法所得方案

圖8 鄰接三點(diǎn)聚類(lèi)方法得到的方案路徑圖

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

表12 考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法所得分類(lèi)方案

圖9 考慮負(fù)荷平衡的鄰接三點(diǎn)聚類(lèi)方法所得分類(lèi)方案路徑

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

表13 三種方案關(guān)鍵指標(biāo)比對(duì)

6 結(jié)論

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

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

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

(3)考慮負(fù)荷平衡的邊緣點(diǎn)重歸類(lèi)方法。尋找對(duì)物流路徑敏感度不高但對(duì)負(fù)荷平衡敏感度較高的邊緣點(diǎn)，對(duì)其進(jìn)行重歸類(lèi)，從而得到綜合滿(mǎn)意度最高的解。

標(biāo)桿問(wèn)題比對(duì)實(shí)驗(yàn)和現(xiàn)實(shí)案例研究證明了以上策略與方法的可靠性、有效性與實(shí)用性。