基于PgRouting 圖計算的人員精確定位軌跡還原技術

閆啟宏 李 健 杜朋浩

（貴州黔西能源開發有限公司，貴州 黔西 551500）

1 引言

煤礦井下人員定位系統在遏制超定員生產、事故應急救援、領導下井帶班管理、特種作業人員管理、防止人員進入危險區域、及時發現未按時升井人員、持證上崗管理、井下作業人員考勤等方面發揮著重要作用。楊娟等（2015）[1]等根據煤礦井下巷道分布特點,應用RSSI 定位算法,提出基于節點協作的精確定位算法。魏霜（2014）[2]利用煤礦企業現有的工業數據網絡,基于物聯網技術設計了一種煤礦井下人員實時精確定位系統。

目前市場主流人員精確定位系統的人員軌跡展示，都是基于預先繪制的預設定路徑，即將相鄰定位設備以一定方式進行連接，然后按照預設軌跡和當前設備狀態進行人員軌跡計算，大多采用樹形結構，其拓撲模型用存儲點和弧段的編號描述圖形之間的關系，對所有可能性路線進行窮舉。

這種展示方式存在幾個問題：（1）以定位設備二維坐標為中心，當設備發生位移或替換后需要重新計算；（2）設備坐標與巷道拓撲關系耦合度高，需要專業軟件技術人員進行操作，無法適應煤礦動態變化；（3）計算結果無GIS 數據庫支持拓展性不高，無法進行預設外的軌跡路徑計算。

隨著礦山物聯網技術的發展，基于UWB 等窄帶物聯技術的人員精確定位硬件解決方案日趨成熟，為井下人員定位的研究[3]提供了新的思路和理論基礎。本文在前人研究的基礎上，以貴州黔西縣青龍煤礦為研究實例，提出了一種基于pgRouting圖計算的人員精確定位軌跡還原技術，精確還原了人員井下運動軌跡，取得較好效果。

2 PgRouting 簡介

pgRouting 是 以PostGIS/PostgreSQL 地 理 空 間數據庫為基礎進行路徑分析，從起點開始計算與各點的最短路徑和終點的最短路徑之和，逐個取出找到最短路徑。

pgRouting 安裝先下載編譯包后解壓縮，將lib目錄下文件復制到PostgreSQL 的lib 目錄下，在PostgreSQL 數據庫中執行share/contrib 目錄下的sql腳本即可。

此解決方案優點是：數據和屬性可由許多客戶端修改，例如QGIS 通過JDBC、ODBC 或直接使用Pl/pgSQL。數據更改可以通過路由引擎即時反映，無需預先計算。其核心功能包括：

（1）所有最短路徑組合（Johnson 算法）；

（2）所有最短路徑組合（Floyd-Warshall 算法）；

（3）最短 A* 路徑；

（4）雙向 Dijkstra 最短路徑；

（5）雙向 A* 最短路徑；

（6）Dijkstra 最短路徑；

（7）行車距離；

（8）K-最短路徑，多候選路徑；

（9）K-Dijkstra，一對多最短路徑；

（10）旅行銷售人員（Traveling Sales Person）；

（11）TRSP（Turn Restriction Shortest Path）。

3 解決思路

3.1 以導向點數據構建井巷工程拓撲關系

煤礦井巷工程是在地質體內開掘的，同一水平巷道存在T 形交叉、Y 形交叉、十字形交叉、X 形交叉、錯位交叉等常規拓撲結構。因巷道功能不同，不同水平的井巷工程從空間上存在立體分離式交叉、立體交叉等復雜的空間關系。相比地面路網，其拓撲關系比路網更加復雜，空間屬性更強，且井巷工程會隨著煤礦的生產過程中開拓、打密閉阻斷等過程，不斷改變現有拓撲關系。因此構造井巷工程拓撲關系的基本數據要采用煤礦常用的勘探設計數據和生產過程數據，便于收集，易于維護，能夠映射客觀世界。

一般煤礦會根據地質勘測資料和礦井設計，計算導向點的坐標，并根據導向點坐標來指導實際現場施工。地質、測量相關科室和部門會根據實際施工進展情況定期更新和維護導向點坐標，因此可以作為構建GIS 空間數據的基礎數據。

3.2 人員軌跡數據的采集

人員定位系統為滿足國家數據采集要求，按《煤礦安全生產在線監測聯網備查系統通用技術要求和數據采集標準》要求提供數據生成工具。該工具可以連接人員定位系統主備機服務器，根據人員數據變化情況，生成符合標準格式要求的交換文件。精確定位系統會根據人員移動情況，生成具有三維坐標的軌跡數據。

架設數據采集服務器（圖1），使用Flume 對交換文件進行偵聽。當每10 s 產生交換文件后，將報文內容抽取至Kafka 消息中間件進行數據緩存，同時將數據推送給前端GIS 和大數據解決方案進行持久化。

圖1 人員軌跡數據采集

3.3 人員軌跡數據還原

如圖2 所示，巷道共有D1～D4 四個導向點數據。P1、P2 為人員精確定位間隔10 s 間推送的2 次坐標數據。前端渲染頁面如直接按P1-＞P2 的數據進行繪制，將產生P1 至P2 虛線效果，與實際不符。

圖2 人員軌跡數據還原

因此，需要對人員軌跡數據坐標進行還原，即補齊中間缺失的D2、D3 坐標數據，構建P1-＞D2-＞D3-＞P2 的軌跡坐標數據，使人員模型按照巷道進行移動。

4 軌跡還原的實現方法

軌跡還原的技術路線如圖3 所示。

4.1 以導向點坐標構建拓撲計算

根據采掘工程平面圖，按巷道逐個提取導向點坐標，并構造拓撲節點表。如圖4 所示巷道共由四個導向點構成。

（1）按表1 數據結構創建拓撲表，用以存放圖計算的點坐標數據。

表1 點坐標數據表

（2）按巷道，組織導向點數據，填充源頂點、目標頂點坐標。

（3）根據源頂點、目標頂點坐標，構造線段計算長度，并填充cost 字段。

（4）調用PgRouting 的拓撲計算函數pgr_createTopology，對拓撲表進行填充，構建井巷工程拓撲關系。

4.2 基于實時數據的軌跡繪制

人員軌跡數據中人員位置是精確定位系統推送的北京54 坐標系的經緯度和高程數據。根據兩次推送的坐標數據對人員模型以動畫方式進行移動。需要以下幾個步驟：

（1）根據人員坐標數據查找最近的拓撲節點ID。根據導向點數據自動生成拓撲頂點表，是PgRouting 的核心數據對象，根據圖計算的方式自動生成各導向點之間的拓撲關系。根據PostGis 提供的空間計算函數stdistance，求取距離開始坐標最近的拓撲節點。

（2） 利 用PgRouting 的 圖 計 算 函 數pgr_dijkstra，根據源頂點和目標頂點ID，求取途徑的拓撲節點ID。該函數可以按開始節點和結束節點，自動計算所有途徑節點ID 及導向點。

（3）人員軌跡還原。根據途徑拓撲節點的坐標構建途經路線，比照人員軌跡數據的開始坐標和結束坐標，對途經路線進行截取，并將人員途徑最終軌跡返回。

5 試驗效果

基于該技術的系統在貴州能化青龍煤礦運行10個月，共截取1200 人/天的人員軌跡數據進行測試，該算法對局部巷道復雜拓撲結構、定位分站設備缺失、人員軌跡數據缺失具有極強的魯棒性。平均GIS 人員位置顯示和實際位置誤差不超過0.3 m，滿足實時性要求。

6 結論及展望

該技術以圖技術為基礎，以煤礦導向點為節點，根據連接關系構建邊數據，進而構建空間拓撲關系。路徑規劃不用預先以窮舉方式進行設定，具體軌跡數據還原等算法不依賴于某系統，根據人員或設備的絕對經緯度坐標即可進行軌跡還原。

該技術可以通過維護兩節點之間的cost、reverse_cost 等屬性，可以動態改變拓撲關系，如打密閉或局部發生災變后，可進行動態拓撲關系計算，將現有無向圖動態改變成有向圖應用方式，在避災路線計算等應急指揮方面也有明顯優勢。