马千里

摘要：城市公交查询系统是一个城市非常重要的基础设施，也是城市文明的一个重要标志。该文探讨城市公交查询系统中最优换乘次数的查询算法。算法以图论中邻接矩阵为基础，结合矩阵算术运算的特点和公交查询系统的要求建立算法。该算法可有效地查找出最优换乘次数的乘车路线，还可推广到火车，民航等相关问题的查询。

关键词：邻接矩阵；公交查询系统；数学模型

中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)09-2084-03

An Urban Public Transport Inquiry Algorithm Based on Optimal Number of Transfers

MA Qian-li

(Ordos City Dongsheng Informatization Committee, Ordos 017000, China)

Abstract: The urban public transport inquiry system is a very important infrastructure，which is also a symbol of urban civilization . This paper is focused on the Algorithm with optimal number of transfers in the urban public transport inquiry system. The algorithm is based on the theory of adjacency matrix and combined the feature of the matrix arithmetic operations and the requirement of public transport inquiry system, which can effectively find out the optimal number of transfers routes and can also be extended to the railway and civil aviation inquiries.

Key words: adjacency matrix; public transport inquiry system; mathematical model

城市公共交通是一个城市的重要基础设施，是关系民生的社会公益事业。与其他出行方式相比，公交具有价格便宜、乘用方便安全、线路分布较广、道路占用率低、耗能低廉等优势，是解决城市交通拥堵的有效途径。发展城市公共交通是改善城市人居环境、构建和谐社会、促进城市可持续发展的必然要求，是科学发展观在城市建设和管理工作中的具体体现。

随着城市规模不断扩大，公交线路互连交汇，错综复杂，选择一条高效便捷的出行方案，使当地居民、外地游客获取足够的公交出行信息很有必要。对于每个城市公交查询系统，乘客均会面临多条线路的选择问题。通常，乘客需要在最少站数的路径和换乘次数最少的路径中做出选择。由于乘客换乘公交需要等待下一趟公交，大多乘客在路径差距不是很大的情况下更愿意选择换乘次数最少的乘车路线。该文正是基于这个特点，讨论公共交通网络中如何寻找两个结点间的一条路径使之换车次数最优。……