求解动态多跑道飞机着陆问题的模因算法

Journal of King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com求解动态多跑道飞机着陆问题的模因算法Ghizlane Bencheikha，*，Jaouad Boukachourb，Ahmed El Hilali Alaouica法律、经济和社会科学系，B.P. 3102，Toural，梅克内斯，摩洛哥b勒阿弗尔大学，5 rue Boris Vian，76610 Le Havre Cedex，法国c科学和技术学院，B.P. 2202，Route接收日期：2014年9月13日;修订日期：2015年6月16日;接受日期：2015年9月8日2015年11月2日在线发布摘要飞机着陆问题（ALP）是指在考虑不同操作约束的情况下，通过为每架飞机分配一个着陆时间和一条特定的跑道，来调度飞机在机场可用跑道这对于空中交通管制员来说是一项复杂的任务，特别是当进入雷达范围的飞机流是连续的并且飞机的数量先验未知时。本文研究了随着时间的推移，新飞机出现时ALP的动态版本，这意味着以前的飞机的着陆应该重新调整。为了解决这个问题，我们提出了一个模因算法相结合的蚁群算法和局部启发式。©2015作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。 这是CC BY-NC-ND许可下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍当飞机（i）进入机场的雷达视野（在出现时间ai）时，空中交通管制员的责任是为该飞机确定适当的路径、跑道和着陆时间（ti）。该着陆时间必须尽可能接近于航空器的优选着陆时间，称为目标着陆时间（tai），其对应于预定的着陆时间。*通讯作者。电子邮件地址：ghizlane_bencheikh@yahoo.fr（G.Bencheikh），jaouad. univ-lehavre.fr （ J. Boukachour ） ， ahmed.fst-usmba.ac.ma（A.El Hilali Alaoui）。沙特国王大学负责同行审查如果飞机以其巡航速度飞行，飞机可以着陆的时间，该巡航速度是飞机的最经济速度，并且它对应于向乘客宣布的时间。着陆时间（ti）必须属于由最早着陆时间（ei）和最晚着陆时间（li）界定的时间窗口最早着陆时间对应于如果飞机以其最快速度飞行（这对于飞机来说是不经济的）时飞机可以着陆的时间，而最晚着陆时间取决于其自身的增碳剂。此外，由于着陆飞机产生的湍流，还这些考虑在两架飞机的着陆之间强加了间隔时间。该最小分离时间取决于飞机类型，并且对于不同的成对飞机可能有所不同。预定着陆时间与目标着陆时间的任何偏差都会在机场造成干扰。为了更好地控制它，惩罚成本与飞机i的目标着陆时间的任何提前（eri）或拖后（tri）相关联。http://dx.doi.org/10.1016/j.jksuci.2015.09.0021319-1578© 2015作者。制作和主办由爱思唯尔B.V.代表沙特国王大学。这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词飞机动态着陆问题蚁群优化;局部搜索;元搜索求解飞机着陆问题99在动态版本的飞机着陆问题中，随着时间的推移会出现新的飞机。这意味着，随着时间的推移，降落的飞机被移除，新出现的飞机被添加，并且定期执行重新调度。被安排在足够接近当前时间降落的飞机被阻止重新安排;这由称为“冻结时间”（fz）的间隔表示：当计划的飞机降落时间位于该时间窗口内时，它被冻结，并且不能重新安排。2. 以前的工作飞机着陆问题引起了许多作者的兴趣，但很少有论文涉及该问题的动态情况，那些治疗的静态案子Ernst等人（1999）提出了一种利用单纯形法计算飞机着陆时间的精确算法.该方法基于飞机之间的部分排序，其允许固定排序变量。该算法也被用于本文提出的其他两种方法。第一个是分支定界算法，他们用单纯形来计算下界。第二种方法是基于问题空间搜索启发式。这些方法进行了测试，涉及多达50架飞机和4条跑道的基准。作者还指出，这些方法可以用于动态版本的问题。Beasley等人（2004），提出了一种使问题位移最小化的数学公式，他们开发了三种求解方法：首先，通过将飞机按出现时间分组将问题划分为子问题，每个子问题使用Cplex进行优化求解。两个元算法的基础上的人口的解决方案被用来解决这个问题。计算结果涉及多达500架飞机和5条跑道。据我们所知，这些结果还没有进行过比较.Moser和Hendtlass（2007）处理了单跑道问题的动态情况，他们应用极值优化与局部搜索启发式混合来调度飞机着陆，并给出了10-50架飞机的计算结果在静态情况下研究ALP的论文中，我们引用Abela等人的工作。（1993）提出了一个混合线性规划问题的求解公式，并用分支定界算法进行了优化求解，他们提出了另一种应用遗传算法的方法，并对这两种方法进行了比较。Ciesielski和Scerri（1998）将遗传算法应用于双跑道情况下的ALP。 Beasley等人（2000）提出了静态情况下ALP的混合线性规划公式;他们通过基于二元变量松弛以及一些约束的方法来求解。计算结果 涉 及 多 达 50 架 飞 机 和 4 条 跑 道 。 Beasley 等 人（2001）提出了一个特殊的案例，他们基于启发式种群开发了一种启发式算法，用于改进飞机在希思罗机场的着陆。Ernst和Krishnamoorthy（2001）提出了两种求解方法，分支定界法和遗传算法。在单跑道的情况下，Boukachour和ElHilaliAlaoui（2002）提出了一种遗传算法.Pinol和Beasley（2006年）提出了一种具有线性和非线性目标函数的ALP的数学公式;他们提出了两种遗传算法。方法：散布搜索和生物算法，计算结果涉及多达500架飞机和5条跑道。Bencheikh等人（2013）提出了遗传算法的另一种应用，在他们的工作中，他们还应用了一种与GA杂交的禁忌搜索算法 计算结果涉及多达500架飞机和5条跑道。 Bauerle等（2007）对减少一条或两条跑道的等待时间感兴趣;他们提出了一个飞机着陆程序模型。Artiouchine等人（2008）对问题的复杂性更感兴趣，他们讨论了在多项式时间内解决的几种情况，并提出了一种紧凑的混合整数规划公式，以解决所有时间窗口具有相同大小的一般问题的大型实例。他们提出了一个通用的混合分支和切割框架。Soomer和Franx（2008）研究了单跑道到达问题;他们提出了一种针对该问题的局部搜索启发式算法，在考虑航空公司成本的情况下为每个航班分配着陆时间。这笔费用与航班的抵达延误有关。 Soomer和Koole（2008）考虑了一个额外的目标函数，它代表了航空公司的偏好。 航空公司为每个航班提供不同的成本函数，每个航班除了其着陆时间外还具有不同的特征。Randall（2002）用蚁群算法求解了ALP问题 我们还应用 了 与 局 部 搜 索 相 结 合 的 蚁 群 优 化 （ ACO ）（Bencheikh等人， 2011年），该算法进行了测试的基准从OR图书馆（比斯利，OR图书馆）涉及50架飞机和5跑道。在本文中，我们提出解决飞机着陆问题的动态和多跑道的情况。我们将Bencheikh等人（2011）中使用的蚁群算法（ACA）应用于动态情况，其中我们必须处理两种情况：第一种是测距雷达中出现新飞机，因此必须执行重新调度，第二种是冻结时间，程序的任何时间，进入冻结时间的飞机必须从列表中删除在第三节中，我们给出了动态情况下ALP的一个数学公式，这个公式是Beasley等人提出的。（2000年）的第10/2000号决议。第四节介绍了蚁群算法在动态飞机着陆问题中的应用.在第5节中，我们提出了一个模因算法结合蚁群算法和局部搜索算法，用于改善解决方案的群体。计算结果在第6节中给出并讨论。结论和一些进一步的工作在第7节中给出。3. 数学公式在这一节中，我们提出的数学公式的飞机着陆问题的动态情况下提出的比斯利等人。（ 2000年）的第10/2000号决议。我们使用以下符号：— N：飞机— R：跑道— ai：飞机i— ti：飞机i— tai：飞机i的目标着陆时间— ei：飞机最早降落时间i— li：飞机i的最晚降落时间100G. Bencheikh等人.¼XX.XXXJ我Sij：飞机着陆间隔时间i如果降落在同一条跑道sij：飞机i着陆间隔时间如果降落在不同的跑道上在某些情况下，我们可以立即决定是否xij=1或x ij= 0。例如，如果l ii6ð1Þ所有飞机的实际着陆时间与其目标着陆时间之间的偏差的惩罚成本的最小化由以下项表示：Nmax0;tai-ti：Pbimax 0;ti-tai：Pai1/1在Beasley等人（2000）中，一个称为位移的约束（7）和（8）将变量yir、yjr和zij联系起来：z ijPyiryjr-18i;j ¼ 1;... ;N;j> i;8r1/4;.. . ; R7z ij6 1-yirjr8i; j ¼ 1;. ; N; r ¼ 1;. ; R8的确，-如果飞机i在跑道r上着陆（即，yir=1）和飞机j功能介绍。该函数定义为：NDT;tDiT;t1/1在同一跑道R上着陆（即，y jr= 1），则变量z ij= 1。这是由约束保证的16zij6 1由于所研究的问题是动态的，它可以发生的降落时间分配给一个或多个飞机的值在调度过程中被修改。因此，他们定义Di（T，t）来量化每个决策变量i从其先前（已知）解值Ti到其新（当前未知）值Ti的修改的效果。它可以表示为：DiT; t Ti-ti23.2. 约束对于每架飞机，其预定着陆时间必须属于着陆窗口，[ei，li]e i6t i6l i8i¼ 1;.. . ;N2以下约束表明存在两种情况：落在j之前或j落在i之前。x ijx ji<$1 8i;j<$1;. ;N;j>i3— 如果飞机i降落在跑道r上（yir=1），但j没有（yjr=0），则zij=006zij6 0— 如果飞机i和j没有降落在跑道r上，所以我们-16zij6 1附件中提出了这个问题的具体公式。4. 应用于DALP的蚁群算法（ACO）是Marco Dorigo在1992年提出的一种解决组合优化问题的元启发式方法。基于真实蚂蚁在搜索食物时的行为，ACO由一群人工蚂蚁组成，这些人工蚂蚁迭代地构造组合优化问题的给定实例的解，并使用信息素---●.●-IJ1/4。求解飞机着陆问题101-来进行交流。蚁群中的每一只蚂蚁从零开始求解，根据问题信息和信息素的轨迹，从一个迭代到另一个迭代，添加新的当所有解被构造出来后，每只蚂蚁根据其解的质量更新信息素的踪迹蚁群算法最初被应用于旅行推销员问题（TSP），以 寻 找 完 全 图 中 的 最 短 哈 密 顿 路 径 （ Dorigo 和Gambardella，1997 a，b）。在此之后，蚁群算法被应用于静态和动态组合问题，包括机器调度（Liao和Juan ， 2007 ） ， 作 业 车 间 调 度 （ Colorni 等 人 ，1994 ） 、 车 辆 路 线 （ Donati 等 人 ， 2008; Bell 和McMullen ， 2008;Reimann 等 人 ， 2004 ） 、 图 着 色（Costa和Hertz，1997）、背包问题（Kong等人，2008）等。由于它对环境变化的适应性，它是解决动态问题的有力工具真正的蚂蚁是动态的性质，他们可以找到最短的路径到食物来源，即使障碍物出现和消失不断。在本文中，我们提出了一个适应ACA的动态飞机着陆问题的多跑道的情况下。它是应用于问题的静态情况的算法的修改版本（Bencheikh等人， 2011年），在这里，我们必须处理随着时间的推移出现的新飞机，而解决方案的过程已经开始。我们还必须考虑到冻结时间，当飞机的降落时间与当前时间“如此接近”时4.1. 图形表示为了使用蚁群算法解决飞机着陆问题，我们需要将其表示为一个图。本文中使用的图形表示是基于一个双层图。在第一层，我们放置可用的跑道，在第二层，我们放置飞机。我们添加两个虚拟节点D和F，分别对应于图的输入和输出（图1）。为了构造它的解决方案，蚂蚁从节点D开始它的轨迹然后，从雷达控制中出现的飞机中选择一架飞机，并为它分配着陆时间，最后，蚂蚁到达图的末尾。在插入下一架飞机之前，蚂蚁必须检查新飞机在射程范围内的出现和飞机着陆时间的冻结重复这个过程，直到没有飞机可以降落。4.2. 解决方案建设我们定义了一个全球性的候选人名单，其中包含所有飞机的索引在实际开始构建解决方案之前，蚂蚁必须创建自己的本地候选列表，该列表对应于已经出现在测距雷达中的可用飞机。它从虚拟节点D开始它的路径;首先，它选择下一架飞机将降落的跑道，这个选择取决于跑道的负荷，或者取决于越早空闲的跑道。在选择跑道后，蚂蚁必须从其本地候选列表中选择下一架飞机降落在该跑道上;这种选择主要取决于飞机与其他飞机相比的优先级和蚁群的记忆。这重复该过程，直到没有飞机可供降落。为了遵守冻结时间限制，在迭代结束时，我们必须固定已进入冻结窗口的飞机的着陆时间当飞机的着陆时间固定（冻结）时，它将被明确地从全局候选列表中删除。在提出应用于动态飞机着陆问题的详细ACA之前，我 们 提 出 了 应 用 于 问 题 的 静 态 情 况 的 原 始 算 法（Bencheikh等人， 2011年）。每个步骤都在以下小节中描述4.2.1. 蚁群算法应用于静态情况下的ALP1. 根据所有飞机的索引初始化候选列表2. 初始化信息素轨迹3. 对于每个蚂蚁ki. 重复根据方程选择跑道r（10）根据方程选择飞机。（十一）将飞机j插入受影响飞机列表中至跑道r，并从候选列表影响飞机降落时间返回节点D当候选人列表不为空时4. 更新信息素踪迹根据Eq. （十二）5. 第3步和第4步是多次迭代.4.2.2. 蚂蚁的代表为了使用蚁群优化来解决组合问题，我们必须定义蚂蚁的表示。蚂蚁代表问题的一个解决方案，在我们的情况下，它表示为：根据蚂蚁的候选列表构造其解决方案R列表，代表每条跑道：它包含受影响的飞机的索引和它们的着陆时间-表示的解决方案的惩罚成本蚂蚁的例子跑道1一分一百二十五秒五点二百零一分四点五十六分–跑道2二点一百零八分三点一百八十四分六点三百八点六五五分三号跑道七点五十四分十点四百零七分九点五百二十分–由该蚂蚁表示的解意味着飞机1、5和4分别在125、201和356处降落在跑道1上2、3、6、8号飞机分别在2号跑道降落，108、184、300和655。最后，7号、10号和8号飞机降落在跑道3分别位于54、407和520处。4.2.3. 初始化在静态情况下的问题，所有的飞机是已知的调度过程的开始，所以对于每个蚂蚁，我们初始化的候选人名单的所有飞机索引和跑道的NULL。------102G. Bencheikh等人b1b2（

下载后可阅读完整内容，剩余1页未读，立即下载