宮寅林,王民濤

(1.國網內蒙古東部電力有限公司物資分公司,內蒙古 呼和浩特 010090) (2.國網內蒙古東部電力有限公司,內蒙古 呼和浩特 010090)

深度卷積神經網絡是基于人工神經網絡逐漸演變而來的[1],其通過神經元處理輸入信號來判斷是否進行下一步響應[2-3]。以此為基礎構建神經網絡數學模型,通過不斷卷積運算保證深度卷積神經網絡的處理結果更加完善,且擬合能力更強。

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

本文提出基于深度卷積神經網絡的電力物資運輸車輛調度優(yōu)化算法,通過Hopfield神經網絡處理電力物資運輸車輛調度問題,并利用禁忌搜索算法對調度模型進行優(yōu)化。

1 電力物資運輸車輛調度優(yōu)化算法

1.1 Hopfield神經網絡基本原理

選用Hopfield神經網絡實現深度卷積,該網絡是一種反饋型網絡[8-9]。神經網絡能量函數為:

(1)

式中:E為能量函數,Tij為神經元i與j之間的連接權值,Ii為神經元i的輸入閾值,Vi、Vj分別為神經元i與j的輸出值。

在一定條件下,只要能量函數沿著網絡的解遞減,能量函數的導數為零時網絡達到平衡狀態(tài)。通過Hopfield神經網絡,可有效實現神經網絡的深度卷積。

1.2 電力物資運輸車輛調度

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

1.2.1電力物資運輸車輛調度問題數學模型

(2)

式中:1表示車輛從點i行駛至點j,0表示車輛未從點i行駛至點j。由此,可得到運輸車調度數學模型如下:

(3)

(4)

(5)

(6)

(7)

(8)

(9)

1)當i為電力物資配送點時,運輸的固定開銷與運行開銷如式(10)所示:

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

(10)

2)當i同時為需求點時,僅包含運行開銷,如式(11)所示:

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

(11)

式中:c1為運輸距離的開銷系數,c0為已有運輸車固定開銷,dij為添加新車輛的邊際開銷。通常情況下,若c1=0,c0>0,則表示達到目標配送點所使用的車輛數最少。

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

1.2.2基于改進Hopfield神經網絡的車輛調度問題數學模型求解

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

運用改進Hopfield神經網絡求解車輛調度問題時,分為以下4個步驟。

1)構造鄰接矩陣。

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

用行與列表示車輛路徑,列描述運輸車配送順序,行描述配送點與需求點。將需求點排序,從“0”開始編號,其中“0”表示起始位置。

2)約束的處理。

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

設需求點所需物資質量為qx,設配送點序號為x,y。

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

(12)

(13)

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

(14)

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

(15)

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

V01=1

(16)

⑤配送車存在負載量限制,且每輛車存在容量限制Q,若達到限制標準則返回起始位置。

⑥構建目標函數,如式(19)所示:

(17)

式中:f為目標函數,Vxi(Vy,i+1+Vy,i-1)為車輛集合反演結果,dxy為需求點訪問閾值。

3)神經網絡計算。

假設鄰接矩陣中各元素均與一個神經元對應,并設定Vxi為位置(x,i)的神經元輸出函數,對應不同車輛集合反演結果。在計算之前,需確定網絡的能量函數,通過能量函數的計算,可獲取神經元的傳遞函數與狀態(tài)轉移方程,之后通過網絡的持續(xù)迭代,實現網絡收斂。網絡的能量函數E′為:

(18)

式中:A、B、C、D、E分別為狀態(tài)轉移階段對應的各神經元收斂系數,gx為當前值,Z為收斂域。

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

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

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

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

4)形成調度方案。

當神經網絡收斂后,可匯集成一個換位陣,該陣由0和1構成,在陣中車輛經過的節(jié)點由1表示,將節(jié)點間的距離、運輸時間與開銷相加,即可得到最短距離、時間以及最低的開銷,結合附加約束條件,可獲得運輸車輛調度方案。

1.3 禁忌搜索算法優(yōu)化車輛調度

利用禁忌搜索算法對上述求解過程進行優(yōu)化,使配送車調度過程更加完善。通過該算法,可以使神經網絡在深度卷積過程中避免出現局部最優(yōu)解現象[14-15],具體算法實現步驟如下:

1)對解進行評價。利用禁忌搜索算法優(yōu)化車輛調度問題時,需對求解的內容進行評價,保證經過迭代后可以獲取最優(yōu)解。針對某個約束條件下的解,假設其相應的配送路徑方案的路徑條數與初始配送路徑之差為M,其目標函數的值為W,并設每條不可運輸路徑的懲罰權重為Pw,由此可計算該解的評價值β′:

β′=W+M×Pw

(19)

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

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

4)獲取禁忌長度。每個被禁對象不能選擇相同數量的迭代步驟,根據求解規(guī)模選擇禁忌長度。

5)獲取候選集合。從當前解鄰域內隨機挑選若干個鄰域,并將這些鄰域設為候選集合。

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

通過上述步驟,可以實現電力物資運輸車輛調度的優(yōu)化,提升算法的迭代速度,使計算效率提高。

2 實驗分析

對某企業(yè)電力物資配送過程中的電力物資運輸車輛調度進行優(yōu)化,并選取文獻[6]基于擾動收縮粒子群算法的物聯網配送車輛調度算法、文獻[7]基于改進飛蛾撲火算法求解多需求點的應急物資調度算法進行對比。

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

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

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

選取10個電力物資需求點進行配送服務,從需求點1起步運輸直至需求點10,分析不同算法路徑規(guī)劃后達到各個需求點的路線長度,結果如圖2所示。

圖2 不同算法規(guī)劃路線長度分析

由圖2可知,隨著需求點逐漸增多,3種算法的配送路線長度也逐漸增加,其中文獻[7]算法在進行配送時路線總長度最長,文獻[6]算法的配送總長度略低于文獻[7]算法,但兩種算法到達需求點10時的配送總長度均已超過180 km。本文算法的配送總長度僅為165 km,低于另外兩種算法,由此可知,利用本文算法進行車輛調度,可有效縮短總的配送路徑長度。

分析向每個需求點運送不同物資時所需的運輸時間,結果如圖3所示。

圖3 不同物資運輸所需時間

由圖3可知,隨著配送需求點的增加,每種物資配送的所需時間也有所增加,其中在配送電力絕緣物資時所需時間最長,這是由于絕緣物資在運輸時需要專用車輛,而應急物資配送所需時間最短,報廢物資配送所需時間略高于應急物資,說明應用本文算法進行配送車輛調度可加快應急電力物資的配送。同時,配送3種物資的所需時間均未超過7.5 h,處于合理的時間范圍內,因此利用本文算法調度電力物資運輸車輛可有效節(jié)約配送時間。

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

表1 不同算法車輛調度后的消耗情況 單位:L/100 km

由表1可知,文獻[6]算法規(guī)劃的路徑油耗最高,文獻[7]算法規(guī)劃的路徑在到達需求點1時的油耗最高,本文算法規(guī)劃路徑的油耗始終低于其他兩種算法,說明本文算法規(guī)劃的車輛配送路徑可以節(jié)約開銷,降低運輸成本。

3 結束語

本文完成了電力物資運輸車輛調度優(yōu)化算法的研究?；谏疃染矸e神經網絡,構建了電力物資運輸車輛調度問題數學模型,并通過禁忌搜索算法實現調度過程優(yōu)化。在未來的研究中,可對現有算法繼續(xù)優(yōu)化,以實現多種類型物資運輸車輛的調度,并通過路徑規(guī)劃避免車輛運輸時出現意外情況。