Feedback controller design and algorithm of freeway system
-
摘要: 为了提高快速路系统的利用效率, 设计了一个反馈控制器, 提出了反馈控制器的迭代求解算法, 控制器能实时跟踪车辆的密度, 并与所期望的密度进行比较, 把误差反馈给车辆, 通过给车辆发布恰当的速度命令来控制车辆运行, 使实际车辆密度收敛于期望密度。仿真计算结果表明: 算法取4次迭代时的车辆密度与运行速度最大相对误差为0.32%, 平均耗时为0.32 s, 因此, 设计的控制器使交通流运行趋于平稳, 减少了车辆延误, 从而提高了系统利用效率。Abstract: In order to improve the using efficiency of freeway system, a feedback controller was designed and its iterative algorithm was proposed, the controller could track vehicles' real-time densities and compare them with the anticipant density, then it sent the errors to the vehicles, and guaranteed the convergence of the real vehicle density to the anticipant density under appropriate speed command followed by vehicles.Simulation result indicates that the maximum relative error of vehicles' densities and travel speeds is 0.32%, and the average time consumption is 0.32 s after the fourth iteration of the algorithm, so the controller guarantees the smooth and stable traffic flow, reduces the vehicle's delay and increases the efficiency of the system.
-
0. 引言
航班延误已成为困扰各航空公司和广大旅客的世界性难题, 因此, 一些研究人员开始探讨解决航班延误的方法, 以改善空中交通管理现状。马正平等给出了一种机场航班延误优化模型, 将机场的到达和出发视为密切相关的两个过程, 对几个小时内可能的延误进行预测、分析和处理[1]。徐肖豪等研究了遗传算法在终端区跑道分配以及飞机排序中的应用, 建立了多条跑道多架飞机排序的数学模型, 以减少延迟时间[2]。航班延误快速恢复是一个复杂的综合调度过程, 目前, 国际、国内航班延误快速恢复在理论方法与实际应用上均没有很好地解决办法。粒子群算法简单易实现, 鲁棒性好, 可并行计算, 已经成功地用于解决旅行商问题[3]、作业车间调度问题[4-6]、交通量多路径分配问题[7]和综合运输通道客运结构配置[8]等复杂问题, 在优化航班延误恢复调度时也具有极大的潜力。本文从航班延误的经济效益和社会影响出发, 尝试将混合粒子群算法用于优化航班延误恢复调度过程中。
1. 航班延误经济损失的构成
航班延误经济损失通常包括显性损失和隐性损失两部分[9], 见图 1。
1.1 航班延误的显性损失
本文假定显性损失与航班的延误时间成线性关系。
1.1.1 航空公司经济损失
(1) 延误航班的运营成本
延误航班的运营成本与延误航班的机型有着直接联系, 起飞质量越大的飞机, 其停场费、起降费、旅客服务费等就越高, 相应的地面等待成本也就越高。本文根据国际民航组织(ICAO) 的标准, 按照飞机的尾流强弱将飞机分为3类分别讨论运营成本, 见表 1。以中型飞机波音737-300为例, 据计算, 一架飞机每年花费的租赁费、税金、停场费、飞机维护费用和相应的航材费用等固定性费用为2 500万元, 按1 a有365 d计算, 1 d的成本约为7万元。为了方便分析, 本文假设重型机、中型机和轻型机延误的运营成本分别为10、7万元·d-1和5 000元·d-1, 按1 d有24 h计, 各机型每小时延误运营成本α0的值见表 1。
表 1 各类飞机每小时延误运营成本Table 1. α0 of different aircrafts机型 代表符号 最大起飞质量/t 尾流类型 α0/ (元·h-1) 重型机 H > 136 重型尾流 4 167 中型机 M 7~136 (含) 中型尾流 2 916 轻型机 L ≤7 轻型尾流 208 对于不同的机型, 其延误运营成本C0 (t) 为
C0(t)=α0t (1)
式中: t为延误时间。
(2) 延误航班的盈利损失
航空器作为航空公司的主要生产工具, 其目的除了要为旅客提供优质的服务外还要为航空公司创造利润, 因此, 当航班发生延误时, 航空公司的盈利也会受到直接的影响, 造成航空公司的经济损失。延误航班的盈利损失与航班最大载客人数、航班客座率和航空公司的净利润率密切相关。
根据2005年英国《商业航空》[10]的统计可得出中国航空公司的平均净利润率r约为2.98%。从中国实际情况出发, 假设航班客座率s为75%, 平均票价a为750元, 平均飞行时间f为2 h, 因此, 令m表示航班最大载客人数, 则各航空器每小时可为航空公司赚取的利润αn为
αn=msar/f (2)
延误航班的盈利损失Cn (t) 为
Cn(t)=αnt (3)
1.1.2 旅客经济损失
航班延误造成的旅客经济损失与飞行的等级相关。国外相关机构就航班延误对旅客造成的经济损失做过较为系统的分析(表 2), 得到旅客的平均时间价值为28.6 $·h-1, 其中最低时间价值为23.8 $·h-1, 最高时间价值为35.6 $·h-1。
表 2 国外旅客延误时间价值Table 2. Delay time values of foreign passengers$·h-1 旅客类型 平均时间价值 最低时间价值 最高时间价值 休闲旅客 23.3 20.0 30.0 商务旅客 40.1 32.1 48.1 根据国外旅客延误时间价值并结合中国飞行的分类, 中国民航运输中对于普通国内航班飞行每名旅客平均延误经济损失约为50元·h-1, 对于国际航班和重要客人的飞行每名旅客平均延误经济损失约为100元·h-1。
航班延误造成的旅客经济损失Cp (t) 为
Cp(t)=αpsmt (4)
式中: αp为航班单位时间每名旅客的平均延误经济损失。
1.2 航班延误的隐性损失
航班延误除了会造成有形的显性损失之外, 还会导致无形的隐性损失, 如航班延误对航空公司形象和声誉的损害。航班不正常使航空公司在旅客面前失去诚信, 也是导致高价值商务旅客流失的最主要原因。再如, 航班延误还会造成很多间接的经济损失, 很多商务谈判或交易不得不因为航班的延误而延期或取消, 很多旅行社不得不处理并非缘于自身责任的投诉、索赔等。由于这些隐性损失的不确定性, 因此, 本文在计算航班延误经济损失的时候并没有考虑这些隐性损失。
1.3 航班延误的总延误经济损失
为了便于对航班延误造成的经济损失进行定量的分析, 本文在计算航班延误经济损失的时候并未考虑航班延误的隐性损失。在计算航班延误经济损失时, 航线对于恢复调度的影响也是不容忽视的, 航线密度大, 恢复调度时就应该优先考虑。对于首都机场, 所有航线对应的目的机场总数为99个, 其中, 密度大的航线的目的机场主要集中在上海虹桥机场、广州白云机场、上海浦东机场、深圳宝安机场、大连周水子机场、成都双流机场和昆明巫家坝机场, 而其他92个机场的航线密度相对小一些。通过对首都机场的航班数据进行分析, 本文定义了航线影响因子来衡量航线所对应的目的机场的重要性。机场和航线影响因子的对应关系见表 3。
表 3 各机场所对应的航线影响因子Table 3. Airline impact factors of airports机场名称 航线影响因子 上海虹桥机场 0.103 广州白云机场 0.059 上海浦东机场 0.049 深圳宝安机场 0.040 大连周水子机场 0.038 成都双流机场 0.041 昆明巫家坝机场 0.024 其他机场 0.007 航班延误造成的总延误经济损失C (t) 为
C(t)=(1+χ)[C0(t)+Cn(t)+Cp(t)] (5)
式中: χ为航班的目的机场所对应的航线影响因子。
2. 航班延误恢复调度模型
航班延误恢复调度(recovery scheduling of flight delays, RSFD) 是指由于某些原因造成了大面积的航班不能正常起飞, 当延误恢复时, 要重新调度这些延误了的航班。调度的任务是给出一种航班调度方案, 使所有延误了的航班在尽可能短的时间内起飞, 并使得延误造成的经济损失尽可能小。
对于延误航班序列F1、F2、…、FN, 设T1、T2、…、TN为航班的计划起飞时刻, Rt为航班延误恢复时刻, t1、t2、…、tN为航班的延误时间(由实际起飞时刻和计划起飞时刻决定), 实际起飞时刻由航班延误恢复时刻Rt和航班延误恢复调度方案决定; M1、M2、…、MN为航班的尾流类型, 航班的运营成本由飞机的尾流类型决定; A1、A2、…、AN为航班的目的机场, 航线影响因子由目的机场决定。本文所研究的航班全为国内航班, 旅客平均延误经济损失按照国内航班的标准进行计算, P1、P2、…、PN为对应航班的最大载客人数, 航班的盈利损失和旅客的经济损失都和航班的最大载客人数相关。
以前面提出的航班延误经济损失构成为基础, 航班延误恢复调度模型建立为
minF=minΝ∑j=1C(tj)=minΝ∑j=1(1+χj)⋅[C0(tj)+Cn(tj)+Cp(tj)] (6)
式中: F为所有航班的总延误经济损失; N为延误航班总数; C (tj) 为航班Fj的总延误经济损失; χj为航班Fj的目的机场所对应的航线影响因子; C0 (tj)、Cn (tj)、Cp (tj) 分别为航班Fj的运营成本、盈利损失与旅客经济损失。
目前, 解决RSFD主要采用的是顺延的办法, 等同于先来先服务(FCFS) 策略, 其思路为延误恢复时按照各航班原来的起飞顺序调度航班, 该法虽然简单, 但没有考虑航班、航空公司和旅客的各种因素, 因此, 往往不能令人满意。本文尝试采用混合粒子群算法(HPSOA) 来求解该问题。
3. 混合粒子群算法优化航班延误恢复调度
3.1 基本粒子群算法
粒子群算法(PSOA) 是由Kennedy和Eberhart于1995年提出的一种基于迭代的进化计算算法。算法中, 数量为Pc的粒子构成了粒子群。在每一次迭代中, 所有的粒子通过追随当前的最好极值在D维空间中“移动”, 以搜索全局最优解。粒子的速度向量和位置向量由以下更新公式确定
V k+1i =V ki +c1r1 (P ki -X ki) +c2r2 (Pgk-X ki) (7)
X k+1i =X ki +V k+1i (8)
式中: i为粒子的序号; k为迭代次数; Vi为第i个粒子的速度向量; Xi为第i个粒子的位置向量; c1和c2为学习因子, 通常取c1=c2=2.0;Pi为第i个粒子迄今为止搜索到的个体极值点向量; Pg为整个粒子群迄今为止搜索到的全局极值点向量; r1、r2分别为2个独立的介于[0, 1]之间的随机数。
3.2 位置和速度的表示
所有延误了的航班按照航班时刻表中的顺序设置标号分别为1、2、3、…、N。位置向量表示为问题的一个解序列, 即
X=(a1,a2,⋯,al,⋯,aΝ)
式中: al为第l个要调度的航班标号。速度向量可表示为位置向量的交换序[4], 交换序的作用是通过交换位置向量的元素来得到新的位置向量。引入交换序后, 基本粒子群算法的更新公式为
V k+1i =V ki ♁α (P ki -X ki) ♁β (Pgk-X ki) (9)
X k+1i =X ki +V k+1i (10)
式中: ⊕表示交换序的合并运算; 符号+具有新的含义, 表示将交换序作用到位置向量上; α、β分别为介于[0, 1]之间的随机数。
3.3 算法步骤描述
为了提高粒子群算法的搜索效率, 本文将局部搜索方法引入到粒子群算法中。采用的局部搜索方法为: 对于每个粒子随机多次交换位置向量的2个元素, 如果交换后的位置向量的适应值好于粒子的当前个体极值点的适应值, 则更新当前个体极值点。在局部搜索完成以后, 由所有粒子的当前个体极值点更新当前全局极值点。综上所述, HPSOA的算法步骤描述如下。
步骤1:设定粒子的总数Pc和最大迭代次数kmax, 给每个粒子赋一个随机的初始解和一个随机的交换序, 并初始化Pi和Pg。
步骤2:对每个粒子的位置向量进行多次交换, 如果交换后的位置向量的适应值好于粒子的当前个体极值点的适应值, 更新粒子的当前个体极值点向量Pi。
步骤3:如果某个粒子的个体极值点的适应值比当前的全局极值点的适应值好, 则用此个体极值点更新当前Pg。
步骤4:如果当前迭代次数等于kmax, 转步骤6。
步骤5:对于每个粒子, 根据式(9)、(10) 计算新的速度和位置, 及新位置的适应值, 如果其比粒子的当前个体极值点的适应值好, 则用新的位置更新当前个体极值点, 转步骤2。
步骤6:输出求得的最优解及其适应值。
HPSOA的算法流程见图 2。
4. 仿真结果分析
首都机场的航班数据见表 4, 本文采用HPSOA进行仿真, 算法参数设置如下: Pc为30, kmax为50, Rt为10∶20∶00。为了调度的快速和安全, 航班调度的时间间隔设置为2 min, 局部搜索中的交换次数为4。
表 4 航班数据Table 4. Scheduled flight data航班号 机型 计划起飞时刻 目的机场 最大载客人数 1 H 8∶00∶00 上海虹桥机场 420 2 H 8∶05∶00 上海虹桥机场 440 3 M 8∶10∶00 海口美兰机场 138 4 M 8∶10∶00 西安咸阳机场 189 5 M 8∶15∶00 海口美兰机场 189 6 M 8∶15∶00 兰州中川机场 189 7 M 8∶20∶00 昆明巫家坝机场 162 8 H 8∶25∶00 西安咸阳机场 440 9 M 8∶30∶00 福州长乐机场 189 10 H 8∶30∶00 上海虹桥机场 335 38 M 10∶00∶00 上海虹桥机场 180 39 M 10∶05∶00 广州白云机场 180 40 M 10∶05∶00 杭州萧山机场 189 41 H 10∶10∶00 大连周水子机场 290 42 M 10∶15∶00 广州白云机场 180 根据表 4中的数据, FCFS策略和HPSOA的排序结果见表 5。HPSOA结果比FCFS策略节约了53 650元, 延误经济损失减少4.2%, 因此, 按照HPSOA的排序结果调度航班, 可以更有效地减少延误经济损失。
表 5 HPSOA和FCFS策略的排序Table 5. Sequencings of HPSOA and FCFS strategy
为了比较算法, 本文采用单一PSOA和进化策略(ES) 算法, 来优化航班延误恢复调度。其中, ES算法采用(μ, λ) 策略, 策略系数μ、λ分别为30、50, 采用基于航班号的编码方式, 重组操作采用次序杂交算子。突变算子采用扩展“倒位”操作的方法, 个体突变采用2点位置外侧子串交换的方法, 即在进行突变的个体中, 随机选择2点位置, 并将此2点位置外侧的子串进行交换, 从而得到新的个体。
本文设定PSOA的参数和HPSOA的相同, ES的最大迭代次数也为50次。在Pentium 4、2.26 GHz、256 MB的计算机上, 利用HPSOA、PSOA和ES分别连续优化10次得到的结果见表 6~8。从表 6~8可以看出, HPSOA的最好结果为1 224 727元, 最差结果为1 236 867元, PSOA的最好结果为1 249 071元, ES的最好结果为1 248 396元, HPSOA连续10次计算的优化结果都明显比PSOA和ES的优化结果好, 而且HPSOA的最差结果比PSOA和ES的最好结果要好, HPSOA求解RSFD的寻优能力比PSOA和ES要强。由于HPSOA采用了局部搜索方法, 在计算时间方面比另2种算法要长, 但这些时间是可以接受的。HPSOA的最好结果比PSOA节约了24 344元, 比ES节约了23 669元, HPSOA比PSOA、ES平均减少损失2.0%左右, HPSOA所花费的时间是值得的。
表 6 HPSOA优化结果Table 6. Optimization results of HPSOA优化次数 总经济损失/元 计算时间/s 1 1 231 251 221 2 1 235 379 222 3 1 224 727 261 4 1 231 018 196 5 1 235 816 254 6 1 236 313 133 7 1 227 700 231 8 1 236 849 252 9 1 232 421 148 10 1 236 867 251 表 7 PSOA优化结果Table 7. Optimization results of PSOA优化次数 总经济损失/元 计算时间/s 1 1 250 798 48 2 1 254 921 48 3 1 255 222 38 4 1 249 071 39 5 1 258 400 46 6 1 249 601 20 7 1 254 439 37 8 1 254 224 42 9 1 253 272 52 10 1 258 059 32 表 8 ES优化结果Table 8. Optimization results of ES优化次数 总经济损失/元 计算时间/s 1 1 254 392 61 2 1 251 608 34 3 1 256 148 76 4 1 252 655 79 5 1 259 735 43 6 1 253 079 73 7 1 251 740 82 8 1 249 876 55 9 1 253 875 68 10 1 248 396 54 HPSOA、PSOA和ES求得最好结果时的收敛过程见图 3。从图 3可以看出, HPSOA算法使整个粒子群快速地向最优结果靠近, 在种群的整体寻优性能上优于其他2种算法。HPSOA采用了局部搜索方法, 能够有效地跳出局部最优, 从而找到更优的结果, HPSOA和PSOA的收敛过程比较可以证明这一点。
5. 结语
本文围绕混合粒子群算法在航班延误恢复调度中的应用进行了研究。为了使航班延误恢复调度更加合理, 目标函数设计综合考虑了航班延误的经济效益和社会影响, 把航班延误的经济损失成本分为显性成本和隐性成本, 尤其在很难确定的航班延误隐性航线损失上, 参考了航线价值及航线航班数量定义了航线影响因子, 从而构建了一种新的航班延误恢复调度模型。为提高算法的求解精度, 将局部搜索方法引入到粒子群算法中, 提出了求解航班延误恢复调度问题的混合粒子群算法。并针对首都机场的某时段离港航班数据进行了仿真试验, 结果表明, 混合粒子群算法与目前使用的FCFS调度方法相比, 可以减少航班延误损失, 而与基本粒子群算法、进化策略2种算法对比, 混合粒子群算法求解精度上优于其他2种算法, 并且随着航班延误恢复规模的增加, 算法优势会更明显。
航班延误的恢复调度是一个综合的复杂系统, 怎样设置航线影响因子, 衡量和评估航班延误的经济损失, 有待进一步研究。本文重点考虑了离港延误的情况, 而与其相对的到港延误以及相关的飞机、机组、地面服务、空中流量等综合因素的分析, 也是值得未来深入研究的。
-
表 1 初始速度和密度
Table 1. Initial speeds and densities
路段 1 2 3 4 5 6 7 8 速度/(km·h-1) 81 81 29 29 81 81 81 81 密度/(veh·km-1) 18 18 52 52 18 18 18 18 
下载: 导出CSV
表 2 模型参数
Table 2. Model parameters
α l m τ κ υ T vf ρjam cξ cζ ρdi 0.95 1.86 4.05 20 40 60 10 110 110 0.85 0.85 25
下载: 导出CSV
-
[1] PAPAGEORGIOU M, KOTSI ALOS A. Freeway ramp metering: an overview[J]. IEEE Transactions on Intelligent Transportation Systems, 2002, 3(4): 271-281. doi: 10.1109/TITS.2002.806803 [2] KOTSI ALOS A, PAPAGEORGIOU M, MANGEAS M, et al. Coordinated and integrated control of motorway net-works via non-linear optimal control[J]. Transportation Research Part C, 2002, 10: 65-84. doi: 10.1016/S0968-090X(01)00005-5 [3] ZHANG H M, RECKER W W. On optimal freeway rampcontrol policies for congested traffic corridors[J]. Transportation Research Part B, 1999, 33: 417-436. doi: 10.1016/S0191-2615(98)00045-9 [4] 李志纯, 谷强, 史峰. 弹性需求下拥挤道路收费的模型与算法研究[J]. 交通运输工程学报, 2001, 1(3): 81-85. http://transport.chd.edu.cn/article/id/200103020LI Zhi-chun, GU Qiang, SHI Feng. Toll model and algorithm of roadjammed with traffic based on elastic demand[J]. Journalof Traffic and Transportation Engineering, 2001, 1(3): 81-85. (in Chinese) http://transport.chd.edu.cn/article/id/200103020 [5] 史峰, 李志纯. 拥挤道路使用收费的理论构架[J]. 交通运输工程学报, 2002, 2(2): 78-82. http://transport.chd.edu.cn/article/id/200202019SHI Feng, LI Zhi-chun. Theoretic framework and development on research of congested road-use pricing[J]. Journal of Traffic and Transportation Engineering, 2002, 2(2): 78-82. (in Chinese) http://transport.chd.edu.cn/article/id/200202019 [6] CHIEN C C, ZHANG Y, IOANNOU P A. Traffic density control for automated highway systems[J]. Automatica, 1997, 33(7): 1273-1285. [7] PAYNE H J. Models of freeway traffic and control[J]. Mathematical Models of Public Systems, 1971, 1: 51-61. [8] KOHAN R R. Robust state estimation and control of highway traffic systems[D]. Toronto: University of Toronto, 2001. [9] PAPAGEORGIOU M, BLOSSEVILLE J M, HADJ-SALEM H. Modelling and real time control of traffic flow on the southern part of boulevard periherique in Paris[J]. Transportation Research Part A, 1990, 24: 345-359. [10] WANG Y, PAPAGEORGIOU M, MESSMER A. A realtime freeway network traffic surveillance tool[J]. IEEE Transactions on Control Systems Technology, 2006, 14(1): 18-32. -
下载:
点击查看大图
计量
- 文章访问数: 328
- HTML全文浏览量: 143
- PDF下载量: 226
- 被引次数: 0
