吳 聰，陳侃松，姚 靜

(湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院物聯(lián)網(wǎng)工程研究所， 武漢 430062)

0 引言

車輛的路徑問題是物流配送中的核心問題，合理地規(guī)劃物流運(yùn)輸過程中的車輛路徑能為企業(yè)降低生產(chǎn)成本，提高企業(yè)市場競爭力。帶軟時(shí)間窗的車輛路徑問題(vehicle routing problem with soft time windows，VRPSTW)，是指在滿足車輛容量不超過核載容量和規(guī)定時(shí)間范圍等約束條件的前提下，合理規(guī)劃車輛運(yùn)輸路徑，使物流配送過程中產(chǎn)生的費(fèi)用最低。

遺傳算法是一種智能進(jìn)化算法，它具有全局搜索能力強(qiáng)，算法靈活，計(jì)算速度快等優(yōu)勢[1]，被廣泛應(yīng)用于求解物流配送路徑優(yōu)化問題[2]，但其存在初始種群的隨機(jī)性強(qiáng)，個(gè)體分布比較分散，同時(shí)局部搜索能力差，搜索到全局最優(yōu)解附近時(shí)收斂速度變慢，容易出現(xiàn)未成熟收斂，陷入局部最優(yōu)[3]等缺點(diǎn)，為克服這些缺陷sriniva[4]等人提出了自適應(yīng)遺傳算法，搜索過程中交叉概率和變異概率根據(jù)進(jìn)化的情況進(jìn)行自適應(yīng)調(diào)整[5]。任子武[6]等人對傳統(tǒng)的自適應(yīng)遺傳算法進(jìn)行改進(jìn)，遺傳參數(shù)隨適應(yīng)度的大小自適應(yīng)調(diào)整，算法的收斂速度和收斂精度得到了一定的提高，但該方法對適應(yīng)值小于平均適應(yīng)值的劣質(zhì)個(gè)體的處理方式單一，算法進(jìn)化到晚期還是存在種群中個(gè)體多樣性降低，收斂速度變慢的缺點(diǎn)，針對這些問題本文提出新的改進(jìn)自適應(yīng)遺傳算法，對遺傳參數(shù)的自適應(yīng)調(diào)整方案進(jìn)行改進(jìn)，并利用該方法來求解VRPSTW問題。

1 數(shù)學(xué)模型的建立

VRPSTW問題的優(yōu)化目標(biāo)是在滿足車輛容量不超過核載容量和規(guī)定時(shí)間范圍等約束條件的前提下，優(yōu)化車輛運(yùn)輸路徑，使物流配送過程中產(chǎn)生的費(fèi)用最低，費(fèi)用函數(shù)可表示如下：

Z=P+P(t)+P(q)

(1)

其中:P為車輛配送過程中產(chǎn)生的費(fèi)用，P(t)表示配送車輛超出時(shí)間窗范圍產(chǎn)生的懲罰費(fèi)用，P(q)表示超過車輛的核載容量產(chǎn)生的懲罰費(fèi)用。車輛在運(yùn)輸過程中必須滿足以下約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

t0≥e0

(10)

(11)

其中:N為客戶編號，K為車輛數(shù)，Qk為每輛車的限制容量，e0為每輛車開始工作的時(shí)間，I0為每輛車最晚回到配送中心的時(shí)間，tij為從客戶i到客戶j的時(shí)間，si表示在客戶i的服務(wù)時(shí)間，wi表示在客戶i的等待時(shí)間。

式(2)～ 式(3)表示車輛服務(wù)的規(guī)則；式(4)～式(11)是VRPSTW的約束條件。式(4)表示K輛車生成K條配送路線，并且是從配送中心出發(fā)，最終回到配送中心，式(5)表示每輛車只給一個(gè)客戶i配送一次貨物，式(6)～(7)表示的是每輛車只能從一個(gè)邊進(jìn)一個(gè)邊出，式(8)表示每輛車每條路徑上送貨的總重量不超過最大容量，式(9)表示每輛車的行駛的總時(shí)間不超過最終回配送中心的限制時(shí)間，式(10)表示車輛要在開始工作時(shí)間之后出發(fā)晚，式(11)表示每個(gè)客戶規(guī)定的服務(wù)時(shí)間窗。

為了保證遺傳操作生成的染色體是有效的，需要將相應(yīng)的約束條件設(shè)計(jì)成懲罰函數(shù)[7]，如果配送車輛超出時(shí)間窗范圍或者超過車輛的核載容量，就會(huì)進(jìn)行相應(yīng)的懲罰[8]。

1) 時(shí)間懲罰函數(shù)：

(12)

c1，c2為早到和晚到的時(shí)間懲罰系數(shù)，ei為客戶要求的最早服務(wù)時(shí)間，ti為車輛到達(dá)客戶i的時(shí)間，li為客戶i要求的最晚服務(wù)時(shí)間。

2) 容量懲罰函數(shù)：

P(q)=c0max(0,(qiyik-Q))

(13)

c0為超過核載容量的懲罰系數(shù),qi表示客戶i的貨物需求量Q表示車輛的限制容量。

由此，得到物流路徑優(yōu)化問題的目標(biāo)函數(shù)如下：

{c1max[0,(ei-ti)]+c2max[0,(ti-li)]}

(14)

其中:p0為車輛發(fā)車所需要的費(fèi)用，p為單位里程所產(chǎn)生的費(fèi)用，dij為車輛從客戶i到客戶j的路程。

配送路徑方案的優(yōu)劣是由適應(yīng)度來評價(jià)的[9]，適應(yīng)度值越大方案越優(yōu)，目標(biāo)函數(shù)值越小，這里選擇目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)，如下：

f=1/Z

(15)

2 自適應(yīng)遺傳算法的改進(jìn)

2.1 基本自適應(yīng)遺傳算法

自適應(yīng)遺傳算法在進(jìn)行搜索的過程中交叉概率和變異概率會(huì)根據(jù)進(jìn)化的情況進(jìn)行自適應(yīng)調(diào)整[10]。傳統(tǒng)的自適應(yīng)遺傳算法(AdaptiveGeneticAlgorithm，AGA)是由sriniva等人提出的。其中交叉概率和變異概率的自適應(yīng)調(diào)整公式如下：

(16)

(17)

其中:fmax為所有個(gè)體適應(yīng)值中最大的適應(yīng)值，favg為所有個(gè)體的平均適應(yīng)值f為要變異個(gè)體的適應(yīng)值f’為準(zhǔn)備交叉的兩個(gè)個(gè)體中較大的適應(yīng)值，系數(shù)k1，k2，k3，k4取(0,1)區(qū)間的值。

由式中可以看出,fmax—favg越大，即種群中個(gè)體適應(yīng)度比較分散時(shí)，則pc、pm比較?。蝗绻鹒max—favg越小，即種群中的個(gè)體適應(yīng)度比較集中時(shí)，則pc、pm越大，pc和pm會(huì)根據(jù)個(gè)體的適應(yīng)度值自適應(yīng)調(diào)整。

但是AGA也存在缺點(diǎn)：一方面由于傳統(tǒng)的自適應(yīng)交叉和變異概率主要取決于取值為(0,1)的隨機(jī)系數(shù)k1，k2，k3，k4，隨機(jī)性比較大，影響了遺傳算法的種群個(gè)體質(zhì)量，可能會(huì)導(dǎo)致遺傳算法陷入局部最優(yōu)；另一方面，f’=fmax或者f=fmax時(shí)，即交叉和變異的個(gè)體適應(yīng)度達(dá)到最高適應(yīng)度時(shí)，交叉概率和變異概率為0，種群個(gè)體會(huì)處于停滯不前的狀態(tài)。

針對AGA的缺點(diǎn)，任子武等人提出了改進(jìn)自適應(yīng)遺傳算法，公式如下：

(18)

(19)

式中,fmax為所有個(gè)體適應(yīng)度值中最大的適應(yīng)值，favg為所有個(gè)體的平均適應(yīng)值，f為要變異個(gè)體的適應(yīng)值，f’為要交叉的個(gè)體中比較大的適應(yīng)度,pc1>pc2,pm1>pm2, 取(0,1)區(qū)間的值，可在優(yōu)化過程中調(diào)整。

以上改進(jìn)后pc和pm不僅可以隨適應(yīng)度的大小自適應(yīng)調(diào)整，而且，若f’=fmax，則pc=pc2，若f=fmax，則pm=pm2，不存在最大適應(yīng)度個(gè)體的pc和pm為0的情況。

但該算法還有如下缺點(diǎn)：

1) 該算法沒有對劣質(zhì)個(gè)體進(jìn)行處理，當(dāng)個(gè)體的適應(yīng)度小于平均適應(yīng)度時(shí)，pc和pm為設(shè)定的固定值。

2) 隨著算法進(jìn)化到晚期，雖然個(gè)體的適應(yīng)度都比較高，但是個(gè)體之間趨于相似，種群中個(gè)體多樣性降低，收斂速度慢，進(jìn)行交叉操作已經(jīng)沒有意義。

2.2 自適應(yīng)遺傳算法的改進(jìn)

下文針對傳統(tǒng)自適應(yīng)遺傳算法和經(jīng)典的改進(jìn)自適應(yīng)遺傳算法的缺點(diǎn)提出了新的自適應(yīng)遺傳算法(new improved adaptive genetic algorithm，NIAGA)如下：

2.2.1 選擇算子的改進(jìn)

首先，將種群中所有個(gè)體的適應(yīng)度按從大到小的順序進(jìn)行排列，新種群中有1/2的個(gè)體直接復(fù)制初始種群中適應(yīng)度最高的個(gè)體而產(chǎn)生，剩下的個(gè)體采用輪盤賭的方式進(jìn)行選擇；然后，將選擇的個(gè)體組合成新的種群，并將新種群中所有個(gè)體的適應(yīng)度按從大到小的順序排列，選擇出適應(yīng)度最高的個(gè)體保存下來；最后完成遺傳算法的所有操作，生成新的種群，如果新種群中適應(yīng)度最高的個(gè)體適應(yīng)度值比舊種群中保存的適應(yīng)度值低，那么就用舊種群中適應(yīng)度值最高的個(gè)體替代新種群中適應(yīng)度最低的個(gè)體。

按以上改進(jìn)方法進(jìn)行選擇操作，不僅在種群個(gè)體的總數(shù)目沒有改變的前提下增加了適應(yīng)高的個(gè)體比率，保持了種群中個(gè)體的多樣性；還在一定程度上解決了輪盤賭選擇法種群單一隨機(jī)化和容易陷入局部最優(yōu)的缺陷。

2.2.2 交叉算子和變異算子的改進(jìn)

由于交叉概率和變異概率是進(jìn)行交叉和變異操作的重要參數(shù)，對遺傳算法的搜索能力有很大影響，而基本遺傳算法的交叉概率和變異概率是設(shè)定的固定值，缺乏理論依據(jù)。本文提出了新的自適應(yīng)遺傳算法，它的交叉概率和變異概率會(huì)根據(jù)適應(yīng)度，進(jìn)化代數(shù)和進(jìn)化過程中最優(yōu)解沒有改變的個(gè)體數(shù)目的變化而自適應(yīng)調(diào)整。不僅可以增加算法的收斂速度，還突出個(gè)體之間的差異以增加個(gè)體之間的競爭力。

根據(jù)傳統(tǒng)和改進(jìn)自適應(yīng)遺傳算法存在的問題，本文提出了交叉概率和變異概率根據(jù)適應(yīng)度、進(jìn)化代數(shù)和進(jìn)化過程中個(gè)體未改變數(shù)目自適應(yīng)調(diào)整的改進(jìn)方法，交叉概率和變異概率變化公式如下：

(20)

(21)

進(jìn)化初期，種群中的個(gè)體之間差異比較大，fmax—favg的值也比較大，此時(shí)進(jìn)化代數(shù)t和進(jìn)化過程中個(gè)體未改變數(shù)目S比較小，所以交叉概率pc比較大，種群收斂速度較快。進(jìn)化后期，由于種群中個(gè)體之間的差異變小，個(gè)體之間相似度變高，收斂速度變慢，有陷入局部最優(yōu)的趨勢，fmax—favg的值變小，進(jìn)化代數(shù)t和進(jìn)化過程中個(gè)體未改變數(shù)目S變大，為了提高收斂效率，交叉概率pc變小，變異概率pm增加，提高了種群個(gè)體的多樣性，充分顯示了變異算子的局部搜索能力。經(jīng)過改進(jìn)的遺傳算法在進(jìn)化的過程中根據(jù)適應(yīng)度大小、進(jìn)化代數(shù)t和進(jìn)化過程中個(gè)體未改變數(shù)目S自適應(yīng)調(diào)整交叉和變異概率，不僅能保證交叉操作的全局搜索能力，并且能充分發(fā)揮變異操作的局部搜索能力。

3 改進(jìn)自適應(yīng)遺傳算法在VRPSTW中的應(yīng)用

改進(jìn)遺傳算法求解VRPSTW問題主要包括編碼，種群初始化，求解適應(yīng)度，選擇，交叉，變異，終止條件判定等步驟。

3.1 參數(shù)設(shè)定

首先對實(shí)驗(yàn)參數(shù)設(shè)定如下：

種群規(guī)模：M=50

交叉概率：pc=0.6,pc1=0.6,pc2=0.3

變異概率：pm=0.01，pm1=0.01，pm2=0.002

終止代數(shù)：T=200

每輛車最大容量：Q=6000

發(fā)車成本：p0=100

考慮到司馬相如寫關(guān)中上林苑，未必也像左思寫《三都賦》那樣“稽之地圖”“驗(yàn)之方志”，個(gè)別地方含糊帶過也許只是文人尋常虛飾，那也還并不是特別值得批駁。但我們注意到，在關(guān)于上林苑的方位、界限這些基本的宏觀地理指稱多用含混虛夸之辭。

單位運(yùn)輸成本：p=10

車輛行駛速度：v=5

超載懲罰系數(shù)：c0= [0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10]

早到懲罰系數(shù)：c1= [0 5.0 6.0 14.0 5.0 4.0 4.0 8.0 5.0 3.0 6.0 15.0 8.0 7.0 15.0 5.0 4.0 6.0]

遲到懲罰系數(shù)：c2=[0 150 300 210 160 180 320 210 2700 220 180 210 2500 310 210 100 1500 180]

3.2 遺傳操作

3.2.1 選擇

采用精英保留策略和輪盤賭方法分別選擇個(gè)體(路徑)組成新的種群，該種群一共包含50條城市路徑(即50條染色體)，首先對所有個(gè)體的適應(yīng)度按從大到小的順序進(jìn)行排列，選擇部分適應(yīng)度最高的個(gè)體(所用費(fèi)用最少的路徑)，剩下的個(gè)體通過輪盤賭選擇法選擇，然后組合成的規(guī)模為50的新種群，將這50個(gè)個(gè)體按照適應(yīng)度從大到小的順序進(jìn)行排列，將適應(yīng)度最高的個(gè)體保存，然后進(jìn)行交叉和變異操作，生成新的種群，如果新的種群中最高適應(yīng)度小于舊種群中最高適應(yīng)度，則用舊種群中適應(yīng)度最高的個(gè)體代替新種群中適應(yīng)度最低的個(gè)體。

3.2.2 交叉

本文采用兩點(diǎn)交叉的方式進(jìn)行交叉操作，首先隨機(jī)選取兩個(gè)交叉位點(diǎn)，對交叉點(diǎn)中間的基因模塊進(jìn)行交叉路徑,比如：

交叉前

父代1：1 5 6 | 4 1 3 1 2 | 8 7 9 1

父代2：1 5 4 | 1 8 6 2 1 | 3 9 7 1

交叉后

子代1： 1 5 6 | 1 8 6 2 1 | 8 7 9 1

子代2： 1 5 4 | 1 8 6 2 1 | 3 9 7 1

3.2.3 變異

本文在用遺傳算法求解VRPSTW問題的過程中，采用的是隨機(jī)選擇基因位點(diǎn)(城市編號)進(jìn)行變異操作的，首先根據(jù)變異概率選中進(jìn)行變異的個(gè)體(路徑)，然后在該個(gè)體上隨機(jī)選擇兩個(gè)基因位，最后將這兩個(gè)基因位上的基因相互交換，形成新的個(gè)體。

變異前

父代： 1 5 6 | 4 1 3 1 2 | 8 7 9 1

變異后

子代： 1 5 6 | 8 1 3 1 2 | 4 7 9 1

4 仿真實(shí)驗(yàn)及結(jié)果分析

應(yīng)用提出的算法解決如下物流路徑問題：6輛車從1個(gè)配送中心出發(fā)，為17個(gè)客戶提供配送服務(wù)。配送中心(城市編號為1)和17個(gè)客戶所在城市坐標(biāo)，每個(gè)客戶的服務(wù)時(shí)間窗和貨物需求量信息如表1所示。

根據(jù)配送過程中產(chǎn)生的費(fèi)用和車輛行駛的路徑來衡量NIAGA求解VRPSTW問題的優(yōu)化效果。對比的算法是任子武等人提出了改進(jìn)自適應(yīng)遺傳算法(improved adaptive genetic algorithm，簡稱IAGA)。設(shè)定進(jìn)化代數(shù)為500，一共進(jìn)行了5次實(shí)驗(yàn)，呈現(xiàn)的結(jié)果是求取5次實(shí)驗(yàn)結(jié)果的平均值。將IAGA和NIAGA求得的VRPSTW問題的實(shí)驗(yàn)結(jié)果進(jìn)行對比，如表2所示。

表2 IAGA和NIAGA求解VRPSTW問題實(shí)驗(yàn)結(jié)果對比

從表中可以看出，NIAGA在求解VRPSTW問題的過程中所產(chǎn)生的費(fèi)用比IAGA低很多，最短路徑也小很多，更進(jìn)一步驗(yàn)證了本文提出的改進(jìn)遺傳算法在求解VRPSTW問題中有明顯優(yōu)勢。

為了更直觀地對IAGA和NIAGA求解VRPSTW問題進(jìn)行觀察，取其中一次的IAGA和NIAGA求解VRPSTW問題的路徑仿真圖，并對其詳細(xì)參數(shù)進(jìn)行對比。如下：

圖1 IAGA在VRPTW中應(yīng)用的路徑圖

注：三角形表示的是配送中心，數(shù)字表示的是城市編號，小圓圈表示客戶所在城市。
圖2 NIAGA在VRPTW問題中應(yīng)用的路徑圖

從圖中可以看出，NIAGA的路徑圖比IAGA的路徑圖簡單一些。其具體參數(shù)如表3所示。

表3 IAGA和NIAGA求解VRPSTW問題的最優(yōu)解對比

從表中可以看出，NIAGA在求解VRPSTW問題與IAGA相比，求得的最優(yōu)成本和行駛里程都比較小。其中，NIAGA求解最優(yōu)路徑中，每輛車的行駛路徑及貨物容量如表4所示。

表4 每輛車的行駛路徑及貨物容量

每輛車的核載總?cè)萘渴? 000，由上表可以看出，本次NIAGA求解最優(yōu)路徑中，每輛車的載貨容量都沒有超過核載總?cè)萘俊?/p>

由每個(gè)城市的坐標(biāo)可以得出每兩個(gè)城市之間的距離，根據(jù)車輛的行駛速度，可以得出每輛車在每兩個(gè)城市之間的行駛時(shí)間，從而計(jì)算出車輛到達(dá)目的地的時(shí)間。與表4.1給出的時(shí)間窗進(jìn)行對比，判斷車輛是否滿足約束條件。每輛車的具體路徑長度及到達(dá)目的地的時(shí)間如表5 ～ 表10所示。

表5 車輛1的具體路徑長度及到達(dá)目的地時(shí)間

表6 車輛2的具體路徑長度及到達(dá)目的地時(shí)間

表7 車輛3的具體路徑長度及到達(dá)目的地時(shí)間

表8 車輛4的具體路徑長度及到達(dá)目的地時(shí)間

表9 車輛5的具體路徑長度及到達(dá)目的地時(shí)間

表10 車輛6的具體路徑長度及到達(dá)目的地時(shí)間

從表5 ～ 表10可以得出車輛1到達(dá)9號城市的時(shí)間是8.8548，但是9號城市的規(guī)定的服務(wù)時(shí)間窗是[7,8]；車輛6到達(dá)17號城市的時(shí)間是9.0424，而17號城市規(guī)定的服務(wù)時(shí)間窗是[7,9]。所以車輛1和車輛6到達(dá)時(shí)間都比規(guī)定時(shí)間晚，應(yīng)該受到相應(yīng)的懲罰。

從以上數(shù)據(jù)可以得出，NIAGA求解VRPSTW問題過程中，能夠求出最優(yōu)解，并且產(chǎn)生的費(fèi)用和行駛路徑距離都比IAGA小很多；同時(shí)車輛載重沒有超過車輛容量的限制，但是還是有兩輛車超過出時(shí)間窗的范圍，產(chǎn)生了相應(yīng)的懲罰費(fèi)用，不過超出時(shí)間窗的值比較小，對求解最優(yōu)解影響不是很大，可見NIAGA在求解VRPSTW問題上有很大的優(yōu)勢。

5 結(jié)語

本文提出一種改進(jìn)的自適應(yīng)遺傳算法，對遺傳參數(shù)的自適應(yīng)調(diào)整方案進(jìn)行改進(jìn)，進(jìn)化過程中交叉概率和變異概率根據(jù)適應(yīng)度、進(jìn)化代數(shù)和進(jìn)化過程中個(gè)體未改變數(shù)目個(gè)數(shù)來自適應(yīng)變化。將該算法應(yīng)用于求解帶軟時(shí)間窗的物流運(yùn)輸車輛路徑優(yōu)化問題，結(jié)果與先前的改進(jìn)自適應(yīng)遺傳算法進(jìn)行比較，分析表明該算法能有效抑制遺傳算法的“早熟”，優(yōu)化精度更高，得到的優(yōu)化結(jié)果更靠近全局最優(yōu)。

[1] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence [M]. MIT Press, 1992.

[2] Vehicle routing: problems, methods and applications[M]. Society for Industrial and Applied Mathematics, 2014.

[3] 葛繼科,邱玉輝,吳春明, 等. 遺傳算法研究綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2008, 25(10): 2911-2916.

[4] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. MIT Press, 1992.

[5] 朱鰲鑫.遺傳算法的適應(yīng)度函數(shù)研究[J]. 系統(tǒng)工程與電子技術(shù), 1998, 20(11): 58-62.

[6] 任子武,傘 冶.自適應(yīng)遺傳算法的改進(jìn)及在系統(tǒng)辨識中應(yīng)用研究[J].系統(tǒng)仿真學(xué)報(bào), 2006, 18(1): 41-43,66.

[7] 李 軍, 郭耀煌. 物流配送車輛優(yōu)化調(diào)度理論與方法[M]. 中囯物資出版社, 2001.

[8] Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations Research,1987，35(2)：254-265.

[9] Holland J L. Making vocational choices: A theory of vocational personalities and work environments [M]. Psychological Assessment Resources, 1997.