基于聚類混合遺傳算法的LRP問題研究

柴宏建 ， 高尚策

（1.東華大學 信息科學與技術學院，上海 201620；2.數(shù)字化紡織服裝技術教育部工程研究中心 上海 201620）

物流作為“第三利潤”的源泉，近年來逐漸成為眾多企業(yè)、專家和學者的研究熱點。物流網(wǎng)絡的日趨復雜，以及交通條件的日益改善其地理分布也不斷擴大，導致物流網(wǎng)絡優(yōu)化的各個子問題（物流中心選址問題、車輛配送路徑問題等）之間的相互影響也越來越大。單純的中心選址問題在建設物流中心時只考慮運輸車輛從中心到需求點的射線型運輸方式，忽略了對車輛配送路徑進行優(yōu)化，必然導致運輸成本的增加；而車輛配送路徑問題只考慮了配送車輛在各需求點之間依次進行配送，雖然對路徑進行了優(yōu)化，提高了運輸效率，但由于缺乏對物流中心選址問題的考慮，使得整個物流 網(wǎng)絡的成本仍不能降到最低。現(xiàn)實中將中心選址問題和配送路徑優(yōu)化問題放在一起進行綜合考慮，逐漸形成了選址-配送聯(lián)合優(yōu)化問題（Location-Routing problem，LRP）。 Tai-His Wu[1]等人將LRP問題分解為LAP和VRP兩個子問題分別進行求解。Wang，Xuefeng[2]等人運用兩階段混合啟發(fā)式搜索方法對LRP進行了求解，Maria Albareda[3]等人研究了隨機 LRP問題，并建立了兩階段模型，提出了兩階段啟發(fā)式算法和下界求法。

本文將配送中心選擇與配送路徑優(yōu)化問題同時考慮，通過聚類算法[6]將需求點劃分為適當?shù)膮^(qū)域，然后針對每個區(qū)域，運用改進的混合遺傳算法對車輛巡回線路進行優(yōu)化，克服了傳統(tǒng)遺傳算法的易陷入局部收斂的缺陷，求得總體成本最小的優(yōu)化方案。

1 模型建立

1.1 LRP定義

LRP可以表述為:給定一系列候選設施及其位置，在一定時間段內每個客戶需求僅由某個確定的設施點出發(fā)的車輛來服務，在滿足一定的約束條件下，以總配送成本最低為目標函數(shù)，確定開放設施的位置及數(shù)量，并確定車輛最佳的運輸行程路線。其總費用包括設施的建設成本、運輸成本以及車輛使用成本等。

本文研究LRP模型基于的假設：客戶量、位置及需求已知；候選設施位置及容量已知；各客戶需求均能得到滿足且每個客戶只由一輛車服務；每輛車在完成全部運輸任務回到出發(fā)點，各線路的總需求小于或等于車輛的容量，車輛類型給定。

1.2 模型參數(shù)及決策變量

G={r|r=1，2，…，R}為 R 個候選設施點集合；H={i|i=R+1，R+2，…，R+N}為 N 個客戶點集合；S={G}∪{H}為所有候選設施點及客戶點集合；V={k|k=1，2，…，K}表示車輛集合；dij表示i到j的兩點間的距離；C0表示單位距離運輸成本；Ck表示車輛k的使用成本（k∈V）；Fr為設施r開放及運作的平均成本（r∈G）；Qr為設施 r的容量（r∈G）；qj為客戶 j的平均需求量（j∈H）；Qk為車輛的容量 （k∈V）；Uik表示客戶 i在路線 k 上被訪問的次序（i∈H，k∈V）。

決策變量：

1.3 LRP 模型

模型的目標函數(shù)為總成本最小 （總成本包括車輛使用成本、運輸成本及設施建設成本）。約束條件：1）式確保每個客戶僅由一車輛提供服務；2）式為車輛容量約束，確保車輛承擔的客戶總需求不超過車輛容量；3）式為設施約束；4）式為車輛路線連續(xù)性約束；5）式確保每輛車只為一個設施服務；6）表示任意兩設施相互獨立；7）式保證任意開放設施必須有車輛為其服務；9）式為支路消去約束，保證任意路線中含有一個設施；式（10）和式（11）為（0，1）變量約束。

2 算法設計

將物流配送中心及配送路徑兩方面的優(yōu)化問題結合在一起進行考慮，建立的雙層規(guī)劃模型具有NP-Hard的性質，用一般的運籌學方法無法解決。因此，在對其進行求解時，一般會分為兩個階段進行求解，先尋求優(yōu)化模型其中一個層次的最優(yōu)解，帶入模型的另一個目標函數(shù)，從而得出整個模型的最優(yōu)化方案。本文設計基于聚類算法及遺傳算法的兩階段混合式算法，并根據(jù)實際問題中的不同決策變量，對模型進行求解。

在求解的第一階段先用聚類算法對最優(yōu)選址問題進行求解，并根據(jù)第一階段求解得到的物流中心選址，在第二階段利用遺傳算法對各物流中心負責配送的需求點進行配送路徑安排，通過不斷的迭代實現(xiàn)兩階段之間的協(xié)調優(yōu)化。求解的具體算法流程如圖1所示。

圖1 雙層規(guī)劃模型求解算法設計圖Fig.1 Flowchart of algorithm design for bilevel programming model

2.1 聚類算法求解上層模型

K-means算法是硬聚類算法，是典型的基于原型的目標函數(shù)聚類方法的代表，它是數(shù)據(jù)點到原型（類別中心）的某種距離和作為優(yōu)化的目標函數(shù)，利用函數(shù)求極值的方法得到迭代運算的調整規(guī)則。K-means算法以歐式距離作為相似性測度，它是求對應某一初始聚類中心向量 V=（v1，v2，…，vk）T最優(yōu)分類，使得評價指標Jc值最小。算法常采用誤差平方和準則函數(shù)作為聚類準則函數(shù)，誤差平方和準則函數(shù)定義為：Jc=其中，Mi是類Ci中數(shù)據(jù)對象的均值，p是類Ci中的空間點。

分析誤差平方和準則函數(shù)發(fā)現(xiàn)：K-means算法是一個最優(yōu)化求解問題，目標函數(shù)存在著許多局部極小點，只有一個全局最小點。目標函數(shù)的搜索方向總是沿著誤差平方和準則函數(shù)減小的方向進行。K-means算法采用迭代更新的方法：在每一輪迭代中，依據(jù)k個聚類中心將周圍的點分別組成k個簇，而重新計算的每個簇的質心（即簇中所有點的平均值）將被作為下一輪迭代的參照點。迭代使得選取的參照點越來越接近真實的簇質心，所以目標函數(shù)越來越小，聚類效果越來越好。具體的算法流程圖如圖2所示。

圖2 聚類算法流程圖Fig.2 Flowchart of clustering algorithm

2.2 遺傳算法求解下層模型

經(jīng)典的物流配送路徑優(yōu)化問題（VRP）[5]是典型的組合優(yōu)化問題，屬于一類NP完全難問題，具有較高的計算復雜性。它只考慮了少量的約束條件，與現(xiàn)實問題比起來，還過于簡單，還不能很好的模擬實際情況.為了更貼近實際情況，車輛路徑問題（VRP）可以擴展成多中心車輛路徑問題（MDVRP）。求解配送路徑優(yōu)化問題的方法很多，常用的有動態(tài)規(guī)劃法、節(jié)約法、掃描法、分區(qū)配送算法，方案評價法等。

遺傳算法本質上是一種不依賴具體問題的直接搜索方法，具有較強的問題求解能力和較強的魯棒性，能夠解決非線性優(yōu)化問題。因此遺傳算法在物流配送領域越來越受重視。

爬山算法是一種基于鄰域搜索技術的、沿著有可能改進解的質量的方向進行的單方向搜索的搜索方法。本文嘗試將爬山算法與自適應遺傳算法相結合，能有效克服傳統(tǒng)遺傳算法易陷入局部極小的問題，收斂速度更快。

2.2.1 編碼設計

編碼是實現(xiàn)問題解空間到遺傳編碼的轉換過程。根據(jù)物流配送路徑優(yōu)化問題的特點，我們采用直接排列的編碼方法，該方法直接生產N個1~N間的互不重復的自然數(shù)的排列，即構成一個個體，按照約束條件依次將個體中的元素（客戶）歸入各配送路徑中。

2.2.2 適應度評估

本文根據(jù)上文所確定的編碼方法，適應度函數(shù)的確定要同時反映解的可行性與對應方案的費用。對于個體r，設其對應的配送路徑方案的不可行路徑數(shù)為Mr（Mr=0表示該個體對應一個可行解），目標函數(shù)值為COSTr，則該個體r的適應度函數(shù)Fr表示為：

其中，pW為每條不可行路徑的懲罰函數(shù) （該權重可以取目標函數(shù)取值范圍中的一個相對較大的正數(shù)）。

2.2.3 改進的自適應交叉和變異操作

交叉和變異概率是影響遺傳算法性能的兩個重要的參數(shù).Srinvivas[6]最早提出了一種自適應遺傳算法，在該算法中，交叉概率Pc和變異概率Pm的值能夠隨著種群中個體的適應度值的大小來進行自動改變。但是該改進GA在進化初期并不理想，容易陷入局部最優(yōu)。在Srinvivas自適應遺傳算法的基礎上我們采用一種典型方法控制兩個參數(shù):

式中，k1，k2，k3，k4是（0，1）之間的常數(shù)。 從公式（13）、（14）可知，當個體的適應度值等于最大適應度時，其交叉和變異概率為0，則算法的進化能力會受到限制，所以本文在該自適應算法的基礎上提出一種新的自適應交叉和變異概率，如公式（15）、（16）。當個體適應度值等于最大適應度值時，也可按一定的概率進行交叉和變異操作，從而提高了算法的尋優(yōu)能力，更易跳出局部最優(yōu)。

其中：f1為要交叉的兩個個體中的較大適應度值，f2是要變異個體的適應度值，favg每代群體的平均適應度，fmax為群體中的最大適應度值。Pc1為初始交叉概率，Pm1為初始變異概率。

交叉是指把兩個父代個體的部分結構加以替換重組而生成新個體的操作。具體操作為：

Step1:按照自適應交叉概率從種群中選擇兩個個體，稱為父個體 P1，P2。

Step2:其次在父代P1，P2中選取兩個非空互余子集D1，D2。

Step3:選取P1中屬于D2的基因組成新的基因片段H1，取P2中屬于D1的基因組成新的基因片段H2填入到基因片段H1相應的位置得到子代C1。

Step4:同理，選取P2中屬于D2的基因組成新的基因片段G2，取P1中屬于D1的基因組成新的基因片段G1填入到基因片段G2相應的位置，得到子代C2。

Step5:在生成的兩個子代個體C1、C2與父代個體P1、P2組成的4個個體中，比較其適應度值；當兩個子代中具有最大適應值的個體大于或等于父代中具有最大適應值的個體時，認為子代優(yōu)于父代，將子代替換父代；否則，保留父代，讓其入下一輪的進化。

利用改進的自適應交叉方法進行交叉運算，不會產生不合理的染色體表現(xiàn)型，可以提高算法的搜索能力和種群的多樣性，有效地避免了算法陷入局部最優(yōu)的情況。

交叉操作之后，我們利用自適應的變異方法處理上一步得到的種群，首先隨機選擇一個父代，然后再隨機生成兩個整數(shù)a1和 a2（a1，a2∈[1，n×m]），最后交換父代中 a1和 a2位置上的基因。

2.2.4 爬山操作

針對遺傳操作產生的每代群體的最優(yōu)個體，通過鄰域搜索實施爬山操作。本文采用基因換位算子實現(xiàn)爬山操作，具體步驟如下：

1）在個體中隨機選擇兩個基因，交換其位置；

2）判斷基因換位后的適應值變化，若適應值增加，則用新個體取代原個體；

3）重復 1）、2），直至達到一定交換次數(shù)。本文算法流程如圖3所示。

圖3 改進的算法流程圖Fig.3 Flowchart of improved algorithm

3 實驗及仿真結果

為了分析此混合遺傳算法的可行性及有效性，我們配置的仿真環(huán)境是：Windows 7操作系統(tǒng)，Intel（R）Core i5 CPU 2.40 GHz，2 GB內存，Matlab R2009b編譯軟件，采用數(shù)據(jù)隨機生成的方法，在均勻分布二維區(qū)間[0，100]2中隨機產生各需求點的坐標（xi，yi），各需求點的需求 qi在均勻分布區(qū)間[1，50]2中隨機產生，中心個數(shù)設為3。根據(jù)本文算法求得的聚類中心和最終車輛數(shù)目及優(yōu)化線路分別如圖4和圖5所示。

4 結束語

本文分析了物流選址及配送路徑模型，通過聚類分析的方法，根據(jù)成本最小化將各需求點分配到不同的區(qū)域，分別由多個配送中心服務；然后運用改進的遺傳算法很好的解決了每個區(qū)域配送中心的配送路徑優(yōu)化問題，使之更貼近實際，并編寫了相應的程序通過數(shù)值試驗驗證了此方法的有效性與優(yōu)越性。本文的MDVRP中，沒有涉及應對動態(tài)信息的處理方法，在現(xiàn)實物流配送過程中，配送車輛被派出后，客戶可能會變更訂單，或者出現(xiàn)預定路線被阻斷等突發(fā)事件，在下一步的工作中，希望能解決這些問題。

圖4 中心選址結果圖Fig.4 The figure of center location results

圖5 最終車輛路徑線路圖Fig.5 The figure of final vehicle road

[1]Tai-His Wu，Chinyao Low，Jiunn-Wei Bai.Heuristic solutions to multi-depot location-routing problems[J].Computer&Operation Research，2002（29）:1392-1417.

[2]WangXuefeng，SunXiaoming，F(xiàn)angYang.A two-phase hybrid heuristic search approach to the location-routing problem（C）.ConferenceProceedings-IEEE International Conference on Systems， Man and Cybernetics，2005:3338-3343.

[3]Albareda-Sambola M，F(xiàn)ernández E，Laporte G.Heuristic and lower bound for a stochastic location-routing problem[J].European Journal of Operational Research，2007，179 （3）:940-955.

[4]Barreto S，F(xiàn)erreira C，Paixao J，et al.Using clustering analysis in acapacitated location-routingproblem[J].European Journal of Operational Research，2007，179（3）:968-977.

[5]Chen Haijun，Chen Yieyin.Application of Hybrid Genetic Algorithm in Vehicle Routing Problem[J].Commputer&Digital Engineering，2005，33（4）:91-95.

[6]Srinivas M，Patnaik L M．Adaptive probabilities of crossover and mutation in genetic algorithms[J]．IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）:17-26.