矿山乘人索道路径规划算法研究与软件实现

发布时间：2018-04-01 21:45

本文选题：K最短路径　切入点：三维可视化　出处：《山东科技大学》2017年硕士论文

【摘要】：巷道架空乘人索道作为矿井下重要的辅助运输设备,对其运输线路的最短路径规划研究不仅可为井下救援提供保障,而且有效提高工时利用率和保存工人体力,从而提高工作效率,矿山巷道乘人索道可视化为井下路径规划提供决策支持。对于井下架空乘人路径规划问题,现有算法存在方向不明确、不适合处理大量数据,不适用于井下交通规划,且不适于k条最短路径的求解问题。本文面向井下实际交通网络的特征,对k最短路径(K Shortest Paths, KSP)问题进行研究,采用参数驱动方法建立巷道架空乘人索道及其路径的三维模型,并实现其三维可视化。论文具体研究如下:(1)针对求解两节点间k最短路径,A*算法中启发函数设定精确性难以控制,从而导致效率不高的问题,本文通过启发函数优化并结合背离路径思想提出k最短路径优化算法(HO-D KSP算法),通过实验证明,该算法相较于A*算法在计算效率上提高15.9%。(2)针对目前最短路径算法中存在预处理工作繁杂、存储数据量大的问题,本文通过有向图顶点分裂运算,采用添加有向边从而获得路径的思想,提出了一种基于顶点分裂运算的求解单源节点间k最短路径算法,从根源上减少待保存的数据量,提高算法效率。实验结果表明,该算法时间复杂度和空间复杂度优于传统的k最短路径算法。(3)对三维巷道乘人索道路径规划进行软件设计,包括其架构设计、可视化设计,并对巷道乘人索道及其路径规划进行可视化建模。
[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.
【学位授予单位】：山东科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TD52;TP301.6

【参考文献】