基于网络流理论的停机位分配多目标优化模型

袁 媛， 翟好鑫

(沈阳航空航天大学经济与管理学院, 沈阳 110136)

机场停机位作为进港飞机运行的终点和离港飞机运行的起点，其为飞机停放、旅客上下机、行李及货物装载提供了场所，也是航空与地面运输的转接点。随着航空运输业的快速发展，中国各大机场的航班数量都有明显增长，有限的机场设施资源逐渐成为限制民航事业发展的重要因素，因此，合理地分配使用各项设施资源是机场需解决的主要问题。而停机位作为机场运输资源的核心，其分配结果对大量物资、旅客及相关工作人员都产生影响，分配计划对机场航班和航线也有着直接的经济影响。作为机场运营管理人员日常面临的重要问题之一，停机位分配的目的是把每个航班分配至可用的登机口，同时也最大限度地为乘客和机场的运营效率提供便利，这就需要一个高效的解决方法来提供合理的停机位分配数据。

停机位分配问题(gate assignment problem, GAP)的研究方法大致分为数学规划[1]、智能优化[2]和系统仿真[3]等3类。由于数学规划法中基于图论的网络流模型自身较好的适应性和可扩展性，近几年中外文献选用此方法进行研究。国外文献较早将网络流理论运用到停机位分配中，二值整数多商品网络流模型在实际问题的分解方法中被证明计算效率很高[4]，而建立两个多商品网络流模型[5]可以有效地解决停机位再分配问题，对于多目标优化模型[6]，利用多商品网络流同样可以得到合理的停机位分配模型。在大规模停机位分配问题中，中国文献在计算时采用分子区的策略[7]来加速对网络流模型的求解，而采用多商品网络流模型建立的双目标停机位实时再分配优化模型[8]，在仿真实验中达到了良好的时效性和乘客满意度。中外文献将多商品网络流的停机位鲁棒性结合研究，部分文献利用算法加速模型求解。现将网络流理论应用到多目标优化模型中，首先对网络流模型进行详细描述，并用实例验证其在大规模停机位分配应用中的适用性和高效性，同时还证明其对多目标优化问题的有效性。

中外学者对于停机位分配模型的研究主要考虑旅客步行距离[9]、预分配方案的鲁棒性[10]或停机位再分配[11-12]建立单目标优化模型，或是兼顾停机位使用效率、航空公司公平性、航空绿色发展等建立双目标停机位分配优化模型[13-14]。但是这些研究只能反映停机位分配需要解决的部分问题。为此，在实际的停机位分配过程中平衡机场、旅客和航空公司的多方利益，考虑停机位分配过程中新的特征，改进停机位分配中实际存在的条件约束和优化目标，建立更高效的分配模型，尽可能使调度结果的综合效能最大化。在进行优化目标选择时，综合考虑旅客步行距离、航空公司成本与停机位浪费率进行协同决策，以期提升旅客满意度，增大机场运行效率，降低航空公司运行成本，达到综合效益最优。

1 停机位分配问题模型描述

1.1 假设条件

在模型建立之前，先提出如下假设条件。

(1)信息完备假设：在机场某个工作日开始之前，制订决策所必需的航班计划、机场资源等信息是已知且完备的，同时不考虑过夜航班。

(2)容量满足假设：航班总量及其进离港时间分布保持在机场容量许可范围之内，远机位可以容纳无限架次飞机，即任何时刻，机场总可以为任一进港航班分配一个停机位，尽管不是最优但一定可行。

(3)停机位使用假设：对到达航班分配停机位时采取“先到先服务”服务策略，不组合使用停机位，不考虑使用备用停机位以及维修机位。

(4)机场为单跑道，每一个时间段仅允许一架次飞机降落。

1.2 数学符号

停机位分配问题相关的数学符号定义如下:F为停机位分配计划期内所有到港航班集合；B为停机位分配计划期内所有离港航班集合；G为停机位分配计划期可提供的所有停机位集合；M为计划期内的航班总数；N为机场的停机位总数，其中N+1为远机位；i为进港航班对应序号，且∀i∈F;j为离港航班对应序号，且∀j∈B;k为停机位对应序号，且∀k∈G;ATi为航班i计划到港时刻;DTi为航班i计划离港时刻;Ei为航班i的停机位占用时间，即航班过站时间，Ei=DTi-ATi;ci为执行航班i的航空器大小;ρk为停机位k允许停放的最大机型;Ω为一个很大的正数。

1.3 网络流模型

多商品网络流的图形是通过网络中的停机位弧在箭头的方向流动来表示的。停机位(G1，G2，…，GN)代表商品，这些商品是从源节点(S)到终节点(T)通过中间的航班到达节点(A1，A2，…，AM)和离开节点(D1，D2，…，DM)连接，每一组节点弧沿箭头方向在网络中从源节点(S)流经到达节点和离开节点流向终节点(T)的过程构成一个完整的商品流，多个商品流相互交错形成多商品网络流模型。以3个停机位5个航班为例，图1所示为其多商品网络流模型的一个可行分配方案。

图1 多商品网络流模型的一个可行分配方案Fig.1 A feasible allocation plan of the multi-commodity network flow model

1.3.1 节点

S为源节点，T为终节点，(A1，A2，…，AM)为到港航班节点，(D1，D2，…，DM)为离港航班节点。其中源节点和终节点是虚拟的节点，只表示网络发散之源和汇聚之处。

1.3.2 弧

(1)流入弧。流入弧是指连接源节点(S)到港航班节点(Ai)之间的弧，使用弧(S，i)表示，其存在表示停机位被使用，且航班i第一个分配给停机位。

(2)服务弧。服务弧是指连接到港航班节点(Ai)到离港航班节点(Dj)之间的弧。服务弧从航班到达时开始使用停机位，一直到航班离开为止，使用弧(i，j)(s.t.i=j)表示，其存在表示航班i在停机位接受服务。航班的服务由乘客离机、加油、清洗和乘客登机等服务组成。

(3)流出弧。流出弧是指连接离港航班节点(Dj)到终节点(T)之间的弧，使用弧(j，T)表示，该弧的存在表示航班j最后一个分配给停机位，并从此停机位离开。

(4)反馈弧。反馈弧是指连接离港航班节点(Dj)和到港航班节点(Ai)之间的弧，其流的方向与其他流向相反，使用弧(j，i)(s. t.j≠i)表示，其存在表示航班i在航班j之后使用停机位(Gk)，如图1中到港航班节点(A2)与离港航班节点(D1)连接的反馈弧，即表示航班2就在航班1之后被安排在第1个停机位。反馈弧只有在航班i的到达时刻比航班j的离开时刻大时才存在，且同用一个停机位的相邻航班之间有安全间隔时间p，取p=30 min。定义一个参数Iji如下：

(1)

(5)穿过弧。穿过弧是指连接源节点(S)到终节点(T)之间的弧，使用弧(S，T)表示，其存在表示没有使用任何中间节点(到达节点、离开节点)，即没有航班分配到该停机位。如图1中没有航班停靠在第3个停机位。

1.3.3 变量

多商品网络流中的0-1整数变量与5种类型的弧一一对应：变量XkSi表示航班i第一个分在停机位k，即从源节点S到到达航班节点(Ai)的停机位(Gk)流入弧；变量Xkij表示航班i在停机位k接受服务，即从到港航班节点(Ai)到离港航班节点(Dj)的停机位(Gk)服务弧(i=j)；变量XkjT表示航班j最后一个流经停机位k，即从离港航班节点(Dj)到终节点(T)的停机位(Gk)流出弧；变量Xkji表示航班i在航班j之后使用停机位k，即从离港航班节点(Dj)到港航班节点(Ai)的停机位(Gk)反馈弧(i≠j)；变量XkST表示没有航班流经停机位k，即从源节点(S)到终节点(T)的停机位(Gk)穿过弧。

1.4 约束条件

(2)

i=j,k∈G

(3)

i=j,k∈G

(4)

(5)

(6)

∀i∈F,k∈G

(7)

(8)

2 目标函数

由于停机位分配问题涉及到旅客步行距离、航空公司的经济效益、机场资源的有效利用以及地面服务部门的工作场所等多个方面，因此从不同角度出发可以得到不同的优化模型，而不同机场的侧重点也不相同。采用线性加权法权衡多方主体利益来优化目标函数指标。

2.1 旅客

从旅客的角度，停机位分配的主要目的是提高旅客满意度。以最小化进离港旅客步行距离为目标建立停机位分配目标函数为

(9)

2.2 航空公司

航空公司运行过程中，应该尽可能地降低航空器运行成本和停机成本。航空器运行成本往往受到恶劣天气、突发事故等不可控因素的影响[15]，且较难控制。而停机成本受到分配效率、分配公平性等因素影响较多，可以通过有效的管理降低航空器停机成本。

根据不同机型的运行性能数据设定滑行油耗为: 大型航空器 40 kg/min、中型航空器22 kg/min、小型航空器12 kg/min。航油价格取7 500元/t。按照民航局2007年颁布的《民用机场收费改革实施方案》中的停机位收费标准和分配原则，假设所有靠桥航班均采用单桥，并建立最小化航空器运行成本和停机成本的停机位分配目标函数为

(10)

Ci,k计算方式为

(11)

2.3 机场

为了充分利用机场的停机位资源，停机位大小要与所停放的飞机机型相匹配，即对于小型机，优先为其分配小型停机位，如果当前没有小型停机位，则再考虑将其分配到空闲的中型停机位上，最后考虑将其分配到空闲的大型停机位上；对于中型机，不能分配到小型停机位，如果当前没有中型停机位，则再考虑将其分配到空闲的大型停机位上；对于大型机，只能被分配到大型停机位上，如果当前暂无空闲停机位，则将到达的飞机停放至远机位。由于机型与停机位不匹配时会造成停机位资源的浪费，因此最大化停机位利用率就是最小化停机位资源的浪费。对于分配到停机位k的航班i，给定一个参数yik来表示停机位资源的浪费率:

(12)

所以最小化停机位资源浪费率的停机位分配目标函数为

(13)

2.4 多目标优化

为平衡机场、旅客和航空公司的多方主体利益，建立多目标优化模型尽可能使调度结果的综合效能最大化，并利用线性加权法进行系统分析，根据各目标的优先级把多目标优化模型转化为综合目标进行优化。由于目标函数具有各自的量纲，其单位和数量级都有所差别，因此不能简单地通过设置权重因子来得到最终的目标函数，而需要对效用函数进行归一化处理。设βm为第m个目标函数的权重，Zmax=maxZm，则经过归一化处理的效果函数为

(14)

3 实例分析

采用某机场实际运行的58个航班数据和航站楼的10个典型的近机位、一个远机位进行实验，其中G01、G02、G03、G04、G05、G06机位为大型机位；G07、G08、G09号机位为中型机位；G10号机位为小型机位。同时选取某日08：00—22：00出发或到达的航班验证和求解模型。算例数据统计如表1所示。

表1 某机场待分配航班数据Table 1 Flight data to be assigned in an airport

3.1 求解速度分析

传统数学模型对停机位与航班的唯一性、同一停机位相邻航班的时间间隔和停机位-航班类型匹配进行约束并建模[16]，利用传统数学模型和建立的多商品网络流模型分别对3种停机位-航班规模进行求解并记录求解时间，对比发现以下结果。

所建立的多商品网络流模型对于停机位分配问题的求解速度有明显的提升(图2)。随着停机位-航班规模的增加，求解速度的提升越来越明显，当对21个停机位116个航班进行分配停机位时，多商品网络流模型的平均求解速度比传统数学模型增长了38.31%。可见所建立的多商品网络流模型在大规模停机位分配问题中的高效性和合理性。另外，所建模型对多目标优化函数的求解速度与大部分单一目标函数相比较快，当对21个停机位116个航班进行分配停机位时，多商品网络流模型对多目标函数求解速度较单目标函数求解速度平均快了13.49%，尤其是相对于乘客步行距离单目标函数速度增长了21.17%，验证了多商品网络流模型对于多目标优化函数求解的可行性和高效性。

图2 两种模型求解时间对比Fig.2 Comparison chart of solution time of two models

3.2 分配结果分析

首先采用贪婪启发式，根据“先到先服务”的原则，综合考虑停机位和航班类型对航班分配停机位，尽量让同等类型的航班和停机位匹配，相同条件下选择距离较近的停机位；若没有同等类型的停机位与其相匹配，再选择次近类型的停机位，相同条件下选择距离较近的停机位。

分别对单目标函数求得最优后，与贪婪启发式对比分析如表2所示。对比数据可见，旅客、航空公司和机场主体利益之间会互相制约、互相影响。当尽量多地考虑停机位类型利用率时会优先将航班分配到与其大小匹配的停机位，此时停机位类型利用率相对贪婪启发式优化了4.69%，从而忽视行李大厅至停机位的距离和安检口至停机位的距离，导致进离港旅客行走距离增加；同样地，如果只考虑乘客满意度而最小化旅客步行距离使得旅客行走距离相对贪婪启发式优化5.18%，极大可能导致中小型航班分配在较近的大型停机位。但是，各目标函数都有其现实意义。

表2 贪婪启发式与单目标优化目标函数值对比Table 2 Comparison of objective function values between greedy heuristic and single objective optimization

通过对36种权重赋值方案对应的停机位分配结果进行分析发现以下结果。

(1)存在3种不随权重变化的停机位-航班组合，如中型航班F35、F50一直分配在中型停机位G07。同等类型的航班-停机位相互匹配，若同时进离港时间只允许其停放在此停机位，或此停机位距离值机柜台距离较近，则航班会一直分配在此停机位。

(2)存在不同航班分配的停机位一直一致，如无论何种目标函数权重，航班F08和航班F15的停机位一直一致。分析上述航班进离港时间可以发现，两个分配同一停机位的相邻航班的间隔时间较为接近安全时间间隔，可以增加为后续航班分配在此停机位争取更多的可利用时间。

(3)临近的相同机型的航班在恰好与其匹配的停机位之间互换，如无论3个目标函数的权重如何分配，中型航班F01、F03在中型停机位G07、G08中互换。由此可见，相同机型的航班在与其相匹配的停机位之间互换不会对乘客步行距离、航空公司成本和停机位浪费率造成太多的负面影响。

(4)临近的不同机型的航班在可与其匹配的停机位之间互换，如小型航班F33、F34在前3类目标函数值下停机位分配在G08和G10，而在第4类目标函数值(权重80/10/10)下分配在G04和G08，减少了乘客步行距离，却使得停机位利用率明显降低。可见不同的目标函数取值下航班所分配的停机位会在匹配的前提下互换。

(5)远机位使用情况：分析结果可以看出，只有大型航班F36或F37会分配至远机位。由于航班停靠在远机位需要使用摆渡车等机场设施资源，耗费机场、航空公司的人力物力成本。由此可知，机场进行停机位分配时，如果可供分配的近机位不够充裕时，应尽可能地将大型航班安排在远机位。

3.3 较优方案选择

根据表2结果设定各目标函数优先级：旅客行走距离目标函数优先于机位类型利用率目标函数，机位类型利用率目标函数优先于航班成本目标函数。由于数据的理想化，导致不同的赋值权重得到不同的分配方式相同的目标函数值的情况，分析得出，该优先级下当赋值权重为50/10/40、50/20/30和60/10/30时目标函数值较优，此时进离港旅客行走距离较贪婪启发式优化了2.08%，航班成本优化了0.08%，机位类型利用率优化了4.69%，比贪婪启发式各个方面均有改善。

但由于3种分配方式下，不同的停机位的利用时间不同，故综合考虑以上3种权重赋值时的停机位分配方案，3个目标函数赋值分别为60/10/30时不同停机位时间上的绝对利用率和相对利用率较为均衡，这样就使得机场停机位资源的使用和机场各工作人员的工作强度较为均衡，同时也增强了停机位分配的鲁棒性。相应的停机位分配结果如表3所示，其对应的甘特图如图3所示，每个停机位的绝对利用时间和相对利用时间如图4所示。

表3 停机位分配结果Table 3 The results of gate assignment

图3 较优权重(60/10/30)下停机位分配甘特图Fig.3 The Gantt chart of gate assignment under better weight (60/10/30)

图4 较优权重(60/10/30)下停机位利用时间Fig.4 The utilization time of gate under better weight(60/10/30)

4 结论

(1)建立了以旅客、航空公司、机场多方主体利益为目标的停机位分配策略，运用多商品网络流进行建模并实现快速求解。

(2)通过线性加权法对多目标权重进行赋值，并在实例中分析不同主体利益的优先级下停机位分配结果的特征，进而选择一种较为经济、适用、满意度高的停机位分配结果，在兼顾国际民航组织有关机场服务质量的规定的同时，也能很好地均衡各主体之间的利益，使旅客获得了不错的满意度，充分利用了停机位资源，降低了航空公司的成本，同时还保证了停机位分配的鲁棒性。

(3)停机位资源的高效率使用是多方主体共同合作的结果，要实现多目标优化模型的结果，不仅需要航空公司和机场之间形成长期合作的沟通机制，还需要根据航空运输业的发展动态调整停机位分配规划。

(4)将网络流理论运用在多目标优化的停机位分配问题中，考虑停机位分配的动态性可以作为停机位分配模型进一步研究方向。