基于GA-ACO的帶時間窗車輛路徑問題研究

（武漢理工大學，湖北 武漢 430063）

1 引言

在物流理論體系中，車輛路徑問題（Vehicle Routing Problem,VRP）是一類經典的組合優化問題。有能力約束的車輛路徑問題[1](Capacitated Vehicle Routing Problem，CVRP)是最基礎的VRP模型，隨著理論發展與實際環境的不斷結合，越來越多的VRP問題模型得以在此基礎上發展，而帶時間窗車輛路徑問題（Vehicle Routing Problem with Time Windows,VRPTW）[2]是其中的經典問題。更多的研究者傾向運用智能優化算法來求解VRPTW，比較普遍的智能優化算法主要包括遺傳算法[3]、蝙蝠算法[4]、蟻群算法[5]以及粒子群算法[6]等。

在解決VRPTW時，針對傳統啟發式算法在求解時容易出現無法收斂和陷入局部最優等不足，越來越多的學者通過改進優化單一啟發式算法或融合多種啟發式算法來提高算法的尋優能力。

在改進優化單一算法方面，學者們主要通過改進算法的某些規則或者引入某因子實現改進的目的。朱杰、張培斯等[7]運用改進蟻群算法來求解MVRPTW，通過改進轉移概率公式，采用鄰域搜索策略提高解的質量，借鑒模擬退火算法的思想對信息素更新，加快收斂速度。孫小軍、介科偉[8]也是運用改進蟻群算法來求解DVRPTW，通過引入交通擁堵因子，并改進揮發因子的選擇策略，以此有效地提高了蟻群算法的尋優能力。陳成[9]則是提出一種改進的遺傳算法來求解VRPTW，通過改變算法的編碼結構和交叉變異策略來提升算法的收斂效果和解的質量。Sivaramkumar V，Thansekhar M R等[10]針對帶時間窗的多目標車輛路徑問題，設計了一種聚合適應度函數的改進遺傳算法（FAGA）。針對同樣的問題，Dong、Zhou等人[11]設計了一種基于MOEA的多細胞組織算法（PDVA），在新的算法中充分利用離散螢火蟲演化機制（DGEM）和可變鄰域演化機制（VNEM）兩種機制，在加快算法求解速度的同時提高算法尋優的能力。

在融合多種啟發式算法方面，學者們主要通過算法之間的相互混合，充分發揮各算法的優點。黃震、羅中良等[12]提出一種混合蟻群優化算法用于解決VRPTW，混合算法結合了蟻群算法與遺傳算法。宋強[13]提出了一種基于局部搜索的混合遺傳算法來求解VRPTW。Keskin，M、Catay,B[14]針對帶時間窗的電動汽車車輛路徑問題（EVRPTW），設計了一種融合大領域搜索（ALNS）與精確式算法的智能算法，有效提高了算法的尋優能力。Ba?os、Julio等[15]在求解帶時間窗的多目標車輛路徑問題時，充分考慮總運輸路程，車輛運力與里程的不平衡，設計了一種基于Pareto最優的進化計算和模擬退火的混合算法。

上述學者的研究工作體現了傳統算法的可塑性，通過傳統算法間的碰撞延伸出多種效率更佳、尋優能力更強的智能算法。算法改進是算法研究過程中一個亙古不變的研究方向，為了更好地解決和改善傳統算法在求解VRPTW時收斂速度慢、解的質量不高等問題，本文借鑒上述學者的研究思想，提出一種以改進蟻群算法為主體，插入遺傳算法作為局部優化方法的混合算法，在蟻群算法轉移概率的改進中借鑒文獻[12-16]引入時間窗因素，除此之外還引入節約距離因子，設置隨機變量來優化算法的迭代過程，在信息素更新機制中，定義信息素為標量，構造信息素揮發因子的階段函數，然后使用遺傳算法中的交叉變異算子對蟻群算法得到的較優解進行下一步優化，達到加快算法收斂速度、提高解的質量的目的。算法的仿真實驗與結果對比驗證了混合算法的有效性與優越性。

2 問題描述

一般帶時間窗的車輛路徑問題可以描述如下：一個具有若干額定載重和行駛速度已知的配送車輛的配送中心，需要向區域內的多個客戶進行貨物配送，各客戶點的坐標位置、需求和可以接受服務的時間窗已知。在這樣的前提下，考慮如何合理安排車輛配送路線，既能在滿足各項約束的條件下，將貨物安全送到客戶的手中，又能實現配送車輛行駛總路徑最短。

VRPTW的時間窗可以分為硬時間窗、軟時間窗和混合時間窗三種類型，這里主要構建硬時間窗車輛路徑問題的數學模型。

為方便構建數學模型，需說明以下符號：將配送中心與客戶節點構成的有向網絡圖集合設為G(N,A) ，其中：N=N0?NC，N0表示配送中心，NC={1,2,...,n}為客戶節點的集合；A={(i,j)| i,j∈N,且i≠j}表示節點i與j的有向線段集合。dij表示節點i與節點j之間的距離，節點i可以接受服務的時間窗為[ETi,LTi]，qi表示節點i的需求量，完成節點i的服務需要的時間為STi，K={1,2,...,m} 表示車輛集合，配送車輛的額定載重量為Q，車輛k到達節點i的時刻為Tik，配送車輛從節點i到節點j所需時間為Tij，同時還需定義以下兩個0-1變量：

建立帶硬時間窗的車輛路徑問題的數學模型，需滿足以下條件：（1）各客戶的需求只能由一輛車一次服務完成，并且各客戶只在自己規定的時間窗范圍內才接受服務；（2）所有車輛均從配送中心出發開始服務，服務完畢后返回配送中心；（3）不考慮配送中心的取貨時間窗，即配送中心在任意時間都可以取貨；（4）除貨物數量外，不考慮貨物的其余屬性，同時各配送車輛的行駛速度固定且不考慮交通狀況。

根據上述符號說明，建立帶硬時間窗的車輛路徑問題數學模型如下：

式（1）為車輛總行駛路徑最小目標函數；式（2）為配送車輛的載重約束；式（3）表示每個客戶只能由一輛車進行服務；式（4）表示車輛服務某節點后必須從此節點出發去下一節點約束；式（5）和（6）表示每個客戶節點只允許被服務一次；式（7）為消去子回路約束；式（8）和（9）為時間窗約束。

3 GA-ACO混合算法

3.1 GA-ACO混合算法策略提出

遺傳算法能夠在大范圍內進行快速全局搜索，但是不能充分利用系統反饋的信息，所以在求解進行到一定范圍后，會有大量的重復迭代，這大大降低了算法的優化效率；而蟻群算法是采用分布式、并行的方式進行搜索，并且還具有正反饋的特點，正反饋使得它能夠很好地運用系統反饋的信息，但是由于前期信息素匱乏，求解速度很慢。遺傳算法和蟻群算法的優勢正好可以互補，混合在一起形成的混合算法可以提高單一算法的優化性能。

目前，蟻群算法和遺傳算法進行混合的研究很多，總結下來，其混合形式主要有以下四種：

（1）蟻群算法為主體，前期使用遺傳算法求解問題的可行解，利用這些可行解進行蟻群算法路徑上的信息素初始化，后期使用蟻群算法求解。

（2）遺傳算法為主體，前期使用蟻群算法求解問題較優解，作為遺傳算法初始種群，再使用遺傳算法進行求解。

（3）融合方式，即在遺傳算法交叉變異操作后，再使用蟻群算法進行優化。

（4）插入的方式，即在蟻群算法優化得到問題可行解后，選取若干可行解作為初始種群進行遺傳優化。

為了能夠充分利用遺傳算法的快速全局搜索特性以及蟻群算法的分布式計算、正反饋的特點，本文采用第四種插入的方式，即在蟻群算法的每一迭代過程中引入遺傳算法的交叉變異操作，將蟻群算法與遺傳算法融為一體，它們之間通過更新每次迭代過程中的最優解來相互指導。首先是蟻群算法在每次迭代后得到問題的若干可行解，從這些可行解中選出相對較優的幾個組合成遺傳算法的父代，父代通過復制、交叉以及變異過程產生子代，使用子代中的較優解來更新蟻群迭代可行解中的較差解，作為當次迭代的路徑來更新蟻群算法中各路徑上的信息素。使用遺傳算法中的交叉變異算子對蟻群算法得到的較優解進行進一步優化，可以有效的避免蟻群算法陷入局部最優。

3.2 GA-ACO混合算法的基本規則設計

（1）轉移規則設計。在求解VRPTW的蟻群遺傳混合算法中，蟻群算法部分的螞蟻轉移規則采用確定性選擇和隨機選擇相結合的過程，首先對螞蟻選擇下一個節點的轉移概率公式進行改進。定義如下參數：節點數量為n，人工蟻群的螞蟻數目為m，節點i與節點j之間的距離為dij，節點i與節點j之間路上的信息素濃度為τij；節點i與節點j之間的可見度（或者親密濃度）為ηij，ηij=1/dij；wij表示時間窗系數，wij=1waitij；螞蟻k可訪問節點的集合為allowedk。

則螞蟻k在t時刻從節點i轉移至節點j的概率pkij為：

其中，α為信息啟發式因子，β為期望啟發式因子，θ為時間窗啟發式因子，γ為節約距離值啟發式因子，Uij為節約距離，其計算公式見式（11），考慮當螞蟻從配送中心出發時，節約距離設定為定值1：

時間窗系數wij中的waitij是一個與車輛行駛時間和各客戶點服務時間窗相關的變量，其表達式為：

為了解決算法過早收斂這一問題，在螞蟻選擇下一個節點過程中引入變量q0，螞蟻按式（13）的規則選擇下一個節點。

其中q為隨機變量，q∈(0,1)，即在隨機變量q小于變量q0時，螞蟻選擇計算的轉移概率最大的節點進行訪問，否則，就隨機選擇一個可訪問的節點進行訪問。變量q0的值會隨著迭代次數的增加而發生改變，其變化公式為：

其中，NC代表當前的迭代次數，根據q0的變化可知，隨著迭代的進行，q0的值先變大再變小。這就意味著，在前期各螞蟻以較大的概率采用隨機選擇機制選擇下一個訪問節點，有助于各螞蟻在全局范圍內搜索最優解；中期則以較大的概率采用確定性選擇機制選擇下一個訪問節點，使得各螞蟻向著遍歷過的最優路徑上靠攏，使得算法收斂；而后期各螞蟻則以較大的概率采用隨機選擇機制選擇下一節點，進行全局搜索，有助于跳出局部最優。

（2）信息素更新規則設計。基本蟻群算法中螞蟻線路上的信息素更新規則如下：

其中：ρ為信息素揮發因子，ρ∈(0,1) ，即：τij(t)表示t時刻節點i到節點j之間的路徑上的信息素含量，它隨時間的推移而不斷的減少；Δτij(t)表示在當次循環中節點i到節點j之間路徑上的信息素增量，其表達式為：

其中：Q表示每只螞蟻攜帶的信息素總量，Lk為螞蟻當次迭代走過的總路徑。

本文對蟻群算法的信息素更新規則中的全局信息素更新規則和信息素殘留因子ρ進行如下改進，而局部信息素更新按照式（15）進行。

①全局信息素更新機制的改進。算法在每一次迭代結束時，對當次迭代下的最優路徑按照式（17）進行信息素的更新，式（17）中的Lk為當次迭代下最優路徑的長度。根據式（16）可以計算出每一次迭代運算后各路徑上的信息素增量。

與基本蟻群算法不同，定義信息素為標量，即信息素不具方向性，同時認為節點i至j與j至i增加的信息素在數值上具有一致性。所以改進的信息素更新規則如下：

②信息素揮發因子ρ的改進。在基本蟻群算法中，信息素揮發因子ρ是一個常量，各路徑上信息素的積累速度與ρ值的大小息息相關。研究發現，在算法前期，為避免陷入局部最優，需要設置較大的ρ值，可以擴大搜索范圍，使螞蟻能夠在更大的范圍內訪問各線路；而在算法后期，需要加快算法的收斂，設置較小的ρ值，放大各路徑上的信息素含量差異，使螞蟻逐步向優勢路徑集聚。為此，ρ值隨著迭代的進行，應該是一個由大到小的變化過程，本文提出使用下列階段函數模擬ρ值的變化：

（3）局部優化規則。為了避免算法陷入局部最優，在每次迭代結束后，使用遺傳算法對當次迭代的較優解進行局部優化，以增加解的多樣性。

3.3 染色體編碼與解碼

遺傳算法處理的直接對象是染色體，所以在使用遺傳算法對VRPTW等實際問題進行優化時，需要通過編碼建立實際問題與遺傳算法的染色體之間的聯系。在遺傳算法中可以使用的編碼方式有二進制編碼、實數編碼、符號編碼、自然數編碼等多種形式，其中二進制編碼和自然數編碼是最常用的。

本文選用自然數編碼方式對染色體進行編碼，由所有的客戶點的編號組成染色體的基因，所有基因的一個排列就是一個染色體結構。比如VRPTW共有14個客戶點，需要有3輛車進行配送，由蟻群算法求解的一個可行解（解中的1代表配送中心）為：

去掉可行解中的配送中心編號，只保留客戶節點編號，并且客戶節點編號的序列保持不變即為可行解對應的染色體結構。則該可行解轉換而來的染色體結構為：在同一限定條件下，編碼能夠保證所有染色體的長度都是一樣的，方便后續的交叉變異。

父代染色體經過復制、交叉、變異處理后，得到子代的染色體結構，進一步對子代染色體進行解碼，轉換成問題的可行解。解碼時按照VRPTW模型里面的約束條件，依次將同時符合車輛載重約束和客戶點時間窗約束的客戶分配給配送車輛。以下面的染色體結構為例：結合VRPTW模型中的約束，對其進行染色體解碼：首先將客戶5分配給車輛1，更新車輛1的時間和載重，再將其后的節點10分配給車輛1，檢驗載重約束和時間窗約束，如果載重和時間窗約束中有一個及以上不滿足，則形成子路徑（1,5,1），即車輛1只為客戶點5配送貨物；若都符合要求，則將客戶10也由車輛1配送，再依次檢驗后面的客戶，只要車輛超載或是不滿足時間窗約束，則啟動下一輛車，依次檢驗下去，直到染色體結構中所有的客戶點都被分配完。上述子代染色體解碼出來的可行解可能為：

即共需要三輛車完成配送，其路徑分別為（1,5,10,6,9,3,1），（1,8,7,14,2,4,1）和（1,12,13,11,1）。

3.4 遺傳算子

遺傳算法中的核心遺傳算子主要有選擇算子、交叉算子和變異算子三個，它們與遺傳算法的性能息息相關。

（1）選擇算子。選擇也稱之為復制，就是按照一定的原則或方法，選擇種群中優秀的個體作為父代來繁衍子代的過程。在基本遺傳算法中，使用的選擇策略有精華選擇和比例選擇兩種形式。精華選擇就是每次從種群中選取適應度最好的個體作為父代中的一個，直到選出組成種群需要的個體數目；而比例選擇就是每次隨機從種群中選取一個，不一定每次都是最好的那個，直到選出構建種群需要的個體數。

本文設計的蟻群遺傳混合算法，是以蟻群算法為主體，將遺傳算法融入到蟻群算法的每一次迭代計算中，使用遺傳算法對蟻群算法求得的解進行局部優化。所以本文采用的是精華選擇策略，即從每次迭代得到的路線中，選取總路徑相對較小的若干只螞蟻的行駛路徑作為遺傳算法中的種群。

（2）交叉算子。交叉也叫重組，是自然進化過程中新個體或物種產生的主要方式。在遺傳算法中常用的交叉算子有一點交叉、兩點交叉、異位交叉、基于次序的交叉等多種形式。前兩種交叉方式主要用于使用二進制編碼的遺傳算法中，后面的幾種形式常用于使用自然數編碼的遺傳算法中。

本文選用的是異位交叉的形式。其主要步驟為：①隨機生成兩個交叉點x和y，假設x≤y；②父代1中的交叉區域基因為第x到y位，父代2中的交叉區域基因為第1到y-x+1位，并交換父代中交叉區域的基因；③對于交換區域外的重復基因，根據交叉區域中的基因對應關系進行替換，替換完成后得到子代。

（3）變異算子。在遺傳算法中通過增加變異算子來模擬自然界中基因突變這一環節，變異算子的作用雖然小于交叉算子，但也是遺傳算法所必須的，它能夠有效地增強遺傳算法的局部搜索能力，避免算法優化得到的解陷入局部最優，發生過早收斂現象。遺傳算法中常用的變異算子有反轉變異、2-opt變異等多種形式。

本文選用的變異算子是反轉變異方式。首先隨機確定兩個基因位，然后把這兩個基因位之間的染色體基因進行反序排列，即得到子代個體的染色體結構。

4 GA-ACO混合算法的實現

4.1 算法步驟

帶硬時間窗的VRPTW混合算法的具體流程描述如下：

Step1：初始化各參數。設初始迭代次數NC=1，設置算法最大迭代次數NCmax，初始化蟻群算法部分的相關系數α、β、γ、θ，螞蟻數量m，信息素Q，初始化Tabu表以及Tau表；設置遺傳算法部分的交叉概率Pc和變異概率Pm。計算ηij，初始化各路徑上的信息素為1。

Step2：將m只螞蟻初始化到各節點上，并將各螞蟻的初始化城市編號放入Tabu表中。

Step3：對于從節點i出發的螞蟻，按照轉移概率式（10）計算并得到螞蟻k將要轉移的下一個節點j。

Step4：判斷螞蟻k是否遍歷完成所有節點或是滿足載重和時間窗約束，若不滿足約束，則回到配送中心，轉到Step3；若遍歷完成所有客戶節點，則轉到Step5；否則，螞蟻k成功轉至節點j，將節點j加入Tabu表中并轉到Step3。

Step5：判斷螞蟻k是否回到配送中心，若沒有回到配送中心，則將節點1加入到Tabu表，并轉至Step6；否則直接轉至Step6。

Step6：判斷k是否大于螞蟻數m，若k＞m，轉到Step7；否則k=k+1，轉至Step3。

Step7：計算各螞蟻所走路徑的長度，按路徑長短選取路徑短的若干只螞蟻的行駛路徑，初始化為蟻群算法的初始種群，并轉至Step8；

Step8：依次隨機從種群中選取兩個個體作為父代，使用遺傳算法進行優化，直到種群中所有的可能都被選擇完畢，得到子代并轉至Step9。

Step9：對子代染色體進行解碼，并計算各子代個體染色體解碼后的路徑長度，用路徑短的線路更新掉原來螞蟻走過的路徑較長的線路，更新Tabu表和相應的路徑長度，以及每次迭代的最佳路徑。

Step10：進行信息素更新，更新Tau表，得到當前迭代次數中的最優解，并初始化相關數據表。

Step11：判斷迭代次數NC是否超過設置的最大迭代次數NCmax，若超過最大迭代次數NCmax，則算法終止，輸出問題的最優路徑和最優路徑長度。否則NC=NC+1，跳到Step2。

4.2 算法流程

根據上面所述的步驟，使用GA-ACO混合算法求解VRPTW問題的流程圖如圖1所示。

4.3 算例分析

選取文獻[12]和文獻[16]中的共同算例作為本文計算算例，在MATLAB軟件中編寫上述GA-ACO混合算法的程序對上述算例進行仿真運算。

該仿真算例有一個配送中心節點，20個客戶節點，共21個節點，配送車輛的額定載重為8t，車輛的行駛速度為60km/h，各節點的坐標位置、需求、允許服務時間窗等數據見表1（節點編號1指配送中心，其余的為各客戶節點的編號）。

圖1 GA-ACO混合算法的流程圖

編寫算法程序，在MATLAB軟件中多次仿真運算，對仿真結果和參數進行統計，結果表明，本文設計的混合蟻群算法在下列參數設置下，算法具有較好的性能。

按照上述參數對改進蟻群算法進行初始化設置，在MATLAB軟件中運行本文改進的蟻群算法100次，取其中較好的10次數據作為展示，見表2。

由上述結果可知，使用本文改進的蟻群算法計算文獻中算例得到的最優路徑長度為1 170.68km，最優路徑車輛行駛線路如圖2所示，最優路徑出現時的混合算法收斂曲線圖如圖3所示。

將使用本文設計的混合算法求解20個客戶節點算例得到的最優結果與文獻中的算法求解同樣算例的結果進行比較，見表3。

表1 算例中各節點的位置坐標與需求量

表2 算例運行結果

表3 最優值比較

由表3中的對比結果可以看出，運用本文設計的蟻群遺傳混合算法求解20個客戶節點的帶硬時間窗的VRPTW算例，得到的最優結果比文獻[12]中的結果優化了6.29%，比文獻[16]中的結果優化了7.53%，可見本文設計的混合算法是有效的，并且具有一定的優越性。

圖2 最優結果路線圖

圖3 最優路徑時算法收斂圖

5 結語

本文針對車輛路徑問題中的經典變型—帶時間窗的車輛路徑問題，設計了一種以改進蟻群算法為主體、插入遺傳算法作為局部優化手段的改進混合算法。充分考慮問題的實際情境，結合時間窗等相關約束條件建立VRPTW問題的數學模型，設計改進混合算法，通過對文獻中的算例進行仿真運算，仿真結果證明改進混合算法可有效提高收斂速度并提高解的質量。通過與其它文獻中的最優結果進行對比分析，驗證了本文設計的GA-ACO改進混合算法在求解帶時間窗的車輛路徑問題上的有效性和優越性。同時需要說明的是，隨著約束條件的變化，算法的構造就更為復雜，同時算法求解時的群體屬性也是可以變化的，這些都可以作為以后的研究方向。