基于深度卷積神經(jīng)網(wǎng)絡(luò)的電力物資運(yùn)輸車(chē)輛調(diào)度優(yōu)化算法研究

宮寅林,王民濤

(1.國(guó)網(wǎng)內(nèi)蒙古東部電力有限公司物資分公司,內(nèi)蒙古 呼和浩特 010090) (2.國(guó)網(wǎng)內(nèi)蒙古東部電力有限公司,內(nèi)蒙古 呼和浩特 010090)

深度卷積神經(jīng)網(wǎng)絡(luò)是基于人工神經(jīng)網(wǎng)絡(luò)逐漸演變而來(lái)的[1],其通過(guò)神經(jīng)元處理輸入信號(hào)來(lái)判斷是否進(jìn)行下一步響應(yīng)[2-3]。以此為基礎(chǔ)構(gòu)建神經(jīng)網(wǎng)絡(luò)數(shù)學(xué)模型,通過(guò)不斷卷積運(yùn)算保證深度卷積神經(jīng)網(wǎng)絡(luò)的處理結(jié)果更加完善,且擬合能力更強(qiáng)。

電力物資的配送根據(jù)不同客戶(hù)的需求特點(diǎn),通過(guò)高效有序方式實(shí)現(xiàn)[4]。隨著社會(huì)的高速發(fā)展,電網(wǎng)企業(yè)項(xiàng)目類(lèi)型不斷增多,各電力公司所需的物資也逐漸增多,而當(dāng)前許多物資配送調(diào)度方法無(wú)法滿(mǎn)足物資的整合與配送要求,在配送過(guò)程中通常難以選擇經(jīng)濟(jì)合理的配送方式與配送路線(xiàn)[5],導(dǎo)致電力企業(yè)在物資配送方面的開(kāi)銷(xiāo)逐漸加大,因此研究一種合理有效的配送車(chē)輛調(diào)度方法就顯得極為重要。許多學(xué)者對(duì)此進(jìn)行了研究,如盧錦川[6]進(jìn)行了基于擾動(dòng)收縮粒子群算法的物聯(lián)網(wǎng)配送車(chē)輛調(diào)度研究,但在進(jìn)行車(chē)輛調(diào)度時(shí)僅考慮了運(yùn)輸路徑,未能有效節(jié)約配送時(shí)間;賀體龍等[7]采用改進(jìn)飛蛾撲火算法獲得車(chē)輛調(diào)度方案,但在進(jìn)行配送時(shí)所需油耗更大,并不能合理節(jié)約開(kāi)銷(xiāo)。

本文提出基于深度卷積神經(jīng)網(wǎng)絡(luò)的電力物資運(yùn)輸車(chē)輛調(diào)度優(yōu)化算法,通過(guò)Hopfield神經(jīng)網(wǎng)絡(luò)處理電力物資運(yùn)輸車(chē)輛調(diào)度問(wèn)題,并利用禁忌搜索算法對(duì)調(diào)度模型進(jìn)行優(yōu)化。

1 電力物資運(yùn)輸車(chē)輛調(diào)度優(yōu)化算法

1.1 Hopfield神經(jīng)網(wǎng)絡(luò)基本原理

選用Hopfield神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)深度卷積,該網(wǎng)絡(luò)是一種反饋型網(wǎng)絡(luò)[8-9]。神經(jīng)網(wǎng)絡(luò)能量函數(shù)為:

(1)

式中:E為能量函數(shù),Tij為神經(jīng)元i與j之間的連接權(quán)值,Ii為神經(jīng)元i的輸入閾值,Vi、Vj分別為神經(jīng)元i與j的輸出值。

在一定條件下,只要能量函數(shù)沿著網(wǎng)絡(luò)的解遞減,能量函數(shù)的導(dǎo)數(shù)為零時(shí)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)。通過(guò)Hopfield神經(jīng)網(wǎng)絡(luò),可有效實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的深度卷積。

1.2 電力物資運(yùn)輸車(chē)輛調(diào)度

為研究電力物資運(yùn)輸車(chē)輛調(diào)度優(yōu)化問(wèn)題,假設(shè)某個(gè)電力物資配送點(diǎn)在T時(shí)刻存在多個(gè)客戶(hù)需求,此時(shí)存在已知的送貨時(shí)間、地點(diǎn)、客戶(hù)需求量以及道路情況,且運(yùn)輸車(chē)容量為已知?；谶@種情況,為使運(yùn)輸車(chē)輛利用率得到提高,需要合理安排行駛路線(xiàn),以使車(chē)輛運(yùn)行距離最短。為此,構(gòu)建電力物資運(yùn)輸車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型,優(yōu)化電力運(yùn)輸車(chē)輛調(diào)度過(guò)程。

1.2.1電力物資運(yùn)輸車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型

(2)

式中:1表示車(chē)輛從點(diǎn)i行駛至點(diǎn)j,0表示車(chē)輛未從點(diǎn)i行駛至點(diǎn)j。由此,可得到運(yùn)輸車(chē)調(diào)度數(shù)學(xué)模型如下:

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1)當(dāng)i為電力物資配送點(diǎn)時(shí),運(yùn)輸?shù)墓潭ㄩ_(kāi)銷(xiāo)與運(yùn)行開(kāi)銷(xiāo)如式(10)所示:

cij=c0+c1dij,j=1,…,n

(10)

2)當(dāng)i同時(shí)為需求點(diǎn)時(shí),僅包含運(yùn)行開(kāi)銷(xiāo),如式(11)所示:

cij=c1dij,i≠0,j=1,…,n

(11)

式中:c1為運(yùn)輸距離的開(kāi)銷(xiāo)系數(shù),c0為已有運(yùn)輸車(chē)固定開(kāi)銷(xiāo),dij為添加新車(chē)輛的邊際開(kāi)銷(xiāo)。通常情況下,若c1=0,c0>0,則表示達(dá)到目標(biāo)配送點(diǎn)所使用的車(chē)輛數(shù)最少。

在構(gòu)建的運(yùn)輸車(chē)輛調(diào)度優(yōu)化問(wèn)題模型中,式(3)為目標(biāo)函數(shù),式(4)～式(9)均為約束條件。其中,式(4)為每輛車(chē)的載貨量限制,式(5)表示每個(gè)需求點(diǎn)僅能進(jìn)行單次訪問(wèn),式(6)～式(8)為每輛車(chē)從配送點(diǎn)出發(fā)到需求點(diǎn)后再次返回配送點(diǎn)的限制,式(9)為路徑選擇約束。通過(guò)參數(shù)差異化分析,可將調(diào)度優(yōu)化問(wèn)題調(diào)整為組合優(yōu)化問(wèn)題。假設(shè)某輛運(yùn)輸車(chē)已經(jīng)被使用,則該問(wèn)題可轉(zhuǎn)變?yōu)槁眯猩虇?wèn)題(TSP),以此構(gòu)建調(diào)度優(yōu)化模型。

1.2.2基于改進(jìn)Hopfield神經(jīng)網(wǎng)絡(luò)的車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型求解

利用改進(jìn)Hopfield神經(jīng)網(wǎng)絡(luò)對(duì)VRPRW進(jìn)行求解。Hopfield神經(jīng)網(wǎng)絡(luò)屬于連續(xù)的單層反饋網(wǎng)絡(luò),變量具有連續(xù)性[11-13],方程為微分形式。

運(yùn)用改進(jìn)Hopfield神經(jīng)網(wǎng)絡(luò)求解車(chē)輛調(diào)度問(wèn)題時(shí),分為以下4個(gè)步驟。

1)構(gòu)造鄰接矩陣。

用網(wǎng)絡(luò)節(jié)點(diǎn)表示起始點(diǎn)、交匯點(diǎn)以及停車(chē)點(diǎn),并用抽象的邊連接每個(gè)點(diǎn)形成有向路徑,繪制出一個(gè)有向圖G,G=(N,L,D),L為邊數(shù),N為節(jié)點(diǎn)數(shù),D為N×N矩陣。由1.2.1節(jié)調(diào)度問(wèn)題數(shù)學(xué)模型可知,需進(jìn)行優(yōu)化的目標(biāo)為邊(i,j)對(duì)應(yīng)的長(zhǎng)度、開(kāi)銷(xiāo)與時(shí)間,因此可構(gòu)建距離、開(kāi)銷(xiāo)與時(shí)間的鄰接矩陣。若兩個(gè)節(jié)點(diǎn)之間存在路徑,那么對(duì)應(yīng)的矩陣元素為路徑長(zhǎng)度、開(kāi)銷(xiāo)與運(yùn)輸時(shí)長(zhǎng);若兩個(gè)節(jié)點(diǎn)之間不存在路徑,那么對(duì)應(yīng)矩陣元素值為∞。

用行與列表示車(chē)輛路徑,列描述運(yùn)輸車(chē)配送順序,行描述配送點(diǎn)與需求點(diǎn)。將需求點(diǎn)排序,從“0”開(kāi)始編號(hào),其中“0”表示起始位置。

2)約束的處理。

將多個(gè)附加約束條件描述為神經(jīng)網(wǎng)絡(luò)的能量項(xiàng),在每個(gè)能量方程中引入懲罰項(xiàng),通過(guò)這種形式,使約束條件的能量隨著神經(jīng)網(wǎng)絡(luò)的不斷收斂而變得更加穩(wěn)定。

設(shè)需求點(diǎn)所需物資質(zhì)量為qx,設(shè)配送點(diǎn)序號(hào)為x,y。

①假設(shè)每行每列僅存在一個(gè)1,此時(shí)車(chē)輛集合為Vyi,若運(yùn)輸車(chē)僅路過(guò)一次需求點(diǎn),則車(chē)輛集合為Vxi,若必須配送一次,則車(chē)輛集合為Vxj,返回配送點(diǎn)的約束條件如式(12)、式(13)所示:

(12)

(13)

②若全部列的值之和為J,即配送的路徑數(shù)量為J,車(chē)輛集合為V0t,則存在約束如式(14)所示:

(14)

③若整個(gè)矩陣內(nèi)每個(gè)單元之和為(n+J),則存在約束如式(15)所示:

(15)

④若配送車(chē)的配送起始點(diǎn)必須為物資配送點(diǎn),則車(chē)輛集合為V0t,存在約束如式(16)所示:

V01=1

(16)

⑤配送車(chē)存在負(fù)載量限制,且每輛車(chē)存在容量限制Q,若達(dá)到限制標(biāo)準(zhǔn)則返回起始位置。

⑥構(gòu)建目標(biāo)函數(shù),如式(19)所示:

(17)

式中:f為目標(biāo)函數(shù),Vxi(Vy,i+1+Vy,i-1)為車(chē)輛集合反演結(jié)果,dxy為需求點(diǎn)訪問(wèn)閾值。

3)神經(jīng)網(wǎng)絡(luò)計(jì)算。

假設(shè)鄰接矩陣中各元素均與一個(gè)神經(jīng)元對(duì)應(yīng),并設(shè)定Vxi為位置(x,i)的神經(jīng)元輸出函數(shù),對(duì)應(yīng)不同車(chē)輛集合反演結(jié)果。在計(jì)算之前,需確定網(wǎng)絡(luò)的能量函數(shù),通過(guò)能量函數(shù)的計(jì)算,可獲取神經(jīng)元的傳遞函數(shù)與狀態(tài)轉(zhuǎn)移方程,之后通過(guò)網(wǎng)絡(luò)的持續(xù)迭代,實(shí)現(xiàn)網(wǎng)絡(luò)收斂。網(wǎng)絡(luò)的能量函數(shù)E′為:

(18)

式中:A、B、C、D、E分別為狀態(tài)轉(zhuǎn)移階段對(duì)應(yīng)的各神經(jīng)元收斂系數(shù),gx為當(dāng)前值,Z為收斂域。

②在初始輸出狀態(tài)中引入一個(gè)小的隨機(jī)偏置,使每個(gè)初始單元的值分布不均勻。

④分析神經(jīng)元生成路徑,獲取再次循環(huán)后的輸入狀態(tài)值,并進(jìn)行循環(huán)計(jì)算。

⑤將狀態(tài)值設(shè)置為不同收斂期的動(dòng)態(tài)值。

⑥若E′在循環(huán)10次內(nèi)變化低于10-4且滿(mǎn)足全部循環(huán)計(jì)算條件,或循環(huán)達(dá)到4 000次后,終止循環(huán)。

4)形成調(diào)度方案。

當(dāng)神經(jīng)網(wǎng)絡(luò)收斂后,可匯集成一個(gè)換位陣,該陣由0和1構(gòu)成,在陣中車(chē)輛經(jīng)過(guò)的節(jié)點(diǎn)由1表示,將節(jié)點(diǎn)間的距離、運(yùn)輸時(shí)間與開(kāi)銷(xiāo)相加,即可得到最短距離、時(shí)間以及最低的開(kāi)銷(xiāo),結(jié)合附加約束條件,可獲得運(yùn)輸車(chē)輛調(diào)度方案。

1.3 禁忌搜索算法優(yōu)化車(chē)輛調(diào)度

利用禁忌搜索算法對(duì)上述求解過(guò)程進(jìn)行優(yōu)化,使配送車(chē)調(diào)度過(guò)程更加完善。通過(guò)該算法,可以使神經(jīng)網(wǎng)絡(luò)在深度卷積過(guò)程中避免出現(xiàn)局部最優(yōu)解現(xiàn)象[14-15],具體算法實(shí)現(xiàn)步驟如下:

1)對(duì)解進(jìn)行評(píng)價(jià)。利用禁忌搜索算法優(yōu)化車(chē)輛調(diào)度問(wèn)題時(shí),需對(duì)求解的內(nèi)容進(jìn)行評(píng)價(jià),保證經(jīng)過(guò)迭代后可以獲取最優(yōu)解。針對(duì)某個(gè)約束條件下的解,假設(shè)其相應(yīng)的配送路徑方案的路徑條數(shù)與初始配送路徑之差為M,其目標(biāo)函數(shù)的值為W,并設(shè)每條不可運(yùn)輸路徑的懲罰權(quán)重為Pw,由此可計(jì)算該解的評(píng)價(jià)值β′:

β′=W+M×Pw

(19)

2)對(duì)鄰域進(jìn)行操作。選取兩交換法處理鄰域,即隨機(jī)挑選解中的兩個(gè)元素,將兩個(gè)元素的值進(jìn)行交換,即完成鄰域處理。

3)獲取禁忌對(duì)象。在每次進(jìn)行迭代時(shí)獲得最優(yōu)解,將其作為禁忌對(duì)象放置在禁忌表內(nèi)。

4)獲取禁忌長(zhǎng)度。每個(gè)被禁對(duì)象不能選擇相同數(shù)量的迭代步驟,根據(jù)求解規(guī)模選擇禁忌長(zhǎng)度。

5)獲取候選集合。從當(dāng)前解鄰域內(nèi)隨機(jī)挑選若干個(gè)鄰域,并將這些鄰域設(shè)為候選集合。

6)確定終止條件。將迭代的指定步數(shù)作為該算法的終止條件。

通過(guò)上述步驟,可以實(shí)現(xiàn)電力物資運(yùn)輸車(chē)輛調(diào)度的優(yōu)化,提升算法的迭代速度,使計(jì)算效率提高。

2 實(shí)驗(yàn)分析

對(duì)某企業(yè)電力物資配送過(guò)程中的電力物資運(yùn)輸車(chē)輛調(diào)度進(jìn)行優(yōu)化,并選取文獻(xiàn)[6]基于擾動(dòng)收縮粒子群算法的物聯(lián)網(wǎng)配送車(chē)輛調(diào)度算法、文獻(xiàn)[7]基于改進(jìn)飛蛾撲火算法求解多需求點(diǎn)的應(yīng)急物資調(diào)度算法進(jìn)行對(duì)比。

分析不同算法從電力物資配送點(diǎn)到達(dá)物資需求點(diǎn)的規(guī)劃路線(xiàn),結(jié)果如圖1所示。

圖1 不同算法的規(guī)劃路線(xiàn)

由圖1可知,不同算法到達(dá)3個(gè)需求點(diǎn)所規(guī)劃的路徑不同,文獻(xiàn)[7]算法規(guī)劃后的路徑距離最長(zhǎng),該路徑呈曲線(xiàn),車(chē)輛依次到達(dá)各需求點(diǎn)后依然按照曲線(xiàn)路徑返回物資配送點(diǎn);文獻(xiàn)[6]算法規(guī)劃后的路徑明顯短于文獻(xiàn)[7]算法規(guī)劃的路徑,但要明顯長(zhǎng)于本文算法規(guī)劃的路徑。本文算法規(guī)劃的路徑為直線(xiàn),將物資配送至各個(gè)需求點(diǎn)后仍沿直線(xiàn)路線(xiàn)返回至物資配送點(diǎn)。由此可知,本文算法可有效優(yōu)化物資配送路徑。

選取10個(gè)電力物資需求點(diǎn)進(jìn)行配送服務(wù),從需求點(diǎn)1起步運(yùn)輸直至需求點(diǎn)10,分析不同算法路徑規(guī)劃后達(dá)到各個(gè)需求點(diǎn)的路線(xiàn)長(zhǎng)度,結(jié)果如圖2所示。

圖2 不同算法規(guī)劃路線(xiàn)長(zhǎng)度分析

由圖2可知,隨著需求點(diǎn)逐漸增多,3種算法的配送路線(xiàn)長(zhǎng)度也逐漸增加,其中文獻(xiàn)[7]算法在進(jìn)行配送時(shí)路線(xiàn)總長(zhǎng)度最長(zhǎng),文獻(xiàn)[6]算法的配送總長(zhǎng)度略低于文獻(xiàn)[7]算法,但兩種算法到達(dá)需求點(diǎn)10時(shí)的配送總長(zhǎng)度均已超過(guò)180 km。本文算法的配送總長(zhǎng)度僅為165 km,低于另外兩種算法,由此可知,利用本文算法進(jìn)行車(chē)輛調(diào)度,可有效縮短總的配送路徑長(zhǎng)度。

分析向每個(gè)需求點(diǎn)運(yùn)送不同物資時(shí)所需的運(yùn)輸時(shí)間,結(jié)果如圖3所示。

圖3 不同物資運(yùn)輸所需時(shí)間

由圖3可知,隨著配送需求點(diǎn)的增加,每種物資配送的所需時(shí)間也有所增加,其中在配送電力絕緣物資時(shí)所需時(shí)間最長(zhǎng),這是由于絕緣物資在運(yùn)輸時(shí)需要專(zhuān)用車(chē)輛,而應(yīng)急物資配送所需時(shí)間最短,報(bào)廢物資配送所需時(shí)間略高于應(yīng)急物資,說(shuō)明應(yīng)用本文算法進(jìn)行配送車(chē)輛調(diào)度可加快應(yīng)急電力物資的配送。同時(shí),配送3種物資的所需時(shí)間均未超過(guò)7.5 h,處于合理的時(shí)間范圍內(nèi),因此利用本文算法調(diào)度電力物資運(yùn)輸車(chē)輛可有效節(jié)約配送時(shí)間。

向10個(gè)需求點(diǎn)分別配送1 000箱物資,并要求在10 h內(nèi)完成所有配送,且3種算法在規(guī)劃路徑后均使用兩輛車(chē)進(jìn)行配送,分析不同算法在配送時(shí)的消耗情況,即不同算法調(diào)度后所需油耗,分析結(jié)果見(jiàn)表1。

表1 不同算法車(chē)輛調(diào)度后的消耗情況 單位:L/100 km

由表1可知,文獻(xiàn)[6]算法規(guī)劃的路徑油耗最高,文獻(xiàn)[7]算法規(guī)劃的路徑在到達(dá)需求點(diǎn)1時(shí)的油耗最高,本文算法規(guī)劃路徑的油耗始終低于其他兩種算法,說(shuō)明本文算法規(guī)劃的車(chē)輛配送路徑可以節(jié)約開(kāi)銷(xiāo),降低運(yùn)輸成本。

3 結(jié)束語(yǔ)

本文完成了電力物資運(yùn)輸車(chē)輛調(diào)度優(yōu)化算法的研究。基于深度卷積神經(jīng)網(wǎng)絡(luò),構(gòu)建了電力物資運(yùn)輸車(chē)輛調(diào)度問(wèn)題數(shù)學(xué)模型,并通過(guò)禁忌搜索算法實(shí)現(xiàn)調(diào)度過(guò)程優(yōu)化。在未來(lái)的研究中,可對(duì)現(xiàn)有算法繼續(xù)優(yōu)化,以實(shí)現(xiàn)多種類(lèi)型物資運(yùn)輸車(chē)輛的調(diào)度,并通過(guò)路徑規(guī)劃避免車(chē)輛運(yùn)輸時(shí)出現(xiàn)意外情況。