基于改進自適應遺傳算法的物流配送路徑優化研究

吳 聰，陳侃松，姚 靜

(湖北大學 計算機與信息工程學院物聯網工程研究所， 武漢 430062)

0 引言

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

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

1 數學模型的建立

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

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

(1)

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

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

t0≥e0

(10)

(11)

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

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

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

1) 時間懲罰函數：

(12)

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

2) 容量懲罰函數：

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

(13)

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

由此，得到物流路徑優化問題的目標函數如下：

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

(14)

其中:p0為車輛發車所需要的費用，p為單位里程所產生的費用，dij為車輛從客戶i到客戶j的路程。

配送路徑方案的優劣是由適應度來評價的[9]，適應度值越大方案越優，目標函數值越小，這里選擇目標函數的倒數作為適應度函數，如下：

f=1/Z

(15)

2 自適應遺傳算法的改進

2.1 基本自適應遺傳算法

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

(16)

(17)

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

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

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

針對AGA的缺點，任子武等人提出了改進自適應遺傳算法，公式如下：

(18)

(19)

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

以上改進后pc和pm不僅可以隨適應度的大小自適應調整，而且，若f’=fmax，則pc=pc2，若f=fmax，則pm=pm2，不存在最大適應度個體的pc和pm為0的情況。

但該算法還有如下缺點：

1) 該算法沒有對劣質個體進行處理，當個體的適應度小于平均適應度時，pc和pm為設定的固定值。

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

2.2 自適應遺傳算法的改進

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

2.2.1 選擇算子的改進

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

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

2.2.2 交叉算子和變異算子的改進

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

根據傳統和改進自適應遺傳算法存在的問題，本文提出了交叉概率和變異概率根據適應度、進化代數和進化過程中個體未改變數目自適應調整的改進方法，交叉概率和變異概率變化公式如下：

(20)

(21)

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

3 改進自適應遺傳算法在VRPSTW中的應用

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

3.1 參數設定

首先對實驗參數設定如下：

種群規模：M=50

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

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

終止代數：T=200

每輛車最大容量：Q=6000

發車成本：p0=100

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

單位運輸成本：p=10

車輛行駛速度：v=5

超載懲罰系數：c0= [0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10]

早到懲罰系數：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]

遲到懲罰系數：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條染色體)，首先對所有個體的適應度按從大到小的順序進行排列，選擇部分適應度最高的個體(所用費用最少的路徑)，剩下的個體通過輪盤賭選擇法選擇，然后組合成的規模為50的新種群，將這50個個體按照適應度從大到小的順序進行排列，將適應度最高的個體保存，然后進行交叉和變異操作，生成新的種群，如果新的種群中最高適應度小于舊種群中最高適應度，則用舊種群中適應度最高的個體代替新種群中適應度最低的個體。

3.2.2 交叉

本文采用兩點交叉的方式進行交叉操作，首先隨機選取兩個交叉位點，對交叉點中間的基因模塊進行交叉路徑,比如：

交叉前

父代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問題的過程中，采用的是隨機選擇基因位點(城市編號)進行變異操作的，首先根據變異概率選中進行變異的個體(路徑)，然后在該個體上隨機選擇兩個基因位，最后將這兩個基因位上的基因相互交換，形成新的個體。

變異前

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

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

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

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

從表中可以看出，NIAGA在求解VRPSTW問題的過程中所產生的費用比IAGA低很多，最短路徑也小很多，更進一步驗證了本文提出的改進遺傳算法在求解VRPSTW問題中有明顯優勢。

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

圖1 IAGA在VRPTW中應用的路徑圖

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

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

表3 IAGA和NIAGA求解VRPSTW問題的最優解對比

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

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

每輛車的核載總容量是6 000，由上表可以看出，本次NIAGA求解最優路徑中，每輛車的載貨容量都沒有超過核載總容量。

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

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

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

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

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

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

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

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

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

5 結語

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

[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]. 計算機應用研究, 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] 朱鰲鑫.遺傳算法的適應度函數研究[J]. 系統工程與電子技術, 1998, 20(11): 58-62.

[6] 任子武,傘 冶.自適應遺傳算法的改進及在系統辨識中應用研究[J].系統仿真學報, 2006, 18(1): 41-43,66.

[7] 李 軍, 郭耀煌. 物流配送車輛優化調度理論與方法[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.