本文選題：K最短路徑　切入點(diǎn)：三維可視化　出處：《山東科技大學(xué)》2017年碩士論文

【摘要】：巷道架空乘人索道作為礦井下重要的輔助運(yùn)輸設(shè)備,對(duì)其運(yùn)輸線路的最短路徑規(guī)劃研究不僅可為井下救援提供保障,而且有效提高工時(shí)利用率和保存工人體力,從而提高工作效率,礦山巷道乘人索道可視化為井下路徑規(guī)劃提供決策支持。對(duì)于井下架空乘人路徑規(guī)劃問(wèn)題,現(xiàn)有算法存在方向不明確、不適合處理大量數(shù)據(jù),不適用于井下交通規(guī)劃,且不適于k條最短路徑的求解問(wèn)題。本文面向井下實(shí)際交通網(wǎng)絡(luò)的特征,對(duì)k最短路徑(K Shortest Paths, KSP)問(wèn)題進(jìn)行研究,采用參數(shù)驅(qū)動(dòng)方法建立巷道架空乘人索道及其路徑的三維模型,并實(shí)現(xiàn)其三維可視化。論文具體研究如下:(1)針對(duì)求解兩節(jié)點(diǎn)間k最短路徑,A*算法中啟發(fā)函數(shù)設(shè)定精確性難以控制,從而導(dǎo)致效率不高的問(wèn)題,本文通過(guò)啟發(fā)函數(shù)優(yōu)化并結(jié)合背離路徑思想提出k最短路徑優(yōu)化算法(HO-D KSP算法),通過(guò)實(shí)驗(yàn)證明,該算法相較于A*算法在計(jì)算效率上提高15.9%。(2)針對(duì)目前最短路徑算法中存在預(yù)處理工作繁雜、存儲(chǔ)數(shù)據(jù)量大的問(wèn)題,本文通過(guò)有向圖頂點(diǎn)分裂運(yùn)算,采用添加有向邊從而獲得路徑的思想,提出了一種基于頂點(diǎn)分裂運(yùn)算的求解單源節(jié)點(diǎn)間k最短路徑算法,從根源上減少待保存的數(shù)據(jù)量,提高算法效率。實(shí)驗(yàn)結(jié)果表明,該算法時(shí)間復(fù)雜度和空間復(fù)雜度優(yōu)于傳統(tǒng)的k最短路徑算法。(3)對(duì)三維巷道乘人索道路徑規(guī)劃進(jìn)行軟件設(shè)計(jì),包括其架構(gòu)設(shè)計(jì)、可視化設(shè)計(jì),并對(duì)巷道乘人索道及其路徑規(guī)劃進(jìn)行可視化建模。
[Abstract]:As an important auxiliary transportation equipment under the mine, the study on the shortest path planning of the transportation route can not only provide protection for the underground rescue, but also effectively improve the man-hour utilization rate and preserve the physical strength of the workers. In order to improve the working efficiency, the visualization of mine roadway by ropeway provides decision support for downhole path planning. For the problem of underground aerial passenger path planning, the existing algorithms are not clear in direction and are not suitable for dealing with a large number of data. It is not suitable for underground traffic planning and is not suitable for solving the problem of k shortest path. In this paper, the problem of k shortest path K Shortest paths (KSPs) is studied in view of the characteristics of underground traffic network. In this paper, the three-dimensional model of roadway ropeway and its path is established by parameter-driven method. And realize its 3D visualization. This paper studies as follows: 1) the precision of the heuristic function in solving the k shortest path between two nodes is difficult to control, which leads to the problem that the efficiency is not high. In this paper, the k shortest path optimization algorithm is proposed by heuristic function optimization and the idea of deviation path. It is proved by experiments that the k shortest path optimization algorithm is HO-D KSP algorithm. Compared with the A * algorithm, the algorithm improves the computational efficiency by 15.9. 2) aiming at the problems of complex preprocessing and large amount of data storage in the current shortest path algorithm, the vertex splitting operation of directed graph is adopted in this paper. Based on the idea of adding directed edges to obtain the path, a new algorithm based on vertex splitting is proposed to solve the k shortest path between single source nodes, which can reduce the amount of data to be saved and improve the efficiency of the algorithm. The time and space complexity of the algorithm is better than that of the traditional k shortest path algorithm. The visual modeling of laneway passenger ropeway and its path planning is also carried out.
【學(xué)位授予單位】：山東科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TD52;TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 楊大明;;新版煤礦安全規(guī)程解讀——技術(shù)裝備及應(yīng)急救援規(guī)定的主要調(diào)整[J];煤炭科學(xué)技術(shù);2017年01期

2 羅毅;;巷道斷面形狀對(duì)井下避險(xiǎn)設(shè)施承受爆炸沖擊載荷的影響[J];煤礦安全;2017年01期

3 孫付偉;康全玉;涂興子;;香山礦大傾角架空乘人裝置[J];煤礦安全;2016年12期

4 王瑞;林敏;盧志剛;;基于VB的某鐵礦山地表沉陷預(yù)警信息系統(tǒng)開(kāi)發(fā)[J];金屬礦山;2016年10期

5 趙禮峰;于汶雨;;求解k最短路徑問(wèn)題的混合遺傳算法[J];計(jì)算機(jī)技術(shù)與發(fā)展;2016年10期

6 宋克志;王夢(mèng)恕;譚忠盛;侯洪超;劉桂賓;;渤海海峽跨海通道地形三維可視化建模技術(shù)與實(shí)現(xiàn)[J];隧道建設(shè);2016年02期

7 胡春華;李萍萍;;樹(shù)木三維可視化建模技術(shù)研究述評(píng)[J];南京林業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年06期

8 王春英;;如何做好煤炭經(jīng)濟(jì)的可持續(xù)發(fā)展[J];現(xiàn)代經(jīng)濟(jì)信息;2015年16期

9 李偉;;煤礦井下輔助運(yùn)輸?shù)陌l(fā)展[J];山東工業(yè)技術(shù);2015年09期

10 付媛;朱禮軍;韓紅旗;;K最短路徑算法與應(yīng)用分析[J];情報(bào)工程;2015年01期

相關(guān)博士學(xué)位論文 前1條

1 廖遠(yuǎn);一對(duì)一最短路徑算法研究及車載導(dǎo)航系統(tǒng)設(shè)計(jì)[D];南昌大學(xué);2012年

相關(guān)碩士學(xué)位論文 前7條

1 于汶雨;K最短路徑問(wèn)題的研究與應(yīng)用[D];南京郵電大學(xué);2016年

2 梁娟;網(wǎng)絡(luò)最短路徑問(wèn)題的研究與應(yīng)用[D];南京郵電大學(xué);2015年

3 黃峰;礦山三維巷道建模關(guān)鍵技術(shù)研究[D];中南大學(xué);2014年

4 盧國(guó)菊;礦井災(zāi)變時(shí)期最優(yōu)避災(zāi)救災(zāi)路徑研究[D];太原理工大學(xué);2013年

5 倪燕;金屬礦山井下災(zāi)害人員逃生最優(yōu)路徑研究[D];中南大學(xué);2013年

6 王紅娟;三維實(shí)體建模及布爾運(yùn)算造型技術(shù)[D];山東科技大學(xué);2007年

7 張前哨;基于A*算法的地圖尋徑的研究[D];武漢科技大學(xué);2005年

，

本文編號(hào)：1697442