基于分布式蚁群算法的城市路网动态最短路径搜索研究与实现
|
摘要
随着社会的发展与进步,城市规模在不断的扩大,交通网络越来越复杂,并且出现了大规模性、动态性等新的特征,传统最短路径搜索无法满足居民快捷出行的动态服务需求。近年来,浮动车采集技术被应用于交通管理与控制,同时积累了大量的数据,为获取路网的动态运行特征提供了基础,因此研究动态特征下的大规模路网最短路径搜索具有理论和实践意义。经典的最短路算法如Dijkstra算法、Floyd算法等多应用于静态路网的前提下,且并行化特性差,很难高效地求解动态最短路问题,因此本文的研究主题是基于分布式蚁群算法求解大规模路网下面向小汽车最短出行时间的动态最短路径搜索问题。
论文首先通过对比分析,选择蚁群算法作为动态路径搜索算法,并对其基本原理、研究现状和并行计算模型进行研究综述；随后对浮动车数据获取路段平均速度方法进行研究,提出了利用多个浮动车样本的行驶时间和距离加权集成的方法获得短时的路段平均速度,作为动态路径选择的基础；其次根据大规模路网的特性,针对基本蚁群算法计算时间长、局部收敛的问题提出了单只蚂蚁路径选择优化和自适应信息素更新两种改进策略；然后在研究了分布式计算理论和蚁群算法并行化特点的基础上,设计了主从式定期交互和广播式触发交互结合的并行策略,并利用基于消息的MPI编程模型在MPICH2平台下实现了并行算法的开发；最后介绍了所开发的分布式计算实验平台和进行蚁群算法关键参数的选择,在此基础上设计多次路径搜索实验,实验结果表明该方法在运行时间和计算结果方面都具有明显的优势,具有良好的实用性。
With the social development and progress, the cities are keeping expanding. Traffic networks in large cities become more and more complex and present some new features with large-scale and dynamic characteristics. Traditional shortest path search cannot meet residents' dynamic service demand on fast travelling. In recent years, floating car technology has been applied widely in the traffic management and control area and a great deal of data are accumulated. This provides foundations for the researchers to obtain the dynamic road network features. Therefore, the research on the dynamic shortest path search has a high theoretical and practical significance. The classic shortest path search algorithms, such as Dijkstra algorithm and Floyd algorithm, are widely used in static network and difficult for parallel computing, which make them difficult to efficiently solve the dynamic shortest path problem. Therefore, this thesis has focused on using distributed ant colony algorithm to solve the dynamic shortest path search problem in large scale network to meet the car travelers' requirement for the shortest travel time.
Firstly, by comparing with other algorithms, ant colony algorithm (i.e. ACO) is selected for dynamic path search and the basic principle and researches on ACO algorithm, as well as parallel computing model are reviewed. Secondly, the research on how to aggregate section average velocity with floating car data is conducted. The travel time and distance weighted aggregation method using samples of floating car records to obtain the time-varying average section speed is proposed, which provides the basis for dynamic path search. Thirdly, according to the characteristics of large-scale network, two improvement strategies of ACO algorithm are put forward to reduce the computing time and avoid the local convergence. One is the optimization of single ant routing and the other is adaptive pheromone update strategy. Then, based on the theory of distributed computing and the characteristics of parallel ACO algorithm, a parallel program of master-slave type regular interaction method combined with radio type trigger interaction method among sub ant colonies is designed. MPI programming model is used to develop parallel ACO algorithm in MPICH2platform. Finally, the method to build the distributed computing platform is introduced and key parameters of ACO algorithm are selected. Experiments on multiple path search are conducted. The experimental results show that the developed algorithm has obvious advantages in both of running time and calculation results, which proves its high performance.
论文首先通过对比分析,选择蚁群算法作为动态路径搜索算法,并对其基本原理、研究现状和并行计算模型进行研究综述；随后对浮动车数据获取路段平均速度方法进行研究,提出了利用多个浮动车样本的行驶时间和距离加权集成的方法获得短时的路段平均速度,作为动态路径选择的基础；其次根据大规模路网的特性,针对基本蚁群算法计算时间长、局部收敛的问题提出了单只蚂蚁路径选择优化和自适应信息素更新两种改进策略；然后在研究了分布式计算理论和蚁群算法并行化特点的基础上,设计了主从式定期交互和广播式触发交互结合的并行策略,并利用基于消息的MPI编程模型在MPICH2平台下实现了并行算法的开发；最后介绍了所开发的分布式计算实验平台和进行蚁群算法关键参数的选择,在此基础上设计多次路径搜索实验,实验结果表明该方法在运行时间和计算结果方面都具有明显的优势,具有良好的实用性。
With the social development and progress, the cities are keeping expanding. Traffic networks in large cities become more and more complex and present some new features with large-scale and dynamic characteristics. Traditional shortest path search cannot meet residents' dynamic service demand on fast travelling. In recent years, floating car technology has been applied widely in the traffic management and control area and a great deal of data are accumulated. This provides foundations for the researchers to obtain the dynamic road network features. Therefore, the research on the dynamic shortest path search has a high theoretical and practical significance. The classic shortest path search algorithms, such as Dijkstra algorithm and Floyd algorithm, are widely used in static network and difficult for parallel computing, which make them difficult to efficiently solve the dynamic shortest path problem. Therefore, this thesis has focused on using distributed ant colony algorithm to solve the dynamic shortest path search problem in large scale network to meet the car travelers' requirement for the shortest travel time.
Firstly, by comparing with other algorithms, ant colony algorithm (i.e. ACO) is selected for dynamic path search and the basic principle and researches on ACO algorithm, as well as parallel computing model are reviewed. Secondly, the research on how to aggregate section average velocity with floating car data is conducted. The travel time and distance weighted aggregation method using samples of floating car records to obtain the time-varying average section speed is proposed, which provides the basis for dynamic path search. Thirdly, according to the characteristics of large-scale network, two improvement strategies of ACO algorithm are put forward to reduce the computing time and avoid the local convergence. One is the optimization of single ant routing and the other is adaptive pheromone update strategy. Then, based on the theory of distributed computing and the characteristics of parallel ACO algorithm, a parallel program of master-slave type regular interaction method combined with radio type trigger interaction method among sub ant colonies is designed. MPI programming model is used to develop parallel ACO algorithm in MPICH2platform. Finally, the method to build the distributed computing platform is introduced and key parameters of ACO algorithm are selected. Experiments on multiple path search are conducted. The experimental results show that the developed algorithm has obvious advantages in both of running time and calculation results, which proves its high performance.
引文
[1]袁振洲,刘梦涵,于雷.ITS数据管理技术发展趋势分析[J].科技导报.2003(1)：40-43.
[2](?)家伟.基于浮动车技术的道路交通特性分析及系统实现.[硕士学位论文].天津大学.2009.
[3]Douglas R Shier. Network Reliability and Algebraic Structures [M] Oxford: Clarendon Press,1991:8-17.
[4]刘霞,李明树,王青等.软件体系结构分析与评价方法评述[J].计算机研究与发展.2005,42(7)：1247-1254.
[5]孙煮,王秀坤,刘业欣.一种简单蚂蚁算法及其收敛性分析.小型微型计算机系统.2003,24(8),1524-1527.
[6]北京市交通发展研究中心.交通拥堵指数解读.北京市交通发展研究中心网站2011-03-14[2012-05-03].http://www.bjtrc.org.cn/PageLayout/IndexReleased/IndexReader.aspx?menuid=li4
[7]与非电子电路技术网站RDS-TMC技术简介及其在欧洲的应用.2006-11-28[2012-05-07].http://www.eefocus.com/article/06-11/061002458970.html.
[8]高娜,贾辉然.蚁群算法在城市交通系统中的应用[J].河北工业科技.2010(3)：205
[9]柴晨.基于AIS的动态路径搜索算法研究[J].廊坊师范学院学报(自然科学版),2009(4)：40
[10]许震洪.动态路径诱导系统的最优路径算法研究及相关软件实现.[硕士毕业论文].南京理工大学.2009
[11]蔡辉.GIS环境下动态路径优化算法问题的研究.[硕士学位论文]长沙理工大学.2006
[12]Anthony Stentz. The Focused D* Algorithm for Real-Time Replanning[C]. Proceedings of the International Joint Conference on Artificial Intelligence, 1995,(8).
[13]Ismail Chabini. Discrete Dynamic Shortest Path Problems In Transportation Applications: Complexity and Algorithms with Optimal Run Time[J].Transportation Research Records, 1998.
[14]王峰,游志胜,曼丽春,高燕,汤丽萍.Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用[J].计算机应用研究.2006(9)：203-208.
[15]田鹏飞,王剑英.动态最短路径算法及其仿真[J].计算机仿真,2007(6)：153-156.
[16]蔡自兴,徐光佑.人工智能及其应用[M].清华大学出版社,2000：60-88.
[17]刘名龙,黄德铺,徐天洋.城市道路网最短路径启发算法研究[J].公路交通科技.2006,23(8)：136-138.
[18]景玲,黄席越.潘娅.基于遗传算法的动态路径诱导[I].重庆大学学报(自然科学 版).2002,25(4)：68-70.
[19]WeiBo Zhang, ZhenHua Lu, Guangyu Zhu. Optimization of Process Route by Genetic Algorithms. Robotics and Computer-Intergraded Manufacturing, 2006(22):180-182.
[20]李松江.基于改进遗传算法的动态路径诱导系统的研究[硕士学位论文].长春理工大学2009.
[21]邹亮,徐建闽,朱玲湘.遗传算法在动态路径诱导系统中的应用[J].交通运输系统工程与信.2007(7)：46-48.
[22]杨兆升.城市交通流诱导系统理论与模型[M].北京：人民交通出版社,2000.
[23]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,23(5)：742-744.
[24]张元亮,郑南宁,代颖.基于遗传算法的混合分形编码.自动化学报1999,25(1)：143-144.
[25]李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社.2004：219-260.
[26]蚁群算法百度百科.[2012-04-12]http://baike.baidu.com/view/539346.htm.
[27]Colorni A, Dorigo Mand Maniezo V. Distributed Optimization by Ant Colonies [A],Proc. Of 1st European Conf. Artificial Life, France: Elsevier.1991:34-142.
[28]祝永华.改进的蚁群算法及其应用研究[D].杭州：浙江工业大学,2010.
[29]Dorigo, GD Caro. Ants Algorithm for discrete problem [R]. Tech. Rep. IRDI A:98-100.
[30]叶志伟.蚁群算法中参数的设置的研究[J].武汉大学学报：信息科版,2004,8(7).
[31]李祚泳.基于蚁群算法的两地之间的最佳路径选择[J].系统工程,2004,23(7).
[32]陈峻,沈洁,秦玲.蚁群算法进行连续参数优化的新途径[J].系统工程理论与实践.2003(3).
[33]M Dorigo and LM Gambardella. Ant colonies for the traveling salesman problem. BioSystems[J].1997,43(2):73-81.
[34]T Stutzle, H Hoos. Max-Min Ant System[J]. Future Generation Computer Systems.2000(16): 889-915.
[35]徐纪峰,张开旺,王晓原.基于自适应蚁群算法的最短路径搜索方法研究[J].中国科技信息,2008,23(12)：81,82.
[36]陈烨.带杂交算子的蚁群算法[J].计算机工程,2001(12).
[37]赵辉,徐俊刚.基于OpenMP多核架构下并行蚁群算法研究[J].微型机与应用.2011(16)：6-11.
[38]章春芳.自适应并行蚁群算法及其应用.[硕士学位论文].扬州大学.2006
[39]阎芳,杨玺,陈蕾.基于OpenMP的并行蚁群物流调度算法研究[J].物流技术.2010(7)：90-93.
[40]朱清新.计算机算法设计与分析导论[M].人民邮电出版社,2007.
[41]张丽丽,张玉清.基于分布式计算的暴力破解分组密码算法[J].计算机工程.2008,34(13).
[42]http://baike.baidu.com/view/30655.htm
[43]陈国良.并行计算——结构、算法、编程[M],北京：高等教育出版社,1999.
[44]张祖平,王丽.基于生物计算的分布式计算系统[J].计算机工程.2008.34(2).
[45]都志辉.高性能计算并行编程技术一性能计并行程序设计[M].清华大学出版社,2001.
[46]李成华,张新访,金海,向文MapReduce:新型的分布式并行计算编程模型[J].计算机工程与科学.2011(33)：129-133.
[47]高艺.基于一次拥堵的城市交通拥堵综合评价方法研究.[硕士学位论文].北京交通大学.2011
[48]王力,王川久,张海,范跃祖.基于浮动车的城市动态交通信息采集处理方法研究[C].第一届中国智能交通年会论文集,2005：291-296.
[49]龚珊.基于浮动车GPS数据的行车速度预测模型研究.[硕士毕业论文].北京交通大学.
[50]孙力娟,王良俊,王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报2004,25(10)：111-116.
[51]Maniezzo V,Antonella C.Ant Colony Optimization:An Overview. Essays and Surveys in Metaheuristics[J].2001:21-44.
[52]Bullnheimer B,Richard F. Hartl,Christine Strauss. An Improved Ant System Algorithm for the Vehicle Routing Problem[J]. Annals of Operations Research,1999,8(9):319-328.
[53]黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报.2004,32(5)：865-868.
[54]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制.2002,31(3)：198-210.
[55]丁建立,陈增强,袁著扯.基于自适应蚂蚁算法的动态最优路由选择[J].控制与决策,2003,18(6)：751-753.
[56]李艳君,吴铁军.求解混杂生产调度问题的嵌套混合蚁群算法[J].自动化学报.2003,291(1)：525-528.
[57]孙煮,王秀坤,刘业欣,张名举.一种简单蚂蚁算法及其收敛性分析.小型微型计算机系统.2003,24(8)：1524-1527.
[58]Piriyakumar D.A.L.A New Approach to Exploiting Parallelism in Ant Colony Optimization. Micromechatronics and Human Science,2002:237-243.
[59]闻育.分布式蚁群算法设计与分析.[博士后研究工作报告].浙江大学.2006.
[60]陈恩修.离散群体智能算法的研究与应用.[硕士学位论文].山东师范大学.2009.
[61]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报.2004,15(2)：185-192.
[62]向晓明.基于分布式蚁群算法的TSP问题研究.[硕士学位论文].西南交通大学.2006.
[63]汪鹏飞.并行蚁群算法及其应用研究.[硕士毕业论文].西南交通大学.2008.
[64]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报.2004,15(2)：185-192.
[65]Guoliang Chen, Hong An, Parallel Algorithm Practice[M],High Education Press, 2004.
[66]叶茂,缪纶,王志璋,李江华.基于LINUX和MPICH2的高性能科学计算集群搭建及其性能评测[J].中国水利水电科学研究院学报.2009,12：302-306.
[67]MPICH2: High-performance and Widely Portable MPI. About MPICH2. 2009-09-02 [2012-04-10].http://www.mcs.anl.gov/research/projects/mpich2/about/index.php?s=about
[68]严蔚敏,吴伟民.数据结构[M].清华大学出版社,1996.
[69]Michalewicz Z.Genetic Algorithms + Data Structures = Evolution Programs[M]. Springer Verlag,Berlin.1998.
[70]刘坤.基于蚁群算法的轨道交通路径选择模型及应用研究.[硕士学位论文].北京交通大学.2011.
[71]詹士昌,徐婕,吴俊.蚁群算法中有关参数的最优选择[J].科技通报.2003,19(5)：381-386.
[72]M.Dorigo,T.Sttizle.Ant Colony Optimization.MIT Press,2004.
[2](?)家伟.基于浮动车技术的道路交通特性分析及系统实现.[硕士学位论文].天津大学.2009.
[3]Douglas R Shier. Network Reliability and Algebraic Structures [M] Oxford: Clarendon Press,1991:8-17.
[4]刘霞,李明树,王青等.软件体系结构分析与评价方法评述[J].计算机研究与发展.2005,42(7)：1247-1254.
[5]孙煮,王秀坤,刘业欣.一种简单蚂蚁算法及其收敛性分析.小型微型计算机系统.2003,24(8),1524-1527.
[6]北京市交通发展研究中心.交通拥堵指数解读.北京市交通发展研究中心网站2011-03-14[2012-05-03].http://www.bjtrc.org.cn/PageLayout/IndexReleased/IndexReader.aspx?menuid=li4
[7]与非电子电路技术网站RDS-TMC技术简介及其在欧洲的应用.2006-11-28[2012-05-07].http://www.eefocus.com/article/06-11/061002458970.html.
[8]高娜,贾辉然.蚁群算法在城市交通系统中的应用[J].河北工业科技.2010(3)：205
[9]柴晨.基于AIS的动态路径搜索算法研究[J].廊坊师范学院学报(自然科学版),2009(4)：40
[10]许震洪.动态路径诱导系统的最优路径算法研究及相关软件实现.[硕士毕业论文].南京理工大学.2009
[11]蔡辉.GIS环境下动态路径优化算法问题的研究.[硕士学位论文]长沙理工大学.2006
[12]Anthony Stentz. The Focused D* Algorithm for Real-Time Replanning[C]. Proceedings of the International Joint Conference on Artificial Intelligence, 1995,(8).
[13]Ismail Chabini. Discrete Dynamic Shortest Path Problems In Transportation Applications: Complexity and Algorithms with Optimal Run Time[J].Transportation Research Records, 1998.
[14]王峰,游志胜,曼丽春,高燕,汤丽萍.Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用[J].计算机应用研究.2006(9)：203-208.
[15]田鹏飞,王剑英.动态最短路径算法及其仿真[J].计算机仿真,2007(6)：153-156.
[16]蔡自兴,徐光佑.人工智能及其应用[M].清华大学出版社,2000：60-88.
[17]刘名龙,黄德铺,徐天洋.城市道路网最短路径启发算法研究[J].公路交通科技.2006,23(8)：136-138.
[18]景玲,黄席越.潘娅.基于遗传算法的动态路径诱导[I].重庆大学学报(自然科学 版).2002,25(4)：68-70.
[19]WeiBo Zhang, ZhenHua Lu, Guangyu Zhu. Optimization of Process Route by Genetic Algorithms. Robotics and Computer-Intergraded Manufacturing, 2006(22):180-182.
[20]李松江.基于改进遗传算法的动态路径诱导系统的研究[硕士学位论文].长春理工大学2009.
[21]邹亮,徐建闽,朱玲湘.遗传算法在动态路径诱导系统中的应用[J].交通运输系统工程与信.2007(7)：46-48.
[22]杨兆升.城市交通流诱导系统理论与模型[M].北京：人民交通出版社,2000.
[23]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,23(5)：742-744.
[24]张元亮,郑南宁,代颖.基于遗传算法的混合分形编码.自动化学报1999,25(1)：143-144.
[25]李士勇.蚁群算法及其应用[M].哈尔滨工业大学出版社.2004：219-260.
[26]蚁群算法百度百科.[2012-04-12]http://baike.baidu.com/view/539346.htm.
[27]Colorni A, Dorigo Mand Maniezo V. Distributed Optimization by Ant Colonies [A],Proc. Of 1st European Conf. Artificial Life, France: Elsevier.1991:34-142.
[28]祝永华.改进的蚁群算法及其应用研究[D].杭州：浙江工业大学,2010.
[29]Dorigo, GD Caro. Ants Algorithm for discrete problem [R]. Tech. Rep. IRDI A:98-100.
[30]叶志伟.蚁群算法中参数的设置的研究[J].武汉大学学报：信息科版,2004,8(7).
[31]李祚泳.基于蚁群算法的两地之间的最佳路径选择[J].系统工程,2004,23(7).
[32]陈峻,沈洁,秦玲.蚁群算法进行连续参数优化的新途径[J].系统工程理论与实践.2003(3).
[33]M Dorigo and LM Gambardella. Ant colonies for the traveling salesman problem. BioSystems[J].1997,43(2):73-81.
[34]T Stutzle, H Hoos. Max-Min Ant System[J]. Future Generation Computer Systems.2000(16): 889-915.
[35]徐纪峰,张开旺,王晓原.基于自适应蚁群算法的最短路径搜索方法研究[J].中国科技信息,2008,23(12)：81,82.
[36]陈烨.带杂交算子的蚁群算法[J].计算机工程,2001(12).
[37]赵辉,徐俊刚.基于OpenMP多核架构下并行蚁群算法研究[J].微型机与应用.2011(16)：6-11.
[38]章春芳.自适应并行蚁群算法及其应用.[硕士学位论文].扬州大学.2006
[39]阎芳,杨玺,陈蕾.基于OpenMP的并行蚁群物流调度算法研究[J].物流技术.2010(7)：90-93.
[40]朱清新.计算机算法设计与分析导论[M].人民邮电出版社,2007.
[41]张丽丽,张玉清.基于分布式计算的暴力破解分组密码算法[J].计算机工程.2008,34(13).
[42]http://baike.baidu.com/view/30655.htm
[43]陈国良.并行计算——结构、算法、编程[M],北京：高等教育出版社,1999.
[44]张祖平,王丽.基于生物计算的分布式计算系统[J].计算机工程.2008.34(2).
[45]都志辉.高性能计算并行编程技术一性能计并行程序设计[M].清华大学出版社,2001.
[46]李成华,张新访,金海,向文MapReduce:新型的分布式并行计算编程模型[J].计算机工程与科学.2011(33)：129-133.
[47]高艺.基于一次拥堵的城市交通拥堵综合评价方法研究.[硕士学位论文].北京交通大学.2011
[48]王力,王川久,张海,范跃祖.基于浮动车的城市动态交通信息采集处理方法研究[C].第一届中国智能交通年会论文集,2005：291-296.
[49]龚珊.基于浮动车GPS数据的行车速度预测模型研究.[硕士毕业论文].北京交通大学.
[50]孙力娟,王良俊,王汝传.改进的蚁群算法及其在TSP中的应用研究[J].通信学报2004,25(10)：111-116.
[51]Maniezzo V,Antonella C.Ant Colony Optimization:An Overview. Essays and Surveys in Metaheuristics[J].2001:21-44.
[52]Bullnheimer B,Richard F. Hartl,Christine Strauss. An Improved Ant System Algorithm for the Vehicle Routing Problem[J]. Annals of Operations Research,1999,8(9):319-328.
[53]黄国锐,曹先彬,王煦法.基于信息素扩散的蚁群算法[J].电子学报.2004,32(5)：865-868.
[54]覃刚力,杨家本.自适应调整信息素的蚁群算法[J].信息与控制.2002,31(3)：198-210.
[55]丁建立,陈增强,袁著扯.基于自适应蚂蚁算法的动态最优路由选择[J].控制与决策,2003,18(6)：751-753.
[56]李艳君,吴铁军.求解混杂生产调度问题的嵌套混合蚁群算法[J].自动化学报.2003,291(1)：525-528.
[57]孙煮,王秀坤,刘业欣,张名举.一种简单蚂蚁算法及其收敛性分析.小型微型计算机系统.2003,24(8)：1524-1527.
[58]Piriyakumar D.A.L.A New Approach to Exploiting Parallelism in Ant Colony Optimization. Micromechatronics and Human Science,2002:237-243.
[59]闻育.分布式蚁群算法设计与分析.[博士后研究工作报告].浙江大学.2006.
[60]陈恩修.离散群体智能算法的研究与应用.[硕士学位论文].山东师范大学.2009.
[61]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报.2004,15(2)：185-192.
[62]向晓明.基于分布式蚁群算法的TSP问题研究.[硕士学位论文].西南交通大学.2006.
[63]汪鹏飞.并行蚁群算法及其应用研究.[硕士毕业论文].西南交通大学.2008.
[64]朱庆保,杨志军.基于变异和动态信息素更新的蚁群优化算法[J].软件学报.2004,15(2)：185-192.
[65]Guoliang Chen, Hong An, Parallel Algorithm Practice[M],High Education Press, 2004.
[66]叶茂,缪纶,王志璋,李江华.基于LINUX和MPICH2的高性能科学计算集群搭建及其性能评测[J].中国水利水电科学研究院学报.2009,12：302-306.
[67]MPICH2: High-performance and Widely Portable MPI. About MPICH2. 2009-09-02 [2012-04-10].http://www.mcs.anl.gov/research/projects/mpich2/about/index.php?s=about
[68]严蔚敏,吴伟民.数据结构[M].清华大学出版社,1996.
[69]Michalewicz Z.Genetic Algorithms + Data Structures = Evolution Programs[M]. Springer Verlag,Berlin.1998.
[70]刘坤.基于蚁群算法的轨道交通路径选择模型及应用研究.[硕士学位论文].北京交通大学.2011.
[71]詹士昌,徐婕,吴俊.蚁群算法中有关参数的最优选择[J].科技通报.2003,19(5)：381-386.
[72]M.Dorigo,T.Sttizle.Ant Colony Optimization.MIT Press,2004.