基于混合煙花算法的兩級(jí)車輛路徑優(yōu)化研究

熊國(guó)文 張 敏,2 張訓(xùn)杰 張則強(qiáng),2

1(西南交通大學(xué)機(jī)械工程學(xué)院 四川 成都 610031)

2(西南交通大學(xué)軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室 四川 成都 610031)

0 引 言

城市交通機(jī)動(dòng)車數(shù)量增加、道路狀況、環(huán)境變化等因素,往往會(huì)引起車輛行駛緩慢,進(jìn)而造成交通擁堵[1-3]。而影響交通擁堵的因素隨著時(shí)間和空間的改變而動(dòng)態(tài)變化,即在不同時(shí)段,同一路段車輛速度不一定相同;在同一時(shí)段,不同路段車輛速度也不一定相同[4]。動(dòng)態(tài)交通狀態(tài)導(dǎo)致物流配送體系存在諸多不確定因素[5]。如遇到交通狀態(tài)惡劣,會(huì)直接影響物流配送的效率,進(jìn)而超出客戶時(shí)間窗,造成延時(shí)配送、成本增加、客戶滿意度下降等問(wèn)題。因此,如何根據(jù)動(dòng)態(tài)交通狀態(tài)規(guī)劃高效的物流配送車輛路徑,是物流企業(yè)亟待解決的問(wèn)題。

基于動(dòng)態(tài)交通狀態(tài)的物流配送車輛路徑問(wèn)題是車輛路徑問(wèn)題的延伸,旨在動(dòng)態(tài)的交通狀態(tài)下規(guī)劃出最佳的物流配送方案。其中如道路條件、交通流量、意外事故、天氣情況等動(dòng)態(tài)交通信息,對(duì)動(dòng)態(tài)車輛路徑問(wèn)題的解決起著非常重要的作用[6]。近年來(lái),隨著通信和信息技術(shù)發(fā)展,動(dòng)態(tài)交通信息可通過(guò)相應(yīng)的平臺(tái)快速有效地獲取和處理[7],為研究動(dòng)態(tài)車輛路徑規(guī)劃提供了先決條件。如Xiao等[8]認(rèn)為車輛行駛速度主要由交通和路況決定,首先從相關(guān)信息系統(tǒng)獲得交通數(shù)據(jù)計(jì)算車輛在各路段的平均速度,在此基礎(chǔ)上建立以溫室氣體排放量最小為目標(biāo)函數(shù)的混合整數(shù)規(guī)劃模型。針對(duì)動(dòng)態(tài)交通影響物流配送效率,進(jìn)而超出客戶時(shí)間窗,Ghani等[9]研究了交通擁擠導(dǎo)致不必要的時(shí)間延誤,從而造成客戶損失。同時(shí),相關(guān)學(xué)者研究了動(dòng)態(tài)交通物流配送車輛的異構(gòu)問(wèn)題,即不同的車輛載重能力、行駛里程等約束不同,如張傳琪等[10]將路網(wǎng)擁擠狀態(tài)沿時(shí)間軸展開(kāi),構(gòu)建了考慮服務(wù)途中動(dòng)態(tài)擁擠的多車型車輛路徑模型,設(shè)計(jì)了求解該模型的改進(jìn)遺傳算法。上述文獻(xiàn)皆對(duì)動(dòng)態(tài)交通狀態(tài)下的車輛路徑問(wèn)題進(jìn)行了研究并取得了可喜的成果,但未考慮客戶之間可能存在多條連通路線以及計(jì)算車輛在各個(gè)路段上的理論行駛時(shí)間可能與實(shí)際行駛時(shí)間相差較大等問(wèn)題?；诖?李順勇等[11]針對(duì)城市路網(wǎng)中的兩節(jié)點(diǎn)之間具有多條連通道路的特性研究動(dòng)態(tài)車輛路徑規(guī)劃問(wèn)題,建立了多通路時(shí)變網(wǎng)絡(luò)下的低碳車輛路徑優(yōu)化模型。Alinaghian等[12]通過(guò)考慮車輛裝載量、速度、道路梯度和城市交通等因素,分析了多路徑選擇對(duì)時(shí)變車輛路徑問(wèn)題的重要性,提出了一種基于高斯螢火蟲(chóng)算法的改進(jìn)算法,以找到油耗最小的最優(yōu)路徑。

目前,大多數(shù)學(xué)者的研究主要集中在單級(jí)物流配送車輛路徑優(yōu)化上,但在實(shí)際物流配送中,為了避免大型車進(jìn)入城市造成污染,很多城市采取車輛限行政策,兩級(jí)物流配送模式廣泛應(yīng)用于各種場(chǎng)景下的商品配送[13-14],即商品先由大型車運(yùn)輸至各個(gè)中轉(zhuǎn)站,再由小型車運(yùn)輸至該中轉(zhuǎn)站所服務(wù)的各個(gè)需求點(diǎn)[15-17]。若兩級(jí)物流配送車輛路徑的優(yōu)化仍然采用優(yōu)化單級(jí)物流配送車輛路徑的方法,自上而下優(yōu)化每一級(jí)物流配送車輛路徑,則無(wú)法實(shí)現(xiàn)兩級(jí)物流配送車輛路徑的整體優(yōu)化。近年來(lái),越來(lái)越多的學(xué)者開(kāi)始從事兩級(jí)車輛路徑問(wèn)題(Two-echelon Vehicle Routing Problem,2e-VRP)的研究。曾正洋等[18]先將貨物從中心倉(cāng)庫(kù)配送至城市外圍的中轉(zhuǎn)站,再轉(zhuǎn)運(yùn)至需求點(diǎn),同時(shí),考慮到將部分或全部運(yùn)輸任務(wù)分配給第三方物流公司,第一級(jí)車輛在完成配送任務(wù)后無(wú)須返回中心倉(cāng)庫(kù),或者必須原路返回,構(gòu)建了開(kāi)閉混合式兩級(jí)車輛路徑問(wèn)題的數(shù)學(xué)模型。張漢鵬等[19]研究應(yīng)急物資配送中的兩級(jí)車輛路徑?jīng)Q策策略與應(yīng)急物資配送績(jī)效問(wèn)題。但兩級(jí)車輛路徑問(wèn)題的研究中較少考慮關(guān)于物流節(jié)點(diǎn)之間有多條連通路線、動(dòng)態(tài)的交通等現(xiàn)實(shí)物流配送情況。

自兩級(jí)車輛路徑提出以來(lái),學(xué)者和專家提出了不同的求解算法。Wang等[20]針對(duì)具有隨機(jī)需求的兩級(jí)容量車輛路徑問(wèn)題,提出了一種基于遺傳算法新的求解方法。Li等[21]考慮碳排放量,研究?jī)杉?jí)長(zhǎng)途運(yùn)輸系統(tǒng)中的車輛路徑優(yōu)化問(wèn)題,提出了一種改進(jìn)的局部搜索階段的Clarke和Wright節(jié)約啟發(fā)式算法(CW),有效降低二氧化碳的排放量。Hemmelmayr等[22]針對(duì)兩級(jí)車輛路徑問(wèn)題和位置路徑問(wèn)題,提出了一種自適應(yīng)大鄰域搜索啟發(fā)式算法。胡喬宇等[23]研究了客戶需求隨機(jī)的兩級(jí)車輛路徑問(wèn)題,設(shè)計(jì)了一種基于蒙特卡洛仿真優(yōu)化方法,將仿真過(guò)程嵌入到啟發(fā)式算法的鄰域搜索過(guò)程進(jìn)行求解。Belgin等[24]研究了兩級(jí)同時(shí)取送車輛路徑問(wèn)題,提出了一種基于變鄰域下降和局部搜索的混合啟發(fā)式算法。由于兩級(jí)車輛路徑屬于NP-hard問(wèn)題,求解比較復(fù)雜,難以同時(shí)確保求解速度和求解質(zhì)量。為了解決此問(wèn)題,本文結(jié)合煙花算法和遺傳算法各自的優(yōu)點(diǎn),提出一種混合煙花算法,以提高收斂速度、降低迭代次數(shù)達(dá)到同時(shí)確保求解速度和求解質(zhì)量。

鑒于上述有關(guān)兩級(jí)動(dòng)態(tài)物流配送車輛路徑以及求解方法研究的不足,結(jié)合物流配送的實(shí)際情況,從車流量大小、道路施工情況、天氣惡劣程度等動(dòng)態(tài)交通因素分析對(duì)車速的實(shí)時(shí)影響,以車輛載重為約束條件,同時(shí)考慮客戶時(shí)間窗,配送時(shí)間超出客戶時(shí)間窗則產(chǎn)生懲罰成本,建立以物流配送總成本最小為優(yōu)化目標(biāo)的兩級(jí)動(dòng)態(tài)物流配送車輛路徑優(yōu)化模型。針對(duì)煙花算法收斂速度慢的缺陷,用插入法生成較優(yōu)的初始種群,引入交叉操作提出一種新的混合煙花算法。通過(guò)計(jì)算兩級(jí)車輛路徑問(wèn)題標(biāo)準(zhǔn)算例,與遺傳算法和現(xiàn)有文獻(xiàn)運(yùn)算結(jié)果作對(duì)比,驗(yàn)證了算法的有效性和高效性。

1 問(wèn)題與建模

1.1 問(wèn)題描述與假設(shè)

兩級(jí)物流配送系統(tǒng)包括一個(gè)配送中心、若干中轉(zhuǎn)站和若干客戶,兩級(jí)物流配送的網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示,D點(diǎn)代表配送中心,S點(diǎn)代表中轉(zhuǎn)站,C點(diǎn)代表客戶點(diǎn)?？蛻羲枭唐肥紫扔纱笮蛙噺呐渌椭行倪\(yùn)輸至各個(gè)中轉(zhuǎn)站,然后由小型車將商品從中轉(zhuǎn)站運(yùn)輸至各個(gè)需求點(diǎn),要求其配送總時(shí)間在客戶能接受的范圍內(nèi),否則會(huì)產(chǎn)生較大的懲罰成本。其中大型車配送階段稱為第一級(jí)物流配送,由于中轉(zhuǎn)站的需求可能大于車輛容量,因此,第一級(jí)物流配送屬于需求可拆分配送,如圖1中實(shí)線箭頭所示;小型車配送階段稱為第二級(jí)物流配送,此階段需求不可拆分配送,如圖1中虛線箭頭所示。為進(jìn)一步切合實(shí)際物流配送,本文考慮動(dòng)態(tài)交通對(duì)物流配送的影響,以及各個(gè)節(jié)點(diǎn)之間有多條交通狀態(tài)不一致的連通道路,使該問(wèn)題更加符合實(shí)際物流配送。

圖1 2e-VRP網(wǎng)絡(luò)結(jié)構(gòu)

綜合考慮帶時(shí)間窗的兩級(jí)動(dòng)態(tài)物流配送特點(diǎn),做出如下假設(shè)：(1) 每條配送線路上的客戶需求量之和不能超過(guò)配送車輛的最大載重量Q1和Q2;(2) 第一級(jí)中轉(zhuǎn)站貨物可拆分配送,第二級(jí)需求點(diǎn)貨物不可拆分配送,每級(jí)物流配送使用同一種車型;(3) 每個(gè)客戶的需求數(shù)量必須得到滿足且只能由一輛車配送;(4) 每輛車從配送中心或中轉(zhuǎn)站出發(fā),完成配送任務(wù)后返回到相應(yīng)的配送中心或中轉(zhuǎn)站;(5) 每項(xiàng)配送任務(wù)必須在客戶要求的時(shí)間范圍內(nèi)完成,否則就會(huì)產(chǎn)生高昂的懲罰費(fèi)用;(6) 車輛一旦確認(rèn)了所服務(wù)的客戶之后便不能再更改。

1.2 符號(hào)說(shuō)明

根據(jù)以上假設(shè),構(gòu)建混合整數(shù)規(guī)劃模型,設(shè)定模型參數(shù)與決策變量。

D：配送中心集合;

S：中轉(zhuǎn)站集合;

P：需求點(diǎn)集合;

C：總成本;

c1：一級(jí)車輛單位距離運(yùn)輸成本;

c2：二級(jí)車輛單位距離運(yùn)輸成本;

c3：時(shí)間懲罰成本;

dij：節(jié)點(diǎn)i到節(jié)點(diǎn)j之間的距離;

Q1：一級(jí)車輛最大載重;

Q2：二級(jí)車輛最大載重;

U：一級(jí)車輛集合;

K：二級(jí)車輛集合;

qi：需求點(diǎn)i的需求量;

v1：一級(jí)車輛最大行駛速度;

v2：二級(jí)車輛最大行駛速度;

v1ij：一級(jí)車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的實(shí)際速度;

M：一個(gè)足夠大的數(shù);

Ti：客戶i能接受的最長(zhǎng)配送時(shí)間;

es：中轉(zhuǎn)站s的需求量;

Tsu：一級(jí)車輛u達(dá)到中轉(zhuǎn)站s的時(shí)間;

Tik：二級(jí)車輛k達(dá)到需求點(diǎn)i的時(shí)間;

ti：到達(dá)客戶i的時(shí)間;

Zsu：一級(jí)車輛u給中轉(zhuǎn)站s的運(yùn)輸量;

riju：一級(jí)車輛u訪問(wèn)中轉(zhuǎn)站i后訪問(wèn)j,riju∈{0,1};

xijk：二級(jí)車輛k訪問(wèn)需求點(diǎn)i后訪問(wèn)j,xijk∈{0,1};

yik：需求點(diǎn)i的需求量由二級(jí)車輛k配送,yik∈{0,1}。

1.3 數(shù)學(xué)模型

用具有代表性的車流量指數(shù)、天氣惡劣指數(shù)、道路施工指數(shù)刻畫交通狀態(tài),參數(shù)α1ij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的車流量指數(shù),α2ij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的天氣惡劣指數(shù),α3ij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的道路施工指數(shù)。一級(jí)與二級(jí)車輛從節(jié)點(diǎn)i到節(jié)點(diǎn)j的實(shí)際速度由式(1)和式(2)求得。

v1ij=α1ij×α2ij×α3ij×v1

(1)

v2ij=α1ij×α2ij×α3ij×v2

(2)

一級(jí)物流配送車輛路徑成本設(shè)為f1,則：

(3)

二級(jí)物流配送車輛路徑成本設(shè)為f2,則：

(4)

配送延時(shí)懲罰成本設(shè)為f3,則：

(5)

目標(biāo)函數(shù)：minC=λ1f1+λ2f2+λ3f3

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

tiu+dis/v1is+M×(1-risu)≥tsui∈D∪S,s∈S,u∈U

(17)

tiu+dis/v1is-M×(1-risu)≤tsui∈D∪S,s∈S,u∈U

(18)

tik+dij/v2ij+max(tsu)+M×(1-xijk)≥tju

s∈S,i∈S∪P,j∈P,k∈K

(19)

tik+dij/v2ij+max(tsu)-M×(1-xijk)≤tju

s∈S,i∈S∪P,j∈P,k∈K

(20)

ti=maxtik

(21)

上述模型中式(6)為目標(biāo)函數(shù),式(7)表示一級(jí)車輛不能超載;式(8)表示二級(jí)車輛不能超載;式(9-10)表示一級(jí)車輛路徑連貫;式(11)和式(12)表示每個(gè)需求點(diǎn)由一輛二級(jí)車服務(wù)一次;式(13)保證中轉(zhuǎn)站的需求量配送完成,式(14)表示每輛車從配送中心出發(fā),經(jīng)過(guò)若干需求點(diǎn)后回到配送中心;式(15)表示每輛車從中轉(zhuǎn)站出發(fā),經(jīng)過(guò)若干需求點(diǎn)后回到出發(fā)的中轉(zhuǎn)站;式(16)求出中轉(zhuǎn)的貨物需求量;式(17)-式(21)求貨物到達(dá)需求點(diǎn)的時(shí)間。

2 算法設(shè)計(jì)

2.1 解的編碼

本文采用實(shí)數(shù)編碼,以多行序列形式表示上述問(wèn)題的解,如圖2所示,正方形代表配送中心,三角形代表中轉(zhuǎn)站,圓形代表需求點(diǎn)。圖2中解的含義是：配送中心需要兩輛一級(jí)車為兩個(gè)中轉(zhuǎn)站配送貨物,其路線是D-S1-S2-D和D-S2-D;中轉(zhuǎn)站1需要兩輛二級(jí)車為5個(gè)需求點(diǎn)配送貨物,其路徑是S1-8-5-S1和S1-3-7-6-S1;中轉(zhuǎn)站2需要一輛二級(jí)車為三個(gè)需求點(diǎn)配送貨物,其路徑是：S2-2-1-4-S2。

圖2 解的表示方法

2.2 插入算法

插入算法由Mole等提出[25],該算法的基本思想是將需求點(diǎn)依次插入到車輛中,每插入一個(gè)需求點(diǎn)都使得總成本增量最小,以此生成較好的解。為了增加初始種群的多樣性,本文從需求點(diǎn)所有可插入的位置中,挑選成本增量較小的幾個(gè)位置以概率Pi選擇其中一個(gè)位置插入需求點(diǎn)。Pi由式(22)計(jì)算,其中：Cost_add(i)代表的是第i個(gè)位置的成本增量;I代表位置集合,為了避免選擇成本增量較大的位置,對(duì)位置集合I設(shè)了限制條件,即當(dāng)需求點(diǎn)可插入位置數(shù)量小于a時(shí),位置集合I就是所有需求點(diǎn)可插入的位置集合,否則,位置集合I指成本增量從小到大的前a個(gè)對(duì)應(yīng)位置集合,a的值可視情況而定,a越大,則初始解的多樣性越好,但初始解的質(zhì)量可能也會(huì)下降。

(22)

具體步驟如下：首先新建車輛,選擇待插入的需求點(diǎn),判斷是否需要新建車輛,若需要?jiǎng)t新建車輛,否則選擇使得成本增量盡可能小的位置插入需求點(diǎn),判斷需求點(diǎn)是否插入完畢,沒(méi)有則繼續(xù)選擇待插入的需求點(diǎn)繼續(xù)插入,需求點(diǎn)插入完畢則生成個(gè)體。插入算法偽代碼如下：

1V=[V1=[],V1_weight=0],k=2

2 fori=1：n

3point=Pi

4 ifVi_weight+q[point]>Q,i∈[1,2,…,k-1]

5V=[Vk=[],Vk_weight=0],k=k+1

6 forj=1：i×(k-1)

7cost_add(j)=0

8cost_add(j)=cost(V[j],point)+

cost(V[j+1],point)-cost(V[j],V[j-1])

9l=select(cost_add)

10m=vehicle(l)

11V=insert(l,point),

Vm_weight=Vm_weight+q[point]

12 Return個(gè)體

在上述偽代碼中,V代表車輛集合,其中Vk代表的是第k輛車所服務(wù)的客戶順序,Vk_weight是第k輛車的載貨量;P代表的是客戶點(diǎn)集合,Cost_add(j)代表的是第j個(gè)位置的成本增量,Cost(V(j),Point)則是代表第j個(gè)位置對(duì)應(yīng)的客戶點(diǎn)Vh(j)與Point之間的成本,Select(Cost_add)選擇成本增量盡可能小對(duì)應(yīng)的插入位置,vehicle(l)代表位置l所在車輛,insert(l,Point)將客戶點(diǎn)Point插入到第l個(gè)位置。經(jīng)過(guò)插入算法可以得到總配送成本盡可能小的初始種群,同時(shí),由于選擇插入的位置不一定是成本增量最小的位置,使得初始種群多樣化。

2.3 爆炸操作

首先通過(guò)式(23)計(jì)算煙花個(gè)體爆炸的火花數(shù),然后針對(duì)個(gè)體的每輛車采用爆炸操作產(chǎn)生火花,爆炸操作如圖3所示,隨機(jī)選擇兩個(gè)位置,交換其對(duì)應(yīng)位置的需求點(diǎn)編號(hào),計(jì)算出爆炸后新車輛的配送費(fèi)用,用配送費(fèi)用最小的新車輛代替原來(lái)的車輛。

圖3 爆炸過(guò)程

(23)

式中：Si為第i個(gè)個(gè)體產(chǎn)生的火花數(shù);m是最大火花數(shù)量;F(i)是第i個(gè)個(gè)體的適應(yīng)度值;Fmax=max{F(i)};ε為一個(gè)極小的常數(shù),避免分母為零。同時(shí),為了限制火花數(shù)量過(guò)多或過(guò)少,設(shè)定如下的產(chǎn)生火花數(shù)量的限制公式：

(24)

式中：round()為取整函數(shù);a和b為給定的常數(shù)。

2.4 車輛交叉

首先求出群體最優(yōu)解,然后用群體最優(yōu)解中車輛的某一段需求點(diǎn)序列代替?zhèn)€體中的某一段相同長(zhǎng)度的需求點(diǎn)序列,最后將重復(fù)的需求點(diǎn)刪除,并且將沒(méi)有被服務(wù)的需求點(diǎn)用插入算法重新插入到車輛中,形成新的可行解。車輛交叉操作如圖4所示。

圖4 交叉操作

2.5 算法流程

本文所提混合煙花算法,融入了插入法和交叉操作,保證了算法的全局搜索與快速收斂性能,首先采用插入算法生成較好的初始種群;其次計(jì)算適應(yīng)度值并找出最優(yōu)初始解;然后引入遺傳算法中的交叉算子,使得煙花個(gè)體與最優(yōu)煙花個(gè)體執(zhí)行交叉操作;再利用煙花算法的爆炸算子產(chǎn)生爆炸火花,提高算法的尋優(yōu)能力;最后采用精英策略保留較好的煙花個(gè)體進(jìn)入下一次迭代。HFWA流程如圖5所示,其中Gen為迭代次數(shù)。

圖5 算法流程

3 算法驗(yàn)證

本文使用2e-VRP標(biāo)準(zhǔn)算例對(duì)本文提出的HFWA進(jìn)行可行性驗(yàn)證,標(biāo)準(zhǔn)算例以車輛行駛路徑最短和使用車輛數(shù)最小為目標(biāo)函數(shù),車輛載重等為約束條件。標(biāo)準(zhǔn)算例數(shù)據(jù)來(lái)源于https：//www.univie.ac.at/prolog/research/TwoEVRP/。并將HFWA計(jì)算結(jié)果與官網(wǎng)給出的最優(yōu)結(jié)果、GA、Marinelli[26]和Jie等[27]求解結(jié)果進(jìn)行比較。其計(jì)算結(jié)果為使用Inter(R) Core(TM)i3-6100CPU@3.70 GHz處理器,仿真軟件采用MATLAB 2010b。兩種算法的種群規(guī)模都設(shè)置為200,HFWA迭代次數(shù)為50,GA迭代次數(shù)為500,計(jì)算10次的平均結(jié)果見(jiàn)表1。

對(duì)比表1中27個(gè)標(biāo)準(zhǔn)算例解的質(zhì)量可見(jiàn),GA僅能求出10個(gè)標(biāo)準(zhǔn)算例的最優(yōu)解,其余結(jié)果與最優(yōu)解相差較大。而HFWA有24個(gè)標(biāo)準(zhǔn)算例均能求出最優(yōu)解,其余3個(gè)算例與現(xiàn)有最優(yōu)解也相差較少。對(duì)比求解效率可見(jiàn),由于HFWA使用了插入算法,設(shè)計(jì)較為復(fù)雜,提高了收斂速度,以降低迭代次數(shù)為代價(jià)提高求解效率,相較于GA在求解效率上快了1倍。而相較于文獻(xiàn)[26]和文獻(xiàn)[27]在求解質(zhì)量與效率上同樣具有優(yōu)勢(shì)。綜上,證明了HFWA的可行性與良好的求解性能。

4 實(shí) 驗(yàn)

本文在標(biāo)準(zhǔn)算例(Set2a_E_n33_k4_s1_9)的實(shí)驗(yàn)數(shù)據(jù)基礎(chǔ)上,通過(guò)隨機(jī)生成客戶點(diǎn)的時(shí)間窗演化為本文的實(shí)驗(yàn)數(shù)據(jù)(見(jiàn)表2)。隨機(jī)生成了各個(gè)路段在各時(shí)刻的車流量指數(shù)、天氣惡劣指數(shù)、道路施工指數(shù)(如表3所示,由于數(shù)據(jù)量太大,表3中僅僅列出前五個(gè)客戶路段之間在某時(shí)刻的刻畫交通狀態(tài)的各項(xiàng)指數(shù))。若某兩個(gè)客戶點(diǎn)之間的交通狀態(tài)比較惡劣,從而使得物流配送成本急劇上漲,則會(huì)重新選擇一條交通狀況較好,路徑不劇增的新路線,使得物流配送總成本變化幅度較小。

表2 實(shí)驗(yàn)數(shù)據(jù)

表3 交通狀態(tài)指數(shù)

在表2中序號(hào)1至序號(hào)32為需要服務(wù)的客戶點(diǎn),客戶點(diǎn)1和9被選擇為中轉(zhuǎn)站,為方便編碼,將中轉(zhuǎn)重新設(shè)置為33和34,35為配送中心。一級(jí)配送網(wǎng)絡(luò)中使用載重量為20 000的大型車,二級(jí)配送網(wǎng)絡(luò)中使用載重量為8 000的小型車。

為了說(shuō)明在優(yōu)化物流配送時(shí),考慮交通狀態(tài)的必要性,本文將不考慮交通狀態(tài)條件下優(yōu)化的車輛路徑代入交通狀態(tài)條件下得到的結(jié)果,與考慮交通狀態(tài)下的優(yōu)化結(jié)果進(jìn)行對(duì)比分析。其車輛單位距離成本設(shè)置為1,延時(shí)懲罰成本設(shè)置為2,算法參數(shù)與求解標(biāo)準(zhǔn)算例一致。計(jì)算結(jié)果見(jiàn)表4,HFWA和GA優(yōu)化后的兩級(jí)車輛路徑見(jiàn)圖6至圖9,其中實(shí)線表示第一級(jí)車輛路徑,虛線表示第二級(jí)車輛路徑。

表4 實(shí)驗(yàn)計(jì)算結(jié)果

圖6 HFWA不考慮交通狀態(tài)的兩級(jí)車輛路徑

圖7 HFWA考慮交通狀態(tài)的兩級(jí)車輛路徑

圖8 GA不考慮交通狀態(tài)的兩級(jí)車輛路徑

圖9 GA考慮交通狀態(tài)的兩級(jí)車輛路徑

從表4中可以得出,HFWA考慮交通狀態(tài)下的優(yōu)化結(jié)果,在靜態(tài)交通下比不考慮交通狀態(tài)條件優(yōu)化結(jié)果代入到考慮交通狀態(tài)后得到的總成本減少了17.8%,在動(dòng)態(tài)交通狀態(tài)下減少了10.5%,總成本平均減少了14.2%,說(shuō)明了優(yōu)化物流配送時(shí)考慮交通條件的必要性。而GA優(yōu)化性能相較于HFWA相對(duì)較差。同時(shí),考慮了交通狀態(tài)在運(yùn)輸總成本、路徑成本、延時(shí)成本相較于不考慮交通狀態(tài)都有所增加,動(dòng)態(tài)交通相較于靜態(tài)交通,各個(gè)成本也有所變化,這是因?yàn)樵谖锪髋渌瓦^(guò)程中,交通狀態(tài)變惡劣、不同道路交通狀態(tài)在不同時(shí)刻不一致、物流節(jié)點(diǎn)間的路徑選擇策略緣故,使得車輛速度緩慢,車輛路徑增加,配送時(shí)間延長(zhǎng),客戶滿意度下降。靜態(tài)路徑成本和動(dòng)態(tài)路徑成本不同則說(shuō)明了在貨物裝車后的實(shí)際配送過(guò)程中,因交通狀態(tài)的時(shí)刻變化,雖然車輛所服務(wù)的客戶不再改變,但所行走的路線卻根據(jù)動(dòng)態(tài)交通狀態(tài)做出了相應(yīng)的變化以降低配送成本。從圖6到圖9也可以看出是否考慮交通對(duì)車輛路徑也有所影響。在不考慮交通狀態(tài)條件下,雖然對(duì)于延時(shí)配送成本,HFWA求解結(jié)果略高于GA求解結(jié)果,但是對(duì)于總成本以及路徑成本,HFWA求解結(jié)果都遠(yuǎn)遠(yuǎn)低于GA求解結(jié)果。

由于車流量和道路施工情況在每個(gè)需求點(diǎn)之間不同,分析比較困難,而天氣狀態(tài)在一段時(shí)間內(nèi),各個(gè)需求點(diǎn)之間都相差有限。為了研究交通狀態(tài)的影響因素對(duì)二級(jí)物流配送成本的影響,本文首先隨機(jī)生成各個(gè)需求點(diǎn)之間的各個(gè)時(shí)刻的車流量指數(shù)和道路施工指數(shù),將其固定不變,以天氣狀態(tài)指數(shù)為變量分析天氣狀態(tài)對(duì)配送成本、車輛行駛路徑和延時(shí)懲罰成本情況的影響,分析計(jì)算結(jié)果如圖10、圖11和圖12所示。

圖11 天氣情況對(duì)車輛行駛路徑的影響

圖12 天氣情況對(duì)延時(shí)配送成本的影響

分析圖10、圖11、圖12可知,在車流量指數(shù)和道路施工指數(shù)已知不變的情況下,運(yùn)輸總成本和延時(shí)配送成本隨著天氣的好轉(zhuǎn)而降低,車輛行駛路徑的長(zhǎng)度總體上也隨著天氣的好轉(zhuǎn)而縮短。在實(shí)際中,除了天氣,考慮車流量以及道路施工等影響因素會(huì)更加符合實(shí)際物流配送,說(shuō)明本文研究交通狀態(tài)對(duì)運(yùn)輸成本的影響符合實(shí)際物流配送過(guò)程,可以在動(dòng)態(tài)交通狀態(tài)下有效降低物流配送成本,具有實(shí)際的應(yīng)用價(jià)值,為動(dòng)態(tài)二級(jí)物流配送路徑優(yōu)化提供了新思路。

5 結(jié) 語(yǔ)

本文考慮了車流量、道路施工和天氣狀態(tài)對(duì)交通狀態(tài)的影響,將動(dòng)態(tài)的交通狀態(tài)和時(shí)間窗同時(shí)引入到兩級(jí)物流配送中,建立了帶時(shí)間窗的動(dòng)態(tài)兩級(jí)物流配送車輛路徑優(yōu)化數(shù)學(xué)模型,設(shè)計(jì)了求解該復(fù)雜問(wèn)題的混合煙花算法。并利用混合煙花算法和遺傳算法計(jì)算2e-VRP標(biāo)準(zhǔn)算例,并與現(xiàn)有文獻(xiàn)所提算法對(duì)比說(shuō)明本文算法的可行性和高效性。在標(biāo)準(zhǔn)算例的基礎(chǔ)上構(gòu)造新的具有時(shí)間窗的實(shí)驗(yàn)數(shù)據(jù),然后用兩種算法計(jì)算帶時(shí)間窗的動(dòng)態(tài)兩級(jí)物流配送車輛路徑規(guī)劃數(shù)學(xué)模型,結(jié)果表明混合煙花算法收斂速度快,迭代次數(shù)少,且求解質(zhì)量和求解效率均優(yōu)于遺傳算法。最后,分析了交通狀態(tài)的影響因素對(duì)車輛路徑以及配送成本的影響;證明了在實(shí)際物流配送車輛路徑規(guī)劃過(guò)程中,考慮動(dòng)態(tài)交通的優(yōu)化結(jié)果更加符合實(shí)際物流配送過(guò)程,具有實(shí)際應(yīng)用價(jià)值,且算法設(shè)計(jì)合理,為求解動(dòng)態(tài)交通的兩級(jí)物流配送車輛路徑問(wèn)題提供了新方法。

本文僅僅考慮了一部分影響交通狀態(tài)的因素,在實(shí)際的物流配送過(guò)程中,還存在車輛限行政策、客戶需求的動(dòng)態(tài)變化等因素,這值得在后續(xù)的研究中進(jìn)一步探討。