基于信息熵的属性约简在多属性决策中的应用

属性约简是在信息系统中的一个重要操作.分类是属性约简的基础,且直接在大数据集上进行属性约简往往存在效率低下的问题.以分类为基础提出了一种基于信息熵的信息系统属性约简算法.算法通过信息熵的计算,在属性约简的同时对原信息系统逐层分解,从而实现了属性的约简并缩小了搜索空间.提出了依据信息熵来确定属性的不必要性及简约属性集,应用在多属性决策中所带来的优势.     

多点收缩混沌优化方法及全局收敛性证明

针对目前混沌优化算法在选取局部搜索空间时的盲目性,提出一种具有自适应调节局部搜索空间能力的多点收缩混沌优化方法.该方法在当前搜索空间搜索时保留多个较好搜索点,之后利用这些点来确定之后的局部搜索空间,以达到对不同的函数和当前搜索空间内已进行搜索次数的自适应效果.给出了该算法以概率1收敛的证明.仿真结果表明该算法有效的提高了混沌优化算法的性能,改善了混沌算法的实用性.     

多机型航班恢复问题研究

主要研究了基于航班延误时间最短的航班行程规划问题,分别建立了最基本的多机型航班恢复问题模型、考虑旅客行程重新规划的航班恢复问题模型.在约束条件下,先在单机型航班恢复的基础上考虑多机型航班恢复,最后考虑基于飞机载客量的多机型航班恢复.构建时空网络模型,结合改进的分支定界法和启发式算法,确定筛选范围,调整不同的影响范围,达到较优的结果.对于多机型航班恢复问题,得到航班总延误时间为12850分钟.接着分析考虑飞机载客量的多机型航班恢复问题,分析建立的模型得到航班总延误时间为约1886650分钟.建立的模型有较好的鲁棒性,且具有较好的实用性.     

装配型企业订货量分配与订单排产联合决策研究

针对供应商交货数量不确定环境下,多品种小批量装配型制造企业因生产物料不配套造成生产计划不可行甚至客户订单拖期的问题,从企业运作整体出发,考虑订货量分配决策对订单生产和交货的影响,以最小化采购成本和最小化订单排产相关成本为优化目标,在允许零部件拖期交货且供应商提供拖期价格折扣条件下,建立订货量分配与订单排产联合优化模型。针对可行解空间巨大、传统数学规划方法难以求解的问题,从增强搜索性能角度出发,设计基于自定义邻域搜索算子的局部搜索机制和基于随机与种群重构变异机制的改进粒子群算法的模型求解策略。通过应用实例对本文模型和算法进行了有效性验证和灵敏度分析,结果表明,相比于传统的分散决策方案,本文模型能够有效降低整体成本水平,引入的改进机制能够显著提升算法搜索性能,为企业供应风险下的运营决策制定提供理论参考。     

基于大系统分解协调的CDM下不正常航班恢复优化

针对不正常航班恢复以及民航调度系统中空管、机场和航空公司之间复杂的协同调度问题,设计了一个基于大系统分解协调的不正常航班调度系统分解方法.首先简述了基于CDM的航班调度系统结构及原理,然后针对不正常航班恢复所涉及的各参与主体利益需求,建立分解级协调级多级递阶结构的不正常航班恢复优化调度模型,对分解后的各子系统模型采用遗传算法优化求解.最后通过东北空域内各主要机场航班调度的算例验证分析,结果表明采用方法能够减少航班延误时间,提高航空管理和服务质量,为具体工程应用提供决策支持.     

基于人机交互—蚁群算法的港口疏船调度优化

为解决因港口无法正常作业导致大量船舶压港后的疏船调度问题,从同时兼顾船公司和港口方利益出发,建立了船舶平均在港时间最短、额外作业成本最低、生产秩序恢复最快的调度生产多目标优化模型。利用多属性效用理论将多目标转换为单目标,并构建了相应的评价函数,采用改进的蚁群算法并结合人机交互以及邻域搜索方法求解,最后以大连港集装箱码头实际案例进行验证。结果表明,与通常调度方法相比,文中建立的优化模型能够更好地解决疏船问题;对比常规的蚁群算法,改进后的算法搜索效率更高。上述模型和算法为集装箱码头的生产组织调度提供了新的优化思路和方法。     

组合优化算法中摆脱局部极小值的几种策略

局部搜索算法是一种非常有效的求解组合优化问题的算法 ,它具有通用、灵活等特点 .但是 ,由于搜索空间和目标函数的复杂性 ,目标函数在搜索空间中有许多局部极小值点 ,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果 .对于此问题 ,笔者查阅了大量文献资料 ,结合自己的研究实践 ,总结出几种跳出局部极小“陷井”的策略 .使用这些策略 ,有望使算法更加完善 ,在求解组合优化问题过程中更能发挥其作用 .     

组合优化算法中摆脱局部极小值的几种策略

局部搜索算法是一种非常有效的求解组合优化问题的算法,它具有通用、灵活等特点。但是,由于搜索空间和目标函数的复杂性,目标函数在搜索空间中有许多局部极小值点,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果。对于此问题,笔查阅了大量献资料,结合自己的研究实践,总结出几种跳出局部极小“陷井”的策略,使用这些策略,有望使算法更加完善,在求解组合优化问题过程中更能发挥其作用。     

基于动态列生成算法的飞机排班问题研究

飞机排班是航空运输生产计划的重要环节,对航空公司的正常运营和整体效益有着决定性影响;飞机排班通常构建为大规模整数规划问题,是航空运筹学研究的重要课题,构建的模型属于严重退化的NP-Hard问题.在考虑对多种机型的飞机进行排班时,大大增加了问题的复杂性.针对航空公司实际情况,建立多种机型的飞机排班模型;为实现模型的有效求解,提出了基于约束编程的动态列生成算法;即用约束编程快速求解航班连线(航班串)并计算航班串简约成本,动态选择列集并与限制主问题进行迭代.最后,利用国内某航空公司干线航班网络实际数据验证模型和算法的有效性.     

基于新模糊熵和得分函数的区间直觉模糊多属性决策

属性权重的确定以及对区间直觉模糊数的排序是多属性决策问题中两个最为关键的点。本文主要针对属性权重完全未知的多属性决策问题进行了研究,分析了现有大多数研究中关于区间直觉模糊熵和得分函数存在的局限性,进而提出了一种将不确定度和犹豫度相结合的新的模糊熵和得分函数。最后,通过对比实验证实了本文所提出的熵和得分函数应用到多属性决策中的有效性和合理性。     

Visibility Queries and Maintenance in Simple Polygons

Abstract. In this paper we explore some novel aspects of visibility for stationary and moving points inside a simple polygon P . We provide a mechanism for expressing the visibility polygon from a point as the disjoint union of logarithmically many canonical pieces using a quadratic-space data structure. This allows us to report visibility polygons in time proportional to their size, but without the cubic space overhead of earlier methods. The same canonical decomposition can be used to determine visibility within a frustum, or to compute various attributes of the visibility polygon efficiently. By exploring the connection between visibility polygons and shortest-path trees, we obtain a kinetic algorithm that can track the visibility polygon as the viewpoint moves along polygonal paths inside P , at a polylogarithmic cost per combinatorial change in the visibility or in the flight plan of the point. The combination of the static and kinetic algorithms leads to a new static algorithm in which we can trade off space for increased overhead in the query time. As another application, we obtain an algorithm which computes the weak visibility polygon from a query segment inside P in output-sensitive time.     

Development of an Expert System: Translating Higher-Level Decisions into Lower-Level Aircraft Flights

This note describes two phases in the development of an expert system that translates European-wide directives into individual flight orders. This expert system was built for a military computer simulation, but parts of the logic can apply — and many of the illustrations in the text have been tailored — to creating and organizing commercial flights. The first phase of the development — a proof of principle expert system — emulated the logical deductions of an air traffic control supervisor or a flight planner. The second phase of development led to a working prototype decision support system that employed more mathematical comparisons of aircraft attributes than logical deductions.     

Aircraft proximity termination conditions for 3D turn centric modes

International airspace design is undergoing significant change that requires formal and rigorous mathematical specifications to assure the safety of flight operations. Aircraft proximity management is one such area. The Point of Closest Approach (PCA) between aircraft flightpaths is the position along a flightpath at which the minima in relative range occurs. To date, PCA has been estimated primarily based on the assumption of a linear extrapolation of the velocity vectors of each aircraft involved, however, this assumption is limiting and aircraft in turning flight must also be considered. A generalised geometric and vector construction for the determination of PCA is presented. A solution based on a characterization of Fermat’s method for stationary points is presented that results in a complex transcendental equation. By casting the equation in a determinant structure a co-linearity condition is revealed between three unique 2D points. A novel aspect is that one of these points is a fixed reference point that lies on either the vector between the aircraft turn centres or on one of its extensions providing a reference to determine the location of the PCA. The analytic method can be readily applied in a laboratory test environment or in an automated guidance context. The rigorous proof enables a higher confidence in achieving dependable operations in a safety critical context and in the adequacy of test strategies when developing algorithms for aircraft avionics.     

On the exact WKB analysis of operators admitting infinitely many phases

To analyze differential operators whose WKB solutions admit infinitely many phases, we introduce a class of differential operators of WKB type and analyze their exact WKB theoretic structure near their turning points. Our analysis makes full use of techniques and ideas in microlocal analysis; we use a quantized contact transformation to construct a WKB solution of a differential equation of WKB type, and we use a Späth-type division theorem for a differential operator of WKB type to study its structure near turning points. As an application, we show a connection formula for WKB solutions near a simple turning point.     

A gate reassignment framework for real time flight delays

Flight delays (such as early or late arrivals and late departures) are a frequent occurrence in actual day to day airport operations and it is often not possible to assign such flights to their original gates. Flight delay information may also vary with time. As a consequence, the airport authority needs to reassign flights to different gates in real-time. The traditional manual flight reassignment method is neither efficient nor effective in cases with variable flight delay information, and the reassignment is frequently time constrained. Consequently, in this study the goal is to develop a gate reassignment framework, and a systematic computerized tool, for repeatedly handling gate reassignments given varied flight delay information. The results of a test case related to Taiwan international airport operations, show that the proposed framework performs well.     

面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班-机位指派问题的全局优化模型.基于国内某机场的真实应用场景及其待决策变量维度的超大规模,导致模型求解成为一个NP-COMPLETE的混合整数规划问题.文章提出一种启发式快速求解算法,基于贪婪规则建立若干优先级队列的航班冲突调整方案,按照3个指标重要程度渐次探求近似最优解.而且,对于每一步贪婪规则的改进,文章都进行了算法有效性检验以及计算性能的对比实验.最终多重对比实验的结果表明,新算法的结果在与理论最优解差距不足3%的代价下,可节约超过90%求解时间.     

Maximizing revenue in the airline industry under one-way pricing

The paper describes a methodology that has been implemented in a major British airline to find the optimal price to charge for airline tickets under one-way pricing. An analytical model has been developed to describe the buying behaviour of customers for flights over the selling period. Using this model and a standard analytical method for constrained optimization, we can find an expression for the optimal price structure for a flight. The expected number of bookings made on each day of the selling period and in each fare class given these prices can then be easily calculated. A simulation model is used to find the confidence ranges on the numbers of bookings and these ranges can be used to regulate the sale of tickets. A procedure to update the price structure based on the remaining capacity has also been developed.     

The Global k-Means Clustering Analysis Based on Multi-Granulations Nearness Neighborhood

Multi-Granulations nearness approximation space is a new generalized model of approximation spaces, in which topology neighborhoods are induced by multi probe functions with many category features. In this paper, by combining global k-means clustering algorithms and topology neighborhoods, two k-means clustering algorithms are proposed, in which AFS topology neighborhoods are employed to determine the clustering initial points. The proposed method can be applied to the data sets with numerical, Boolean, linguistic rating scale, sub-preference relations features. The illustrative examples show that the proposed method is effective for clustering problems, and can enrich the applicable field on the idea of qualitatively near.     

机场新增卫星厅对登机口影响的评估方法

为了解决航站楼客流量饱和的问题,采用一种增加卫星厅的方法,实现了旅客分流.基于单目标整数线性规划和多目标优化的方法,分别构建了登机口优化分配网络模型和多目标优化模型.利用登机口优化分配网络算法筛选出所使用的共同登机口,建立了目标函数并列出约束条件,采用目标约束法对建立的模型进行求解.在此基础上,根据目标建模的思想,建立了可供中转旅客总体流程时间最短且使用登机口数量最小的航班-登机口分配模型.利用MATLAB计算可知,利用42个登机口即可实现303架航班的正常运转.     

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.