精确求解进港飞机调度双目标优化问题的epsilon约束算法

随着机场客流的持续增长,航班延误日益严重。同时,对于机场最重要的跑道资源而言,积雪结冰等会造成 飞机 打滑,从而出现事故。对于机场管理者,周期性地维护跑道至关重要,以防雨雪天气出现飞机打滑事故。该研究主要针对跑道上的 航班调度问题,考虑恶劣天气环境下跑道的周期性维护(如周期性喷洒除雪盐等)。为了在保证航班的服务质量的同时提高机场跑道的使用效率,文中以最小化航班总延误和跑道使用时间为优化的双目标。首先,提出该双目标优化问题混合整数规划模型;其次,为了精确求解出Pareto前沿,开发出epsilon约束算法;最后,给出算例来说明模型和算法的可行性。通过数学规划理论建模并开发精确求解算法,为机场资源优化研究提供参考。     

基于LSD检测的无人机视觉着陆定位算法

针对复杂电磁和拒止环境下固定翼无人机自主着陆应用场景,提出了一种基于LSD(Line Segment Detector)的飞机着陆跑道检测和定位的方法;根据机场数据特点,构建机场跑道数据模型,并对数据进行标定和预处理,采用LSD直线检测算法以提高检测时间,采用蒙版技术以提高跑道的检测精度,通过检测得到机场跑道线在图像坐标系下的信息;根据相机成像原理推导出基于线检测的PNP(Perspective-n-Points)定位算法,从而求出飞机相对于跑道的位置;分别在视景仿真环境和真实机场环境进行检测和定位解算,结果表明本文设计的算法满足无人机着陆定位的实时性要求。     

改进的机场停泊飞行器目标分割算法

考虑到飞行器目标在整幅图像中所占的比例往往较小,且图像背景复杂,本文提出了一种基于机场区域提取的飞行器目标分割算法.该算法首先利用Hough变换检测直线的特性,定位机场跑道和停机坪的位置,并结合教学形态学等图像处理技术去除了非机场区域;在提取机场区域后,再选择适当的阈值对图像进行分割,最后经过形态学去噪、小区域去除等步骤分割出飞行器目标.实验结果表明,该算法改进了以往机场区域提取算法保留候机楼等附属部分以及提取结果中存在机场区域以外区域的缺点,较好地实现了机场停泊飞行器目标的分割,为下一步准确识别飞行器类型奠定了基础.     

基于Mask R-CNN的机场地面保护区航空器识别研究

为解决民航中小机场缺乏低成本运行的防跑道侵入技术的问题,提出了一种通过摄像头获取地面保护区图像信息以防止跑道侵入的模型。该模型首先利用迁移学习Mask R-CNN对航空器进行识别和跟踪,通过结合摄像头在地面保护区的布局方案,提出了一种基于摄像头的检测结果判断是否发生跑道侵入的逻辑电路。该模型通过等比例缩小的机场模型进行实验验证。结果表明,该模型的跟踪准确率为95%,可以有效地跟踪机场场面目标,进而判断跑道侵入的发生。     

多Agent的航空器滑行策略优化

快速发展的民航事业导致很多机场容量不足。为缓解大型机场交通拥堵的现状,研究了航空器滑行策略优化问题。滑行路径优化是指在特定的时间段内,根据机场资源信息和地面运行管理系统对进离场航空器在跑道和停机位之间的距离进行优化管理。通过深入剖析机场地面的网络结构,综合考虑滑行冲突、地面运行规则等因素,提出了多Agent滑行策略优化方法,该方法提升了机场资源利用率;基于地面网络链路结构的概念,建立了航空器滑行策略优化模型;结合多Agent的基本理论,设计了跑道出口选择概率函数和多Agent系统滑行路径优化结构,以寻求航空器的最优滑行路径。以国内某大型机场的实际情况为研究背景进行了航空器滑行策略实验,结果表明,与以往的算法相比,多Agent滑行策略优化方法的效果更为显著。设置跑道口的速度和同一交叉口航空器的最小间隔距离,通过对跑道出口的选择和Agent间的交互协商,航空器能够对原滑行路径进行有效调整,并缩短其在机场场面上的滑行时间。与最短路径算法相比,多Agent滑行策略方法在航空器的总滑行距离、航空器在滑行道上的密度以及平均等待时间方面的优化效果更好,且其对滑行道资源的分配更合理。其中,航空器在节点处的平均等待时间减少了8.26%。所提策略可有效缓解机场交通拥堵的现状,提高场面运行效率,对减少航空器延误和保障机场的运营安全具有重要意义。     

The evaluation of air transportation network based on multiple criteria

The problem is partitioned into two components: to propose the air transportation network based on “hub and spoke” pattern as alternative network in Sumatera island (one of the islands in Indonesia), and to propose the algorithm for the aircraft selection of the suitable type of aircraft in the operation on airport pairs. The algorithm presented in this paper is obtained from heuristic, and then comparing of our proposal with the existing one is done, based on the multiple criteria.     

基于多目标两阶段的跑道起飞调度模型

为了减少起飞延误,针对优化飞机起飞调度问题,提出一种基于多目标、两阶段的跑道调度模型。该模型由培植器、穿越发生器、一阶段组件、二阶段组件组成。培植器建立机场模型,根据飞机重量类别输出飞机从推出到跑道的最短时间。穿越发生器通过扫描进场航班,计算需穿越飞机时间。一阶段组件计算以上输出,从各种飞机类别序列中选择最优序列。二阶段组件将具体航班指配到最优序列得出飞机推出时间,生成优化的离场航班时刻表。实验表明,该模型较之传统的先来先服务模型,跑道吞吐量加大,延迟减少,可节约可观运营成本。     

Algorithms for a realistic variant of flowshop scheduling

This paper deals with a realistic variant of flowshop scheduling, namely the hybrid flexible flowshop. A hybrid flowshop mixes the characteristics of regular flowshops and parallel machine problems by considering stages with parallel machines instead of having one single machine per stage. We also investigate the flexible version where stage skipping might occur, i.e., not all stages must be visited by all jobs. Lastly, we also consider job sequence dependent setup times per stage. The optimization criterion considered is makespan minimization. While many approaches for hybrid flowshops have been proposed, hybrid flexible flowshops have been rarely studied. The situation is even worse with the addition of sequence dependent setups. In this study, we propose two advanced algorithms that specifically deal with the flexible and setup characteristics of this problem. The first algorithm is a dynamic dispatching rule heuristic, and the second is an iterated local search metaheuristic. The proposed algorithms are evaluated by comparison against seven other high performing existing algorithms. The statistically sound results support the idea that the proposed algorithms are very competitive for the studied problem.     

Optimizing network robustness by edge rewiring: a general framework

Spectral measures have long been used to quantify the robustness of real-world graphs. For example, spectral radius (or the principal eigenvalue) is related to the effective spreading rates of dynamic processes (e.g., rumor, disease, information propagation) on graphs. Algebraic connectivity (or the Fiedler value), which is a lower bound on the node and edge connectivity of a graph, captures the “partitionability” of a graph into disjoint components. In this work we address the problem of modifying a given graph’s structure under a given budget so as to maximally improve its robustness, as quantified by spectral measures. We focus on modifications based on degree-preserving edge rewiring, such that the expected load (e.g., airport flight capacity) or physical/hardware requirement (e.g., count of ISP router traffic switches) of nodes remain unchanged. Different from a vast literature of measure-independent heuristic approaches, we propose an algorithm, called EdgeRewire, which optimizes a specific measure of interest directly. Notably, EdgeRewire is general to accommodate six different spectral measures. Experiments on real-world datasets from three different domains (Internet AS-level, P2P, and airport flights graphs) show the effectiveness of our approach, where EdgeRewire produces graphs with both (i) higher robustness, and (ii) higher attack-tolerance over several state-of-the-art methods.     

A new bidirectional heuristic for the assembly line balancing problem

Assembly line balancing problem (ALBP) is one of the well-known NP-hard layout planning problems for mass production systems. Many exact solution approaches have been developed, including 0–1 integer programming model, branch and bound algorithm, dynamic programming model, etc.; however, all optimal approaches are computationally inefficient in solving large-scale problems, which makes heuristic approaches a necessity in practice. In this paper we propose a new efficient heuristic, based on a recent bidirectional approach and the famous critical path method (CPM) widely used in project management, to resolve the issue of task assignment for ALBP. An example is given for illustration, and numerical results of sample problems selected from the literature are also given to show the effectiveness of the proposed heuristic.