考慮時(shí)空特征的機(jī)器人VRP問題求解方法

張 煒，賓冬梅，梁俊斌

（1.廣西電網(wǎng)有限責(zé)任公司電力科學(xué)研究院，廣西 南寧 530023；2.廣西大學(xué)廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530004）

1 引言

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

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

VRP問題具備典型的時(shí)空分布特征，其應(yīng)用研究不局限于交通運(yùn)輸方面，且已拓展至電網(wǎng)布局等方面［8］。……