有時間約束的非滿載VRP遺傳算法研究

張 亮，杜培俊，何兆芳（中國十七冶集團有限公司，安徽 馬鞍山 243000）

1 問題的描述及數學模型的建立

1.1 問題的描述

本文所要研究的是多車型、單一配送中心、多個客戶點、帶有軟時間窗的車輛路徑問題。所要達到的目標是：總成本最小，車輛數目最少。

為了方便起見，將車場編號為0，任務編號為1,2,…,L，任務及車場均以點i（i=0,1,…,L）來表示。以Qk表示車輛k的裝載能力，tij為從i到j的行駛時間，cij為從i到j的行駛所花費的費用，di為客戶i的需求量。Sik為第k輛車到達客戶i的時間，Tik為第k輛車在客戶i的卸貨時間，c為汽車的固定費用。（Ei,Li）為客戶i的時間窗口。E0為車從配送時間出發的時刻。xijk為第k輛車是否從i出發后開向j，如果是，xijk=1，否則為0。yik為客戶i的任務是否由車輛k完成，如果是，yik=1，否則為0。zik為車輛k給客戶點i的載貨量。M表示懲罰系數。

1.2 模型的建立

（1）表示目標函數，由三部分組成：汽車的固定費用、可變費用和時間延誤或者提前的懲罰；（2），（3）表示車輛從出發點出來完成任務后回到配送中心；（4）表示每個客戶至少被服務一次；（5）表示客戶需求量被滿足；（6）是車輛載重約束；（7）是時間約束；（8）是客戶車輛唯一性約束。

2 算法原理及步驟

本文應用遺傳算法來求解VRPTW問題，有如下步驟：

2.1 設計染色體結構

首先要將問題解編碼，常用的是自然數編碼。0表示配送中心，1,2,…,n表示需求點集合。

2.2 生成初始群體

Step1：隨機給需求點排序。

Step2：采用貪婪算法，從左到右計算，若第一輛車裝載容量大于前a個需求點的需求量之和，且小于前a+1個客戶需求量之和，則得到第一輛車負責送貨的需求點子串l“12…a”。

Step3：刪去排序中的前a個物資需求點，同樣方法計算確定第二輛車的負責送貨的物資需求點子串2“a+l a+2…b”。如此反復，直到所有車輛和客戶被安排完。

Step4：兩子串間插入0后把所有子串連接，再首尾加0就可以得到一條初始染色體。

Step5：重新給物資需求點隨機排序，按照相同步驟可以得到另一條染色體。反復計算操作，直到染色體條數等于群體規模n時為止。

2.3 計算適應度

根據公式：

式中，fh表示染色體h的適應度函數，Zmin表示同代群體中最佳染色體的綜合路權之和，Zh表示染色體h的綜合路權之和。

2.4 復制算子

Stepl：計算每條染色體的適應度fh，h=1,2,…,n。

Step2：按適應度大小給n條染色體排序，復制適應度最大的染色體，將其作為下一代群體中第一個染色體。

Step3：計算染色體選擇概率wh

Step4：計算染色體累計概率uk

Step5：在［0,1］區間內產生均勻分布隨機數R，若R≤u1，則復制父代群體中第一條染色體，否則復制第k條染色體，使得uk-1≤R≤uk成立（k= 2 ,…,n）如此反復操作，復制新的染色體，直到符合群體規模為止。

2.5 交叉算子

在車輛路徑問題里，采用自然數編碼，為了防止交叉過程中產生過多無效染色體，減弱對群體多樣性的要求，采用改進的部分匹配交叉（PMX）方法。任意選取兩個父代染色體，隨機選取兩個交叉點，將每一個染色體的交叉段移到對方染色體的首部，然后削去對方染色體的相同項得到子代個體。如：

交叉率pc：交叉率一般來說應該比較大，0.4～0.99；推薦使用80%～95%，選擇概率表示了被選擇的種群總體被交叉的概率。

交叉前隨機次序，再逐組交叉。

具體實施步驟過程說明如下所示:

分別將雙親1中的3,4,5,6和雙親2中的6,9,2,1為映射段，在原始后代a中，城市1,2,9重復，城市3,4和5卻丟失了。同理，在原始后代b中，城市3,4和5重復，城市1,2,9丟失。根據確定的映射關系，重復的城市3,4和5分別被城市1,2和9代替，交換的子串保持不變。

初始雙親：

映射將后代合法化：

2.6 變異算子

由禁忌搜索算法來實現，變異率本來非常小，一般為5%以下，變異率也由本來的很小變成足夠大。

對于每一個染色體，生成［0,1］區間的隨機數r，如果r≤Pm（變異率），則對染色體進行TSM變異，否則考慮下一個染色體。

2.7 終止條件

遺傳算法的終止條件有兩類常見條件：

（1）采用設定最大（遺傳）代數的方法，T：遺傳運算終止進化代數，取50～500；一般可設定為100代。

（2）根據個體的差異來判斷，通過計算種群中基因多樣性測度，即所有基因位相似程度來進行控制。具體有以下幾種方式：

①計算每代群體中染色體適應度的方差，當方差小于ε時，可認為算法收斂；

②計算每代群體適應度均值，當均值與最佳染色體適應度的比值大于λ時，可認為算法收斂；

③記錄每代最佳染色體，若某染色體連續保持最佳達到X代，可終止算法。

3 結束語

顧客對時間的需求變得越來越重要，作為物流配送方應當充分考慮時間性，將時間因素加入到問題的模型之中，運用現代啟發式算法求解，得出的結果更合理，更符合實際。本文研究出了有時間窗車輛路徑問題的模型和算法步驟，在實際應用中有關此類問題可以用上述方法來求解。

[1] 徐小勇.有時間約束的非滿載車輛調度問題的啟發式改進算法[J].商場現代化，2009(2):137-138.

[2] 楊愛梅.帶軟時間窗的車輛路徑問題研究[D].合肥：合肥工業大學（碩士論文），2009.

[3] 孟凡.有時間窗的物流配送車輛調度計劃制定以及算法研究[D].武漢：武漢理工大學（碩士論文），2010.

[4] 陳一永，許力.C-K節約算法在配載車輛調度問題中的應用研究[J].商場現代化，2009(1):149.