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 de-icing vehicles within airport logistics: a heuristic algorithm and performance evaluation

Most delays in the air transport occur at the airport. A particular reason is the complexity of managing the large number of supporting flows in airport logistics. We consider the optimisation problem of scheduling de-icing vehicles that is one of the key supporting logistic flows in the turn-around process of aircraft. The objective is to minimise the delay of flights due to de-icing, and the travel distance of the de-icing vehicles. We study the complexity of the problem, and develop a solution algorithm using greedy randomised adaptive search. A case study of real-life data from Stockholm Arlanda Airport shows that optimised schedule leads to significantly better performance in comparison to intuitive and simple scheduling strategies. The benefit of optimisation in reducing the waiting time for de-icing is further demonstrated via dynamic simulations.     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

Metaheuristic approaches to the placement of suicide bomber detectors

Suicide bombing is an infamous form of terrorism that is becoming increasingly prevalent in the current era of global terror warfare. We consider the case of targeted attacks of this kind, and the use of detectors distributed over the area under threat as a protective countermeasure. Such detectors are non-fully reliable, and must be strategically placed in order to maximize the chances of detecting the attack, hence minimizing the expected number of casualties. To this end, different metaheuristic approaches based on local search and on population-based search (such as a hill climber, different Greedy randomized adaptive search procedures, an evolutionary algorithm and several estimation of distribution algorithms) are considered and benchmarked against a powerful greedy heuristic from the literature. We conduct an extensive empirical evaluation on synthetic instances featuring very diverse properties. Most metaheuristics outperform the greedy algorithm, and a hill-climber is shown to be superior to remaining approaches. This hill-climber is subsequently subject to a sensitivity analysis to determine which problem features make it stand above the greedy approach, and is finally deployed on a number of problem instances built after realistic scenarios, corroborating the good performance of the heuristic.     

On some new types of greedy chains and greedy linear extensions of partially ordered sets

Two new types of greedy chains, strongly and semi-strongly greedy, in posets are defined and their role in solving the jump number problem is discussed in this paper. If a poset P contains a strongly greedy chain C then C may be taken as the first chain in an optimal linear extension of P. If a poset P has no strongly greedy chains then it contains an optimal linear extension which starts with a semi-strongly greedy chain. Hence, every poset has an optimal linear extension which consists of strongly and semi-strongly greedy chains. Algorithmic issues of finding such linear extensions are discussed elsewhere (Syslo, 1987, 1988), where we provide a very efficient method for solving the jump number problem which is polynomial in the class of posets whose arc representations contain a bounded number of dummy arcs. In another work, the author has recently demonstrated that this method restricted to interval orders gives rise to 3/2-approximation algorithm for such posets.     

On the optimality of the greedy solutions of the general knapsack problems

Summary: In this paper we submit a unified discussion of some closely related results which were achieved independently in number theory and integer programming, and we partially generalize them. In the unified discussion we treat together two problems where the greedy method has different characters, in the first one it is an internal-point algorithm, in the second one it is an outer-point method. We call a knapsack problem "pleasant" if the greedy solution is optimal for every right-hand side. A sufficient and two finite necessary and sufficient conditions for the pleasantness of a problem are discussed. The sufficient condition can be checked very easily. The paper is finished with an error analysis of some nonpleasant problems     

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.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

有元素类型约束的k-划分问题研究

研究有元素类型约束且每个元素权重为正数的k-集合划分问题,元素类型约束指k-划分后每个集合所包含的元素的类型均不同. 该问题是对k-划分问题(k-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景. 提出基于LPT算法思想的贪婪算法,并得出以下结论: k≤2, 该算法给出最优解: k>2, 最坏情况下的性能比为2-m^-1, 这里m指待分配集合的数量.     

On the resolution of certain discrete univariate max–min problems

Graph coloring is a classical NP-hard combinatorial optimization problem with many practical applications. A broad range of heuristic methods exist for tackling the graph coloring problem: from fast greedy algorithms to more time-consuming metaheuristics. Although the latter produce better results in terms of minimizing the number of colors, the former are widely employed due to their simplicity. These heuristic methods are centralized since they operate by using complete knowledge of the graph. However, in real-world environmets where each component only interacts with a limited number of other components, the only option is to apply decentralized methods. This paper explores a novel and simple algorithm for decentralized graph coloring that uses a fixed number of colors and iteratively reduces the edge conflicts in the graph. We experimentally demonstrate that, for most of the tested instances, the new algorithm outperforms a recent and very competitive algorithm for decentralized graph coloring in terms of coloring quality. In our experiments, the fixed number of colors used by the new algorithm is controlled in a centralized manner.     

A Combinatorial Approach to Piecewise Linear Time Series Analysis

Over recent years, several nonlinear time series models have been proposed in the literature. One model that has found a large number of successful applications is the threshold autoregressive model (TAR). The TAR model is a piecewise linear process whose central idea is to change the parameters of a linear autoregressive model according to the value of an observable variable, called the threshold variable. If this variable is a lagged value of the time series, the model is called a self-exciting threshold autoregressive (SETAR) model. In this article, we propose a heuristic to estimate a more general SETAR model, where the thresholds are multivariate. We formulate the task of finding multivariate thresholds as a combinatorial optimization problem. We develop an algorithm based on a greedy randomized adaptive search procedure (GRASP) to solve the problem. GRASP is an iterative randomized sampling technique that has been shown to quickly produce good quality solutions for a wide variety of optimization problems. The proposed model performs well on both simulated and real data.     

Maximally Disjoint Solutions of the Set Covering Problem

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP-complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, extensive computational tests are given demonstrating the nature of these algorithms. These tests are carried out both on randomly generated problems and on problems found in the literature.     

Optimal partial hedging of an American option: shifting the focus to the expiration date

As a main contribution we present a new approach for studying the problem of optimal partial hedging of an American contingent claim in a finite and complete discrete-time market. We assume that at an early exercise time the investor can borrow the amount she has to pay for the option holder by entering a short position in the numéraire asset and that this loan in turn will mature at the expiration date. We model and solve a partial hedging problem, where the investor’s purpose is to find a minimal amount at which she can hedge the above-mentioned loan with a given probability, while the potential shortfall is bounded above by a certain number of numéraire assets. A knapsack problem approach and greedy algorithm are used in solving the problem. To get a wider view of the subject and to make interesting comparisons, we treat also a closely related European case as well as an American case where a barrier condition is applied.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

Some properties of optimal schedules for the Johnson problem with preemption

The properties are under study of the optimal schedules for the NP-hard Johnson problem with preemption. The length of an optimal schedule is shown to coincide with the total length of some subset of operations. These properties demonstrate that the optimal schedule of every instance of the problem can be found by a greedy algorithm (for the properly defined priority orders of operations on machines). This yields the first exact algorithm for the problem known since 1978. It is shown that the number of interruptions in a greedy schedule (and therefore, in the optimal schedule) is at most the number of operations, which is significantly better than the available upper bounds on the number of interruptions in the optimal schedule.     

Optimization over the polyhedron determined by a submodular function on a co-intersecting family

A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities.     

求解多维约束下下模函数最大值的改进贪婪算法

提出了多维约束下下模函数最大值问题,分析其在组合优化中的重要应用.此问题是NP-难的,故给出了求解该问题的改进贪婪算法.最后,从理论上证明了这一算法的时间复杂性和性能保证.说明该算法是多项式时间近似算法,同时也具有较好的性能保证.     

Another greedy heuristic for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.     

The traveling purchaser problem with stochastic prices: Exact and approximate algorithms

The paper formulates an extension of the traveling purchaser problem where multiple types of commodities are sold at spatially distributed locations with stochastic prices (each following a known probability distribution). A purchaser’s goal is to find the optimal routing and purchasing strategies that minimize the expected total travel and purchasing costs needed to purchase one unit of each commodity. The purchaser reveals the actual commodity price at a seller upon arrival, and then either purchases the commodity at the offered price, or rejects the price and visits a next seller. In this paper, we propose an exact solution algorithm based on dynamic programming, an iterative approximate algorithm that yields bounds for the minimum total expected cost, and a greedy heuristic for fast solutions to large-scale applications. We analyze the characteristics of the problem and test the computational performance of the proposed algorithms. The numerical results show that the approximate and heuristic algorithms yield near-optimum strategies and very good estimates of the minimum total cost.     

A multi-heuristic approach for solving the pre-marshalling problem

Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.