动态时隙再分配的分布式协同进化模型研究

王 湛，吴 术

(1.南京航空航天大学民航学院，南京210016;2.南京大学工程管理学院，南京210093)

1 引言

随着CDM(流量管理协同决策机制)在空中交通中的深入研究和广泛应用，协同时隙再分配管理将从集中式决策逐步过渡到分布式协同决策模式，可分为简单交易和复杂交易问题.简单交易，即“一对一”交易，指一次只允许交易一个时隙资源;复杂交易，即“多对多”的交易，可以同时交易多个时隙资源.协同时隙再次分配问题实质上就是一种资源协调交易问题，其主要个体为流管部门和航空公司，流管部门分配目标为最大化资源利用率，航空公司分配目标为最大化自身效益，相应的群体目标为在最大化资源利用的基础上，最小化总延误损失［1-3］.

DCCEA使用一种新的小生境机制、保留非劣解的档案和一种扩展操作.算法可根据决策变量的个数将问题分解，产生多个子种群，然后通过子种群的协同进化来逼近问题的全局Pareto最前端［4］.分析该算法在处理分布式动态协同优化问题上的优势及特点，将该算法应用于协同时隙再次分配中，构建基于动态时隙再分配的分布式协同多目标进化算法模型，可有效解决分布式动态环境下的CDM GDP时隙再次分配问题.

2 DCCEA模型构建

DCCEA可通过将复杂系统分解为独立进化的模块，利用一组独立进化的种群来解决问题，在模块进化过程中，存在模块的集成以还原成完整系统.在时隙再分配过程中，分配结果由内外部效用共同决定，同时内外部效用又由各自不同的效用函数决定，由此，结合上述DCCEA的特点可知构建基于时隙再次分配的DCCEA模型的可行性.

2.1 协同时隙再分配复杂交易效用分析

在时隙再分配中，AOC(航空公司运控中心)为时隙提供者和需求者，可同时取消或延误多个航班、放弃它们占用的较早时隙，其请求交易的必要条件为:能在其指定时隙区间集内获得多个可以为后面某些航班所用的较晚时隙，以消除或降低延误;同时为了获得多个较早时隙，以降低某些航班的延误［5-9］.为便于描述，定义交易相关参量如表1所示.在表1中，为配置给中m个航班的n个接受时隙;当m=n=1，为简单交易;当m，n≥2，为复杂交易;若m=n≥2，为平衡复杂交易问题;若m≠n≥2，为非平衡复杂交易问题.

表1 协同时隙再分配参量Table 1 CDM GDP slot assignment parameters

续表

启动协同复杂交易过程时，首先AOC放弃时隙时便在中介市场上注册发布交易信息表示预拍卖时隙，在内拥有时隙AOC可请求交易;然后满足条件的AOC检测自身航班集中是否存在交易链，若有，则单独出价请求，否则与其它需求者联合出价.请求交易信息为:，表示用某时隙组成的时隙集交换中的所有时隙，追加补偿金pr，由此在提供者和请求者的交易对象之间搭建“航班桥”，通过上移或下移桥梁航班实现交换;然后AOC根据设定目标，选取最佳请求者，进行效用分析，选出即时最佳者，驳回失败请求;最后交易达成，AOC间评估需求及分析系统，交换时隙和追加补偿金，更新信息、清理市场.

(1)内部优化效用分析.

内部优化决策定义为，航空公司在初次分配后，为达最佳配置，其会根据目标置换或取消航班以调整航班与时隙配置关系的行为.该行为产生的效益为内部优化效用，包括有形和无形效用，本文内部优化目标定为最小化航空公司的总延误成本损失Da，约束条件为:任一航班须配置一个晚于其预计进场时间，且引起的延误小于等于最大延误时隙;任一时隙至多分配给一个航班;为确保延误不会传播到续航航班的后续飞机，制定续航航班最大延误约束:tj-otai≤ΔTi，∀fi∈F'a;决策变量为xij，yi，内部优化效用Ua为优化前的总延误成本损失D'a减去优化后的总延误成本损失Da.

初次分配按照“先到先分配”原则，没有考虑最大延误约束，当机场进场容量下降过多时，优化可能会无解.

(2)外部优化效用分析.

2.2 模型目标函数及约束条件

(1)目标函数.

时隙再分配模型的目标函数由内外部优化效用两部分组成，构建时要求效用最优，制定目标函数如下:

(2)有效性约束条件.

时隙再分配需满足以下条件:续航航班配置最大延误约束，延误不会影响后续飞机;航班与所配置时隙一一对应，时隙晚于其预计进场时间，所引起的延误小于等于最大延误;由此有效性约束条件如下所示:

2.3 模型结构

DCCEA模型中，每个子种群优化一个参数，根据各点计算机的数量，将子种群分组至各同位机.各子种群间无直接通信，所有通信在子种群和中心服务器间进行，在每个同位机中，利用通过合作产生的候选解对档案升级，同时各子种群不断调整其代表［4］.

DCCEA在分布计算框架Paladin-DEC实现.Paladin-DEC软件由两块组成——服务区和工作区，二者通过RMI-IIOP相连.服务区作为信息中心和支持站，各个点的机器通过服务区识别身份或恢复其工作状态;工作区是各个点的机器以组为单位共同工作的地方，服务区内具有三种不同的服务器——logon服务器、调度服务器和数据库服务器，其中logon服务器为每个注册的同位机安排一个身份，当一个同位机退出并将其信息与调度服务器保持同步时，logon服务器将注销该同位机的信息和身份.调度服务器选择要执行的任务并将同位机进行分组以执行该任务.

每个同位机的具体工作过程如下:同位机首先通过发送合法E-mail地址给服务器以完成登录，然后同位机组合在一起，等待服务器分派的任务.一旦同位机监测到一个已分派任务，在从服务器中远程下载类之前，它将从服务器提取相关信息，若已下载的类与Paladin-DEC系统一致，则计算开始，工作过程如图1所示.

图1 同位机的工作过程Fig.1 The working process of apposition machine

3 仿真实验

设定某机场四家航空公司(A1、A2、A3、A4)在10:00～14:00执行CDM-GDP，航班信息及机场时隙如表1中所示.航班分为重、中、轻型三类，其单位时间延误运营成本分别为4 250元/小时、2 873元/小时和199元/小时;航班等级分为国内、国际和要客三种等级，其每名旅客的平均延误成本分别为50元/小时、100元/小时、100元/小时;补偿金支付比率ra=0.53，ΔTi=90 min，航班均价、均净利润率及飞行小时分别设定为739元、2.35%、2小时.采用RBS算法进行初次时隙分配;A1和A2分别取消A14、A16和 A24、A25，进行再分配，全局优化时令:yi=1;∀fi∈ C;yi=0，∀fi∈F/C.模型采用matlab2009编程构建，采用cell工具把整个模型程序分步.记忆库数据量为300，种群规模为300，迭代次数 300.DCCEA和Compression基于内部优化，DCCEA采用分步式仿真:(1)A2发布交易信息:［1 140］→A28［1 150，1 250］;(降低 A28的延误，交易时隙1 140，在［1 150，1 250］内拥有时隙的航空公司具有交易请求提出资格);(2)A1发布交易信息:［1 130］→A17［1 150，1 250］;(3)A1 发布交易信息:［1 120］→A18［1 200，1 300］.DCCEA 交易结果见表 2，黑体代表桥梁航班.效用分析对比如表3所示，DCCEA较Compression得到更多补偿，总交换效用有所提高，有助于提高资源利用率;同时运行显示，采用DCCEA、Comression及全局优化三种方法模型运算时间分别为 t1= 0.313 86 s，t2=0.367 85 s，t3=0.473 24 s，由此采用 DCCEA 模型运行的效率相较Compression和全局优化有了一定的提高.

表2 CDM GDP时隙分配Table 2 CDM GDP slot assignment

表3 再分配效用分析Table 3 Utility analysis generated by reassignment

4 研究结论

本文针对时隙再分配问题，提出了以效用来表示航空公司对交易的自主决策.利用DCCEA在处理分布式动态协同优化问题上的优势，将其应用于协同时隙再次分配中，构建基于动态时隙再次分配的分布式协同多目标进化算法模型.算例仿真表明，该模型能够提高航空公司的交易效用，适用于动态的分布式空管协同决策环境中.在下一步研究中，可进一步纳入实际空管因素，增强其应用价值.

［1］马正平，崔德光.机场航班延误优化模型［J］.清华大学学报(自然科学版)，2004，44(4):474-477.［MA Z P，CUI D G.Optimizing airport flight delays［J］.Journal of Tsinghua University (Science And Technology)，2004，44(4):474-477.］

［2］胡明华，钱爱东，苏兰根.基于地面等待策略的航班时刻规划方法［J］.航空学报，2001，23(3):262-264.［HU M H，QIAN A D，SU L G.Airlines time table programming method on ground holding strategy［J］.Acta Aeronautica et Astronautica Sinica，2001，23(3):262-264.］

［3］Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs［J］.Naval Research Logistics，2006，53(1):75-90.

［4］雷德明，严新平.多目标智能优化算法及其应用［M］.北京:科学出版社，2009:133-139.［LEI D M，YAN X P.Multiobjective intelligent optimization algorithm and its application［M］.Beijing Science Press，2009:133-139.］

［5］Capri S，Ignaccolo M，Genetic algorithms for solving the aircraft-sequencing problem: the introduction of departures into the dynamic model［J］.Journal of Air Transport Management，2004，10(5):345-351.

［6］Vossen T，Ball M.Optimization and mediated bartering models for ground delay programs ［J］.Naval Research Logistics，2006，53(1):75-90.

［7］余江，王大海，浦云.终端区起飞着陆的协同优化［J］. 系统工程学报，2003，18(5):462-465.［YU J，WANG D H，PU Y.Coordinated optimization of terminal area landingand takeoff［J］.JournalofSystems Engineering，2003，18(5):462-465.］

［8］张洪海，胡明华.协同地面机场延误时隙MAS动态协调交易［J］. 系统工程学报，2010，25(3):394-400.［ZHANG H H，HU M H.Dynamic coordination trading slot MAS-based in collaborative ground delay airport［J］.Journal of Systems Engineering，2010，25(3):394-400.］

［9］张洪海.机场终端区协同流量管理关键技术研究［D］.南京航空航天大学，2009.［ZHANG H H.The key technologies of collaborative flow management in airportterminalarea［J］. Nanjing University of Aeronautics and Astronautics，2009.］