公交查询系统的数学模型

更新时间：2023-07-18 01:45:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

公交查询系统的数据库设计推荐度：
相关推荐

公交查询系统,07年全国赛B题

第２５卷第４期

２００８年８月黑龙江大学自然科学学报ＪＯＵＲＮＡＬＯＦＮＡＴＵＲＡＬＳＣＩＥＮＣＥＯＦＨＥＩＬＯＮＧＪＩＡＮＧＵＮＩＶＥＲＳＩＴＹＶ０１．２５Ｎｏ．４Ａｕｇｕｓｔ，２００８

公交查询系统的数学模型

李响，张睿智

（黑龙江大学数学科学学院，哈尔滨１５００８０）

摘要：运用Ｄｉｊｋｓｔｒａ标号法的推广算法和线性规划理论，建立了已知公交起点站到欲到达的

公交目的站的最优线路数学模型。解决了已知大数据量的多条公交线路和多个公交站点的最优乘

车线路查询问题，同时可以根据目标的不同，选择最短线路和耗资最少线路。模型也可应用于多种

交通工具并用的线路选择问题，并设计程序实现了该模型。

关键词：Ｄｉｊｋｓｔｒａ标号法；线路集合；线路组合；转车次数；最优路线

中图分类号：０１７７．９１文献标志码：Ｂ文章编号：１００１—７０１１（２００８）０４—０５５４一０４

０引言

２００７年全国大学生数学建模竞赛Ｂ题的含义是：在已知的５００多条公交线路和有重合情况的１５０００多个公交站点中，设计出一套可以根据不同的目标，从起始站到终点站的最优乘车线路的查询系统。问题的难点在于大数据量的处理、公交车的转乘和算法的实用性，也就是说，查询者在输人起始公交站点和欲到达公交站点后，系统能够在最短的时间提供最佳的乘车信息，包括乘车的线路、转乘的站点、用费以及其他的到达方式等。

公交问题常见的解法是Ｄｉｊｋｓｔｒａ标号法…，该算法是使用最广的适合拓扑网络节点间最短路径搜索的算法之一，它从站点人手，求出从始点到终点的最短路径；如果将它直接应用于公交网络，将会出现多次转车才能达到路径最短的目的；另外，此种方法不适用于大数据量的问题；进一步的优化算法，在文献［２—６］中也有相应的讨论，但均把着眼点放在了最短路径上。本文立足优先考虑乘车次数，以转乘次数最少为主要目标，建立速度快，计算量小的最优路径查询算法。作者所采用的方法具有独到的创新之处，主要体现在以下几点：

１．将问题的突破点放在线路的选择上，这样的搜索范围就限制在５００条公交线路上；

２．找到由起点至终点的所有可行线路，从中选取最优解，搜索范围就限制在几十条线路上；

３．在转乘问题的求解中ｉ将所经站点赋双下角标值，第一下角标为车次编号，第二下角标为此站点是该车次的第几站。当第一下角标变化时表示转乘，当第一下角标相同时，第二下角标的差为乘坐该车次共需几站。此种方法既简便又直观，而且便于计算机实现；

４．在程序实现《，设计了一个实用的可视化界面，只需输入起点站和欲到达站，便可根据查询者不同的要求给出相应的结果，运算时间在２０ｓ左右。

鉴于篇幅所限，本文作者只选摘了获奖论文的主要过程和结论。

１问题分析

根据引言叙述的问题背景，现欲构造一运算速度快且可行性高的算法，从而寻求任意两站点间的最优路径。首先分析公交网络本身所具有的特点，它有连通性、节点性、有向性，可将其视为一连通的有向图；其次

收稿日期：２００８一Ｏｉ一０８

基金项目：黑龙江大学新世纪教育教学改革丁程项目基金资助（０７ＪＳ００６）

作者简介：李响（１９８６一），女，２００５级本科生，Ｅ—ｍａｉｌ：ｈａｌｉｘｉａｎｇ＠１２６．ｔｏｍ通讯作者ｉ张睿智（１９８０一），男，助教

公交查询系统,07年全国赛B题

第４期李响等：公交查询系统的数学模型５５５考虑人们乘车的一般心理，大多数是把转乘次数少做为首要因素。那么针对连通有向图，如果把站点视为“点”，公交线路视为“线”，从大数量的站点出发，势必造成运算量大，影响查询速度。因而本文的算法优化方向如下：

１）从线路人手，构造连通有向图，即把公交线路视为“点”，若两公交线路中有公共站点就相连。从中选取与换乘车次、价格、路径有关的最优乘车路线；

２）在保证相同转车次数的前提下求得乘车路径最短、费用最省。

２模型建立与求解

做适当的模型假设：

１）相邻公汽站平均行驶时间不变；

２）交通情况良好，无堵车及车辆损坏等意外情况发生；

３）设各种交通工具的换乘时间保持不变；

４）将换乘次数这一因素作为第一约束目标，其次考虑路程和费用等因素；

５）在一条线路上２０站以内票价１元，２１站至４０站票价２元，超过４０站票价３元；

６）根据实际情况，两次以内换乘比较合理，超过两次不予考虑。

为叙述问题方便，引入如下记号：

用厶表示第ｉ条线路（ｉ＝１，２，３，…），口ｉ表示第ｉ条线路经过的第』个站点（若在单行线中表示按前进方向的第，个站点，若在循环线路中表示从左向右的第．『个站点），ｃｉ表示乘坐第ｉ条线路经过的站点数，－表示乘坐第ｉ条线路所花费用。

基于本问题所考虑站点数据量大的情况，作者将对站点的搜索转化为对线路的搜索。利用Ｄｉｊｋｓｔｒａ算法原理，将公交车的线路视为“节点”，既保留了Ｄｉｊｋｓｔｒａ算法适合拓扑网络的特点，同时也避免了节点过多带来的多次转车问题；另外，将上万个数据的处理优化为对５００多个数据的处理，大大缩短了运算时间。

算法实现如下：

对任意两个站点菇与），，分别选出所有经过站点ｚ及站点Ｙ的线路，其中经过站点ｚ的所有线路集合记

‘

为幔，经过站点Ｙ的所有线路集合记为Ｍ，．

２．１直达车算法

若Ｍ，ｎＭｒ≠毋，则此时表示从戈到Ｙ的直达车。对任意Ｌｉ∈丝ｆ＇ｌＭｙ，若

１．Ｌ；∈Ｍｏ（眠表示单行线的集合），此时石，Ｙ在这条线路中的位置分别为口¨口＂有以下两种情况：（１）当＿『；＞ｊｙ时，则说明此线路虽然直接连接了石与，，，但运行方向是反向，此条线路行不通；

（２）当Ｌ＜＾时，则计算Ｃｉ＝．『，一五．

２．Ｌｊ∈Ｍ，（肘。表示环形线的集合），则存在如下两种情况：

（１）当』。＞歹，时，则计算ｑ＝Ｊ，＋ＪＤ一丘（其中Ｐ为Ｌ。线路上总的站点数）；

（２）当丘＜歹，时，则计算ｑ＝＿『，一丘．

求出最少站点数Ｃ。＝ｍｉｎ｛ｃ。，ｃ：，…｝，因为直达时站点数少与费用少的目标是一致的，因此￡。便是最佳的乘车线路。再由假设５）可得所花费用为

ｒｌｃｍ≤２０

２０＜ｃ。≤４０

ｃ。＞４０ｒ。＝｛２【３

２．２一次转乘算法

若帆ｎＭｙ＝中，这时必须转车才可以到达终点，此时找出与幔中各个元素线路相交的线路的集合Ｑ，．若Ｑ。ｆ３Ｍ，≠痧，则此时转一次车就可以了。

用ｃ｛，ｃ；分别表示一次转乘和两次转乘的第ｉ种线路要经过的总站点数；尺：，Ｒ；分别为一次转乘和两次转乘第ｉ种线路所花总费用。．

对任意Ｌｉ∈Ｑ，ｎ肘，，若鸠中的厶和厶有相同的站点，则可行线路为乙＋厶．假设共有ｒ种可行线路，对上述可行线路取厶和Ｌ。的第一个公共站点ｚ，则此时相当于从戈到：有直达

公交查询系统,07年全国赛B题

．５５６．黑龙江大学自然科学学报第２５卷车毛，从彳到Ｙ有直达车ｔ，按照直达车算法分别得站点数为ｃ。和ｃ。，用ｑ表示从Ｌ。转到厶的一次转车到达的总站数，则有

ｑ＝ｃＩ＋ｃｉ，（，＝１，２，３，…，ｒ）

所经站点总数最少为

ｃ：＝ｍｉｎ｛ｃ：，砭，…，Ｃ：｝

计算出相应的费用ｈ和ｒ…总费用为刊

最少费用为＝ｋ＋－（Ｊ＝１，２，…，ｒ）．

Ｒ：＝ｍｉｎ｛尺：，Ｒ；，…，Ｒ：｝

２．３两次转乘算法

若Ｑ，ｎＭｙ＝中，则此时至少要转两次车才可以到达终点，记Ｑ，为与鸠中的各条线路相交的线路的集合。

由假设，Ｑ，ｎＱ，≠中．对于Ｑ，ｎＱ，中的任意一条线路厶，则在鸩中至少存在一条线路厶与其相交，同样在Ｍ，中至少存在一条线路乙和厶相交，这样毛＋厶＋厶便是一个可行线路的组合。

假设有ｓ种这样的组合，类似一次转乘，求出厶和厶的第一个交点ｅ，Ｌｊ与ｋ的第一个交点，这样就相当于从戈到ｅ有直达车厶，从ｅ到，有直达车厶，从厂到Ｙ有直达车厶．

按照转一次车算法求出ｔ，Ｌ。，厶线路中相应的站点数Ｃ＾，ｃ；，ｃ。和费用“，ｒｉ，“．

按照ｃ；＝ｃ。＋ｃｉ＋ｃ。（Ｊ＝１，２，…，ｓ）计算出二次转车各种可行线路组合要经过的站点数，求出

ｃ：＝ｍｉｎ｛ｃ；，谚，…，ｃ：｝

则第ｍ种可行线路组合便是换乘两次时路程较短的线路。

利用Ｒ；＝“＋－＋ｈ（Ｊ＝１，２，…，ｓ）求出各种可行线路组合所需费用。

求出Ｒ：＝ｍｉｎ｛Ｒ；，尺；．…，碍｝就是相对比较省钱的线路组合。

利用ＶＢ编制可视化程序，实现查询结果，在可视化窗ｌＹｌ中只需输入起点站和欲到达站，便可根据查询者不同的要求给出相应的结果。

下面以北京公交线路为例，选取６组站点，运用此算法实现查询结果如下（其中耗时栏含等车时间３ｒａｉｎ）：

表１一次换乘最优路线

Ｔａｂｌｅ１ＯｐｔｉｍｕｍｒｏｕｔｅｗｉｔＩｌｏｎｅｔｒａｎｓｆｅｒ

表２二次换乘最优路线

Ｔａｂｌｅ２Ｏｐｔｉｍｕｍｒｏｕｔｅｗｉｔｈｔｗｏｔｒａｎｓｆｅｒ

３模型评价

针对本文的问题，如用Ｄｉｊｋｓｔｒａ标号法，把站点看成节点，把公交线路看成连接节点的路径，可以找到从起点ｚ到终点Ｙ的最短站点距离的线路，但Ｄｉｊｋｓｔｒａ标号法找线路时没有考虑有几个转折点的问题，即最后找到的线路可能路径较短，但要转很多次车；另外Ｄｉｊｋｓｔｒａ算法在节点数量较多的情况下计算的时间成倍甚至幂次增长【卜８｜，这就脱离了实际。一文中算法将对站点的搜索转化为对线路的搜索，从而将上万个数据的处理优化为对５００多个数据的处理，大大缩短了运算时间。不仅如此，而且更符合乘客的查询要求（线路）。经检验输入起点与终点，结果查询运算时间不超过３０ｓ。同时，所得结果必为由起点到终点的路径。在转车

公交查询系统,07年全国赛B题

第４期李响等：公交查询系统的数学模型５５７次数的限定条件下，大大缩小了求解最佳路线的运算量。相比之下，该算法具有运算速度快，运算结果准确，实用性强等优点。

另外，模型也应用于多种交通工具并用的线路选择问题。如同时考虑公汽与地铁线路，由于同一地铁站对应多个公交站点，则可将地铁线路视为一条连通的公交汽车线，只需在数据处理时以“Ｌ”和“Ｔ”字头分别代表汽车和地铁线，应用本算法同样可获得最优线路选择。

参考文献

［１］刘缵武．应用图论［Ｍ］．长沙：国防科技大学出版社。２００６．

［２］翁敏，杜清运．基于公交网络模型的最优出行路径选择的研究［Ｊ］．武汉大学学报，２００４．２９（６）：５００—５０３．

［３］杨新苗，王炜，马文腾．基于ＧＩＳ的公交乘客出行路径选择模型［Ｊ］．东南大学学报（自然科学版），２０００，（６）：８７—９１．

［４］陈箫枫，蔡秀云，唐德强．最短路径算法分析及其在公交查询的应用［Ｊ］．工程图学学报．２００１，（３）：２６—３０．

马良河，刘信斌，廖大庆．城市公交线路网络图的最短路与乘车路线问题［Ｊ］．数学的实践与认识，２００４，（６）：３９—４５．

ＳＲ，ＯｓｍａｎＩＨ，ＶｉｎａｙａｇａｏｏｒｔｈｙＲ，ｅｔ［５］［６］Ｔｈａｎｇｉａｈａ１．Ａｌｇｏｒｉｔｈｍｓｆｏｒｖｅｈｉｃｌｅｒｏｕｔｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｔｉｍｅｄｅａｄｌｉｎｅｓ［Ｊ］．ＡｍｅｒｉｃａｎＪｏｕｒｎａｌｏｆｍａｔｈｅ—

ｍａｒｉｔａｌａｎｄＭａｎａｇｅｍｅｎｔＳｃｉｅｎｃｅ，１９９４，１３（３—４）：３２３—３５５．

［７］李文勇，王炜，陈学武．公交出行路径蚂蚁算法［Ｊ］．交通运输Ｔ程学报，２００４。４（４）：１０２—１０５．

［８］王朝晖，杨洁．公交线路中最优路线的查询算法设计［Ｊ］．现代测绘，２００５，８１：１５３—１５６．

Ａｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌａｂｏｕｔｅｎｑｕｉｒｙｓｙｓｔｅｍｏｆｐｕｂｌｉｃｔｒａｎｓｐｏｒｔｓｙｓｔｅｍ

ＬｉＸｉａｎｇ，ＺｈａｎｇＲｕｉｚｈｉ

（ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃａｌＳｃｉｅｎｃｅ，ＨｅｉｌｏｎｇｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ１５００８０，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ＢｙａｐｐｌｙｉｎｇｔｈｅｇｅｎｅｒａｌｉｚｅｄＤｉｊｋｓｔｒａｓｌａｂｅｌｉｎｇｍｅｔｈｏｄａｎｄｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇｔｈｅｏｒｙ，ａｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆｃｈｏｏｓｉｎｇｔｈｅｏｐｔｉｍａｌｂｕｓｐａｔｈｂｅｔｗｅｅｎｉｔｓｏｒｉｇｉｎｓｔａｔｉｏｎａｎｄｔｅｒｍｉｎａｌＳｔａｔｉｏｎｉｓｇｉｖｅｎ．Ｔｈｅｐｒｏｂｌｅｍｏｆｑｕｅ．ｒｙｉｎｇｏｐｔｉｍａｌｐａｔｈａｍｏｎｇａｇｒｅａｔｎｕｍｂｅｒｏｆｂｕｓｌｉｎｅｓａｎｄｂｕｓｓｔｏｐｓｂｙｍｉｎｉｎｇｍａｓｓｉｖｅｔｒａｆｆｉｃｄａｔａｉｓｓｏｌｖｅｄ．Ａｎｄ，

ｏｒｆｏｒｄｉｆｆｅｒｅｎｔａｉｍｓ，ｌｅａｓｔ—ｃｏｓｔ

ａｌｓｏ

ｅｎｔｃａｎｓｈｏｒｔｅｓｔ—ｄｉｓｔａｎｃｅｐａｔｈｃａｎｂｅｃｈｏｓｅｎｒｅｓｐｅｃｔｉｖｅｌｙ．Ｂｅｓｉｄｅｓ，ｔｈｅｐｒｏｐｏｓｅｄｍｏｄｅｌｂｅａｐｐｌｉｅｄｔｏｔｈｅｐｒｏｂｌｅｍｏｆｈｏｗｔｏｃｈｏｏｓｅｔｈｅｐａｔｈｗｈｅｎｓｅｖｅｒａｌｋｉｎｄｓｏｆｖｅｈｉｃｌｅｓｈｏｕｌｄｂｅｔａｋｅｎｉｎｄｉｆｋｒ－ｓｅｃｔｉｏｎｓｏｆｊｏｕｒｎｅｙ，ａｎｄａｐｒｏｇｒａｍｈａｓｂｅｅｎｄｅｓｉｇｎｅｄｔｏｒｅａｌｉｚｅｔｈｉｓｍｏｄｅｌ．

Ｋｅｙｗｏｒｄｓ：Ｄｉｊｋｓｔｒａｓｌａｂｅｌｉｎｇｍｅｔｈｏｄ；ｒｏｕｔｅｓｓｅｔ；ｒｏｕｔｅｓｃｏｍｂｉｎａｔｉｏｎ；ｔｈｅｔｉｍｅｓｏｆｔｒａｎｓｆｅｒ；ｏｐｔｉｍａｌｐａｔｈ

斗－＋－＋－＋—＋—＋—＋－＋－—卜－‘ ．．－— 卜－—＋－－‘—＋－－。＋——＋＿一—＋＿——＋－‘１＋—。－＋一一＋—＋＋——卜—＋－＋一＋－＋—＋—＋－＋－＋一十－＋－＋－＋——－—＋－＋－＋一＋—＋—＋－＋—＋－—＋一—＋（上接第５５３页）

Ｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆｓｏｌｕｔｉｏｎｔｏａｒｅａｃｔｉｏｎｄｉｆｆｕｓｉｏｎｓｙｓｔｅｍ

Ｗｅｎｊｉｅ

ｏｆＺｈａｎｇＪｉｎｇ，Ｇａｏ（１．ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｉｑｉｈａｒＵｎｉｖｅｒｓｉｔｙ，Ｑｉｑｉｈａｒ１６１００５，Ｃｈｉｎａ；２．ＩｎｓｔｉｔｕｔｅＭａｔｈｅｍａｔｉｃｓ，ＪｉｌｉｎＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｃｈｕｎ１３００１２。Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：Ｂｙｓｔｕｄｉｎｇａｔｙｐｅｏｆｒｅａｃｔｉｏｎｄｉｆｆｕｓｉｏｎｓｙｓｔｅｍｄｅｓｃｒｉｂｉｎｇｒｅａｔｉｏｎｆｏｒａｎｔｉｂｏｄｙａｎｄｖｉｒｔｕｓ，ｔｈｅｈｅａｔｃｏｎｄｕｃ．ｔｉｏｎｅｑｕａｔｉｏｎｗｈｉｃｈｈａｓｔｈｅｓａｍｅｓｏｌｕｔｉｏｎｔｏｔｈｅｒｅａｃｔｉｏｎｄｉｆｆｕｓｉｏｎｓｙｓｔｅｍｂｙｃｈａｎｇｉｎｇｖａｒｉａｂｌｅｓｉｓｏｂｔａｉｎｅｄ．Ｆｉｒｓｔｌｙ，ｕｎｄｅｒｔｈｅｗｅａｋｅｒｓｕｐｏｓｅｏｆｐｏｓｉｔｉｖｅｃｏｎｃｅｎｔｒａｔｉｏｎ‘口（ｔ）ｏｆ

ａａｎｔｉｂｏｄｙ，ｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆｔｈｅｓｏｌｕｔｉｏｎｔｏｈｅａｔｃｏｎｄｕｃｔｉｏｎｅｑｕａｔｉｏｎｉｓｓｔｕｄｉｅｄ．Ｂｙｃｏｍｏｕｔｎｅｓｓｉｔｅｘｉｓｔｓｃｏｎｖｅｒｇｅｎｔｓｕｂｓｅｑｕｅｎｃｅｗｈｅｎ妒（ｔ）ｓａｔｉｓｆｅｓｔｈｅｏｒｉｇｉｎａｌｓｕｐｐｏｓｅ，ＳＯ

ｔｈｅｃｏｎｃｌｕｓｉｏｎａｂｏｕｔｔｈｅｅｘｉｓｔｅｎｃｅ．ｕｎｉｑｕｅｎｅｓｓｏｆｓｏｌｕｔｉｏｎａｎｄｃｏｎｖｅｒｇｅｎｃｅｏｆｓｏｌｕｔｉｏｎｏｆｒｅａｃｔ

ｑｕａｔｉｏｎａｒｅｒａｔｅ后。∞ｔｏｔｈｅｅ．ｄｒａｗｎ．Ｆｉｎａｌｌｙ，ｔｈｅｅｘｉｓｔｅｎｃｅ，ｕｎｉｑｕｅｎｅｓｓａｎｄｃｏｎｖｅｒｇｅｎｃｅｏｆｓｏｌｕｔｉｏｎｔｏｔｈｅｏｒｉｇｉｎａｌｒｅａｃｔｉｏｎｄｉｆｆｕｓｓｉｏｎｓｙｓｔｅｍａｒｅｏｂｔａｉｎｅｄｂｙｔｈｅｐｒｏｐｅｒｔｉｅｓｏｆｈｅａｔｃｏｎｄｕｃｔｉｏｎｅｑｕａｔｉｏｎ．

Ｋｅｙｗｏｒｄｓ：ｒｅａｃｔｉｏｎｄｉｆｆｕｓｉｏｎｓｙｓｔｅｍ；ｈｅａｔｃｏｎｄｕｃｔｉｏｎｅｑｕａｔｉｏｎ；ｅｘｉｓｔｅｎｃｅ；ｕｎｉｑｕｅｎｅｓｓ；ｃｏｎｖｅｒｇｅｎｃｅ

公交查询系统,07年全国赛B题

公交查询系统的数学模型

作者：

作者单位：

刊名：

英文刊名：

年，卷(期)：

被引用次数：李响，张睿智， Li Xiang， Zhang Ruizhi黑龙江大学,数学科学学院,哈尔滨,150080黑龙江大学自然科学学报JOURNAL OF NATURAL SCIENCE OF HEILONGJIANG UNIVERSITY2008，25(4)0次

参考文献(8条)

1.刘缵武应用图论 2006

2.翁敏.杜清运基于公交网络模型的最优出行路径选择的研究[期刊论文]-武汉大学学报 2004(06)