An optimization model for a real-time flight scheduling problem

Although airlines plan aircraft routes and crew schedules in advance, perturbations occur everyday. As a result, flight schedules may become infeasible and would need to be updated. This Day of Operations Scheduling problem impacts the entire system of an airline as the decisions enforced are final. When perturbations are relatively small, the airline may be able to at least preserve the planned aircraft and crew itineraries. We propose a model that determines new flight schedules based on planned crew transfers, rest periods, passenger connections, and maintenance. Its dual is shown to be a network model, hence solvable in a real-time environment. In addition, it can be used in more sophisticated operational and planning systems.     

An optimization model for integrated planning of railway traffic and network maintenance

Railway transportation systems are important for society and have many challenging and important planning problems. Train services as well as maintenance of a railway network need to be scheduled efficiently, but have mostly been treated as two separate planning problems. Since these activities are mutually exclusive they must be coordinated and should ideally be planned together. In this paper we present a mixed integer programming model for solving an integrated railway traffic and network maintenance problem. The aim is to find a long term tactical plan that optimally schedules train free windows sufficient for a given volume of regular maintenance together with the wanted train traffic. A spatial and temporal aggregation is used for controlling the available network capacity. The properties of the proposed model are analyzed and computational experiments on various synthetic problem instances are reported. Model extensions and possible modifications are discussed as well as future research directions.     

Bus maintenance systems and maintenance scheduling: model formulations and solutions

This paper deals with the problem of scheduling bus maintenance activities. The scheduling of maintenance activities is an important component in bus transit operations planning process. The other components include network route design, setting timetables, scheduling vehicles, and assignment of drivers. This paper presents a mathematical programming approach to the problem. This approach takes as input a given daily operating schedule for all buses assigned to a depot along with available maintenance resources. It, then, attempts to design daily inspection and maintenance schedules for the buses that are due for inspection so as to minimize the interruptions in the daily bus operating schedule, and maximize the utilization of the maintenance facilities. Three integer programming formulations are presented and different properties of the problem are discussed. Several heuristic methods are presented and tested. Some of these procedures produce very close to optimal solutions very efficiently. In some cases, the computational times required to obtain these solutions are less than 1% of the computational time required for the conventional branch and bound algorithm. Several small examples are offered and the computational results of solving the problem for an actual, 181-bus transit property are reported.     

A model and optimization-based heuristic for the operational aircraft maintenance routing problem

This paper investigates the Operational Aircraft Maintenance Routing Problem (OAMRP). Given a set of flights for a specific homogeneous fleet type, this short-term planning problem requires building feasible aircraft routes that cover each flight exactly once and that satisfy maintenance requirements. Basically, these requirements enforce an aircraft to undergo a planned maintenance at a specified station before accumulating a maximum number of flying hours. This stage is significant to airline companies as it directly impacts the fleet availability, safety, and profitability. The contribution of this paper is twofold. First, we elucidate the complexity status of the OAMRP and we propose an exact mixed-integer programming model that includes a polynomial number of variables and constraints. Furthermore, we propose a graph reduction procedure and valid inequalities that aim at improving the model solvability. Second, we propose a very large-scale neighborhood search algorithm along with a procedure for computing tight lower bounds. We present the results of extensive computational experiments that were carried out on real-world flight networks and attest to the efficacy of the proposed exact and heuristic approaches. In particular, we provide evidence that the exact model delivers optimal solutions for instances with up to 354 flights and 8 aircraft, and that the heuristic approach consistently delivers high-quality solutions while requiring short CPU times.     

Integrated optimization on train scheduling and preventive maintenance time slots planning

We address the problem of simultaneously scheduling trains and planning preventive maintenance time slots (PMTSs) on a general railway network. Based on network cumulative flow variables, a novel integrated mixed-integer linear programming (MILP) model is proposed to simultaneously optimize train routes, orders and passing times at each station, as well as work-time of preventive maintenance tasks (PMTSs). In order to provide an easy decomposition mechanism, the limited capacity of complex tracks is modelled as side constraints and a PMTS is modelled as a virtual train. A Lagrangian relaxation solution framework is proposed, in which the difficult track capacity constraints are relaxed, to decompose the original complex integrated train scheduling and PMTSs planning problem into a sequence of single train-based sub-problems. For each sub-problem, a standard label correcting algorithm is employed for finding the time-dependent least cost path on a time-space network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted on a small artificial network and a real-world network adapted from a Chinese railway network, to evaluate the effectiveness and computational efficiency of the integrated optimization model and the proposed Lagrangian relaxation solution framework. The benefits of simultaneously scheduling trains and planning PMTSs are demonstrated, compared with a commonly-used sequential scheduling method.     

An optimization approach to resolve activity scheduling conflicts in ADAPTS activity-based model

Activity conflict resolution as the core of scheduling process in activity-based modeling is a challenging step because the activity diary databases mostly report the outcome of the scheduling decisions and often fail to capture key factors influencing the resolution process itself. Consequently, most activity-based frameworks ignore modeling this process by using either predefined set of activity patterns or priority-based assumptions to schedule daily activities and prevent conflict occasions. ADAPTS is one of the few activity-based models that attempts to simulate the process of activity scheduling and resolve the conflicts as they occur. This paper advances the current rule-based conflict resolution model of ADAPTS by implementing an advanced and flexible non-linear optimization model. A set of linear optimization sub-models is then proposed that together perform the same task as the non-linear model, however they are much easier to implement and maintain, while fast to run and flexible to extend. The proposed approach defines an objective function, which aims to minimize the extent of changes in timing and duration of conflicting activities, while fitting them in the schedule. Comparing performance of the proposed model with TASHA scheduler and former resolution module of ADAPTS using CHASE scheduling process data reveals significant improvement in fitting the newly planned activities in the schedules with the minimal modifications in the timing and duration of activities.     

An optimal data-splitting algorithm for aircraft scheduling on a single runway to maximize throughput

In this research, we present a data-splitting algorithm to optimally solve the aircraft sequencing problem (ASP) on a single runway under both segregated and mixed-mode of operation. This problem is formulated as a 0–1 mixed-integer program (MIP), taking into account several realistic constraints, including safety separation standards, wide time-windows, and constrained position shifting, with the objective of maximizing the total throughput. Varied scenarios of large scale realistic instances of this problem, which is NP-hard in general, are computationally difficult to solve with the direct use of commercial solver as well as existing state-of-the-art dynamic programming method. The design of the algorithm is based on a recently introduced data-splitting algorithm which uses the divide-and-conquer paradigm, wherein the given set of flights is divided into several disjoint subsets, each of which is optimized using 0–1 MIP while ensuring the optimality of the entire set. Computational results show that the difficult instances can be solved in real-time and the solution is efficient in comparison to the commercial solver and dynamic programming, using both sequential, as well as parallel, implementation of this pleasingly parallel algorithm.     

An optimization model for integrated transit-parking policy planning

The optimization model proposed in this paper is aimed to assist city councils (or other transport authorities) in the planning of integrated transit-parking policies. The objective is to minimize the joint operating deficit of the transit and parking operators while ensuring given minimum levels of (motorized) mobility in a city. The key decision variables are transit fares and parking fees. The impact of price changes on transit and car modal shares are described by logit functions of the generalized travel costs. The practical utility of the model is illustrated with a case study involving a midsize city in Portugal.

     

Metaheuristics for efficient aircraft scheduling and re-routing at busy terminal control areas

Intelligent decision support systems for the real-time management of landing and take-off operations can be very effective in helping air traffic controllers to limit airport congestion at busy terminal control areas. The key optimization problem to be solved regards the assignment of airport resources to take-off and landing aircraft and the aircraft sequencing on them. The problem can be formulated as a mixed integer linear program. However, since this problem is strongly NP-hard, heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. This paper presents a number of algorithmic improvements implemented in the AGLIBRARY solver (a state-of-the-art optimization solver to deal with complex routing and scheduling problems) in order to improve the possibility of finding good quality solutions quickly. The proposed framework starts from a good initial solution for the aircraft scheduling problem with fixed routes (given the resources to be traversed by each aircraft), computed via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by re-routing some aircraft in the terminal control area. New metaheuristics, based on variable neighbourhood search, tabu search and hybrid schemes, are introduced. Computational experiments are performed on an Italian terminal control area under various types of disturbances, including multiple aircraft delays and a temporarily disrupted runway. The metaheuristics achieve solutions of remarkable quality, within a small computation time, compared with a commercial solver and with the previous versions of AGLIBRARY.     

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.     

Effective aircraft maintenance schedule adjustment following incidents

In the real world, planned aircraft maintenance schedules are often affected by incidents. Airlines may thus need to adjust their aircraft maintenance schedules following the incidents that occur during routine operations. In tradition, such aircraft maintenance schedule adjustment has been performed manually, a process which is neither effective nor efficient, especially when the problem scale is large. In this study, an aircraft maintenance schedule adjustment model is developed, with the objective of minimizing the total system cost, subject to the related operating constraints. The model is formulated as a zero-one integer program and is solved using a mathematical programing solver. The effectiveness of the model is evaluated by application to a case study using data from an aircraft maintenance center in Taiwan. The test results show the proposed model, as well as the scheduling rules abstracted from the results are useful for the decision maker to adjust good maintenance schedules.     

An analytical decision model for resource allocation in highway maintenance management

The annual expenditure for maintenance of the highway system in the United States runs into billions of dollars. The majority of maintenance decisions are undertaken based on subjective judgments and rules of thumb which, in many cases, are not very efficient. This paper is concerned with the development of an efficient technique for allocation of resources in highway maintenance management. The highway maintenance problem is formulated in terms of a 0–1 integer linear programming problem. For a realistic highway maintenance system, the number of 0–1 variables and constraints become large. A solution technique was developed so that meaningful solutions can be obtained for this large-scale problem within a reasonable computation time.     

Vulnerability evaluation of freight railway networks using a heuristic routing and scheduling optimization model

Transportation - Railway network is an integral part of the economy of many countries. Identifying critical network elements can help network executives to take appropriate preventive actions...     

An optimization model for bus fleet replacement with budgetary and environmental constraints

ABSTRACT

As maintenance and operation costs increase with usage over time, equipment is replaced when the value of new equipment is more attractive. Some methods have been developed to solve this problem. In the public transport sector, such problems are frequently analyzed by fleet managers and determined by bus age restriction regulations. We propose an Integer Programming model that integrates both budgetary and environmental constraints (CO₂ emissions) which, as far as we know, have not previously been studied in conjunction. The study aims to determine the optimal replacement plan for a fleet of diesel buses of different size, age, maintenance costs and emissions rates, with new (less polluting) diesel buses over a time horizon of 50 years. The results indicate that it is possible to reduce emissions with a low annual budget using an optimal replacement policy.     

An aircraft boarding model with the group behavior and the quantity of luggage

A reasonable boarding model can effectively improve the boarding efficiency. Therefore, developing boarding models/strategies to improve the boarding efficiency has been an interesting topic in the air transportation. In this paper, we incorporate the group behavior and the quantity of luggage into the boarding process, and then develop an extended boarding model to investigate the effects of the two factors on the delay time and boarding time. The numerical results show that the quantity of luggage may make each passenger’s boarding behavior more complex, while the group behavior can shorten some passengers’ delay time and the total boarding time. The results can help administrators organize the boarding process and enhance the boarding efficiency.     

Data-driven optimization of railway maintenance for track geometry

Railway big data technologies are transforming the existing track inspection and maintenance policy deployed for railroads in North America. This paper develops a data-driven condition-based policy for the inspection and maintenance of track geometry. Both preventive maintenance and spot corrective maintenance are taken into account in the investigation of a 33-month inspection dataset that contains a variety of geometry measurements for every foot of track. First, this study separates the data based on the time interval of the inspection run, calculates the aggregate track quality index (TQI) for each track section, and predicts the track spot geo-defect occurrence probability using random forests. Then, a Markov chain is built to model aggregated track deterioration, and the spot geo-defects are modeled by a Bernoulli process. Finally, a Markov decision process (MDP) is developed for track maintenance decision making, and it is optimized by using a value iteration algorithm. Compared with the existing maintenance policy using Markov chain Monte Carlo (MCMC) simulation, the maintenance policy developed in this paper results in an approximately 10% savings in the total maintenance costs for every 1 mile of track.     

A bi-objective maintenance scheduling for power feeding substations in electrified railways

Railway infrastructure is characterized by intensive capital investment, long lifecycle and low return. It is crucial to attain a reasonable system reliability while keeping the recurrent cost manageable throughout the asset lifecycle. Power feeding substations are the key assets on electrified rail lines. As they are subject to various adverse operating conditions, maintenance works of different levels are scheduled to ensure reliability and extend the asset life time if possible. Maintenance scheduling is often regarded as a trade-off between reliability and cost. This study incorporates considerations of different levels of maintenance activities to balance between reliability and cost. In establishing the system reliability model, the contribution of individual component reliability toward the overall system reliability is extracted from the functional relationship among the components. Solution methodologies to this scheduling problem are also proposed here. Evaluation of the scheduling model and the proposed solution is discussed and analyzed through simulation. To cater for the operating conditions in different systems, the impact of weighting factors between reliability and cost on the variations of resulting schedules will be investigated.     

An aircraft performance model implementation for the estimation of global and regional commercial aviation fuel burn and emissions

Estimates of global aviation fuel burn and emissions are currently nearly 10 years out of date. Here, the development of the Aircraft Performance Model Implementation (APMI) software which is used to update global commercial aviation fuel burn and emissions estimates is described. The results from APMI are compared with published estimates obtained using the US Federal Aviation Administration’s System for Assessing Aviation’s Global Emissions (SAGE) for the year 2006. The number of global departures modelled with the APMI software is 8% lower compared with SAGE and reflects the difference between their commercial air traffic statistics data sources. The mission fuel burn, CO₂ and H₂O estimates from APMI are approximately 20% lower than those predicted by SAGE for 2006 while the estimate for the total global aircraft SO_x emissions is approximately 40% lower. The estimates for the emissions of CO, HC and NO_x are 10%, 140% and 30% higher than those predicted by SAGE respectively. The reasons for these differences are discussed in detail.     

An analytical method for aircraft collision risk estimation

Transportation system safety is difficult to assess, particularly when examining future systems that are unlike existing systems. The absence of consensus concerning safety metrics and associated mathematical techniques inhibits implementation of improvements. One method for assessing safety was recently applied to assess new air traffic control procedures. The method contains several steps, including use of a collision risk model. The model uses probability theory to assess collision risk between aircraft due to random deviations from course. Techniques that recognize human monitoring and intervention to avoid collisions must be combined with the model to obtain absolute values of risk. Examples of model application are presented, together with a discussion of model limitations and use.     

A reference-dependent user equilibrium model for activity-travel scheduling

Existing user equilibrium models of activity-travel scheduling generally fall short in representing travelers’ decision-making processes. The majority have either implicitly or explicitly assumed that travelers follow the principle of utility maximization. This assumption ignores the fact that individuals may be loss–averse when making activity-travel decisions. Allowing for the situation that travelers possess accurate information of the urban-transportation system due to modern technologies, studies on reference-dependent decision-making under near-perfect information are receiving increasing attention. In view of traveler heterogeneity, individuals can be divided into multiple classes according to their reference points. In this paper, we propose a reference-dependent multi-class user equilibrium model for activity-travel scheduling, which can be reformulated as a variational inequality problem. Moreover, comparative analyses are conducted on the equilibrium states between utility-maximization (no reference) and reference-dependency of exogenous and endogenous references. A numerical example regarding combined departure-time and mode choice for commuting is conducted to illustrate the proposed model. The simulated results indicate that reference points and loss aversion attitudes have significant effects on the choice of departure time and mode.