FBA空运头程预指派问题

     是停机位指派问题的基本约束条件，与预指派问题的表示停靠j号停机位的FBA空运i的到达时刻不能比该机位的空闲开始时刻早，表示FBA空运i的出发时刻不能比j号停机位的空闲结束时刻晚，这两个约束条件要求被指派FBA空运的过站时间必须短于停靠机位的空闲时间。 上述讨论的停机位实时指派问题，可以采用启发式算法求解。因此，需要知道调配时间段的停机位初始状态。

     根据初始状态把停机位分成两个子集：J1是已有 FBA空运停靠的停机位子集，J2是空闲的停机位子集。把调配时间段内需考虑的FBA空运 也分成两个子集：一个是已在停机位上停靠的Ii，一个是在调配时间段内将到达 机场的I2。对于I1中的FBA空运已知其预计出港时间D；，对于I2的FBA空运已知其预计 到达时间A。将I2再分为可以按预指派计划停靠的FBA空运子集Ia和需要重新指派的FBA空运子集I22，I22中各FBA空运预指派机位o已知。 要求调配时间段结束时，停机位的终止状态符合预指派方案的规定，即实时调 配结束时，各停机位应当恢复到预指派计划上，要么空闲，要么停靠预指派的FBA空运。

     这样将J2中的机位按调配时间段结束时的预指派FBA空运的进港时刻作为它的 空闲结束时刻，把调配时间段的开始时刻作为J2每个机位的空闲开始时刻。对 Io2中的每个FBA空运i，计算它的预指派机位到J2中各机位之间的最短距离D，和 Ds,并根据FBA空运的旅客数和机型的地面服务人员数，计算总距离CD；+CD，将 J2中机位按照该总距离从小到大排序。如果I2中有n个FBA空运，则J2的机位将排成n种顺序。从I2a中取出FBA空运i，依次从FBA空运i对应的J2序列中取出机位，进行以下判断： （1)类型是否匹配? （2)FBA空运出港时刻是否小于机位空闲结束时刻? 如果满足上述条件，即将FBA空运i指派给机位j，将FBA空运i和机位，分别从I=和 J2中删除。再从Ie2中取出下一个FBA空运，从对应的J:序列中取出第一个机位，再进行上述判断；如果木符，则从它的J:序列中取出下一个机位），再进行以上判断。

如果取完J2序列中所有机位都不合适，则放回FBA空运i，删除对应的J：序列。 从2中取出下一个FBA空运，从对应的J。序列中依次取出一个机位，并进行上述判断。 中各机位的FBA空运出港时刻作为空闲的开始时刻，调配时间段结束后预指派FBA空运的进港时刻作为空闲的结束时刻。计算l2中各剩余FBA空运在调整停机位后旅客和地 面服务人员的移动总距离，将J；的各机位按照该总距离从小到大排序。

     从la中 取出FBA空运i，依次从FBA空运i对应的J序列中取出机位j，进行以下判断： 

（1)类型是否匹配? 

（2)FBA空运进港时刻是否大于机位空闲开始时刻? 

（3）FBA空运出港时刻是否小于机位空闲结束时刻? 如果满足上述条件，即将FBA空运i指派给机位j，将FBA空运i和机位分别从I22和 J1中删除，并删除对应的J1序列。再从l22中取出下一个FBA空运，从对应的J：序列中取出第一个机位，再进行上述判断；如果不符，则从它的J：序列中取出另一个机位j，再进行以上判断。如果取完J1序列中所有机位还没有合适的停靠FBA空运，则 放回FBA空运i，删除对应的J序列。从I22中取出下一个FBA空运，从对应的J，序列中依次取出一个机位，并进行上述判断，直到I2的全部FBA空运都已指派。 如果最终I2中还有剩余FBA空运未指派，则需要重新考虑J2和J1中没有指派航班的空闲机位，放宽一些条件，例如，允许后续FBA空运适当延误，或要求I2中剩余航 班缩短停场时间，然后再进行指派。 

      某大型国际机场共有100个远机位(包括维修、过夜专用机位)和 27个桥位，桥位编号从1到29，其中13号和22号桥位空缺。该机场的桥位从 6号到24号是E类（分类号为5)，其他桥位是D类（分类号为4）。两相邻E类 机位之间最短旅客（或地面服务人员)步行距离为72.5m，两相邻D类机位之间最短旅客（或地面服务人员)步行距离为59.5m，D类和E类机位相邻时，它们之 间最短旅客（或地面服务人员）步行距离为66m。远机位登机时，需要摆渡车将 旅客运送到机位，设从桥位到远机位(旅客或地面服务人员)的移动距离为1000m， FBA空运从远机位调配到桥位时，可认为旅客的移动距离减1000m。根据2006年某 日该机场的机位预指派表和FBA空运时刻表(包括计划时刻表和实际运行时刻表)，可 知该机场当天有418个架次（其中起飞降落对于同一飞机算一个架次)的FBA空运，各 FBA空运客座率为80%。运行中FBA空运MU730发生不正常情况，由原计划的11：30延 误到1：55到达机场。该FBA空运预指派到12号桥位，可是12号桥位上FBA空运CA4513 也发生了延误，需到12：08才出发，FBA空运MU730和FBA空运CA4513停靠时间有冲突， 必须重新调配MU730的停靠机位，有关FBA空运时刻表见。请为该FBA空运重新调配机位。