考慮時空特征的機器人VRP問題求解方法

張 煒，賓冬梅，梁俊斌

（1.廣西電網(wǎng)有限責任公司電力科學研究院，廣西 南寧 530023；2.廣西大學廣西多媒體通信與網(wǎng)絡技術重點實驗室，廣西 南寧 530004）

1 引言

變電站巡檢的項目、周期、方式及要求均有明確規(guī)范，是電力生產(chǎn)中的常規(guī)工作，也是占據(jù)運行人員精力的主要工作。近年來，變電站巡檢機器人已在電力行業(yè)推廣運用，并深刻改變了設備巡檢模式［1-2］。變電站機器人巡檢系統(tǒng)由變電站機器人、本地監(jiān)控后臺、遠程集控后臺、機器人室等組成，能夠通過全自主或遙控模式開展變電站的紅外熱成像、可見光、噪聲等檢測作業(yè)，提高工作效率和質(zhì)量，緩解結(jié)構(gòu)性缺員等問題［3-4］。其中，變電站機器人由移動載體、通信設備和檢測設備等組成的，采用遙控或全自主運行模式，用于變電站設備巡檢作業(yè)的移動巡檢裝置。

變電站巡檢機器人管理模式分為集控管理和分布管理。隨著機器人鋪開推廣，電網(wǎng)企業(yè)紛紛建設了遠程集控后臺，并研究應用了可集中調(diào)配管理轄區(qū)內(nèi)機器人的集控管理模式［5-6］。集控管理模式的優(yōu)勢在于可以在不同變電站之間調(diào)配機器人資源，充分應用數(shù)量有限的機器人。在此前提下，考慮多機器人、多起點、多時間窗等組合優(yōu)化條件的轉(zhuǎn)移運用車輛路徑問題（Vehicle Routing Problem，VRP），成為提升機器人整體調(diào)配效率的關鍵。此類問題是基于單臺機器人路徑規(guī)劃問題的延伸應用，但是問題求解難度隨參與調(diào)配機器人的數(shù)量不同而呈指數(shù)級增長［7］。

VRP問題具備典型的時空分布特征，其應用研究不局限于交通運輸方面，且已拓展至電網(wǎng)布局等方面［8］。變電站機器人VRP的優(yōu)化目標是指在遍歷巡檢不同變電站過程中，給出一組總行程最短的調(diào)度方案集合［8］。當前變電站機器人路徑規(guī)劃方面的研究工作僅側(cè)重于機器人在站內(nèi)行走的路徑長短、安全避障及動作難度［9-11］，缺少機器人在變電站之間轉(zhuǎn)移運用的路徑規(guī)劃研究。同時，簡單依靠人工經(jīng)驗決策、基于排隊論的傳統(tǒng)靜態(tài)問題等物流算法，又容易陷入局部最優(yōu)、過程復雜等局限［12-13］。論文針對機器人群體的互動時空特征，考慮以巡維中心、變電站為節(jié)點構(gòu)成的點線網(wǎng)絡，提出針對機器人群體調(diào)度分配過程中VRP問題的路徑規(guī)劃算法，得到開放式的路徑方案。

2 VRP問題描述

2.1 設備巡檢

變電站巡檢包括日巡、夜巡，通常有人值班站日巡每日一次，夜巡每周一次；無人值班站日巡、夜巡每月一次。特殊情況時，將靈活調(diào)整巡檢項目、周期、次數(shù)等。變電站機器人可針對14類設備，執(zhí)行74項巡檢任務。因為變電站的分布位置、設備數(shù)量、場地規(guī)模不同，所以機器人的巡檢區(qū)域、任務點及耗時等也存在差異［14］。解決調(diào)配巡檢機器人路徑規(guī)劃的VRP問題，需綜合考慮巡檢機器人電量、路途耗時、巡檢周期、停留充電等因素。

2.2 路徑規(guī)劃

路徑規(guī)劃是指搜索空間網(wǎng)絡中位置之間最小成本函數(shù)的路徑［15］。路徑規(guī)劃技術在機器人自主運行、無人機避障飛行、城市道路網(wǎng)規(guī)劃、物流交通管理等領域應用廣泛，有助于分析解決拓撲為點線網(wǎng)絡的規(guī)劃問題［16］。調(diào)度分配變電站機器人是電網(wǎng)企業(yè)制定電力生產(chǎn)周期性巡檢計劃的內(nèi)容，同樣面臨著機器人群體路徑規(guī)劃的VRP問題。

調(diào)配單臺變電站機器人是指在已知變電站節(jié)點位置、路徑參數(shù)等拓撲網(wǎng)絡布局及巡檢項目情況下，機器人個體以最短路徑巡檢全部變電站。調(diào)度分配多臺變電站機器人，則可以理解為求解機器人群體的最優(yōu)路徑組合，但最優(yōu)路徑目標難以協(xié)調(diào)一致。

調(diào)度分配多臺變電站機器人的VRP問題可以描述為：多臺巡檢機器人從屬的不同巡維中心出發(fā)，赴不同變電站巡檢，在不浪費工作時間（充電、巡視、途中及回傳數(shù)據(jù)）的前提下，以最短路徑遍歷巡檢既定的變電站。當前主要依靠人工經(jīng)驗決策、基于排隊論的傳統(tǒng)靜態(tài)問題物流算法制定調(diào)配變電站機器人的路徑策略［17-18］，未能基于時間及空間特性研究運行規(guī)則，故難以實現(xiàn)對機器人群體路徑規(guī)劃所需的全局最優(yōu)。

3 機器人調(diào)度分配算法

3.1 基于時空三維坐標系的路徑規(guī)劃

在調(diào)配單臺變電站機器人個體時，僅需基于遍歷式尋優(yōu)思路提出路徑最短的巡檢方案，屬于“一對多”的路徑規(guī)劃。但在調(diào)度分配多臺變電站機器人群體時，還需考慮機器人所在的不同位置，進而提出組合優(yōu)化后的路徑規(guī)劃。機器人群體調(diào)度分配受到機器人當前部署位置、變電站分布位置及工作時間等時空限制條件。論文以變電站的橫、縱坐標為第一維和第二維，以時間為第三維，建立“時間-空間”分析框架，并基于時空三維坐標系中提出機器人的“時空路徑”，求解VRP問題。首先建立基于變電站位置構(gòu)建平面二維坐標的宏觀路網(wǎng)；其次梳理距離、能耗等約束條件，構(gòu)建考慮時間窗的時空三維坐標系；最后遍歷搜索各機器人的可選路徑，并提出解決VRP的調(diào)配方案?？紤]時間窗的時空三維坐標系有助于滿足時空約束條件，得到最優(yōu)路徑規(guī)劃［19-20］。

3.2 路徑規(guī)劃的約束條件

調(diào)度分配變電站機器人群體的VRP問題需面對路徑規(guī)劃過程中的時限和距離這兩項約束條件。

一方面，時限約束是指機器人完成站內(nèi)巡檢任務所需的工作時間，但是由于變電站的設備數(shù)量、場地規(guī)模不同，導致機器人所需工作時間各不相同，即時間窗存在差異［14］，并成為與傳統(tǒng)VRP問題解決方案的主要區(qū)別。另一方面，距離約束是指機器人全部巡檢一輪變電站所需轉(zhuǎn)運的路徑最短。

為求解機器人群體路徑規(guī)劃的最優(yōu)組合，透過基于時間窗的時空三維坐標系分別處理機器人個體的轉(zhuǎn)運路徑，即可避免陷入局部最優(yōu)和繁復計算。

3.3 群體路徑規(guī)劃算法

調(diào)度分配機器人群體算法采用啟發(fā)式原理，可在路徑規(guī)劃過程中逐步收斂至全局最優(yōu)解，算法基本流程，如圖1所示。

圖1 路徑規(guī)劃算法Fig.1 The Algorithm of Path Planning

（1）輸入待巡檢變電站、機器人所屬巡維中心的數(shù)量、坐標及巡檢所需時間窗，構(gòu)建基于時間窗的時空三維坐標系，并設置迭代次數(shù)為N以及迭代次數(shù)最大值Nmax；其中巡維中心的數(shù)量為A；

（2）將m臺機器人隨機均勻地部署在A個巡維中心，初始化機器人k已巡檢的站點集Ck以及待巡檢站點集；初始設置已完成巡檢任務的機器人數(shù)量l=0；

同時，設置巡維中心數(shù)量的最大值Amax，設置機器人的總數(shù)量的最小值mmin，其中，每個巡維中心配置（1～3）臺機器人，即mmin≥Amax。例如，Amax為100，即巡維中心實際最大值為100，可設置的mmin為100。

（3）當機器人k電量至少滿足巡檢一座目標站點時，則將機器人k轉(zhuǎn)運至目標站點j，并更新機器人k已巡檢的站點集Ck以及待巡檢站點集；

同時，m臺機器人隨機選擇一座變電站為始發(fā)站點，機器人k由站點i出發(fā)至下一目標站點j，并由轉(zhuǎn)運概率遴選轉(zhuǎn)運路徑，轉(zhuǎn)運概率的計算方式如下：

（4）如果待巡檢站點集≠?，至少有一個待巡檢站點的任務量滿足機器人k當前電量，則轉(zhuǎn)（3）；否則轉(zhuǎn)（5）；

（5）如果待巡檢站點集≠?，機器人k當前電量不滿足完成剩余待巡檢站點的任務量，則在當前站點充電，使其恢復充足的電量，并轉(zhuǎn)（3）；否則，轉(zhuǎn)（6）；

（6）如果待巡檢站點集≠?，并且機器人k當前最后剩余的巡檢站點附近不是巡維中心班部所在站點，則令其返回至最近的巡維中心；如果已完成巡檢任務的機器人數(shù)量小于機器人的總數(shù)量，即l＜m，轉(zhuǎn)（3）；否則，轉(zhuǎn)（7）；

（7）所有機器人完成既定巡檢任務后，則更新其電量需求，具體如下：

當所有機器人完成一次重復轉(zhuǎn)運計算迭代后，各邊上的節(jié)點電量需求由以下公式更新：

式中：ρ—電量需求中的測算因子；

Δτij—邊（i，j）上的電量需求變化量；

Δτijk—第k臺機器人在邊（i，j）上的電量需求量；

Q—機器人完成一次轉(zhuǎn)運所釋放的電量需求總量；

Lk—機器人所經(jīng)過的路徑距離。

（8）由已巡檢的變電站節(jié)點集Ck得到m臺機器人的路徑集L=｛L1，L2…Lm｝，根據(jù)（3）～（6）計算并記錄本次迭代得到的最優(yōu)路徑集，同時更新全局的最優(yōu)解；

（9）迭代計算，如果同一最優(yōu)解連續(xù)出現(xiàn)m次，則轉(zhuǎn)（10），否則轉(zhuǎn)（11）；

（10）分別向m臺機器人輸出方案；

赭曲霉毒素A（OTA）是由多種生長在糧食（小麥、玉米、大麥、燕麥、黑麥、大米等）、蔬菜等農(nóng)作物上的曲霉和青霉產(chǎn)生的[1-3]。目前，小麥、大麥、玉米等谷類作物中OTA的測定方法有薄層色譜法（TLC）、酶聯(lián)免疫吸附法（ELISA）[2-7]、高效液相色譜法（HPLC）[3]和膠體金免疫快速定量檢測法（GICT）[4]。本研究對常用的三種檢測方法即HPLC、ELISA和GICT進行了考察，從儀器、人員和時間等多方面論證了三種檢測方法的優(yōu)劣，從最低檢出限、定量限、回收率、精密度和重復性等參數(shù)分析了三種檢測方法的精確度，為日益復雜的檢測需求提供了多種選擇[8-11]。

（11）如果迭代次數(shù)達到Nmax，但仍未連續(xù)出現(xiàn)m次最優(yōu)解，則停止迭代計算，并向運維決策人員提出手動配置建議。

4 算例分析

某供電局的3臺機器人分布在3個巡維中心，需外出完成12座戶外式無人變電站的日巡工作。機器人充電后工作時長不小于9h。給定待巡檢站點的名稱、相對坐標、數(shù)量、時間窗，如表1所示。

表1 時間窗約束條件Tab.1 The Constraints of Time Windows

根據(jù)表1所示內(nèi)容，繪制機器人在巡維中心、各站點之間的群體互動時空分布圖，如圖2所示。

利用群體互動時空分布圖，算法尋找潛在的下一時空節(jié)點，就簡化為機器人在各站點相對坐標、時間圓柱的交集。圖2中的X軸、Y軸構(gòu)成平面二維坐標，表示巡維中心和變電站的空間位置；垂直坐標（T軸）上的時間圓柱表示完成巡檢所需時間。

圖2 群體互動時空分布圖Fig.2 The Diagram of Group Interaction

通過機器人群體調(diào)度分配算法求解3 臺機器人VRP 分別在12 個節(jié)點之間轉(zhuǎn)移運用路徑，通過遠程集控后臺輸出滿足距離最小等約束條件的調(diào)配方案，三臺機器人的路徑規(guī)劃，如表2所示。

表2 路徑規(guī)劃方案Tab.2 The Scheme of Path Planning

圖3 輸出的路徑規(guī)劃方案Fig.3 The Scheme of Path Planning

5 結(jié)論

基于時空特征的變電站機器人路徑規(guī)劃算法，針對機器人群體調(diào)度分配過程中的VRP問題，考慮時限和距離這兩項約束條件，遍歷式搜索最優(yōu)路徑，提出組合優(yōu)化后的路徑規(guī)劃方案，實現(xiàn)充分應用機器人資源。其主要特點在于：

（1）在考慮多機器人、多起點的路徑參數(shù)等拓撲網(wǎng)絡布局情況下，針對多目標站點的路徑規(guī)劃逐步收斂至全局最優(yōu)解，通過啟發(fā)式遍歷搜索可選路徑的方式，避免陷入路徑方案的局部最優(yōu)。

（2）以變電站的橫、縱坐標為第一維和第二維，以巡檢所需時間為第三維，構(gòu)建時空三維坐標系，用于分析滿足時空約束條件，避免路徑陷入復雜計算，有助于得到最優(yōu)路徑規(guī)劃。