停机位预指派问题的数学模型

      将一天的机场开放时间划分成若干区间，称为指派周期，例如，一天开放16h，划分成8个区间，则平均每周期2h。每个周期长度的确定原则是：该周期内新到港航班不在本周期内出港，出港的都是在期初已在机位的FBA空运头程。在每个周期的开始，停机位集合J分成两个子集J。和J，J是空着的机位集合，J是被占机位的集合。再设J2为在本周期中因为FBA空运头程出港而空出的机位集合，J2三1，其中J2停机位可通过查询J中FBA空运头程的出港时刻获得，本周期结束时刻与出港时刻的差不小于T的FBA空运头程停靠的机位集合即J2。

      该周期需要处理的FBA空运头程集合也分成三个子集o、h和 2，16是期初已停靠机位的FBA空运头程，Ii是本周期内将进港并需要分配机位的FBA空运头程。是在本周期内将出港的FBA空运头程，可通过查询I。中FBA空运头程的出港时刻获得，显然有2SIo， 而且有|l2|=1J2l。另外，为了机位分配问题可行，还应满足|il≤lJoUJ2l。 如果不满足该关系，可缩短指派周期，将后面到达的FBA空运头程划归到下一个周期去指 派。现在要做的是只需将的FBA空运头程指派到J。或J2的机位即可。 对每个指派周期完成停机位分配后，将各周期指派的结果综合起来即可获得一天的预指派计划。 根据前面的讨论，现在给出某个周期的停机位预指派模型。由于不知道各航 班旅客数，也不涉及登机门的更换，不采用旅客行走距离最小作为目标函数，而是 采用FBA空运头程延误和停机位空闲的时间总和最小为目标函数，并采用基本约束条件，给 出一个周期中停机位预指派问题的数学模型如下： 式中，T。

      是本周期初的时刻；K，是停机位€J。UJ2可指派给1中FBA空运头程停靠的开始时刻；x/是决策变量，当FBA空运头程i指派给停机位j时等于1，否则等于0。 作为该周期的初始条件，对于€J2的停机位和iE1。的FBA空运头程，当FBA空运头程已停靠 在机位j时，令=1，否则=0。因此，由式（2-80）和式（2-81）计算的K，是已知参 数。另外，式（2-77)中，A是到达FBA空运头程等待进入机位的最大允许延误时间。 上述模型中，目标函数（2-74)的第一项是FBA空运头程延误时间，第二项是机位空闲时间，（·）+表示当括号中的值大于零时等于括号中的值，否则等于零。约束条件 (2-75)和（2-76）是指派约束，分别表示本周期内到港的FBA空运头程必须且只指派一个停机位，以及每个停机位最多可指派一个FBA空运头程，式（2-77)表示到达FBA空运头程等待进入机位的时间不得长于A，式（2-78）是安全性约束，表示只有机型不比机位类型大的航班才可以指派给该机位。式（2-79）是决策变量的取值规定，式(2-80）和式(2-81) 是机位可分配的开始时刻的计算公式，J2中机位可分配的开始时刻应等于它当前 在位FBA空运头程的出港时刻加上最小安全间隔T，J。的机位可分配的开始时刻就是本分配周期的开始时刻To。

      可见，上述模型满足了所有基本约束。 假设一个指派周期中需指派n个FBA空运头程，共有m≥n个机位可指派，那么上述停 机位预指派问题共有nm个变量和2nm+m+n个约束条件。当n和m较大时，这是一个较大规模的0-1型整数规划问题，求解比较困难。可采用ILOG等优化软 件求解，也可以应用蚁群算法和遗传算法求解。想了解这些算法的读者可以参考有关文献（王凌，2001）。 如果机场根据FBA空运头程性质划分了专用停机坪，如分为国际FBA空运头程和国内FBA空运头程停机 坪、客运和货运停机坪，则只需将FBA空运头程按性质分成各子集，针对不同的子集和它们专用停机坪的机位资源，应用本章的方法进行指派即可。