公交最优路径选择的数学模型及算法

第１７卷第２期２００８年６月湖Ｊｏｕｒｎａｌ南ｏｆ城Ｈｕｎａｎ市学院学报（自然科学版）（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）、，０１．１７Ｎｏ．２Ｊｕｎ．２００８ＣｉｔｙＵｎｉＶｅｒｓｉｔｙ公交最优路径选择的数学模型及算法雷一鸣（广东工业大学华立学院，广州５１１３２５）摘要：在公交出行查询系统中，最关键的部分是寻找两站点间乘车的出行最优路径问题．建立了以最小换乘次数为第一目标，最小途经站点为第二目标的公交出行最优路径模型．同时，设计了一种算法以确定最优公交线路序列。分析了线路相交的几种情况，给出了换乘点选择方法．关键词：最优路径；换乘次数；公交网络中图分类号：０２３２文献标识码：Ａ文章编号：１６７２—７３０４（２００８）０２—００５０一０３公交最优路径问题一直是应用数学、运筹学、计算机科学等学科的一个研究热点．对公交最优路径问题的理论研究主要包括公交网络的数学描述和设计最优路径算法．在公交网络描述方面，Ａｎｅｚ等用对偶图描述能够涵盖公交线路的交置，并且知道可乘的各种公汽和地铁以及到达目的地有哪几种不同选择的机会．在公交线路网中，不同的公交线路在行程上一定会有重叠，也就是说不同的线路上一定会有同名站点．在进行网络分析时，把空间上相近的异线同名站点合理抽象成一个节点．３）假设出行者对公汽和地铁的偏好程度不一样．在不换乘的情况下，宁愿乘地铁，以求舒适；通网络，ｃｈｏｉ等讨论了利用ＧＩｓ技术从街道的地理数据产生公交线路和站点的问题；在设计最优算法方面，常用的算、法【ｕ有Ｄ冰ｓｔｒａ算法、Ｆｌｏｙｄ算法、Ｍｏｏｒｅ—ｐａｐｅ算法等．Ｍｏｏｒｅ—ｐａｐｅ算法计算速度较快，适用于大型网络，但它无法进行“一在路途较近的情况下，宁愿坐公汽而放弃乘地铁．出行者可根据自己的偏好结合自己的出行需求（换乘次数、最短路程、费用等），可在各种出对一”的计算．Ｆｌｏｙｄ算法虽然可以快速地进行“多对多”的计算，但它不能应用于大型网络，而Ｄｉｉｋｓｔｒａ算法是目前公认的最好的算法，但它数据结构复杂、算法时间长，不适合公交线路的查询．本文首先对公交网络进行了数学描述，考虑到公交乘客出行时所面临的各种重要因素，包括换乘次数、途径站点、出行耗时和出行费用等，行方案中选出满足自己出行需求的乘车方案．设Ｌ（，）为经过点Ａ或其附近的公交线路集，其中，＝ｌ，２，．．．，ｍ；ｓ（．，）为经过点Ｂ或其附近的公交线路集，其中．，＝，，２，．．．，，ｌ；Ｅ（，，ｕ）为线路Ｌ（，）上的站点，其中Ｕ＝Ｊ，２，．．．，ｐ；Ｆ（－，，ｙ）为线路Ｓ（，）上的站点，其中ｙ＝Ｊ，２，．．．，ｑ；ｘ（Ｋ）为经过站点Ｅ（，，Ｕ）的线路，其中Ｋ＝ｊ，２，．．．，ｗ；ｙ（Ｄ）为经过站点Ｆ（，，ｙ）的线路，其中Ｄ＝Ｊ『，２，．．．，ｖ；ｄ（Ｅ，Ｆ）≤Ｍ表示从站点Ｅ步行到站点，之间的距离不超过乘客换车时步行的最大心理承受值Ｍ，其中Ｍ表示乘客在换车时步行的最大心理承受值．通常，Ｍ与公交站点问的平均距离呈线性正相关．Ｚ。，表示站点Ａ的下行第ｉ个站点；Ｚ。，表示站点Ｂ的上行第．７个站点；另外，公交的可行线路的集合可表示为：选择以换乘次数最少作为最优路径算法的第一约束目标，而出行耗时虽难以准确测算但它与途径站点数相关，所以选择易于量化的途经站点数最少作为第二约束目标，建立公交乘车数学模型，设计相应的算法，并利用有关实验数据验证了它的有效性和可行性．１模型的建立及其算法１．１模型假设及符号规定为了更好地建立数学模型，首先对公交网络及出行者作出以下假设１２Ｊ：１）不考虑高峰期、道路交通堵塞等外界因素对乘车耗时的影响．２）假设出行者熟悉公交站点及附近地理位收稿日期：２００８一０３一ｌＯ豫＝｛腿Ｉ职＝＜日ｏ，ｐｆｌ，ｄｆｌ，ｐｉ２，…，口ｉ．ｄ—ｔ，ｐ耐，口ｄ＞｝，其中，｛口ｏ，以……，口Ⅻ一１，以ｄ｝为站点集合，｛ｐ”ｐｆ２’…，见＇ｄ＿ｌ，玖｝为公交车次的集合，豫。作者简介：雷一鸣（１９７２．），男，湖南临武人。助教，硕七，主要从事数学模型及经济信息管理研究　第１７卷雷一鸣：公交最优路径选择的数学模型及算法５ｌ表示在起始站点‰通过乘坐公交到达终点站％的可行的一条路线表示线路Ｓ（．，）．１．２模型描述设线路豫；的换乘次数为ＪＶｉ，出行费用为Ｘ，，路上总耗时为Ｚ，则该线路途经总站数为ｄ，不包括起始站点．出行费用、路上总耗时与途径站点正相关．在日常生活中，公交乘客的个人偏好往往是要求换乘次数少、出行费用低、出行耗时短，但在实践中这３个要素往往很难同时满足，所以选择效用函数ｕ（．）作为目标函数为：ｍａ）【Ｕ（Ｍ，ｘｒ，Ｚ），目标函数具有以下性质：器如，等如，筹锄，Ｉ筹ｆ））｝等｝．在上式，设相邻公汽站点间的平均行驶时间（包括停站时间）为＾，公汽换乘公汽平均耗时为ｆ，．总行程时间瓦与换乘次数Ⅳｉ的函数关系为：Ｚ＝西，＋Ⅳ；ｆ，．设第一次换乘前的价格为Ｘ。，第ｉ次换乘后到第ｉ＋１次换乘前这段线路的价格为ＸⅣ，则有ｘｆ＝ｘ。＋∑ｘ竹．１．３最优路径算法根据公交路线的现实情况，一般乘客转乘次数不会超过３次【３１，如图１所示．假设起始站点为Ａ，终点站点为曰．从Ａ、Ｂ两点出发，寻找出分别经过该两点的所有的线路，再进行比较分析，看是否能找出直接到达的路线，有则停止搜索，没有则选择两点中经过该路线中较少的站点的所有下一个站点，再进行线路搜索，再跟没有选中站点的线路进行比较，选择最优的站点．没有相同的线路则再进行同样的搜索，直到同样的路线出现才停止搜索．最后比较所有可行的结果，从中选择最优的方案．（＾）Ｉ选的情况‘Ｄ）换秉一次的情况一ｉ／｜｜—舢洛孑Ｖ，＼／／＾×棚图ｌ公交线路换乘方案示意图　公交路线选择的最优方案的算法步骤，如下所示：ｓｔｅｐ１：输入乘车起始站点Ａ和终止站点曰；ｓｔｅｐ２：分别求经过站点Ａ和Ｂ的所有车次组成的集合Ｌ（，）和ｓ（，）；Ｓｔｅｐ３：判断Ｌ（Ｊ）ｒ、Ｓ（，）≠妒是否成立？若成立，则Ｌ（，）ｎＳ（，）中的元素即为直达车次，即乘坐该车次可由起始站点Ａ直达终点站点Ｂ，输出Ｌ（，）ｎＳ（．，）的结果，计算Ｌ（，）广、Ｓ（，）中各直达车次经过的站点数，站点数最少的车次即为最优选择，终止算法．若不成立，则执行下一步．Ｓｔｅｐ４：判断两条公交线路是否有相同站点，即Ｅ（，，Ｕ）＝，（．，，ｙ）或存在紧邻站点，即满足ｄ（Ｅ，Ｆ）≤Ｍ．如果满足Ｅ（，，Ｕ）＝，（．，，ｙ），则线路Ｌ（，）、Ｓ（．，）即为转乘一次的线路，Ｅ（，，（，）即为转乘站点；如果Ｅ（，，Ｕ）≠Ｆ（．，，ｙ），但满足ｄ（互，Ｆ）≤Ｍ，说明乘客可以步行到邻近的站点转乘一次车到达目的地．乘客可从站点Ｅ（，，Ｕ）下车，然后步行到邻近的站点Ｆ（，，ｙ）换乘下一条线路的车，否则转入下一步．ｓｔｅｐ５：设Ｃ（Ｌ（ｚ））表示经过站点ｘ线路的条数．比较Ｃ（ＪＬ（Ａ））与Ｃ（Ｓ（Ｂ））的大小，即Ｌ（Ａ）与ｓ（Ｂ）集合中元素个数的多少．若Ｃ（Ｌ（Ａ））≤Ｃ（Ｓ（Ｂ）），则查找经过站点Ａ的车次中的下一站点ｚ。，这些所有站点Ｚ。．构成一个集合，记为Ｇ（ｚ＾＋。），查找经过Ｇ（Ｚ＾＋。）中的元素（比如站点Ｚ。）的所有车次，组成一个集合Ｌ（Ｚ＾＋。），分别判断集合Ｌ（ＺＡ＋。）中的元素是否与Ｆ（．，，ｙ）有交集．若有交集，则Ｆ（，，ｙ）为第二中转站点，即乘客在站点ｚ。转乘一次，然后在站点Ｆ（．，，ｙ）第二次转乘即可到达终点站Ｂ．若没有交集，再看下一个站点．若Ｃ（Ｌ（Ａ））≥Ｃ（Ｓ（Ｂ）），则查找经过站点Ｂ车次的前一个站Ｚ。．，所有这些站点构成一个集合，记为Ｇ（ｚ乩），查找经过Ｇ（ｚ乩）中的元素（比如站点Ｚ。）的所有车次，组成一个集合Ｓ（ｚ趴），分别判断集合ｓ（ｚ。）中的元素是否与￡（，，∥）有交集．若有交集，则Ｅ（，，Ｕ）为第二中转站点，即乘客在站点Ｅ（，，Ｕ）转乘一次，然后在站点ｚ趴第二次转乘即可到达终点站召．若没有交集，则转入下一步．５２湖南城市学院学报（自然科学版）ｓｔｅｐ２００８年第２期６：判断ｘ（Ｋ）厂、ｌ，（Ｄ）≠≯是否成立？若不妨设交集中的站点为过起始点的某条公汽线路上的站点属于这个集成立，合，说明乘客可以在该地铁站转乘地铁．如果地铁站旁的某公汽站点属于经过目的地的某条公汽线，说明乘客可以在该地铁站点出站转乘公汽到达目的地．其算法基本与不存在地铁的情形一样．当然，如果进一步考虑乘客在路途行走时间、公汽上所耗时间、地铁上所耗时间以及最后转乘公汽所耗时间等４部分的时间，可以考虑在上述模型的目标函数中加入时间变量，在约束条件中加入一个时间的限制条件，其算法依然满足这种情形．另外，由于在上下班的高峰期，车流量比较多，可以根据实际的情况给出一个关于时间的Ｚｆ（Ｘ，ｌ，）（ｆ＝ｌ，２，…），则找到了转乘３次的线路，如图１中所示．若不成立，把ｚ．作为起始站点，Ｚ毋一。作为终止站点，转入ｓｔｅｐ５继续类推搜索．１．４算法中的程序算法中用Ｍａｔｌａｂ求交集的程序‘４１如下：％求集合Ａ与Ｂ的交集Ａ＝【】：％输入Ａ的元素Ｂ＝【】；％输入Ｂ的元素Ｃ＝ｚＰｒＤＪ（ｍａｘ（ｓｆｚＰ（Ａ），ＪｉｚＰ（Ｂ）））；，ｌｌ＝ｓｆｚＰ（Ａ）；，ｚ＝玛（２）；铂＝Ｊｆｚ已（８）；Ｊ，ｌ＝铂（２）；ｆｏｒｉ＝２：ｎ分段函数加入到约束条件中，这样，可使模型更加接近实际情况．３ｆｂｒｊ＝１：ｍｉｆＡ（ｉ）＝＝Ｂ（ｊ）Ｃ＝【Ｃ（１：ｉ—１），Ｂ（ｊ）】ｅｎｄｅｎｄｅｎｄ结束语本文深入分析了一般公交网络系统的特点，建立了以换乘次数最小为第一目标，途径站数最２模型的拓广上述模型可以推广到以下情况：在城市交通网络系统中，同时有公共汽车和地铁．为了节约出行时间，乘客不是立即搭乘公共汽车，而是选择步行到临近的一个或两个站点在选择交通工少为第二目标的最优公交出行路径模型．对这一组合优化模型，设计了双向优先搜索算法．当然，公交出行的实际情况要复杂的多，本文对这一问题进行了相当程度的简化，从提供最优出行计划的角度进行了初步研究．目前还有许多问题，如环行线路、换乘的难易、时间的因素、非线性费用结构以及个人偏好等因素，都需要进一步研究．参考文献：【１】陈宝林．最优化理论与算法【Ｍ】．北京：清华大学出版社，２００５．具．由于地铁可以给乘客带来舒适、便捷，人们也会选择转乘地铁，而放弃路途遥远的直达公汽．当然考虑到地铁转乘公汽以及公汽转乘地铁所耗时间较长，在没有地铁直达或是距离地铁遥远的站点，乘客只有选择公汽，甚至不得不需要转乘几次．在考虑存在地铁的情况下，可以把地铁线路作为一条特殊的公汽线路．地铁线上有许多站点，地铁出口及其附近的所有公交站点可构成一个集【２接；启源．数学模型【Ｍ】．第３版．北京：高等教育出版社，２００３．【３】ＪｏｈｎｓｏｎｂａｕｇｈＲ．离散数学【Ｍ】．石纯一，译．北京：人民邮电出版社，２００３．【４】王正东．数学软件与数学实验【Ｍ】．北京：科学出版社，２００４．合，本文把该集合作为一个站点来看待．如果经ＯｐｔｉｍｕｍＲｏｕｔｅＭｏｄｅａｎｄＩｔｓＡｌｇｏｒｉｔｈｍｔｏＰｕｂｌｉｃ１ＹａｍｃＮｅｔｗｏｒｋ上ＩⅣＭ—ｍｉ愕（ＨｕａｌｉＣｏｌｌｅｇｅ，ＧｕａｎｇｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｇｕａｌｌｇｚｈｏｕ５１１３２５，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＴｈｅｋｅｙｐｏｎｉｏｎｉｎｍｅｔｒａＶｅｌｑｕｅｒｙｓｙｓｔｅｍｆｏｒｐｕｂＩｉｃ仃ａｎｓｐｏｒｔａｔｉＯｎｉｓｔｔｌｅｐｒｏｂＩｅｍｏｆｓｅｅｋｉｎｇｏｐｔｉｍｕｍ仃ａＶｅｌｒｏｕｔｅｂａｓｅｄｏｎｔｗｏｔｒａｎｓｐｏｎａｔｉｏｎｐｏｒｔｓｐｍＶｉｄｅｄ．ＡｍａｔｈｅｍａｔｉｃｍｏｄｅｌｏｆｏｐｔｉｍｕｍｒｏｕｔｅｗｉｔｈｒＩｌｉｎｉｍａｌ仃ａｎｓｆｅｒｔｉｍｅｓａｓｐｒｉｍａｒｙｇｏａｌａｎｄｔｈｅｍｉｎｉｍａｌｓｔｏｐｓａｓｍｅｓｅｃｏｎｄｇｏａｌｗａｓｂｕｉｌｔｉｎｍｅｐ印ｅｒ．ＡｎｄａＩｌａｌｇｏｒｉｍｍｗａｓｄｅｓｉｇｎｅｄｔｏｆｉｎｄｔｈｅｌｉｎｅｓｓｅ五ａ１ｏｆｔｈｅｏｐｔｉｍｕｍｒｏｕｔｅ．ＴｈｅＣｒａｎｓｆｅｒｒｉｎｇｗａｓｄｅｔｅｍｌｉｎｅｄｔｌｌｅａｆｌａｌｙｓｉｓｏｆｓｏｍｅｃｌａｓｓｏｆｉｎｔｅｒｃｏｎｎｅｃｔｉＶｉｔｙｏｆｌｉｎｅ．ＴｈｅｏｐｔｉｍｕｍｒｏｕｔｅｗａｓｃｏｍｐｒｉｓｅｄｏｆｌｉｎｅｓｓｅｒｉａｌａｎｄｔＩ．ａｎｓｆ色ｒｓ．ｂａｓｅｄｏｎＫｅｙｗＯｒｄｓ：Ｏｐｔｉｍｕｍｒｏｕｔｅ；ｔｒａｎｓｆｅｒｔｉｍｅ；ｐｕｂｌｉｃ仃ａｆｆｉｃｎｅｔｗｏｒｋ（责任编校：曾伟）　公交最优路径选择的数学模型及算法

作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：

雷一鸣， LEI Yi-ming

广东工业大学,华立学院,广州,511325

湖南城市学院学报（自然科学版）

JOURNAL OF HUNAN CITY UNIVERSITY(NATURAL SCIENCE)2008，17(2)0次

1.陈宝林 最优化理论与算法 20052.姜启源 数学模型 2003

3.Johnsonbaugh R.石纯一 离散数学 20034.王正东 数学软件与数学实验 2004

1.期刊论文 王建林.WANG Jian-lin 基于换乘次数最少的城市公交网络最优路径算法 -经济地理2005,25(5)

依据对公交乘客出行心理调查的统计结果,指出换乘次数最少是乘客出行时考虑的首要因素.描述了传统的Dijkstra算法,并分析了Dijkstra算法不适合公交网络最优路径选择的原因.最后根据公交乘客可以步行小段距离再转车的实际情况,提出一种基于换乘次数最少的公交最短路径改进算法.

2.学位论文 汪江洪 公交换乘系统研究及其评价 2006

自从17世纪城市公共交通出现以来，它已经成为整个城市交通系统中最重要的组成部分之一，它的发展水平是衡量国家现代化程度的重要标志，同时也体现着国家的综合经济实力、城市经济的发展和城市居民生活的水平。而换乘系统是城市客运交通系统的重要的一个子系统，是公共交通优先的保证，也是城市客运交通整体化的关键，它对城市结构的完善、土地使用的合理化有着重要的意义。

本文首先对国内外城市交通换乘系统的研究和实践进行了总结，在此基础上分析了城市交通换乘的内涵、换乘系统高效运行的实现条件和影响因素以及换乘枢纽的分类。由于公交换乘枢纽非常复杂，协调管理非常重要。本文从规划、运行、环境3方面讨论了公交换乘枢纽从协调管理的角度所考虑的多方面因素。

可达性是城市公共交通系统是否高质、高效完成运输任务的一项重要指标，而平均换乘次数(ATT)可以对它进行评价。如果在乘客的步行距离范围内，他们可能步行以减少换乘公交的次数，本文据此提出了一种计算平均换乘次数的新的算法，并且给出了一个实例验证该算法的有效性。

根据有关文献提出的考虑公交换乘的公交系统最短路径算法，提出了一种基于网络变换的公交系统最短路径算法。公交网络经过网络变换，有换乘的网络问题被变换为没有换乘的网络问题。与原有算法相比，该算法避免计算直达矩阵(T矩阵)与最小换乘矩阵(Q矩阵)，并且经过一次变换之后，能够以Dijkstra算法直接计算一个起始点到其余所有站点的最短路径。

公交乘客出行路径选择模型是公交乘客信息系统的关键技术。考虑乘客在步行距离范围内步行以减少换乘公交的次数的实际情况，提出了以换乘次数最少为首要目标、出行距离最短为第二目标的基于前N条最短路径的公交乘客出行路径选择算法。

为了评价城市公交换乘枢纽的布局优劣、运营状况、服务水平，进而优化规划方案，遵循5个评价原则，建立了综合评价体系，提出了5项评价指标。结合工程实际，以定量与定性相结合的方法给出了指标的定义、计算方法和指标分级值。权系数的确定问题是狄色聚类方法中的关键和难点，提出了一种基于粗糙集理论的权系数确定方法。将权系数确定问题转化为粗糙集中属性重要性评价问题，建立关于灰色聚类方法的关系数据模型，计算出灰色聚类分析模型的权系数，这种方法使得灰色聚类方法更具客观性。本文将该方法应用于公交换乘枢纽评价，通过案例说明了所提方法的可行性。

本文研究了评价城市公交换乘系统的主要因素和评价指标，在分析了主观赋权法和客观赋权法的基本原理的基础上，提出了一种基于多目标规划的主客观评价一致的组合评价方法，并通过实例说明这种方法的合理性。

3.期刊论文 郑朝晖.Zheng Zhaohui 公交网络中最优路径算法的探索 -太原师范学院学报（自然科学版）2008,7(2)

通过对公交乘客出行心理调查的统计结果,可以了解换乘次数最少是乘客考虑的首要优先目标,其次是出行耗时最少和出行距离最短.文章则将出行耗时最少和出行距离最短合并简化为第二目标,最后根据公交乘客可以步行小段距离再转车的实际情况,提出既实用又简便的公交最优路径的算法.

4.期刊论文 孙浩博 一种公交线路优选模型及实现 -金卡工程2010,14(6)

根据乘客的各种不同需求,建立了以换乘次数最少和途经站数最少为首要目标,出行耗时、出行费用为次要目标的优化模型.借鉴深度优先搜索算法搜索出满足目标的线路选择方案.

5.期刊论文 侯刚.周宽久.HOU Gang.ZHOU Kuan-jiu 基于换乘次数最少的公交网络最优路径模型研究 -计算机技术与发展2008,18(1)

结合乘客出行心理分析,提出以换乘次数最少为目标的公交乘车模型.在公交网络建模方面,综合考虑公交站点空间关系,提出空间数据到拓扑模型再到搜索模型的公交网络双层建模方案.通过搜索模型的建立,将最小换乘次数问题转化为两点间的最短路径问题进行求解.在搜索算法的设计上,首先提出改造的边权为1的Dijktra算法,以此为基础设计前驱节点算法.并以前驱节点算法为前提,设计所有最短路径算法,能够高效地求解两点间的所有换乘次数最小的乘车方案.最后,以大连市公交数据为例,验证了建模方案和算法的可行性.

6.期刊论文 朱江云.王玉琨 基于最小换乘次数的最优路径算法 -福建电脑2007,\"\"(3)

分析公交网络的特点,说明公交网络中最短路径的意义.根据乘客出行时考虑的首要因素是还乘次数最少的事实,考虑了乘客可以步行小段距离再转车的实际情况,提出了基于最小换乘次数的城市公交网络最优路径算法.

7.学位论文 陈丽佳 基于公交网络模型的最优路径算法研究与实现 2009

城市公共交通是整个城市交通系统中的一个重要组成部分，它的发展水平是衡量城市现代化程度的重要标志，同时也是解决大中城市交通拥挤问题的最佳途径。而基于公交网络模型的最优路径选择是城市公共交通中的一个重要子系统，是公共交通优先的保证，它对城市结构的完善、土地使用的合理化有着重要的意义。

本文首先对国内外城市基于公交网络模型的最优路径算法的研究和实践进行了总结，在此基础上分析了城市公交系统高效运行的实现条件和影响因

素。接着介绍公交网络的图的存储表示，并在分析公交网络模型的基础上将其抽象成具有拓扑性质的网络图。然后提出了用“平均换乘次数”来对公交网络的可达性进行评价，并给出了基于N次换乘矩阵和基于A*算法的平均换乘次数计算方法。如果在乘客的步行距离范围内，他们可能步行以减少公交换乘的次数，本文据此给出了一种考虑步行换乘的平均换乘次数计算方法，并且通过一个实例分析验证了该算法的有效性。

对于公交网络最优路径选择问题，本文给出了两种算法：一种是基于网络变换的最短路径算法，公交网络经过网络变换，有换乘的网络问题变换为没有换乘的网络问题，避免了计算直达矩阵与最小换乘矩阵；一种是基于前N条最短路径的以换乘次数最小为第一目标、出行距离最短为第二目标的路径选择模型，并考虑乘客在步行距离范围内步行以减少公交换乘次数的实际情况，给出了一个考虑步行换乘的双目标公交路径选择算法。

本文以长沙派诺电子科技有限公司提供的长春市城市空间数据为基础，完成了长春市公交信息查询系统的设计与开发。系统的主要功能公交网络最优路径查询，用户通过键盘输入起终点或图上点击选择起终点，然后系统就可以列出所有的以换乘次数最少为第一目标、出行路径最短为第二目标的出行方案。另外，系统还有信息查询功能即公交站点查询、公交线路查询、地名查询及公共场所查询等，并可进行精确查询和模糊查询。 最后，对本文进行了总结，并对进一步的研究提出了一些建议和展望。

8.期刊论文 赵巧霞.马志强.张发 以最小换乘次数和站数为目标的公交出行算法 -计算机应用2004,24(12)

提供两点乘车的最优公交路径是ATIS的核心功能.文中建立了以最小换乘次数为第一目标,最小途经站数为第二目标的公交出行最优路径模型.提出了可行路径的最小换乘次数动态规划算法,依此确定换乘次数上界;设计了搜索算法确定最优公交线路序列,分析了线路相交的四种情况,给出了换乘点选择方法,由公交线路序列和换乘点共同组成最优路径.

9.学位论文 王磊 基于WEBGIS的公交信息系统最优路径算法研究 2007

在我国众多大城市普遍存在交通拥挤问题，造成交通拥挤的首要原因是城市交通基础设施的建设远远落后于城市交通需求的增长。大力发展公共交通是解决城市交通拥挤问题的首选措施。然而，通过对我国目前公共交通系统的分析，可以看出我国公共交通系统存在的一个普遍问题，就是乘客出行换乘比率高。另外，我们对公交乘客的出行心理也进行了调查分析，结果显示，乘客在选择出行路径时首先考虑的是换乘次数最少，其次是考虑时间最短。

针对目前这种形式，本文通过对于道路交通网络两点间最短路径的搜索算法进行研究，发现目前的很多种成熟算法在公交换乘网络的应用上都存在一定问题：Dijkstra算法是传统最短路径算法中最为常用的经典算法，但该算法的执行效率明显不足，它求解最短路径问题是基于网络的权矩阵，运用了关联矩阵、邻接矩阵和距离矩阵的概念，在存储图形数据和运算时需要定义n×n阶矩阵，其中n为网络的结点数。当网络的结点数较多时，其庞大的网络数据存储需求及算法的空间时间复杂度将占用大量的计算机内存，执行效率较低。目前还有许多基于Dijkstra算法的改进算法如：基于点——边拓扑关系的算法、优先搜索算法和采用动态数据串等方法。以上这些算法的研究目的都是为了提高运算的效率，但一般都还不能直接运用于公交网络的路径选择中，因为公交乘客在出行的过程中不仅要考虑出行距离，还要考虑换乘次数这一重要因素。

而近年来逐渐兴起的很多智能算法比如遗传算法、蚂蚁算法、神经网络等算法也开始应用于公交换乘的算法研究中，并在基于海量网络图中的最优路径问题求解中取得了较好的效果，但这些智能算法首先本质上还是一种随机搜索算法，有其自身不可避免的局限性，不可能达到全部网络路径的遍历求解，往往因为参数选取不当和公交网络图的表达问题造成得到的结果实际并不是最优解；其次，其算法的高效率主要体现在应用于超大海量网络图上，但实际应用中的城市交通网尤其是中小城市交通网络还远没有达到那样的复杂度，所以其实际运行效率不能得到很好的体现。

本文在分析和总结归纳以上算法的优缺点的同时，通过对公交网络的分析与研究，针对公交网络的特点，首先进行公交网络的抽象，建立换乘矩阵和权值矩阵，然后给出相应的算法实现，即根据公交车站路线表，依据该换乘矩阵和权值矩阵对应的值就可以计算出任意两站之间的最少换乘次数和出行方案。提出了以换乘次数最少为第一目标、经过的站数最少和时间最短为第二目标的城市公交查询系统的设计与实现方案。全文共分七章，第一章为绪论，为全文搭建一定的理论基础平台，并对论文的结构作整体的概述；第七章为结语，归纳全文主要结论和有待进一步研究的问题。

第二章、第三章，从现实中我国公共交通状况出发，分析我国公共交通系统的弊端，并对国外的智能交通系统的产生与发展进行详细背景研究。着重介绍了现阶段公交换乘系统的研究现状，并从问题类型、网络特征以及实现技术等几个方面对最优路径算法进行分类讨论；最后对经典的dijkstra算法和流行的智能算法如遗传算法、神经网络、蚂蚁算法等最新的公交换乘算法研究进展做了详细论述。第四章、第五章，论文的重点部分。利用

Dijkstra基本思想和基于邻接矩阵的改进算法进一步对其优化、改进，直接将公交换乘矩阵中的换乘次数改为换乘方案字符串，同时对时间最短作为权值分析，将路程花费用公式转化合并入权值，并建立基于时间最短的网络矩阵序列，这样，将大部分换乘查询放在矩阵的生成阶段，在用户查询时只需要对换成矩阵和权值矩阵进行简单的取值、分解、计算即可得到最优路径的解。大大减少了用户查询时的反应时间。

第六章，结合克拉玛依电子地图实例，在WEBGIS环境下利用典型的客户机、地图应用服务器与Web服务器、数据库服务器的三层结构，实现了克拉玛依市的公交换乘模块并验证了其算法的高效和实用性。

10.学位论文 廖楚江 基于STL的公交网络最优路径查询组件的设计与实现 2004

公交网络最优路径查询一直是城市电子地图的研究热点,它也几乎成了电子地图产品的一个必备功能,然而时下,众多电子地图产品都将最优寄望于最短上,不可否认,这在某些情况下是合理的,在一定程度上也满足了人们的需求.然而,在使用的过程中,人们也逐渐发现,求取得到的最短路径常常是以增加换乘次数为代价的,这显然有悖于人们的乘车习惯,事实上人们日常更倾向于选择的是最少换乘次数的乘车方案,即使它有时相对来说距离较远,因此,如何实现基于最少换乘的最优路径查询是当前电子地图产品必须要解决的一个问题.本文创造性地提出了基于最少换乘次数的最优路径查询,并将其与传统的基于最短路径的最优路径查询结合起来,使得最优路径查询更贴近于日常生活中人们的乘车习惯,在具体实现的过程中,笔者将两种方案都采用组件来加以实现,提高了算法的可移植性和可重用性,同时,笔者在算法中注入了STL的优越性能,不仅简化了代码,便于维护,而且使得算法的执行效率得到了极大的改进,最后,笔者在单机版的系统和网络系统中都实现了对该组件的调用,尤其是在网路环境中的调用方法,在WebGIS的实现上将不失为一条好的途径.

本文链接：http://d.g.wanfangdata.com.cn/Periodical_huncjgdzkxxxb200802015.aspx

授权使用：洛阳工学院（河南科技大学）(wflskd)，授权号：24635afe-4e93-4a72-b09b-9dd800b04689

下载时间：2010年8月20日