物流配送中煙花算法結(jié)合遺傳算法的異質(zhì)車隊路徑優(yōu)化方法

龐 凌12

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

0 引言

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

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

已有的文獻采用單個智能算法用于求解VRP問題，在全局搜索能力方面仍有一定的改進空間?；旌现悄芩惴軌蛴行ЫY(jié)合各個算法中的優(yōu)點，提高算法的全局搜索能力。因此，針對物流配送中異質(zhì)車隊路徑優(yōu)化問題，提出了一種煙花算法結(jié)合遺傳算法的車輛路徑優(yōu)化方法。利用兩階段構(gòu)造理論有效的將兩種智能算法進行融合。車輛分配階段采用改進的遺傳算法為客戶分配車輛。路徑階段的倉庫局部路徑采用煙花算法生成并優(yōu)化從倉庫到適當(dāng)容量區(qū)域內(nèi)所有城市的路線。提出的混合算法有效的提高了搜索的全局能力。

1 車輛路徑問題及其拓展

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

1.1 車輛路徑問題

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

圖1 車輛路徑問題

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

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

基于要優(yōu)化的目標(biāo)函數(shù)和要滿足的約束類型，產(chǎn)生了該問題的大量的變體。當(dāng)具有不同容量和成本的車輛可用于分配活動時，VRP的一個重要變體出現(xiàn)。

1.2 路由VRP 的數(shù)學(xué)表示

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

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

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

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

2)每種車輛所執(zhí)行的路徑總數(shù)不超過mk。

可以通過以下方式呈現(xiàn)異構(gòu)車輛路徑問題的最一般變型的形式。由(F1)z(F1) 表示的目標(biāo)函數(shù)表示路線的最小旅行成本函數(shù)，并由下面的式(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)，可以獲得可用于汽車類型的車輛的最大數(shù)量。約束(5)是商品流量約束。他們指出，在訪問客戶之前和之后車輛攜帶的貨物數(shù)量之間的差異等于該客戶的需求。最后，約束(6)確保永遠不會超過車輛容量。

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

2 煙花算法結(jié)合遺傳算法的異質(zhì)車隊路徑優(yōu)化方法

2.1 煙花算法

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

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

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

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

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

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

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

煙花算法的算法執(zhí)行流程如圖2所示。

圖2 煙花算法的算法執(zhí)行流程

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

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

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

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

2.3 兩階段構(gòu)造理論

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

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

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

異質(zhì)性VRP的特點是不同的容量和成本可用于分配活動?；趦呻A段構(gòu)造的理論，能夠非常好地解決了異構(gòu)的VRP的問題。采用優(yōu)先聚類其次路徑的構(gòu)造理論。由兩個不同的模塊組成：通過聚類在第一個階段內(nèi)容為客戶分配車輛；第二階段通過對路徑排序?qū)崿F(xiàn)本地路徑優(yōu)化。

2.3 混合算法異質(zhì)車隊路徑優(yōu)化方法

混合算法利用兩階段構(gòu)造理論對兩種算法進行融合。對聚類階段在的進行了改進，為了實現(xiàn)更真實的現(xiàn)實模型定義了運力空間，運力空間是一個地理區(qū)域，所有適當(dāng)?shù)目蛻艏捌溆唵沃荒芡ㄟ^一個參與的車隊來提供服務(wù)。然后，按運力空間劃分聚類區(qū)域，并且基于圓形層組。由兩個不同的模塊組成：1)聚類模塊，它定義容量區(qū)，然后將客戶分配給車輛—這是第一個過程；2)一個倉庫區(qū)域路線模塊，它優(yōu)化從倉庫到適當(dāng)容量區(qū)域內(nèi)所有城市的路線，這是第二個過程。

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

3 算例分析

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

表1 車隊中每種車輛的數(shù)量和運力 kg

實驗結(jié)果如表2所示，它們包括距離，運輸肉的重量，路線數(shù)量，參與的容量和經(jīng)驗?zāi)Ｐ偷倪\力利用率。然后，對經(jīng)驗?zāi)Ｐ秃突旌纤惴ǖ玫降膶嶒灲Y(jié)果進行比較，比較包括距離，路徑，參與的流量和流量利用率。特別強調(diào)這兩種方法之間的比較結(jié)果，即1)減少和最小化距離方面的改進，以及2)車輛容量利用方面的改進。

表2 經(jīng)驗?zāi)Ｐ团c混合算法對比

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

4 結(jié)論

針對物流配送中車輛路徑的問題，提出了一種煙花算法結(jié)合遺傳算法的物流配送中異質(zhì)車隊路徑優(yōu)化方法。將實驗結(jié)果與經(jīng)驗結(jié)果對比，所提出的方法得到的實驗結(jié)果優(yōu)于原始數(shù)據(jù)的經(jīng)驗結(jié)果。

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