（计算机软件与理论专业论文）多目标登机门分配问题的研究.pdf

多目标登机门分配问题的研究 专业： 计算机软件与理论 硕士生：关沛勇 指导教师：郭嵩山 摘要 多目标登机门分配问题是从经典的登机门问题加以扩展的一个新问题，传统的 登机门分配问题多只考虑一个目标，例如乘客等待的时间最小，乘客步行的距离最 小，机门的利用率最高等等。而在单目标规划得出的结果往往不尽如人意，因为决 策者往往是有多个目标的，例如希望机门利用率尽量高，同时乘客满意度也最高， 即等待时间或步行距离较小。本文正是考虑到这些现实因素，选择了两个比较经典 的目标来加以研究，即飞机分配冲突尽量小。乘客步行距离尽量小。 本论文将对多目标登机门问题进行较深入的研究，给出它在数学软件o p l 的模 型，给出禁忌搜索算法并给出相应的实验结果。 关键词：多目标规划，禁忌搜索，登机门分配问题 m u l t i 一0 b j e c t i v eg a t ea s s i g n m e n tp r o b l e m m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：p e i y o n gg u a n s u p e r v i s o r ：s o n g s h a ng u o a b s t r a c t t h em o g a p ( m u l t i o b j e c t i v eg a t ea s s i g n m e n tp r o b l e m ) i san e wv a r i a n to f t h e t r a d i t i o n a lg a t ea s s i g n m e n tp m b l e m t r a d i t i o n a lg a t ea s s i g n m e n tp r o b l e ma l w a y s c o n c e n t r a t e so i ls i n g l eo b j e c t i v e ，s u c ha sm i n i m i z ec u s t o m e r w a l k i n gd i s t a n c e ，m i n i m i z e c u s t o m e r w a l k i n gt i m e ，m a x i m i z eg a t ea s s i g n m e n t , e t c t h em o g a p d i s c u s s e di nt h i s a r t i c l ef o c u s e so nn o to n l ys i n g l eo b j e c t i v e ，b u tt w o ，o n ei st om i n i m i z et o t a lw a l k i n g d i s t a n c e ，t h eo t h e ri st om i n i m i z et h ec o n f l i c tp o s s i b i l i t yb e t w e e np l a n e s i nt h i sp a p e r , 1w i l ld i s c u s st h em o d e lu n d e rm a t h e m a t i c ss o f t w a r eo p la n dat a b u s e a r c ha p p r o a c h e x p e r i m e n tr e s u l t sa 咒g i v e na n dc o m p a r e d k e yw o r d s ：m u l t i o b j e c t i v e ，t a b us e a r c h 2 引言 多目标登机门分配问题足从经典的登机门问题加以扩展的一个新问题传统的 登机门分配问题多只考虑一个目标，例如乘客等待的时间最小，乘客步行的距离最 小，机门的利用率虽高等等。而在单目标规划得出的结果往往不尽如人意，因为决 策者往往是有多个目标的，例如希望机门利用率尽量高，同时乘客满意度也最高， 即等待时间或步行距离较小。本文正是考虑到这些现实因素，选择了两个比较经典 的目标来加以研究，即飞机分配冲突尽量小，乘客步行距离尽量小。 4 第1 章简介 对登机门分配问题，传统的研究主要集中在静态的分配上，即不考虑航班时间 的改变；目标主要包括有乘客总的步行距离，机门利用率等；采用的方法多是数学 规划法，把登机门分配问题转化为整数规划问题，混合整数规划问题等。 单目标的登机门分配问题已经是一个n p 难问题，多目标的登机门分配问题就更 难了，要找出最优解更不切实际，所以近来的研究开始注重贴近应用的需求，用一 些近代优化技术来找近似解，如遗传算法，模拟退火，禁忌搜索，模拟等。参考资料 1 1 考虑了两个目标：乘客总的步行距离和乘客总的等等时间，并通过转化合成一个 目标，并利用分支定界等技术加以优化。参考资料【2 】考虑了乘客总的步行距离和行 李的运输时间，并设计了一个启发式搜索算法来求解，结果跟c p l e x j j f i 以比较。参 考资料【3 】提出了一个模型来模拟机场的日常运行情况，可以作为算法试验的模型。 参考资料【6 】考虑最小化乘客的最小步行距离，并设计出了插入，交换和移动航班分 配等的算法来生成新状态，并应用到遗传算法，禁忌搜索算法等。参考资料【9 】是结 合贪心算法和禁忌搜索算法来优化两个目标：尽量满足航班，尽量减少乘客总的步 行距离。 登机门分配问题已经是现在机场核心规划问题之一，参考资料【4 】介绍了一个在 香港国际机场中运行的登机门分配软件，当中介绍了机场决策者的的多个目标。本 论文正是切合应用的需求，找出两个决策者比较关心的两个目标加以研究。 2 i 实际问题 第2 章问题描述 在一个机场中，登机门是很珍贵的资源，一般只有几十个，却要负责每天数以 千计的航班，如何有效利用登机门成了机场资源规划中的核心问题之。在登机门 资源规划当中，一般有两大类目标：一类是以提高资源利用率为目标的如满足尽 量多的航班，使用尽量少的登机门，或者让登机门的负荷尽量均衡等等；另一类是 以提高服务质量为目标的，如让乘客总的步行距离尽量小，让乘客总的等待时间尽 量小等。而且决策者们的目标也越来越多样多，单一目标已经不能满足要求，例如 决策者可能希望在满足所有航班的前提下尽量让顾客满意( 最小步行距离，最小等 待时间等) ，或者希望用最小的登机门满足航班需求并尽量减少航班的冲突。 本论文在众多的目标中选出比较有代表性的两个目标加以研究，一个目标是尽 量减少乘客总的步行距离，另一个目标是尽量减少航班直接的冲突。 2 2 问题的一般描述 本论文的问题可以简单概括为：机场要安排若干个航班到若干个登机门，每个 航班有一个要到达机场的时间窗口，分配各个航班到各个登机门，使同一登机门的 所有航班的时间窗口都没有重叠，并尽量满足两个目标，即尽量减少乘客总的步行 距离，和尽量减少航班直接的冲突。 f ：所有航班的集合 g ：所有登机门的集合 6 x i ：航班i 分配到的登机门 c 自：从航班i 转到航班j 的人数( c u + c j - o ) d ：从登机门i 到登机门j 的距离( d i j = d j i ，d i i = 0 ) ：航班i 和航班j 冲突的概率( 不妨设当i j 时跗= 0 ) m i n z 1 = ) - - 村村c 0 木比，彤 z 2 = 村肼助：蚵何 限制条件： 每个航班都分配到某个登记门； 钋配引同一个瞀加门的所有骷骄的时间宙口不重晷 说明：目标z l 中的总步行距离只考虑了转航乘客的总步行距离，即登机口直接的 距离，这个为了使表达式具有比较统一的表示。实际上还有登机门与机场出入口之 间的距离，不过我们可以把出入口看做没有飞机的登机v i ，那就可以转化为登机口 直接的距离，所以采用以上模型对算法来说没有本质的差别。 第3 章多目标的处理 多目标最优化跟单目标很不同的一点是，多目标的最优解不是一个，而是有很 多个。对于解空间里的任一个解s ，如果不存在另一个解s ，使得s 的各个分目标 都不比s 的相应分目标差，并且至少有一个更优的分目标，那么s 就是一个最优解。 对多目标的处理方法一般有两：k 类，一类是把多个目标化为单目标，另一类是 每次求解生成一个解的集合，然后跟决策者交互，然后牛成更合适的解集合，逐次 缩小解集合到最后得出决策者需求的解。作为本问题的一个初步研究，这篇论文采 用比较简单的方法，即把多个目标化为单目标。多目标化为单目标的常用方法有三 种，一种是采用目标函数z = f ( z l ，z 2 ，z n ) 把多个目标化为单个目标；一种是 把一个目标作为最终目标，其他目标转化为条件，这种方法有比较直观的意义，例 如对于本论文的问题，要求在航班冲突概率满足一定要求的前提下，使乘客总的步 行距离尽量小，就是把冲突概率的目标转化为条件并把总步行距离作为日标的方法： 还有一种方法是让决策者先确定一个目标，然后以每个可行解到那个目标的距离作 为目标函数，目标是这个距离尽量小，就是尽量靠近决策者的目标。 本论文采用第二种方法，把目标z 2 转化为条件，目标z l 作为最终目标。3 1 直接采用这种方法，3 2 是它的一个变种，采用罚函数的形式，本质是一样的。 3 1 目标化为条件 目标化为条件的方法就是把一个目标作为最终目标，其他目标转换为条件。对 这个登记门分配问题，把z l 作为最终目标，把z 2 转化为条件，其意义就是在z 2 满足一定条件的情况下，z l 的最优值是多少。o p l 编程将会用这个模型。 给定z 2 的上限m a x z 2 ，那么具体的模型是： m i n z l = y 肼脚c i j 4 巩， 限制条件： 每个航班都分配到某个登记门。 分配到同一个登机门的所有航班的时间窗口不重叠 z 2 = zi ；f ej ；f 幽；q e i j m a 7 7 9 ， 那么z = z 1 + m ( z 2 一m a x z 2 ) ， 其中m 是一个足够大的数。 即，定义z = z 1 + m * m a x o ，z 2 m a x z 2 定义罚函数模型为： m i n z 限制条件： 每个航班都分配到某个登记门； 分配到同一个登机门的所有航班的时间窗口不重叠。 9 第4 章邻域的生成 禁忌搜索在框架上已经有比较成熟稳定的模型，而应用禁忌搜索算法的难点和 重点是结合具体问题设计高效和有效的邻域牛成算法，可以说，邻域的牛成算法对 禁忌搜索算法来说具有决定性的意义。 本算法采用的邻域生成算法有两类，k 迹变换和k 环变换，这两类变换都归结为 若干个m o v e i j 操作。4 1 和4 2 简要介绍这两类变换，4 3 论述状态的记录，4 4 定 义对一个状态进行m o v e i j 操作生成新的状态，4 5 和4 6 详细介绍这两类变换如何 利用m o v e i j 来实现。 4 1k 迹变换简介 k 迹变换操作概述： ( 1 ) 选择k 个不同的航班f 1 ，但，n ( ， 使得f j 和f i + l 冲突f 即时间窗口有 重叠) ，i - l ，2 ，k l 。设k 个航班所在的登机门分别为g l ，9 2 ，醇， 另外再选择一个登机门g k + l ，然后把f i 从g i 移到百+ i ，i = l ，2 ，k 。 图1 ：3 迹变换例孑 1 0 图2 ：3 迹变换例子 ( 2 ) 若这k 个航班在以上移动中时间有相互冲突( 只算这k 个，不算其他的) ，则新 状态不合法，舍弃新状态。 ( 3 ) 在这k 个航班移动后，除这k 个航班以外的航班中，那些与这k 个航班有冲突 的航班的集合记为c o n f l i c t ，把c o n f l i c t 中所有航班随机排序，按序调整每个航班： ( 3 1 ) 在它不影响其他已安排的航班的条件下可分配的登机门中选一个使目标 值z 增加较小的一个，更具体的说， 是这样分配登机门的，当前中间状态 中选出一个可分配的使z l 增加最小的登机门g ) 【，若把该航班重新分配到g x 后的状态o 中，有z 2 ( o ) m a x z 2 ，则把该航班分配到g x ，否则z 2 ( o ) m o x z 2 ， 那么对当前状态o ，选一个可分配的使z 2 增加最小的登机门 g y ， 把航班分配到g y 。这样就能使z 较小( 当然不一定是最小的， 但在 z 2 一 m a x z 2 ， 那么对当前状态0 ，选一个可分配的使z 2 增加最小的登机门 g y ，把航班分配到g y 。这样就能使z 较小( 当然不一定是最小的， 但在 z 2 m a x z 2 的条件下是最小的) 了。往下会对以上这个分配方法有更精确的描 述。 ( 3 2 ) 若当前航班没有可分配的登机门，则新状态不合法，舍弃之。 图6 ：3 环变换例子 4 3 状态的表示 状态的表示就是记录一个状态的所有信息，从编程的角度就是用来表示一个状 态用到的数据结构，设计这些信息结构的目标是使状态转换能更高效的实现。以下 先说明一些符号，然后再具体提出怎么记录状态信息。 ( 一) 符号说明 为了使描述更简洁，我们利用图论概念来描述。 首先，定义一个表示转航的赋权有向图g t ( v t ，盯) ： v t 为f ，即所有航班； 设e t = ，e r e e ti f f c o 不为0 ，即从航班i 到航班j 有人转航，且e t 赋权 c 。 记v t i 为所有以点i 为始点的边的终点的集合。 记v t i 为所有以点i 为终点的边的始点的集合。 再定义一个冲突无向图g c c v c ，e c l ： v c = f ，即所有航班； ( i ，j ) e c i f f 航班i 与航班j 冲突。 记v c i 为所有与顶点i 相连的点的集合。 那么目标z 1 可以重定义为： z 1 = 时e 肿c i j 术， 根据实际情况，g t 大多是稀疏图，即o ( i e t i f o ( i v t i ) ，用上式计算z l 效率更高。 ( 二) 状态的表示 以下逐一说明表示一个状态的所有信息： ( 1 ) o ：一个状态，表示对各个航班的分配，可用一个f 到g 的映射表示。 ( 2 ) x i ( o ) ：在状态o 中分配给航班i 的登机门。 ( 3 ) p z b j ( o ) ：把。中的航班i 分配到登机门j 后得到新状态记为o ，那么 p z i i j ( o1 定义为如下值 咫狄回= ( c i k 木上九( 盯讶( ) + ( 魄术上) 皿( 伽( ) 女肺t p 丁f 形象的说，p z l i j ( o ) 说表示吧状态o 中的航班i 分配到登机门j 后的新状态中 z 1 的与航班i 有关的部分。p z l 是p a r t i a lz 1 的意思。 ( 4 ) p z 2 0 ( o ) ：把。中航班j 分配到登机门j 得到o ，那么p z 2 0 ( o ) 定义为如下 值 p z 2 i j ( t r ) =( p i k + p k i ) k e f 且x k ( 口) = x i ( 口 形象的说，p z 2 i j ( o ) 表示吧状态o 中的航班i 分配到登机门j 后的新状态中z 2 的与航班i 有关的部分。p z 2 是p a r t i a lz 2 的意思。 ( 5 ) s i ( o ) ：状态o 中可以不冲突地分配给航班i 的所有登机门的集合。 ( 6 ) p 1 s i ( o ) ：s i ( o ) 中p z lo ( o ) 最小的登机门。p l s i ( o ) 在算法实现的时候用堆 h e a p l ( o ) 来维护。p 1 s 将会在往下定义的k 迹变换和k 环变换作为参考信息。 ( 7 ) p 2 s i ( o ) ： s i ( o ) 中p z 2 i j ( o ) 最小的登机门。p 2 s 。( o ) 在算法实现的时候用堆 h e a p 2 i ( o1 来维护。p 2 s 将会在往下定义的k 迹变换和k 环变换作为参考信息。 ( 8 ) c o u n t i j ( o ) ： 表示状态o 下分配到登机门j 中的与航班i 有时间冲突的 航班数目。 ( 9 ) z k o1 ：表示状态。的目标值z l 。 ( 1 0 ) z 2 ( o ) ：表示状态o 的目标值z 2 。 4 4m o v e i j 变换 ( - - ) m o v e i j 变换算法 m o v e i j 操作简单来说就是把航班i 重新分配到登机门j ，并调整其他与航班i 冲突的航班使各个航班的分配没有冲突。下面给出m o v e i j 操作的算法描述： 其中o = m o v e i ( o ) ，是对o 作如下变换： ( 1 ) 从当前目标值计算新的目标值，新的目标值就是当前目标值减去与航班i 有关 的部分再加上分配到新位置后与航班i 有关的部分： z ko ) 2 z l ( o ) 一p z l - rx i ( a ) ( o ) + p z i i j ( o ) z 2 ( o ) = z 2 ( o ) 一p z 2 i x i ( a o ) + p z 2 i j ( o ) ( 2 ) 分配航班i 到登机门j x i ( o ) = j ( 3 ) 调整p z l f o r e a c h 航班k i n v t i 并且f o r e a c h 登机门li n g 。 p z l k l ( o ) 2 p z i k i ( o ) + c p ( o i l d 。i t 。) 维护h e a p lk ( o ) 。 ) f o r e a c h 航班k i n v t i 并且f o r e a c h 登机门l i n g p z l k i ( o ) = p z lk l ( o ) + c k i + ( d l i d l ，x i ( 。) ) 维护h e a p lk ( o1 。 ) ( 4 ) 调整p z 2 f o r e a c h 航班k i n v p z 2 k j ( o ) = p z 2 k j ( o ) + w + ( p k i + p i k ) p z 2 kx i ( 。) ( o ) = p z 2 k ，x i ( 。) ( o ) _ w + ( p k i + p i k ) 维护h e a p 2 k ( o1 。 ( 5 ) 调整c o u n t f o r e a c h 航班k i n v c i c o u n t k j ( 0 ) = c o u n t q ( d ) + 1 i f c o u n t k j ( o ) = it h e n s k ( o ) = s k ( o ) 一登机门j 维护h e a p l k ( o ) 和h e a p 2 k ( o ) c o u n t k x i ( 。l ( o ) = c o u n t k f 。) ( o ) 一1 i f c o u n t kx i ( 。) ( o ) = 0 t h e n s k ( o ) = s k ( o ) + 登机门x i ( o ) 维护h e a p lk ( o ) 和h e a p 2 k ( o ) ( 6 ) 更新p i s 和p 2 s f o r e a c h 航班k i n v p l s k ( o ) 置为h e a p l “o ) 的最小值对应的登机门； p 2 s k ( o ) 置为h e a p 2 “o ) 的最小值对应的登机门； ) ( 二) m o v e i j 变换算法复杂度分析 首先指出以上每次堆的调整操作的复杂度为1 9 | g 。而m o v e i j 变换算法复杂度是以 下各个步骤复杂度的和： 步骤( 1 ) 和( 2 ) 复杂度为常数； 步骤( 3 ) 复杂度为( i v t i h v t i 州g l + l g i g | ； 步骤( 4 ) 复杂度为i v r l g l g i ； 步骤( 5 ) 复杂度) b i v c i l * l g l g i ； 步骤( 6 ) 复杂度为常数； 因此，总的复杂度为o ( ( i v t i i * i g i + i v t i l + i g l + l v l + l w c i l ) + i g g i ) 如果把登机门的数目看作常数，那么复杂度简化为o ( i v l ) 。 4 5k 迹变换 k 迹变换的算法如y ( f i ，f 2 ，f k ，g ) 变换步骤如下： ( 1 ) 选择k 个航班f i ，f 2 ，丘，设当前它们所在的登机门分别为g i ，9 2 ， g k ，另外再选出一个登机门g k + i 。 ( 2 ) 分别作变换m o v e n ，9 2 ，m o v e f 2 ，o ，m o v e f k ，g k + l a ( 3 ) 在( 2 ) 的变换后，若f i ，6 ，f ；c 有冲突，则结束，新状态不合法，舍弃 之，否则： ( 4 ) 对所有与f i ，b ，丘有冲突的航班按随机的顺序逐一调整，调整方法如下： 设航班f 要调整，那么 ( 4 1 ) 若s f ( o ) 为空，则结束，新状态不合法，舍弃之。 ( 4 2 ) 否则s f ( o ) 不为空，这时p l s o ) 和p 2 s do ) 有定义，那么 若z 2 州o v e fp l s r 。) ( o ) ) m a x z 2 时， 即z 2 ( o ) 一p z 2 f , 柚。) ( o ) + p z 2 fp i s t 【。) ( o ) m a x z 2 时， 进行m o v e r , p 嘲。1 操作； 否则进行m o v e r p 2 s n 。操作。 这是为了变换以后的新状态目标值z 较小。 4 6k 环变换 k 环变换算法与k 迹变换算法类似，不同的地方在于k 环变换的第k 个航班不是分 配到“l ，而是f i 。 ( 1 ) 选择k 个航班f i ，f 2 ，f k ，设当前它们所在的登机门分别为g l ，9 2 ， g k o ( 2 ) 分别作变换m o v e n ，9 2 ，m o v e e ，日，m o v e , ，时1 ，m o v e , 、g i 。 ( 3 ) 在( 2 ) 的变换后，若，f 2 ，丘有冲突，则结束，新状态不合法，舍弃 之，否则： ( 4 ) 对所有与f i ，f 2 ，f k 有冲突的航班按随机的顺序逐一调整，调整方法如下： 没航班f 要调整，那么 ( 4 1 ) 若s f ( o ) 为空，则结束，新状态不合法，舍弃之。 ( 4 2 ) 否则s f ( o ) 不为空，这时p l s o ) 和p 2 s f ( o ) 有定义，那么 若z 2 ( m o v e fp l s f ( 。) ( o ) ) m a x z 2 时， 即z 2 ( o ) 一p z 2 f 趣。o ) + p z 2ep l s f ( 。) ( o ) m a x z 2 时， 进行m o v e bp l s f t 。1 操作； 否则进行m o v e r p 2 s r 。操作。 这是为了变换以后的新状态目标值z 较小。 第5 章禁忌搜索算法 禁忌搜索算法是在邻域搜索算法基础上加以改良的算法，邻域搜索算法在每次 生成的邻域中找一个最优的作为新状态，但禁忌搜索算法会禁忌某些步骤或操作在 选用后的若干轮跌到中不再被选用，这样能有效的避开局部最优解。以下先提出一 个生成初始解的算法，然后结合以上邻域牛成算法提出禁忌搜索算法。 5 1 初始可行解的生成 初始可行解的生成使用随机方法： 对所有航班按时间窗1 3 的开始时间b e g i n i 从小到大排序，然后逐一分配登机门 分配的方法是在当前可分配的所有登机门中随机分配一个登机门。 若某个航班没有可分配的登机门，则失败，原问题无解。 下面证明如果按这个算法不能构造可行解，那就没有可行解了。 证明： 设按这个算法分配第一个不能分配登机门的是航班f ，b e g i n f 为航班f 的时间窗 口开始时间，i t ( b e g i n 旧，b e g i n 【日+ d e l t a ) 这d x 段时间内，d e l t a 很小， 肯定是m 个登机门都由f 之前的m 个航班占用，加上f 就有m + 1 个航班，根据容 斥定理，它们分配到m 个登机门肯定至少有2 个冲突。因此，若干以上的随机算 法不能生成可行解，那么原问题就无解。 5 2 禁忌搜索过程 在第四章介绍了k 迹变换和k 环变换，而在这里我们的搜索算法只利用1 迹变 换，2 迹变换和2 环变换来生成领域。具体的步骤如下： 循环搜索2 0 次，把2 0 次的结果的最小值作为最终解，其中每次搜索的步骤如下： b e g i n 用5 1 的算法生成初始可行解o 。 02o0 w h i l e 不满足结束条件d o b e g i n ： 对每个没有被禁忌的航班i ， 。 若艺( m o v e i p i s i t 。) ( o ) ) m a x z 2 ，令j = p 1 s i ( o ) ，否则令j = p 2 s 。( o ) ； 若j 存在且j x ( o ) ，则生成新状态卜t r a c e ，( o ) ： 令k 为一个随机的登机门，并且k 不属于s i ( o ) ，生成新状态 卜t r a c e 。k ( o ) ： 电迹变换 ： 对每个航班i ，随机选取与i 冲突的航班j ，令g 为随机的一个登机门，生成新 状态2 - t r a c e ( o ) ： ： 对每个航班i ，随机选取与i 冲突的航班j ， 生成新状态2 - l o o pi ，( o ) ； o = 合法新状态中z 值较小的某个o 禁忌某些航班s ，具体的说， 若新状态由卜t r a c e ，。( o ) 而来，则禁忌i ， 若由2 - l o o p 。( o ) 而来，则禁忌i 和j ， 若由2 - t r a c e 。( o ) 而来，则禁忌i 和j ； 更新本次搜索的最优解 e n d 更新全局最优解 e n d 说明： ( 1 ) 以上进行l o o p 2 和t r a c e 2 的变换的时候，允许被禁忌的航班进行这两个变换 这是为了能逃开局部最优解。 ( 2 ) 禁忌搜索结束条件：2 s q r t ( n + m ) 步没有获得本次搜索的更优值则结束。其中 n 为航班数目，m 为登机门数目。 ( 3 ) 禁忌长度：s q r t ( n + m ) 。 第6 章实现 在本章中，我们将生成小，中，大二种规模的数据，以检验本论文提出的算法 的优劣。 6 1 数据生成 ( 一) 符号说明 x 、u a ，b 表示x 是等概率的在a 到b 这( b a + 1 ) 个自然数中选一个。 n ：航班数目 m ：登机门数日 b e g i n i ：航班i 的时间窗口的开始时间 e n d i ：航班i 的时间窗口的结束时间 d i j ：登机门i 和登机门j 之间的距离 c i j ：航班i 和航班j 之间的转航人数 p i 儿j ：航班i 和航班j 冲突的概率 ( 二) 小规模数据s e t a b e g i n i 、u 0 ，2 0 0 e n d i u b e g i n i + 1 0 ，b e g i n i + 2 0 d i j = d j i u 1 0 ，1 0 0 ，i ! = j d i i = 0 ，i = l ，2 ，m 对所有航班i 和航班j 如果e n d i b e g i n j ，即航班i 的结束时间不比航 班j 的开始时间迟，则，c i j 、u 0 ，1 0 ，否则c i j = 0 若i j 且航班i 和航班j 有时间冲突，则p i j = 1 若i = j 则p i j = o p i j 保留3 位小数 m a x z 2 的生成： 用5 1 中的算法随机的生成一个可行解，对这个可行解计算其z 2 ，t , z 2 作为 m a x z 2 ，并取3 位小数， 其中t 为 1 ，2 中一个随机的实数。 分别取1 2 ，i n 为如下值 l o ，3 ；1 0 ，3 ；1 0 ，3 ；1 l ，3 ；1 1 ，3 ； 1 1 ，4 ；1 1 ，4 ；1 2 ，4 ；1 2 ，4 ：1 2 ，4 其他变量按上面说的方法生成十组数据，分别记为s e t a l ，s e t a 2 ，s e t a l o ( 三) 中规模数据s e t c b e g i n i 、t l 0 ，3 0 0 e n d i u b e g i n i + 1 0 ，b e g i n i + 2 0 d i 儿j = d j i u 1 0 ，1 0 0 ，i ! = j d i i = 0 ，i = l ，2 ，i l l 对所有航班i 和航班j 若e n d i b e g i n j ，即航班i 的结束时间不迟于 航班j 的开始时间，那么c i 儿j 、u o ，1 0 ，否则c i j = 0 若i j 且航班i 和航班j 有时间冲突，则p i j = 1 若i = j 则p i j = 0 pe i j 保留3 位小数 m a x z 2 的生成： 用5 1 的算法随机的生成一个可行解，对这个可行解计算其z 2 ，用t z 2 作为 m a x z 2 ，并取3 位小数，其中t 为 1 ，2 中一个随机的实数。 分别取n ，m 为如下值 2 l ，5 ：2 2 ，5 ；2 3 ，5 ；2 4 ，5 ；2 5 ，5 ；2 6 ，6 ；2 7 ，6 ：2 8 ，6 ；2 9 ，6 ：3 0 ，6 其他变量按上面说的方法生成，得到十组数据，分别记为s e t b l ，s e t b 2 ，s e t b l o ( 四) 大规模数据s e t c b e g i n i 、“0 ，2 4 * 6 0 d i j = d j i u 1 0 0 ， d i i = 0 ，i = 1 ，2 ， = l 吾l 加 m 对所有航班i 和航班j 若e n d i b e g i n j ，即航班i 的结束时问不迟于 航班j 的开始时间，那么c i j “0 ，i 0 0 ，否则c i 儿j = o 若i j 且航班i 和航班j 有时间冲突，则p i 儿j = l 若i = j 则p i j = 0 p i j 保留3 位小数 m a x z 2 的生成： 用5 1 的算法随机的生成一个可行解，对这个可行解计算其z 2 ，用t , z 2 作为m a x z 2 ， 并取3 位小数，其中t 为 i ，2 中一个随机的实数。 分别取n ，m 为如下值 7 2 ，1 5 ；7 4 ，1 5 ；7 6 ，1 5 ；7 8 ，1 5 ；8 0 ，1 5 ： 9 2 ，2 0 ；9 4 ，2 0 ；9 6 ，2 0 ；9 8 ，2 0 ；1 0 0 ，2 0 其他变量按上面说的方法牛成得到十组数据，分别记为s e t c l ，s e t c 2 ，s e t c i 0 6 2o p l 建模 以下模型在o p l 软件运行通过。 i n ta f l i g h t s = ； i n tb f l i g h t s 】_ ； i n tc f l i g h t s ，f l i g h t s l - ； f l o a t + d g a t e s ，g a t e s 】= ； f l o m + p f l i g h t s ，f l i g h t s 】2 ； j n t m = 1 0 0 0 0 0 0 ； v a r i n t x f l i g h t s ，g a t e s 】i n0 1 ； v a ri n ty f l i g h t s ，f l i g h t s 】i no 1 ； v a r i n t z f l i g h t s ，f l i g h t s ，g a t e s ，g a t e s 】i n 0 1 ； m l n l m l z e ( s u m ( ii nf l i g h t s ) s u m ( ji nf l i g h t s ) s u m ( 1 ( i ng a t e s ) s u m ( 1i ng a t e s ) c i ，j 】+ d 【l 【，l 】幸z i ，j ，k ，l 】) s u b j e c tt o ( s u m ( ii nf l i g h t s ) s u m ( ji nf l i g h t s ) s u m n ( i ng a t e s ) “i ，j 】+ z 【i ，j ，k ，k 】) _ m a x z 2 ； f o r a l l ( ii nf l i g h t s ) ( s u m ( ki ng a t e s ) x i ，k 】产l ； f o r a l l ( ii nf l i g h t s ) f o r a l l ( ji nf l i g h t s ) f o r a l l ( ki ng a t e s ) f o m l i ( 1i ng a t e s ) z 【i ，j ，k ，l 】 2 x i ，k 1 ； f o r a l l ( ii nf l i g h t s ) f o r a l l ( ji nf l i g h t s ) f o m l l ( ki ng a t e s ) f o r a l i ( ii ng a t e s ) z 【i ，j ，k ，l 】 - x d ，l 】； f o r a l l ( ii nf l i g h t s ) f o m l i ( ji nf l i g h t s ) f o r a l i ( ki ng a t e s ) f o r a l l ( ii ng a t e s ) x i ，k + x d ，l 】一l 0 ； f o r a l l ( ii nf l i g h t s ) f o m l i ( ji nf l i g h t s ) b 【i 】- a u - ( 1 y i ，j 】) + m 2 0 ； 6 3 实验结果 禁忌搜索全部达到全局最优解，并且效率比o p l 高很多。 表l 数据 规模( n x m ) o p l 最优解o p l 时间禁忌解禁忌时间 s e t a l 1 0 3 3 3 4 92s3 3 4 90 0 6s s e t a 2 l o 3 6 4 3 34s6 4 3 30 0 4s s e t a 3 1 0 3 9 4 9 34s9 4 9 30 0 3s s e t a 4 l l 3 4 6 8 07s4 6 8 00 0 4s s e t a 5 l l 3 3 9 3 12s3 9 3 10 0 4s s e t a 6 1 l 4 4 4 3 93 2s4 4 3 90 0 7 is s e t a 7 l l 4 5 0 9 8 2 2s 5 0 9 80 0 6s s e t a 8 1 2 4 4 4 5 98 9s4 4 5 90 0 6s s e t a 9 1 2 4 7 7 6 08 ls7 7 6 00 0 6s s e t a l 0 1 2 4 7 1 4 68 2s7 1 4 60 0 8s ( 二) s e t b 用o p l 运行半小时所得结果跟禁忌搜索的结果比较。 表2 数据 规模( n x m )o p l 解0 p l 时间 禁忌解禁忌时间 s e t b l 2 1 5 3 3 0 1 91 8 0 0s2 8 1 3 9o 5 2s s e t b 2 2 2 5 3 9 4 0 81 8 0 0s1 7 2 4 30 5 9 ls s e t b 3 2 3 x 5 1 7 6 7 31 8 0 0s1 5 1 6 30 5 9 ls s e t b 4 2 4 5 2 7 9 2 6 1 8 0 0s 2 0 7 5 60 7 2 ls s e t b 5 2 5 5 6 2 7 4 81 8 0 0s5 2 2 4 40 7 8 ls s e t b 6 2 6 x 6 5 6 3 9 5 1 8 0 0s2 9 0 6 l 1 1 9 2s s e t b 7 2 7 6 4 9 9 5 21 8 0 0s3 5 9 9 01 7 4 3s s e t b 8 2 8 6 7 6 8 0 81 8 0 0s4 6 2 9 41 7 1 3s s e t b 9 2 9 x 6 3 1 9 8 81 8 0 0s2 6 6 3 61 7 4 2s s e t b l 0 3 0 6 7 9 6 2 7 1 8 0 0s5 2 4 9 3 1 8 7 3s ( 三) s e t e o p l 在可接受的时间内不能找出一个可行解。 表3 数据 规模( n x m l 禁忌解禁忌时间 s e t e l 7 2 1 5 4 3 8 6 8 0 5 78 3s s e t e 2 7 4 1 5 3 7 1 3 8 3 7 l9 4s s e t 0 3 7 6 1 5 5 6 1 8 5 2 1 31 0 4s s e t c 4 7 8 1 5 3 5 5 0 0 8 9 21 3 4s s e t 0 5 8 0 1 5 4 81 2 5 5 9 31 3 2s s e t c 6 9 2 2 0 8 0 1 9 6 6 3 l2 9 2s s e t 0 7 9 4 x 2 0 8 3 6 8 7 0 3 03 5 0s s e t e 8 9 6 2 0 8 8 8 8 7 6 1 3 3 1 5s 【s e t 0 99 8 2 0 7 9 3 1 4 4 6 23 9 7s s e t e l 0 1 0 0 2 0 9 4 0 2 3 8 1 53 3 9s ( 四) 实验结论 本论文的算法的效率比较高，对中小规模数据接近或达到最优解，最大规模数 据也在可接受的时间内求出结果。 7 1 总结 第7 章结束语 本论文提出了一个禁忌搜索算法求解多目标登记门分配问题，该禁忌搜索算法 邻域牛成比较高效，而且生成的邻域尽量保持较优特性，这样就可能减少了迭代步 数。这个方法可以很容易的修改并适应到经典的登机门分配问题，或其他多目标登 机门分配问题。跟o p l 软件比较的实验结果表明该算法效率比较高，效果比较好。 本文的创新与独到之处有： e 1 提出了一个新的问题，即在登机门分配问题中，既考虑乘客总的步行距离， 也考虑航班直接的冲突。 口 结合多目标登机门分配问题提出了一个高效的邻域生成算法。 口 结合多目标登机门分配问题设计了一个禁忌搜索算法。 7 2 进一步研究的方向 进一步的研究可以考虑遗传算法，模拟退火算法在这个问题的应用，并跟本禁 忌搜索算法作比较；也可以考虑把这个禁忌搜索算法和其邻域生成算法应用到其他 登机门分配问题。 参考文献 【l 】s h a n g y a oy a h ，c h e n n m i n gh u o ，o p t i m i z a t i o no fm u l t i p l eo b j e c t i v eg a t e a s s i g n m e n t s t r a n s p o r t a t i o n r e s e a r c hp a r t a3 5 ( 2 0 0 1 ) 4 1 3 4 3 2 【2 a l lh a g h a n ia n dm i n - c h i n gc h e n ，o p t i m i z i n gg a t ea s s i g n m e n t sa ta i r p o r t t e r m i n a l s ，t r a n s p nr e s - a ，v 0 1 3 2n o 6 ，p p 4 3 7 4 5 4 ，1 9 9 8 3 1s h a n g y a oy a n ，c h i - y u a ns h i e h , m i a w j a n ec h e n ，as i m u l a t i o nf r a m e w o r kf o re v a l u a t i n ga i r p o r t g a t ea s s i g n m e n t s ，t r a n s p o r t a t i o nr e s e a r c hp a r ta3 6 ( 2 0 0 2 ) 8 8 5 8 9 8 【4 a n d yh o nw a ic h u n ，s t e v eh oc h u e nc h a r t , f r a n c i sm i n gf a it s a n ga n dd e n n i sw a im i