·486 智能系统学报 第10卷 即S4中的S,站点与S。站点可与S。站点直达，而 query system of transit network[J].Journal of Liaoning 且它们分别都在L,线路上，则可求得 Technical University:Social Science Edition,2008,10 d(S4,So)= (4):380-382. min{o.5+03.g+0g.g,o8.6+0.g+0g.g}= [5]伍雁鹏，彭小奇，杨恒伏.改进的基于关系数据库技术 的公交查询算法[J].中南大学学报：自然科学版， min{6+7+5,1+4+5}=10 2009,40(3):763-766. 对应最优路线为从S,站点乘坐地铁线路L。到达 WU Yanpeng,PENG Xiaoqi,YANG Hengfu.Improved al- S。站点，转乘公交线路L3到达S。站点，再转乘公 gorithm based on relational database technology for querying 交线路L,到达S。站点，途径10站。 transit network[].Journal of Central South University:Sci- 5结束语 ence and Technology,2009,40(3):763-766. [6]刘健，徐维祥，刘旭敏.公交出行最优路线查询系统设 在文献[10]的基础上，将公交地铁进行一体化 计[J].计算机应用，2009,29(S2):110-112. 标号，缩小地铁两站点间的路径距离以达到优选地 LIU Jian,XU Weixiang,LIU Xumin.Design of urban pub- 铁的目的。据乘客出行心理，依次以换乘次数少、出 lic transit optimal route inquiry system[J].Journal of Com- 行距离短为优化目标，利用高维数组运算，根据公交 puter Applications,2009,29(S2):110-112. [7]伍雁鹏，彭小奇，黄同成.基于路径集合运算的公交网 地铁网络图与二分图、线路映射网络图、站点映射网 络寻径算法研究[J].计算机科学，2009,36(6)：239 络图得到两站点间的最优路径的选择算法。 240,272. 公交网络的寻径问题一直以来被认为是NP难 WU Yanpeng,PENG Xiaoqi,HUANG Tongcheng.Re- 问题，而日益发达的公交系统对最优路径选择算法的 search on path set operation based algorithm for path search- 要求也越来越高。因此，改进和创新算法在整个公交 ing in public transit network[J].Computer Science,2009. 系统中至关重要。本文尚未将地铁的时变性考虑在 36(6):239-240,272. 内，可对此进一步研究，使得人们无论何时出行都有 [8]刘作虎，黄明和，邹小云，等.一种网络公交查询系统 一个对应此时间点的方案，使查询更加精确可靠。 的改进算法[J].计算机与信息技术，2009，(4)：29-31. [9]徐勇，李杰，张军芳，等.新型公交网络模型与最优线 参考文献： 路选择算法[J].系统工程理论与实践，2011,31(11)： 2234-2240. [1]闫小勇，尚艳亮.基于二部图模型的公交网络路径搜索 XU Yong,LI Jie,ZHANG Junfang,et al.New urban transit 算法[J].计算机工程与应用，2010,46(5)：246-248. network models and optimal path searching algorithm[J]. YAN Xiaoyong,SHANG Yanliang.Path-finding algorithm of Systems Engineering-Theory and Practice,2011,31 public transport networks based on bipartite graph model (11）：2234-2240. [J].Computer Engineering and Applications,2010,46 [10]刘旭浩，徐勇.基于半张量积理论的公交网络查询[J]. (5):246-248. 复杂系统与复杂性科学，2013,10(1)：38-44. [2]梁虹，袁小群，刘蕊.一种新的公交数据模型与公交查 LIU Xuhao,XU Yong.An inquiry method of transit net- 询系统实现[J].计算机工程与应用，2007,43(3)：234 work based on semi-tensor productJ.Complex Systems 238. and Complexity Science,2013,10(1):38-44. LIANG Hong,YUAN Xiaoqun,LIU Rui.Novel model and [11]张林峰，范炳全，吕智林.公交网络换乘矩阵的分析与 realization of public transport route inquiring system[J]. 算法[J].系统工程，2003,21(6)：92-96. Computer Engineering and Applications,2007,43(3): ZHANG Linfeng,FAN Bingquan,LO Zhilin.Transfer ma- 234-238. trix of public transit network and algorithm J.Systems [3]王海帅，冀振燕，王森.公交线路查询算法[J].计算机 Engineering,2003,21(6):92-96. 系统应用，2013,22(2)：88-91. [12]程代展，齐洪胜.矩阵的半张量积理论与应用[M].北 WANG Haishuai,JI Zhenyan,WANG Sen.Bus transport 京：科学出版社，2007. transfer algorithm[J].Computer Systems and Applications, [13]YAO Baozhen,HU Ping,LU Xiaohong,et al.Transit net- 2013,22(2):88-91. work design based on travel time reliability[J].Transpor- [4]王防肠，于丽娜，郑保华，等.“集合燃烧”算法在公交 tation Research,Part C:Emerging Technologies,2014, 网络查询中的应用[J].辽宁工程技术大学学报：社会 43(3):233-248. 科学版，2008,10(4)：380-382 [14]张译，靳香翔，张毅，等.基于二分图的城市公交网络 WANG Fangyang,YU Lina,ZHENG Baohua,et al."Ag- 拓扑性质研究[J].系统工程理论与实践，2007,27 gregate-combustion"arithmetic and its application in the (7):149-155.即 Ｓ ′ ４ 中的 Ｓ５ 站点与 Ｓ６ 站点可与 Ｓ８ 站点直达，而 且它们分别都在 Ｌ３ 线路上，则可求得 ｄ（ Ｓ４ ，Ｓ９ ） ＝ ｍｉｎ ｗ ２ ４，５ ＋ ｗ ３ ５，８ ＋ ｗ ４ ８，９ ，ｗ ０ ４，６ ＋ ｗ ３ ６，８ ＋ ｗ ４ ８，９ { } ＝ ｍｉｎ｛ ６ ＋ ７ ＋ ５，１ ＋ ４ ＋ ５｝ ＝ １０ 对应最优路线为从 Ｓ４ 站点乘坐地铁线路 Ｌ０ 到达 Ｓ６ 站点，转乘公交线路 Ｌ３ 到达 Ｓ８ 站点，再转乘公 交线路 Ｌ４ 到达 Ｓ９ 站点，途径 １０ 站。 ５ 结束语 在文献［１０］的基础上，将公交地铁进行一体化 标号，缩小地铁两站点间的路径距离以达到优选地 铁的目的。 据乘客出行心理，依次以换乘次数少、出 行距离短为优化目标，利用高维数组运算，根据公交 地铁网络图与二分图、线路映射网络图、站点映射网 络图得到两站点间的最优路径的选择算法。 公交网络的寻径问题一直以来被认为是 ＮＰ 难 问题，而日益发达的公交系统对最优路径选择算法的 要求也越来越高。 因此，改进和创新算法在整个公交 系统中至关重要。 本文尚未将地铁的时变性考虑在 内，可对此进一步研究，使得人们无论何时出行都有 一个对应此时间点的方案，使查询更加精确可靠。 参考文献： ［１］闫小勇， 尚艳亮． 基于二部图模型的公交网络路径搜索 算法［Ｊ］． 计算机工程与应用， ２０１０， ４６（５）： ２４６⁃２４８． ＹＡＮ Ｘｉａｏｙｏｎｇ， ＳＨＡＮＧ Ｙａｎｌｉａｎｇ． Ｐａｔｈ⁃ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｐｏｒｔ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｍｏｄｅｌ ［Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０， ４６ （５）： ２４６⁃２４８． ［２］梁虹， 袁小群， 刘蕊． 一种新的公交数据模型与公交查 询系统实现［Ｊ］． 计算机工程与应用， ２００７， ４３（３）： ２３４⁃ ２３８． ＬＩＡＮＧ Ｈｏｎｇ， ＹＵＡＮ Ｘｉａｏｑｕｎ， ＬＩＵ Ｒｕｉ． Ｎｏｖｅｌ ｍｏｄｅｌ ａｎｄ ｒｅａｌｉｚａｔｉｏｎ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｐｏｒｔ ｒｏｕｔｅ ｉｎｑｕｉｒｉｎｇ ｓｙｓｔｅｍ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００７， ４３ （ ３ ）： ２３４⁃２３８． ［３］王海帅， 冀振燕， 王森． 公交线路查询算法［ Ｊ］． 计算机 系统应用， ２０１３， ２２（２）： ８８⁃９１． ＷＡＮＧ Ｈａｉｓｈｕａｉ， ＪＩ Ｚｈｅｎｙａｎ， ＷＡＮＧ Ｓｅｎ． Ｂｕｓ ｔｒａｎｓｐｏｒｔ ｔｒａｎｓｆｅｒ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１３， ２２（２）： ８８⁃９１． ［４］王昉旸， 于丽娜， 郑保华， 等． “集合燃烧”算法在公交 网络查询中的应用［ Ｊ］． 辽宁工程技术大学学报： 社会 科学版， ２００８， １０（４）： ３８０⁃３８２． ＷＡＮＧ Ｆａｎｇｙａｎｇ， ＹＵ Ｌｉｎａ， ＺＨＥＮＧ Ｂａｏｈｕａ， ｅｔ ａｌ． “Ａｇ⁃ ｇｒｅｇａｔｅ⁃ｃｏｍｂｕｓｔｉｏｎ” ａｒｉｔｈｍｅｔｉｃ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｔｈｅ ｑｕｅｒｙ ｓｙｓｔｅｍ ｏｆ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｏｎｉｎｇ Ｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ： Ｓｏｃｉａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ， ２００８， １０ （４）： ３８０⁃３８２． ［５］伍雁鹏， 彭小奇， 杨恒伏． 改进的基于关系数据库技术 的公交查询算法 ［ Ｊ］． 中南大学学报： 自然科学版， ２００９， ４０（３）： ７６３⁃７６６． ＷＵ Ｙａｎｐｅｎｇ， ＰＥＮＧ Ｘｉａｏｑｉ， ＹＡＮＧ Ｈｅｎｇｆｕ． Ｉｍｐｒｏｖｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒｅｌａｔｉｏｎａｌ ｄａｔａｂａｓｅ ｔｅｃｈｎｏｌｏｇｙ ｆｏｒ ｑｕｅｒｙｉｎｇ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ： Ｓｃｉ⁃ ｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００９， ４０（３）： ７６３⁃７６６． ［６］刘健， 徐维祥， 刘旭敏． 公交出行最优路线查询系统设 计［Ｊ］． 计算机应用， ２００９， ２９（Ｓ２）： １１０⁃１１２． ＬＩＵ Ｊｉａｎ， ＸＵ Ｗｅｉｘｉａｎｇ， ＬＩＵ Ｘｕｍｉｎ． Ｄｅｓｉｇｎ ｏｆ ｕｒｂａｎ ｐｕｂ⁃ ｌｉｃ ｔｒａｎｓｉｔ ｏｐｔｉｍａｌ ｒｏｕｔｅ ｉｎｑｕｉｒｙ ｓｙｓｔｅｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００９， ２９（Ｓ２）： １１０⁃１１２． ［７］伍雁鹏， 彭小奇， 黄同成． 基于路径集合运算的公交网 络寻径算法研究［ Ｊ］． 计算机科学， ２００９， ３６（ ６）： ２３９⁃ ２４０， ２７２． ＷＵ Ｙａｎｐｅｎｇ， ＰＥＮＧ Ｘｉａｏｑｉ， ＨＵＡＮＧ Ｔｏｎｇｃｈｅｎｇ． Ｒｅ⁃ ｓｅａｒｃｈ ｏｎ ｐａｔｈ ｓｅｔ ｏｐｅｒａｔｉｏｎ ｂａｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐａｔｈ ｓｅａｒｃｈ⁃ ｉｎｇ ｉｎ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００９， ３６（６）： ２３９⁃２４０， ２７２． ［８］刘作虎， 黄明和， 邹小云， 等． 一种网络公交查询系统 的改进算法［Ｊ］． 计算机与信息技术， ２００９， （４）： ２９⁃３１． ［９］徐勇， 李杰， 张军芳， 等． 新型公交网络模型与最优线 路选择算法［Ｊ］． 系统工程理论与实践， ２０１１， ３１（１１）： ２２３４⁃２２４０． ＸＵ Ｙｏｎｇ， ＬＩ Ｊｉｅ， ＺＨＡＮＧ Ｊｕｎｆａｎｇ， ｅｔ ａｌ． Ｎｅｗ ｕｒｂａｎ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ—Ｔｈｅｏｒｙ ａｎｄ Ｐｒａｃｔｉｃｅ， ２０１１， ３１ （１１）： ２２３４⁃２２４０． ［１０］刘旭浩， 徐勇． 基于半张量积理论的公交网络查询［ Ｊ］． 复杂系统与复杂性科学， ２０１３， １０（１）： ３８⁃４４． ＬＩＵ Ｘｕｈａｏ， ＸＵ Ｙｏｎｇ． Ａｎ ｉｎｑｕｉｒｙ ｍｅｔｈｏｄ ｏｆ ｔｒａｎｓｉｔ ｎｅｔ⁃ ｗｏｒｋ ｂａｓｅｄ ｏｎ ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ［ Ｊ］． Ｃｏｍｐｌｅｘ Ｓｙｓｔｅｍｓ ａｎｄ Ｃｏｍｐｌｅｘｉｔｙ Ｓｃｉｅｎｃｅ， ２０１３， １０（１）： ３８⁃４４． ［１１］张林峰， 范炳全， 吕智林． 公交网络换乘矩阵的分析与 算法［Ｊ］． 系统工程， ２００３， ２１（６）： ９２⁃９６． ＺＨＡＮＧ Ｌｉｎｆｅｎｇ， ＦＡＮ Ｂｉｎｇｑｕａｎ， ＬÜ Ｚｈｉｌｉｎ． Ｔｒａｎｓｆｅｒ ｍａ⁃ ｔｒｉｘ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ａｎｄ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００３， ２１（６）： ９２⁃９６． ［１２］程代展， 齐洪胜． 矩阵的半张量积理论与应用［Ｍ］． 北 京： 科学出版社， ２００７． ［１３］ＹＡＯ Ｂａｏｚｈｅｎ， ＨＵ Ｐｉｎｇ， ＬＵ Ｘｉａｏｈｏｎｇ， ｅｔ ａｌ． Ｔｒａｎｓｉｔ ｎｅｔ⁃ ｗｏｒｋ ｄｅｓｉｇｎ ｂａｓｅｄ ｏｎ ｔｒａｖｅｌ ｔｉｍｅ ｒｅｌｉａｂｉｌｉｔｙ［ Ｊ］． Ｔｒａｎｓｐｏｒ⁃ ｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ， Ｐａｒｔ Ｃ： Ｅｍｅｒｇｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ， ２０１４， ４３（３）： ２３３⁃２４８． ［１４］张译， 靳雪翔， 张毅， 等． 基于二分图的城市公交网络 拓扑性质研究［ Ｊ］． 系统工程理论与实践， ２００７， ２７ （７）： １４９⁃１５５． ·４８６· 智 能 系 统 学 报 第 １０ 卷