物流配送中煙花算法結合遺傳算法的異質車隊路徑優化方法

龐 凌12

(1.遼寧裝備制造職業技術學院，沈陽 110161；2.遼寧廣播電視大學，沈陽 110161)

0 引言

物流作為現代社會運轉的重要環節，越來越受到人們的關注[1]。貨物配送是物流的核心環節，車輛路徑問題一直是物流中的基本問題之一，因此研究配送中的車輛路徑問題(vehicle routing problem，VRP)對于企業經濟性至關重要。VRP問題在傳統意義上來說是指已知倉庫位置、客戶位置和需求，在特定的約束下尋找到一條最優路徑，對各個客戶進行訪問，要求運輸成本最低。VRP問題是經典的組合優化領域典型難題之一，在數學和計算機科學等領域已經研究多年的問題，它易于描述但很難解決[2]。

傳統VRP的衍生變化主要來源于一些時間、空間和非空間限制，例如有考慮運輸能力的VRP，其車輛的均勻可用且唯一的約束是車輛容量；或具有時間窗的VRP，其客戶服務必須在規定的時間間隔內進行，需要確定車輛行程的時間表[3]；當以不同容量和成本為特征的車輛用于配送業務時，VRP的一個重要變體出現，這被稱為混合車隊VRP或異質車隊VRP[4]。許多學者致力于解決這一難題及其衍生問題。文獻[5]提出了一種基于遺傳算法的應急疏散中車輛路徑規劃研究。文獻[6]提出了一種基于禁忌搜索算法車輛路徑優化方法，禁忌算法在初始解的基礎上引入靈活的儲存結構和相應的禁忌準則來避免重復的搜索，但對于初始解的依賴過多。文獻[7]提出了一種混合回程和時間窗的VRP的粒子群優化算法。文獻[8]提出了一種基于改進蝙蝠算法的帶模糊需求的車輛路徑優化方法。文獻[9]提出了一種基于人工魚群算法的模糊VRP問題優化方法。文獻[10]研究了異構固定的開放式車輛路徑問題，其中客戶的需求由固定數量的具有各種容量和相關成本的車輛組成，是典型VRP的重要變體，可以涵蓋運輸中的更多實際情況。

已有的文獻采用單個智能算法用于求解VRP問題，在全局搜索能力方面仍有一定的改進空間。混合智能算法能夠有效結合各個算法中的優點，提高算法的全局搜索能力。因此，針對物流配送中異質車隊路徑優化問題，提出了一種煙花算法結合遺傳算法的車輛路徑優化方法。利用兩階段構造理論有效的將兩種智能算法進行融合。車輛分配階段采用改進的遺傳算法為客戶分配車輛。路徑階段的倉庫局部路徑采用煙花算法生成并優化從倉庫到適當容量區域內所有城市的路線。提出的混合算法有效的提高了搜索的全局能力。

1 車輛路徑問題及其拓展

車輛路徑的目的是確定交通網絡中車輛的最佳收集或交付路線[11]。VRP是一個非確定性的多項式時間內求解困難問題，通過要求將車頂點分配到每個車輛路線內的這些頂點的順序來概括經典旅行商問題以獲得解決方案。

1.1 車輛路徑問題

VRP問題如圖1中描述。假定有M個車輛，每輛車的運力為Q，并且具有N個客戶，他們所要求的貨物必須從倉庫發出。每個客戶要求的貨物和它們之間的距離是事先已知的。車輛從倉庫出發，為客戶提供服務并返回倉庫。要求車輛的路線應適當布置，以便使用最少數量的車輛并能夠保證運送的距離最短，同時必須滿足以下條件：(1)任何車輛路線的總需求不得超過車輛的容量；(2)任何特定客戶由一輛且僅一輛車輛提供服務；(3)客戶交付不能在兩輛運輸車輛之間分配。

圖1 車輛路徑問題

該成本通常被解釋為距離或旅行時間，具體取決于上下文。除非另有說明，否則可以認為這是一個最具成本效益的車輛路線。這一點確定了一組最具成本效益的車輛路線，以便(1)除了倉庫之外，每個頂點只需一輛車就可以訪問一次以滿足其需求;(2)所有車輛路線在倉庫開始和結束;(3)每條路線的總需求量不超過車輛容量。

有時，每個車輛都有一個固定的開銷。需要優化的目標是最小化固定費用和旅行費用的加權總和。除了容量約束之外，還可以考慮每個車輛路線的最大距離或時間約束。

基于要優化的目標函數和要滿足的約束類型，產生了該問題的大量的變體。當具有不同容量和成本的車輛可用于分配活動時，VRP的一個重要變體出現。

1.2 路由VRP 的數學表示

混合車隊VRP 可以以下面的方式描述。給定一個有向圖G=(V,A) ，其中V={0,1,2,...,n} 表示具有(n+1) 個節點的節點集合，A表示弧的集合。節點0表示倉庫，剩余的節點V{0} 表示n個客戶。

路徑可以以二元組(R,k)的形式定義，其中R=(i1,i2,...,i|R|)，i1=i|R|=0且有一個包含倉庫的回路G=(i2,...,i|R|-1)?V′，k是與路線相關的車輛類型，R用于參考訪問序列和顧客的集合(包括倉庫)的路線。一個路線(R,k) 是可行的如果路徑上所有需要訪問的客戶的總需求不超過車輛的運力Qk。

異構VRP的最通用版本由分配一組可行的最短路徑和使總開銷最小化兩部分組成，即：

1)每個客戶都僅在一條路徑上被訪問；

2)每種車輛所執行的路徑總數不超過mk。

可以通過以下方式呈現異構車輛路徑問題的最一般變型的形式。由(F1)z(F1) 表示的目標函數表示路線的最小旅行成本函數，并由下面的式(1)定義：

(1)

(2)

?p∈V′,?k∈M

(3)

(4)

(5)

?i,j∈V,i≠j,?k∈M

(6)

yij≥0,?i,j∈V,i≠j

(7)

(8)

在上述書面表述中，約束條件(2)和(3)確?？蛻舯辉L問，并且訪問客戶需要從訪問者的角度來看待客戶。通過約束(4)，可以獲得可用于汽車類型的車輛的最大數量。約束(5)是商品流量約束。他們指出，在訪問客戶之前和之后車輛攜帶的貨物數量之間的差異等于該客戶的需求。最后，約束(6)確保永遠不會超過車輛容量。

在本研究中，式(5)未討論車輛攜帶的貨物數量與客戶要求的貨物數量之間的差異。通過這種方式，異構VRP部分地簡化了這個NP 困難問題的復雜性。除容量限制外，還可以考慮每個車輛路線的最大距離約束。

2 煙花算法結合遺傳算法的異質車隊路徑優化方法

2.1 煙花算法

煙花算法(Fireworks Algorithm, FWA)[11]是一種新型的群體智能算法。煙花算法通過模擬煙花在空中爆炸的現象來進行多點同時爆炸式搜索，能夠解決各種全局最優解搜索的問題，并且適應性很強，易于融入到實際生產和生活中。

煙花算法將尋優問題中的搜索空間對應到實際煙花爆炸產生的范圍，采用煙花爆炸的位置、爆炸產生火花的位置來表示可行解，并選擇其中適應值最好的位置來當作下一個煙花的炸點，而且能夠通過設置煙花爆炸范圍、層數、煙花數量等來調整鄰域集。在計算過程中，使用適應值函數對每個煙花及其產生的火花進行比較，求得適應值。若適應值越小，則對應的煙花及火花則屬于優質的個體。在下一代中，其煙花或則火花爆炸時產生的火花數量越多，爆炸的范圍越小。反之，適應值越大，煙花質量越差，下一代時產生火花越小，爆炸范圍越大。

煙花算法主要由4個部分組成：爆炸算子、變異操作、映射操作和選擇操作。

1)爆炸算子：由爆炸強度、爆炸幅度和位移操作三部分組成；

2)變異操作：采用高斯變異；

3)映射操作：由模運算、鏡面反射、隨機映射組成；

4)選擇操作：由基于距離的選擇操作、隨機選擇操作等組成。

煙花算法的算法執行流程如圖2所示。

圖2 煙花算法的算法執行流程

煙花算法具體包括以下幾個步驟[12]:

1)所有的煙花都是無性的，因此，在一定的空間中隨機產生一定數量的煙花，每個煙花代表該空間中的一個可行解。

2)煙花爆炸釋放出來的火花可以分為兩種形式：爆炸火花和高斯變異火花。煙花質量的好壞可以通過計算每個煙花的適應度值來評估。

3)判定是否滿足終止條件。如果滿足則停止搜索，否則在爆炸火花、高斯變異火花和煙花中選擇一定數量的個體作為煙花進入下一代的迭代。

2.3 兩階段構造理論

在許多VRP問題的解決方案中，兩階段理論常被采用的主要有兩種：

1)優先聚類，其次路徑?；谝恍┙咏葴y量，首先將頂點分組在兩個不同的子集中。然后，在每一個組內，將頂點排序從而形成一條路徑。

2)優先路徑，其次聚類。這是聚類優先的一種替代方法，它首先構建了訪問所有頂點的巨型路徑。然后，路徑被劃分為較小的可行路徑。

異質性VRP的特點是不同的容量和成本可用于分配活動?；趦呻A段構造的理論，能夠非常好地解決了異構的VRP的問題。采用優先聚類其次路徑的構造理論。由兩個不同的模塊組成：通過聚類在第一個階段內容為客戶分配車輛；第二階段通過對路徑排序實現本地路徑優化。

2.3 混合算法異質車隊路徑優化方法

混合算法利用兩階段構造理論對兩種算法進行融合。對聚類階段在的進行了改進，為了實現更真實的現實模型定義了運力空間，運力空間是一個地理區域，所有適當的客戶及其訂單只能通過一個參與的車隊來提供服務。然后，按運力空間劃分聚類區域，并且基于圓形層組。由兩個不同的模塊組成：1)聚類模塊，它定義容量區，然后將客戶分配給車輛—這是第一個過程；2)一個倉庫區域路線模塊，它優化從倉庫到適當容量區域內所有城市的路線，這是第二個過程。

遺傳算法[13]用于優化過程的第一部分，以定義容量區域。對于優化過程的第二部分，使用煙花優化算法。在路徑異構車隊VRP中提出的混合遺傳算法結合了遺傳算法和煙花算法來生成容量區、弧和路徑，從而在數據集中獲得異構車隊VRP的最佳結果。

3 算例分析

實驗結果顯示了原始數據集的經驗模型，其中顯示了距離(km)、肉類重量(kg)、數量，接合能力(kg)和運力利用率。實驗結果通過混合遺傳算法獲得。表1是車隊中各種車輛的運輸能力。

表1 車隊中每種車輛的數量和運力 kg

實驗結果如表2所示，它們包括距離，運輸肉的重量，路線數量，參與的容量和經驗模型的運力利用率。然后，對經驗模型和混合算法得到的實驗結果進行比較，比較包括距離，路徑，參與的流量和流量利用率。特別強調這兩種方法之間的比較結果，即1)減少和最小化距離方面的改進，以及2)車輛容量利用方面的改進。

表2 經驗模型與混合算法對比

實驗結果表明，通過對平均值、標準差和中位數的值進行比較，所提出的混合算法比經驗模型得到的結果更好。與經驗模型相比，所提出的混合算法中10個分布日覆蓋的總距離值減少了5 103 km，即10.4%?？梢哉J為車輛的平均油耗為每100公里32升，1升燃油成本為7.62[14]，這意味著在這10個工作日中可以節約12 000元的成本?；旌纤惴ㄅc經驗模型的總運力的值差異為84 420千克，或8 420千克/天。這意味著參與的車輛的總運力減少了4.4%，也就是每天可以少使用兩輛車，每天減少兩條路線。因此可以得出結論，更多的客戶聚集在相似的位置，即同一容量區域，可以降低成本運輸功能，從而能夠更好地優化物流配送流程。

4 結論

針對物流配送中車輛路徑的問題，提出了一種煙花算法結合遺傳算法的物流配送中異質車隊路徑優化方法。將實驗結果與經驗結果對比，所提出的方法得到的實驗結果優于原始數據的經驗結果。

異質車隊路徑研究未來的發展主要集中在其他大型數據集上，并且在混合智能算法改進與應用中需進一步開展研究工作。另外所提的混合算法只考慮了不帶時間窗的異質車隊問題，對于更加復雜的VRP問題的應用仍需要后續進一步研究。