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

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

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

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

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

1 系統(tǒng)總體架構(gòu)設(shè)計

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

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

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

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

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

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

2 道路網(wǎng)結(jié)構(gòu)設(shè)計

2.1 道路網(wǎng)定義

露天礦道路網(wǎng)拓撲關(guān)系如圖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（關(guān)鍵點）。關(guān)鍵點屬于節(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（道路網(wǎng)）。道路網(wǎng)由有限的路段組成。

定義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，表示關(guān)鍵點范圍。圖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 道路網(wǎng)類結(jié)構(gòu)

根據(jù)道路網(wǎng)定義，節(jié)點與間斷點為基礎(chǔ)部分，節(jié)點序列組成路段，路段序列組成路徑，間斷點序列組成區(qū)域和導航路徑。據(jù)此，建立了點、路段、區(qū)域等道路網(wǎng)結(jié)構(gòu)，在此基礎(chǔ)上采用面向?qū)ο蠹夹g(shù)，首先建立了節(jié)點類與間斷點類，進而建立了路段類、區(qū)域類、路徑類、導航路徑類，后續(xù)開發(fā)的算法通過接口調(diào)用道路網(wǎng)結(jié)構(gòu)實體。類結(jié)構(gòu)屬性如圖3所示，各類之間的組合關(guān)系構(gòu)成了道路網(wǎng)數(shù)據(jù)結(jié)構(gòu)。

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

3 導航關(guān)鍵算法研究

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

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

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

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

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

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

（3）基于狀態(tài)轉(zhuǎn)移方程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之間的任意數(shù)，n為矩陣s的階數(shù)）尋找兩節(jié)點間是否存在插入點k，使得i節(jié)點經(jīng)過插入點到達j節(jié)點的距離最短，若s[i,k]+s[k,j]＜s[i,j]，則更新矩陣s與矩陣P對應(yīng)的值。

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

3.2 路網(wǎng)匹配算法

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

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

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

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

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

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

3.3 運行距離與時間預(yù)測算法

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

（1）定位點經(jīng)過道路匹配算法修正并匹配至對應(yīng)路段。

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

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

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

3.4 路口轉(zhuǎn)向提示算法

在交叉路口應(yīng)提示左右轉(zhuǎn)向，需要使用路口轉(zhuǎn)向提示算法，步驟為：

（1）定位點經(jīng)過路網(wǎng)匹配算法修正并匹配至對應(yīng)路段。

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

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

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

4 系統(tǒng)接口實現(xiàn)

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

4.1 導航算法接口

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

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

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

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

4.2 百度地圖接口

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

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

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

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

5 系統(tǒng)應(yīng)用開發(fā)

本研究以華能集團伊敏露天礦的道路網(wǎng)數(shù)據(jù)為基礎(chǔ)進行了導航系統(tǒng)開發(fā)，該系統(tǒng)包括獨立導航、百度地圖導航兩部分。獨立導航部分開發(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所示，界面中顯示了道路網(wǎng)，規(guī)劃了開始點到終止點的導航路徑，可實現(xiàn)對地圖的放大、縮小、平移等操作，實時顯示設(shè)備的當前位置，箭頭指向為設(shè)備的方位，同時每間隔固定時間提示到達目的地的距離與時間，在前方路口轉(zhuǎn)彎處可提示左轉(zhuǎn)、右轉(zhuǎn)。

5.2 百度地圖導航

5.2.1 地圖顯示與操作

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

5.2.2 路徑規(guī)劃

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

5.2.3 信息實時更新

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

6 結(jié)論

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

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

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