最短路径算法在物流运输中地应用

《最短路径算法在物流运输中地应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档本科生毕业设计（论文）题目：线性表的设计和实现学生姓名：张三学号：201107011153院系：基础科学学院信息技术系专业年级：2012级信息与计算科学专业指导教师：李四　注：1.论文封面单独打印一张纸；中英文摘要正反打印一张纸；目录、正文、参考文献、致谢、附录均独立正反打印！2.部分专业对格式有特殊要求的，教学院（系）可自行商定。年月日标准文案实用文档摘要随着现代物流业的发展，如何优化和配置物流的运输路径成为了一个热点的问题。其中，最具代表性的问题就是如何在一个道路网络中选择两点之间的合适路径

2、，使其距离最短。为了解决这个问题，本文介绍了两种最常用的最短路径求解方法——DIJKSTRA算法与FLOYD算法，分析了它们的适用范围以及时间复杂度。最后，对一个具体的航空公司物流配送问题进行了求解，得到了理论最优路径。关键词：最短路径问题；DIJKSTRA算法；物流运输标准文案实用文档ABSTRACTWiththedevelopmentofmodernlogisticsindustry,howtooptimizeandconfigurethetransportpathoflogisticshasbec

3、omeahotissue.Amongthem,themostrepresentativeproblemishowtoselecttheappropriatepathbetweentwopointsinaroadnetworktominimizethedistance.Inordertosolvethisproblem,thispaperintroducestwomostcommonshortestpathsolutions——DijkstraalgorithmandFloydalgorithm,anda

4、nalyzestheirapplicationrangeandtimecomplexity.Finally,aspecificairlinelogisticsdistributionproblemissolved,andthetheoreticaloptimalpathisobtained.Keywords：Minimumpathproblem；Dijkstraalgorithm；Logisticstransportation标准文案实用文档目录第一章引言11.1研究背景11.2研究现状11.2.1最短

5、路径算法研究现状11.2.2最短路径算法分类2第二章最短路径问题的基本理论知识32.1最短路问题的定义32.2最短路问题的Dijkstra算法32.2.1Dijkstra算法的局限性32.2.2Dijkstra算法求解步骤32.2.3Dijkstra算法的时间复杂度42.2.4简单案例分析42.3最短路问题的Floyd算法52.3.1算法定义52.3.2算法思想原理52.3.3算法过程描述62.3.4算法适用范围62.3.5算法简单实例6第三章实际案例分析73.1问题描述73.1.1问题的背景及假设73

6、.1.2符号说明73.2模型的建立与求解83.2.1模型一83.2.2模型二10第四章总结154.1优点15标准文案实用文档4.2缺点15参考文献16致谢17附录18附录A实际案例背景数据18标准文案实用文档第一章引言1.1研究背景在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E],连接两点u和v的边用e(

7、u,v)表示。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。1.2研究现状本节主要讨论两个方面的问题，首先简要回顾最短路径算法研究现状，然后概要总结最短路径算法分类。1.2.1最短路径算法研究现状最短路径问题一直是计算机科学、运筹学、地理信息科学等学科领域的研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有

8、效结合使得新的最短路径算法不断涌现。常用的路径规划方法有:平行最短路径搜索算法，蚁群算法，基于矩阵负载平衡的启发算法,EBSP*算法和Dijkstra算法等。创门在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色但是因为Dijkstra算法可以给出最可靠的最短路径，并且容易实现，所以备受青睐和并被广泛应用。经典的Dijkstra算法的时间复杂度为，直接应用到大规模城市路网时，最短路径查询时间难以令人接受，专家学者纷纷开展Dijkst