公交线路选择（共9篇）
公交线路选择 篇1
2007年全国大学生数学建模竞赛甲组B题是“乘公交，看奥运”[1]。公汽线路选择问题是一个智能交通系统[2](Intelligent Transportation System)中先进出行信息服务系统(ATIS)的一个重要组成部分。两个站点之间的最佳线路选择问题实际上就是基于最短路径查询的公交乘车路线问题，首先求出从起始点到目标点的距离最优路径，获得构成这条最优路径的站点;将这些站点作为搜索的中转站点，根据这些站点及通过这些站点的公交线路，获得可行的换乘矩阵。对于复杂的公交网络来说，乘车方案的选择不仅依赖于用户的实际取向，所涉及的因素很多，与交通拥挤状况、公交车发车频率、换乘车行走距离、交通费用等有关，除此之外，还应考虑多因素对用户选择乘车方案的影响，明确寻优目标，判断各种条件下乘客的路径选择的原则，提出通用模型和算法，以满足用户各种形式的需求。
文献[2]提出了基于最少换乘的公交最优路径理论，在此基础上设计了公交最少换乘的算法，文献[3,3]提出了基于自组织理论的路线选择的模型，研究了存在实时交通信息条件下司机线选择行为的演化规律，讨论了模型参数，分析了模型的稳定性;文献[4,4]从节约存储空间、提高速度要出发，结合最短路径换乘算法给出了一种高效的换乘算法数据模型，并设计了基于站点优先级的公交换乘算法。除此之外还有经典的Dijkstra算法、Floyd算法、贪心算法、A*算法、爬山法等。上述算法在问题规模变得很大的时候，其效率就会呈指数降低。但更为重要的是这些算法都不能体现查询者的主观意向。本文针对这个问题，提出了一种基于带偏好自适应评价的公交线路选择算法，较好的体现了查询者对乘车时间和乘车价格两个因素的考虑。对公交线路的评判较强的依赖于查询者对这两个因素的主观接受程度。
1 问题分析
“乘公交，看奥运”题目中，给出了详细的公交线路及其站点情况，通过仿真计算和推理，我们得到关于这个问题中关于公汽站点和线路的一些基本信息如下：
公汽站点总数(Sation)：3957从S0001～S3957
总公汽线路数(Line)：520从L001～L520
最长公汽线路：L207长度为86;
最短公汽线路：L93,L234,L471共三条长度为7;
平均公汽线路长度：29
公汽线路类型：共有三种(上、下行线相同的公汽线路，上、下行不同的公汽线路，环形公汽线路)。其数目分别是:
上、下行线相同的公汽线路数：89;上、下行不同的公汽线路数：409;
环形公汽线路数：22;
公汽线路票价类型：单一票制、分段计价,其数目分别是：
单一票制的公汽线路数目：283;分段计价的公汽线路数目：237;
2 基于带偏好自适应评价的公交线路选择算法
2.1 算法思想
对于这个问题而言，建立的模型应该考虑三种情况：1)只考虑时间因素的模型;2)只考虑价格因素的模型;3)时间和价格都考虑得模型。对于前两种模型而言，只要分情况讨论换乘站数就可以很容易的得到，所以本文就不仔细阐述这几个模型了，感兴趣的读者可以自己来总结。第三种模型是在前两个模型的基础上进行的，并且要综合考虑时间Time和价格Price两个因素，通常的做法是首先通过归一化消除量纲，其次用加固定权组合得到最后的结果。其缺点在于：
1)查询者在不同情况下，对换乘次数和乘车站数的忍耐程度是不一样的。换句话说，用固定权值组合得到最后结果与实际情况不符;
2)查询者在不同情况下，对乘车时间和乘车价格的优先考虑程度是不一样的。换句话说，即使是同一个乘客，有的时候，他会优先考虑时间，有的时候，他会优先考虑价格。而前面的方法无法反映这个情况。
针对上述缺点，本文提出了一种基于带偏好自适应评价的公交线路选择算法，利用自适应调节的时间评判系数来解决第一个缺点，利用偏好系数来解决第二个缺点。
首先我们引入用户期望度ρ:
其中：0≤a,B≤1，α为时间偏好系数，β为价格偏好系数，ω1+ω2=1,0≤ω1，ω2≤1，ω1为时间评判系数，ω2为价格评判系数，ω1满足Logistic增长曲线：
其中：t为任意两个站点之间公交站数，k表示换乘次数，在我们这个实际问题中，k=0,1,2,a,b为函数参数。其函数曲线在a=0.2,b=0.3时的曲线如图1所示。可以看到这是一个S型函数。
模型中的时间评判系数ω1随着换乘系数k的增大而减小，而随着站数t的增大而增大的，在现实生活中换乘次数依据人的心里承受的能力数值是很小的，所以换乘次数一般控制在一到两次，这样站数的多少则客观的决定着时间评判系数ω1的大小。当站数t增幅不大时，时间评判系数ω1的增幅不大;当站数t增幅不大时，时间评判系数ω1的增幅急剧增大;当站数t增大到一定程度时，时间评判系数ω1的增幅又变缓。这种变化与人的心理感觉是一致的。当人乘坐公交时，在站数不是很多的情况下，在心理上会过多考虑的是价格较优;在站数变得越来越多的时候，此时价格的比重开始慢慢下降，人在心理上更多倾向于更多考虑时间，并且随着站数的增加，这种感觉就越强烈，时间被作为首先考虑的因素，其比重增长的很快;当站数很多时，尽管我们对时间仍然十分关注，但其增幅变得缓慢了。所以本文提出了自适应评价函数，函数中的时间评判系数ω1和价格评判系数ω2直观的给出了对这种现象的模拟，从而具有一定的合理性，采用这个函数来计算每条可行线路的用户期望度ρ比单纯考虑Time和Price具有很强的优势。在后面的仿真实验中，我们可以清晰的看到这一点。
模型中的时间偏好系数α和价格偏好系数β是为了描述在实际生活中，不同的查询者由于客观因素或者是一些主观情绪的影响，希望对时间或价格的决定程度进行一定程度的修改，模型中通过对定义一对偏好系数α，β的修正来完成这个事情。当查询者对时间的需求变得很强烈时，可以通过增大时间偏好系数α来改变时间的比重;当查询者对价格的需求变得很强烈时，可以通过增大价格偏好系数β来改变价格所占的比重;在查询者没有上述需求的时候，α，β的取值一般情况下为1。由此我们不难看到，这对参数能较好的满足查询者的一些特殊需求，具有较大的实际意义。
2.2 基于带偏好自适应评价的公交线路选择算法
算法思想：
换乘0次(同一线路)。start的换线行与end的换线行的交集，交集非空表示可以换乘0次，交集为空表示不能换乘0次。
换乘1次。start的m条过站线并集(各过站线上站点集合之并集)，与end的n条过站线并集的交集为换乘站集，因为此交集(若非空)的元素(站点)既在start的某一过站线上又在end的某一过站线上，交集即为换乘1次的换乘站集。
换乘2次。start的m条过站线上各站点(可能的换乘站)的换线行并集与end的n条过站线上各站点(可能的换乘站)的换线行并集的交集为换乘站集，因为此交集(若非空)的元素(线路)既通过start的某条过站线上某站点又通过end的某站线上某站点，相应的两站点是换乘两次的换乘站。
3 实验结果
本实验采用Matlab6.0编程，利用我们提出的算法，对该问题进行求解，得到如下结论：
1)在0次转乘的条件下，在题目中指定的六对起始站—>终到站中，没有一条可以直接到达;
2)在1次转乘的条件下，从S1557—>S0481,S0148—>S0485是不可达的，其余4对起始站—>终到站全部可达;
3)在2次转乘的条件下，六对起始站—>终到站全部可达;
4)六对起始站—>终到站的具体路线情况如下(限于篇幅，此处只给出一组，如表1)。
在所有可行换乘线路中，价格是相同的，所以价格在其中不起决定性作用。
在所有可行换乘线路中，经过的车站数不同，因此乘车用时差异较大，根据时间来评判，最优的换乘线路编号是：3,5;
根据用户期望度来评判，最优的换乘线路编号是：3,5;需要说明的是，此处的α,β均默认为1。
第3条换乘方案是从S3359乘坐L436公交，在L436的第51个站(S1784)下车，换乘L167,在第17个站下车，即到达终到站S1828。
最优换乘线路序列是：
第5条换乘方案与第3条不同之处在于中转后乘坐了不同的公交。此处不再详细说明。
摘要：在智能交通系统中公汽线路选择是一个重要的问题。该文首先利用公汽的行驶线路进行深度优先搜索,得到从开始站点到结束站点所有可能的乘车线路。然后分别考虑乘车时间Time和乘车价格Price来评价这些乘车线路优劣,最终得到题目要求的最佳线路。为了能够综合考虑Time和Price,通过引入用户期望度ρ,提出了一种带偏好的自适应评价函数来对基于Time和Price的评价方法进行进一步的改进,这个带偏好的自适应评价函数合理表达了查询者的主观意向、乘车线路差异,从而可以满足不同查询者的不同需求。最后通过仿真实验对该文方法进行了有效性验证。
关键词：智能交通系统,轨迹深度优先搜索,自适应评价函数,偏好系数,Logistic函数
参考文献
[1]http://www.mcm.edu.cn/mcm07/Problems2007c.asp.
[2]唐楚江,蔡忠亮,杜清运,等.基于最少换乘的公交最优路径算法的设计与实现[J].武汉大学学报:信息科学版,2006,31(10):904-907.
[3]贺国光,冯蔚东.路线选择行为的分支模型[J].土木工程学报,2003,36(1):21-25.
[4]徐兵,谢仕义.基于站点优先级的公交换乘算法实现[J].计算机时代,2005,7:16-17.
[3]孙勇.基于宽度优先遍历树的公交线路换乘算法[J].深圳职业技术学院学报,2004,4:10-12.
[4]周涛,张艳宁,袁和金,等.基于聚类分析和集成改进支持向量机的序列目标识别算法[J].计算机科学,2009,36(1):148-152.
[5]周涛,张艳宁,袁和金,等.基于聚类分析和集成神经网络的序列目标识别算法[J].计算机科学,2009,36(3):215-219.
[6]周涛,张艳宁,袁和金,等.粗糙核k-means聚类算法[J].系统仿真学报,2008,20(4):921-925.
[7]周涛.ACDB中ECA规则调度的一个新算法[J].计算机工程与应用,2007,43(16):175-179.
[8]周涛.基于线性相关思想的属性约简算法[J].广西师范大学学报,2007,25(4):44-47.
[9]周涛.ACDB中ECA规则调度的一个新算法[J].计算机工程与应用,2007,43(16):175-179.
公交线路选择 篇2
1路：火车站—中铁航空港
火车站—（水岸尚城）—中银公寓—行政中心—隆泰小区南—（农机公司）—城管局—市医院东—步行街东—明珠大厦—新华书店—荣盛小区—兽医院—（汽车站）—（包裹庄）—（许庄）—中铁航空港
2路：二矿—幸福佳苑
（二矿）—（西陶村）—（北岸村口）—东陶村—玫瑰庄园—金亨会馆—黎昌假日—体育中心—戏曲大观园—临津村东口—堤角村—南燕家务—大何庄—环保局—图书馆—水榭花都西—隆泰小区西—行政中心—温泉小区—公安局—（技术监督局）—市医院—步行街东口—兴华商业城北— 阿尔卡迪亚—（燃气公司）—联通小区—（幸福佳苑）
3路：维民房道口—看守所
（维民房道口）—（东关七街）—（东关老道口）—（东八道口）—（中国电信）—（东关五街）—（交通石化）—大洋模具城—兽医院—荣盛小区—新华书店—明珠大厦—步行街东口—市医院东门—城管局—（农机公司）—隆泰东门—（隆泰D区）—丽雅苑小区—（北杨庄）—（北杨庄新村道口）—（同和堂药店）—（万德福家具城）—（满义大饭店）—（大世界家具城）—（南沙道口）—（看守所）
4路：火车站—开发区医院
火车站—（水岸尚城）—中银公寓—温泉小区—李少春大剧院—骨伤科医院—（自来水公司）—步行街南口—步行街东口—市医院东口—城管局—（农机公司）—隆泰东门—（隆泰D区）—丽雅苑小区—（中国邮政）—图书馆—市政府西门—（开发区医院）
5路：田各庄—西苑小区
（田各庄）—（金各庄）—（检测站）—（农研所）—丽雅苑小区—（隆泰D区）—隆泰小区东—（农机公司）—城管局—市医院东—步行街东—步行街南—（自来水公司）—骨伤科医院—公安分局—（西苑小区）
6路：汽车站—二矿
汽车站—益津市场—骨伤科医院—（自来水公司）—步行街南口—步行街东口—市医院东门—城管局—（农机公司）—隆泰小区东门—（隆泰D区）—丽雅苑小区—（中国邮政）—图书馆—霸州一中—茗汤温泉—广电中心—金各庄—（罗卜营）—（圈子村）—（六必居）—（中石油气站）—（南孟村）—（北岸村口）—（西陶村）—（二矿）
公交线路选择 篇3
全国巾帼文明岗线路2路全国青年文明号驾驶员、福建省五四青年奖章获得者林晓蕾代表优质服务示范线路驾驶员表态发言;集美公交公司副总经理李勇全代表优质服务示范创建运营企业代表发言。启动仪式上, 龚建阳、张松、林荣生共同为十条优质服务示范创建线路授牌。龚建阳对创建工作提出了具体要求。
在全市开展公交服务质量提升专项行动中, 一项重要的举措就是开展公交优质服务示范线路的创建, 每家公交基层公司可以推荐1~2条的典型线路参与创建。
通过开展示范线路的创建, 树立标杆, 以点带面, 总结推广先进经验, 引领公交服务质量的全面提升。前一阶段, 公交集团发动各基层公司积极参与, 踊跃报名, 经过自下而上多次推荐, 多方酝酿和评选, 最终确定首批推出的10条公交优质服务示范创建线路。
公交优质服务示范创建线路主要特点:
高标准严要求。确定的十条线路以提升服务质量为出发点, 都提出了具体创建方案, 同时营造浓厚的创建氛围, 从运营服务、行车安全、车容车貌、投诉处理、线路管理、创建活动、班次执行率、乘客满意度等方面进行全方位提升, 着力打造比其它线路更高标准、更优质服务的精品线路。
各具特色。除了标准化服务提升以外, 这十条线路还各具特色。有全国级巾帼文明岗线路2路;有福建省级青年文明号线路、福州市首条无饮食车厢线路51路;有无饮食车厢推广得不错的18路;有集社区公交、纯电动公交、手绘公交、环五缘湾公交等特色为一体的439路;有着力打造“工人之家”主题车厢的854路;有高峰期断面客流量最大, 同时也是全程高架的公交线路BRT快3路;有全线均为CNG清洁能源型公交车的931路;有采用双语报站的节能环保型天然气公交线路929路;有贯通厦门城市中心的公交进出岛线路659路, 这条线路有7名驾驶员参加义务交警;还有推出翔安特色闽南语报站、手机摇一摇填写“服务卡”反馈乘车意见等多项便民服务举措的753路。其中, 有岛内线路, 有岛外区内线路, 也有跨区、跨岛线路。
梁山县公交线路 篇4
收车时间：夏季：19：:35冬季：19：20（全程票价一元）
南转盘←→水浒驾校←→孟家店←→平安驾校←→独山加油站←→杏花村宾馆←→马振杨路口←→现代汽修厂←→山水家园←→郝山头村←→县医院←→县医院北门←→梁山风景区←→三角花园←→长途汽车站←→社会客车站←→一中路口←→公安局←→第一实验小学←→医药公司←→百货大楼←→水泊花园小区←→解放桥←→石棉厂←→北区派出所←→一点厂家属院←→山景花苑小区←→关庄村←→外贸局←→国棉厂北家属院←→位山局汽修厂←→北环城路口←→前码头←→后码头村←→床单厂←→收费站（终点）
公交二路（县医院←→火车站）终点站9分钟
收车时间：夏季：19:20冬季：19：00（县医院——华清中学站点票价为一元，全程二元）
郝山头←→县医院←→医院北门←→梁山风景区←→三角花园←→长途汽车站←→社会客车站←→一中路口←→公安局←→第一实验小学←→医药公司←→百贷大楼←→保健站←→中医院←→吕屹口村←→水浒商贸城←→黄河局家属院←→冯屹口村←→西环城路口←→开发区管委会←→宏志中学←→水浒面粉厂←→公安局看守所←→金帝纺织厂←→华清中学←→孙庄村←→刘仙庄村←→大候村←→良福集团（李阁村）←→太平王村←→太平集村←→陈营村←→大华轮胎公司←→任庄村←→高楼路口←→杨营镇政府←→火车站（终点）公交三路（公交公司←→南转盘）终点站8分钟
收车时间：夏季：18:56冬季：18:29（全程一元）
公交公司←→胡坑村←→西环城路口←→磷肥厂←→物价局（凤园路口）←→设计院（种子站）←→交警大队←→镇一中←→南区派出所←→农业银行←→交通局←→社会客车站←→一中路口←→县法院←→粮食局家属院←→直属库←→武装部←→县政府←→城关医院←→国棉厂←→油漆厂路口←→建设银行←→杏苑小区←→计生局←→中行←→骨科医院←→东环路口←→茶庄村←→郑垓村北←→郑垓村←→郑垓村南←→杏花村←→马庙种子站←→马庙村←→郭庙村←→刘集村←→邵楼村←→祥宏挂 车厂←→南转盘（终点）公交五路（长途汽车站←→五里庙）终点站8分钟
收车时间：夏季：19:22冬季：17:56（车站至马营站点一元，全程二元）
交通局←→长途汽车站←→三角花园←→国税局路口←→自来水公司←→防疫站←→物价局←→西环路口←→薛屯村←→华良学校←→马营信用社←→马营乡政府←→赵坝村←→倪楼村路口←→五里庙（终点）
公交六路（公交公司←→二电厂）终点站3分钟
收车时间：夏季：19:12冬季18:20（全程一元）
公交公司←→杏花村宾馆←→马振杨路口←→现代汽修厂←→山水家园←→郝山头村←→县医院←→医院北门←→梁山风景区←→防疫站←→自来水公
司←→国税局←→农行←→交通局←→县农行←→工商局家属院←→教育局←→县财局←→工商局←→凤山公园←→中医院←→建设局←→棉麻公司←→城关医院←→水泊市场←→轴承厂←→县二中←→农机厂←→美术厂←→任庄村←→开发区←→环城路口←→二电厂（终点）
公交七路（收费站←→小安山）终点站14分钟
收车时间：夏季：18:35 冬季：17:45（全程票价一元）
收费站←→西唐庄←→小安山镇政府←→宋庄村←→地税局←→水泥厂（终点）公交八路（南转盘←→拳铺镇）终点站11分钟
收车时间：夏季：18:28 冬季：18:48（全程票价一元）
南转盘←→新科挂车厂←→华宇集团（聚丰挂车厂）←→巨源汽配公司←→宝通汽配公司←→姜庄←→钢材市场←→福豪汽贸←→永固挂车厂←→金源钢板开平有限公司（环球挂车厂）←→远东公司←→远大挂车厂←→宝华挂车厂←→恩信集团（华信专用汽车制造）←→水泊焊割←→后杨楼村←→拳铺镇政府（通亚汽车公司）←→泰福路口←→中集东岳公司←→拳铺信用社←→聚鑫商贸有限公司←→徐庄桥（绿色家园）（终点）
公交九路（南转盘←→梁山工业园）终点站10分钟
收车时间：夏季：18:36冬季：17：:30（全程票价一元）
南转盘←→林庄路口←→交警大队车管所←→前孙庄←→孙庄大桥←→环亚挂车厂（解庄村）←→梁庄村←→仁德二手车市场←→耿乡村←→柴林村←→华阳挂车厂（三 利树脂公司）←→徐集镇政府←→徐集镇中学←→梁山工业园（终点）
公交十路（西环路口←→鲍垓）终点站10分钟
收车时间：夏季：18:30冬季：18：00（全程票价二元）
三角花园←→国税局路口←→自来水公司←→东方华城小区←→物价局←→西环路口←→张飞垓←→吴垓←→胡屯←→鲍垓（终点）
公交十二路（县医院←→赵固堆）县医院25分钟，赵固堆15分钟
收车时间：夏季：18:30 冬季：18:00（县医院-----高楼路口2元，全程四元）
县医院←→医院北门←→梁山风景区←→三角花园←→长途汽车站←→交通局←→县农行←→工商局家属院←→教育局←→县财局←→工商局←→凤山公园←→华清←→高楼←→杨寨←→赵固堆
公交十三路（景区←→陈楼）终点站18分
收车时间：夏季：18:57冬季：18：:20（全程票价一元）
水泊梁山←→梁山风景区←→三角花园←→长途汽车站←→社会客车站←→一中路口←→公安局←→第一实验小学←→医药公司←→百货大楼←→水泊花园小区←→解放桥←→石棉厂←→北区派出所←→陈楼
公交十五路（火车站←→义和村）终点站10分钟
收车时间：夏季：18:20冬季：17：:30（全程票价二元）
公交十六路（三角花园←→方庄）终点站9分钟
收车时间：夏季：18:40冬季：18:00（全程票价二元）
方庄←→杨集←→曾庄←→杏花村宾馆←→马振杨路口←→现代汽修厂←→山水家园←→郝山头村←→县医院←→县医院北门←→梁山风景区←→三角花园 公交十七路（火车站←→赵那里）终点站15分钟
收车时间：夏季：18:20冬季：17:30（全程票价一元）
二十一路
收车时间：夏季：18:20冬季：17:30（全程票价一元）
重庆公交线路复杂网络性质研究 篇5
PAJEK软件以六种数据类型为形式, 以网络图的模型为基础, 以其快速有效性和人性化的特点, 为复杂网络的分析提供了一个仿真平台。它利用行之有效的算法分析复杂网络的拓扑结构, 包括从局部的角度分析网络节点和边的作用关系、利用抽象化的手段分析网络的全局结构, 还能方便的实现各种数据类型的相互转换。PA-JEK软件可以提供用户一个三维的可视化界面和一系列可视化工具。用户可随意地通过手动或者自动的调节节点位置、旋转网络图等方法, 从视觉的角度直观地分析网络模型[3]。
1 重庆主城区公交复杂网络构建
公共交通网络包含停靠站点和线路两个基本要素, 从公交线路之间的关系、公交系统的换乘特点、以及公交系统停靠站点之间的关系这3个方面出发, 可以构建公交线路、公交换乘和停靠站点三个复杂网络。文章中, 主要研究重庆市主城区公共交通系统中, 由公交线路构成的公交线路复杂网络。
公交线路网络[4]是以公交线路为节点, 若2条公交线路有相同的停靠站点, 则2个节点之间存在1条边。如101路和105路有共同的站点, 则这2个节点有边相连, 如图1所示。在PAJEK软件中, 必须按照PAJEK软件规定的格式分别对复杂网络的节点和边进行存储, 存储格式如下:
根据统计结果, 重庆市主城区公交线路有299条, 即结点有299个, 边有7213条, 用pajek软件仿真获得由299个结点和7213条边组成的巨型复杂网络图。
2 重庆主城区公交线路网络分析
2.1 度、度分布
网络节点的度是众多属性中最为基本也是极其重要的性质。一个节点i的度定义为与它相连的节点的数目, 用ki表示。因此, 一个节点的度越大意味着这个节点对于整个网络来说越重要。网络的平均度是所有节点度的平均值, 定义为
2.2 平均路径长度
平均路径长度是指网络中所有节点与节点之间距离的平均值, 表示任意两节点之间所连接的最小边数, 在文章公交线路网络中, 最短路径指任意两条线路之间最少相交的数目, 以重庆主城区公共交通网络的实际数据进行编程计算, 计算结果表明该网络是一个全连通无向网络, 计算得到平均路径长度d=2.15, 说明重庆市出行平均换乘2次公交线路才能达到目的地。
2.3 聚集系数
集聚系数用来描述网络中节点的聚集情况, 即网络的紧密程度.在文章公共交通网络中, 聚集系数反映各线路与附近线路的紧密程度, 聚集系数的平均值则反映了整个交通网络中公交线路的密集程度.平均聚集系数公式[5]:
计算后得到网络的平均聚集系数.说明重庆主城区线路公交网络中各线路的紧密程度较大, 具有很好的聚类特性, 因此线路网络具有小世界网络特性。
3 结束语
文章对重庆主城区公交线路网络作了实证研究, 利用matlab编程计算出其平均路径长度、度公布及聚集系数, 其平均路径长度为2.15, 平均聚集系数0.510775, 这些数值表明具有小世界网络特性[6]。研究表明重庆市主城区的线路规化比较合理, 总体上能满足市民出行需求。但从整体上看, 重庆主城区公交网络存在着密度大、站点的度分布不均以及线路重复较多等诸多问题。文章只是对线路公交网络的静态指标进行了分析, 但没有从整个网络的整体效率和网络上的动力学行为进行研究分析。因此对上述问题进行, 有待更进一步的研究与分析。
参考文献
[1]张兰华, 杜海涛.基于复杂网络的公交网络特性研究[J].机械设计与制造, 2012 (6) , 6:277-279.
[2]何悦, 重庆与中部地区开放型经济经较分析[J].重庆工商大学学报:自然科学版, 2013, 3 (4) :72-75.
[3]PAJEK中文使用手册[EB].
[4]王喆, 彭其渊.成都市公交复杂网络拓扑特性研究[J].交通与计算机2007 (2) 25 235.
[5]Dorogovtsev S N.Clustering of correlatged networks[J].系统工程, 2005, 23 (6) :1-7.
公交线路选择 篇6
2013年1月和2014年11月,我市分别举行了第一届、第二届“十佳公交线路”、“十佳百姓‘专职司机’”评选活动,取得了良好效果,推进了济南公交事业发展和公交服务水平的显著提升。
十佳公交线路的评选标准是:行车秩序优良;车厢环境整洁;服务质量过关;首末班车按点发车;按规定线路行驶,均衡运行,不串车,不甩站;依次进出站;车辆整洁,达到“四净一亮”,即车皮净、地板净、车厢内壁净、轮胎净、玻璃明亮;规范服务,无投诉;工装整洁,仪表端庄,悬挂工号;尊重乘客,主动照顾老、幼、病、残、孕等特需乘客;公交驾驶员自觉遵守交通法规及有关规定,无违章违纪行为,做到起步稳、转弯稳、行车稳、停车稳。
十佳百姓‘专职司机’评选标准是:悬挂服务工号,着标志服,衣着整洁,仪表大方;遵章守纪,文明行车,安全运行,无违法违规驾驶行为,无责任交通事故;按线行驶,均衡运行,无前压后赶、甩站、越站现象;严格操作规程,起步稳、行驶稳、停车稳;礼貌待客,微笑服务,语言文明、规范,使用普通话,开门迎客时使用“您好”问候语;遇有老、幼、病、残、孕及怀抱婴儿的乘客乘车时,给予照顾;耐心解答乘客询问,熟知济南市公交线路走向和服务网点的换乘,有问必答,多问不烦;文明监督投币和查验各类乘车凭证;车辆技术良好,无中途抛锚和冒黑烟现象;车辆服务设施齐全、有效,车厢内无乱贴、乱挂和堆积杂物现象。
公交线路选择 篇7
优先发展城市公共交通是缓解城市交通拥堵的有效措施。公交网络的设计与优化是优先发展公交的核心,对提高公交系统运输效率、实现资源优化配置具有重要作用。接运公交线路作为城市公交系统的重要组成部分,一般指专门为综合客运枢纽集疏乘客的常规地面公交线路[1]。它是提高综合客运枢纽换乘效率,增加城市公共交通吸引力的关键。
综合客运枢纽是多种客运方式衔接的地点,是实现客运方式转变的场所,乘客通过枢纽选择换乘,从而达到出行目的。它包括火车站、汽车站、轨道交通站等。随着综合交通的发展,如何为客运枢纽设计、优化接运公交线网已成为交通领域研究的热点。在国外的研究中,Vuchic提出了以最大客运需求来设计接运公交线网的方法[2];Kuan等利用启发式遗传算法来求解接运巴士网络优化的NP难问题[3];Chien和Schonfeld提出了基于交通枢纽的干、支线路发车时刻协调的接运线路优化设计方法[4]。在国内,这方面的研究相对较少,许旺土等以最少线路接运最大客流量为目标,曹玫以运营者消耗和使用者消耗之和最小为目标,建立了线路优化设计模型[5],并给出了求解模型的遗传算法。陆化普等学者对其也有一定的研究。虽然现有的研究已取得了一定的成果,但都很少探讨接运公交的布设和客流集疏优化的关系,也没有考虑客运枢纽对接运公交的吸引范围。因此,本文以单位里程内客运周转量最大化为目标,在尽量保障线路条数最小的情况下,设计了综合客运枢纽的接运公交线路布设优化模型,采用禁忌搜索算法对模型进行求解,最后测试了算法的效率。
2 优化模型的建立
2.1 问题描述
综合客运枢纽的主要功能是实现客流的集散。它的接运公交线路优化设计问题可以描述为:在某个综合客运枢纽的客流吸引范围内,布设若干接运公交线路,连接综合客运枢纽和周边公交站点,从而来实现站点之间客流的集散与换乘,要求尽量保证该接运系统最优(线路最少、效率最高等)。
综合客运枢纽接运公交线路优化设计问题可以认为是一类特殊的取送一体化的开放式车辆路径问题(Open Vehicle Routing Problem with Pickup and Delivery, OVRPPD),综合客运枢纽可以看成是OVRPPD的集散中心,接运公交站点可以看成是OVRPPD的客户[6,7]。一般的OVRPPD是在给定的约束条件下,研究如何合理地安排线路,将集散中心的货物运送到客户(对应的是将综合客运枢纽的客流疏散到各接运公交站点);而综合客运枢纽接运公交线路优化问题是OVRPPD的升级,它要求在安排线路时,首先要完全满足综合客运枢纽与接运站点之间的交通需求;其次还要尽量满足各接运站点之间直达交通需求(如果没有直达线路,各接运站点之间则通过综合客运枢纽换乘);同时,还要考虑综合客运枢纽对接运公交站点的吸引有一定的范围限制(因为受枢纽区位、规模及公交线路长度等影响)。
2.2 模型构建
综合客运枢纽接运公交线路优化设计问题可归结为如下的网络模型:设G=(V,E)是一连通的网络, V是顶点集,V=0,1,2,…,n,其中, 0表示综合客运枢纽, 其它表示公交接运站点; E为边集, 是连接各顶点的边, 边被赋权重(本模型用距离表示);D为距离矩阵,D=(dij)(n+1)×(n+1),其中,i,j=0,1,2,…,n,它的元素表示各站点之间的距离;OD为公交需求矩阵,OD=(odij)(n+1)×(n+1),其中,i,j=0,1,2,…,n,它的元素表示各站点之间的公交需求量;D与OD均为对称矩阵;K为布设的线路条数,nk为第k条线路上的站点数;Rk为一集合,表示布设的第k条线路,其中元素rki表示接运站点rki在第k条线路上的顺序为i,令rki=0表示综合客运枢纽;qij表示布设线路上站点i与站点j的公交客流量。
为构建数学模型,我们基于如下假设:
①每个接运公交站点仅对应唯一的接运线路;
②每条接运线路都是以综合客运枢纽站和某个接运公交站为起始点,且长度有一定的限制;
③各站点的位置、公交车的容量、营运速度等均已知;
④各站点之间的客运需求量,即公交OD矩阵已知,且假设OD矩阵为对称矩阵;
⑤接运公交车在其线路上所有站点都停靠;
⑥线路布设之后,按照全有全无方式分配公交客流。
因此,综合客运枢纽接运公交线路优化设计问题的数学模型可以描述为:
上述模型中,式(1)表示第一优化目标,最大化整个系统的运输效率,即单位里程内公交旅客周转量,其中分子为整个系统公交旅客周转量,分母为整个系统布设线路总长度,该目标是要求最大可能的满足各站点之间的OD需求,但允许某些站点之间存在OD需求但没有布设线路(需通过客运枢纽换乘);式(2)表示第二优化目标,最小化布设的线路条数;式(3)表示同一线路上相邻两个站点间的公交客流量,它包括这两点间的直达客流量(对应OD点对)和其他站点途径此两点的客流量。式(3)的处理方式是将相邻两站点看成是前站点和后站点,那么,在同一接运线路上,相邻两个站点间的公交客流量等于所有后站点之前的站点到该站点的OD量之和加上所有前站点之后的站点到该站点的OD量之和,然后再减去重复计算的前站点到后站点的OD量。式(4)表示线路长度的取值范围;式(5)表示线路非直线系数的取值范围。式(6)表示整个系统中各接运公交站点都有一条线路通过;式(7)表示布设接运线路的站点组成;(8)表示布设公交线路仅在综合客运枢纽处交汇。
2.3 优化流程
综合客运枢纽接运公交线路优化的流程如图2所示。
接运公交线路优化首先要确定综合枢纽合理吸引范围,一般认为,它是以一个综合客运枢纽为圆心、以乘客通过常规公交换乘到该枢纽的空间距离为半径的圆所覆盖的区域。作者在文献[8]中已经研究了轨道交通枢纽对常规公交客流的吸引范围。所以,本文直接利用该研究结论作为综合枢纽合理吸引范围的一种形式,进一步探讨优化模型的求解及算法。由于该优化问题是一个NP难问题,求解问题相当复杂。因此,通常需要采用智能优化算法才能实现。参考相关文献,综合考虑,作者采用禁忌搜索算法来求解该模型。
3 算法分析及描述
禁忌搜索(Tabu Search,TS)算法,也称为列表寻优法,是局部(爬山算法)搜索算法的推广,是一种全局逐步寻优算法。Glover[9]于1986年首次提出了这一概念,进而形成了一套完整的算法。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效搜索以最终实现全局优化。
一般TS的基本思想是:给定一个当前解(初始解)和一个邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于到目前为止搜索到的“最好解”,则忽视其禁忌特性,用其取代当前解和“最好解”,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代过程,直至满足停止准则[10]。
基于这一思想,本文提出了一种求解综合客运枢纽接运公交线路优化设计问题的禁忌搜索算法。
3.1 解的表示
用禁忌搜索算法求解接运公交线路优化设计问题时,确定解的表示方式是一项非常关键的工作。它直接决定算法实现的难以程度和算法性能的优劣。首先确定解由综合客运枢纽和接运公交站点共同排列组成,然后采用自然数编码的表示方式,对于n+1个站点,产生n+1个0～n不重复的自然数排列。其中,0表示综合客运枢纽,其它表示公交接运站点。如{013450298076},它表示3条接运公交线路,01345,0298和076。
3.2 初始解
任何禁忌搜索算法需要一个初始解,以开始其局部搜索过程。本算法将以随机方式产生初始解。
3.3 邻域结构
传统的禁忌搜索算法在求解组合优化问题时,往往仅采用单一邻域变化产生候选解,通常这样会花费较长的时间来搜索解空间。为进一步增强禁忌搜索算法的性能,在求解综合客运枢纽接运公交线路优化设计问题,本算法设计了四种邻域,分别是重新指派、顶点交换、2-opt和“尾巴”交换。在同一线路或不同线路中随机挑选2个顶点(综合客运枢纽或接运站点),随机执行以上四种邻域变换中的一种[11]。
3.4 解的评价
用禁忌搜索算法求解组合优化问题时,需要对解进行评价,使算法在迭代过程中,不断搜索到质量更优的解。针对综合客运枢纽接运公交线路优化设计问题,判断某个解的优劣需首先要将该解转化为对应的线网方案,然后再判断该线网方案是否满足约束条件,同时计算该线网方案的目标函数值,若其目标函数值越优,则解的质量越高(本模型需优化2个目标:最大化整个系统的运输效率和最小化布设的线路条数)。采用由综合客运枢纽和接运公交站点共同排列组成的解的表示,能清晰地确定线网的布设方案,也隐含着每个接运公交站点仅对应唯一的接运线路、布设公交线路仅在综合客运枢纽处交叉等约束条件,但不能保证线路满足长度和非直线系数的约束条件。因此,对于不满足上述2个约束条件的解,应分别引入惩罚值,将约束条件包含到目标函数中进行衡量。此外,对于本算法确定的解的表示方式,经过若干次邻域变换后,可能存在2个“0”相邻或1个“0”排列在末尾的极端情况,这两种情况与实际不符合,也应该给予惩罚。综上,将优化的2个目标及约束条件进行整合,得到解的评价方式,见式(8)。
其中,E和K分别为第一和第二优化目标,P1、P2和P3分别为线路长度、非直线系数以及2种“0”排列极端情况对应的惩罚值。P1,P2,P3∈(1,M),当满足约束条件或不存在“0”排列极端情况时,分别取1;反之,分别取M.其中,M为一个无穷小的正数,如M=10-4.通过这样的处理,允许不可行解存在,Z越大,目标函数越优,解的质量越高。
3.5 禁忌表
本算法构造的禁忌表用于记载最近5～10(随机挑选)次迭代中解的变换特征,用一组(n+1)(n+1)阶矩阵来记录禁忌情况,若点i被挑选来进行顶点重新指派变化,则将其禁忌情况存入矩阵的元素(i,j)中。若点i和j被挑选来进行以下三种变换:顶点交换,2-opt,“尾巴”交换,则将其禁忌情况存入矩阵的元素(i,j)中,在每一次迭代时,都必须将上一步所进行的变换填入到禁忌表中,而表中的其他元素相应地减1直到等于0为止[11]。
3.6 终止准则
当总迭代次数达到一个给定值,或在一个给定的连续迭代步数内当前最好解无改变时,算法终止。将用到以下相关变量:
steps为当前的迭代步数;
maxsteps为最大的迭代步数;
conssteps表示当前最好解保持不变的当前连续迭代步数;
maxconssteps表示当前最好解保持不变的最大连续迭代步数;
candlist 当前的候选解数量;
maxcandlist 最大的候选解数量。
3.7 算法描述
随机产生一个初始可行解,并置该解为当前解和当前最好解;
从候选解集中选择非禁忌的最佳候选解,或若存在一个优于当前最好解的禁忌候选解,则解禁该候选解,并将其作为最佳候选解;
置新的最佳候选解为当前解,steps的值加1;
若新的最佳候选解优于当前最好解,则更新当前最好解,并置conssteps为0;否则,conssteps的值增加1;
end
该禁忌搜索算法的特点是:解的表示十分直观,惩罚值的运用使得我们在搜索过程中可以对不可行解进行试探,有助于跳出局部最优解。灵活的邻域结构使得算法在搜索过程中,可随机地从4种邻域变换中择其1种,禁忌长度也是随机地在5～10之间选择,这样增加了搜索的多样性。
4 案例分析
用Matlab语言实现了上述优化问题的禁忌搜索算法, 并构造了相关算例。算例中, 该综合客运枢纽是由多条轨道交通线路相交形成, 它周边有若干常规公交接运站点, 参考相关文献可知, 此类枢纽的合理吸引半径为 7.8kM. 在这个合理吸引范围内,共搜索到接运站点16个,各站点的分布坐标及各站点间的OD需求情况分别见表1和见表2。
算法的主要参数如下:允许最大的迭代步数maxsteps=1200+300n,当前最好解保持不变的最大连续迭代步数maxconssteps=600+100n,最大的候选解数量maxlist=150+2n, n为接运的站点数。用该算法连续10次求解该优化问题,优化目标值全为12.9123,对应的最终解为[0 3 6 10 11 2 12 1 0 15 7 8 13 14 4 5 0 9 16], 得到该解的迭代步数685～2449次, 运行时间在9.52～50.66s,充分表明该算法有较好的稳定性和较快的收敛速度。由此,该案例的接运线路优化方案是:布设设3条公交接运线,分别是(0 3 6 10 11 2 12 1)(0 15 7 8 13 14 4 5)和(0 9 16)。
5 结论
①本文描述了以综合客运交通枢纽为中心的接运公交线路优化问题,将其归结为一类取送一体化的开放式车辆路径问题,并构建了优化模型。将系统运输效率最大和布设线路最小作为优化模型的双目标,在综合客运枢纽的吸引范围内布设线路,同时考虑线路长度、非直线系数等约束条件。
②实验计算结果表明,用本文设计的禁忌搜索算法求解综合客运枢纽接运公交线路优化设计问题,算法收敛速度较快,计算结果较稳定,显示了良好的寻优性能。
③本模型的优化结果是假设将公交客流按照全有全无方式进行配流,在后续研究过程中,可进一步探讨其他配流方法,以更好地仿真公交系统。
摘要：分析了综合客运枢纽接运公交线路优化设计问题的内涵及作用,构建了以运输效率最大和布设线路最小为双目标的优化模型,并将它转化为一类特殊的取送一体化的开放式车辆路径问题进行求解,给出了求解的禁忌搜索算法。最后通过案例进行了验证,证实了该算法具有良好的寻优性能。
关键词：接运公交,综合客运枢纽,禁忌搜索算法,车辆路径问题
参考文献
[1]曹玫,林小涵.基于遗传算法的城市轨道交通接运公交线网规划[J].武汉理工大学学报,2005,(8):568～570.
[2]Vuchic V R.Urban transit:Operation,planning,and economics[M].Hoboken,New Jersey:Johnwiley&Sons,Inc.,2004.
[3]Kuan S N,Ong H L,Ng K M.Solving feeder busnetwork design problem by genetic algorithms andant colony optimization[J].Advances inEngineering Software,2006,37(6):351～359.
[4]Chien S,Schonfeld P.Joint optimization of a bailtransit line and its feeder bus system[J].Journal ofAdvanced Transportation,1998,32(3):253～284.
[5]许旺土等.基于改进遗传算法的接运公交线路生成优化模型[J].北京交通大学学报,2009,(6):40～44.
[6]孙丽君等.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,24(11):31～35.
[7]符卓,聂靖.求解带装载能力限制的开放式车辆路径问题的遗传算法[J].系统工程,2008,26(2):78～83.
[8]王佳,胡列格.城市轨道交通站点对常规公交客流的吸引范围研究[J].系统工程,2010,28(1):14～18.
[9]Glover F.Future paths for integer programmingand links to artificial intelligence[J].Computersand Operations Research,1986,13:533～549.
[10]郎茂祥.配送车辆优化调度模型与算法[M].北京:电子工业出版社,2009.
可变线路式公交车辆调度优化模型 篇8
随着经济的发展和机动化水平的提高,城市交通拥堵问题也不断加剧。公共交通在道路交通资源的充分利用上具有私人交通无法比拟的优越性,已经成为缓解道路交通拥堵的1条重要途径。可变线路式公交(flex-route transit)作为1种新型公交运营模式,融合了常规公交运营模式(FRT)的高成本效益以及需求响应式公交系统(DRT)的机动灵活,能够提供门到门的公交运输服务,是解决城郊地区公交服务问题的1条重要途径。
可变线路式公交可以描述为:车辆在一定的服务区域内围绕基准线路运行,并在松弛时间内偏离基准路线行驶,在乘客要求的地点停车上下客。车辆行驶过程中满足一定的时空限制,即车辆驶离基准路线为乘客提供站外上下车服务之后,需要返回基准线路继续行驶,并且满足线路上固定站点的时间约束。根据可变线路式公交乘客的上下车位置可以将其分为4类:站外上车站外下车(I类)、站内上车站外下车(II类)、站外上车站内下车(III类)和站内上车站内下车(IV类)。其运行模式见图1,其中1和s为公交线路的首末站。
现阶段国内外学者对于可变线路式公交系统已经做了一些研究。云亮等[1,2]总结了目前国内外可变线路式公交的主要研究成果,并研究了多车辆可变线路式公交的调度问题;Koffman[3]探讨了已有的可变线路式公交系统的实践经验;Quadrifoglio等[4,5,6]利用连续近似的方法计算出可变线路式公交系统中车辆径向速度的上限和下限,并全面描述了可变线路式公交的参数,建立了可变线路式公交的混合整数规划模型,同时分别提出可变线路式公交的静态和动态路径选择及调度模型;Wei Lu等[7]针对多车辆可变线路式公交调度的动态插入算法进行了研究;Quadrifoglio和Dessoukly[8]利用仿真实验对可变线路式公交的性能指标进行了分析;Baha W.Alshalalfah等[9]以多伦多市的3条公交线路为例,利用数学仿真模型证明单纯增加松弛时间并不能有效的增加公交服务能力,并通过与常规公交运营方式进行对比,判定其作为地铁接驳线路的可行性和适用性。
本文在总结已有研究的基础上,以为更多乘客提供站外上车(下车)服务为目标,综合考虑乘客出行成本和公交运营成本,建立了可变线路式公交的运营调度模型。这对于我国开展可变线路式公交服务,提高公交整体服务水平具有重要意义。
1 可变线路式公交车辆调度模型
1.1 模型假设
可变线路式公交车辆调度时,要求有站外上车或下车请求的乘客(I类、II类和III类乘客)提前通过电话预约系统或者网上预定系统提出出行请求,说明其个人信息以及出行信息。可变线路式公交运行过程中受到诸多因素的影响,为建立其调度模型,本文做出如下假设:
1)将研究目标定为有S个(S≥3)固定站点的单车辆调度模型,车辆由站点1到站点S为下行方向,由站点S到站点1为上行方向。
2)乘客车上时间不会超过1个班次的发车间隔T,发车间隔T为公交车辆在站点S与站点1发车时间的时间差。
3)出行需求在整个服务区域内均匀分布,第IV类乘客随机到达固定站点。
4)公交车辆保持匀速按照直线形式运行,如车辆先沿水平方向行驶,再沿垂直方向行驶到达需求点;车辆严格按照行车时刻表运行,不允许车辆越站、超车。
5)车辆能正常运行,不考虑诸如车辆抛锚、堵车、交通事故等特殊道路交通状况的发生。
1.2 变量说明
xij为二进制变量,当车辆在路段(i,j)上行驶时取值为1,否则取值为0;A为路网中所有路段的集合;Iij为路段(i,j)上的道路交通路阻系数;dij为路段(i,j)间的直线距离;M={m|m=1,2,3,4}为乘客类型的集合;nm为第m类乘客的数量;nli为车辆到达固定站点i时公交车上出行终点不在站点i的乘客数量;NB(t)为t时刻公交车辆上的乘客数量;Di(t)为t时刻到达并在固定站点i上车的第IV类乘客数量;Nm为第m类乘客的集合,N=N1∪N2∪N3∪N4为所有乘客的集合;S为固定站点的集合,NS为站外停靠点的集合,SS为所有停靠点的集合,SS=S∪NS;xi为停靠点i的横坐标;dxback为车辆在x方向上允许的最大逆行距离;固定站点i的车辆计划发车时间用TSi表示,上一发车班次固定站点i的发车时间用TS′i表示,且TSi=TS′i+T;ASi为计划中车辆到达固定站点i的时间;分别用ta(i)、td(i)(i∈SS)表示车辆到达停靠点i的时间和从停靠点i发车的时间;TPk和TDk分别为乘客k的上车时间和下车时间;TRi(k)为站外上车乘客希望在停靠点i(i∈NS)能够上车的时间;[ek,lk]为站外上车乘客k(k∈N1∪N3)上车时间的时间窗;Ts为公交车辆在每个站点的服务时间,文中认为各个站点的服务时间相同;w1、w2和w3分别为车辆运营成本、乘客候车时间和乘客在固定站点空闲时间的权重系数;α1为车辆行驶里程的货币成本,α2为乘客时间消耗的货币价值;cm(m∈M)为第m类乘客支付的公交票价,本文认为同类乘客的票价相同;车辆的行驶速度用v表示;CB为公交车辆的额定载客数;Z为一个任意大的值。
1.3 数学模型
以系统总成本最优为目标建立的可变线路式公交车辆调度模型为
上述模型中,式(1)为可变线路式公交调度模型以出行成本系统最低为目标,即车辆运营成本和乘客出行成本的最小化,其中运营成本为车辆行驶成本与票价收入之差,乘客出行成本用乘客的候车时间以及乘客在固定站点的空闲时间衡量,其中站外上车乘客的候车时间用乘客实际上车时间与期望上车时间之间的差值表示,固定站点空闲时间的最小化是为了使公交车辆尽可能地服务更多的需求响应式乘客;式(2)和式(3)为车辆在所有停靠点只停留1次,保证每1个停靠点只有1条发车路径和到达路径;式(4)保证了车辆能在固定站点的计划发车时间之前到达站点并且完成乘客的上下车服务;式(5)为站外上车乘客上车时间满足时间窗限制;式(6)保证乘客下车时间晚于其上车时间;式(7)为站外上车乘客的上车时间不早于系统给定的上车时间;式(8)为任何时刻车上乘客数量都能满足公交车辆的额定载客容量限制;式(9)为当车辆在路段(i,j)上行驶时,车辆到达停靠点j的时间不会早于从停靠点i的发车时间加上在2个停靠点之间的行驶时间;式(10)为车辆的在路段(i,j)上的x方向的逆行距离不超过允许的最大逆行距离。
2 模型算法设计
可变线路式公交车辆调度可以看作1个混合整数规划问题,受到松弛时间、固定站点发车时刻等多种因素的限制,是1类特殊的NP-Hard问题,在问题规模较小的情况下可以采用精确算法,但是其计算量随着问题规模的增大按指数方式增长,因此这类问题常采用启发式算法编程求解。遗传算法[10]是基于“适者生存”规律的1种高效、并行、随机和自适应的优化算法。本文拟针对可变线路式公交静态调度模型的特点,设计相应的遗传算法进行求解。
2.1 遗传算子设计
由于遗传算法[10]不能直接处理问题的解,因此设计遗传算子之前需要对变量进行编码,将问题的解转换成遗传空间的基因型串结构数据即染色体。本文采用自然数编码即序数编码的方式,编码主要是给出车辆经过的停靠点。如“1 3 7…”表示车辆依次经过停靠点1、停靠点3和停靠点7等。
1)复制算子。复制算子模仿优胜劣汰的遗传法则,即从当前群体中选择性能优良的个体,使它们有机会作为父代繁殖下一代群体。本文设计的遗传算法中,采用最佳保留的轮盘赌法进行染色体的复制。
2)交叉算子。交叉算子是用双亲基因生成新染色体,体现的是有性繁殖的自然规律。本文构造的交叉算子为最大保留交叉[11]:若染色体交叉点处的2个基因都为0,直接进行顺序交叉运算;若染色体交叉点处的基因不全为0,则将交叉点左移(右移),直到左、右2个交叉点处的基因都为0,再进行顺序交叉运算。
3)变异算子。变异模仿自然界中基因突变现象,并按照一定的概率即变异率发生,从而改变染色体的基因链,挖掘染色体个体重基因组合的多样性。变异运算采用单点变异的方式。
为了更好的求得最优解,采用自适应参数策略调整交叉变异概率,通过设定目标函数最大累计未变化代数,提高交叉变异概率,从而避免陷入局部最优。
2.2 适应度函数
适应度函数是用来区分群体中个体好坏的标准,是进行自然选择的依据,一般是由目标函数加以变换得到。可变线路式公交静态调度模型的目标函数是系统运营成本的最小化,本文的适应度计算函数为
式中:fh为个体h的适应度函数;Zmin为同一代群体中最佳个体的目标函数值;Zh为个体h的目标函数值。适应度函数值越大的个体越优,反之越劣质。
2.3 初始解构造
本文拟采用最近插入法生成初始解。首先由第1个和第2个固定站点形成1个初始路径。然后根据车辆的容量限制、时间窗限制及松弛时间限制等约束条件,判断站外停靠点i(i∈NS)是否具有插入路径中的可能,不断修正车辆的路径。
步骤1。从第1个固定站点出发,找到1个最近的站外停靠点i(i∈NS),如果具有插入的可能性即满足时间窗及松弛时间等约束,检验目标函数的增量Δ,将停靠点i插入Δ最小的节点之间。
步骤2。如果停靠点i不具有插入的可能性,则将剔除出站外停靠点的集合NS,转到步骤3。
步骤3。重复步骤1、2,直到集合NS中所有能插入的点都加入到路径中,得到1个初始解,即遗传算法的初始群体。
2.4 算法步骤
步骤1。输入路网特性、出行需求特性及车辆容量等参数信息。
步骤2。对问题进行编码,设置初始进化代数GEN=0和累计目标函数未变化代数n=0,设置最大进化代数GENmax和最大累计目标函数未变化代数nmax,并设定选择运算参数和初始交叉、变异概率等计算参数,按照2.3节介绍的方法产生一个初始种群作为初始解。
步骤3。计算种群中各个个体目标函数以及适应度函数,对比前后2个个体的目标函数,如果相等,则n=n+1;否则,n=0,并保留适应度值较大的个体进入新一代种群。
步骤4。采用轮盘赌方式进行选择操作,若n>nmax,则提高交叉和变异概率,否则,就按照初始设定的交叉和变异概率进行交叉、变异操作。如果出现了新的最优解,则将新生成的种群作为当代种群。
步骤5。判定种群的进化代数是否达到最大进化代数。若GEN=GENmax,转到步骤6;否则,GEN=GEN+1,转到步骤3。
步骤6。结束遗传操作,输出结果。
3 算例分析
算例通过将可变线路式公交与常规公交进行对比的方式,论证可变线路式公交系统的实用性。为了便于比较2个系统的性能,算例中选用了以下性能指标:
PAR,系统接受站外需求概率;PT,人均车内时间;PW,人均候车时间;PWK,人均步行时间;TL,车辆行驶总里程。
全局性能指标F(以时间单位计)定义如下:
式中:CT为乘客总数;CP为第Ⅳ类乘客的数量;w1,…,w4为权重系数。Z的值越小,表示系统的全局性能越优。
算例中采用的服务区域为矩形区域,其中:L×W=10×1km2,车速为v=25km/h,各站点车辆服务时间为12s。对于常规公交系统,假设基准线路上均匀分布有21个固定站点(即2个相邻固定站点间的距离为0.5km),公交车辆的车头时距为60min。假设有10%的乘客碰巧赶上公交车,等待时间为0,有80%的乘客基于公交时刻表和个人经验,在最佳时间到达公交站点并且等待时间几乎为0,剩余10%的乘客随机到达,并且平均等待时间为公交车辆平均发车间隔的一半。对于可变线路式公交系统,假设基准线路上均匀分布有5个固定站点(即S=5,2个相邻固定站点间的距离为2.5km),并且2个相邻固定站点的车辆发车时间间隔为12.5 min。因此可变线路式公交车辆的车头时距为100min,2个连续的固定站点间有5.98min的松弛时间可用于为站外上车(下车)的乘客服务。对于系统不能接受的那部分站外需求,则转变为在固定站点上下车,即归入第Ⅳ类乘客。
假设2个连续停靠点间的路阻系数相同即Iij=0.92。4类出行需求的比例为:I类(10%)II类(40%)III类(40%)IV类(10%)。根据乘客出行需求的灵活性,4类乘客的票价分别为:I类乘客:3元,II类、III类乘客:2元,IV类乘客:1元。行驶里程的货币成本取为6元/km,乘客时间消耗的货币价值取为18元/h。在为权重系数赋值时,假定乘客对站点等待上车时间的不满意度是对在车内等待下车时间不满意度的2倍,而车辆行驶时间和乘客车上时间的权重相同,步行时间和候车时间的权重相同。因此,算例中采用的权重值为w1=0.1、w2=0.2、w3=0.2、w4=0.1。设置最大进化代数GENmax=200,初始交叉概率为0.4,变异概率为0.1,目标函数值累计进化80代没有变化(nmax=80),将提高交叉变异概率。
算例利用Matlab编程实现仿真实验。算例中对各系统取共同随机数,并分别针对ρ=15人/h、ρ=20人/h和ρ=25人/h进行了100h的仿真实验,即常规公交车辆共运行了200个班次,可变线路式公交车辆共运行了120个班次。仿真对比结果见表1。
由仿真结果表明,对于可变线路式公交系统,随着出行需求率的增大,人均车内时间呈现逐渐增加的趋势,比同类型常规公交乘客大约要多花费10min。并且由于系统接受的站外上(下)车乘客比例降低,被拒绝的那部分乘客转变为在固定站点上下车,需要步行到站(离站),人均步行时间、人均等待时间也逐渐增加。此外,为了服务站外上车(下车)的乘客,车辆需要绕行一定的距离,因此单个班次可变线路式公交车辆的行驶里程大于常规公交车辆的行驶里程。由表1中全局性能指标的数据可知,可变线路式公交系统相比于常规公交系统更优,即在该服务区域比常规公交系统更有效,然而随着出行需求率的增大,可变线路式公交系统的优势愈来愈不明显。事实上,当出行需求达到一定量的时候,采用常规公交运营方式更为经济高效,算例结果符合实际。
4 结束语
在分析公交公司运营成本及乘客出行费用的基础上,综合考虑了乘客的出行时间、候车时间以及车辆的行驶里程、公交票价等因素,建立了可变线路式公交系统的调度模型。并且针对该模型设计了相应的遗传算法,从而在系统成本最优的情况下,获取公交车辆的最佳路径。本文在建立模型时,只考虑了提前预约的已经确定的出行服务。实际中,可变线路式公交不仅能够为预约需求提供服务,还需要为实时出现的乘客即动态需求提供服务。这类既考虑预约需求又考虑实时需求的混合调度模型更具有实用性,还有待于进一步深入地分析研究。
参考文献
[1]云亮,蒋阳升,宋雪梅.机动式辅助客运系统(MAST)及其研究进展综述[J].交通运输工程与信息学报,2009,7(4):79-83.
[2]Jiang Yangsheng,Yun Liang,Liu Huijun,et al.Multi-vehicle system design for mobility allowanceshuttle transit service[C]∥China Wuhan:Interna-tional Conference on Mechanic Automation andControl Engineering,2010:2858-2862.
[3]Koffman D.Operational experience with flexible transitservice[R].Washington,DC:Transportation ResearchCooperative Research(TCRP),Report 53,TRB,Na-tional Research Council,2004.
[4]Quadrifoglio L,Dessouky M M,Hall R W.Perform-ance and design of mobility allowance shuttle transit(mast)services:bounds on the maximum longitudi-nal velocity[J].Transportation Science,2006,40(3):351-363.
[5]Quadrifoglio L,Dessouky M M F.Mobility allow-ance shuttle transit(MAST)services:MIP formu-lation and strengthening with logic constraints[J].European Journal of Operational Research.Europe-an Journal of Operational Research,2008,185(2):481-494.
[6]Quadrifoglio L,Dessouky M M,Palmer K.An inser-tion heuristic for scheduling mobility allowanceshuttle transit(MAST)services[J].Journal ofScheduling,2007,10(1):25-40.
[7]Wei Lu,Lu Lu,Luca Quadrifoglio.Scheduling mul-tiple vehicle mobility allowance shuttle transit(m-MAST)services[C]∥Washington,DC:USA,14thInternational IEEE Conference on Intelligent Trans-portation Systems,2011:125-132.
[8]Quadrifoglio L,Dessouky M M.Mobility allowanceshuttle transit(MAST)services:formulation andsimulation comparison with conventional fixedroutte bus services[C]∥proceedings of the fauthIASTED International conference on Modeling,Simulation and Optimization(USA),2004:31-36.
[9]Alshalalfah B,Shalaby A.Feasibility of flex-route asa feeder transit service to rail stations in the sub-urbs:Case study in Toronto[J].Journal of UrbanPlanning and Development,2012,138(1):90-100.
[10]史峰,王辉,郁磊,等.MATLAB智能算法30个案例分析[M].北京:北京航空航天大学出版社,2011.
公交线路选择 篇9
去年12月29日上午,在温馨的冬日暖阳里,湖里区禾山街道439路环五缘湾“社区公交”开通仪式暨“你的样子——手绘公交最美厦门”发车仪式在浪漫的五缘湾畔正式启动,车外五彩斑斓的图案、车内逼真的3D图案,吸引了大批乘客。
为缓解环五缘湾游客及南北岸周边居民的出行难问题,湖里区禾山街道与厦门公交集团湖里公交公司合作,在环五缘湾区域内开通“社区公交”线路439路公交车。
【公交线路选择】推荐阅读：
霸州公交线路信息05-12
公交线路的报告07-31
公交线路调度员及车站站务员招聘 职位描述07-10
线路方案选择09-14
旅游线路的选择09-25
线路保护与通道选择10-03
发挥工会职能 构建和谐公交—慈溪公交08-11
公交问题10-16
公交安全10-19
公交环境10-20