公交车最佳乘车路径优化算法

《公交车最佳乘车路径优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第2期唐山师范学院学报2009年3月Vol.31No.2JournalofTangshanTeachersCollegeMar.2009计算机与自动化技术公交车最佳乘车路径优化算法王祥（北京交通大学计算机学院，北京100044）摘要：公交乘客出行路径选择是公交乘客信息系统的关键技术，而公交车最佳路径算法是路径选择的基础，目前公交车最佳路径的算法有很多种，算法的区别在于数据存储的结构，各个数据存储结构有各自的优点与不足，基于唐山市公交基础信息和实际生活中公交乘客出行的特点，设计了合乎乘客需求的最佳路径查询的

2、算法。提出以换乘次数最少为首要目标，在此基础上以出行距离最短为第二目标的算法。可将其用于公交公司的管理系统中，也可以用于公交公司查询服务系统中。关键词：公交查询；最佳路径；算法；数据结构；优化中图分类号：TP301.6文献标识码：A文章编号：1009-9115(2009)02-0079-04OptimizationAlgorithmofBestTravelPathWANGXiang(SchoolofComputer,BeijingJiaotongUniversity,Beijing100044,China)Abstr

3、act:Bustravelpathselectionisthekeytechnologyofpassengerinformationsystem,andtheoptimizationalgorithmofthebesttravelpathisthebasisforthecurrentpathselection.Therearemanyalgorithmsofthebesttravelpath,andsomeofthemaredifferentinthestructuresofdatastorage.Datastora

4、gestructuresallhavetheirownadvantagesanddisadvantages.BasedonthecharacteristicsofbasicTangshancitybusinformationandpassengerstravelinactuallife,analgorithmofthebestpathqueryisdesignedtosatisfytherequirementsofpassengers,andanalgorithmisproposed,takingtheleastch

5、angeasthefirsttarget,theshortesttraveldistanceasthesecondtarget.Keywords:businquiries;bestpath;algorithm;datastructure;optimization1引言车出行的乘客的心理行为进行调查研究，确定优化的目标和大部分城市提出了“优先发展城市公共交通”的交通政条件，通过对公交乘客的随机问卷调查得知公交乘客选择乘策，以缓解交通堵塞，能源紧张，废气污染等问题。为方便车路径的心理过程，主要受到以下因素的影响，换乘次数

6、，乘客出行，交通部门大力发展完善公交服务系统，改善乘车出行距离，出行时间和出行消费。如表1所示。环境的同时，也努力为乘客的出行提供及时、准确、最佳的表1出行影响因素比例表公交信息查询服务。从现有网站看出，公交路线查询信息服影响因素换乘次数出行距离出行时间出行消费务很全面，从A地到B地给出了多种路线，建议哪条路线所占比例45%30%20%5%是最佳路线并不多。最佳路径是指乘客在乘车从起点到终点其中换乘次数指的是乘客完成一次由起点到达终点的的多条路径中，能最好满足乘客期望的线路，即出行效用最出行过程中所换乘公交车的次数。

7、出行距离分为车外距离和大的线路。车上距离。车外距离指的是乘客为乘坐某路公交车而行走的2公交乘客出行最佳路径的定义距离，其中包括从起点到上车地点步行的距离，中途换乘其确定公交出行最佳路径，很重要的一点是通过对乘公交──────────收稿日期：2009-01-14作者简介：王祥（1965-），男，河北唐山人，北京交通大学硕士研究生，唐山师范学院高级工程师，研究方向为计算机网络安全及软件工程。-79-第31卷第2期唐山师范学院学报2009年3月它车走的距离以及下车后到终点行走的距离，车上距离指的以直达，不需要换乘。如图1

8、所示。是所乘公交车所走的距离。出行时间也同样包括车外时间和（2）起点pij与终点phk不在同一线路上，即ih，车上时间。车外时间指乘客的车外路程消耗的时间以及站台且存在pimpht（m=1,2,…n,t=0,1,2,…n），需要换车等车时间，车上时间指乘坐公交车所消耗的时间。出行消费一次。如图2所示。指乘公交车所消费的费用。乘客的目的就是在