最佳公交线路的实时查询模型及算法.doc

《最佳公交线路的实时查询模型及算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最佳公交线路的实时查询模型及算法摘要本文针对查询者的不同需求，为公交查询系统提供了最佳线路查询的模型与算法。查询者的需求从换乘次数少、时间少和费用少三方面进行考虑。故查询算法从换乘次数（从实际出发，换乘不超过两次）入手：对直通的任意两站点，可设计出较简单的最佳直通线路查询算法（直通算法）。故对需要查询的两站点，算法先由线路、站点的原始数据判断此两站点是否直通，若是，便可通过直通算法进行查询。不论是否存在直通线路，算法都考虑对换乘的情形进行查询。考虑到城市公交系统中的站点基数较大，可行的换乘方案数也将较大，故查

2、询算法根据所有可行的一、二换乘点必与起、止站点直通的原则，对可能成为给定两站点的换乘点的站点进行了筛选，得到相关站点集，较大的缩小了查询的范围。得到相关站点集后，建立了反映站点集中任意两站点直通关系的连通矩阵，并通过矩阵乘法，较快地得出了所有可行的一次、二次换乘点。考虑到所有可行的换乘点可能较多，特别是二次换乘的情形，故查询算法采用分支定界法以较高效率对最佳方案进行了最后的筛选。在考虑地铁的公交系统时，本文从实际出发，对模型进行了一定的修改。同时，本文考虑了引入站点之间的步行时间的情况，提出了线路选择的模型。

3、由于筛选算法、矩阵乘法和分支定界法的高效性，整个查询算法具有很高的效率，并能在换乘次数不超过两次的条件下，求得全局最优解，得出满足查询者不同需求的所有最佳方案。并且，从系统设计的角度出发，整个系统需要预存的数据量很小，系统的实用性很强。对给定的六对站点，采用本算法进行查询，在1.7GHZ的CPU环境下，平均运行时间为：1.27秒，最长运行时间为7.43秒，验证了算法的实时性。同时，对每一对站点，得到了满足不同查询需求的所有最佳线路方案，验证了模型与算法的精确性。关键词：最佳线路、实时、筛选算法、分支定界一、问

4、题重述第29届奥运会将于今年8月在北京举行，届时有大量观众到现场观看比赛，其中大部分人将乘坐公共交通工具（包括公汽、地铁等）出行。北京市的800多条公交线路使得公众面临多条线路选择问题。因此，有必要开发一个解决公交线路选择问题的自主查询计算机系统。现有如下数据：1.基本参数设定：包括相邻站点平均行驶时间、换乘时间、票价等信息。2.公交线路信息：包括公汽和地铁的所有线路、途经站点、票制等信息。3.公交换乘信息：包括在每个地铁站点可以换乘的所有公汽站点。从实际情况出发考虑，在满足查询者不同需求的条件下，我们需要完

5、成如下工作：1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用模型与算法，求出以下6对起始站→终到站之间的最佳线路（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762.同时考虑公汽与地铁线路，解决以上问题。3.假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型。二、问题分析对于公交线路查询

6、系统，需设计查询最佳公交线路的模型和算法，满足查询者的各种需求，并使查询系统具有实时性。对于一般的查询者来说，对线路的选择主要有以下几种需求：换乘次数少、乘车总时间少和乘车总费用少，但不同的查询者对这三个因素有不同的偏好，故查询系统应能提供多种方案供查询者自行选择。可以先固定换乘次数，求得连通某两个站点的所有方案；再对在该换乘次数下的每一种乘车总费用所对应的方案，筛选出花费时间最少的方案；最后再对换乘次数不同的方案进行比较，淘汰掉劣势方案，得出满足不同查询者需求的最佳线路集。从实际的城市交通状况出发，交通部门

7、在设置公交站点时会保证整个城市交通网的连通性，以方便人们出行，故可以假设任何两个公汽或地铁站点最多经过2次换乘便可到达。在查询系统寻找最佳线路集时，若给定的两站点直通，可方便的找出其最佳线路，得到其乘车总费用及总时间。但对于存在换乘点的方案，需要确定途径的线路和换乘点，使得通过这些线路和换乘点可以到达终到站，并需要判断各个方案的优劣。对于目前的城市交通系统，线路和站点的数目都较大，故可能的换乘方案的数目也会较多，特别是对2次换乘的情形。这对各个方案的筛选即最佳线路集的确定将带来一定难度，并对查询算法的效率提出

8、了较高的要求。故问题的关键在于怎样高效的找出最佳方案中的换乘点。现需要考虑的是有着3957个公汽站点的交通网的最优线路查询问题。为了便于量化交通网中任意两站点的连通关系，先由线路原始数据可建立所有站点的连通矩阵。在查询给定两站点的最佳线路时，由于查询时间和遍历的站点数目成正相关，故不宜采用直接遍历全部站点的方法，应考虑对可能成为换乘点的站点进行筛选。由于假设的换乘次数不超过两次，故所有可能的换乘点都