鐘小宇 趙慶豐 孫效玉 孫 健 肖開泰6

（1.鞍鋼集團鞍千礦業(yè)有限責任公司，遼寧鞍山112000；2.東北大學智慧礦山研究中心，遼寧沈陽110819；3.東北大學資源與土木工程學院，遼寧沈陽110819；4.紫金礦業(yè)集團股份有限公司，福建龍巖364000；5.鞍鋼集團礦業(yè)公司，遼寧鞍山112000；6.煤科集團沈陽研究院有限公司通風防滅火研究分院，遼寧撫順113112）

露天礦道路網是露天礦設備行駛的道路和關鍵點（裝載點、卸載點、停車場、加油站等）的集合，通常分為固定道路、半固定道路、移動道路、臨時道路4種類型，具有空間形態(tài)復雜、路段性質與動態(tài)變化不一的特點［1］。露天礦運輸設備規(guī)格大，駕駛室在卡車左側，前方與右方視線被遮擋，存在較大盲區(qū)與安全隱患［2］。露天礦生產環(huán)境復雜，存在灰塵、風沙、夜間照明效果不佳、能見度較低等問題［3］。上述特點導致駕駛員在行駛過程中容易走錯路，行駛的安全性較低。因此，開發(fā)露天礦導航系統十分必要。

目前導航系統按平臺可大致分為3類：基于地理信息系統平臺的導航系統［4］（借助 ArcGIS［5］、MapX［6］、SuperMap［7］、MapGIS［8］等軟件提供的二次開發(fā)接口開發(fā)導航系統），基于電子地圖服務的導航系統（借助百度地圖 API［9］、GoogleMap API［10］等提供的二次開發(fā)接口開發(fā)導航系統），基于自主開發(fā)式電子地圖的導航系統（借助Unity3d［11］、C++［12］等自主開發(fā)導航系統）。

針對露天礦運輸設備運行過程中存在的問題，結合當前導航技術的最新進展，設計了系統總體架構與道路網絡結構，自主開發(fā)了后臺的標準算法接口（導航路徑規(guī)劃算法、路網匹配算法、運行距離與時間預測算法和路口轉向提示算法）。考慮到部分露天礦山采用了卡車調度系統，但缺乏導航功能，因此開發(fā)了適用于卡車調度終端的獨立導航；針對部分露天礦山沒有安裝卡車調度終端的問題，開發(fā)了百度地圖導航，可用于手機等其它終端。

1 系統總體架構設計

系統總體架構如圖1所示，本研究將系統總體架構分為數據訪問層、業(yè)務邏輯層、接口層、應用層4層，各部分特征論述如下。

（1）數據訪問層。數據訪問層主要實現對基礎數據、流水數據、道路網數據的訪問。基礎數據存儲設備、司機、生產計劃等基礎信息；流水數據存儲車載終端上傳的數據，包括設備位置、狀態(tài)、速度、方向等信息；道路網數據為露天礦道路網的數據信息。

（2）業(yè)務邏輯層。業(yè)務邏輯層實現系統業(yè)務邏輯的處理，為后臺標準算法，接口層將其封裝為接口，應用層通過接口調用后臺標準算法，包括導航路徑規(guī)劃、路網匹配、運行距離與時間預測、路口轉向提示算法。導航路徑規(guī)劃算法用于規(guī)劃起點到終點的導航路徑，路網匹配算法用于將定位點進行修正并匹配至對應的路段上，運行距離與時間預測算法用于計算到達目的地的距離，路口轉向提示算法用于判斷前方路口左右轉向，進而進行語音提示。

（3）接口層。接口層將業(yè)務邏輯層的算法進行封裝，給外部應用提供了訪問接口，分為導航算法接口、百度地圖接口兩部分。其中，導航算法接口包括導航路徑規(guī)劃算法、路網匹配算法、運行距離與時間預測算法、路口轉向提示算法接口；百度地圖接口包括地圖初始化、折線繪制、覆蓋物添加等接口，用于實現前端圖像繪制。

（4）應用層。應用層分為獨立導航、百度地圖導航兩部分。獨立導航通過調用導航算法接口實現導航功能，獨立導航主要用于車載終端；百度地圖導航通過調用導航算法接口與百度地圖接口實現導航功能，百度地圖導航主要用于手機等其他移動終端。

通過以上架構可知，接口層將應用層的應用與業(yè)務邏輯層的標準算法分開，應用層各部分的應用可以通過接口層的接口調用標準算法，使得系統能夠解決實際問題，適用于不同礦山，加快了開發(fā)進度，加強了系統的實用性、通用性、擴展性。

2 道路網結構設計

2.1 道路網定義

露天礦道路網拓撲關系如圖2所示，具體定義論述如下：

定義1（節(jié)點）。節(jié)點是礦區(qū)坐標系中任意一點，包含坐標x、y、z，是道路分岔口、路段起始點或終止點，節(jié)點所組成的集合為B={ }B1,B2,B3,…,Bn,n∈N。

定義2（間斷點）。間斷點是礦區(qū)坐標系中的任意一點，包含坐標x、y、z，間斷點與間斷點間由直線連接，間斷組成的集合為A={ }A1,A2,A3,…,An,n∈N。

定義3（關鍵點）。關鍵點屬于節(jié)點，記為kx，x∈N，其中kx∈B，表示排卸點、停車場、加油站等露天礦地點。

定義4（路段）。路段起始于一節(jié)點Bi連接于另一節(jié)點Bj,i,j∈N，由一系列有序的間斷點依次連接成的 直 線 所 組 成 ，可 表 示 為 rs:Bi—Bj,i,j∈N，其 中Bi、Bj∈ B，。圖2中B1—B2為路段。

定義5（道路網）。道路網由有限的路段組成。

定義6（路徑）。起始于一節(jié)點終止于一節(jié)點的有序的路段集合，可表示為rp:B1—B2—B3—…—Bn,n∈N，其中B1,B2,B3,…,Bn∈ B。圖2中B1—B2—B4為路徑。

定義7（區(qū)域）。由有序的間斷點依次連接成的直線組成的多邊形，可表示為 aq:C1—C2—C3—…—Cn,n∈N，其中C1,C2,C3,…,Cn∈A，表示關鍵點范圍。圖2中C1—C2—C3—C4—C5為區(qū)域。

定義8（導航路徑）。起始于一節(jié)點終止于一節(jié)點的有序的間斷點集合，可表示為np:A1—A2—A3—…—An,n∈ N，其中 A1,A2,A3,…,An∈ A。圖 2中A1—A2—A3—A4為導航路徑。

2.2 道路網類結構

根據道路網定義，節(jié)點與間斷點為基礎部分，節(jié)點序列組成路段，路段序列組成路徑，間斷點序列組成區(qū)域和導航路徑。據此，建立了點、路段、區(qū)域等道路網結構，在此基礎上采用面向對象技術，首先建立了節(jié)點類與間斷點類，進而建立了路段類、區(qū)域類、路徑類、導航路徑類，后續(xù)開發(fā)的算法通過接口調用道路網結構實體。類結構屬性如圖3所示，各類之間的組合關系構成了道路網數據結構。

節(jié)點類：點名稱表示關鍵點的名稱，坐標x、y、z表示關鍵點的位置。間斷點類：坐標x、y、z為間斷點的位置。路段類：開始節(jié)點與終止節(jié)點為路段的開始節(jié)點號與終止節(jié)點號，間斷點集合為路段中所有間斷點實例的集合。路徑類：路段集合為路徑中所有路段實例的集合。導航路徑類：間斷點集合為導航路徑上所有間斷點實例的集合，路段集合為導航路徑中所有路段實例的集合，路徑類為后臺各算法服務，導航路徑類則用于為前端返回最終路徑的詳細間斷點坐標，以具體的間斷點集合來表示。區(qū)域類：一個區(qū)域對應一個間斷點集合，間斷點為區(qū)域多邊形的頂點。

3 導航關鍵算法研究

3.1 導航路徑規(guī)劃算法

導航路徑規(guī)劃算法即根據當前位置、目的地位置、道路網數據返回當前位置到達目的地的路徑。

道路網可視為圖的數據結構，定義為G(V ,E)，V為頂點，E為邊。常用最短路算法有Floyd（弗洛伊德［13］）、Dijkstra（迪杰斯特拉［14］）、Bellman-Ford（貝爾曼-福特［15］）等，算法的時間復雜度（未經其他措施進行算法優(yōu)化）分別表示為O(V3)、O(V2)、O(V E)。露天礦道路網中不存在負權值的邊，道路網節(jié)點（頂點V）有數百個，數據規(guī)模較小，對于時間復雜度要求不高，相比于其他算法，Floyd算法更適用于多源最短路徑，運用一次算法就可求得任意兩個頂點的最短路徑，且簡單易用，故本研究選取該算法作為導航路徑規(guī)劃算法。

利用數據結構中圖的思想，構建了節(jié)點與節(jié)點之間的鄰接矩陣S（n×n階矩陣，n為節(jié)點數量）。為存儲圖中節(jié)點到節(jié)點的距離，建立了矩陣P（n×n階矩陣，n為節(jié)點數量）記錄兩個節(jié)點之間的插入點。Floyd最短路徑算法步驟如下：

（1）初始化鄰接矩陣S。當兩個節(jié)點有通路時，依次計算兩個節(jié)點間的相鄰間斷點的直線距離，累加即可得到兩個節(jié)點間的最短距離。當兩個節(jié)點無通路時，設置該距離為所用數據類型的最大值。當兩個節(jié)點相同時，設置距離為0。

（2）初始化矩陣P。矩陣P中的元素值為所在列的下標值，經過兩次循環(huán)遍歷矩陣P為元素賦初始值。

（3）基于狀態(tài)轉移方程s[i,j]=min{s[i,k]+s[k,j],s[i,j]}（i、j為矩陣行標、列標，s[i,j]為第i節(jié)點到第j節(jié)點間的距離，k為0至n之間的任意數，n為矩陣s的階數）尋找兩節(jié)點間是否存在插入點k，使得i節(jié)點經過插入點到達j節(jié)點的距離最短，若s[i,k]+s[k,j]＜s[i,j]，則更新矩陣s與矩陣P對應的值。

（4）在P矩陣中得到起始點、插入點、終止點所組成的節(jié)點序列。

3.2 路網匹配算法

由于GNSS的定位精度較低及道路更新不及時，定位點與實際的道路可能存在偏離，需通過路網匹配算法進行修正，以匹配至正確的路段上。

路網匹配算法大致可以分為4類［16］：幾何匹配算法［17］、拓撲關系算法［18］、概率統計算法［19］、先進匹配算法［20］。露天礦道路網的拓撲關系較簡單，幾何匹配算法在道路網拓撲關系較簡單的情況下匹配穩(wěn)定性較好，故本研究選用了幾何匹配算法。幾何匹配算法可細分為點到點、點到線、線到線匹配算法，點到線匹配算法比點到點匹配算法準確性高，比線到線的匹配算法計算量小，故選用基于幾何學點到線的路網匹配算法。步驟為：

（1）定義垂線長度l、定位點所在路段號R、垂足坐標C，進行初始化：l=+∞、R=-1、C=(0,0)。

旅行社實現規(guī)范化經營管理有很長的路要走。應完善相關制度體系，按照規(guī)范化管理的要求穩(wěn)步推進各項工作有序開展。在進行旅游產品創(chuàng)新時，旅行社應積極尋求有關部門支持，實現旅游地和旅行社的雙贏。各地應提高對旅游業(yè)發(fā)展的重視程度，鼓勵旅行社研發(fā)具有地方特色的旅游產品和開展規(guī)范化運營，從而帶來豐厚的經濟效益。

（2）由定位點X直線序列中的直線（由路段中相鄰間斷點連接而成）作垂線，若直線遍歷完畢，則退出并輸出垂足坐標C與所在路段R。若垂足的x、y坐標值不在直線上，則繼續(xù)執(zhí)行步驟（2），否則，執(zhí)行步驟（3）。

（3）若垂線長度小于l，則將l更新為該垂線的長度，并將C更新為該垂足，將R更新為直線所在的路段，繼續(xù)執(zhí)行步驟（2）。

3.3 運行距離與時間預測算法

定位點實時更新時，應實時顯示當前定位點與目的地的距離以及行程時間。將定位點與道路的關系簡化為點到線的關系，距離應等于修正后的點在匹配路段的剩余長度與導航路徑中其他路段長度的總和。算法步驟為：

（1）定位點經過道路匹配算法修正并匹配至對應路段。

（2）基于距離最近原則匹配對應路段中距離定位點最近的間斷點，以該間斷點開始到對應路段尾間斷點結束，依次累加相鄰間斷點的距離，得出本路段的剩余長度。

（3）遍歷導航路徑中的剩余路段，依次累加所遍歷路段的間斷點序列中相鄰間斷點的距離，得出導航路徑中剩余路段的長度。

（4）累加步驟（2）與步驟（3）中計算的長度，得出定位點至終止點的距離，退出算法。

3.4 路口轉向提示算法

在交叉路口應提示左右轉向，需要使用路口轉向提示算法，步驟為：

（1）定位點經過路網匹配算法修正并匹配至對應路段。

（2）若定位點與路段尾節(jié)點距離小于50，則執(zhí)行步驟（3），否則，退出算法。

（3）令當前路段的起始節(jié)點坐標、終止節(jié)點坐標分別為A(x1,y1)、B(x2,y2)，導航路徑中下一路段終止節(jié)點坐標為P(x3,y3)，令轉向因子s=(x1-x3)?(y2-y3)-(y1-y3)·(x2-x3)。

（4）若s＞ 0，返回“左轉”；若s＜ 0，返回“右轉”，退出算法。

4 系統接口實現

系統的部分功能通過調用接口層所封裝的算法接口來實現，部分功能在其上進行擴展，故而本研究首先實現了系統的接口，然后對獨立導航、百度地圖導航進行開發(fā)。接口實現如下：

4.1 導航算法接口

（1）導航路徑規(guī)劃算法接口。double［］The Shotest Path（int startPoint，int endPoint），規(guī)劃開始節(jié)點到終止節(jié)點間的導航路徑，其中startPoint為開始節(jié)點，endPoint為終止節(jié)點，返回的double類型數組為路徑的間斷點集合。

（2）路網匹配算法接口。double［］The Road Network Matching（double x，double y，double z），將定位點進行修正并匹配到路段上，其中x、y、z為定位點的x、y、z坐標值，double數組前3位為修正后的x、y、z坐標值，第4位為點所在的路段號。

（3）運行距離與時間預測算法接口。double Update Distance（double x，double y，double z，int［］path-Section），獲取到達目的地的距離，其中x、y、z為定位點的x、y、z坐標值，pathSection數組為導航路徑的路段集合，返回的double類型值為到達目的地的距離。

（4）路口轉向提示算法接口。string Turn Around（double x，double y，double z，int［］pathSection），判斷路口左右轉向，其中x、y、z為定位點的x、y、z坐標值，pathSection數組為導航路徑的路段集合，返回的string類型值為左右轉向。

4.2 百度地圖接口

（1）地圖初始化接口。center And Zoom（center:Point，zoom：Number），地圖初始化，Point為地圖中心，Number為級別。

（2）折線繪制接口。Polyline（points：Array＜Point＞，opts：PolylineOptions），創(chuàng)建折線覆蓋物對象，Array＜Point＞為折線的轉折點，Polyline Options為線的屬性。

（3）標注創(chuàng)建接口。Marker（point：Point，opts：Marker Options），創(chuàng)建圖像標注實例，Point為標注的坐標，Marker Options為標注的屬性。

（4）覆蓋物添加接口。add Overlay（overlay：Overlay），將覆蓋物實例（折線、標注等）添加到地圖中，Overlay為覆蓋物。

5 系統應用開發(fā)

本研究以華能集團伊敏露天礦的道路網數據為基礎進行了導航系統開發(fā)，該系統包括獨立導航、百度地圖導航兩部分。獨立導航部分開發(fā)語言為C#語言，采用Visual Studio 2015為開發(fā)工具，運行環(huán)境為.NET Framework 4；百度地圖導航部分開發(fā)語言為Java、HTML、CSS、JavaScript，采用 eclipse jee 2019 為開發(fā)工具，java開發(fā)工具包為jdk1.8.0_91。

5.1 獨立導航

終端界面如圖4所示，界面中顯示了道路網，規(guī)劃了開始點到終止點的導航路徑，可實現對地圖的放大、縮小、平移等操作，實時顯示設備的當前位置，箭頭指向為設備的方位，同時每間隔固定時間提示到達目的地的距離與時間，在前方路口轉彎處可提示左轉、右轉。

5.2 百度地圖導航

5.2.1 地圖顯示與操作

導航系統的地圖顯示與操作界面如圖5所示。界面最左側提供了顯示控制控件，點擊控件或通過鼠標的點擊、移動可實現地圖的放大、縮小、平移功能，分別如圖5（a）、圖5（b）和圖5（c）所示。

5.2.2 路徑規(guī)劃

導航系統的路徑規(guī)劃界面如圖6所示，分別提供了二維地圖、衛(wèi)星地圖兩種顯示模式，如圖6（a）和圖6（b）所示。圖中560、680、二破為排卸點，2005、1205為裝載點，箭頭為當前設備的定位點，箭頭方向為設備的朝向，開始點為設備的起始位置，終點為設備的目的地，圖中規(guī)劃了從一號機修廠前往裝載點2005的導航路徑。

5.2.3 信息實時更新

導航設備的位置、到達目的地的距離與時間、路口轉向等信息會實時更新，界面如圖7所示?？ㄜ噺囊惶枡C修廠前往裝載點2005，運行至中途某點，箭頭為設備的當前位置，到達裝載點的距離為7.22 km?；跉v史行車數據，統計該車的平均速度為20 km/h，預測該車到達裝載點2005需耗時21.66 min。

6 結論

（1）將露天礦導航系統總體架構分為數據訪問層、業(yè)務邏輯層、接口層、應用層4層，接口層為應用層與業(yè)務邏輯層之間的橋梁，具有較強的通用性、實用性和擴展性。

（2）基于Floyd算法、路網匹配算法、運行距離與時間預測算法、路口轉向提示算法，開發(fā)了導航路徑規(guī)劃、定位點修正與路段匹配、到達目的地的運行距離與行程時間預測、路口轉向提示等功能，導航功能全面、實用、可靠。

（3）導航算法與應用有效分離，通過接口實現有效銜接，既可實現自主獨立運行，用于卡車調度系統終端；也可兼容百度地圖，用于手機App導航，通用性和擴展性強。