机场航班航线调度优化管理仿真研究

第３５卷第７期　文章编号：１００６—９３４８（２０１８）０７—００５４—０５　计算机仿真　２０１８年７月　机场航班航线调度优化管理仿真研究　于　焯，樊　玮　（中国民航大学计算机科学与技术学院，天津３００３００）　摘要：飞机航线调度是航空公司组织生产计划活动的关键环节，由于问题的复杂性，是民航界著名的ＮＰ难题，合理的航线调　度保障航空公司的经济效益。针对机场航班航线调度优化做出研究，首先将飞机航线调配问题进行数学建模，通过引入满　足限制条件的有向无环图来定义等图，证明飞机航线调配问题与等图的路径查找问题是等价的，等图的路径查找问题即为　满足特定限制条件的图的路径划分问题。随后将飞机的维护限制条件附加到等图中构造出网络状态图，根据对网络状态图　的路径划分问题得到飞机航线调配问题的可行解。提出基于网络状态图的线性规划模型，设计成本最小化和飞机使用均衡　求解目标函数，提出了不同于列生成方法的基于网络状态图的线性规划求解方法。使用国内某航空公司真实航班数据对提　出的方法模型进行了仿真研究。仿真结果表明该方法能够得到经济合理的飞机调度方案，能够为航空公司提供决策支持。　关键词：航线调配；飞机排班；路径划分；网络状态图；线性规划　中图分类号：ＴＰ３９１．９　文献标识码：Ｂ　Ｒｅｓｅａｒｃｈ　ｏｎ　Ｓｉｍｕｌａｔｉｏｎ　ｏｆ　Ａｉｒｐｏｒｔ　Ｆｌｉｇｈｔ　Ｓｃｈｅｄｕｌｉｎｇ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｍａｎａｇｅｍｅｎｔ　ＹＵ　Ｚｈｕｏ．ＦＡＮ　Ｗｅｉ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｃｉｖｉｌ　Ａｖｉａｔｉｏｎ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｃｈｉｎａ，Ｔｉａｎｊｉｎ　３００３００，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｋｅｙ　ｆａｃｔｏｒｓ　ｔｈａｔ　ａｆｆｅｃｔ　ｔｈｅ　ｏｐｅｒａｔｉｏｎ　ｅｆｉｃｉｆｅｎｃｙ　ｏｆ　ａｉｒｌｉｎｅ　ｃｏｍｐａ—　ｎｉｅｓ．Ｉｔ　ｉｓ　ｏｆｔｅｎ　ｒｅｆｅｒｒｅｄ　ｔｏ　ｂｅ　ａ　ｆａｍｏｕｓ　ＮＰ－ｃｏｍｐｌｅｔｅ　ｐｒｏｂｌｅｍ　ｉｎ　ｃｉｖｉｌ　ａｖｉａｔｉｏｎ．Ｒｅａｓｏｎａｂｌｅ　ｆｌｉｇｈｔ　ｓｃｈｅｄｕｌｉｎｇ　ｐｌａｎｓ　ｅｎｓｕｒｅ　ｔｈｅ　ｅｃｏｎｏｍｉｃ　ｂｅｎｅｆｉｔｓ　ｏｆ　ａｉｒｌｉｎｅｓ．Ｆｉｒｓｔｌｙ，ｔｈｅ　ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｗａｓ　ｅｘｐｒｅｓｓｅｄ　ｉｎ　ｍａｔｈｅｍａｔｉｃａｌ　ｌａｎ—　ｇｕａｇｅ，ａｎ　ｅｑｕｉｇｒａｐｈ　ｗａｓ　ｄｅｆｉｎｅｄ　ｕｓｉｎｇ　ｔｈｅ　ｄｉｒｅｃｔｅｄ　ａｃｙｃｌｉｃ　ｇｒａｐｈ　ｓａｔｉｓｆｙｉｎｇ　ｓｅｖｅｒａｌ　ｃｏｎｓｔｒａｉｎｔｓ．Ｉｔ　ｗａｓ　ｐｒｏｖｅｄ　ｔｈａｔ　ｔｈｅ　ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｉｓ　ｅｑｕｉｖａｌｅｎｔ　ｔｏ　ａｎ　ｅｑｕｉｇｒａｐｈ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ．Ｅｑｕｉｇｒａｐｈ　ｍｕｔｉｎｇ　ｐｒｏｂｌｅｍ　ｉｓ　ａ　ｐａｔｈ　ｐａｒｔｉｔｉｏｎ　ｐｒｏｂｌｅｍ　ｏｎ　ａ　ｇｒａｐｈ　ｗｉｔｈ　ａｄｄｉｔｉｏｎａｌ　ｃｏｎｓｔｒａｉｎｔｓ．Ｔｈｅｎ　ｔｈｅ　ｓｔａｔｅ　ｇｒａｐｈ　ｗａｓ　ｂｕｉｌｔ　ａｎｄ　ａｐｐｌｉｅｄ　ｔｏ　ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ．　Ｆｉｎａｌｌｙ，ａ　ｎｅｗ　ｃｏｍｐａｃｔ　ｉｎｔｅｇｅｒ　ｌｉｎｅａｒ　ｆｏｒｍｕｌａｔｉｏｎ　ｆｏｒ　ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ｗａｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅｎ，ｔｈｅ　ｇｏａｌ　ｏｆ　ｕｓｉｎｇ　ｂａｌａｎｃｅｄ　ａｎｄ　ｃｏｓｔ　ｍｉｎｉｍｉｚａｔｉｏｎ　ｗａｓ　ｄｅｓｉｇｎｅｄ，ｗｈｉｃｈ　ｉｓ　ｄｉｆｆｅｒｅｎｔ　ｆｒｏｍ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｃｏｌｕｍｎ　ｇｅｎｅｒａｔｉｏｎ　ｍｅｔｈｏｄ，ａｎｄ　ｔｈｅ　ｓｉｍｕｌａ—　ｔｉｏｎ　ｗａｓ　ｖｅｒｉｉｆｅｄ　ｂｙ　ｆｉｅｌｄ　ｄａｔａ　ｆｒｏｍ　ｏｎｅ　ａｉｒｌｉｎｅ　ｔｒｕｎｋ　ｆｌｉｇｈｔ　ｎｅｔｗｏｒｋ　ｉｎ　ｃｈｉｎａ．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｍｅｔｈｏｄ　ｉｓ　ｆｅａｓｉｂｌｅ　ａｎｄ　ｃａｌｌ　ｐｒｏｖｉｄｅ　ｄｅｃｉｓｉｏｎ　ｓｕｐｐｏｒｔ　ｆｏｒ　ａｉｄｉｎｅｓ．　ＫＥＹＷＯＲＤＳ：Ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ；Ｆｌｅｅｔ　ａｓｓｉｎｍｅｎｔ；Ｐａｔｈ　ｐａｒｔｉｇｔｉｏｎ；Ｎｅｔｗｏｒｋ　ｓｔａｔｅ　ｇｒａｐｈ；Ｌｉｎｅａｒ　ｐｒｏｇｒａｍｍｉｎｇ　ｌ　引言　航班计划是航空公司一切生产活动的基础和核心。航空　架飞机需要执飞一个航班序列，航班序列的始发和到达机场　相同。不仅仅是确定执飞的问题，还必须要确保航线调配过　程的安全性，每一架飞机在规定的时间间隔（Ｄ天）都必须到　公司的航班计划生成后，形成相应的航线网络，机型分配…　将航线网络分割成若干子网。为每个航线子网分配一种机　型。机型分配完成后，下一阶段航空公司需要考虑飞机排　特定的基地机场进行维修检查。传统的求解方案是在满足　维护等条件下，通过集合划分将每个决策变量对应代表一个　班＿２　问题，飞机排班包括飞机航线调配和尾号指派问题，其　实质就是在航空公司完成机型分配后。依据公司的航班时刻　表为每一个航班指定一架具体执行的飞机。通常情况下。一　航班串，当问题规模决定了变量个数，当Ｄ＞１４时，成为ＮＰ—　ｃｏｍｐｌｅｔｅ问题　３］。针对规模大难求解的问题，列生成方法被　提出。广泛应用于解决航空公司运营规划类问题，最先是由　ＭｉｎｏｕｘＬ４　１９８４年研究机组排班时提出的。随后被应用于机　型分配、飞机航线调配等航空公司运营规划其它重要环　基金项目：中央高校基本科研业务费（３１２２０１６Ｂ００６）　收稿日期：２０１７—０３—２８修回日期：２０１７—０４—１１　—节［５】［引。Ｃｏｒｄｅａｕｆ’　和Ｍｅｒｃｉｅｒｌ８　等人将列生成算法应用于　非线性资源限制约束的多商品流模型中，非线性资源约束代　５４一　表了维护需求．模型通过列生成结合ｂｅｎｄｅｒｓ分解和分支定　发状态（ｏ　，ｆ　，ｄ　），一个三元组描述其抵达状态（。；　，￡　，　ｄ　）。ｔ　＝航班时刻表中的飞机落地时间＋最小地面周转　时间。这样航班，能和任意在　飞离ｎ；　的航班连成航班　串。　价算法＿９］得出确切的最优解。国内朱金福，朱星辉等　人＿１　０＿［１１］使用列生成方法对飞机排班问题作出研究。另一种　广泛应用的求解是基于多商品流的模型，Ｌｅｖｉｎｌｌ　］针对飞机　航线调配问题第一个提出．问题通过０—１整数线性规划建　模，０—１决策变量为ｘ　，若航班ｉ和航班ｊ由飞机ｋ连续执　飞，则决策变量取值为１。　Ａｄ：过夜集合。对于每一天ｄ∈［Ｈ一１］，Ａｄ　Ｆ　ｕ　。如果萌≤ｄ并且ｄ　＞ｄ，则航班，属于过夜集以　。若　＝　，　≤ｄＹｒ－￣．　＞ｄ，则航班对　）属于过夜　本文在分析了现有文献基础上，引人航线调配等图模　型，证明飞机航线调配问题与等图路径查找问题的等价性。　然后将飞机维护限制条件附加到状态图中，使用航线调配等　集Ａｄ。　Ｊ　：维护过夜集。若口　，则这个航班对为维护航班　图构造航线网络状态图。最后提出可替代列生成法的基于　网络状态图的线性规划求解方法，设计成本最小化和飞机使　用均衡求解目标，使用ＬＩＮＧＯ１５求解器对算法进行了仿真　验证。　２航线调度的原理与建模　飞机航线调配问题成为民航界著名的ＮＰ—Ｃｏｍｐｌｅｔｅｎｅｓｓ　难题．众多的调配规则和复杂的约束条件是一项重要的原　因，合理高效的飞机航线调配方案。首要必须符合飞机航线　调配的调配规则，然后实现调配方案的成本最小，保障航空　公司运营效益。在满足基本规则的条件下，通过形成航线，　将把单个航班分配给飞机的问题，转换为把飞机航线分配给　特定飞机的问题，大大简化问题的复杂程度，降低求解规模，　本章对航线调配问题进行数学建模，随后章节引人等图概　念，通过图的路径划分问题，获得调配航线方案，加入基本规　则条件，构造出网络状态图，设计求解目标，提出基于网络状　态图的线性规划求解方法，为航空公司提供决策支持。　２．１基本调配规则　在飞机航线调配的过程中生成的可行性航线调配方案，　必须要满足以下基本规则：　１）符合航班计划：分配给每个航班的飞机应该满足航班　计划中规定的机型、航班起飞到达机场、航班起飞时刻。指　派给同一架飞机的两个航班应满足过站时间要求航站衔接　要求。　２）航班覆盖：每个航班应当且仅能安排一架飞机执行。　３）维护要求：航空公司一般只在各自的基地机场飞机进　行维护检修。保证维护要求就是要使飞机在航线执飞时能　在正确的基地和正确的时间里得到所需要维护。　２．２航线调配数学建模　日：飞机航线调配的时间维度。即每次航线调配的时间　周期（一周或一个月）。　ｔ：离散化时间。离散化为ｒ个间隔。　Ｄ：维护周期。　Ａ：机场集合，机场　∈Ａ。　Ｂ：基地机场集合，　Ａ。　Ｆ：航班集合。　每一个航班用两个三元组来定义，一个三元组描述其始　对　）∈　Ａ　，表示这个航班对在过夜期间完成维　护。　ｒ　：过站时间。两个航班之间的时间间隔大于过站检查　的时间（　＋　—ｔ　ａｒｒ≥　。　：表示航班串。　＝（　，‘‘　），满足　＝皖。，且　≤宪　，ｉ＝１，２，３…ｎ一１。如果两个连续的航班　＋－满　足　＋　）ｅ　，若ｏｒ中存在两个连续的航班使得在维护周　期Ｄ满足　＋　）ｅ　，则航班串为可行航班串。　Ｄ，　的运营天数。ｏｆ＝ｄ　一ｄ　始发时距最近一次维护　的过夜ｄ之间的天数。　航线调配问题就是用可行的航班串去覆盖所有的航　班。航班串　的最后一个航班厂不是必须抵达维护基地，因　此，在航线调配问题中需要将ｍ，作为每次计算周期的初始　条件。　ｋ：：机场８在ｄ天的初始状态。对于ｄ∈［Ｄ］，机场　有　ｋ：架飞机，必须在Ｄ—ｄ＋１天内进行维护检修。　７：：机场口在ｄ天的结束状态。对于ｄ∈［Ｄ］，到达。机　场的飞机至少∑：一　：架飞机在过去的ｄ天内进行过维护。　Ｑ：机队规模。Ｑ＝∑。　∑　：。　３　构建航线调度等图　引入等图的概念，构建航线调度等图数学建模，证明等　图的路径查找问题与飞机航线调配问题等价性，通过等图的　路径查找来获得飞机航线。　３．１　等图的定义　一　一个无环有向图Ｇ＝（　，Ｅ），它具有两个非空的不相交　的顶点子集Ｓ，　，其中Ｓ称为源，　称为汇，其它Ｊ＝Ｖ一（Ｓ　ｕ　）为内部点。　艿　（　）表示终点为　点的弧的集合，即入边。　占　（　）表示以　点为起点的弧的集合，即出边。　ｄ一（　）＝Ｉ　６　（　）Ｉ表示　点的入度。　ｄ　（口）＝ｌ　６　（　）Ｉ表示　点的出度。　若６’（　）＝（２ｊ，则点　ｅ　Ｖ为源节点。若艿　（　）＝　，　点　∈Ｖ为汇节点。若路径Ｐ∈Ｇ，是从源节点始发，指向汇　节点的路径。为一条ｓ—　路径。弧０∈Ｐ称为弧。被路径Ｐ　覆盖。若对于每条弧ａ　ｅ　Ａ，当且仅当存在一条满足ｏ∈Ｐ的　一５５—　路径的Ｐ∈的集合，称为图Ｇ的路径划分。如果图中的每一　个内部点　等图。　定理１：如果Ｐ是等图Ｇ中从源点指向汇点的一条路径．　在Ｇ中去掉路径Ｐ，剩下的部分依然是等图。　证明：人边与出边以相同的数量减少，所以结论显而易　见。　由此．得出飞机航线调配等图的数学建模为：　等图Ｇ＝（Ｖ，Ａ），过夜弧集合　，维护弧集合　，　，满足ｄ一（　）＝ｄ　（　），则这个有向无环图Ｇ为　维护约束Ｄ，初始约束　；，终止约束　；。　３．３等图合理性证明　定理２：飞机航线调配和等图路径查找问题是等价的：一　个问题可在线性时间内推导成另一个问题。　证明：令　，Ａ，口，Ｆ，Ｄ，，（：，　：为航线调配问题的实例。　令Ｇ　，　，Ｍ　，Ｄ　，，ｃ　，　为等图的实例，ｔ为一个按时间顺序　排列的索引，Ｏ／机场的初始飞机总数表示为　，　＝　在有向图中，连通两个点集　与　＼　的边的集为一个　割集。对应到等图中，有向割集　＝６一（　）。飞机的过夜　情况用点集的有向割集表示，例如图１中，有向割集为Ｎ　＝　６一（　）。　ｏ　●　一·一　Ｎ　图１　图的有向割集　３．２　航线调配等图建模　ｄａｙ（　）：顶点　表示的天数。在时间维度日内，如果一　个点　∈Ｕ　＼Ｕｄ，则定义函数ｄａｙ（　）＝ｄ。　Ⅳｄ：过夜弧集合。　＝６一（　）。　：维护弧集合。维护弧集合　表示在基地机场过夜　且进行维修检查。　为，ｖｄ的子集。　若路径Ｐ在维护周期Ｄ天覆盖到维护弧，则这条路径为　可行路径，即对于ｄ∈［　一Ｄ＋１］，有Ｐ　ｆ３（ｕ：　。）≠　。　（ｎ）：运营天数。路径Ｐ中，存在一条弧ｎ，运营天数　０　（ｎ）等于弧。和最近的维护弧Ｍ　间隔的天数。当路径Ｐ　中每一条弧的运营天数小于维护约束，即对于Ｖｏ∈Ｐ，　ｏ　（。）≤Ｄ，Ｐ为可行路径。　？：初始限制条件。每条可行路径在源节点的初始运营　天数。　：终止限制条件。每条可行路径在汇结点的运营天　数。　当等图的一组可行路径Ｐ满足下述要求时，则这组路径　生成了一个可行的航线调配方案。　１）每个航班能且只能被覆盖一次。　２）至少∑　Ｋ：条路径以ｓ为源点，Ｊ　ｎ—　在Ｄ—ｄ＋１天内遍　历集合ｕ　“　。的维护弧，即必须确保航班在Ｄ周期内进　行维护，Ｖｄ　［Ｄ］。　３）至少∑：一　ｙ　条路径以ｆ为终点，在最后的维护间隔　ｄ天内，遍历集合Ｕ　：　，Ｍ。中的维护弧，Ｖｄ∈［Ｄ］。　５６一　∑Ｄ　，ｃ：。由于航班覆盖约束，每一个航班只能由一架飞机　来执飞，Ｏｔ机场在　时刻的飞机数　可以用ｔ时刻前抵达的飞　机数减去ｔ时刻前离开的飞机数求得。　：　＋∑【∑１一∑１］　呼＝　，　＝ｒ　，、　：　＝ｒ　飞机航线调配有向等图Ｇ　＝（　，　）定义如下：对于每　个机场Ｏｔ∈Ａ在任意时刻ｆ，如果至少有一个航班在ｔ时刻离　开机场Ｏｌ，则图中对应形成一个内部点　（ｏ，ｔ）　。对于每　一个机场Ｏｌ，图中分别对应一个源节点ｓ　Ｓ和一个汇节点　ｔ　Ｔ。对于每一个航班，＝（（。　，　，ｄ　），（ｏ　，　；，　）），图　中对应存在一个起点为　（　ｄ，ｆ　，ｄ　），终点为　（　ａ，ｃ１’ｄ　）的　航班弧，其中ｔ，，ｄ　是第一个比ｔ　，ｄ　大的时间参数并且在　，　ｄ　时刻有航班从机场Ｏｔ起飞，如果不存在这样的ｔ，，那么这个　航班弧的目的节点指向终结点ｔ　。图中每一个点　表示为　机场和天数ｄａｙ（　）。令ｔ　，ｔ２，…ｔ　为飞离机场０连续的时　间点，ｉ　［ｎ］，则节点　（。，ｔ　）和节点　（ｏ，　）之间存在　条地面弧，若ｉ＝ｒｔ，则指向终结点￡　。定义Ｎ　．＝６一（Ｕ　，）是　ｄ天之后形成的有向割集合，即Ｕ　：｛　ｌ　ｄａｙ（　）＞ｄ｝，因　此，满足了等图中过夜特征Ｕ　，．ｃ　Ｕ　，。对于所有的ｓ，ｔ和ｄ，　初始条件和结束限制条件是相同的，即　＝　，ｙ　＝　。源　节点　和终结点　满足ｄ一（ｓ　）＝０，ｄ　（ｓ　）＝０。令　＝　（。，　ｔ）是中间点，令ｔ一为从Ｏｌ始发的ｆ时刻的前一个时刻，则可以　得出　ｄ　（　）一ｄ一（　）＝　一　一一［∑１一∑１］＝０　呼＝ｎ，　：　：ａ　：ｒ　×源结点　．中间结点　口汇结点　一航班弧　…　－过夜弧　…一维护弧　图２　航线信息对应的等图　因此，有飞机航线调配实例推导出来的图为等图，即为　飞机航线调酋己等图。例如表１中航线信息有对应如图２航线　调配等图。　表１航班时刻　４　基于网络状态图的航线调度优化　根据定理１．定理２．飞机航线调配问题可以转化为在等　图上的路径划分问题。本章引入状态图的概念。在飞机航线　调度等图的基础上，加入飞机维护的限制条件，构造飞机航　线调配网络状态图，通过求解状态图的路径划分，即可得到　航线调配问题可行解。　４．１　状态图的定义　在航线调配等图中。将飞机必须在每个Ｄ天内访问维护　过夜的限制条件附加到路径中来求解路径划分。这个限制　条件要求每个飞机携带其经过维护后飞行的天数。现在使　用网络状态图的形式定义航班在维护后的天数。　令Ｇ＝（　，Ａ）是一个有向无环图称为网络图。顶点集　＝ｓ　ｕ　ｆ　ｕ　ｒ，其中Ｓ是源节点的集合，ｆ是中间节点的集合，　是汇点的集合。　定义一个有向无环图Ｇ＝（　，Ａ）为图Ｇ的状态图：　对于每个顶点对应一个状态集　，。顶点　称为状态集　中状态顶点的网络顶点。状态图中顶点的集合即为　＝ｕ　。这些顶点称为状态顶点。　对于两个状态节点　．，ｔ，　与对应的网络节点　，　：，存在　一条弧　＝（　，１．／：）当且仅当ｏ＝（　，　：）是网络图中的一　条弧。弧ｔ／，称为　的网络弧，ｏｔ称为。的状态弧。令Ａ　为。的　状态弧的集合。对于每个状态节点ｕ∈　，，最多有一条状态　弧ａ　Ｅ　Ａ　从该节点指出。状态图的弧的集合Ａ＝Ｕ　Ａ。。　同样的，在状态图中源节点Ｓ，中间节点Ｊ，汇点　分别定义为　Ｓ＝ｕ　ｓ　，，＝ｕｆ　，　，Ｔ：ｔ．Ｊ　ｒ　。　４．２　网络状态图的构造流程　对于一个航线等图问题（Ｇ，　，Ｍａ，Ｄ，　０，　：），相对应的　航线网络状态图即Ｇ＝（　，Ａ）的状态图构建过程如下：　对于每一个顶点　ｅ　Ｖ，生成一个关于Ｄ的状态顶点集　＝｛ｔ，　，…，ｕ　｝。定义状态弧来确保每一个源点到汇点的　路径霄可以覆盖到Ｇ中的ｔ，：，其中０为路径划分Ｐ（仃）中维　护弧访问维护基地后的天数。对于每条弧ｎ＝（　，　）∈　Ａ＼（ｕｄＮ，ｉ），将弧（　：，，　）添加到Ａ。，其中ｏ　Ｅ［Ｄ］，表示非　过夜弧的状态不变；对于每条弧０＝（　，　）∈（ｕ　Ｍ　），将　弧（ｔ，：，，＂　１　）添加到Ａ。，其中ｏ　［Ｄ］，表示经过维护弧后，距　离上次维护的天数变为了１；对于每个弧。＝（　。，　）∈　（ｕ　＼ｕ　Ｍｄ），将弧（　：，，　）添加到Ａ。，其中ｏ　［Ｄ一　１］，表示经过非维护过夜弧后，距离上次维护的天数进行加　１；如果节点　，中的飞机距离上次维护之后已经过去Ｄ天，该　节点就不能将非维护过夜弧添加到状态图中。　对于附加到状态图中的初始和结束条件按照如下处理：　对于每个状态源”，定义Ｋ１，为从ｕ指出的路径的数；对于每个　状态汇　，定义Ｋ．，为指向　的路径的数。一个网络的路径划　分是一个包含在Ｇ的源到汇的路径仃的集合Ⅱ．其中仃要满　足在每个状态弧集　中有且仅有一条状态弧Ｏ／被路径７ｒ覆　盖，这样就有Ｋ　条路径从源ｌ，指出，有，ｃ　条路径指向ｔ，。对　于路径７ｒ中每条状态弧对应的网络弧。推导出图Ｇ中的路径　Ｐ　，因此根据打可推导出图Ｇ的路径划分为１７＝Ｕ　口Ｐ　。　一个状态等图是状态图Ｇ的部分图，是其中满足每条弧　口∈Ａ，ｌ　Ｇ　ｎ　Ａ　ｌ＝１条件的等图。若仃是Ｇ的网络路径　划分，则Ｇ　＝ｕ　７ｒ是状态等图。因此网络路径划分即为　航线调配问题的可行解。　图３　航线状态图构造流程　４．３　网络状态图数学模型的提出　令Ｇ为航线等图Ｇ的状态图，ｃ　∈　为Ａ中每条弧０／的　开销，ｕ　∈　为Ａ中每条弧０ｔ的运行时长。网络路径划分的　总时长是路径划分中每条状态弧的时长之和，即Ｕ（口）＝　∑　“　。为解决航线调配网络路径划分问题，在满足飞　机维护要求的前提下。综合考虑成本最小化和飞机使用均衡　条件下的提出整数线性规划如下。　目标函数　ｍｉｎ∑ａｅＡＣａＸｅ　ｔ（１）　ｍｉｎ∑　Ｊ　ｕ　一ｕ（ｘ／）／ｋ　Ｉ　（２）　约束条件　一５７—　∑　一　＝∑　＋　∑　。　Ｖ”　集表示过夜的航班。然后将飞机维护限制条件附加到状态　＝ｌ　Ｖ。　Ａ　图中，使用航线调配等图构造航线调配状态图。最后提出了　不同于列生成方法的线性规划求解方法的基于网络状态图　的航线调配问题数学模型，设计成本最小和使用均衡目标函　数，并对模型进行求解验证。在后续的研究中，可以将飞机　航线调配问题与机组配对优化问题，机型分配等问题集成考　（７）　∑　＋　＝Ｓｖ　Ｖ　Ｓ　∑。　一　＝ｔｖ　Ｖ”　．∈｛０，１｝　Ｖ　ｄ∈Ａ　虑，实现航空公司运营规划一体化优化管理。　参考文献：　［１］乐美龙，黄文秀．基于时空网络的航班机型分配问题研究［Ｊ］．　交通运输系统工程与信息，２０１４，１４（１）：８１—８７．　目标函数（１）表示成本最小化，目标函数（２）表示飞机　均衡使用，式（３）确保满足Ｂ：｛ｄ　ｌ　＝１｝条件的部分图　（Ｖ，Ｂ）是一个等图，式（４）要求Ｂ中对于每条ａ　Ａ的弧仅　有一条　∈Ａ，，与之对应。因此（　，曰）是一个状态等图，状态　等图就是航线调配状态图的路径划分即可行解。　５　航线调度优化仿真验证　为了验证本文提出的基于网络状态图的线性规划求解　方法，使用某公司真实航班信息进行实验。实验中使用杭州　，Ｌ／　，　，　基地组航班时刻表，共４０个国内航班，分配给９架７３８机型，　不考虑飞机间的差异。以ＨＧＨ为基地。表２中为部分航班　时刻信息。　表２实验中使用的部分航班信息　使用ＪＡＶＡ完成状态图的构建，使用Ｌｉｎｇｏｌ５软件数学　模型进行求解，结果如下表３所示。　表３实验结果　编号　航线调配可行解　７，２３，４，１１，１６，３０，２，１８，３１，３６　５，１９，２９，３５，３，１７，２７，３８，８，１３，２２，２８，３７，４０　４，１１，１６，３０，２，１８，３１，３６，４，１１，１６，３０　８，１３，２２，２８，３７，４０，４，１１，１６，３０，３，１７，２６，３４　５　９，１５，２４，３２，７，２３，２，１８，３１，３６　６　１，　ｌ２，２０，２５，３３，３９，８，１３，２２，２８，３７，４０，１，１２，２０，２５，３３，３９　７　３，１７，２６，３４，１，１２，２０，２５，３３，３９，６，１０，１４，２１，２７，３８　８　２，１８，３１，３６，９，１５，２４，３２，９，１５，２４，３２　９　６，１０，１４，２１，２７，３８，６，１０，１４，２１，２６，３４，７，２３　６结语　为了解决飞机航线调配问题，本文引入满足几个特殊条　件的图的概念，并将其等价于图的路径划分问题。等图中的　点表示机场与时间，等图中的弧表示航班，等图中的有向割　一５８　［２］　孙宏，杜文．航空公司飞机排班问题的排序模型及算法［Ｊ］．系　统工程理论方法应用，２００２，１１（３）：２４４—２４７．　［３］　Ｒ　Ｇｏｐａｌａｎ，Ｋ　Ｔ　Ｔａｌｌｕｒｉ．Ｔｈｅ　ａｉｒｃｒａｆｔ　ｍａｉｎｔｅｎａｎｃｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ　［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，１９９８，３２（１）：４３—５３．　［４］　Ｍ　Ｍｉｎｏｕｘ．Ｃｏｌｕｍｎ　Ｇｅｎｅｒａｔｉｏｎ　Ｔｅｃｈｎｉｑｕｅｓｉｎ　Ｃｏｍｂｉｎａｔｏｒｉａｌ　Ｏｐｔｉ－　ｍｉｚａｔｉｏｎ：Ａ　Ｎｅｗ　Ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　Ｃｒｅｗ　Ｐａｉｉｒｎｇ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｊｏｕｒｎａｌ　ｆｏｒ　Ｎｕｍｅｒｉｃａｌ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，１９８４，７８（９）：１１１３　—１１３４．　［５］　Ｍ　Ｓ　Ｄａｓｋｉｎ，Ｎ　Ｄ　Ｐａｎａｙｏｔｏｐｏｕｌｏｓ．Ａ　Ｌａｇｒａｎｇｉａｎ　Ｒｅｌａｘａｔｉｏｎ　Ａｐ—　ｐｒｏａｃｈ　ｔｏ　Ａｓｓｉｇｎｉｎｇ　Ａｉｒｃｒａｆｔ　ｔｏ　Ｒｏｕｔｅｓ　ｉｎ　Ｈｕｂ　ａｎｄ　Ｓｐｏｋｅ　Ｎｅｔｗｏｒｋｓ　［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９８９，２３（２３）：９１—９９．　［６］Ｃ　Ａ　Ｈａｎｅ，ｅｔ　ａ１．Ｔｈｅ　ｆｌｅｅｔ　ａｓｓｉｇｎｍｅｎｔ　ｐｒｏｂｌｅｍ：Ｓｏｌｖｉｎｇ　ａ　ｌａｒｇｅ—　ｓｃａｌｅ　ｉｎｔｅｇｅｒ　ｐｒｏｇｒａｍ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ　Ｐｒｏｇｒａｍｍｉｎｇ，１９９５，７０　（１）：２１１—２３２．　［７］　Ｊ　Ｆ　Ｃｏｒｄｅａｕ，ｅｔ　ａ１．Ｂｅｎｄｅｒｓ　Ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｆｏｒ　Ｓｉｍｕｌｔａｎｅｏｕｓ　Ａｉｒ－　ｃｒａｆｔ　Ｒｏｕｔｉｎｇ　ａｎｄ　Ｃｒｅｗ　Ｓｃｈｅｄｕｌｉｎｇ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｃｉｅｎｃｅ，　２００１，３５（４）：３７５—３８８．　［８］　Ａ　Ｍｅｒｃｉｅｒ，Ｊ　Ｆ　Ｃｏｒｄｅａｕ，Ｆ　Ｓｏｕｍｉｓ．Ａ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｓｔｕｄｙ　ｏｆ　Ｂｅｎｄｅ￣ｄｅｃｏｍｐｏｓｉｔｉｏｎ　ｆｏｒ　ｔｈｅ　ｉｎｔｅｇｒａｔｅｄ　ａｉｒｃｒａｆｔ　ｒｏｕｔｉｎｇ　ａｎｄ　ｃｒｅｗ　ｓｃｈｅｄｕｌｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｃｏｍｐｕｔｅｒｓ＆Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，　２００５，３２（６）：１４５１—１４７６．　［９］　Ｃ　Ｂａｒｎｈａｒｔ，ｅｔ　ａ１．Ｆｌｉｇｈｔ　Ｓｔｒｉｎｇ　Ｍｏｄｅｌｓ　ｆｏｒ　Ａｉｒｃｒａｆｔ　Ｆｌｅｅｔｉｎｇ　ａｎｄ　Ｒｏｕｔｉｎｇ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９９８，３２（３）：２０８—２２０．　［１０］朱星辉，朱金福，高强．基于约束编程的飞机排班问题研究　［Ｊ］．交通运输系统工程与信息，２０１１，（６）．　［１１］朱星辉，朱金福，高强．基于动态列生成算法的飞机排班问题　研究［Ｊ　Ｊ．数学的实线与认识，２０１４，（１９）．　［１２］　Ａ　Ｌｅｖｉｎ．Ｓｃｈｅｄｕｌｉｎｇ　ａｎｄ　Ｆｌｅｅｔ　Ｒｏｕｔｉｎｇ　Ｍｏｄｅｌｓ　ｆｏｒ　Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｙｓｔｅｍｓ［Ｊ］．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９７１，５（３）：２３２—２５５．　［作者简介］　于焯（１９８９一），女（汉族），辽宁大连人，硕士研究　生，主要研究方向：航空公司收益管理理论及应用、　计算机软件理论及应用、智能信息处理：　樊玮（１９６８一），男（汉族），陕西成阳人，教授，博　士，ＣＣＦ会员，主要研究方向：航空公司收益管理理　论及应用、大数据处理、计算机软件理论及应用、智能信息处理。