黃煜坤，彭 成，戚銘堯，李 銳

（1.廣東電網(wǎng)有限責(zé)任公司惠州供電局，廣東 惠州 516001；2.清華大學(xué)深圳研究生院 物流與交通學(xué)部，廣東 深圳 518055）

電網(wǎng)運(yùn)維物資配送線路規(guī)劃系統(tǒng)的設(shè)計與實現(xiàn)

黃煜坤1，彭 成2，戚銘堯2，李 銳1

（1.廣東電網(wǎng)有限責(zé)任公司惠州供電局，廣東 惠州 516001；2.清華大學(xué)深圳研究生院 物流與交通學(xué)部，廣東 深圳 518055）

主要研究電網(wǎng)運(yùn)維物資從配送中心（電網(wǎng)一級倉）到電網(wǎng)末端倉庫（急救包）的配送線路的優(yōu)化以及配送管理系統(tǒng)的設(shè)計與實現(xiàn)問題。首先針對配送線路優(yōu)化問題，設(shè)計了一個基于元啟發(fā)式方法—變鄰域搜索算法的多時間窗車輛路徑規(guī)劃算法；同時，應(yīng)用百度地圖等空間信息技術(shù)，設(shè)計和實現(xiàn)了一個配送管理系統(tǒng)，并且把以上所設(shè)計的路徑優(yōu)化算法嵌入到此系統(tǒng)中。通過實際案例表明此算法對電網(wǎng)運(yùn)維物資的配送線路有顯著的改進(jìn)效果，設(shè)計的系統(tǒng)可減輕電網(wǎng)人員的工作強(qiáng)度，提高了工作效率。

電網(wǎng)運(yùn)維物資；物流配送；線路優(yōu)化；變鄰域搜索

1 引言

電網(wǎng)運(yùn)維物資是電網(wǎng)物資中除了基礎(chǔ)建設(shè)物資之外的最重要的一部分物資，主要用于電網(wǎng)設(shè)施的日常維護(hù)和運(yùn)行。一般情況下，電網(wǎng)的配送中心（倉庫）每月都會定期為其管理的急救包（電網(wǎng)末端倉庫）配送其所需要的日常運(yùn)維物資。電網(wǎng)運(yùn)維物資的配送問題，本質(zhì)上是一種車輛路徑規(guī)劃問題（Vehicle Routing Problem, VRP），其中存在兩點基本約束：（1）配送中心和急救包往往有著自己的時間安排，即都有時間窗限制，而且急救包有上午和下午多個時間窗限制；（2）配送中心的車輛有載重限制。目標(biāo)是在滿足以上兩種約束的情況下，滿足急救包的需求，使得配送線路的距離最小。電網(wǎng)運(yùn)維物資是日常所需，其特點是需求量不大，但需求頻率高，不合理的運(yùn)輸線路往往會消耗很大的成本。因此，如何高效地組織配送、節(jié)約運(yùn)輸成本是亟待解決的難題。同時隨著在線電子地圖、全球定位系統(tǒng)等技術(shù)的普及，設(shè)計與開發(fā)一套高效易用的線路規(guī)劃調(diào)度系統(tǒng)對于電網(wǎng)系統(tǒng)物流管理人員來說是非常必要的。

目前專門研究電網(wǎng)運(yùn)維物資運(yùn)輸路線優(yōu)化的文獻(xiàn)不多。文獻(xiàn)[1]提出了一個模糊運(yùn)輸網(wǎng)絡(luò)模型，其中需求點之間的邊權(quán)值為模糊數(shù)，在規(guī)定的時間窗下，利用最短路算法，尋找一個最短路徑。文獻(xiàn)[2]研究了物資需求頻繁且每次需求量較小的情況，提出基于時間和數(shù)量的發(fā)貨模式，即每達(dá)到一定時間點的發(fā)貨模式和需求每達(dá)到一定的數(shù)量的發(fā)貨模式，線路求解采用的是極值法。文獻(xiàn)[3]提出了利用層次分析法確定多目標(biāo)配送線路規(guī)劃的方法，同時也設(shè)計了一個通用的線路求解軟件。文獻(xiàn)[4-5]分別采用了粒子群和遺傳算法對路徑進(jìn)行優(yōu)化。在實際配送過程中，物資配送線路的優(yōu)化計算多使用節(jié)約里程法，例如文獻(xiàn)[6-8]。此外，配送管理系統(tǒng)的框架設(shè)計也吸引了一些學(xué)者進(jìn)行研究，文獻(xiàn)[9-10]都提出了基于物聯(lián)網(wǎng)技術(shù)的物流配送系統(tǒng)設(shè)計，其中線路優(yōu)化是利用地理信息系統(tǒng)(Geographic Information System,GIS)軟件來求解。

然而，在以上這些研究中，都存在著一些不足。如：一些類似于求導(dǎo)得到函數(shù)極值的精確方法只能夠處理比較小規(guī)模的問題；節(jié)約里程法的思想比較簡單，需要列出所有節(jié)點的節(jié)約里程數(shù)，運(yùn)算復(fù)雜度比較高；粒子群算法和遺傳算法等元啟發(fā)式方法一般沒有考慮多時間窗的情況；借助GIS軟件設(shè)計配送系統(tǒng)的方法需要購買專業(yè)的GIS軟件，投資比較大，對地圖管理的技術(shù)要求比較高，不利于應(yīng)用的推廣。

因此，針對這些問題，相對于節(jié)約算法，我們設(shè)計了一種元啟發(fā)式算法—擴(kuò)展的變鄰域搜索算法（Skewed Variable neighborhood search algorithm,SVNS），如文獻(xiàn)[11]。眾所周知，VNS算法已廣泛應(yīng)用于求解各類VRP問題中，是一種高效的路徑優(yōu)化算法。針對電網(wǎng)運(yùn)維物資的配送問題，本文的主要貢獻(xiàn)有：首先，設(shè)計了一個基于SVNS的多時間窗車輛路徑算法（以下稱為VRASVNS算法）來配送線路的優(yōu)化；其次，設(shè)計并實現(xiàn)了一個方便且實用的電網(wǎng)運(yùn)維物資配送線路規(guī)劃系統(tǒng)；第三，采用百度在線地圖API（Application Programming Interface）技術(shù)，處理地理數(shù)據(jù)并可視化展示配送線路。

2 VRA-SVNS算法

如上所述，本文基于VRA-SVNS算法來設(shè)計車輛路徑，其基本步驟如下：

（1）應(yīng)用文獻(xiàn)[12]的I1算法求得一個可行的初始解；

（2）通過有序的選擇某一個鄰域結(jié)構(gòu)產(chǎn)生基于當(dāng)前解的一個鄰域解—Shaking階段；

（3）通過一些算子來尋找基于當(dāng)前鄰域解的一個局部最優(yōu)解—local search階段；

（4）判斷當(dāng)前局部最優(yōu)解是否優(yōu)于當(dāng)前最優(yōu)解，如果是則用局部最優(yōu)解替換當(dāng)前最優(yōu)解—Improve or not階段；

（5）計算局部最優(yōu)解和當(dāng)前解“距離”，選擇是否更換鄰域結(jié)構(gòu)—move or not階段。

如此循環(huán)步驟（2）至步驟（5），直到循環(huán)條件滿足為止。

2.1 Shaking階段

利用當(dāng)前鄰域結(jié)構(gòu)無法得到一個更好的解時，我們嘗試新的鄰域結(jié)構(gòu)，使得搜索的解空間具有多樣性，這個階段稱為Shaking，這是VRA-SVNS算法的關(guān)鍵。定義鄰域結(jié)構(gòu)需要考慮如下三個方面：首先，在算法效率和算法跳出局部最優(yōu)解的機(jī)會之間維持一個好的平衡；其次，鄰域結(jié)構(gòu)是否可以產(chǎn)生非可行解；最后，鄰域結(jié)構(gòu)的數(shù)量也需要考慮。

對于本文所研究的路徑規(guī)劃問題，最常用且有效的鄰域結(jié)構(gòu)是文獻(xiàn)[13]使用的cross-exchange算子。這個算子的主要思想是選擇兩條路徑，交換這兩條路徑中任意數(shù)量（最大的為該路徑上的所有顧客，最小值為0）的顧客點，從而產(chǎn)生兩條新的路徑，即為鄰域解。與此同時，Michael et al還擴(kuò)展了該算子，叫做icross-exchange。這兩者的唯一不同就是前者是在兩條交換的路徑上正向放置所交換的顧客點，而后者是逆向的。類似的，本文也設(shè)計了一種算子half-icross-exchange，與以上兩個的區(qū)別是放置所交換的顧客點的方式，即一條路徑上是正向放置，另外一條逆向放置，路徑選擇正向或逆向放置是隨機(jī)的。

除了以上鄰域結(jié)構(gòu)算子之外，我們還應(yīng)用到了如下算子：在一條路徑上隨機(jī)交換兩點(2-opt)[14]；在兩條不同的路徑上隨機(jī)交換任意兩個顧客點(swap)。另一個經(jīng)典的算子2-opt*[15]，也被應(yīng)用于本文之中。表1展示了本文使用的所有算子。

表1 鄰域結(jié)構(gòu)

2.2 Local search階段

本階段的主要任務(wù)是用一些局部搜索算子，對shaking階段產(chǎn)生的鄰域解進(jìn)行改進(jìn)，得到一個局部最優(yōu)解，稱為local search，這是SVNS設(shè)計的另一個關(guān)鍵點。為了設(shè)計和選擇這些搜索算子，我們從兩個角度考慮，第一是算子操作角度，包括一條路徑中的操作、多條路徑的操作；第二是搜索范圍角度，包括在部分路徑中搜索、對解中的所有路徑進(jìn)行搜索尋優(yōu)。本文的局部搜索步驟如下：

（1）為了把一些不可行解變成可行解，首先，應(yīng)用算子relocate（例如文獻(xiàn)[16]），這是單條路徑上的顧客重定位算子。其次，應(yīng)用算子sequence invert[14]，這個算子是把一條路徑上的部分顧客點逆序重新排列，圖1展示了其原理。接下來進(jìn)行relocate的擴(kuò)展，即extension of relocate算子，對兩條不同路徑上的顧客點重定位，最后，我們還應(yīng)用了swap算子。

（2）為了更進(jìn)一步搜索更好的解，考慮全局的搜索空間，如下的算子依次被應(yīng)用：首先我們在所有的路徑上，應(yīng)用relocate、sequence invert和swap算子。然后，應(yīng)用文獻(xiàn)[13]使用的一種限制3-opt算子。此外，我們定義和應(yīng)用了一種新的重定位算子—relocate*算子，它的原理是重定位一個顧客點與所有路徑的所有位置，選出一個使得距離減少最多的定位方式。最后，文獻(xiàn)[17]使用的Ejection Chain(EC)算子被應(yīng)用尋找更優(yōu)的解，這個算子可以同時考慮三條路徑，圖2展示了EC的一個操作示例。表2展示了local search階段所使用的所有尋優(yōu)算子。

表2 局部搜索算子

圖1 Sequence invert的原理

圖2 Ejection Chain的操作示例

2.3 Improve or not階段

在shaking和local search階段之后產(chǎn)生了一個局部最優(yōu)解，improve or not階段的作用是決定是否用這個局部最優(yōu)解代替當(dāng)前最優(yōu)解。我們考慮如下的兩個標(biāo)準(zhǔn)來決定是否更新最優(yōu)解：（1）使用的車輛數(shù)的是否減少，若減少了，則更新，否則不更新；（2）在標(biāo)準(zhǔn)；（3）不滿足的情況下，如果車輛總的行駛里程數(shù)減少了，則更新，否則不更新。

2.4 Move or not階段

本階段需要做另外一個決策：是否更新當(dāng)前的鄰域結(jié)構(gòu)算子。在基本的VNS算法中，需要尋找距離當(dāng)前解很遠(yuǎn)的解來跳出局部最優(yōu)解，這樣會導(dǎo)致算法的退化，成多極值問題。SVNS提供了一個方法來克服這個問題，其主要思想是考慮局部最優(yōu)解和當(dāng)前解的“距離”。在本文的研究中，利用這兩個解中的所有顧客點不同序號數(shù)之和的大小來定義這個“距離”，具體的決策函數(shù)見下面的SVNS算法整體流程。

我們用x代表當(dāng)前解，x''表示局部最優(yōu)解。用ρ（x, x''）表示上文中的“距離”，其參數(shù)為α，領(lǐng)域結(jié)構(gòu)被定義為Nk，k=1,2,…,kmax。定義方f(x),xopt和fopt分別為目標(biāo)函數(shù)、最優(yōu)解和最優(yōu)解的函數(shù)值。最大迭代次數(shù)被定義為Nmax，作為算法的終止條件，用Ntemp表示當(dāng)前迭代次數(shù)。另外的兩個終止條件為由Shaking階段產(chǎn)生的不可行解的最多次數(shù)(NSmax)和由local search階段產(chǎn)生的不可行解的最多次數(shù)(NLmax)，對應(yīng)的，NStemp和NLtemp表示這兩個階段當(dāng)前產(chǎn)生的不可行解的次數(shù)，產(chǎn)生一次可行解后NStemp和NLtemp將被清零，最后，代表所使用的車輛數(shù)。

算法流程：SVNS algorithm.

（1）設(shè)定k=1，參數(shù)初始化；

（2）重復(fù)以下步驟直到任意一個終止條件滿足；

（3）如果Ntemp＞Nmax，程序結(jié)束；

（4）Shaking，產(chǎn)生一個鄰域解x',(x'∈Nk(x))；

（5）如果x'不滿足載重約束，則轉(zhuǎn)到步驟6，否則轉(zhuǎn)到步驟7；

（6）設(shè)置NStemp=NStemp+1，如果NStemp＞NSmax，算法結(jié)束，否則轉(zhuǎn)到步驟4；

（7）Local search，得到局部最優(yōu)解x''；

（8）如果x''不滿足時間窗或者載重約束，則轉(zhuǎn)至步驟9；否則，轉(zhuǎn)至步驟10；

（9）設(shè)置NLtemp=NLtemp+1，如果NLtemp＞NLmax，算法結(jié)束，否則轉(zhuǎn)到步驟4；

（10）Improve or not，如果①NVtemp減少，或者在車輛數(shù)不減少的情況下；② f(x'')＜fopt，設(shè)置 fopt=f(x'')以及xopt=x''；

（11）Move or not，如果，更新 x=x''，同時設(shè)置k=1，否則，設(shè)置k=k+1。更新Ntemp=Ntemp+1。

3 系統(tǒng)管理流程

本章主要描述電網(wǎng)運(yùn)維物資配送線路規(guī)劃系統(tǒng)的總體設(shè)計，包括總體功能設(shè)計和流程設(shè)計。

3.1 系統(tǒng)總體功能設(shè)計

當(dāng)前電網(wǎng)運(yùn)維物資配送線路主要是依靠人工經(jīng)驗來制定，配送效率低下且配送成本較高。本配送線路規(guī)劃系統(tǒng)綜合考慮公司物流網(wǎng)絡(luò)布局、車輛載重、時限要求等因素進(jìn)行配送線路優(yōu)化，并且將算法固化在系統(tǒng)中，針對電網(wǎng)物資管理人員進(jìn)行設(shè)計，做到簡單、方便、智能。該系統(tǒng)包括配送任務(wù)生成、配送路線排程、配送任務(wù)跟蹤等3個主要功能業(yè)務(wù)?？傮w功能設(shè)計如圖3所示。

3.2 系統(tǒng)主要功能業(yè)務(wù)描述

如上所述，本系統(tǒng)的三大主要業(yè)務(wù)為配送路線排程、配送車輛跟蹤、配送報表生成。

（1）線路排程。此業(yè)務(wù)的主要功能是為配送中心到急救包的物資配送規(guī)劃合理的路線。在選擇了需要配送的調(diào)撥單、設(shè)置線路排程參數(shù)以后，可以選擇自動或者手動排程，由此可以產(chǎn)生一條或多條優(yōu)化的配送路線，同時系統(tǒng)會生成相對應(yīng)的配送單。

其主要的子功能操作為：選擇調(diào)撥單、設(shè)置排程參數(shù)、人工手動排程或者利用系統(tǒng)算法自動排程、生成配送單。

（2）車輛跟蹤。此業(yè)務(wù)的主要功能是實現(xiàn)配送任務(wù)的跟蹤。采用手持終端設(shè)備（配備GPS全球定位系統(tǒng)模塊），司機(jī)在貨物送達(dá)時進(jìn)行確認(rèn)操作，管理者可以及時得到在途車輛的位置和狀態(tài)，實現(xiàn)對配送貨物的實時跟蹤。

（3）配送報表。生成配送報表業(yè)務(wù)，是在配送任務(wù)完成后，從不同維度、不同時間段統(tǒng)計配送業(yè)務(wù)量、員工工作量及其它配送績效指標(biāo)。

3.3 系統(tǒng)操作流程

圖3 系統(tǒng)總體功能設(shè)計

系統(tǒng)的主要操作流程如圖4所示。

圖4 系統(tǒng)主要業(yè)務(wù)流程

4 案例分析

本文考慮A供電局“一級倉（配送中心）+急救包”模式，日常補(bǔ)貨中，需要從1個一級倉向40個急救包補(bǔ)貨。每個急救包都有午休時間12:00-14:00，此期間不接受送貨。所以若車輛到達(dá)一個急救包后，不能在12:00前完成服務(wù)，那么就要推遲到14:00開始卸貨，完成貨物交接后去往下一個急救包，因此可以看做是有多時間窗要求（上午和下午各一個時間窗）。

4.1 基礎(chǔ)數(shù)據(jù)

配送中心和急救包的經(jīng)緯度坐標(biāo)利用Google Maps API的Geocoding接口獲得。任意兩個倉庫點之間的距離矩陣和時間矩陣可調(diào)用Google Maps API的direction接口獲得。

配送中心的工作時間設(shè)定為8:30-17:30，車輛在配送中心處的裝貨時間為1.5h，而后即10:00正式出發(fā)。在每個急救包處卸貨0.5h。目前A供電局規(guī)定每輛車每天最多服務(wù)4個急救包。

4.2 算法結(jié)果

我們設(shè)定兩種計算方式，第一種（scenario 1）是有限制條件：每輛車每天最多服務(wù)4個急救包；第二種（scenario 2）是沒有這個限制。表3展示了其對比結(jié)果，同時表4給出了兩種情況的所有配送線路（routes）上的急救包（customers）的數(shù)目（Cus.Number），以及具體的配送順序（Cus.Order）。

表3 計算結(jié)果對比

從表3和表4的結(jié)果，我們可以看出：第一，不考慮每輛車每天配送急救包的數(shù)量限制的情況下，車輛的總行駛里程要減少11.27%；第二，同樣是在這種情況下，車輛的使用數(shù)可以減少3輛。由此可見，采用優(yōu)化算法后，配送績效有很大的改進(jìn)空間。

5 結(jié)束語

本文研究了考慮車輛載重、帶多時間窗約束的電網(wǎng)運(yùn)維物資的線路規(guī)劃與調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)問題。首先設(shè)計了一個基于Skewed VNS算法的線路規(guī)劃算法VRA-SVNS，用于自動計算配送線路；其次設(shè)計了配送線路規(guī)劃系統(tǒng)的功能和流程，并且將VRA-SVNS算法集成到此系統(tǒng)中，用于電網(wǎng)運(yùn)維物資配送的管理。在案例分析部分，對A供電局的配送線路進(jìn)行了優(yōu)化計算，通過與企業(yè)現(xiàn)實情況的對比，表明此算法能夠降低車輛的使用數(shù)，并節(jié)省運(yùn)輸里程。同時，所設(shè)計開發(fā)的信息系統(tǒng)可提高配送管理的工作效率，降低人員的工作強(qiáng)度。

表4 配送線路信息對比

[1]張國英,張宏偉,郅青.電力物資應(yīng)急配送體系最優(yōu)路徑模型設(shè)計[J].物流科技,2012,(5):54-57.

[2]余劍林.電網(wǎng)運(yùn)維物資的集中發(fā)貨策略研究[J].物流科技, 2015,(5):70-74.

[3]劉宏志,李慧蘭,趙啟蘭.多目標(biāo)配送線路的合理選擇[J].物流技術(shù),1998,(6):22-24.

[4]鄧先瑞,于曉慧,李春艷,等.差異化高斯雙導(dǎo)向差分物流配送優(yōu)化[J].計算機(jī)應(yīng)用研究,2015,32.

[5]王楨,黃磊.考慮訂單發(fā)貨區(qū)域的物流配送調(diào)度問題研究[J].計算機(jī)應(yīng)用研究,2015,33.

[6]劉俊娥,李奇.基于節(jié)約里程法的北京市家樂福超市配送線路優(yōu)化方案[J].物流技術(shù),2015,34:107-109.

[7]張文華.基于節(jié)約里程法的物流配送路線優(yōu)化[J].物流工程與管理,2012,34(3):143-146.

[8]鄭靜,程幼明.基于時間約束的節(jié)約里程法配送路徑優(yōu)化研究[J].物流工程與管理,2010,32(10):89-90.

[9]李浩松,王瑋,張建業(yè),等.基于物聯(lián)網(wǎng)的電力企業(yè)物資配送平臺研究[J].電力信息與通訊技術(shù),2014,12(12):101-105.

[10]杜輝,盧琳.物聯(lián)網(wǎng)技術(shù)下的物流配送系統(tǒng)總體框架設(shè)計[J].物流技術(shù),2014,33(9):410-412.

[11]Hansen P,Mladenovic N.Avariable neighborhood search algorithm:Principles and applications[J].European Journal of Operation Research,2001,130:449-467.

[12]Solomon,MM.Algorithms for the vehicle-routing and scheduling problems with time window constraints[J].Operations Research,1987,35(2):254-265.

[13]Michael P,Richard F Hartl,Karl D.A Variable Neighborhood Search for the Multi-Depot Vehicle Routing Problem with Time Windows[J].Journal of Heuristics,2004,10:613-627.

[14]Belhaiza S,Hansen P,Laporte.G A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows[J].Computers Operations Research 2014,52:269-281.

[15]Prins C.A simple and effective evolutionary algorithm for the vehicle routing problem[J].Computers Operations Research,2004,31:1 985-2 002.

[16]Cattaruzza D,Absi N,Feillet D,Vigo D.An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows[J].Computers and Operations Research,2014,51:257-267.

[17]Braysy O.A reactive variable neighborhood search for vehicle-routing problem with time windows[J].Informs Journal on Computing,2003,15(4):347-368.

Design and Realization of Distribution Route Planning System of Power Grid Operation and Maintenance Materials

Huang Yukun1,Peng Cheng2,Qi Mingyao2,Li Rui1
(1.Huizhou Power Supply Company of Guangdong State Grid Co.,Ltd.,Huizhou 516001; 2.Logistics&Communication Department,Tsinghua University Graduate School at Shenzhen,Shenzhen 518055,China)

In this paper,we mainly studied the optimization of the distribution route of the power grid operation and maintenance materials from the distribution center(grade-1 power grid warehouse)to the end-point warehouse of the power grid(emergency package)and the issues in the design and realization of the distribution management system.In this paper,we designed the multiple time window VRP algorithm based on a meta-heuristic algorithm-the variable local search algorithm;at the same time,we applied a variety of spatial information technologies to design and realize a distribution management system and then embedded the route optimization algorithm designed above into the system.Next,we demonstrated the effectiveness of the algorithm in improving the efficiency of the distribution route of the power grid operation and maintenance materials through an empirical example.

power gridoperationandmaintenance material;logistics distribution;routeoptimization;variablelocalsearch

F253.9;U116

A

1005-152X(2017)01-0124-05

10.3969/j.issn.1005-152X.2017.01.027

2016-11-28

黃煜坤（1990-），男，廣東河源人，廣東電網(wǎng)有限責(zé)任公司惠州供電局助理工程師，研究方向：電網(wǎng)信息化；戚銘堯（1974-），通訊作者，男，清華大學(xué)深圳研究生院副教授，博士生導(dǎo)師，研究方向：物流系統(tǒng)建模與優(yōu)化。