基于改進(jìn)自適應(yīng)遺傳算法的物流配送路徑優(yōu)化研究

吳 聰，陳侃松，姚 靜

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

0 引言

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

遺傳算法是一種智能進(jìn)化算法，它具有全局搜索能力強，算法靈活，計算速度快等優(yōu)勢[1]，被廣泛應(yīng)用于求解物流配送路徑優(yōu)化問題[2]，但其存在初始種群的隨機性強，個體分布比較分散，同時局部搜索能力差，搜索到全局最優(yōu)解附近時收斂速度變慢，容易出現(xiàn)未成熟收斂，陷入局部最優(yōu)[3]等缺點，為克服這些缺陷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ì)個體的處理方式單一，算法進(jìn)化到晚期還是存在種群中個體多樣性降低，收斂速度變慢的缺點，針對這些問題本文提出新的改進(jìn)自適應(yīng)遺傳算法，對遺傳參數(shù)的自適應(yīng)調(diào)整方案進(jìn)行改進(jìn)，并利用該方法來求解VRPSTW問題。

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

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

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

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

t0≥e0

(10)

(11)

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

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

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

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

(12)

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

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ā)車所需要的費用，p為單位里程所產(chǎn)生的費用，dij為車輛從客戶i到客戶j的路程。

配送路徑方案的優(yōu)劣是由適應(yīng)度來評價的[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)行搜索的過程中交叉概率和變異概率會根據(jù)進(jìn)化的情況進(jìn)行自適應(yīng)調(diào)整[10]。傳統(tǒng)的自適應(yīng)遺傳算法(AdaptiveGeneticAlgorithm，AGA)是由sriniva等人提出的。其中交叉概率和變異概率的自適應(yīng)調(diào)整公式如下：

(16)

(17)

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

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

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

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

(18)

(19)

式中,fmax為所有個體適應(yīng)度值中最大的適應(yīng)值，favg為所有個體的平均適應(yīng)值，f為要變異個體的適應(yīng)值，f’為要交叉的個體中比較大的適應(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)度個體的pc和pm為0的情況。

但該算法還有如下缺點：

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

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

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

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

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

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

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

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

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

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

(20)

(21)

進(jìn)化初期，種群中的個體之間差異比較大，fmax—favg的值也比較大，此時進(jìn)化代數(shù)t和進(jìn)化過程中個體未改變數(shù)目S比較小，所以交叉概率pc比較大，種群收斂速度較快。進(jìn)化后期，由于種群中個體之間的差異變小，個體之間相似度變高，收斂速度變慢，有陷入局部最優(yōu)的趨勢，fmax—favg的值變小，進(jìn)化代數(shù)t和進(jìn)化過程中個體未改變數(shù)目S變大，為了提高收斂效率，交叉概率pc變小，變異概率pm增加，提高了種群個體的多樣性，充分顯示了變異算子的局部搜索能力。經(jīng)過改進(jìn)的遺傳算法在進(jìn)化的過程中根據(jù)適應(yīng)度大小、進(jìn)化代數(shù)t和進(jìn)化過程中個體未改變數(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ù)設(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)中上林苑，未必也像左思寫《三都賦》那樣“稽之地圖”“驗之方志”，個別地方含糊帶過也許只是文人尋常虛飾，那也還并不是特別值得批駁。但我們注意到，在關(guā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 選擇

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

3.2.2 交叉

本文采用兩點交叉的方式進(jì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ìn)行變異操作的，首先根據(jù)變異概率選中進(jìn)行變異的個體(路徑)，然后在該個體上隨機選擇兩個基因位，最后將這兩個基因位上的基因相互交換，形成新的個體。

變異前

父代： 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 仿真實驗及結(jié)果分析

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

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

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

從表中可以看出，NIAGA在求解VRPSTW問題的過程中所產(chǎn)生的費用比IAGA低很多，最短路徑也小很多，更進(jì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>

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

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

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

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

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

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

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

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

從以上數(shù)據(jù)可以得出，NIAGA求解VRPSTW問題過程中，能夠求出最優(yōu)解，并且產(chǎn)生的費用和行駛路徑距離都比IAGA小很多；同時車輛載重沒有超過車輛容量的限制，但是還是有兩輛車超過出時間窗的范圍，產(chǎn)生了相應(yīng)的懲罰費用，不過超出時間窗的值比較小，對求解最優(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)化過程中個體未改變數(shù)目個數(shù)來自適應(yīng)變化。將該算法應(yīng)用于求解帶軟時間窗的物流運輸車輛路徑優(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]. 計算機應(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é)報, 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.