1。2 交通运输最短路线问题研究意义

最短路径的算法问题是图论中的核心问题之一，也是许多更深层次算法的基础。同时，最短路问题有着大量的实际运用的背景。最短问题与很多问题从表面上看并没有什么关系，但这些问题也可以归结为最短路问题。例如：线路安装、管路铺设、厂区布局和设备更新等实际问题。在更加注重效率的现在，如何快速的实现一些问题，诸如：必要的道路交通网，消防选址的高效性，企业生产的节约成本，网络数据传输的减少能耗，灾难发生时的快速逃生，抓捕罪犯时的最佳路线选择等问题。最短路问题作为这些问题的基础，可以作为一个参考。比如，可以利用最短路问题算出逃生时的最短路线，这样在灾难发生时，可以直接利用最短路线快速逃生，挽救更多生命。

1。3 交通运输最短路线问题国内外研究现状与发展

1。4 本文的主要内容

将交通运输网络最短路线问题的模型建立与讨论划分为分为四个部分来讨论：

（1）绪论。介绍最短路问题的研究现状和背景意义，阐述本文主要内容。

（2）预备知识。在该部分引入了所有需要用到的相关知识，为讨论该问题打下一个基础。

（3）交通运输网络的图论模型的建立。运用图论，数学建模，运筹学等知识建立相关数学模型，以便解决后续问题。

（4）最短路问题的解决的讨论。应用遗传算法，处理复杂的交通运输最短路线问题，以此达到我们研究该问题的最终目的。

1。5 研究方法

运用遗传算法来实现图论中的交通运输网络的最短路问题。遗传算法是基于生物进化原理的一种全局性优化算法，是一种模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型。本文主要运用遗传算法的思想，通过选择，交叉，变异来求出最短路线问题的近似最优解。

第二章 预备知识

 2。1图的概念

   定义 2。1。1一个图定义为一个偶对，记作，其中

   （1）是一个集合，其中的元素称为顶点；

   （2）是无序积的一个子集合，则其元素称为边；

集合中的元素可以在中出现不止一次。

    我们分别用和表示图的顶点集合与边的集合。如果和都是有限集合，则称为有限图；否则称为无限图。

定义 2。1。2 一个有向图定义为一个偶对，其中

   （1）是个非空集合，其元素称为顶点；

   （2）是有序积的其中一个子集，则其元素称为弧。

 根据有向图的定义，与一条弧有关联的两个端点都具有一定的次序关系（弧是顶点和的有序对）。我们称为弧的起点，为终点。如果对有向图的每一条弧表示从起点到终点作一条矢线，方向是从指向，即有向图的每一条弧都有确定的方向。因此，有向图就是每一条边都有一定方向的图。文献综述

定义 2。1。3如果图中任意一条边上都附有一个数，则我们称这样的图为赋权图，称为边上的权。

定义2。1。4如果图是赋权图并且,,如果是到的路的权,那么，则称为的长,长最小的到的路称为最短路。

若要找出从到的通路,使全长最短,即。

最短路问题是图论中的经典问题。

2。2最短路径问题

2。2。1交通运输模型问题的引入 

交通运输要求满足最短路径。已知共有个节点，从节点到节点的距离为。

以总路程最小为目标函数构造模型如下: