A Lagrangian relaxation based heuristic for the consolidation problem of airfreight forwarders

International air cargo is an operation-intensive industry, involving complex procedures and many players. As an important player, airfreight forwarders need to consolidate the collected goods skillfully in order to satisfy the requirements of the shippers and, at the same time minimize the expense charged by the airlines. However, the air cargo rate structure is very complicated, making the consolidation a difficult mixed-integer programming problem for the airfreight forwarder. In this paper, the consolidation problem is first transformed into a well-known set covering problem by treating a feasible consolidated shipment as a set. Lagrangian Relaxation is used as the backbone to develop a recursive heuristic algorithm. Based on the numerical experiment, the heuristic algorithm generates solutions very close to optimality. In particular, a sensitivity analysis is performed with respect to the degree of concavity. The results suggest that the solution algorithm can be used as a core module of the decision support system for air cargo consolidation.     

Assessment of carbon emission costs for air cargo transportation

This study presents a set of models that calculate carbon emissions in individual phases of flight during air cargo transportation, investigates resultant carbon footprints by aircraft type and flight route, and estimates increases in transportation costs for airlines due to carbon taxes imposed by the EU ETS. The estimated results provide useful references for airlines in aircraft assignment on different routes and in aircraft selection for new purchases. Validation of the model is conducted by simulating the potential impact of the implementation of the EU ETS on costs of air cargo transportation for six routes and six types of aircraft. Results show that the impact may be subject to various factors including unit carbon emissions per aircraft, aviation emission allowances per airline, and carbon trading prices; and that increases in costs of air cargo transportation range from 0% to 5.27% per aircraft per route. Therefore, the implementation of the EU ETS may encourage airlines to cut down their operating costs by reducing their carbon emissions, thereby ameliorating greenhouse gas pollution caused by air cargo transportation.     

Air cargo operations: Literature review and comparison with practices

This study reviews the literature on air cargo operations and compares theoretical studies with the practical problems of airlines, freight forwarders, and terminal service providers. In particular, we review studies in which mathematical models were used to identify the essential characteristics of air cargo operations, such as the intrinsic differences from passenger operations, and to explore the service processes in air cargo operations. The typical models used in previous studies are summarized. We then highlight the insightful findings from an industrial interview and present the gaps between previous research and practical realities. We finally discuss the new research opportunities of air cargo operations according to the gaps.     

Coordinated scheduling models for allied airlines

Recently, as a means of forming global networks and improving operation efficiency, major air carriers have increasingly entered into alliances with other carriers. Fleet routing and flight scheduling are not only important in individual airline operations, but also affect the alliances. The setting of a good flight schedule can not only enhance allied airline operating performance, but can also be a useful reference for alliance decision-making. In this research, we develop several coordinated scheduling models, which will help the allied airlines solve for the most satisfactory fleet routes and timetables under the alliance. We employ network flow techniques to construct the models. The models are formulated as multiple commodity network flow problems which can be solved using a mathematical programming solver. Finally, to evaluate the models, we perform a case study based on real operating data from two Taiwan airlines. The preliminary results are good, showing that the models could be useful for airline alliances.     

The integration of Taiwanese and Chinese air networks for direct air cargo services

The two sides of the Taiwan Strait perform mutually dependent but complementary activities in the global manufacturing supply-chain. As a result, trade between Taiwan and China grew in double digits annually in the 1990s. With growing economic ties, direct air links are inevitable. In this research, we analyzed government documents and interviewed the air cargo carriers and airlines that currently serve the Taiwan–China air cargo market. This information enabled us to tabulate the trade, estimate the airport-to-airport air cargo demand and calibrate the international and domestic freight tariffs. We used a connectivity measurement and classified Chinese airports into national, regional and local classes in a hub-and-spoke air cargo network. We developed a mathematical model and a branch-and-bound algorithm. The results showed that at least two transit airports are economically necessary for a Taiwan–China air link. Shanghai and Xiamen were always the top two transit airports. The third airport would be Changsha if the decision becomes three air-links. These links are different from the top three passenger transit airports, Fuzhou, Xiamen and Shanghai, even though the cost saving is moderate.     

Performance based clustering for benchmarking of US airports

Managing service operations is gaining significant attention in both academic and practitioner circles. In this broad area, performance evaluation and process improvement of airlines and air carriers has been the focus of several studies. Although efficient airport operations are critical for improved performance of airlines and air carriers, few studies have focused on airport performance measurement. This study evaluates the operational efficiencies of 44 major US airports across 5 years using multi-criteria non-parametric models. These efficiency scores are treated by a clustering method in identifying benchmarks for improving poorly performing airports. Efficiency measures are based on four resource input measures including airport operational costs, number of airport employees, gates and runways, and five output measures including operational revenue, passenger flow, commercial and general aviation movement, and total cargo transportation. The methodology presented here can be generalized to other industries and institutions.     

航空公司安全管理绩效动态提升机制

为解决航空公司安全管理决策短期化、滞后化问题,有效提升其安全管理水平,在民航安全管理理论系统分析的基础上,深入挖掘安全管理绩效要素及其影响路径,构建了航空公司安全管理绩效系统动力学模型。通过专家访谈法确定了各要素指标间的影响关系及其权重,并运用VENSIM软件对模型进行了仿真,结果表明:当航空公司安全管理绩效达到某种程度后,其提升速率呈减缓趋势,需及时调整安全投入策略;此时安全政策和目标、安全监督检查、安全保障资源和安全沟通可作为未来提升安全管理绩效的最佳干预策略组合,为航空公司的安全管理决策提供科学依据。     

A bi-objective dynamic programming approach for airline green fleet planning

Ensuring a fleet of green aircraft is a basic step in mitigating aviation pollution issues that are expected to be worsen in the coming years due to rapid air traffic growth. This study proposed a novel methodology in green fleet planning in which both profit and green performance of airline are considered simultaneously and explicitly. To do this, a Green Fleet Index (GFI) is derived as an indicator to quantify the green performance of airline’s fleet. It measures the degree of airline compliance with a standard requirement in terms of emission, noise, and fuel consumption. A bi-objective dynamic programming model is then formulated to find optimal aircraft acquisition (lease or purchase) decision by minimizing GFI and maximizing profit. Several interesting results are obtained: (1) considering environmental issue as secondary objective yields a greener fleet; (2) airline’s profit is affected, but could be recovered from environmental cost savings; (3) increasing load factor is an effective operational improvement strategy to enhance airline’s green performance and raise profit level. It is anticipated that the framework developed in this study could assist airlines to make a smart decision when considering the need to be green.     

Optimisation of motorway operations via ramp metering and variable speed limits

This paper presents a modelling and optimisation framework for deriving ramp metering and variable speed control strategies. We formulate the optimal control problems aiming to minimise the travel delay on motorways based upon a macroscopic cell transmission model of traffic. The optimal ramp metering optimisation is formulated as a linear programming (LP) while the variable speed control problem is formulated as a mixed integer LP. The optimisation models are applied to a real scenario over a section of M25 motorway in the UK. This paper also includes various analyses on the sensitivity of the optimal control solutions with respect to different network configurations and model assumptions.     

Itinerary choice and advance ticket booking for high-speed-railway network services

This paper formulates and examines the passenger flow assignment (itinerary choice) problem in high-speed railway (HSR) systems with multiple-class users and multiple-class seats, given the train schedules and time-varying travel demand. In particular, we take into account advance booking cost of travelers in the itinerary choice problem. Rather than a direct approach to model advance booking cost with an explicit cost function, we consider advance booking cost endogenously, which is determined as a part of the passenger choice equilibrium. We show that this equilibrium problem can be formulated as a linear programming (LP) model based on a three-dimension network representation of time, space, and seat class. At the equilibrium solution, a set of Lagrange multipliers for the LP model are obtained, which are associated with the rigid in-train passenger capacity constraints (limited numbers of seats). We found that the sum of the Lagrange multipliers along a path in the three-dimension network reflects the advance booking cost of tickets (due to advance/early booking to guarantee availability) perceived by the passengers. Numerical examples are presented to demonstrate and illustrate the proposed model for the passenger assignment problem.     

Evaluating airlines with slack‐based measures and meta‐frontiers

This study develops a new performance evaluation model, called the meta dynamic network slack‐based measure (MDN‐SBM). This model incorporates the concept of meta‐frontiers to facilitate comparisons of performance of decision making units, while at the same time it generalizes the slack‐based measure (SBM), network SBM, and dynamic SBM. This MDN‐SBM model is capable of dealing with two important special features of the transportation industry: unfavorable accidents and non‐storable goods, i.e. available seat‐kilometers that are wasting assets that lose value completely if unsold before departure. Hence, this generalized model contains higher differentiable capability than all its SBM‐related submodels in the literature. To demonstrate, 35 international airlines with two divisions (production and consumption) in three terms (one‐year time periods from 2007 to 2009) have been analyzed using meta‐performance efficiency measures (ME) for all decision making units and have also been compared by geographical area (Asia‐Pacific, N. America/Europe). The numerical example and comparison validate the proposed MDN‐SBM model and suggest the airlines should put more focus on input resources reduction for productivity improvement. Copyright © 2016 John Wiley & Sons, Ltd.     

Model uncertainty and the management of a system of infrastructure facilities

The network-level infrastructure management problem involves selecting and scheduling maintenance, repair, and rehabilitation (MR&R) activities on networks of infrastructure facilities so as to maintain the level of service provided by the network in a cost-effective manner. This problem is frequently formulated as a Markov decision problem (MDP) solved via linear programming (LP). The conditions of facilities are represented by elements of discrete condition rating sets, and transition probabilities are employed to describe deterioration processes. Epistemic and parametric uncertainties not considered within the standard MDP/LP framework are associated with the transition probabilities used in infrastructure management optimization routines. This paper contrasts the expected costs incurred when model uncertainty is ignored with those incurred when this uncertainty is explicitly considered using robust optimization. A case study involving a network-level pavement management MDP/LP problem demonstrates how explicitly considering uncertainty may limit worst-case MR&R expenditures. The methods and results can also be used to identify the costs of uncertainty in transition probability matrices used in infrastructure management systems.     

The flight perturbation problem

Airlines spend considerable time, effort and financial resources on planning. It is essential to create a competitive timetable and construct a fleet and a crew schedule that utilizes these resources to the maximum. Unfortunately, it is all too common that an airline is faced with the necessity of reconstructing their schedules due to some unforeseen event, for example an aircraft breakdown or a crew member that is indisposed. In this paper, an application that can help airlines solve the complex problem of reconstructing aircraft schedules is presented. A mixed integer multicommodity flow model with side constraints is developed and further reformulated into a set packing model using the Dantzig—Wolfe decomposition. Cancellations, delays and aircraft swaps are used to resolve the perturbation, and the model ensures that the schedule returns to normal within a certain time. Two column generation schemes for heuristically solving the model are tested on real problem data obtained from a Swedish domestic airline. The computational tests show that the application is capable of presenting high quality solutions in a few seconds and therefore can be used as a dynamic decision support tool by the airlines.     

An optimal aircraft fleet management decision model under uncertainty

Decision planning for an efficient fleet management is crucial for airlines to ensure a profit while maintaining a good level of service. Fleet management involves acquisition and leasing of aircraft to meet travelers' demand. Accordingly, the methods used in modeling travelers' demand are crucial as they could affect the robustness and accuracy of the solutions. Compared with most of the existing studies that consider deterministic demand, this study proposes a new methodology to find optimal solutions for a fleet management decision model by considering stochastic demand. The proposed methodology comes in threefold. First, a five‐step modeling framework, which is incorporated with a stochastic demand index (SDI), is proposed to capture the occurrence of uncertain events that could affect the travelers' demand. Second, a probabilistic dynamic programming model is developed to optimize the fleet management model. Third, a probable phenomenon indicator is defined to capture the targeted level of service that could be achieved satisfactorily by the airlines under uncertainty. An illustrative case study is presented to evaluate the applicability of the proposed methodology. The results show that it is viable to provide optimal solutions for the aircraft fleet management model. Copyright © 2013 John Wiley & Sons, Ltd.     

Airline-driven ground delay programs: A benefits assessment

Three decades of research studies in ground delay program (GDP) decision-making, and air traffic flow management in general, have produced several analytical models and decision support tools to design GDPs with minimum delay costs. Most of these models are centralized, i.e., the central authority almost completely decides the GDP design by optimizing certain centralized objectives. In this paper, we assess the benefits of an airline-driven decentralized approach for designing GDPs. The motivation for an airline-driven approach is the ability to incorporate the inherent differences between airlines when prioritizing, and responding to, different GDP designs. Such differences arise from the airlines’ diverse business objectives and operational characteristics. We develop an integrated platform for simulating flight operations during GDPs, an airline recovery module for mimicking the recovery actions of each individual airline under a GDP, and an algorithm for fast solution of the recovery problems to optimality. While some of the individual analytical components of our framework, model and algorithm share certain similarities with those used by previous researchers, to the best of our knowledge, this paper presents the first comprehensive platform for simulating and optimizing airline operations under a GDP and is the most important technological contribution of this paper. Using this framework, we conduct detailed computational experiments based on actual schedule data at three of the busiest airports in the United States. We choose the recently developed Majority Judgment voting and grading method as our airline-driven decentralized approach for GDP design because of the superior theoretical and practical benefits afforded by this approach as shown by multiple recent studies. The results of our evaluation suggest that adopting this airline-driven approach in designing the GDPs consistently and significantly reduces airport-wide delay costs compared to the state-of-the-research centralized approaches. Moreover, the cost reduction benefits of the resultant airline-driven GDP designs are equitably distributed across different airlines.     

Dynamic stability metrics for the container loading problem

The Container Loading Problem (CLP) literature has traditionally evaluated the dynamic stability of cargo by applying two metrics to box arrangements: the mean number of boxes supporting the items excluding those placed directly on the floor (M1) and the percentage of boxes with insufficient lateral support (M2). However, these metrics, that aim to be proxies for cargo stability during transportation, fail to translate real-world cargo conditions of dynamic stability.In this paper two new performance indicators are proposed to evaluate the dynamic stability of cargo arrangements: the number of fallen boxes (NFB) and the number of boxes within the Damage Boundary Curve fragility test (NB_DBC). Using 1500 solutions for well-known problem instances found in the literature, these new performance indicators are evaluated using a physics simulation tool (StableCargo), replacing the real-world transportation by a truck with a simulation of the dynamic behaviour of container loading arrangements.Two new dynamic stability metrics that can be integrated within any container loading algorithm are also proposed. The metrics are analytical models of the proposed stability performance indicators, computed by multiple linear regression. Pearson’s r correlation coefficient was used as an evaluation parameter for the performance of the models. The extensive computational results show that the proposed metrics are better proxies for dynamic stability in the CLP than the previous widely used metrics.     

Designing an integrated distribution system for catering services for high-speed railways: A three-echelon location routing model with tight time windows and time deadlines

An emerging task in catering services for high-speed railways (CSHR) is to design a distribution system for the delivery of high-quality perishable food products to trains in need. This paper proposes a novel model for integrating location decision making with daily rail catering operations, which are affected by various aspects of rail planning, to meet time-sensitive passenger demands. A three-echelon location routing problem with time windows and time budget constraints (3E-LRPTWTBC) is thus proposed toward formulating this integrated distribution system design problem. This model attempts to determine the capacities/locations of distribution centers and to optimize the number of meals delivered to stations. The model also attempts to generate a schedule for refrigerated cars traveling from distribution centers to rail stations for train loading whereby meals can be catered to trains within tight time windows and sold before a specified time deadline. By relaxing the time-window constraints, a relaxation model that can be solved using an off-the-shelf mixed integer programming (MIP) solver is obtained to provide a lower bound on the 3E-LRPTWTBC. A hybrid cross entropy algorithm (HCEA) is proposed to solve the 3E-LRPTWTBC. A small-scale case study is implemented, which reveals a 9.3% gap between the solution obtained using the HCEA and that obtained using the relaxation model (RM). A comparative analysis of the HCEA and an exhaustive enumeration algorithm indicates that the HCEA shows good performance in terms of computation time. Finally, a case study considering 156 trains on the Beijing-Shanghai high-speed corridor and a large-scale case study considering 1130 trains on the Chinese railway network are addressed in a comprehensive study to demonstrate the applicability of the proposed models and algorithm.     

Cargo Container Loading Plan Model and Solution Method for International Air Express Carriers

Abstract

In this article, a cargo container loading plan model is developed based on the operations of FedEx, the international air express carrier. The objective is to minimize total container handling cost, subject to related operating constraints. The model is expected to be a useful planning tool whereby international air express carriers such as FedEx can decide on container loading plans that will lead to lower operating costs, thus enhancing profits and market competitiveness. The model is formulated as a non-linear mixed integer program that is characterized as NP-hard. A solution method is then developed, with the use of the mathematical programming solver, CPLEX, to solve the problem efficiently. To evaluate the model and the solution method, we perform a case study using data from FedEx. The preliminary results indicate that the model and the solution method are both efficient and effective.     

A decision support system for integrated hazardous materials routing and emergency response decisions

Hazardous materials routing constitutes a critical decision in mitigating the associated transportation risk. This paper presents a decision support system for assessing alternative distribution routes in terms of travel time, risk and evacuation implications while coordinating the emergency response deployment decisions with the hazardous materials routes. The proposed system provides the following functionalities: (i) determination of alternative non-dominated hazardous materials distribution routes in terms of cost and risk minimization, (ii) specification of the hazardous materials first-response emergency service units locations in order to achieve timely response to an accident, and (iii) determination of evacuation paths from the impacted area to designated shelters and estimation of the associated evacuation time. The proposed system has been implemented, used and evaluated for assessing alternative hazardous materials routing decisions within the heavily industrialized area of Thriasion Pedion of Attica, Greece. The implementation of the aforementioned functionalities is based on two new integer programming models for the hazardous materials routing and the emergency response units location problems, respectively. A simplified version of the routing model is solved by an existing heuristic algorithm developed by the authors. A new Lagrangean relaxation heuristic algorithm has been developed for solving the emergency response units location problem. The focus of this paper is on the exposition of the proposed decision support system components and functionalities. Special emphasis is placed on the presentation of the two new mathematical models and the new solution method for the location model.     

Optimal shipment decisions for an airfreight forwarder: Formulation and solution methods

We study the freight forwarder’s shipment planning problem in an airfreight forwarding network where a set of cargo shipments have to be transported to given destinations. We provide mixed integer programming formulations that use piecewise-linear cargo rates and account for volume and weight constraints, flight departure/arrival times, as well as shipment-ready times.After exploring the solution of such models using CPLEX, we devise two solution methodologies to handle large problem sizes. The first is based on Lagrangian relaxation, where the problems decompose into a set of knapsack problems and a set of network flow problems. The second is a local branching heuristic that combines branching ideas and local search. The two approaches show promising results in providing good quality heuristic solutions within reasonable computational times, for difficult and large shipment consolidation problems.