公交查询系统的数学模型

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

第２５卷第４期

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

公交查询系统的数学模型

李响，张睿智

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

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

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

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

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

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

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

０引言

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

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

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

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

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

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

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

１问题分析

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

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

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

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

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新资格考试认证公交查询系统的数学模型全文阅读和word下载服务。