交通运输网络的最短路线问题
摘要最短路问题（shortest-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点（通常是源节点和阱节点）之间总权和最小的路径就是最短路问题。最短路径问题是图论解决的典型问题之一，可用来解决交通运输、管路铺设、线路安装、厂区布局和设备更新等实际问题。遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。在运用遗传算法时，我们先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选适应性高的解，再用这些适应性高的解衍生出更好的解，然后再筛选，再衍生。反复迭代一定次数，可以得到近似最优解。本文介绍了图论最短路径问题及遗传算法，并应用图论最短路径问题的分析方法，运用遗传算法，解决仓库选址的问题。86911
本文分四个部分来讨论：
第一部分：阐述交通运输网络的研究背景及意义；
第二部分：介绍最短路径问题的基本思想及算法；
第三部分：介绍遗传算法及其图论模型；
第四部分：应用遗传算法实现最短路问题。
毕业论文关键词：赋权图；最短路线；遗传算法
Abstract Shortest-path problem: if each edge of the network has a value(means length, cost, time, etc),then find the total weight and the minimum path between the two given nodes (usually the source node and the sink node)。The shortest path problem is one of the typical problems in graph theory，it can be used to solve problems in transportation, pipeline laying, line installation, plant layout and equipment updates and other practical fields。The genetic algorithm is the core of Darwin's survival of the fittest survival of the fittest evolutionary theory。 In the use of genetic algorithms, firstly, we create a lot of solutions randomly, and then find a reliable evaluation system, to select the highly adaptive solution, then these adaptive high solutions derivative to produce a better solution, and then screen, then derived them。The approximate optimal solution can be obtained by repeating iteration of a certain number of times。This paper introduces the shortest path problem of graph theory and its algorithm ,and the analytical method for the shortest path problem in graph theory is used to solve the problem of warehouse location。
This paper is pided into four parts to discuss:
First chapter:This paper describes the background and significance of the research on the transportation network。
Second chapter:The basic idea and the classical algorithm of the shortest path problem are introduced。
Third chapter:Introduce the genetic algorithm and its graph theory model。
Fourth chapter: The application of genetic algorithm to achieve the shortest path problem
Keywords: Weighted graph; Shortest path; Genetic algorithm
目 录
第一章 绪论--1
1。1 研究背景--1
1。2 交通运输最短路线问题研究意义--1
1。4 本文的主要内容2
1。5 研究方法--3
第二章 预备知识4
2。1 图的概念--4
2。2 最短路问题4
2。2。1 交通运输模型问题的引入 ---4
2。2。2 最短路径问题--5
2。2。3 最短路问题算法的基本思想及基本步骤5
第三章 遗传算法--8
3。1 遗传算法的基本步骤8
3。2 适应函数-10
3。3 遗传算法的应用---11
结论--15
致谢--16
参考文献-17
第一章 绪论
1。1 研究背景
最短路问题的研究在上个世纪60年代以前就卓有成效了,求解网络图上节点间最短路径时,目前国内外一致公认的较好算法有Dijkstra算法和Floyd算法。1959年，荷兰著名计算机专家迪杰斯特拉对赋权图的问题首次提出有效算法即Dijkstra算法,该算法能够解决两指定点间的最短路,也可以求解图中一特定点到其它各顶点的最短路。但这种算法并不能解决含有负权的图的最短路问题。因此Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。1975年美国Michigan大学J。Holland教授提出了遗传算法（Genetic Algorithm），并且出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》。遗传算法是一种模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是通过模拟自然进化过程搜索最优解的方法。遗传算法是一种通用的算法框架，有很强的适应性，可以忽略具体条件，得到近似最优解。论文网