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

1 問題的描述及數(shù)學(xué)模型的建立

1.1 問題的描述

本文所要研究的是多車型、單一配送中心、多個(gè)客戶點(diǎn)、帶有軟時(shí)間窗的車輛路徑問題。所要達(dá)到的目標(biāo)是：總成本最小，車輛數(shù)目最少。

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

1.2 模型的建立

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

2 算法原理及步驟

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

2.1 設(shè)計(jì)染色體結(jié)構(gòu)

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

2.2 生成初始群體

Step1：隨機(jī)給需求點(diǎn)排序。

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

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

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

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

2.3 計(jì)算適應(yīng)度

根據(jù)公式：

式中，fh表示染色體h的適應(yīng)度函數(shù)，Zmin表示同代群體中最佳染色體的綜合路權(quán)之和，Zh表示染色體h的綜合路權(quán)之和。

2.4 復(fù)制算子

Stepl：計(jì)算每條染色體的適應(yīng)度fh，h=1,2,…,n。

Step2：按適應(yīng)度大小給n條染色體排序，復(fù)制適應(yīng)度最大的染色體，將其作為下一代群體中第一個(gè)染色體。

Step3：計(jì)算染色體選擇概率wh

Step4：計(jì)算染色體累計(jì)概率uk

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

2.5 交叉算子

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

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

交叉前隨機(jī)次序，再逐組交叉。

具體實(shí)施步驟過程說明如下所示:

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

初始雙親：

映射將后代合法化：

2.6 變異算子

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

對(duì)于每一個(gè)染色體，生成［0,1］區(qū)間的隨機(jī)數(shù)r，如果r≤Pm（變異率），則對(duì)染色體進(jìn)行TSM變異，否則考慮下一個(gè)染色體。

2.7 終止條件

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

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

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

①計(jì)算每代群體中染色體適應(yīng)度的方差，當(dāng)方差小于ε時(shí)，可認(rèn)為算法收斂；

②計(jì)算每代群體適應(yīng)度均值，當(dāng)均值與最佳染色體適應(yīng)度的比值大于λ時(shí)，可認(rèn)為算法收斂；

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

3 結(jié)束語

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

[1] 徐小勇.有時(shí)間約束的非滿載車輛調(diào)度問題的啟發(fā)式改進(jìn)算法[J].商場(chǎng)現(xiàn)代化，2009(2):137-138.

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

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

[4] 陳一永，許力.C-K節(jié)約算法在配載車輛調(diào)度問題中的應(yīng)用研究[J].商場(chǎng)現(xiàn)代化，2009(1):149.