一种基于加权复杂网络的最优公交换乘算法.pdfVIP

第 32卷 第 6期 武汉理工大学学报(鸯霾差) Vo1．32 N0．6 20o8年 12月 JournalofWuhanUniversityofTechnology Dec．2O08 (Transp0rtati0nScience＆Engineering) 一 种基于加权复杂网络的最优公交换乘算法* 王 波 王万 良 杨旭华 (浙江工业大学信息工程学院 杭州 31O032) 摘要 ：用spaceP方法对公共汽车交通网络 (公交网络)进行建模，得到一个无权的复杂网络模型， 并简单分析了其统计特性．利用广度优先有哪些信誉好的足球投注网站算法得到需换乘两公交站点间的所有最少次数换乘 方案．在此基础上，引入了网络点权，即站点的经纬度，进而得到网络的边权，即站点间的直线距 离，把公交网络进一步建模成一个加权的复杂网络模型．结合得到的最少换乘次数方案，最终得到 一 种在保证换乘次数最少的基础上站间总直线距离也最短的换乘方案，并用杭州的实际数据验证 了此算法 的有效性． 关键词：公交网络；小世界网络；加权复杂网络；换乘；广度优先有哪些信誉好的足球投注网站 中图法分类号 ：U491_1；N94；TP274 O 引 言 引入了网络的点权 ，即各站点的经纬度 ，进一步得 到了网络 的边权，即站点间的直线距离 ，把公交网 近年来 ，公共汽车交通网络 (公交 网络)的研 络建模成一个加权的复杂网络；并结合利用广度 究工作 已经成为一个新兴 的热点，许多学者对此 优先有哪些信誉好的足球投注网站算法得到的站点间所有最少次数换乘方 进行 了大量深入广泛 的研究[1≈]．研究表明：公交 案 ，最终可 以得到一种在保证换乘次数最少 的基 网络是一个典型的具有小世界特性L3的复杂 网 础上站问总直线距离也最短的换乘方案． 络．公交汽车是中国城市交通的主要载体，是城市 居民出行的主要交通工具．因此，公交换乘就是人 公交网络的统计特性 们乘坐公交所关心的最主要问题之一．公交换乘 问题在复杂 网络 中表现为 网络 的有哪些信誉好的足球投注网站 问题 ． 从网络上得到了北京、上海 、杭州的公交网络 Kleinberg首先在理论上研究了复杂网络的有哪些信誉好的足球投注网站 的实际数据，用spaceP方法对其进行建模 ，并利 能力，证明了小世界网络的可快速有哪些信誉好的足球投注网站性L4]，随后 用邻接矩阵来表示此无权复杂网络．通过对各公 watts等人又对这一 问题作 了进一步的研究．因 交网络邻接矩阵的分析，得到如下数据，见表 1． 此，公交网络作为一个典型的复杂网络，也具有可 表 1 公交网络统计特性 快速有哪些信誉好的足球投注网站性，即站点间的换乘 问题是可 以快速搜 索解决的． 依据对公交乘客 出行心理调查的统计结果 ， 换乘次数最少是乘客 出行时考虑 的首要因素 ，其 次是行驶距离 、时间、费用等．目前 的一些研究结 果主要是利用 网络节点最短路径算法 ，找到2个 从表 1中看到，公交 网络具有小 的平均最短 站点间的最短路径，即只保证换乘次数最少，并没 距离和大的平均聚类系数，因此它是一个典型的 有考虑其他因素，提出一些换乘的方案Ls]．本文 小世界网络．进一步可以得到公交网络的平均最 收稿 日期 ：2008一O7—04 王 波：男，26岁，博士生，主要研究领域为复杂网格、智能交通 。国家 自然科学基金项 目资助 (批准号：605O4O27，6O573123)． ·1114 · 武汉理工大学学报 (交通科学与工程版)