交通中最优线路问题的数学模型.doc

武汉工业学院毕业论文论文题目：交通中最优线路问题的数学模型姓 名 吴惠平 学 号 061201222 院 （系） 数理科学系 专 业 信息与计算科学 指导教师 同小军 2010年 6 月 15日目 录摘 要IAbstractII1.引言11.1课题来源11.2 课题简介11.3 交通中最优线路问题的研究现状11.4 论文章节安排2本章小结22.最优线路及最优线路的评价标准22.1最优线路的定义及评价指标22.2最优线路评价指标的量化32.2.1 最短出行线路的量化32.2.2 最少换乘次数的量化32.2.3 最低票价的量化4本章小结43.Floyd算法43.1 Floyd算法的基本原理43.2 Floyd算法构造距离矩阵的原理53.2.1 Floyd算法步骤53.2.2 回溯法求最短路径53.3 Floyd算法改进63.3.1改进Floyd算法原理63.3.2改进Floyd算法的计算步骤6本章小结64.多维Floyd算法74.1 算法的基本思想74.1.1建立赋权有向图D74.1.2 构造路由矩阵T74.1.3 构造统计矩阵S84.1.4 迭代过程94.2算法的基本步骤10本章小结115.Dijkstra算法介绍1151 Dijkstra算法原理115.2 Dijkstra算法的基本步骤125.3 Dijkstra算法与基本Floyd算法时间复杂度的比较12本章小结136.Floyd算法实例应用136.1 问题的提出136.2 问题分析1462.1 问题一的分析1462.2 问题二的分析1562.3 问题三的分析166.3 问题求解166.3.1问题一的求解166.3.2问题二的求解176.3.3问题三的求解186.4 问题的结果196.4.1问题一的汽车最优路线196.4.2问题二的汽车和地铁最优路线226.4.3 问题三的最优线路22本章小结22谢 辞23参考文献24附 录26 摘 要交通问题与城市经济和居民生活息息相关，建立以交通网络为基础的交通优化模型就显得尤为重要。本文以城市交通优化问题为例，研究了网络交通优化问题的数学模型。在已有Floyd算法的基础上提出了多维Floyd算法。目前关于最佳出行线路的算法有很多，具有代表性的有Dijkstra算法、Floyd算法、Bellman算法等。但是现有的这些算法都只能解决单权最短路问题，对于多权最短路问题则无法解决，而实际交通优化问题均是多权网络交通优化问题。本文首先构造了向量矩阵，并定义了向量矩阵的运算方法，由此得到多维Floyd算法，该算法能够有效得解决多权网络交通优化问题。本文最后以北京市公交为例，建立了多权交通网，根据所采用的不同交通工具，分别讨论了从出发点A站到目的地B站的最优路线查询问题。运用向量Floyd算法建立该问题的数学模型，最后用C语言实现对该算法的求解。通过实例应用，进一步证明了该算法和模型的可行性和合理性。关键词：最优线路 赋权有向图 Floyd算法 多维Floyd算法AbstractTransportion problem is relevant to urban economy and residents life. So it is very important to establish the mathematical model of optimization of traffic based on transpatation network. In this paper,we take the urban transportation for an example, make a research about the optimization of traffic network problems of mathematical model. We proposed the multidimensional Floyd algorithm based on the existing Floyd algorithm. At present there are many algorithms on the best travel route， the representative algorithm is the Dijkstra algorithm, Floyd algorithm, Bellman algorithm and so on. However, these existing algorithms can only solve a single weight of shortest path problem, for the more weight the shortest path problem it can not solve. But the actual traffic optimization problems are multi-weight network traffic optimization. In this paper,we structured a multi-dimensional matrix first, then defined the methods of calculation about dimensional matrix. Last, resulting the multidimensional Floyd algorithm. The algorithm can solve the problem of multi-weight network traffic optimization effectively. At the end of this paper,we take the bus transportation network of Beijing for an example, based on the situation by means of transport , discuss the problem of points from starting point A to point B of the optimal destination route query respectively. We take multidimensional Floyd algorithm to establish the mathematical model of the optimal line . Then use C language solved the problem eventually. By an example application, proved the feasibility and rationality of the algorithm and the model further.Keywords: Best routes, Empowering directed graph, Floyd algorithm, Multidimensional Floyd algorithm.1.引言随着社会的发展，最优线路问题成为研究交通问题中的一个重要问题，在解决公交最佳出行线路、城市援救最佳线路、物流配送、高速公路联网收费等与人们日常生活密切相关问题中发挥着重要的作用。这些年来，城市的交通系统有了很大发展，为公众的出行等进行各项日常活动带来了很大的便利，但同时也面临着多条线路的选择问题。所以建立交通中最优线路问题的数学模型，为人们进行日常活动提供参考有很大的价值，是一个值得研究的课题。1.1课题来源 交通问题与我们的日常活动息息相关，随着社会的高速发展，交通工具越来越多，同时交通线路也越来越复杂，这就使得公众的出行面临着更多的选择。如何用最短的时间、花最少的钱到达目的地是人们密切关注的一个问题。如北京市的公交线路有800多条，上海市的公交线路有1000多条，去北京旅游，去上海看世界博览会等，都需要解决如何选择出行线路问题。因此选择最优线路出行显得更加重要。正因为它的重要性，所以本文选择研究建立交通中最优线路的数学模型给公众的出行提供参考。1.2 课题简介 本文主要研究如何建立交通中最优线路的数学模型。寻找最优线路问题即研究最短路径问题。一般来说最短路径问题分为单源最短路径和全源最短路径，现有的算法中Dijkstra算法1-6比较适合于求解单源最短路径，而Floyd算法7-9适合用于求解全源最短路径。本文首先对影响交通中最优线路的各因素进行量化处理，然后用Floyd算法求解全源最短路径，用改进的向量Floyd算法对模型进行优化。1.3 交通中最优线路问题的研究现状随着我国汽车工业与公路建设的不断发展和完善，公众的出行也更加通畅、便利，但同时也面临多条线路的选择问题。由于公众的个体差异较大，在城市客运交通中，影响公众路径选择的因素很多，一般来说，除了时间因素外，还有换乘因素、感观因素（行驶的安全性、景观、道路状况和舒适感）、经济因素（出行费用）和交通管制因素。1999年在南京市8个主要公交站点的乘客出行心理调查表明，公交乘客选择出行路径的决策过程主要受到“换乘次数”、“出行距离”和“出行耗时”三个因素的影响10。所建模型既应考虑不同乘客的个性要求，又要满足大多数乘客的出行要求。根据乘客的个性要求，依次主要考虑乘车方式、换乘次数、最短距离、乘车费用等因素，作为评价最优线路的依据。但这些因素又相互影响、相互制约，所有单目标下的最佳出行线路并不能满足大多数乘客的出行需求，因此，建立综合最佳线路的评价准则及最佳出行线路选择模型是非常必要的。建立交通中最优线路问题是数学模型的目的就是寻找最优路径，为公众做出出行决策提供参考。目前关于最佳出行线路问题的研究主要是一些传统算法和根据问题的特点对传统算法进行改造。具有代表性的有Dijkstra算法、Floyd算法、Bellman算法11；Angelica Lozano12研究了标号修正技术在综合运输网络中求解起点到终点的最短可行路径；Paola Modesti等13针对最小出行时间研究了求解综合运输网络最短路径问题，使用多标记图构建运输网络和对应的数据，并提出了求解算法。但这些已有的算法都不能解决出行线路双向选择、环形出行线路和多权问题，因此需要一种新的算法来建立交通中最优线路问题的数学模型。1.4 论文章节安排论文基本按照目录的安排进行，也是按照最优线路的数学模型的建立过程来叙述的。在文章的开始介绍了交通中最优线路的数学模型的课题简介和研究现状等。该课题主要就是算法说明，根据模型建立的过程一步一步完成叙述的，然后在现有算法的基础上对其进行改进，此论文还是比较容易的，简单说就是按照模型建立过程及算法改进过程进行论文的章节安排的。论文的最后一章将前面章节中研究的算法应用于解决一个实际问题，通过实例来进一步验证该算法和模型的可行性和合理性。本章小结：在本章中简单介绍了课题的来源、简介和研究现状。为了这个课题的论文能够更好的完成，在此之前作好论文的章节安排是很有必要的。作好这些必要的准备工作，为后续的章节奠定好基础。在好的基础上才能设计出和建造出好的上层“建筑”。2.最优线路及最优线路的评价标准2.1最优线路的定义及评价指标 所谓最优线路是指从起始位置到目的地的最优行走路径或方案14。 最优线路的评价指标15有很多，其中主要有最短距离法、最短时间法以及某些特定要求（如沿途风景足够多等）。针对不同的人群及要求，所选择的评价指标包括如下几种：（a）最短路径 所谓最短路径是指在起始站点到目的地的所有肯线路中寻求距离最短的一条线路作为最优出行线路，该方法充分考虑距离最短的要求，而对于换乘次数及票价消费考虑较少，或不考虑这次因素是影响；（b）最少换乘车次 换乘车次是指乘客完成一次出行过程所需的换乘次数，次数的多少是衡量出行线路的最优与否的又一关键因素，若换乘次数较多，出行者会放弃对公交的选择，转向其他更快捷的方式，此外在同一票价的公交运营体制下，换乘次数的增加也意味着票价消费的增加，理想的出行线路应该保证在最少的换乘次数的前提下达到目的地，大量实际调研表明，最优出行换乘次数不应超过3次7。（c）最低票价消费 一般来说，乘客从起始站点到达目的地可选择的交通工具有多种，途径也不是唯一的，最低票价消费即要求满足保证乘客到达目的地条件下所有票价总和最小。2.2最优线路评价指标的量化2.2.1 最短出行线路的量化 记为出行的起始点，为所要到达的目的地，表示从到所有可能路线的距离，为从起始站到终点站的第k条线路上相邻两站点的距离，则按照第k条线路行驶的总距离为： 而最短路径即为所有可能行驶线路距离的最小值，即： 其中，k0为从到所有可能线路中按最短距离所选的最优线路。2.2.2 最少换乘次数的量化 对乘客而言，从起始点到目的地可乘坐的交通工具主要包括公汽和地铁两类，而公汽又包括一票制和分段计价两种不同方式。设从起始站到目的地所有的可能线路有k条；用I、II、III表示乘坐单一票价、分段计价（1元票价、2元票价、3元票价）以及地铁三类交通工具；表示第k条线路上各类交通工具之间的转换次数；为标识函数，定义如下：则从起始点到终点站按第k条线路出行的换乘次数为：最少换乘次数为：其中，k0为起始点到终点站所有可能线路中按最少换乘次数所选的最优线路。2.2.3 最低票价的量化记为从起始点到终点站的票价消费，由于从起始点到终点站的可选择出行方式及线路有多种，如单一票价、分段计价以及乘坐地铁计价，记为沿k号线路乘坐以上几种交通工具的次数，为标识函数（i=1,2，5），且 则沿第k条线路出行的票价消费为： 最低票价即为： 其中，k0为从起始点到终点站的所有可能线路中按最少票价消费所选的最优线路。本章小结：该章节主要介绍了最优线路及最优线路的评价标准，同时给出了最优线路评价指标的量化处理方法，为后续模型的建立做好准备工作，可以说本章是模型建立的初始阶段。3.Floyd算法Floyd（弗洛伊德）算法16-17是一种矩阵（表格）迭代方法，对于求任意两点间的最短路、混合图的最短路、有负权图的最短路等一般网络问题来说均比较有效。该算法通过对表示有向图的邻接矩阵作叠代计算，来解决有向图任意一对顶点之间的最短路径间题，Floyd算法不仅是建立在简单的数据结构基础之上，而且就解决问题的彻底性而言也是最完满的。迄今为止，它仅仅是作为解决有向图的最短路径问题的一个重要方法而被提及。实际上，Floyd算法与图的许多重要性质以及与图论中其它一些重要问题的解决有着密切的联系。3.1 Floyd算法的基本原理 Floyd算法的主要思想是从代表任意2个顶点到的距离的带权邻接矩阵开始，每次插入一个顶点，然后将到间的已知最短路径与插入顶点作为中间顶点(一条路径中除始点和终点外的其他顶点)时可能产生的到路径距离比较，取较小值以得到新的距离矩阵。如此循环迭代下去，依次构造出个矩阵，当所有的顶点均作为任意2个顶点到中间顶点时得到的最后的带权邻接矩阵就反映了所有顶点对之间的最短距离信息，成为有个顶点的图的距离矩阵。最后对G中各行元素求和并比较大小，决定最优的路线。3.2 Floyd算法构造距离矩阵的原理对一个有个顶点的图G，将顶点用个整数(从1到)进行编号8。把G的带权邻接矩阵W作为距离矩阵的初值，即。从图的带权邻接矩阵W开始，递归地进行次更新，即由矩阵，按一个公式,构造出矩阵；又用同样的公式由构造出矩阵；最后又用同样的公式由构造出矩阵。矩阵的行列元素便是号顶点到号顶点的最短路径长度，称为图的距离矩阵，同时还可以引入一个路由矩阵path来记录两点间的最短路径18-19。第一步：构造。第二步：构造，其中是从到的只允许作为中间点的路径中最短路长度。第三步：构造，其中是从到的只允许，作为中间点的路径中最短路长度。第步：构造，其中是从到的只允许，,作为中间点的路径中最短路长度,即是从到中间可插入任何顶点的路径中最短路的长度，因此即是距离矩阵。 3.2.1 Floyd算法步骤 上述矩阵序列可以递归地产生，利用循环迭代便可求出，算法的详细步骤如下：;：对应于的路径上的后继点，最终的取值为到的最短路径上的后继点。Step1：赋权值, 对所有;当时，,否则。Step2：更新， 对所有若，则转入step3,否则继续执行step3。Step3：重复step2直到。迭代结束后得到最终的距离矩阵和路由矩阵path，根据距离矩阵可得任意两点间的最短路长度，根据路由矩阵path可得任意两点间取最短路径。3.2.2 回溯法求最短路径已知路由矩阵，利用回溯法求解点与点取最短路径，若已知，分别从点和点开始回溯：（a）从点开始回溯 （b）从点开始回溯 则从点到点的最短路径为：。3.3 Floyd算法改进3.3.1改进Floyd算法原理在原有的Floyd算法中，矩阵给出网络中任意两点直接到达，经过一个、两个、到个中间点时比较得到的最短距离。一般地。在计算过程中，由于，其中，从1到取值。当较大时，从1到取值，比较之间的值取其最小，计算量大。由于表示的是从点到点插入个节点后的最好结果，导致插入个节点应该优于，实际上包含。然而当从1到取值时，不一定所有就优于，为了简化计算量，我们将作为计算取小运算的首次比较标准。3.3.2改进Floyd算法的计算步骤首先用 来保存当从1到取值时的最小值20。用来记载取最小值时的取值。Step1：初始值为，即。Step2：当从1到取值时，如果，则值不变；如果，则，进入step3步。Step3：将作为新的比较标准，从到取值时，如果，则值不变；如果，则，。Step4：循环第step3步，直到，则，即 。改进后，的计算由原来的次运算减少到次运算。本章小结：在本章中主要介绍了基本的Floyd算法思想及其步骤，这也是Floyd算法改进的基础。在理解了基本的Floyd算法之后，对该算法进行改进。通过增加变量来保存每次跌代中的最优结果，避免了重复计算，从而大大减少了算法运算次数。该章节介绍的基本Floyd算法也是向量Floyd算法的基础，是后续章节的必备知识4.多维Floyd算法4.1 算法的基本思想由于Floyd方法只针对一种交通工具而建立的，若有多种交通工具（例如：出租、公汽、地铁、自行车等），那么此方法中就无法确定，由此，我们采用多维的Floyd算法求解该问题。多维的Floyd算法又叫做向量Floyd算法，将赋权有向图的权矩阵D的每个元素用向量表示。在计算网络中最短路的长时，点与点之间可以通过多种方式到达，如在交通中可以通过乘坐出租车、乘坐公汽、乘坐地铁、步行等方式到达，在到达中间还可以通过中间点转换各种交通工具。设各种交通工具换乘平均耗时如下：出租换乘出租平均耗时： 分钟公汽换乘公汽平均耗时： 分钟地铁换乘地铁平均耗时： 分钟出租换乘公汽平均耗时： 分钟出租换乘地铁平均耗时： 分钟公汽换乘出租平均耗时： 分钟公汽换乘地铁平均耗时： 分钟地铁换乘出租平均耗时： 分钟地铁换乘公汽平均耗时： 分钟条件假设：交通路段不存在拥堵问题；公交工具在行驶中不存在拥挤问题；公交工具的数量足以满足公交正常运输的需求；公交车辆的运行状况不受外界的干扰，按标准时间行驶，准点到达；乘客在各交通工具之间转乘也在规定的时间内准点完成；乘客判断最佳线路的标准是在转乘次数尽可能少的情况下花费的时间最少，其次再考虑费用问题。4.1.1建立赋权有向图D用表示最优线路矩阵，其中为所有站点数，并且用来对该个站点进行编号，表示从站点分别乘坐出租、公汽、地铁到达站点的最优直达路径。当与之间没有出租、公汽、地铁直达时，则均取，当时，均取0，。4.1.2 构造路由矩阵T用向量矩阵记录从站点到站点的最优路径上站点的后继站点以及乘坐交通工具情况记录。表示从站点到站点最后是乘坐出租到达的，表示从站点到站点最后是乘坐公汽到达的，表示从站点到站点最后是乘坐地铁到达的。用分别表示乘坐出租、公汽、地铁到底目的地，其中分别表示出租车号、公汽车号、地铁线路号。构造如下：第一步：从站点到站点，若能够乘坐出租直达，则令，否则令；若能够乘坐公汽直达，则令，否则令；若能够乘坐地铁到达，则令，否则令。第二步：根据Floyd算法的思想知，第二步迭代的时，从站点到站点中间可在号站点处转乘一次到达，且最后一站是乘坐出租到达的，若在号站点处由出租转乘出租，则，其中分别表示出租车号，如果乘坐同一辆出租车，则，以下同理；若在号站点由出租转乘公汽，则；若由出租转乘地铁，则。若最后一站是乘坐公汽到达的，则若在号站点处由公汽转乘出租，则，若由公汽转乘公汽，则，若由公汽转乘地铁，则。若最后一站乘坐地铁到达，则若则若在号站点处由公汽转乘地铁，则，若由出租转乘地铁，则，若由地铁转乘地铁，则。第步：根据Floyd算法，第步迭代的时，从站点到站点中间可在号站点处转乘到达，假设从站点到站点的最短路中在第步的基础上增加一个转乘点，且最后一站乘坐出租到达，则若在站点处由出租转乘出租，则，若在站点处由出租转乘公汽，则，若在站点处由出租转乘地铁，则，若在站点处由公汽转乘出租，则，；若最后一站乘坐公汽到达，则按照上述方法修改的值，若最后一站乘坐地铁到达，则修改的值。4.1.3 构造统计矩阵S用向量矩阵来记录从站点到站点的过程中所经过的站点总数，其中分别表示最终乘坐出租、公汽、地铁到达目的地。构造向量矩阵如下：第一步：初始化矩阵若站点到站点可乘坐出租直达，则，否则；若站点到站点可乘坐公汽直达，则，否则；若站点到站点可乘坐地铁直达，则，否则。第二步：根据Floyd算法的思想知，第二步迭代的时，从站点到站点中间可在号站点处转乘一次到达，若在号站点处由出租转乘出租，则,若由出租转乘公汽，则，若由出租转乘地铁，则，若由公汽转乘出租，则，。第步：迭代到第步时，从站点依次可经过中转1个，2个，个站到达站点。假设从站点到站点的最短路中在第步的基础上增加一个转乘点，若在站点处由出租转乘出租，则，；若在站点处由出租转乘公汽，则；若在站点处由出租转乘地铁，则；若在站点处由公汽转乘出租，则；。4.1.4 迭代过程在第步迭代中计算向量为：即，其中 如果取值，则表示转乘点处由出租转乘出租， ，；若取，则表示转乘点处由公汽转乘出租，；若取，则表示转乘点处由地铁转乘出租，；若取则表示在第步最优距离矩阵中，与之间没有找到比第步更优的路径，。即，其中如果取值，则表示转乘点处由公汽转乘公汽，；若取，则表示转乘点处由出租转乘公汽，；若取，则表示转乘点处由地铁转乘公汽，；若取，则表示在第步最优距离矩阵中，与之间没有找到比第步更优的路径，, 。即，其中如果取值，则表示转乘点处由地铁转乘地铁，；若取，则表示转乘点处由出租转乘地铁，；若取，则表示转乘点处由公汽转乘地铁，；若取，则表示在第步最优距离矩阵中，与之间没有找到比第步更优的路径，, 。4.2算法的基本步骤 由该算法的基本原理知该算法的步骤如下： Step1：计算赋权有向图的权向量矩阵：，其中表示从站点分别乘坐出租、公汽、地铁到达站点的最优直达路径。置，其中为总的站点数。当与之间没有出租、公汽、地铁直达时，则均取，当时，均取0，。按照构造向量矩阵T和向量矩阵S的方法分别给矩阵和赋初值。,其中记录从站点分别乘坐出租、公汽、地铁到达站点最优路径上站点的后继站点以及乘坐交通工具情况记录。当没有直达车辆时，则用F记录。，记录从站点分别乘坐出租、公汽、地铁到达站点是否能够直达。没有直达车辆时，则用来表示。Step2：按照上述计算方法计算出迭代矩阵，并且计算向量矩阵和。Step3：如果或则得，若，则，；若，则，；若，则，结束；否则令，转入step2。 由距离矩阵可知任意两点间的最优线路的长度，由路由矩阵利用回溯法可得任意两点间的最短路径，有矩阵可知任意两点间取最优线路时中间经过的站点总数。本章小结：本章节主要是在Floyd算法的基础上增加两站点之间的交通工具，将基本的Floyd算法扩展至多维，多维的Floyd算法建立的数学模型更符合实际生活要求，能更好得满足实际生活中人们的出行需求。本章也是该论文的核心章节，利用多维的Floyd算法建立的数学模型能够更好的解决实际生活中的问题，为人们的出行提供参考。5.Dijkstra算法介绍5.1 Dijkstra算法原理Dijkstra算法是计算从某个点到其余各个顶点的最短路径，是按照路径长度递增的次序产生最短路径的算法。给定一个赋权有向图1，即给了一个有向图,对每一个弧，相应地有权，又给定中的两个顶点，设是中从到的一条路，定义路的权是中所有弧的权之和，记为。最短路问题就是要在所有从到的路中，求一条权最小的路，即求一条从到的路使，式中对中所有从到的路最小，称使从到的最短路。路的权称为从到的距离记为。如果是中从到的最短路，是中的一个点。那么,从沿到的路是从到的最短路。事实上，如果这个结论不成立,设是从到的最短路，令是从沿到达,再从沿到达的路，那么的权就是比的权小，这与是从到的最短路矛盾 。Dijkstra方法具体的步骤中，用,分别表示某个点的标号、标号，表示第步时，具标号点的集合。为了在求从到各点的距离的同时，也求从到各点的最短路，给每个点以一个值，算法终止时，如果，表示在从到最短路上，的前一点是；如果，则表示中不含从到的路；表示。5.2 Dijkstra算法的基本步骤Dijkstra方法的具体步骤如下：赋权有向图。Step 1:令 ，对每一个令，令，。Step 2: 如果，算法终止，这时，对每个,，否则转入step 2。Step 3: 考查每个使,且的点。如果，则把修改为，把修改为k；否则转入step 3.Step 4: 令，如果，则把的T标号变为P标号，令，把换成，转入step；否则终止，这时对每一个，而对每一个，。5.3 Dijkstra算法与基本Floyd算法时间复杂度的比较 Floyd算法必须计算个矩阵。其中每一个矩阵包含个元素。因此Floyd算法总共必须计算出个元素，并且每计算一次都需要做一次加法运算和一次球极小值运算，因而Floyd算法需要运行时间21。 在Dijkstra算法的第一次迭代中，必须检验个未着色的顶点，这需要次加法、次求极小值和从个数中选出最小的数，亦即，还需要另外的次求极小值。因此第一次迭代需要次运算。同样，第二次迭代需要次运算，等等。总共需要次运算。因此，Dijkstra算法需要运算时间21，归纳起来：Dijkstra算法需要1.5n2次运算；Floyd算法需要2n3次运算。如上所述，Floyd法可以用重复做n次Dijkstra算法来代替，每次将一个顶点作为始点，这需要运行时间，比Floyd算法需要运行时间要短。但是如果有些弧的长度为负值，则必须用Floyd算法代替Dijkstra算法。在最坏的情况下，Floyd算法运行时间为，对于大的n来说，这比Floyd算法运行时间要差。但是，在大多数情况下，Floyd算法的运算次数比最坏情况下所有可能的运算次数要少得多。本章小结：该章节简单介绍了经典Dijkstra算法的原理及其步骤，并就Dijkstra算法与Floyd算法的时间复杂度进行了比较，使我们对Dijkstra算法有一个初步的了解。6.Floyd算法实例应用6.1问题的提出近年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。我们需要解决如下问题：1）仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用我们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。S3359S1828 、 S1557S0481 、 S0971S0485S0008S0073 、 S0148S0485 、 S0087S36762）同时考虑公汽与地铁线路，解决以上问题。3）假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）6.2 问题分析公交自主查询计算机系统需要满足旅客的主要需求为:在起始站、终点站已知的前提下，找出一条最优的乘车路线，所以我们要求的问题是一个在费用和时间约束下的最短路问题。62.1 问题一的分析公交自主查询系统应包含两种查询方式：寻优查询和表格查询。寻优查询就是乘客针对固定的起点和终点查询最佳路线。表格查询就是乘客可以通过表格上的信息获得任意两站点之间的最佳路线。寻优查询方式采用两阶段算法求解。第一阶段用动态规划的思想，找出问题的可行解。具体计算过程为：首先计算出起点的直达站点和终点的直达站点，然后通过对这些直达站点的比较，可以立即得到直达的公交线路和转乘一次的公交线路。如果找不到，就进一步搜索起点的直达站点和终点的直达站点的直达线路。如果能搜索到，就说明该线路需要转乘两次。如果搜索不到，就对两边的直达站点采用类似的方法进行搜索。依据最优化的标准，已找到两种不同的转乘次数的可行解为准，中止算法。根据条件假设，第二阶段可按照如下的最优化的标准寻找最优解：（1）在行程时间与第二条相比差别较大的情况下，转乘次数少的线路为较优线路。（2）在转乘次数相同且行程时间相当的线路中，费用少的线路为较优线路。（3）在两条可行线路中，如果第一条线路转乘次数少，但行程时间特别长，那么第二条可行线路优于第一条。表格查询方式也采用两阶段算法求解。第一阶段是对原始数据的处理。原始数据的具体处理过程为：我们将原始数据存入access数据库的两个数据表中，其中一个表记录了车次，计费方式和公交线路的样式并用id进行自动编号。另一张表记录了车次的id值和车次通过的各个站点，通过id值实现两表之间数据的交叉查询，大大减少了检索量。通过对数据的查找和删除，就找出了所有能直达的路线，并得到相应的时间与费用综合的评价指标。为了消除时间与费用之间的数量级差别造成的影响，时间与费用综合的评价指标规定为公交的费用乘上10后与它行驶的时间之和。根据综合评价指标最小的原则，从所有可行的直达线路中找到最优的直达线路。第二阶段的算法是在一个赋权有向图中用改进的Floyd算法求解最短路问题来得到最佳换乘点。赋权有向图的顶点表示换乘点，弧为两换乘点间的最短直达线路，弧的权值为时间与费用综合的评价指标。我们设计的算法与Floyd算法基本相同，只是在迭代的过程中需要加入换乘时间。例如，在得到第k个迭代矩阵，计算第k1个迭代矩阵时，求解的计算公式为：其中在中没有换乘，所以没有加换乘时间5分钟，而在中由于换乘，所以加上了换乘时间。62.2 问题二的分析第二问是在第一问的基础上增加了一种新的交通工具（A站到B站的乘车方式如图2），因此其最优解优于第一问的最优解。图1：A站到B站的方式根据本题第一问的计算结果发现：6对站点的最优路线的转乘点的个数不超过3个，且这6对站点中有一对站点可以通过地铁直达，而另外5对站点均不能直接到达地铁站，因此只需要求出需要转乘地铁的最优线路，再与第一问的最优线路进行比较，如果行程时间特别短，则取转乘地铁的最优线路。因此第二问的寻优查询只需要计算出转乘两到三次且中间的交通工具为地铁的最优线路。当增加一种新的交通工具后，换乘方式新增了三种情况：公汽换乘地铁、地铁换乘公汽、地铁换乘地铁（具体乘车方式如图2）。图2：A站到B站经过C站的乘车方式因此迭代矩阵中各元素的计算不能完全使用第一问中所用的方法，应该要考虑乘客在换乘点下车时所使用的交通工具。在问题二表格查询方式的算法中，要分别算出乘客下车时乘坐汽车或是地铁时的最佳换乘方式。因此不能完全采用问题一中的Floyd算法，而应该使用二维向量Floyd算法来求解，二维向量的两个分量分别表示乘客下车时乘坐汽车和乘客下车时乘坐地铁。例如：在第k步时得到迭代矩阵，其中为乘客下车时乘坐汽车的最短路长度，为乘客下车时乘坐地铁的最短路长度。计算第k1个迭代矩阵时，求解的计算公式为：求解的计算公式为：62.3 问题三的分析根据第三问的要求，需要求出任意两站点之间的最佳线路，所以只能通过表格查询方式来求解。根据第二问中的向量Floyd算法的特点，增加一种新的交通工具，只需在算法中将迭代矩阵中的元素，即二维向量，改为三维向量就可以求解了。在求解三维向量的各分量时，由于换乘方式的增加，计算量也增加了。例如在第k步迭代中计算向量为：6.3 问题求解6.3.1问题一的求解利用改进的Floyd算法求解该问题。(1) 赋权有向图的建立通过数据预处理过程，我们求出了任意两站点之间的最佳直达路径。现在以公汽行驶过程中的换乘点为顶点，两顶点之间的最佳直达路线为弧，以行驶时间加行驶费用的10倍为权重建立一个赋权有向图，则解任意两站点之间的最佳行驶路线问题就转换为求该赋权有向图任意两站点间的最短路问题。(2) 改进的Floyd算法求解步骤如下：Step1：计算赋权有向图的权矩阵=，置。其中为题中所给的站点数；为、两换乘点间时间与费用结合的权重，且当不能直达时，取+；、都为。Step2：按如下公式计算迭代矩阵=()=min+5, +5, +,+,+5=+5其中为第k+1次迭代的最短路的长度,并记录下换乘点。Step3：如果=或k=n-1则结束；否则令k=k+1，转入step2。根据迭代结束得到的距离矩阵可得任意两点间的最优路径长度，根据记录的换乘点信息可得最优路径行走方案。6.3.2问题二的求解利用二维的Floyd算法求解该问题该算法步骤如下：Step1： 计算赋权有向图的权向量矩阵：=其中表示从站点分别乘坐公汽、地铁到达站点时的最佳直达路径。置。其中为题中所给的站点数；和为、两换乘点时间与费用结合的权重，且当没有公汽直达时，取+；当没有地铁直达时，取+；、都为。Step2： 按如下公式计算迭代矩阵 = =(min+5,+5,+,+,+5，+7,+7,+,+,+7，min+6,+6,+,+,+6+4,+4,+,+,+4)=(+5+7, +6或+4)如果取值为(+5, +6)，则表明在转乘点处由公汽转乘公汽；在转乘点处由公汽转乘地铁。并记录下换乘点，；如果取值为(+5, +4)，则表明在转乘点处由公汽转乘公汽；在转乘点处由地铁转乘地铁。路由矩阵为，。矩阵S的各分量为，。如果取值为(+7, +6)，则表明在转乘点处由地铁转乘公汽；在转乘点处由公汽转乘地铁。路由矩阵为，。矩阵S的各分量为，。如果取值为(+7, +4)，则表明在转乘点处由地铁转乘公汽；在转乘点处由地铁转乘地铁。路由矩阵，。矩阵S的各分量为，。Step3：如果=或k=n-1则得=()，=，结束；否则令k=k+1，转入step2。6.3.3问题三的求解利用三维的Floyd算法求解该问题该算法的步骤如下：Step1： 计算赋权有向图的权向量矩阵：=其中表示从站点分别乘坐公汽、地铁、步行到达站点的最佳直达路径。置。其中为题中所给的站点数；、和两换乘点时间与费用结合的权重，且当没有公汽直达时，取+；当没有地铁直达时，取+；仅为、两站点间的步行时间；、都为。Step2：按如下公式计算迭代矩阵 = ，其中=(min+5,+5,+,+，+5，+7,+7,+,+,+7，+2,+2, +,+,+2, min+6,+6,+,+,+6，+4,+4,+,+,+4，+2,+ +2, +,+,+2，min+,+, +,+,+，+,+,+ ,+,+，+,+, +,+,+，)=(+5或+7或+2, +6或+4或+2，+或 + 或+)如果取值为(+5, +6，+)，则表明在转乘点处由公汽转乘公汽,在转乘点处由公汽转乘地铁,在转乘点r处由公汽改为步行。记录路由矩阵，（表示步行，则不用区分）。矩阵S为，。如果取值为(+5, +4，+)，则表明在转乘点处由公汽转乘公汽；在转乘点处由地铁转乘地铁；在转乘点r处由公汽改为步行。路由矩阵，。矩阵S为，。如果取值为(+7, +6，+ )，则表明在转乘点处由地铁转乘公汽；在转乘点处由公汽转乘地铁；在转乘点r处由乘坐地铁改为步行。路由矩阵为，。矩阵S为，。如果取值为(+7, +4，+)，则表明在转乘点处由地铁转乘公汽；在转乘点处由地铁转乘地铁；在转乘点r处继续步行。路由矩阵，。矩阵S为，。Step3： 如果或则得，。若，则，；若，则，；若，则，结束；否则令k=k+1，转入step2。由距离矩阵，可分别知任意两点间的最优线路的长度、最短路径和最优线路时中间经过的站点总数。6.4 问题的结果6.4.1问题一的汽车最优路线该问题是一个多重最优模型，可以根据对时间、转乘次数和车费的不同要求来选择最优线路。根据实际情况知，转车次数越多，所经过的站点数越多，相应的耗时也会越长，所在求解的过程中，求解出了转乘次数为一次和两次的情况，并记录每条线路所经过的总站点数，在根据不同的要求选择一条最优线路。表一：S3359-S1828中转一站的乘车路线可达路线乘车线路费用（元）总 站点 数最 优线 路134424453344433453326344734083449336 从表上可知，从S3359-S1828站中间换乘一次的乘车方式有9种，首先考虑费用最少，其次再考虑所经过的总站点数，选择一条最优线路。最优线路为：由S3359乘坐L469车次上行线路经29站到达S0304，再转乘L167车次下行线路经1站到达S1828，费用为3元，总共经过32站到达。其它线路依次类推。表二：S1557-S0481中转两站的乘车线路（部分路线）可达路线乘车线路费用（元）总 站点 数最 优线 路13412446334043365453645573358332944810456从S1557-S0481站中间换乘两次的乘车方式总共有128种，上表中列出了其中的10种乘车方式，综合考虑乘车费用最少且经过的总站数少，从中选择一条最优线路。最优线路为：由S1557乘坐L084车次下行线路经12站到达S1919，再转乘L189车次下行线路经3站到达S3186，再转乘L460车次环形线路经17站到达S0481,总费用为3元，总共经过32站到达。其它线路依次类推。6.4.2问题二的汽车和地铁最优路线表三：综合考虑车费与耗时的汽车和地铁最优路线标号乘车路线路费（元）耗时（分钟）1511825120.535964552.55587.56325在汽车和地铁最优路线表中，（1）由S3359乘坐L484车次下行线路经9站到达S0391，并在此站处改乘T1经12站到达D18站，再乘坐T2经2站到达D34，并在此站改乘L447上行线路经18站到达S0481，这是所有汽车与地铁换乘中最优的线路，耗时118分钟，花费5元，其他线路依次类推。6.4.3 问题三的最优线路多维的Floyd算法迭代到最后产生的矩阵即是任意两点的最短距离矩阵。通过路由矩阵利用回溯法可得最短路径。本章小结：在本章中主要是利用Floyd算法解决一个实际问题。首先提出问题，在利用前面几个章节讲到的Floyd算法对提出的问题一一求解，做到了将理论应用于解决实际问题，为人们的方便出行带来参考。谢 辞我衷心感谢导师同小军教授的悉心指导和热情帮助。是他让我选择了目前所写的研究领域，并在我的论文完成过程中不断地给我具体指导和启发，使我得以比较顺利地完成学业，完成论文。同老师对科学的不懈追求，严谨的治学态度，严于律己的工作作风，诲人不倦的工作态度，一贯团结奉献的精神，都使我备受教益，终身难忘。他所创造的优良科研氛围和团结协作精神也将使我受益终身。同时，论文的顺利完成，离不开其它各位老师、同学和朋友的关心和帮助。特别是王防修老师和曾山老师，在整个的论文写作中，他们帮助我查找资料并提供有利于论文写作的建议和意见，在他们的帮助下，论文才能得以不断的完善。 另外，要感谢在大学期间所有传授我知识的老师，是他们的悉心教导使我有了良好的专业课知识，这也是写作论文的基础。 参考文献1 刁在筠，郑汉鼎，刘家壮，刘桂真. 运筹学M.北京：高等教育出版社，2005：203-207.2 宋金华. Dijkstra算法程序的优化J. 海南广播电视大学学报. 2008,04.3 谢政. 网络算法与复杂性理论M. 长沙：国防科技大学出版社，2004.4 王战红，孙明明，姚瑶. Dijkstra算法的分析与改进J. 湖北第二师范学院学报. 2008,08.5 姜启源，谢金星，叶 俊. 数学模型M. 北京：高等教育出版社，2004：375-381.6 吴文泷图论基础及应用M北京：中国铁道出版社，1984.7 朱德通. 最优化模型与实验M. 上海：同济大学出版社，2003.8 赵静，但琦. 数学建模与数学实验M. 北京：高等教育出版社，2000.9 钟守楠, 高成修. 运筹学理论基础M. 武汉大学出版社 ，2005.10 杨新苗，王炜，马文腾. 基于GIS的公交乘客出行路径选择模型J. 东南大学报. 2000,30(6):87-91.11 王杰. 基于分层网络模型的单一讫（不同）点物流运送路径优化研究D. 北京：北京交通大学，2002.12 Angelica Lozano，Giovanni Storchi. Shortest viable path algorithm in multimodal networks. Transportation Research. Part A 35(2001):225-241.13 Paola Modesti，Anna Sciomachen. A utility measure for finding multimodal transportation networks. European Journal of Operational Research. 111(1998):495-508.14 许谷声，陈逸群，王解先等，结合最优信息的路径搜索J. 测绘工程，1998，(4)：44-47.15 魏峰，夏小刚，张守刚，杨云峰. 公交最优出行线路的一个模型及算法J. 交通标准化，2008，(6)：155-157.16 米涅卡，李家滢，赵关旗. 网络和图的最优化算法M. 北京：中国铁道出版社，1984.17 钱项迪，运筹学M，清华大学出版社，199018 殷人昆. 数据结构：用面向对象方法与C+描述M. 北京：清华大学出版社，1999.19 郝自军，何尚录. 最短路问题的Floyd算法的若干讨论J. 重庆工学院报(自然科学). 2008，05. 22(5)：156-159.20 同小军，陈绵云. 动态规划中函数值序迭代法J. 佛山科学技术学院学报(自然科学). 2002，03. 20(1)：10-16.21 张权范. 求解PERT两点间最短路径的Floyd算法分析与程序实现J. 中国制造业信息化. 2008,06. 37(11)：69-71.22 维普资讯 .23 万方数据