龐 凌12

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

0 引言

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

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

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

1 車輛路徑問題及其拓展

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

1.1 車輛路徑問題

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

圖1 車輛路徑問題

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

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

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

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

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

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

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

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

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)確保永遠(yuǎn)不會(huì)超過車輛容量。

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

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

2.1 煙花算法

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

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

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

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

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

3)映射操作：由模運(yùn)算、鏡面反射、隨機(jī)映射組成；

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

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

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

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

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

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

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

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

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

1)優(yōu)先聚類，其次路徑。基于一些接近度測(cè)量，首先將頂點(diǎn)分組在兩個(gè)不同的子集中。然后，在每一個(gè)組內(nèi)，將頂點(diǎn)排序從而形成一條路徑。

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

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

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

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

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

3 算例分析

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

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

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

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

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

4 結(jié)論

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

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