基于NSGA算法的公交车辆调度优化模型

优先发展城市公共交通是提高交通资源利用效率、缓解交通拥堵的重要手段.作为城市交通的主要通行方式,公共交通服务水平与居民出行需求和城市交通运行状态息息相关.优化发车间隔是公交调度的主要技术手段.准确和高效率的发车调度对提高公交线路的服务能力,减少居民的出行延误,提高乘客满意度有着重要意义.Huisman等[1]提出了用于描述多场站调度问题的动态模型,并应用“聚类再生成”启发式算法,基于数学规划模型得出优化的结果,但对公交车容量未作考虑.孙芙灵[2]根据乘客需求来确定发车间隔,用数学规划的思想建立调度模型,并用时间步长法、等效法进行求解,得出仿真结果,但对公交公司利益考虑不足.陈芳[3]根据客流变化规律,对发车间隔采用多时段处理思想,建立了以乘客与公交企业运营费用最小为目标的公交车辆调度模型,对于信号控制的干扰没有进行考虑.刘志刚等[4]根据区域公交调度模型,把公交车容量作为理想状态,不受信号控制的干扰,建立了公交调度系统双层规划模型.本文综合考虑乘客与公交公司利益,并基于极小极大思想,考虑公交车车辆容量的限制及城市道路信号控制的干扰因素,建立公交发车间隔优化模型,并利用非支配排序遗传算法(NSGA)进行模型的求解. 1 优化模型的建立 1.1 模型假设

公交车辆的运营受很多因素的影响,本文为建立公交调度优化模型作出以下假设:

a.线路上的公交车辆为同一型号,公交车会按照调度表准时到站和出站;

b.全程票价统一;

c.公交车辆行驶过程中不存在阻塞现象及突发情况,且公交车之间依次行进,不存在超车及越站现象;

d.各站点乘客上下车的时间、公交车在各站点的停留时间均被考虑在公交车的平均速度之内;

e.仅考虑沿线信号延误干扰,沿线交叉口具有相同的信号延误;

f.各交叉口有足够大的通行能力,仅考虑单行方向公交车运行. 1.2 模型的构建

公交车运行调度模型的建立是一个复杂过程,根据极小极大思想,为使服从相同规律的受控群体的性能指标在总体上最小,其充分条件就是使群体中性能指标值最大的个体值最小.作为乘客希望获得便捷、舒适、车辆间隔小、等待时间短的公交服务,这样势必造成空驶率过高,公交公司的利益得不到保证而影响其服务质量.而公交公司希望发车间隔增大,发车次数少且载客量大,以获取更大利益,这与乘客的需求相违背.因此,综合考虑公交公司与乘客的利益,使乘客最大广义费用最小及公交公司最大广义费用最小.

在时间T内出行者的广义费用为

关于乘客等车时间有

对于某一站点,记W(t)为t时刻在节点等待的乘客数量.等待的乘客包含在下一辆车到达之前陆续来到站点作等待的乘客及在上一运次滞留的乘客.t时刻为某一公交车进站时刻.并且设定公交车的容量为C,则在该站点乘客上车的数量为P(t).

对于滞留的乘客,需要等待下一运次才能乘上公交车,假定不存在3次等车,而保证一定的服务标准,对于滞留的乘客需要再次等待一个ti时间才能上车.若对于上一时刻存在乘客滞留,则滞留人数为D(t-ti).

由于公交车按照行车时刻表运营,因此,乘客到达公交站点会产生等车时间.根据Bowman等[5]提出的等车时间模型,乘客期望等待时间的均值为

如果排除外界干扰,公交车平均车头时距应与发车间隔相等.由于公交车运行受交叉口信号控制的干扰,车头时距发生波动,则平均车头时距为

出行者等待时间

由于乘客在车时间只与路段的不同而不同,因此定义在车时间费用是只与路段相关的常数.对于惩罚费用同样与发车频率无关,取决于路段,同样可以作为常数处理[7].对于在车时间费用与惩罚费用相应权重可以通过实际调查统计得到[8].在时间T内,相应公交车运营的广义费用为

其中固定费用主要包含公交车的保养维修费用、公交公司的管理费用及员工工资[9],在T时段内可得到的相应固定费用为

在T时段内运营了N辆车,则

所有车辆行驶里程

公交车辆的运行势必受到红绿灯的干扰而影响正常运营,为保障公交车服务标准,相邻运行中的公交车车头时距因交叉口信号干扰需保持在一个发车间隔内.公交车遇到交叉口引起的延误是随机的[10],因而根据Miller提出的随机延误理论得到

公交车遇到交叉口引起的总的延误满足如下约束

基于公交公司与出行者综合广义费用最小,公交车发车间隔与信号控制之间存在相互影响,交通信号控制影响着车头时距的波动程度,约束发车间隔的确定.发车间隔的合理性又反映了信号控制的优化程度,信号控制得以优化可减少公交车运行时由于交叉口的干扰引起的延误,提高通行能力.根据以上分析,建立如下公交车运行调度模型

对于公共交通,当交通需求增加时,提高发车频率,可使乘客的等车时间减少[11].为保证优化结果较优,相邻运行公交车不发生超车或前后相接的现象. 2 模型的求解

乘客广义费用和公交公司的广义费用这些目标并不是彼此独立,二者耦合在一起,互为矛盾,互为竞争.某子目标的改善可能引起其它子目标性能的改变,而同时使所有子目标达到最优往往是不可能的.要找到这些目标的最佳设计方案,就要解决多目标与多约束的优化问题,即多目标优化[12].对于模型的求解引进NSGA.

可以定义为在一组约束条件下,极小化这两个目标函数[13],令[C(f)]max=u1(X),[B(f)]max=u2(X),形式如下:

NSGA是基于对个体的几层分级实现的.在选择执行前,群体根据支配与非支配关系来排序,所有非支配个体被排成一类,这些被分级的个体共享它们的虚拟适应度值.然后忽略这组已分级的个体,对种群中的其它个体按照支配与非支配关系再进行分级,该过程继续直到群体中的所有个体被分级.在NSGA中对每个局部的Pareto曲面(线)上的所有个体分别采用适应度共享策略,有利于保持群体多样性,可以克服超级个体的多度繁殖,防止早熟收敛.根据关志华[14]对于非支配排序遗传算法算子分析,参数选取分别为:交叉概率取0.8;共享半径取0.05;变异概率取0.00.算法流程如图 1[13]所示.

由式(9)知乘客的平均等待时间与发车间隔具有一定的关联性.此外,董强等[15]对公交车调度问题研究表明发车间隔与公交车的满载率相关.由于车次与发车时刻一一对应,而车辆的队列顺序不发生改变,因而对所需车辆进行统一标号后,则每一车次与其对应的车辆编号是确定的.直接对第k次车进行考察,公交车全日平均满载率为

选取河南省焦作市具有代表意义的5条公交线路,如图 2所示,分别为21路、9路、13路、17路、14路.乘客平均等待时间能够直观地反映乘客的出行利益,公交车辆全日平均满载率能够衡量车辆的利用程度,反映了公交公司的利益.因此,以乘客平均等待时间和全日平均满载率作为评价指标,进行相关的调查分析.经实地调查,上述模型相关参数选取如表 1所示.

在实际调查中,线路21路、9路由于客流量较大,满载率较高,对乘客来说舒适性下降,不利于乘客利益;线路17路、14路,乘客等待时间太长,吸引客流较弱,不利于乘客利益,满载率过低,车辆利用程度较低,影响公交公司利益.对于满载率,各个城市都没有形成统一的规范值.按照焦作市城市公交行业管理规范规定,为保持车辆利用程度,全日线路平均满载率控制在60%~100%.线路13路满载率维持在合理水平,乘客等待时间稍长,可适当调节,维持乘客利益.通过Matlab对上述算法进行实现,利用模型对21路、9路、13路、17路、14路公交线路发车间隔进行优化,优化结果以乘客平均等待时间和公交车平均满载率为衡量指标,如图 3与图 4所示.

根据本研究的优化结果,各线路乘客平均等待时间及对应的全日平均满载率不仅满足焦作市城市公交行业管理规范中的规定,且各线路总的平均满载率减少了3.8%,舒适度增加,吸引了客流,保证了公交公司的相应利益.同时,乘客平均等车时间相对于现状平均等待时间减少48.3%,满足乘客的利益. 4 总 结

兼顾公交公司与出行者的利益愿景,根据极小极大思想对公交车发车间隔进行了优化.运用非支配排序遗传算法解决此类多目标问题,并获得最优解组合集合,在集合中找到最优解,规避了同时使所有子目标均达到最优的不实际现象.充分考虑了公交车容量限制产生的乘客滞留状况和交叉口信号控制对公交车运行的影响.通过对发车间隔的优化,不仅能满足客流需求,同时规避了公交资源的浪费,具有现实适用性.