基于蚁群算法的智能公交运营调度研究.docx

基于蚁群算法的智能公交运营调度研究 本文结合吴江市公交运营现状，建立了一个基于成本费用，兼顾公交公司与乘客候车成本利益的目标函数在该调度模型基础上，结合吴江市101路公交线路上各时段的客流情况，先给每个时段设定几个经验发车间隔，这些备选的经验发车间隔可以理解为“路段”；通过构建这样一个公交排班网络图，把文中所要求解的公交调度问题转化为一个“TSP”问题(TravellingSalesmanProblem，即旅行商问题)[1]，再应用蚁群算法按照求解“TSP”问题的步骤，对所要解决的公交调度问题进行求解最后，运用C语言对公交排班调度问题的蚁群算法进行编程，根据不同的参数组合得到的目标函数值的优劣，确定出一组最优的参数组合，依据这组最优参数组合，通过反复计算，最终得到一组最优发车间隔，从而制定出一张该公交线路上的全天发车时刻表期望文中所用方法能够对吴江市的公交调度工作有一定的应用价值一、建立目标函数结合公交公司既有企业性质又具有公益性质的特点，在制定全天某条线路上的发车时刻表时，应该考虑全天内该线路的整体效益以及全天内乘坐该线路车的所有乘客的等车成本可以通过一天内总的发车车次来反映公交公司的利益，通过乘客一天内的总等车时间来反映乘客的利益[2]。

一天内总发车车次最少：注：k表示第k时段，将一天划分为K个时段，时段集K={1......k......K}mk表示k时段内的发车次数一天内乘客总的等车时间最短：注：j表示第j个车站，j表示线路的车站总数，车站集J={1......j......J }表示第j站等待第k时段发出的第i次车的乘客数，表示k时段发出的第i次车在j站上的滞留乘客人数表示k时段发出第i次车的发车间隔目标函数要从整体考虑达到最优，需将两个函数合并为一个函数，合并时统一量纲，需要把两者统一折算为费用(元)第一项总的发车车次可折算为公交公司的运营费用假设某市公交车辆平均每车公里的成本费用为元，公交线路里程为L，这样一天内总的发车车次由运营费用来衡量，可以折算为：第二项乘客总的等车时间可折算为乘客等车损失的费用，假定某市市民的单位时间成本为y元/min单位时间成本y的值可以根据当地城市人均月收入除以每月减去双休日的天数得到每天的收入费用，然后再用这个费用除以按照每天八小时工作日换算出的分钟得到这样所有乘客总的时间损失费用可表示为：为了体现公交行业公益性的特点，合并两函数时在乘客的总损失费用前面加一个公益系数F，统一后的目标函数为：已知某市公交公司某条线路上发一趟车的成本费用为χL，假设该市公交票价为α元/人。

若要保证公交公司盈利，必须使得平均一趟车载客收费大于，而考虑到公交的公益性特点，给每趟车的发车费用乘以一个小于1的系数，即：注：μkj表示k时段第j站的上车乘客数考虑到公交公司每发一趟车的成本费用，给出了一个车辆最低满载率f ´；同时也考虑到公交乘坐服务质量对乘客的舒适度影响，给出了一个车辆最高满载率f各时段内的每趟车的实际车载率满足：如前所述在调整时段内的发车间隔时，可能会根据前一趟车的满载率情况，对下一趟车的发车间隔做相应调整，而为了避免引起两趟车间发车间隔的很大波动，给调整数规定了一个范围：综上整个函数可表示为：目标函数：约束条件：注：Tk表示时段的k时段长度△tk表示k时段的备选发车间隔，该时间是从几个经验发车间隔中随机产生的二、蚁群算法网络图设计在抽象蚂蚁路径之前，先根据每个时段的客流量，把全天内所有时段按照客流高峰、平峰、低峰状态归类根据经验给归好类的各时段分别界定一个发车间隔区间相应的每个时段便对应一个可供选择的发车间隔区间在编程运算过程中，为了方便计算，需要把各时段内的备选间隔定为相同数目，不足的部分用一个大数来补充假定每个区间内可供选择的发车间隔元素数为6个，用△tsk表示第k时段的发车间隔区间里的第个供选择的元素[3]，便构造出如图1所示的供人工智能蚂蚁搜索的公交运营调度网络图。

三、蚁群算法步骤通过前面构造的公交运营调度网络图，已经把公交运营调度问题转化成为了“TSP”问题，通过公交调度蚁群算法模型的建立，已经把公交运营调度蚁群算法中的变量以及相关运算与公交运营调度模型中的变量和相关运算建立了对应关系因而，公交运营调度蚁群算法可以基本按照该蚁群算法在求解“TSP”问题的步骤来实现[4]具体实现步骤如下：Step1：参数初始化，令时间t=0和循环次数Nc=0，设置最大循环次数Nc max，首先将N只蚂蚁如数置于第一个发车时段上，令每个时段k内的备选发车间隔s上的初始化信息量τks(0)=const，其中const表示常数，且初始时刻△τks(0)=0；Step2：循环次数；Nc ← Nc+1;Step3：蚂蚁的禁忌表索引号m=1；Step4：蚂蚁数目；m←m+1Step5：蚂蚁个体根据状态转移概率pnks(t)选择时段内的备选发车间隔s，然后进入下一时段k+1进行选择，直到选择完最后一时段K；Step6：修改禁忌表指针，即选择好之后将蚂蚁移动到所选时段k内的备选发车间隔s，并把这个间隔移动到该个体的禁忌表中；Step7：若所有时段未被依次走完，即m

四、实例分析结合吴江市101路公交线路上行方向全天内的客流数据，运用蚁群算法求解该条线路的公交运营调度问题，该条线路的基本情况为：该路车为单向发车，线路总长11.9KM，全线共有13个站，公交车标准载客80人，最低满载率50%，最高满载率120%，首班车为6：00，末班车为18：00，单一客票价为1元/人．次，车辆的每公里成本费用χ=3元/km，乘客等车单位成本y=0.11元/min从首班车6：00开始以一小时为一时段，依次编号，到末班车18：00为止，全天共有12个发车时段通过反复试算得到该实例中蚁群算法最优参数组合为α=1，β=5，Q=25,ρ=0.2注：α表示信息启发式因子β表示期望启发式因子ρ表示信息素挥发因子Q 表示信息素强度，体现蚂蚁所留轨迹数量的一个常数在WIN-TC程序运行软件中运行30次后，求得线路上全天内的最优发车间隔，如下表五、结论及展望在实际的运营调度中，调度人员可以先结合经验为每个时段设定一定量的备选发车间隔，然后在调查数据的基础上，运用文中所采用的方法，生成一张全天内线路上的公交排班表，并根据客流、车流的变化进行滚动更新在具体的公交数据采集中，如果单靠人工来完成数据的采集，将是一项既庞大又烦琐的工作。

随着公交刷磁卡的普遍推广以及公交车载客流采集仪器的应用，公交客流数据的采集工作量将大为减小公交车辆在实际行驶过程中，受到其他车辆和交叉口红灯的影响，沿线行驶速度不够平稳相信随着城市道路中公交专用车道的不断开辟、交叉口公交优先通行管理措施的普遍实施，公交车辆在行驶途中所受的干扰将减小，行驶速度将会减少波动、增加平稳性，交叉口延误将降低参考文献：[1]杨建峰.蚁群算法及其应用研究[D].杭州：浙江大学博士学位论文，2007.[2]于斌.城市公交系统模型与算法研究[D].大连：大连理工大学博士学位论文，2006.[3]吴斌，史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报，2001，24(12).[4]段海滨．蚁群算法原理及其应用[M].北京：北京科学出版社，2005，24(42)：297.作者简介：王丹(1977-)，女，辽宁大连人，项目经理，工程师，从事交通规划研究；张少波(1983-)，男，山东泰安人，工程师，从事交通工程研究江苏省交通科学研究院；吴江市交通运输管理处)(责任编辑：张娟)-全文完-。