基于代价值模型的公交换乘算法研究张晓欢，王勤，刘文龙，赵文深**（北京邮电大学电子工程学院，北京市100876）5101520摘要：公交换乘算法没有统一的标准，各种算法考虑条件都不相同，存在各种各样的问题。本文从用户结果体验及高并发量查询出发，提出了基于代价值模型的公交换乘算法。通过建立统一的模型，将现实生活中换乘需要考虑的因素都统一到模型中，得到较合理的结果。将生成的合理的方案保存在数据库中，建立合适的索引，可以快速的查询出换乘结果，支持比较大的并发查询。关键词：公交换乘；代价值模型；高并发中图分类号：TP312BustransferalgorithmbasedonvaluemodelZHANGXiaohuan,WANGQin,LIUWenLong,ZHAOWenshen(SchoolofElectronicEngineering,BeijingUniversityofPostsandTelecommunications,Beijing100876)Abstract:Bustransferalgorithmhasnounifiedstandard,anddifferentalgorithmhasdifferentconsideration.Inthispaper,theauthorproposeaalgorithmbaseonvaluemodel,focusontheuserexperienceandhighconcurrencyquery.Withconsideringthecommonfactorsinthevaluemodel,morereasonableresultscanbeobtained.Theexchangeresultsisstoredindatabasewithappropriateindexesbuilt,sousercanquerytheresultsquitequicklyandhighconcurrentquerycanbesupportedwell.Keywords:bustransfer;valuemodel;highconcurrency250引言随着信息技术及交通行业的发展，人们对于出行的要求越来越高。在乘坐公共交通工具时，人们希望能快速查询到最优的方案，公司希望能用最少的成本为用户提供最好的换乘方案。现在有各种各样的公交换乘算法，主要有基于最短路径和邻接矩阵的算法[1]，其中基于3035最短路径的算法比较常用，对最短路径的求解方法很多,主要有两类:一类如Dikstra算法、Moore-pape算等[2]。第二类是基于遗传算法的较为智能的搜索算法。基于最短路径的算法将焦点聚焦于路程，步行距离，对于换乘次数，车的停站时间等影响用户体验的因素未考虑进来[3]。常用算法实现中，主要采用动态搜索换乘方案的方法，随着换乘次数的增加，计算量呈指数形式增长[4]，还且存在重复计算的问题，如果有多个用户搜索同样的换乘，会产生重复计算的问题，一定性能的服务器不能提高较大的并发访问量。针对这两点需求，本文提出了一种新的思路，基于代价值的换乘模型，将换乘中需要考虑的因素统一换算成代价值，不仅仅考虑唯一的换乘次数，出行距离或者时间等单一因素[5]。最后基于代价值进行方案的比较，排序。将最优的结果返回给用户。同时系统采用生成方案数据库的方式，将所有生成的换乘方案都保存到数据库里[6]，建立合适的索引，可以快速的查询出方案。40作者简介：张晓欢（1989-），男，研究生，无线通信与物联网通信联系人：赵文深(1954-)，男，高级工程师，电子电路测试技术.zhaows@bupt.edu.cn-1-ZDij1基于代价值的换乘模型1.11.1.1最优模型设计公交术语描述大城市的公交系统错综复杂，但是确可以用一套简单的数学模型来表示，比如图论中455055的点、有方向的边、区域面等等。首先，我们定义以下术语：线路（APTS_ROUTE）：线路就是每一路公交车在上下行的不同方向经过的一条直线，每条线路会包含一系列唯一的顺序排列的站点，每一条线路在计算机中以一条链表来存储。站点（APTS_BUSSTOP）：站点是每条公交线路中的某一个车站，一个站点只属于一条线路，且该站点在线路中是有序的。站台（APTS_STATION）：站台是指在一定区域范围内的站点的集合，这些站点可以有相同的名字也可以有不同的名字，换乘方案中起始站，终点站和中转站都是对站台而言的。步行区域（APTS_WALK）：步行区域是指以可以步行的距离作为阈值的一个区域的所有站点的集合，在区域中的站点都是步行可达的。在换乘方案中，当需要到马路对面换乘时需要考虑步行距离，距离超过阈值视为不能换乘。搜索热点：即算法搜索站点和路线的总区域，如果不进行搜索区域划分的话默认搜索热点是整个城市。为了减小搜索数据量的负担，可以人为的按照某个策略定义一个小范围的搜索热点，在这个热点内保证换乘方...