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.     

Routing and scheduling of RoRo ships with stowage constraints

Roll-on/Roll-off ships are used for international transport of vehicles and other rolling equipment. We consider the problem where a ship sails between two geographical regions, picking up cargo in the first and making deliveries to the second. Several variations are considered with optional cargoes, flexible cargo quantities, and ship stability restrictions. Decisions must be made regarding the route and schedule of the ship as well as the stowage of cargo onboard. The problem is modeled as a mixed integer program, which has been solved using Xpress. In addition, a tailor made heuristic procedure is built using components from tabu search and squeaky wheel optimization. Extensive computational results are presented, showing that the heuristic is able to handle realistically sized problem instances.     

A linear programming-based method for the network revenue management problem of air cargo

One critical operational issue of air cargo operation faced by airlines is the control over the sales of their limited cargo space. Since American Airlines’ successful implementation in the post-deregulation era, revenue management (RM) has become a common practice for the airline industry. However, unlike the air passenger operation supported by well-developed RM systems with advanced decision models, the decision process in selling air cargo space to freight forwarders is usually based on experience, without much support from optimization techniques. This study first formulates a multi-dimensional dynamic programming (DP) model to present a network RM problem for air cargo. In order to overcome the computational challenge, this study develops two linear programming (LP) based models to provide the decision support operationally suitable for airlines. In addition, this study further introduces a dynamic adjustment factor to alleviate the inaccuracy problem of the static LP models in estimating resource opportunity cost. Finally, a numerical experiment is performed to validate the applicability of the developed model and solution algorithm to the real-world problems.     

The Time Dependent Traveling Salesman Planning Problem in Controlled Airspace

The integration of drones into civil airspace is one of the most challenging problems for the automation of the controlled airspace, and the optimization of the drone route is a key step for this process. In this paper, we optimize the route planning of a drone mission that consists of departing from an airport, flying over a set of mission way points and coming back to the initial airport. We assume that during the mission a set of piloted aircraft flies in the same airspace and thus the cost of the drone route depends on the air traffic and on the avoidance maneuvers used to prevent possible conflicts. Two air traffic management techniques, i.e., routing and holding, are modeled in order to maintain a minimum separation between the drone and the piloted aircraft. The considered problem, called the Time Dependent Traveling Salesman Planning Problem in Controlled Airspace (TDTSPPCA), relates to the drone route planning phase and aims to minimize the total operational cost. Two heuristic algorithms are proposed for the solution of the problem. A mathematical formulation based on a particular version of the Time Dependent Traveling Salesman Problem, which allows holdings at mission way points, and a Branch and Cut algorithm are proposed for solving the TDTSPPCA to optimality. An additional formulation, based on a Travelling Salesman Problem variant that uses specific penalties to model the holding times, is proposed and a Cutting Plane algorithm is designed. Finally, computational experiments on real-world air traffic data from Milano Linate Terminal Maneuvering Area are reported to evaluate the performance of the proposed formulations and of the heuristic algorithms.     

A dynamic empty equipment and crew allocation model for long-haul networks

This research develops a realistic and efficient operational model to optimize empty equipment and crew movements in long-haul trucking networks with consolidation, where returning drivers home within a reasonable amount of time is an important issue. The problem can be stated as follows. On a network of consolidation centers, demand is expressed as a set of trailer-loads that need to be moved between each pair of consolidation centers in each time period and the objective is to optimize trailer, tractor and driver movements while ensuring that drivers return home within a pre-determined period of time. In this paper, a dynamic integer programming model is developed and an efficient approximate solution method is proposed, which involves column generation and branch-and-bound. The algorithm switches from a combination of network and primal simplex to dual simplex to overcome the degeneracy problem, which is very common for dynamic networks. This novel approach enables solving large problems with many intervals. We solved problems with up to 30 nodes and 48 periods successfully by using real data provided by a less-than-truckload company, and by generating statistical forecasts based on the real data.     

Empirical estimation of price and income elasticities of air cargo demand: The case of Hong Kong

This paper estimates the price and income elasticities of air cargo demand and examines how they may change after the 2008 financial crisis. Using a set of time series data, we simultaneously estimate the aggregated demand and supply functions of air cargo at Hong Kong International Airport (HKIA). We find that during the entire sampling period of 2001–2013, the price elasticity for air cargo transport demand at HKIA ranges from −0.74 to −0.29, suggesting that air cargo demand in Hong Kong reacts negatively to price (as expected) but does not appear to be very sensitive to price. The income elasticity ranges from 0.29 to 1.47 and appears sensitive to seasonality adjustment approaches. However, in terms of the speed of changes, air cargo demand changes much faster than overall economy, indicating the presence of a pro-cyclical pattern of air cargo traffic with respect to the overall economy. Our analysis shows that air cargo demand becomes more sensitive to changes in both price and income after 2008.     

Liner shipping network design with emission control areas: A genetic algorithm-based approach

To curb emissions, containerized shipping lines face the traditional trade-off between cost and emissions (CO₂ and SO_x) reduction. This paper considers this element in the context of liner service design and proposes a mixed integer linear programming (MILP) model based on a multi-commodity pickup and delivery arc-flow formulation. The objective is to maximize the profit by selecting the ports to be visited, the sequence of port visit, the cargo flows between ports, as well as the number/operating speeds of vessels on each arc of the selected route. The problem also considers that Emission Control Areas (ECAs) exist in the liner network and accounts for the vessel carrying capacity. In addition to using the MILP solver of CPLEX, we develop in the paper a specific genetic algorithm (GA) based heuristic and show that it gives the possibility to reach an optimal solution when solving large size instances.     

Multi-impact optimization to reduce aviation noise and emissions

This paper describes a multi-indicator assessment and minimization problem focused on aviation “Community” noise. The model explores a combined noise and emission objective for airfreight movements at Luxembourg’s Findel Airport. Community noise is evaluated via four population impact indicators emissions are tabulated from in-flight segments in the proximity of the airport and from the contribution of taxiing. A set of scenarios based on trajectory, aircraft scheduling, fleet composition, operational procedures are implemented in software. An integer programming methodology is used to search for minimal environmental impact. An on/off switch allows for an evaluation of each indicator in the objective. Different impacts on the population are explored in a case study involving the Cargolux Airlines International S.A.     

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.     

A Heuristic Algorithm for the Allocation of Airport Runway System Capacity

Abstract

This paper develops a heuristic algorithm for the allocation of airport runway capacity to minimise the cost of arrival and departure aircraft/flight delays. The algorithm is developed as a potential alternative to optimisation models based on linear and integer programming. The algorithm is based on heuristic (‘greedy’) criteria that closely reflect the ‘rules of thumb’ used by air traffic controllers. Using inputs such as arrival and departure demand, airport runway system capacity envelopes and cost of aircraft/flight delays, the main output minimises the cost of arrival and departure delays as well as the corresponding interdependent airport runway system arrival and departure capacity allocation. The algorithm is applied to traffic scenarios at three busy US airports. The results are used to validate the performance of the proposed heuristic algorithm against results from selected benchmarking optimisation models.     

Assessing the effect of urban socioeconomic factors and the financial crisis of 2008 on domestic air cargo traffic in Florida

In this paper, we investigate the relationship between the social and economic attributes of metropolitan areas and their corresponding domestic cargo traffic. We considered a period of 14 years (2003–2016) and studied the impact of population demographics, employment, and regional industries on domestic cargo traffic of a sampled set of metropolitan areas in Florida. We considered all-cargo carriers and mixed passenger–cargo carriers. Our results provide empirical insights into factors determining the air cargo traffic in Florida. Both population and age demographics of a region is shown to be influential on cargo traffic. Manufacturing industries are shown to prefer all-cargo carriers to mixed passenger–cargo carriers and their concentration in a metro area results in an increase of cargo traffic. In contrast, service industries generate low demand for air cargo. Our results show that larger airports tend to attract cargo traffic away from smaller airports in their close proximity. We also provide insights into the impact of the financial crisis of 2008 on domestic cargo traffic in the region. We study the recovery trend and the impact of the high fuel jet prices on slowing down this trend.

     

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.     

An appraisal of a column-generation-based algorithm for centralized train-conflict resolution on a metropolitan railway network

In practice, a train-conflict resolution is decentralized around dispatchers each of whom controls a few segments in a global railway network with her rule-of-thumb to operational data. Conceptually, the global sub-optimality or infeasibility of the decentralized system is resolved by a network controller who coordinates the dispatchers and train operators at the lower layers on a real-time basis. However, such notion of a multi-layer system cannot be effectual unless the top layer is able to provide a global solution soon enough for the dynamic lower layers to adapt in a seamless manner. Unfortunately, a train-conflict resolution problem is NP-hard as formally established in this paper and an effective solution method traded off between computation time and solution quality has been lacking in literature. Thus, we propose a column-generation-based algorithm that exploits the separability of the problem. A key ingredient of the algorithm is an efficient heuristic for the pricing subproblem for column generation. Tested on the real data from the Seoul metropolitan railway network, the algorithm provides near-optimal conflict-free timetables in a few seconds for most cases. The performance of the proposed algorithm is compared to the ones of the previous MIP-based heuristic by Törnquist and Persson (2007) and the priority-based heuristic by Sahin (1999).     

A discrete-convex programming approach to the simultaneous optimization of land use and transportation

Three design problems are discussed in this article. First, it is shown that the network design problem with congestion reduces to an all-or nothing traffic assignment problem under some assumptions on the congestion function and the investment cost function. Second, the land use design problem is formulated as an extension of the Koopmans-Beckmann problem and a heuristic is proposed to solve this problem. Third, it is shown that the seemingly more complex problem of designing jointly a land-use plan and a transportation network reduces to a pure land-use design problem. All that is needed to solve the joint optimization problem is a shortest path algorithm and a heuristic to solve the land use design problem. Computational experience is reported for each algorithm.     

A rolling horizon algorithm for auto-carrier transportation

This paper introduces a rolling horizon algorithm to plan the delivery of vehicles to automotive dealers by a heterogeneous fleet of auto-carriers. The problem consists in scheduling the deliveries over a multiple-day planning horizon during which requests for transportation arrive dynamically. In addition, the routing of the auto-carriers must take into account constraints related to the loading of the vehicles on the carriers. The objective is to minimize the sum of traveled distances, fixed costs for auto-carrier operation, service costs, and penalties for late deliveries. The problem is solved by a heuristic that first selects the vehicles to be delivered in the next few days and then optimizes the deliveries by an iterated local search procedure. A branch-and-bound search is used to check the feasibility of the loading. To handle the dynamic nature of the problem, the complete algorithm is applied repeatedly in a rolling horizon framework. Computational results on data from a major European logistics service provider show that the heuristic is fast and yields significant improvements compared to the sequential solution of independent daily problems.     

The European freight railway system as a hub-and-spoke network

This paper addresses a hub-and-spoke network problem for railroad freight, where a central planner is to find transport routes, frequency of service, length of trains to be used, and transportation volume. Hub-and-spoke networks, often found in air freight, have not been favoured by railways in the past. Such a structure could be profitable, however, if there exist concentrated freight flows on some service links. We formulate a linear integer programming model whose objective function includes not only the typical operational cost, but also cost due to the transit time spent by freight in the network. We then develop heuristic algorithms to solve large scale instances occurring in rail freight systems in France plus Italy; Germany; and a 10-country European network. By assuming that every node is equipped with consolidation capability, we let the final solution naturally reveal potential hub locations, the impact of several of which is studied by sensitivity analysis.     

A bilevel flow model for hazmat transportation network design

In this work we consider the following hazmat transportation network design problem. A given set of hazmat shipments has to be shipped over a road transportation network in order to transport a given amount of hazardous materials from specific origin points to specific destination points, and we assume there are regional and local government authorities that want to regulate the hazmat transportations by imposing restrictions on the amount of hazmat traffic over the network links. In particular, the regional authority aims to minimize the total transport risk induced over the entire region in which the transportation network is embedded, while local authorities want the risk over their local jurisdictions to be the lowest possible, forcing the regional authority to assure also risk equity. We provide a linear bilevel programming formulation for this hazmat transportation network design problem that takes into account both total risk minimization and risk equity. We transform the bilevel model into a single-level mixed integer linear program by replacing the second level (follower) problem by its KKT conditions and by linearizing the complementary constraints, and then we solve the MIP problem with a commercial optimization solver. The optimal solution may not be stable, and we provide an approach for testing its stability and for evaluating the range of its solution values when it is not stable. Moreover, since the bilevel model is difficult to be solved optimally and its optimal solution may not be stable, we provide a heuristic algorithm for the bilevel model able to always find a stable solution. The proposed bilevel model and heuristic algorithm are experimented on real scenarios of an Italian regional network.     

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.     

Determinants of air cargo traffic in California

Studies on the economic impacts of air cargo traffic have been gaining traction in recent years. The slowed growth of air cargo traffic at California’s airports, however, has raised pressing questions about the determinants of air cargo traffic. Specifically, it would be useful to know how California’s air cargo traffic is affected by urban economic characteristics. Accordingly, this study estimates the socioeconomic determinants of air cargo traffic across cities in California. We construct a 7-year panel (2003–2009) using quarterly employment, wage, population, and traffic data for metro areas in the state. Our results reveal that the concentrations of both service and manufacturing employment impact the volume of outbound air cargo. Total air cargo traffic is found to grow faster than population, while the corresponding domestic traffic grows less than proportionally to city size. Wages play a significant role in determining both total and domestic air cargo movement. We provide point estimates for traffic diversion between cities, showing that 80% of air cargo traffic is diverted away from a small city located within 100 miles of a large one. Using socioeconomic and demographic forecasts prepared for California’s Department of Transportation, we also forecast metro-level total and domestic air cargo tonnage for the years 2010–2040. Our forecasts for this period indicate that California’s total (domestic) air cargo traffic will increase at an average rate of 5.9% (4.4%) per year.     

Multi-fleet ferry service network design with passenger preferences for differential services

This paper investigates a multi-fleet ferry routing and scheduling problem that takes into account ferry services with different operation characteristics and passengers with different preferred arrival time windows. The logit model is used to represent passengers’ service choices. The full problem is formulated as a mixed integer nonlinear programming problem and solved with a heuristic procedure that first fixes the demand and then decomposes the resultant model by ferry services. At each iteration of the algorithm, the demand is updated and the relaxed problem is re-solved. Numerical results for the case of ferry service network design in Hong Kong are provided to illustrate the properties of the model and the performance of the heuristic.