The over-constrained airport gate assignment problem

In this paper, we study the over-constrained airport gate assignment problem where the objectives are to minimize the number of ungated flights and total walking distances or connection times. We first use a greedy algorithm to minimize ungated flights. Exchange moves are employed to facilitate the use of heuristics. Simulated annealing and a hybrid of simulated annealing and tabu search are used. Experimental results are good and exceed those previously obtained.     

A stochastic neighborhood search approach for airport gate assignment problem

An appropriate and efficient gate assignment is of great importance in airports since it plays a major role in the revenue obtained from the airport operations. In this study, we have focused mainly on maximum gate employment, or in other words minimize the total duration of un-gated flights. Here, we propose a method that combines the benefits of heuristic approaches with some stochastic approach instead of using a purely probabilistic approach to top-down solution of the problem. The heuristic approaches are usually used in order to provide a fast solution of the problem and later stochastic searches are used in order to ameliorate the previous results of the heuristic approach whenever possible. The proposed method generates an assignment order for the whole planes that corresponds to assignment priority. The ordering process is followed by the allocation step. Since, in practice, each airport has its own physical architecture, there have been arisen many constraints mainly concerning airplane types and parking lots in this step. Sequentially handling the plane ordering and allocation phases provides us great modularity in handling the constraints. The effectiveness of the proposed methodology has been tried to be illustrated firstly on fictively generated flight schedule data and secondly on the real world data obtained from a real world application developed for ?stanbul Atatürk Airport.     

The use of meta-heuristics for airport gate assignment

Improper assignment of gates may result in flight delays, inefficient use of the resource, customer’s dissatisfaction. A typical metropolitan airport handles hundreds of flights a day. Solving the gate assignment problem (GAP) to optimality is often impractical. Meta-heuristics have recently been proposed to generate good solutions within a reasonable timeframe. In this work, we attempt to assess the performance of three meta-heuristics, namely, genetic algorithm (GA), tabu search (TS), simulated annealing (SA) and a hybrid approach based on SA and TS. Flight data from Incheon International Airport are collected to carry out the computational comparison. Although the literature has documented these algorithms, this work may be a first attempt to evaluate their performance using a set of realistic flight data.     

基于松弛算法的停机位分配优化方法

针对机场近机位资源紧缺及实际航班到离港时间偏离计划时间对停机位分配所造成的扰动，提出了在同机位相邻航班间加入缓冲时间的停机位分配调度方法。首先，建立了以机位空闲时间、远机位占用时间最小为目标的鲁棒性停机位分配模型；然后，设计了一种基于双目标的拉格朗日松弛优化算法，并使用次梯度算法求解拉格朗日松弛算法中的对偶问题。基于国内某枢纽机场运行数据的仿真结果表明，所提方法的优化方案和原始机位分配方案相比，机位使用量和机位空闲时间分别降低了15.79%、7.56%，机位占用率提高了18.72%，并且冲突率降低到3.57%，达到了有效提高停机位利用率与鲁棒性的目的。     

An integrated mathematical programming model for offset planning

The ability of a company to compete successfully in a global environment often extends beyond the ability to sell a product at a given price or service level. International “deals” are often based upon the company's ability to provide access to international markets (economic benefits), be perceived as socially responsible and meet political requirements. These requirements come in the form of offset, industrial participation or countertrade. Unfortunately, these factors cannot be measured in quantitative terms, but rather qualitative objectives. This paper presents the development of a quantitative model using multicriteria mathematical programming methods.This paper deals with the development of an integrated quantitative model for offset (countertrade) planning. The model includes multiple conflicting goals with inconsistent units requiring prioritization. As common in today's business environment, a single methodology for solving problems is insufficient. This paper discusses a case in which business decision-makers can take existing models from analytic hierarchy process (AHP) in socio-economic literature and apply it to the well-established goal programming model for an empirical example, based on the data obtained from the U.S. aerospace companies. The model is solved by a Micro Management Science computer software and its result is analyzed. The model validation is performed by sensitivity and factor analyses.     

A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming

The U.S. commercial airline movement to “hub” operations has increased rapidly over the past several years. This trend will grow with the introduction of the Wayport concept. These giant “people exchange” facilities will feature multiple runways and massive concourses. While the Wayport developers may automate the ground movement of passengers, the sheer size of the facilities and the anticipated close scheduling of flights will confront the passenger with a problem of new dimension in getting from arrival gate to departure gate. One thing that could help alleviate the situation would be “sensible” assignment of flights to gates - sensible in that the assignment would take into account the communion of interest of the passengers. Other things being equal, the positioning of incoming flights should take into account the distribution of passengers among connecting flights. The larger the number of passengers arriving on flight X for destination A, the closer flight X should be positioned to the flight departing for A. This inquiry looks conceptually at this problem, reducing the distance passengers must walk from gate to gate. The criterion selected is minimization of the total passenger-distance travel for a given arrival-departure cycle. The problem can be conveniently cast as a 0,1 Linear Programming (LP) problem. The author discusses derivation of problem parameters and then solves several representative problems. A unique feature of the LP approach is the availability with the optimal solution of cost factors and assignments for suboptimal solutions. Minor changes in the input data do not require reworking the problem. Although the solution is characterized as conceptual, some ideas are given for practical use of the solution methodology in a dynamic airport environment.     

A knowledge-based system for information management in an automated and integrated manufacturing system

In recent years there has been considerable interest in flexible automation of manufacturing processes in an effort to improve the productivity of manufacturing industry. Central to an integrated, flexible and intelligent manufacturing system is the information management function. The sharing of data is the basis of flexible and intelligent decision-making, the means of integrating the system components, the mode of synchronizing their processes and the method of maintaining the consistency of their states.

It appears that the data management and manipulation function in manufacturing systems is increasingly becoming a bottleneck for further performance improvement of manufacturing systems. New information management systems need to be developed that meet the needs of modern manufacturing systems in terms of efficiency, flexibility, reliability and intelligence. A new model for an integrated manufacturing information system is presented. A double structure of two parallel but independent system is proposed for manufacturing control and manufacturing information management. The objective is to improve service efficiency. representational adequacy, consistency of information and reliability in the information system.     

A New Integrated System of Logic Programming and Relational Database

Based on the study of the current two methods-interpretation and compilation-for the integration of logic programming and relational database,a new precompilation-based interpretive approach is proposed.It inherits the advantages of both methods,but overcomes the drawbacks of theirs.A new integrated system based on this approach is presented,which has been implemented on Micro VAX Ⅱ and applied to practise as the kernel of the GKBMS knowledge base management system.Also discussed are the key implementation techniques,including the coupling of logic and relational database systems,the compound of logic and relational database languages,the partial evaluation and static optimization of user‘s programs,fact scheduling and version management in problem-solving.     

A knowledge-based task-level programming and execution environment for robots

A knowledge-based framework to support task-level programming and operational control of robots is described. Our bask intention is to enhance the intelligence of a robot control system so that it may carefully coordinate the interactions among discrete, asynchronous and concurrent events under the constraints of action precedence and resource allocation. We do this by integrating both off-line and on-line planning capabilities in a single framework. The off-line phase is equipped with proper languages for describing workbenches, specifying tasks, and soliciting knowledge from the user to support the execution of robot tasks. A static planner is included in the phase to conduct static planning, which develops local plans for various specific tasks. The on-line phase is designed as a dynamic control loop for the robot system. It employs a dynamic planner to tackle any contingent situations during the robot operations. It is responsible for developing proper working paths and motion plans to achieve the task goals within designated temporal and resource constraints. It is implemented in a distributed and cooperative blackboard system, which facilitates the integration of various types of knowledge. Finally, any failures from the on-line phase are fed back to the off-line phase. This forms the interaction between the off-line and on-line phases and introduces an extra closed loop opportunistically to tune the dynamic planner to adapt to the variation of the working environment in a long-term manner.     

Robust assignment of airport gates with operational safety constraints

This paper reviews existing approaches to the airport gate assignment problem (AGAP) and presents an optimization model for the problem considering operational safety constraints. The main objective is to minimize the dispersion of gate idle time periods (to get robust optimization) while ensuring appropriate matching between the size of each aircraft and its assigned gate type and avoiding the potential hazard caused by gate apron operational conflict. Genetic algorithm is adopted to solve the problem. An illustrative example is given to show the effectiveness and efficiency of the algorithm. The algorithm performance is further demonstrated using data of a terminal from Beijing Capital International Airport (PEK).     

Aircraft identification integrated into an airport surface surveillance video system

A video aircraft identification algorithm, based on tail number recognition, is proposed as part of a global airport surveillance video system. The recognition procedure searches and detects the presence of the tail number in the image and then recognizes the tail number using pattern matching techniques. The identification system has been designed to deal with airport real images, taking into account letter size differences and potential deformations. Finally, the aircraft identification system calculates the joint probability of each tail number in the airport database. The tail number maximizing the joint probability is selected. Results show that the identification procedure achieves a robust identification using the database.Received: 7 November 2002, Accepted: 21 January 2004, Published online: 27 May 2004 Correspondence to: J.A. Besada     

复合类别航站楼分配问题的改进和声搜索算法

随着航空运输业的蓬勃发展,如何在硬件条件受限的情况下尽量提高机场的运行效率来满足日益增长的航班起降需求,日益受到关注.为了对机场航站楼登机门分配问题进一步优化,提出一种考虑登机门复合类别的航站楼分配问题,并建立数学模型,描述在航线类别、班机型号以及最短停靠间隔对于登机门选取的约束下,带有临时停机坪辅助的登机门分配优化问题.在模型经过精确算法验证的基础上,为适应登机门问题特性并求解中大规模问题,首次引进和声搜索算法,增加复杂约束条件,对编码解码、初始解产生以及寻优过程进行改进,提出一种更高效的改进和声搜索算法对模型进行求解.通过使用Lingo软件和Matlab软件对中小规模算例分别进行精确求解和智能算法求解,对比表明所提出智能算法的有效性、全局搜索能力以及求解效率.再通过对大规模问题的求解,表明所提出算法在现有条件下能够减小转机旅客的总转机路程,取得了较好的效果.     

A mathematical programming approach to three-dimensional contact problems with friction

The present study is concerned with the numerical treatment of linear elastic contact problems with friction. Making the restriction that the contact surface is constant during the loading history, we obtain a variational inequality formulation, which justifies a finite element approximation. The finitedimensional problem so obtained is shown to be equivalent to a problem of mathematical programming—namely, a parametric linear complementarity problem (LCP) involving derivatives. A solution procedure for such problems has previously been suggested. In this paper, the conditions under which this procedure defines a unique solution map, which describes the evolution of contact stresses and displacements for a prescribed load history, are given. As an application of the theory presented, the indentation of a halfspace by a flat-ended square punch is considered. Both the loading cases of a vertical displacement of the punch that increases monotonically and the gradual removal of the same displacement are considered.     

A mathematical approach to large scale personnel assignment

This paper reports on a computer-based system for military personnel assignment. Transportation costs, job skill requirements and individual skills and preferences are manipulated to produce three measures of assignment costs. The weighted combination of these measures is the total cost of each assignment. An algorithm based on the Ford-Fulkerson network flow approach is used to generate the optimal set of assignments by identifying the set which minimizes the total cost of all possible assignments.     

A regression tree approach using mathematical programming

Regression analysis is a machine learning approach that aims to accurately predict the value of continuous output variables from certain independent input variables, via automatic estimation of their latent relationship from data. Tree-based regression models are popular in literature due to their flexibility to model higher order non-linearity and great interpretability. Conventionally, regression tree models are trained in a two-stage procedure, i.e. recursive binary partitioning is employed to produce a tree structure, followed by a pruning process of removing insignificant leaves, with the possibility of assigning multivariate functions to terminal leaves to improve generalisation. This work introduces a novel methodology of node partitioning which, in a single optimisation model, simultaneously performs the two tasks of identifying the break-point of a binary split and assignment of multivariate functions to either leaf, thus leading to an efficient regression tree model. Using six real world benchmark problems, we demonstrate that the proposed method consistently outperforms a number of state-of-the-art regression tree models and methods based on other techniques, with an average improvement of 7–60% on the mean absolute errors (MAE) of the predictions.     

A mathematical programming approach to salary administration

This paper discusses a mathematical programming approach to designing an executive salary administration guide based on the importance of the positions and the quality of job performance. The two fundamental concepts of the salary system that is considered in this study are the compensation plan and the classification plan. The purpose of the compensation plan, and the objective of the paper, is to develop a salary guide for given results from the classification plan. The paper assumes an understanding of basic principles of job evaluation and some exposure to formulation of mathematical models. Emphasis is put on the formulation and linearization of the models, rather than on development of solution techniques that would exploit the particular structure of the models.     

A mathematical model for integrated diagnostics

The authors expand on the form of the information flow model they introduced previously, (see ibid., vol.8, no.3, p.16-30 (1991)). Compiling the model requires three algorithms for determining higher-order relationships. One of these, the algorithm for computing logical closure, helps to simplify the modeling task. The authors also introduce a hypothetical antitank missile launcher to illustrate concepts and computations presented previously     

Multi-choice multi-objective mathematical programming model for integrated production planning: a case study

This article develops a multi-choice multi-objective linear programming model in order to solve an integrated production planning problem of a steel plant. The aim of the integrated production planning problem is to integrate the planning sub-functions into a single planning operation. The sub-functions are formulated by considering the capacity of different units of the plant, cost of raw materials from various territories, demands of customers in different geographical locations, time constraint for delivery the products, production cost and production rate at different stages of production process. Departure cost is also considered in the formulation of mathematical programming model. Some of the parameters are decided from a set of possible choices, therefore such parameters are considered as multi-choice type. Multi-choice mathematical programming problem cannot be solved directly. Therefore an equivalent multi-objective mathematical programming model is established in order to find the optimal solution of the problem. Computation of the mathematical programming model is performed with the practical production data of a plant to study the methodology.