李士動(dòng)，陳 綱，劉 方

（1.國(guó)網(wǎng)山東省電力公司泰安供電公司，山東 泰安 271000；2.上海電力大學(xué)電氣工程學(xué)院，上海 200090）

0 引言

近年來(lái)，為進(jìn)一步提升配電網(wǎng)可靠供電和優(yōu)質(zhì)服務(wù)水平，配電網(wǎng)檢修正逐步向“去停電化”方向發(fā)展，帶電作業(yè)以其檢修不停電和便捷高效的優(yōu)點(diǎn)而得到快速發(fā)展，各地區(qū)每年的帶電作業(yè)規(guī)模也在持續(xù)增長(zhǎng)［1］。

實(shí)際工作中，供電企業(yè)需要通過(guò)制定工作計(jì)劃來(lái)管理帶電作業(yè)任務(wù)，即將眾多的工作任務(wù)分配到各個(gè)工作日，并安排給不同作業(yè)車輛。配電線路分布的特點(diǎn)是“點(diǎn)多面廣”，因此帶電作業(yè)地點(diǎn)地域分散，各地點(diǎn)的作業(yè)分組、作業(yè)順序決定了作業(yè)路徑，進(jìn)而成為影響工作效率的重要因素。實(shí)際中，基于人工經(jīng)驗(yàn)的工作計(jì)劃編制方式，無(wú)法實(shí)現(xiàn)不同地點(diǎn)作業(yè)任務(wù)的優(yōu)化組合，導(dǎo)致工作效率大大降低，造成人力、物力、時(shí)間資源的極大浪費(fèi)。尤其是，絕緣斗臂車作為當(dāng)前配電網(wǎng)帶電作業(yè)的主要裝備［2］，油耗較高，合理規(guī)劃車輛行駛路徑能夠有效降低車輛運(yùn)行成本。

配電網(wǎng)帶電作業(yè)計(jì)劃的制定本質(zhì)上屬于車輛路徑問(wèn)題（Vehicle Routing Problem，VRP）。目前，VRP已逐漸發(fā)展成為考慮容量約束［3］、時(shí)間窗口約束［4-5］、多車場(chǎng)條件［6-7］及動(dòng)態(tài)需求［8］的車輛路徑模型，并廣泛應(yīng)用于物流配送［9-10］、應(yīng)急物資調(diào)度［11-12］、電動(dòng)汽車充電和無(wú)人機(jī)巡檢路徑規(guī)劃［13-15］問(wèn)題。傳統(tǒng)上帶時(shí)間窗VRP 模型考慮的時(shí)間尺度為日內(nèi)，主要針對(duì)車輛到達(dá)配送點(diǎn)的時(shí)間點(diǎn)進(jìn)行約束，而未考慮多時(shí)間尺度下的任務(wù)分配問(wèn)題。文獻(xiàn)［16］對(duì)帶電作業(yè)路徑優(yōu)化問(wèn)題進(jìn)行了研究，但時(shí)間尺度僅考慮單個(gè)工作日，同時(shí)也未考慮時(shí)間窗要求。VRP 屬于多約束的組合優(yōu)化問(wèn)題，目前多采用智能算法如粒子群優(yōu)化算法、遺傳算法和蟻群算法等進(jìn)行求解。

基于“先分區(qū)、后優(yōu)化”的技術(shù)路線，建立了周前作業(yè)任務(wù)組合與日前作業(yè)路徑滾動(dòng)優(yōu)化的兩階段模型及算法，有效解決多時(shí)間尺度下的帶電作業(yè)路徑優(yōu)化問(wèn)題，同時(shí)提出了決策支持系統(tǒng)開(kāi)發(fā)方法，經(jīng)過(guò)仿真分析驗(yàn)證，所提出兩階段方法實(shí)現(xiàn)了不同地點(diǎn)作業(yè)任務(wù)的合理組合及路徑優(yōu)化。

1 帶電作業(yè)路徑的兩階段優(yōu)化方法

1.1 問(wèn)題分析

配電網(wǎng)帶電作業(yè)計(jì)劃一般以周為時(shí)間尺度，將眾多的工作任務(wù)分配至下一周的每個(gè)工作日內(nèi)，同時(shí)確定每個(gè)工作日作業(yè)車輛的行使路徑，車輛出發(fā)后依次經(jīng)過(guò)每個(gè)作業(yè)點(diǎn)并完成工作任務(wù)，當(dāng)日工作結(jié)束后返回出發(fā)點(diǎn)。單日最大可用作業(yè)車輛、作業(yè)點(diǎn)之間的距離和路程行駛用時(shí)、各任務(wù)作業(yè)用時(shí)及完成時(shí)限要求為已知信息。帶電作業(yè)路徑優(yōu)化的目標(biāo)就是找到作業(yè)車輛的最優(yōu)行駛路徑，使總成本（路程或用時(shí)）達(dá)到最小，同時(shí)滿足如下約束條件：

1）確保完成計(jì)劃周期內(nèi)的所有工作任務(wù)；

2）對(duì)于某些有時(shí)限要求（工作日或時(shí)間點(diǎn)）的工作任務(wù)，應(yīng)在要求的時(shí)限內(nèi)完成；

3）滿足臨時(shí)的緊急工作任務(wù)要求。根據(jù)《配電網(wǎng)缺陷管理辦法》要求，配電線路缺陷包括一般、嚴(yán)重及緊急缺陷，一般與嚴(yán)重缺陷的處理時(shí)限為周或月度及以上，因此可納入周優(yōu)化范疇，緊急缺陷則需要在24 h內(nèi)處理完畢，應(yīng)納入日前優(yōu)化范疇；

4）每車次路徑的總作業(yè)用時(shí)不超過(guò)人員日最大作業(yè)時(shí)長(zhǎng)，該約束用以考慮人員現(xiàn)場(chǎng)工作承載力；

5）每車次路徑上的總用時(shí)不超過(guò)日最大工作用時(shí)（包括總路程用時(shí)和總作業(yè)用時(shí)）；

6）每個(gè)工作任務(wù)只能由一個(gè)工作日的一輛作業(yè)車次完成；

7）單日調(diào)用車次不超過(guò)最大可用作業(yè)車輛。

配電網(wǎng)帶電作業(yè)車輛路徑問(wèn)題的優(yōu)化范圍包括確定性的周計(jì)劃任務(wù)及不確定性的緊急消缺任務(wù)，涉及周前與日前兩個(gè)時(shí)間尺度，難以建立統(tǒng)一的數(shù)學(xué)模型進(jìn)行一體化求解，為此提出“先分區(qū)，后優(yōu)化”的思路，依次建立周前作業(yè)任務(wù)合理組合與日前作業(yè)路徑滾動(dòng)優(yōu)化的兩階段模型。

1.2 周前作業(yè)任務(wù)組合模型

建立周前作業(yè)任務(wù)組合模型的目標(biāo)，是將確定性的周計(jì)劃任務(wù)合理分配至下一周的每個(gè)工作日內(nèi)。提出一階段作業(yè)點(diǎn)分區(qū)的處理方法，即依據(jù)作業(yè)任務(wù)的地理位置及時(shí)限要求，將作業(yè)點(diǎn)劃分至不同區(qū)域，區(qū)域與工作日一一對(duì)應(yīng)，為盡可能縮短作業(yè)車輛行駛路程，便于二階段開(kāi)展最優(yōu)路徑的搜索，一階段分區(qū)的原則應(yīng)是同一區(qū)域內(nèi)的作業(yè)點(diǎn)在地理位置上距離相近且具有相同的工作日時(shí)限要求。一階段的計(jì)算時(shí)間點(diǎn)是周前，優(yōu)化的周期為周，因此能夠?qū)崿F(xiàn)整體優(yōu)化，分區(qū)結(jié)果也將直接影響二階段的路徑優(yōu)化結(jié)果。

基于上述“分區(qū)”的方法，以各區(qū)域作業(yè)點(diǎn)連接成的多邊形周長(zhǎng)之和最小為優(yōu)化目標(biāo)，建立周前作業(yè)任務(wù)組合模型如式（1）所示。

式中：D為區(qū)域數(shù)量（工作日天數(shù)）；ND為周計(jì)劃任務(wù)數(shù)量；d為某區(qū)域即工作日；lij為作業(yè)點(diǎn)i與j之間的路徑距離；xijd為整數(shù)變量；tj為作業(yè)點(diǎn)j的作業(yè)用時(shí)；K為具備的作業(yè)車輛數(shù)量；T1max為每車次人員單日最大作業(yè)時(shí)長(zhǎng)；Rd為滿足緊急任務(wù)需求而預(yù)留的時(shí)間；SDj為作業(yè)點(diǎn)j的最早工作日時(shí)限；EDj為作業(yè)點(diǎn)j的最遲工作日時(shí)限。

式（2）表示考慮緊急任務(wù)需求后的單日最大作業(yè)時(shí)長(zhǎng)約束；式（3）表示作業(yè)點(diǎn)的工作日時(shí)限約束；式（4）和式（5）表示每個(gè)作業(yè)點(diǎn)只能安排在一個(gè)工作日；式（6）表示變量定義規(guī)則。

1.3 日前作業(yè)路徑滾動(dòng)優(yōu)化模型

日前作業(yè)路徑優(yōu)化是在周前作業(yè)任務(wù)分區(qū)的基礎(chǔ)上，進(jìn)一步確定每日作業(yè)車輛的最優(yōu)行駛路徑，同時(shí)考慮緊急任務(wù)需求對(duì)作業(yè)路徑進(jìn)行滾動(dòng)優(yōu)化。二階段的計(jì)算時(shí)間點(diǎn)是日前，優(yōu)化的周期為日，能夠利用最新的人員、車輛和任務(wù)邊界信息，結(jié)果具有實(shí)際的可執(zhí)行性。一階段分區(qū)結(jié)果縮小了二階段優(yōu)化范圍，降低了計(jì)算難度。

對(duì)于某區(qū)域（工作日），以完成該日工作任務(wù)所需全部車輛行駛路程之和最小為目標(biāo)，建立日前作業(yè)路徑滾動(dòng)優(yōu)化模型如式（7）所示。

式中：Nd為d區(qū)域（工作日）內(nèi)作業(yè)點(diǎn)數(shù)量（包含緊急任務(wù)需求）；下標(biāo)0 表示出發(fā)地；yijk為整數(shù)變量；T2max為每車次人員單日最大工時(shí)；分別為車輛k到達(dá)作業(yè)點(diǎn)i、j的時(shí)間；tijk為i與j之間的路程行駛用時(shí)；vk為車輛k的平均行駛速度；STj為作業(yè)點(diǎn)j的最早日內(nèi)時(shí)間點(diǎn)時(shí)限；ETj為作業(yè)點(diǎn)j的最遲日內(nèi)時(shí)間點(diǎn)時(shí)限。

式（8）表示單日可用作業(yè)車輛約束；式（9）表示每車次人員單日最大作業(yè)時(shí)長(zhǎng)約束；式（10）和式（11）表示每個(gè)作業(yè)點(diǎn)有且僅有一輛車次完成；式（12）表示每輛作業(yè)車輛都是從出發(fā)地出發(fā)并返回；式（13）—式（15）表示作業(yè)點(diǎn)的時(shí)間點(diǎn)時(shí)限約束；式（16）表示每車次人員的單日最大工作用時(shí)約束；式（17）表示變量定義規(guī)則。

2 帶電作業(yè)路徑優(yōu)化決策支持系統(tǒng)

為將上述模型應(yīng)用于實(shí)際工作，需開(kāi)發(fā)相應(yīng)的路經(jīng)優(yōu)化決策支持系統(tǒng)，滿足所需人機(jī)交互、數(shù)據(jù)處理和仿真優(yōu)化等功能要求。根據(jù)帶電作業(yè)工作流程，將決策支持系統(tǒng)設(shè)計(jì)為以下3個(gè)模塊：

1）現(xiàn)場(chǎng)勘察模塊。用于采集工作任務(wù)數(shù)據(jù)，例如需求單位、線路名稱、工作內(nèi)容、定位地理位置、現(xiàn)場(chǎng)照片等，并將以上數(shù)據(jù)上傳至后端服務(wù)器。為實(shí)現(xiàn)信息的實(shí)地采集和實(shí)時(shí)傳輸，該模塊可開(kāi)發(fā)為移動(dòng)端應(yīng)用程序。

2）任務(wù)管理模塊。用于工作任務(wù)數(shù)據(jù)的管理和優(yōu)化，包括數(shù)據(jù)存儲(chǔ)、數(shù)據(jù)調(diào)用和仿真優(yōu)化，該模塊將執(zhí)行調(diào)用兩階段路徑優(yōu)化模型實(shí)現(xiàn)工作計(jì)劃的優(yōu)化編制。該模塊采用C/S架構(gòu)，包括任務(wù)管理Web、數(shù)據(jù)庫(kù)軟件和仿真優(yōu)化軟件。

3）現(xiàn)場(chǎng)作業(yè)模塊。用于工作計(jì)劃數(shù)據(jù)下載與執(zhí)行，工作結(jié)束后可用于統(tǒng)計(jì)作業(yè)項(xiàng)目、人員等現(xiàn)場(chǎng)數(shù)據(jù)。為方便實(shí)時(shí)獲取工作計(jì)劃和歸檔工作任務(wù)，該模塊應(yīng)開(kāi)發(fā)為移動(dòng)端應(yīng)用程序。

以上3 個(gè)模塊的開(kāi)發(fā)涉及人機(jī)交互系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)和仿真優(yōu)化系統(tǒng)，須借助開(kāi)發(fā)語(yǔ)言或軟件編程實(shí)現(xiàn)，本文采用以下方法：

1）人機(jī)交互系統(tǒng)。包括前端人機(jī)界面和后端交互服務(wù)，前端界面分別開(kāi)發(fā)基于Android 設(shè)備的移動(dòng)端應(yīng)用程序和基于PC 端的任務(wù)管理Web 界面，可采用HTML、CSS、JavaScript 或VUE 語(yǔ)言開(kāi)發(fā)，后端服務(wù)采用Java 開(kāi)發(fā)程序，前后端可通過(guò)建立Socket 通信進(jìn)行數(shù)據(jù)交互［17］。

2）仿真優(yōu)化系統(tǒng)。采用MATLAB 編寫兩階段路徑優(yōu)化模型算法.M 文件，并通過(guò)Java 和Mtalab 混合編程，實(shí)現(xiàn)任務(wù)管理模塊對(duì)仿真優(yōu)化模型的調(diào)用，一種高效方法是使用MATLAB“Delopment Tool”命令將.M文件編譯成Java軟件可調(diào)用的.Jar包［18-19］。

3）數(shù)據(jù)庫(kù)系統(tǒng)。采用MySQL 關(guān)系數(shù)據(jù)庫(kù)，通過(guò)JDBC（Java Data Base Connection）作為數(shù)據(jù)庫(kù)訪問(wèn)接口，實(shí)現(xiàn)任務(wù)管理系統(tǒng)與MySQL 數(shù)據(jù)庫(kù)的信息連接和交互訪問(wèn)［19］。

將路徑優(yōu)化決策支持系統(tǒng)架構(gòu)分為展示層、服務(wù)層與數(shù)據(jù)層，結(jié)構(gòu)關(guān)系如圖1所示。

圖1 帶電作業(yè)路徑優(yōu)化決策支持系統(tǒng)結(jié)構(gòu)

3 求解兩階段模型的混沌粒子群算法

粒子群優(yōu)化（Particles Swarm Optimization，PSO）是基于群體智能的隨機(jī)尋優(yōu)算法［20-22］，但尋優(yōu)過(guò)程中種群逐漸趨于單一，常常無(wú)法找到全局最優(yōu)解，為此文獻(xiàn)［21-22］提出了一種混沌粒子群優(yōu)化算法來(lái)增強(qiáng)搜索的多樣性，使得初始粒子能夠均勻分布，同時(shí)求解過(guò)程中對(duì)最優(yōu)粒子進(jìn)行變異，確保能夠跳出局部最優(yōu)。兩階段模型為離散型變量問(wèn)題，為了實(shí)現(xiàn)粒子與解的一一對(duì)應(yīng)，采取編碼方式為：以一階段作業(yè)任務(wù)組合模型的求解為例，對(duì)于M個(gè)作業(yè)點(diǎn)與D個(gè)區(qū)域的問(wèn)題，以0 代表出發(fā)地，以正整數(shù)i表示第i個(gè)作業(yè)點(diǎn)，隨機(jī)生產(chǎn)維度為M的作業(yè)點(diǎn)序列，并在該序列中插入D-1 個(gè)0，從而把該序列劃分為D段，每一段代表一個(gè)區(qū)域。

例如，作業(yè)點(diǎn)數(shù)目為8、區(qū)域數(shù)為4，某粒子的位置向量為［8 7 0 5 3 0 6 1 4 0 2］，則第1 個(gè)工作日的作業(yè)點(diǎn)為8、7，第2 個(gè)工作日的作業(yè)點(diǎn)為5、3，第3 個(gè)工作日的作業(yè)點(diǎn)為6、1、4，第4 個(gè)工作日的作業(yè)點(diǎn)為2。同樣的編碼方式可用于本文二階段路徑優(yōu)化問(wèn)題的求解。

采用以上改進(jìn)整數(shù)編碼的混沌粒子群優(yōu)化算法求解本文模型，兩階段方法的步驟如圖2所示。

圖2 兩階段優(yōu)化流程

4 算例分析

采用MATLAB 建立改進(jìn)整數(shù)編碼的混沌粒子群優(yōu)化算法，驗(yàn)證兩階段路徑優(yōu)化模型的有效性，種群規(guī)模取400，迭代次數(shù)取500，wmax、wmin分別取0.9、0.4，c1、c2分別取0.5、0.5。假設(shè)某地區(qū)周計(jì)劃涉及40 項(xiàng)帶電作業(yè)任務(wù)，工作地點(diǎn)地理位置橫縱坐標(biāo)在［0，100 km］內(nèi)隨機(jī)取值，出發(fā)地的坐標(biāo)為（50，50），各點(diǎn)之間的路程距離以直線距離代替，其中8 項(xiàng)任務(wù)有工作時(shí)限要求。各作業(yè)點(diǎn)位置如圖3 所示，作業(yè)用時(shí)、時(shí)限要求信息如表1 所示?，F(xiàn)有作業(yè)車輛為3 輛，每日出發(fā)時(shí)間為09：00，車輛行駛速度為40 km/h，每車次人員單日最大作業(yè)時(shí)長(zhǎng)為3 h，單日最大工時(shí)為7 h，緊急任務(wù)預(yù)留用時(shí)為1.5 h。

圖3 作業(yè)點(diǎn)分布

表1 作業(yè)點(diǎn)相關(guān)數(shù)據(jù)

圖4 為一階段周前作業(yè)任務(wù)組合模型優(yōu)化結(jié)果。從圖中可以看出40個(gè)作業(yè)點(diǎn)被分配至5個(gè)區(qū)域，分別對(duì)應(yīng)5 個(gè)工作日，區(qū)域的劃分滿足了特定作業(yè)點(diǎn)（1—8 項(xiàng)任務(wù)）的工作日時(shí)限要求。此外，從圖1 分區(qū)結(jié)果可以看出，一階段模型能夠?qū)崿F(xiàn)每個(gè)區(qū)域內(nèi)作業(yè)點(diǎn)在地理位置上相近的原則。區(qū)域、作業(yè)點(diǎn)及工作日具體對(duì)應(yīng)關(guān)系見(jiàn)表2。

圖4 任務(wù)組合結(jié)果

表2 任務(wù)組合結(jié)果

圖5 為二階段日前作業(yè)路徑滾動(dòng)優(yōu)化結(jié)果。根據(jù)一階段區(qū)域劃分（考慮日前緊急任務(wù)需求后），二階段模型依次對(duì)每個(gè)工作日進(jìn)行作業(yè)路徑優(yōu)化，得到了車輛最優(yōu)行駛路徑，從圖5 結(jié)果可以看出，各作業(yè)路徑滿足由近及遠(yuǎn)、路徑閉環(huán)的優(yōu)化目標(biāo)，證明了二階段模型的有效性。完成算例所述40 項(xiàng)作業(yè)任務(wù)，需要5 個(gè)工作日、12 輛車次，累計(jì)最短行駛里程1 879 km，各作業(yè)路徑均能滿足日最大作業(yè)用時(shí)、日最大工作用時(shí)約束以及特定作業(yè)點(diǎn)的時(shí)間點(diǎn)時(shí)限要求，具體結(jié)果見(jiàn)表3。

表3 路徑優(yōu)化結(jié)果

圖5 路徑優(yōu)化結(jié)果

5 結(jié)語(yǔ)

配電網(wǎng)帶電作業(yè)地點(diǎn)位置分散、分布廣泛，工作計(jì)劃成為影響工作效率的顯著因素。為此，提出了帶電作業(yè)路徑的兩階段優(yōu)化方法，一階段作業(yè)任務(wù)組合模型用于周前分區(qū)優(yōu)化，二階段作業(yè)路徑滾動(dòng)優(yōu)化模型用于日前路徑優(yōu)化，一、二階段模型有效解決了周前與日前兩個(gè)時(shí)間尺度的協(xié)調(diào)問(wèn)題，該方法實(shí)現(xiàn)了作業(yè)任務(wù)的最優(yōu)組合和路徑選擇，能夠有效降低車輛行駛里程、提升工作效率。

同時(shí)提出了路徑優(yōu)化決策支持系統(tǒng)開(kāi)發(fā)方法，該系統(tǒng)可應(yīng)用于帶電作業(yè)任務(wù)管理的輔助決策和實(shí)時(shí)調(diào)度。