推出冲突避免的机场停机位分配问题

为了科学合理地利用机场停机位资源,克服现有模型对飞机进出机位安全性的考虑不足,研究兼顾运行安全和运行效率的机场停机位分配问题.首先分析了飞机在停机坪中的运行过程,提出以主动避免方式来解除飞机进出机位过程中的冲突,从而将具有潜在冲突的飞机对的机位分配作为约束条件,建立了一类推出冲突避免的停机位分配模型.然后对目标函数和约束条件进行分析和简化,将模型转化为线性模型来求解.算例仿真结果验证了该模型的有效性,表明所提出的主动避免冲突方法是能兼顾运行安全和效率的一种有效方法.     

机场新增卫星厅对中转旅客影响的模型和算法

基于"华为杯"第十五届中国研究生数学建模F题中关于机场新增卫星厅对中转旅客的影响问题的研究.通过建立描述登机口与机场航班对应矩阵,采用0-1整型规划模型和基于最优个体保留策略的遗传算法求解航班-登机口分配的最优解,并且将最大化分配航班数、最小化登机口数、以及最小化乘客总体换乘紧张度等优化目标采用加权的方式实现多目标优化,最后得出相对最优解.     

基于“货到人”拣选模式的储位分配问题研究

研究了“货到人”拣选模式下的储位分配问题,以订单拣选过程中搬运货架总时间最短为目标建立了整数非线性规划模型,并证明其为NP-hard问题,分别设计了求解模型的贪婪算法和单亲进化遗传算法。首先根据订单和物品的关联关系对物品进行聚类,基于聚类结果设计了求解模型的贪婪算法。然后设计了直接求解模型的单亲进化遗传算法,遗传算法中采用了0-1矩阵编码、多点基因倒位算子、单点基因突变算子和精英保留等策略,通过合理选取参数,能够很快求解出问题的近似最优解。最后利用模拟算例和一个具体实例进行计算,并对贪婪算法和遗传算法的求解时间和求解效果进行了比较分析。结果显示,对于小规模问题,两种算法均能在较短的时间内以很高的概率得到问题的全局最优解,对于中等规模的实际问题,利用两种算法得到的储位分配方案均优于企业目前采取的基于出库频率的储位分配方案,遗传算法得到的储位分配方案对应的货架搬运次数、货架搬运总时间等均优于贪婪算法。本文设计的遗传算法可以作为智能仓库管理信息系统的核心算法。     

大规模多设施Weber问题的改进Cooper算法

 多设施Weber问题（multi-source Weber problem,MWP）是设施选址中的重要模型之一,而Cooper算法是求解MWP最为常用的数值方法.Cooper算法包含选址步和分配步,两步交替进行直至达到局部最优解.本文对Cooper算法的选址步和分配步分别引入改进策略,提出改进Cooper算法：选址步中将Weiszfeld算法和adaptive Barzilai-Borwein （ABB）算法结合,提出收敛速度更快的ABB-Weiszfeld算法求解选址子问题;分配步中提出贪婪簇分割策略来处理退化设施,由此进一步提出具有更好性质的贪婪混合策略.数值实验表明本文提出的改进策略有效地提高了Cooper算法的计算效率,改进算法有着更好的数值表现.     

航班登机口分配问题的数学建模

登机口作为机场的重要组成部分,其资源利用率直接影响航班服务的效率.针对不同的优先级建立多目标规划模型对航班进行优化分配,采用贪心算法和禁忌搜索算法,结合登机口类型、航班时间的约束,逐次对最大化分配航班问题、最小化中转旅客最短流程时间问题、最小化旅客总体紧张度问题进行建模求解.结果表明该算法不仅提升了求解速度,并且在航班登机口分配问题中展现了较好的综合寻优能力.这对民航机场实现经济效益、提高旅客满意度有一定的参考价值.     

基于AGV的智能仓库系统储位分配问题研究

研究了基于自动引导机器人(AGV)的"货到人"拣选模式下的智能仓库系统补货阶段的储位分配问题.根据待拣选订单信息计算出商品之间的关联度,考虑了货架上存放的物品信息、空余储位数量、待补货物品信息,以同一货架上的各种商品之间的关联度之和最大化为目标函数,建立了补货阶段储位分配问题的整数规划模型;设计了求解模型的贪婪算法,并分析了算法复杂度.利用一个具体实例进行模拟计算,分析了贪婪算法的求解效果.进一步利用不同规模算例进行模拟计算,分析了贪婪算法的计算时间和近似比,结果显示贪婪算法可以在很短的时间内得到近似最优解,近似比不超过1.15.设计的贪婪算法可以作为智能仓库管理信息系统的核心算法.     

单架飞机受干扰后飞机路径恢复最优化研究

本文基于现实情况中航空公司调整航班的一些原则,提出单架飞机受短时间干扰后的航班调整问题,把最大航班延误时间最小化作为问题的目标,以航班在时间和空间上的衔接作为约束,建立数学模型,并根据问题的一些特点,分析出在受干扰飞机所在机场进行调整就能得到最优解,然后设计了二分搜索匹配算法,并证明该算法能够找到最优解,最后通过案例验证了算法的有效性。     

不正常航班恢复模型和算法研究

主要根据2017年中国研究生数学建模竞赛中的航班恢复问题,探讨航班遇到突发情况时,如:机场在某时间段关闭,如何按照不同要求重新规划航班,使得旅客总延误时间或航班总延误时间尽可能短.航班恢复是一个NP-Hard问题,根据竞赛所涉航班恢复的4个子问题,分别根据其特有的约束条件和飞机间调整所需额外成本的计算办法,建立了相应的混合整数规划模型.通过先检测不正常航班的相关信息如延误扩散情况,再选择航班恢复计划使延误尽可能小,给出了启发式算法求解上述规划模型.进一步,对航班恢复问题所涉及的前3个子问题,分析了其延误时间下界,并与算法所得的延误时间进行比较,发现算法所得延误时间等于或者非常接近估计下界,这说明算法所得新航班计划是最优的或者非常接近最优航班恢复计划.     

基于移动机器人的拣选系统货架动态储位分配研究

为了提高基于移动机器人的拣选系统拣货效率,更好地满足客户动态需求和订单时效要求,提出了考虑货架后续需求频次、需求紧迫程度以及拥堵因素的货架动态储位分配策略,构建了最小化货架搬运距离的动态储位分配模型,并设计了启发式算法进行模型求解.首先,基于货架需求紧迫程度,构造贪婪算法生成动态货架储位分配的初始解;然后,基于货架在后续批次订单的需求频次及通道间负载均衡,采用邻域搜索算法进行动态货架储位优化.最后,通过与其他静态和动态储位分配方法对比,验证文章提出的模型和算法的有效性.     

基于多目标规划的飞机路径恢复最优化算法研究

本文针对同一机场中同机型的多架飞机受到干扰后, 飞机路径恢复的多目标最优化问题进行研究。首先根据航空公司实际航班调整的常用原则和航班干扰管理的基本思想, 基于连接网络建立多目标规划模型, 其中两个目标按照优先级排列:第一个目标为最小化航班的最大延误时间, 第二个目标为最小化参与交换的飞机数量。然后根据该问题的航班波结构特点, 结合求解多目标规划的分层序列法, 分析优化问题的若干最优性质, 并基于快速排序算法和最小费用路算法设计出多项式算法。最后用算例验证了算法的有效性。该研究结果可以为航空公司减少航班延误提供理论和技术支持。     

Flight gate scheduling with respect to a reference schedule

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods.     

Models and a genetic algorithm for static aircraft-gate assignment problem

Assigning aircraft to available gates at an airport can have a major impact on the efficiency of flight schedules and on the level of passenger satisfaction with the service. Unexpected changes, due to air traffic delays, severe weather conditions, or equipment failures, may disrupt the initial assignments and compound the difficulty of maintaining smooth station operations. Recently, mathematical models and procedures (optimal and heuristic) have been proposed to provide solutions with minimum dispersion of idle time periods for static aircraft-gate assignment problems. This paper introduces a unified framework to specifically treat the objective functions of the previous models. It also provides linear representations of these models and identifies the conditions under which the optimal solutions can be obtained in polynomial time. Furthermore, a genetic algorithm utilizing problem specific knowledge is proposed to provide effective alternative solutions.     

Network flow-based approaches for integrated aircraft fleeting and routing

Given a schedule of flights to be flown, the aircraft fleeting and routing problem (AFRP) consists of determining a minimum-cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance requirements and other activity constraints. We investigate network flow-based heuristic approaches for this problem. Computational experiments conducted on real-data given by TunisAir show that the proposed heuristic consistently yields very near-optimal solutions while requiring modest CPU effort.     

Exact approaches for integrated aircraft fleeting and routing at TunisAir

We describe models and exact solutions approaches for an integrated aircraft fleeting and routing problem arising at TunisAir. Given a schedule of flights to be flown, the problem consists of determining a minimum cost route assignment for each aircraft so as to cover each flight by exactly one aircraft while satisfying maintenance activity constraints. We investigate two tailored approaches for this problem: Benders decomposition and branch-and-price. Computational experiments conducted on real-data provide evidence that the branch-and-price approach outperforms the Benders decomposition approach and delivers optimal solutions within moderate CPU times. On the other hand, the Benders algorithm yields very quickly high quality near-optimal solutions.     

The daily tail assignment problem under operational uncertainty using look-ahead maintenance constraints

The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to satisfy operational constraints. The aim of this paper is to develop an operationally flexible method, based upon the one-day routes business model, to compute tail assignments that satisfy short-range—within the next three days—aircraft maintenance requirements. While maintenance plans commonly span multiple days, the methods used to compute tail assignments for the given plans can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by using solutions from the one-day routes aircraft maintenance routing approach as input. The daily tail assignment problem is solved with an objective to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A computational study will be performed to assess the performance of exact and heuristic solution algorithms that modify the input lines-of-flight to reduce maintenance misalignments. The daily tail assignment problem and the developed algorithms are demonstrated to compute solutions that effectively satisfy maintenance requirements when evaluated using input data collected from three different airlines.     

Assigning arriving flights at an airport to the available gates

Unexpected changes in the flight schedules may disrupt the initial aircraft-gate assignments, and result in congestions and delays in getting aircraft onto gates. A mathematical model is developed to assign the flights with the minimum range of unutilised time periods of gates, subject to the level of service offered to passengers and other physical and managerial considerations. (The assignments are expected to be flexible enough to absorb the minor modifications in the flight schedules.) Interactive optimum and heuristic procedures, both utilising lower bounds on the ranges of future solutions, are proposed to cope with the major changes in disrupting the initial gate-assignments. Over randomly generated schedules, 74 flights can be optimally assigned to seven gates within 17 seconds when the gates are re-utilised within 30 minutes after each departure. The heuristic reaches the optimal solution after evaluating at most 20 partial solutions at one level. Over data obtained from Riyadh’s International Airport, the heuristic outperforms the existing practice: On average, 72.03% and 54.28% improvements are obtained on the number of remote served aircraft and towed aircraft, respectively.     

机场任务指派问题的优化方案研究

本文研究了机场任务指派问题,该问题是指将具有特殊属性的任务指派给有限数量的班次。由于机场任务和班次属性的多样性,机场任务指派问题是一个复杂的组合优化问题,属于NP-完全问题。本文以任务完成产生的效益总和最大化为目标建立数学优化模型,提出有效不等式,应用CPLEX软件对实际数据进行求解,结果表明,CPLEX可以在较短时间内对一定规模的算例求得最优解。同时对影响目标函数的四个因素:任务数量、班次数量、班次工作时长和任务属性分别进行分析,通过实际算例测试对比,得出具有指导意义的结论,即根据机场特征分别调整四个因素不仅能够提高机场资源的有效利用率,而且能够提高机场的运行效率和服务水平。     

Airport noise modelling and aircraft scheduling so as to minimize community annoyance

A mathematical model of the annoyance created at an airport by aircraft operations is developed. The model incorporates population distribution considerations around an airport and the annoyance caused by aircraft noise. The objective function of this model corresponds to seeking to minimize total population annoyance created by all aircraft operations in a 24-hour period. Several factors are included in this model as constraint relationships. Aircraft operations by type and time period are upper bounded. Demand for flight services is incorporated by including lower bounds on the number of operations by type of aircraft, runway used and time period. Also upper bounds on the number of operations for each runway are included. The mathematical model as formulated is recognized as corresponding to a nonlinear integer mathematical programming problem.The solution technique selected makes use of a successive linear approximation optimization algorithm. An especially attractive feature of this solution algorithm is that it is capable of obtaining solutions to large problems. For example, it would be feasible to attempt the solution of problems involving several thousand variables and over 500 linear constraints. This suggested solution algorithm was implemented on a computer and computational results obtained for example problems.     

A dynamic programming approach for the airport capacity allocation problem

In most of the optimization models developed to manage airportsoperations, arrivals and departures capacities are treated asindependent variables: that is the number of flights allowedto take off does not affect the number of landings in any unitof time, and vice versa. This assumption is seldom verifiedin most of the congested airports, where many interactions betweenarrivals and departures take place. In this paper, we face the problem of finding the optimal trade-offbetween the number of arrivals and departures in order to reducea delay function of all the flights, using a more realisticrepresentation of the airport capacity, i.e. the capacity envelope. Under the assumption of piecewise linear convex capacity envelopesand of the exact interpolation of all the Pareto-optimal operationalpoints, we show that the problem can be formulated as a linearprogramming model. For general airport capacity envelopes, wepropose a dynamic programming formulation with a correspondingbackward solution algorithm, which is robust, easy to implementand has a linear computational complexity. The algorithm performancesare evaluated on different realistic scenarios, and the optimalsolutions are compared with those computed by a greedy algorithm,which can be seen as an approximation of the current decisionprocedures. The percentage deviation of the cost of these twosolutions ranges from 3.98 to 35.64%.     

Scheduling aircraft landings at London Heathrow using a population heuristic

With increasing levels of air traffic, making effective use of limited airport capacity is obviously important. This paper reports on an investigation undertaken by National Air Traffic Services in the UK into improving runway utilisation at London Heathrow. This investigation centred on developing an algorithm for improving the scheduling of aircraft waiting to land. The heuristic algorithm developed (a population heuristic) is discussed and results presented using actual operational data relating to aircraft landings at London Heathrow. This data indicates that our algorithm could have improved on air traffic control decisions in such cases by between 2–5?% in terms of reducing the timespan required to land all of the aircraft considered.