改進(jìn)果蠅算法的運(yùn)輸車輛路徑規(guī)劃

趙 杰， 胡浩然， 孫啟智, 葛遵輝

(黑龍江科技大學(xué) 電氣與控制工程學(xué)院， 哈爾濱 150022)

0 引 言

物流配送車輛的路徑規(guī)劃是諸多規(guī)劃出將物品運(yùn)送到客戶手中的最優(yōu)方案，是一個(gè)多配送站的配送問題(Multi-depot vehicle routing problem,MDVRP)。目前，關(guān)于MDVRP問題有諸多的研究，Klapp等[1]以最小化總運(yùn)送成本為目標(biāo)，提出以車輛容量和行駛里程為約束條件的MDVRP，設(shè)計(jì)了禁忌搜索算法。Mirabi等[2]研究了以最小配送時(shí)間為目標(biāo)的MDVRP，提出一種隨機(jī)混合啟發(fā)式算法。Kuo等[3]針對(duì)具有裝載成本的MDVRP，設(shè)計(jì)了三階段的變鄰域搜索算法。Ran等[4]基于多承運(yùn)商合作情形下的MDVRP，給出一種兩階段貪婪啟發(fā)式算法。Salhi等[5]建立了異質(zhì)車輛的MDVRP模型，根據(jù)車站是否共享、每種車輛數(shù)目限制、每個(gè)配送站的容量限制進(jìn)行了擴(kuò)展，配送車輛的行駛速度、行駛距離均會(huì)對(duì)燃料消耗量具有顯著的影響，燃料消耗直接影響配送成本。Demir等[6]提出車輛裝載量、發(fā)動(dòng)機(jī)類型和尺寸、道路坡度等因素與配送車輛的燃料消耗具有一定的關(guān)系，影響配送成本。筆者提出考慮成本和燃料消耗優(yōu)化MDVRP的方法，設(shè)計(jì)多種群果蠅算法對(duì)路徑規(guī)劃問題進(jìn)行求解。

1 模型構(gòu)建

1.1 燃料消耗量與成本模型

Sahin等[7]指出，載荷20 t的卡車滿載行駛時(shí)平均每1 000 km的燃料消耗成本占據(jù)了物流總成本的60%。基于上述研究，構(gòu)建了行駛里程與燃料消耗量的模型為

式中：ρ*——車輛滿載時(shí)的燃料消耗率；

ρ0——車輛空載時(shí)的燃料消耗率；

mmax——車輛的最大裝載量；

ρ(m1)——車輛裝載量m1時(shí)單位行駛里程的燃料消耗量。

對(duì)于任意配送路徑(i,j)，當(dāng)配送車輛配送完消費(fèi)者i，駛向消費(fèi)者j的這段路徑中，設(shè)配送車輛k在該段路徑上的實(shí)際裝載量為mijk，則該段路徑上單位行駛里程的燃料消耗為

ρij=ρ(mijk)，

式中,ρij——車輛行駛在i和j之間的路徑(i,j)上的燃料消耗率。

燃料消耗成本可以表示為

式中：Co——單位燃料成本；

dij——兩個(gè)消費(fèi)者之間的歐氏距離。

1.2 問題描述與模型構(gòu)建

一個(gè)城市物流配送系統(tǒng)擁有M個(gè)配送中心，n個(gè)客戶。每輛配送車輛的最大荷載量為mmax，考慮到車輛油耗和司機(jī)工作負(fù)荷存在約束，配送車輛的行駛距離不超過L。要求在滿足車輛載重和行駛距離的約束條件下，合理安排配送車輛和車輛的行駛路線，基于最小化配送的成本和行駛距離，構(gòu)建的模型為：

式中：Chc——每輛車的租賃成本費(fèi)用；

Cvc——車輛單位行駛里程的變動(dòng)成本；

Cfc——單位燃料消耗成本；

C——消費(fèi)者位置的集合，C={v1,v2,…,vn}；

n——消費(fèi)者數(shù)量；

D——配送中心點(diǎn)集合，D={vn+1,vn+2,…,vn+M}；

M——配送中心數(shù)量；

N——消費(fèi)者和配送中心集合，N=C∪D；

K——可供使用的配送車輛集合，K={k1,k2,…,ks}，

s——車輛總數(shù)；

dij——任意兩點(diǎn)i和j之間的歐氏距離；

xijk——變量，若車輛k經(jīng)過路徑(i,j)值為1，否則為0。

為保證每個(gè)消費(fèi)者僅被一輛車服務(wù)一次，加入的約束條件為：

為保證路徑的連續(xù)性，加入的約束條件為：

車輛的容量約束和行駛時(shí)間限制分別表示為：

式中：mk——配送車輛k(k∈K)的最大裝載量；

Ti——配送中心給消費(fèi)者i的最晚收貨時(shí)間；

mi——消費(fèi)者i的需求量(0≤mi≤mmax,i∈C)。

車輛行駛過程中每段行駛路徑上的載重量限制條件為：

mjxijk≤gijk≤(mmax-mi)xijk，?(i,j)∈A,k∈K，

式中：gijk——配送車輛k經(jīng)過路徑(i,j)時(shí)貨物的運(yùn)輸量；

A——路徑集合，A={(i,j)|i,j∈N,i≠j}。

2 多種群的改進(jìn)果蠅算法

VRP屬于NP-Hard問題，國內(nèi)外學(xué)者通常采用啟發(fā)式或亞啟發(fā)式算法進(jìn)行求解[8-10]，而文中模型涉及多個(gè)配送中心、燃料消耗量優(yōu)化，使求解更加困難。Pan[11]受到果蠅覓食行為的啟發(fā)提出果蠅優(yōu)化算法(Fruit fly optimization,FFO)。FFO具有參數(shù)少，收斂速度快的優(yōu)點(diǎn)，然而果蠅種群存在容易陷入局部最優(yōu)的劣勢(shì)[12]，因此文中試圖對(duì)其進(jìn)行改進(jìn)，在FFO的基礎(chǔ)上，設(shè)計(jì)基于多種群的改進(jìn)果蠅優(yōu)化算法(Improved fruit fly optimization algorithm, IFFO)對(duì)文中模型進(jìn)行求解。

2.1 解的編碼

考慮到MDVRP屬于典型的離散優(yōu)化問題，文中采用自然數(shù)編碼方式表示調(diào)度方案，設(shè)調(diào)度方案X=(x1,x2,…,xk)T，其中k表示車輛數(shù)目，xk=(0,r1,r2,…,rs,0)表示第k輛車的配送路線，0則表示配送站下標(biāo)。在具體編碼階段，首先將MDVRP轉(zhuǎn)化為多個(gè)VRP進(jìn)行并行求解，然后根據(jù)油耗、成本等外部因素，為每一位客戶分配配送車輛，設(shè)計(jì)配送車輛的行駛路線。具體解碼過程：(1)根據(jù)果蠅個(gè)體編碼，得到車輛的具體方位與排列順序。(2)根據(jù)車輛的排列順序，得到運(yùn)輸任務(wù)的序列T=(t1,t2,…,tk)。(3)將運(yùn)輸任務(wù)序列按照油耗配送時(shí)間等約束條件分配給W個(gè)運(yùn)輸車輛。(4)得到W個(gè)運(yùn)輸車輛根據(jù)建模條件的約束，自動(dòng)劃分每個(gè)車輛應(yīng)到哪個(gè)目標(biāo)點(diǎn)合理。(5)根據(jù)改進(jìn)果蠅優(yōu)化算法進(jìn)行合理路徑規(guī)劃。

2.2 多種群方法

多種群的方法可以使算法在一次運(yùn)行中獲得多個(gè)較優(yōu)解，已被廣泛應(yīng)用到車間調(diào)度等NP-Hard問題求解中[12]。針對(duì)果蠅算法求解過程中易陷入局部最優(yōu)的劣勢(shì)，文中采用多種群同時(shí)進(jìn)化的策略，將果蠅種群中的個(gè)體分成多個(gè)子種群；同時(shí)，為了有效地利用各子種群中優(yōu)勢(shì)解的有利信息，加強(qiáng)子種群之間的交流協(xié)作，在果蠅算法的迭代過程中設(shè)計(jì)了子種群之間的交流互動(dòng)策略，通過子種群中最優(yōu)個(gè)體之間的信息交互，增強(qiáng)最優(yōu)解的搜索效率和搜索精度。圖1為子種群間的信息交互策略，在子種群1中隨機(jī)選擇一個(gè)果蠅個(gè)體，如選中子種群1中的個(gè)體d1作為父代1，然后分別以概率P0、P1和P2選擇同一種群中的個(gè)體、其他子種群中的個(gè)體和全局最優(yōu)個(gè)體執(zhí)行交叉操作，這種子種群之間的信息交互方式提高了對(duì)問題最優(yōu)解的搜索能力，同時(shí)以一定概率將種群中最優(yōu)個(gè)體的優(yōu)秀基因傳遞到當(dāng)前個(gè)體中，可以實(shí)現(xiàn)快速收斂。

圖1 子種群之間的信息交互形式Fig. 1 Information interaction between subpopulations

2.3 個(gè)體的遺傳進(jìn)化策略

在原果蠅算法中，果蠅個(gè)體的更新是通過不斷的新舊最佳值比較而得到的，這樣容易陷入早熟收斂境地，同時(shí)也會(huì)失去果蠅群體中果蠅的的個(gè)數(shù)，導(dǎo)致搜索速度下降，在文中設(shè)計(jì)的IFFO中，引入遺傳算法中的交叉操作，以獲得新的果蠅個(gè)體。為提高解的搜索能力，根據(jù)果蠅個(gè)體的編碼方式設(shè)計(jì)了果蠅個(gè)體基因的刪除、交叉策略，如圖2所示。在同一種群中果蠅個(gè)體必有相似基因，但是在相似基因中所包含的信息不同。隨機(jī)選中同一種群中的父代1果蠅個(gè)體和父代2果蠅個(gè)體，其中鎖定父代1和父代2的相同基因，然后在父代1中刪除一組相似基因，在父代2中刪除另一組相似基因，由于父代1 中刪除的基因與父代2中的基因存在相似基因，因此利用父代2中基因來代替父代1中刪除的基因，進(jìn)而實(shí)現(xiàn)了果蠅個(gè)體基因的刪除、交叉策略。同理在父代2中刪除的基因也是如此替代。此時(shí)產(chǎn)生新的果蠅個(gè)體，新的果蠅個(gè)體都具有了對(duì)方的基因信息，從而進(jìn)一步提升搜素速度。

圖2 交叉算子Fig. 2 Crossover operator

同時(shí)，為了提高果蠅個(gè)體間的多樣性，在IFFO中采用交換(swap)、移位(insert)、倒置(invert)三種變異算子，三種變異算子的圖示如圖3所示。其中，交換變異是隨機(jī)的選擇兩個(gè)不同位置，然后交換兩個(gè)位置上的消費(fèi)者；而移位變異是隨機(jī)選擇一個(gè)位置上的消費(fèi)者，并將其插入到另一個(gè)隨機(jī)位置，根據(jù)文中的編碼方式可知，交換變異操作和移位變異操作選中的兩個(gè)位置既可以是同一條子路徑上的兩個(gè)位置，也可以是不同子路徑上的兩個(gè)位置，這樣就使得不同的路徑能夠順暢的實(shí)現(xiàn)“信息交流”，增加解空間的搜索范圍。倒置變異首先隨機(jī)選中一條子路徑(即一條配送路線)，然后在該子路徑上隨機(jī)選擇兩個(gè)不同的位置，并將兩個(gè)位置之間的消費(fèi)者順序進(jìn)行翻轉(zhuǎn)。

通過交叉和變異產(chǎn)生的新果蠅個(gè)體被放入到對(duì)應(yīng)的種群中，并在選擇階段依據(jù)精英保留策略將該子問題的較好個(gè)體遺傳到下一代。

圖3 交換、倒置、隨機(jī)插入算子Fig. 3 Swap, invert, and random insert operators

2.4 算法步驟

初始化階段主要分為兩步：算法參數(shù)的初始化與種群個(gè)體的初始化。

Step1算法參數(shù)主要有：果蠅子種群個(gè)數(shù)(N)、子種群的果蠅個(gè)體數(shù)目(P)、算法迭代次數(shù)(M)、子種群交流互動(dòng)準(zhǔn)則(I)。

Step2為了擴(kuò)大解的搜索范圍，文中采用隨機(jī)初始化的方式，具體來說，在為消費(fèi)者i分配配送車輛時(shí)，隨機(jī)選擇一輛配送車輛，如選擇配送車輛k1，將該消費(fèi)者分配到該配送車輛，由配送車輛k1對(duì)其執(zhí)行配送任務(wù)，當(dāng)該配送車輛的容量和行駛路徑超過最大限制約束時(shí)，再次隨機(jī)選擇另一車輛k2，直至所有的消費(fèi)者均得到配送車輛對(duì)其執(zhí)行配送任務(wù)后，種群個(gè)體的初始化階段完成。

在嗅覺搜索階段，對(duì)于每個(gè)子種群，在當(dāng)前位置通過上述的遺傳進(jìn)化策略產(chǎn)生P個(gè)新的果蠅個(gè)體。如設(shè)子種群r在當(dāng)前位置Xc處通過遺傳進(jìn)化策略新產(chǎn)生的P1個(gè)果蠅個(gè)體(X1，X2，…，XP)且新個(gè)體中的最優(yōu)個(gè)體為Xb，那么在視覺搜索階段執(zhí)行果蠅個(gè)體的更新，如果目標(biāo)函數(shù)值f(Xb)

對(duì)于基于種群的智能優(yōu)化算法而言，種群中個(gè)體之間的交流協(xié)作可以擴(kuò)展解的搜索空間，加快收斂速度，從而提高算法的求解效率和求解精度，而文中設(shè)計(jì)的多種群的果蠅算法具有多個(gè)子種群，且各子種群之間分別進(jìn)行種群解的更新，缺乏種群之間的交流。因此，采用圖1所示的子種群交流機(jī)制，在果蠅算法的迭代過程中，每經(jīng)歷P次的迭代次數(shù)后，執(zhí)行多次種群之間的互動(dòng)交流，以此為子種群選擇性的引入外部種群或者最優(yōu)個(gè)體的優(yōu)良基因，進(jìn)而提高對(duì)問題最優(yōu)解的搜索能力。具體流程如圖4所示。

圖4 改進(jìn)果蠅優(yōu)化算法流程Fig. 4 Flow of improved fruit fly optimization algorithm

3 實(shí)例分析

為驗(yàn)證模型及IFFO算法的有效性，文中以某電商物流公司為例進(jìn)行數(shù)值仿真。該物流公司擁有4個(gè)配送中心，每輛配送車輛的最大載重量均為200 kg，每輛車的最大行駛距離均為500 km，每輛配送車的租賃成本為600元/輛，單位行駛里程的變動(dòng)成本為5元/km；燃料費(fèi)用為7.5元/L。4個(gè)配送站需要向48個(gè)消費(fèi)者提供配送服務(wù)，用歐氏距離表示任意點(diǎn)之間的距離，已知各消費(fèi)者的需求量，假設(shè)物流配送車輛從當(dāng)天的上午10:00出發(fā)執(zhí)行配送任務(wù)，并承諾在當(dāng)天的17:00之前將貨物送達(dá)，允許一定的延遲配送，但是最晚不能超過18:00，車輛的平均行駛速度為60 km/h。要求滿足降低物流配送成本并減少顧客的延時(shí)收貨時(shí)間，設(shè)計(jì)合理的調(diào)度和物流配送路線。其中配送站信息的坐標(biāo)(單位：km)分別為：(4.163，13.559)，(21.387，17.105)，(-36.118，49.097)(-31.201，0.235)，消費(fèi)者信息如表1所示。

表1 消費(fèi)者位置和需求量信息

3.1 IFFO算法求解效率

遺傳算法(Genetic algorithm, GA)在求解NP-Hard問題中具有快速收斂的求解優(yōu)勢(shì)，已成為求解車輛路徑規(guī)劃問題的重要方法。為了驗(yàn)證IFFO的有效性，將FFO、IFFO與GA三種算法求解結(jié)果進(jìn)行比較，繪制了三種算法得到的配送路線圖。其中，GA、FFO的種群數(shù)目設(shè)置為60，IFFO子種群數(shù)目設(shè)置為5，每個(gè)種群均有12個(gè)個(gè)體，GA的交叉率和變異率分別設(shè)置為0.9和0.1，IFFA每迭代10次進(jìn)行一次子種群之間的信息交互，三個(gè)算法的總迭代次數(shù)均為500次。三個(gè)算法各獨(dú)立運(yùn)行20次，取最優(yōu)計(jì)算結(jié)果如圖5、6所示。

圖5 FFO計(jì)算得到的配送路線Fig. 5 Distribution route obtained by FFO

圖6 不同算法計(jì)算得到的配送路線 Fig. 6 Distribution routes calculated by different algorithms

由圖5、6可以看出，GA和FFO運(yùn)行后均得到了8條配送路線，而文中設(shè)計(jì)的多種群果蠅算法IFFO運(yùn)行后得到了7條配送路線，即減少了一輛配送車的使用，也減少了配送路徑的長度，這進(jìn)一步說明了改進(jìn)的果蠅算法可以規(guī)劃出合理的物流配送路線。

為驗(yàn)證IFFO的實(shí)用性分別對(duì)FO、IFFO與GA三種算的收斂性進(jìn)行對(duì)比如圖7所示。

圖7 三種算法的收斂性對(duì)比Fig. 7 Convergence comparison of three algorithms

從圖7可以看出，在算法迭代的過程中，GA和FFO的求解結(jié)果和IFFO的求解結(jié)果差距不斷增大，說明文中提出的多種群機(jī)制對(duì)于物流配送車輛的路徑規(guī)劃可擴(kuò)大解的搜索范圍，提高解的尋優(yōu)速度和精度。

相比GA而言，GA計(jì)算得到的基本配送費(fèi)用為13 000元，燃料成本為13 000元，超時(shí)賠付費(fèi)用為2 000元。IFFO計(jì)算得到的基本配送費(fèi)用為10 358元、燃料成本為9 789元、超時(shí)賠付費(fèi)用1 622元，因此基本配送費(fèi)用，燃料成本，超時(shí)賠付費(fèi)用分別降低25.5%、32.8%、23.3%，相比基本的果蠅算法FFO計(jì)算得到的配送費(fèi)用為11 228元，燃料成本費(fèi)用為10 346元，因此IFFO計(jì)算得到的配送費(fèi)用、燃料成本分別降低8.4%、5.1%。因此結(jié)合上述得到的配送路線、燃料成本、配送費(fèi)用充分證明了改進(jìn)的果蠅算法對(duì)車輛的物流配送有著很大的提升效率。

3.2 ρ*的靈敏度

為了驗(yàn)證滿載時(shí)的燃料消耗率參數(shù)ρ*對(duì)燃料消耗成本的影響，以ρ0=1不變，分別設(shè)置ρ*為間隔0.5的不同數(shù)值，探索ρ*不同取值下的物流配送成本變動(dòng)情況如圖8所示。

從圖8可以看出，基本配送費(fèi)用和燃料成本總體趨勢(shì)均隨著滿載時(shí)的燃料消耗率ρ*的增加而增加，而當(dāng)ρ*=1.5時(shí)基本配送費(fèi)用得到了減少，這主要是因?yàn)樵讦?=1.5時(shí)，減少了一輛配送車輛的使用，使得基本配送費(fèi)用減少了600元，從而降低了基本配送費(fèi)用。

圖8 基本配送費(fèi)和燃料成本隨ρ*的變化趨勢(shì)Fig. 8 Trend of basic distribution fee fuel cost with ρ*

4 結(jié)束語

文中將配送車輛的行駛距離和載重量作為影響燃料消耗量的關(guān)鍵因素，建立了燃料消耗量模型和包含有多個(gè)配送站的終端配送路徑規(guī)劃模型，設(shè)計(jì)了問題的編碼方式。在路徑規(guī)劃方面，考慮到傳統(tǒng)果蠅算法易陷入局部最優(yōu)的不足，設(shè)計(jì)了多個(gè)果蠅種群同時(shí)進(jìn)化的多種群進(jìn)化機(jī)制，給出了子種群個(gè)體之間的交流互動(dòng)機(jī)制，應(yīng)用遺傳算法、果蠅算法和改進(jìn)后的果蠅算法對(duì)模型進(jìn)行求解，驗(yàn)證了改進(jìn)多種群果蠅算法的有效性，確保了在燃料消耗，配送成本這些外部條件因素的限制下，規(guī)劃出最合理的路徑。改進(jìn)的果蠅算法收斂速度得到明顯的提升，擴(kuò)大了搜索范圍，提高解的尋優(yōu)速度和精度。