当前位置: > 硕士毕业论文 > 51200字硕士毕业论文快速寻路优秀地理信息系统网络数据结构规划及算法研究

51200字硕士毕业论文快速寻路优秀地理信息系统网络数据结构规划及算法研究

论文类型:硕士毕业论文
论文字数:51200字
论点:算法,短路,网络
论文概述:

本文针对大规模GIS道路网络,在D.Schultes 02005)提出的层次数据结构基础上,进一步考虑GIS道路网络中存在车辆通行限制(吨位限制)的情形,对GIS网络的数据结构进行重新建构,并给出相应的最

论文正文:

引言

路径优化问题是组合优化中的经典问题。在物流优化决策中,如从原材料采购到生产制造,从制造到仓储,从配送中心到每个配送终端,从回收点到回收中心,都会遇到路径优化问题。路径优化的目标通常用道路网络中边缘的权重来表示。根据不同的求解要求,目标函数可以是路径距离、行驶时间、成本等。
随着地理信息系统在物流领域的广泛应用,物流软件业对大型复杂路网中的快速路径优化提出了计算要求。Dijkstra算法目前广泛应用于单个源点的最短路径问题。该算法能有效解决一般规模的最短路径问题,但对于大规模复杂路网,仍然存在较大的时延,不能满足地理信息系统在物流优化决策支持中的应用要求。然而,一些文献中采用的启发式算法不能保证最优,不能普遍应用于物流优化决策。
对地理信息系统道路网的地理信息系统网络结构进行了重构,设计了分层数据结构设计,并给出了相应的算法,实现了快速路径优化,有效支持物流决策的实时计算功能。

1。1研究背景

现代物流管理的快速发展对提高物流水平提出了严峻的要求。然而,在物流配送过程的每个环节都存在快速路径优化的问题:从仓库到仓库物流的仓库,从仓库到配送中心和配送中心到每个配送点,从回收转运站到回收终端,在回收物流中存在寻找单点、单点、多点和多点的最短路径问题。在整个过程中,最短路径求解的目标在不同的应用环境中有不同的实际意义,可能是最短的总距离或最短的总时间。在物流管理中,实际问题中最短目标的含义主要是从物流成本和物流效益的角度给出的。例如,在将货物从交货点交付给客户的过程中,客户可能是具有非常高优先级的客户,并且要求货物在第一时间交付。在这种情况下,需要从物流效益中的顾客满意度指数出发,找到以最短的总时间为目标的最佳配送路径。
信息技术的发展和商业日益国际化推动了物流管理的发展。除了一些垄断行业之外,全球化促进了企业间的竞争成为完全竞争。为了提高核心竞争力,企业不仅要考虑如何增加利润,还要注意控制总成本。因此,降低物流总成本也成为影响企业竞争力的因素之一。做好企业物流管理的路径规划,在复杂的配送网络中及时有效地获取最优配送路径,为物流企业改进管理方法、降低管理成本、提高经济效益、最终提升核心竞争力提供了机遇。
随着地理信息系统在物流管理中的广泛应用,实际路径优化问题的规划和解决依赖于地理信息系统的路网图。地理信息系统可以在可视化界面上以图文并茂的方式显示路网的地理信息和属性信息,并具有良好的数据存储功能,可以直观、科学地提供决策支持。物流配送通常出现在大规模的道路网络图中。道路网的范围可能是社区、城市,同时也可能发生在整个国家或整个大陆。地理信息系统路网图中物流配送的路径优化属于大规模最短路径问题。
实际地理信息系统网络地图中的实时批量路径优化问题可以多次视为解决单一源点的最短路径问题。目前,图论中已经提出了许多经典的最短路径算法。在第三章中,本文将详细回顾和评价单点算法。可以发现,这些算法在大规模路网中的实施主要表现出两个不足:
1。最短路径问题的最优解算法需要很长时间来处理大规模网络图的数据,因此,要获得最优路径,需要等待很长的响应时间。最短路径优化算法中的经典Dijkstra算法解决了从网络中的一个点到所有其他点的最短路径。在大规模网络图中搜索最短路径时,当获得从单点到单点或从单点到某个多点的最短路径时,Dijkstra算法的大规模搜索和大量数据处理会延长等待结果的时间。

3算法概述……19-28
3.1优化算法……19-26
3.1.1标签方法……19-20
3.1.2高炉和高炉煤气处理算法……20-22
3.1.3迪克斯特拉算法……22-23
3.1.4迪卡姆,迪卡巴……23-24
3.1.5 PAPE,二_ _问……24-25[/比尔/] 3.1.6阈值算法……25-26 [/BR/] 3.1.7拓扑排序……26 [/溴/] 3.2启发式算法……26-28
4地理信息系统网络的层次结构……28-43
4.1主干道网络建设……28-31
4.1.1主要道路歧视标准……[28-30/BR/]4 . 1 . 2主要道路歧视……30-31[/比尔/] 4.2……主干道网络4.3多级31-32
……32-34
4.4地理信息系统网络的层次数据结构……34-43
5基于地理信息系统的多层主干道网……43-53
5.1双向搜索算法……43-44 [/BR/] 5.2双向搜索算法……44-46 [/BR/] 5.3双向搜索算法……[46-47/BR/]5.4基于地理信息系统的多级主干道……47-53

总结
本章总结了本文的研究工作,并提出了进一步的研究方向。
基于舒尔茨02005提出的分层数据结构,针对大规模的地理信息系统道路网络,进一步考虑了地理信息系统道路网络中的交通约束(吨位约束)情况,重构了地理信息系统网络的数据结构,并给出了相应的最短路径优化算法。研究内容包括:
1。利用地理信息系统路网节点数量少、路网有限、道路交通有限的特点,采用两阶段法识别主干道,构建底层主干道网络,通过图形的压缩处理方法构建多层主干道网络。