同机位相邻机场间停机位分配鲁棒性调整算法

同机位相邻机场间停机位分配鲁棒性调整算法

0问题的提出及研究进路随着客运吞吐量和飞机布局的逐年增加，机场运营中的延误问题日益严重。停机位资源的分配是机场运营管理的重要环节之一，合理的机位资源分配方案是减少冲突、提高机位利用率的重要途径。在航空需求无限增长与机位资源有限的不均衡现象日益突出的情况下，如何在减少航班延误或提前到达对机位分配方案产生的冲突的同时又提高机位利用率是机场运行亟待解决的问题。目前，已有很多国内外学者分别从不同的角度对机位分配问题进行了深入研究。李亚玲等以上大部分研究都是从鲁棒性、旅客行走距离、换乘时间等方面进行研究，未考虑到机位利用率与鲁棒性的关系。本文综合考虑了停机位的利用率及鲁棒性，提出了一种新的停机位分配方法，通过分析航班到达的分布特点，设计同机位相邻航班间的缓冲时间，并考虑运行中的相关约束，建立停机位分配模型。针对该分配模型的特点采用拉格朗日松弛算法对其进行仿真模拟优化，并与实际机场运行数据进行验证和对比，说明本文所提出的方法能够较好地提高机位利用率，并减少航班冲突数量。1停止并分配模型1.1到港机位分配问题描述机场停机位分为近机位和远机位，近机位配有廊桥，乘客上下飞机方便，乘客在远机位登机则需要借助摆渡车，不但给旅客带来不便，而且增加机场运营成本。停机位分配是指将有限的停机位资源合理地分配给某个时间段内的到港航班，兼顾旅客登转机时间、航班地面服务时间、航班类型、航班时刻、停机位类型等因素，最终实现对未来某个时间段内的到港航班分配合适的停机位，并且在分配过程中力求提高机场运行效率、减少运营成本，同时又能提高旅客满意度。不失一般性，需要解决的问题可以描述为：存在m个停机位为航班停靠及旅客登机服务，选取的时间段内有n个航班需要停靠在机位上。稳定性是反映停机位分配方案鲁棒性的指标，即停机位分配方案在受到扰动后的偏离程度，假设Q1）最小化每个停机位的空闲时间，即所有停机位的未被占用时间总和最小。2）最小化远机位的占用时间，即尽可能把航班分配到近机位，最小化远机位个数，从而既方便旅客登机又减少摆渡车等的费用。本文研究停机位分配问题，基于如下假设：1）机场停机位数量充足，在某时间段内不会出现航班无机位可分配的情况；2）不考虑某些特定区域机位指定给某固定的航空公司使用；3）进港航班均服从“先到先服务”的原则；4）航班计划信息完备已知，包括航班机型、到离港航班时刻计划等；5）不考虑某些停机位因设备故障等特殊原因而导致的不可用的情况。1.2模型建设1.2.1变量解释停机位分配模型所使用的符号参数说明如下：1）输入变量：N为航班集合；M为停机位集合；ε2）决策变量：y1.2.2优化目标根据上述分析，停机位分配模型的优化目标如下。1）最小化各机位空闲时间为：2）最小化远机位占用时间为：1.2.3上停机位分配模型如果航班i和航班j为同机位的相邻航班，则两航班间要有安全缓冲时间，需要满足：航班i离港时间-航班j进港时间≥最小安全缓冲时间；如果航班i和航班j为同机位的紧前紧后航班，可以推算两航班间的空闲时间应小于航班过站时间：航班i离港时间-航班j进港时间≤航班过站时间。综上停机位分配模型的约束条件如下：式（3）表示每架航班只能且必须分配一个停机位。式（4）表示同一停机位在同一时刻只能停放一架飞机，分两种情况：1）航班i先被分配到停机位k上，航班j后被分配到停机位k上，即a2基于拉格朗日松弛算法的模型求解根据1.2节的介绍，停机位分配调度模型是一个典型的NP(Non-deterministicPolynomial)-hard混合整数规划问题，拉格朗日松弛算法可以通过将机位分配问题中的困难约束条件松弛到目标函数中，从而降低模型的求解难度。同时通过求解松弛问题，可获得原问题的解的上下界，然后对拉格朗日乘子进行不断的迭代更新，使得松弛问题的解逐渐逼近原问题的解。2.1使用次梯度算法求解表面约束假设zs.t.Ax≥b（松弛约束）Bx≥d（保留约束）从zs.t.Bx≥d（保留约束）s.t.Bx≥d（保留约束）有限个离散点的集合Q={x|Bx≥d,x∈Z得到：若zs.t.Ax≥b（松弛约束）即z然后在已知的可行解域中对凸函数使用次梯度算法通过不断的迭代求得全局最优解。2.2拉格朗日对偶对偶问题对机位分配模型中的约束式（3）松弛，则原问题变成了不考虑机位约束的问题。松弛后的模型相较于原模型约束条件减少一个，限制因素减弱，即解空间增大。拉格朗日松弛算法是一种求最值问题很有效的方法，设λ上述目标函数需满足式（4）～式（9）和式（11):记z将式（13）的拉格朗日松弛对偶问题分成两部分：式（14）为非正则子问题；式（15）为正则子问题。当给定一组拉格朗日乘子λ正则子问题可以给予航班分解：其中，λ2.3子阶段算法优化拉格朗日乘数次梯度算法是一种求解拉格朗日问题的有效方法，T式（17）中拉格朗日乘子的初始值为0，上标u表示迭代次数。Sθ其中：2.4问题可行化的处理对偶问题得到的解对原问题来说可能是不可行的，因为可能不符合唯一性的约束条件（3），因此需要对松弛问题的解进行可行化，从而获得原问题的上界。本文设计了一种启发式算法，其步骤如下：将式（16）求得的解作为启发信息，将2.5机场服刑人员的要求解的更新基于松弛算法的停机位分配调度优化算法具体步骤如下：步骤1初始化：令当前迭代次数u=0，令所有拉格朗日乘子λ步骤2计算下界：用动态规划求解每个航班的子问题，得到原问题解的下界。步骤3解的可行化：对松弛问题的解进行可行化，得到原问题解的上界。步骤4更新解的上下界。步骤5判断是否满足终止条件：所得问题解的上界和下界差小于最优间隔或迭代次数大于200时，则终止迭代，获得最终解步骤6更新拉格朗日乘子：设定迭代步长初始值为β=2，则令β3某嘴唇上的旅客停机位本文以某国际机场为研究对象，选用该机场5月份某个繁忙日8:00—12:00的航班数据，在此时间段内共有56架航班、38个停机位，其中包括近机位34个、远机位4个。数据样本如表1所示。3.1误时对后续机组的影响从图1所示的原计划机位分配甘特图可以看出，1号和9号停机位中两航班间的空闲时间较少，当有航班延误时对后续航班占用机位的影响较大，分配方案的鲁棒性较差。与原分配方案相比，如图2所示的优化后机位分配图，其航班间的空闲时间分布均匀且间隔较大，能较好地吸收一定时间范围内航班延误产生的扰动，减少航班延误对分配方案的影响。式（20）和（21）分别为机位空闲时间及机位占用比的计算方法：其中：F3.2平均磷空间时间优化前后的机位空闲时间如图3所示。从图3中可知，优化前机位最大空闲时间为270min，最小空闲时间为140min，求得其平均空闲时间约为220.9min；优化后的平均空闲时间为204.2min，空闲时间缩短了7.56%，满足了目标函数中缩小机位间的空闲时间的需求，验证了本文所提方法的有效性。3.3机位利用率的提高从图4可以看出，优化后的机位预分配方案中几乎大部分机位的占用比均有所提高，平均占用比为34.12%，而优化前的平均占用比只有28.74%，增幅为18.72%。大大提高了机位的利用率。根据调查，该枢纽机场的航班高峰时段分别为8:00—12:00和15:00—18:00，同理采用上述方法对15:00—18:00的39个航班进行分配，得到机位占用比如图5所示。从图5中可以看出，优化后使用停机位的数量从30个减少到26个，停机位占用比从22.84%提高到26.36%。综上可知，本文提出的基于松弛算法的停机位分配方法可以适应不同航班延误时间、不同航班密度等情况。3.4优化前后分配方案对比将当日航班实际到、离港时刻运用到预分配方案中，表3为实际运行数据。这56个航班中，航班最早到达时刻为8:22，航班最晚离港时刻为19:00。与原分配方案相比，优化后分配方案所用停机位数量从38个缩减到32个，机位使用量减少了15.79%，并且所有航班都被分配在近机位上，符合优化目标中最小化远机位占用时间的要求，这样既方便旅客上下飞机，又减少了调用摆渡车等的使用费用。从表3中可以看出，实际运行中，优化后的占用比相较优化前提高了22.47%，原冲突率为5.36%，优化后冲突率为3.57%，所以总的来说优化后的方案整体性能较好，达到了提高机位占用比、减少航班冲突的效果。4流程深入分析本文研究了停机位分配问题，以提高停机位利用率为目标，并提出基于松弛算法的停机位分配模型求解方法，具体包括如下几个方面：1）通过对机场的停机位分配业务流程进行深入分析，基于机场航班实际运行需求，构建了停机