![](https://csdnimg.cn/release/download_crawler_static/18687406/bg1.jpg)
第 29 卷第 3 期 温 州 大 学 学 报·自 然 科 学 版 2008 年 6 月
Vol 29, No 3 Journal of Wenzhou University · Natural Sciences Jun, 2008
公共交通出行线路最优选择
连新泽
(温州大学数学与信息科学学院,浙江温州 325035)
摘 要:运用数学理论和方法以及计算机代数系统 Maple,建立了公共交通(包括公汽、地铁等)出
行线路选择问题的算法.针对 2007 年全国大学生数学建模竞赛 B 题,对任意给定起始站点和目的站
点以及乘客的选择模式,应用该算法得到了乘客需求的最佳换乘公交路线及所花的时间和费用.
关键词:最短路径;最少换乘;公共交通系统
中图分类号:O141.4 文献标识码:A 文章编号:1006-0375(2008)03-0037-07
公共交通(包括公汽、地铁等)是现代化城市的动脉,以其经济、安全、相对环保等特点,
成为人们出行的首选.随着城市化进程的加快,城市的公共交通系统有了很大改观,大型城市的
公交线路已达800多条.如此众多的公交线路使得人们出行更加通畅、便利,但人们同时也面临
多条线路的选择问题.因此,提供方便、快捷、经济、高效的公共交通出行线路选择方案,不仅
可以方便人们的出行和生活,同时也有利于提高城市的交通运输效率,展示现代城市信息化的风貌.
1959年,Dijkstra
[1]
提出了最短路径算法。该算法由于适应网络拓扑变化的稳定性,在计算机
网络拓扑路径选择以及地理信息系统(GIS)中得到了广泛应用
[2-3]
.但是Dijkstra算法是针对从某
点到其余各点的最短路径,对大型数据的计算所需时间较长,所以Dijkstra算法并不适合公交最短
路径查询
[4,5]
.随着对公交线路选择问题研究的不断深入,当前流行的地理信息系统(GIS)借助
其空间分析能力和可视化表达发挥着重要作用.马良河
[6]
研究了城市公交线路网络图的最短路径
与乘车路线问题,Choi K
[7]
利用GIS技术讨论了从街道地理数据产生公交线路和站点的问题,黄正
东
[8]
研究了GIS中公交实体与基础路网的关联。针对现有的城市公交运行线路、站点分布和城市
的道路网络特点,GIS技术对于建立城市公交查询系统有极大帮助。但由于其计算量巨大,只能
较好地应用于小城市的公交系统。在大城市中使用GIS尚不能达到理想的速度和结果.
事实上,人们出行的公交线路主要基于两种方式:单纯乘坐公汽或地铁;乘坐公汽和地铁.考
虑线路的选择、主要乘车时间、换成次数及费用等因素,并根据相关心理学研究结果,换乘3次
是人们的心理承受上限,本文建立了公交出行线路选择模型及相应的优化算法.
1 模型假设与符号说明
1.1 模型假设
(I)假设公交到达最后一站,乘客必须下车;
收稿日期:2007-11-10
基金项目:大学生数学建模竞赛研究和实践(314040310407)
作者简介:连新泽(1980- ),男,浙江温州人,助理实验师,学士,研究方向:计算机数学