公交查询系统的数学模型(2)

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

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

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

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

２模型建立与求解

做适当的模型假设：

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

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

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

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

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

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

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

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

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

算法实现如下：

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

‘

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

２．１直达车算法

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

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

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

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

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

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

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

ｒｌｃｍ≤２０

２０＜ｃ。≤４０

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

２．２一次转乘算法

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

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

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

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