计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (2): 237-239.DOI: 10.3778/j.issn.1002-8331.2010.02.070

• 工程与应用 • 上一篇    下一篇

优化枚举算法研究与应用

肖华勇,郑娜莉,田 铮   

  1. 西北工业大学 理学院,西安 710072
  • 收稿日期:2008-12-17 修回日期:2009-04-27 出版日期:2010-01-11 发布日期:2010-01-11
  • 通讯作者: 肖华勇

Research and application with optimal enumeration algorithm of public traffic transfer

XIAO Hua-yong,ZHENG Na-li,TIAN Zheng   

  1. School of Science,Northwestern Polytechnical University,Xi’an 710072,China
  • Received:2008-12-17 Revised:2009-04-27 Online:2010-01-11 Published:2010-01-11
  • Contact: XIAO Hua-yong

摘要: 公交换乘问题在公共交通中是一个重要的问题。针对十分流行的8684公交网络查询系统只能查询到2次换乘的缺点,提出了一种对公交线路信息预先进行处理,然后采用减少站点和线路剪枝的优化枚举算法,可以实现换乘4次的优化线路;并用Visucal C++实现了该算法。通过对大型城市的公交网络的实际计算,与8684的查询结果进行比较;结果表明该算法不但可以提供更好的线路,而且还能提供8684无法提供的线路。实际计算时间不到1 s,能够到达实时性要求,因此算法具有很强的实用性和通用性,在公交网络中可以广泛采用。

关键词: 优化枚举算法, 换乘次数, 公交换乘, 实时性

Abstract: Public traffic transfer is an important problem.The shortcoming of the popular 8684 public transport network query system can only take two transfer times inquiries of the bus information.This paper offers the optimal enumeration algorithm,which processes the route information firstly,then uses to reduce stations and cut routes,can achieve optimization routes of four transfer times.The algorithm is realized with Visual C++.Through verifying the large cities public transportation information,and comparing with 8684 bus network query result,the results show that this algorithm can give a better route,and also can provide the routes that the 8684 can not give.The actual calculate time less than one second,can satisfy the real-time.Therefore the algorithm is of great practical and versatile,and can be widely used in the transit network.

Key words: optimal enumeration, transfer times, public traffic transfer, real-time

中图分类号: