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

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

0 引 言

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

1 模型構(gòu)建

1.1 燃料消耗量與成本模型

Sahin等[7]指出，載荷20 t的卡車滿載行駛時平均每1 000 km的燃料消耗成本占據(jù)了物流總成本的60%?；谏鲜鲅芯?，構(gòu)建了行駛里程與燃料消耗量的模型為

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

ρ0——車輛空載時的燃料消耗率；

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

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

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

ρij=ρ(mijk)，

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

燃料消耗成本可以表示為

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

dij——兩個消費者之間的歐氏距離。

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

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

式中：Chc——每輛車的租賃成本費用；

Cvc——車輛單位行駛里程的變動成本；

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

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

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

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

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

N——消費者和配送中心集合，N=C∪D；

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

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

dij——任意兩點i和j之間的歐氏距離；

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

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

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

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

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

Ti——配送中心給消費者i的最晚收貨時間；

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

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

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

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

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

2 多種群的改進果蠅算法

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

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則表示配送站下標。在具體編碼階段，首先將MDVRP轉(zhuǎn)化為多個VRP進行并行求解，然后根據(jù)油耗、成本等外部因素，為每一位客戶分配配送車輛，設(shè)計配送車輛的行駛路線。具體解碼過程：(1)根據(jù)果蠅個體編碼，得到車輛的具體方位與排列順序。(2)根據(jù)車輛的排列順序，得到運輸任務(wù)的序列T=(t1,t2,…,tk)。(3)將運輸任務(wù)序列按照油耗配送時間等約束條件分配給W個運輸車輛。(4)得到W個運輸車輛根據(jù)建模條件的約束，自動劃分每個車輛應(yīng)到哪個目標點合理。(5)根據(jù)改進果蠅優(yōu)化算法進行合理路徑規(guī)劃。

2.2 多種群方法

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

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

2.3 個體的遺傳進化策略

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

圖2 交叉算子Fig. 2 Crossover operator

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

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

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

2.4 算法步驟

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

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

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

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

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

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

3 實例分析

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

表1 消費者位置和需求量信息

3.1 IFFO算法求解效率

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

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

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

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

為驗證IFFO的實用性分別對FO、IFFO與GA三種算的收斂性進行對比如圖7所示。

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

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

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

3.2 ρ*的靈敏度

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

從圖8可以看出，基本配送費用和燃料成本總體趨勢均隨著滿載時的燃料消耗率ρ*的增加而增加，而當ρ*=1.5時基本配送費用得到了減少，這主要是因為在ρ*=1.5時，減少了一輛配送車輛的使用，使得基本配送費用減少了600元，從而降低了基本配送費用。

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

4 結(jié)束語

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