Aircraft and crew scheduling for fractional ownership programs

Fractional aircraft ownership programs, where individuals or corporations own a fraction of an aircraft, have revolutionized the corporate aviation industry. Fractional management companies (FMC) manage all aspects of aircraft operations enabling the owners to enjoy the benefits of private aviation without the associated responsibilities. We describe here the development of a scheduling decision support tool for a leading FMC. We present mathematical models, exact and heuristic solution methods. Our computational results using real and randomly generated data indicate that these models are quite effective in finding optimal or near-optimal solutions. The first phase of the implementation of one of these models at the FMC led to a significant improvement in effective utilization of the aircraft, reduction of costs due to reduced empty moves, and hence increased profits.     

The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies

In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.     

Airline crew scheduling from planning to operations

Crew scheduling problems at the planning level are typically solved in two steps: first, creating working patterns, and then assigning these to individual crew. The first step is solved with a set covering model, and the second with a set-partitioning model. At the operational level, the (re) planning period is considerably smaller than during the strategic planning phase. We integrate both models to solve time critical crew recovery problems arising on the day of operations. We describe how pairing construction and pairing assignment are done in a single step, and provide solution techniques based on simple tree search and more sophisticated column generation and shortest-path algorithms.     

Column generation in the integral simplex method

The integral simplex method for set partitioning problems allows only pivots-on-one to be made, which results in a primal all-integer method. In this technical note we outline how to tailor the column generation principle to this method. Because of the restriction to pivots-on-one, only local optimality can be guaranteed, and to ensure global optimality we consider the use of implicit enumeration.     

All-integer column generation for set partitioning: Basic principles and extensions

Column generation, combined with an appropriate integer programming technique, has shown to be a powerful tool for solving huge integer programmes arising in various applications. In these column generation approaches, the master problem is often of a set partitioning type.     

Stabilized dynamic constraint aggregation for solving set partitioning problems

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solving linear programs. The first uses a projection to reduce the primal space whereas the second acts in the dual space. In this paper, we develop a new method, called stabilized dynamic constraint aggregation (SDCA), that combines DCA and DVS for solving set partitioning problems. It allows to fight degeneracy from both primal and dual perspectives simultaneously. To assess the effectiveness of SDCA, we report computational results obtained for highly degenerate multi-depot vehicle scheduling problem instances solved by column generation. These results indicate that SDCA can reduce the average computational time of the master problem by a factor of up to 7 with respect to the best of the two combined methods. Furthermore, they show that its performance is robust with regard to increasing levels of degeneracy in test problems.     

Network design: taxi planning

The effect of managing aircraft movements on the airport’s ground is an important tool that can alleviate the delays of flights, specially in peak hours or congested situations. Although some strategic design decisions regarding aeronautical and safety aspects have a main impact on the airport’s topology, there exists a number of other additional factors that must be evaluated according to the on ground operations, i.e. previous to the taking-off or after landing. Among these factors one can consider capacities at waiting points and directions of some corridors. These factors are related to the demand situation of a given period and influence the aircraft’s routing on the ground or short term Taxi Planning problem (or TP-S). While the TP-S problem studies the aircraft routing and scheduling on the airport’s ground under a dynamic point of view, this paper presents a Taxi Planning network design model (or TPND), attending to these additional factors of the airport’s topology and the conflicting movements of the aircraft on them with the same modelling approach used in the TP-S problem. The TPND model is formulated as a binary multicommodity network flow problem with additional side constraints under a multiobjective approach. The side constraints included are the classical limitations due to capacity and also as a distinctive approach, constraints that restrict the interference of aircraft in order to decrease the intervention of human controllers during the operations or increase their safety margins. The multiobjective approach adopted for the TPND model balances conflicting objectives: airport’s throughput, travel times, safety of operations and costs. In the paper computational results are included on two test airports solving the TPND model by “Branch and Bound” showing the effect of the conflicting objectives in the design decisions. Research supported under Research Project TRA-2005-09068-C03-01/MODAL from the “Ministerio de Educación y Ciencia”.     

Integrated airline crew scheduling: A bi-dynamic constraint aggregation method using neighborhoods

The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions.     

Solving a tactical operating room planning problem by a column-generation-based heuristic procedure with four criteria

In some hospitals, an “open scheduling” strategy is applied to solve the operating room planning problem; i.e., surgeons can choose any workday for his surgical cases, and the staffing of anesthetists and nurses is adjusted to maximize the efficiency of operating room utilization. In this paper, we aim at obtaining an efficient operating program for an operating theatre with several multifunctional operating rooms by using this “open scheduling” strategy. First, a mathematical model is constructed to assign surgical cases to operating rooms within one week. This model complies with the availability of operating rooms and surgeons, and its objective is not only to maximize utilization of operating rooms, but to minimize their overtime cost. Then a column-generation-based heuristic (CGBH) procedure is proposed, where four different criteria are compared with each other so as to find a solution with the best performance. In addition, the best approximate solution, obtained by this CGBH procedure after running all the criteria proposed, is compared with the lower bound obtained by an explicit column generation (CG) procedure, LP, to evaluate the distance between the approximate solution obtained and the optimum one. Although no criterion, according to the experimental results, is found superior to all other three in both robustness and quality of the solution obtained, it is found that the best solution obtained among those four criteria is often very close to LP, which means that the proposed algorithm can obtain a near optimal solution. In one word, the CGBH procedure proposed in this paper can obtain an efficient assignment of the surgical cases if the other resources (anesthesia and nursing staff, equipment, beds in the recovery room and etc.) are well organized.     

Airport management: taxi planning

The Taxi Planning studies the aircraft routing and scheduling on the airport ground. This is a dynamic problem, which must be updated almost every time that a new aircraft enters or exits the system. Taxi Planning has been modelled using a linear multicommodity flow network model with side constraints and binary variables. The flow capacity constraints are used to represent the conflicts and competence between aircrafts using a given airport capacity. The “Branch and Bound” and “Fix and Relax” methodologies have been used. The computational tests have been run at the Madrid-Barajas airport, using actual data from the airport traffic.     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

This text summarizes the PhD thesis defended by the author in January 2006 under the supervision of Professor Erik Demeulemeester at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/jeroen.belien). In this research we propose a number of exact and heuristic algorithms for various scheduling problems encountered in hospitals. The emphasis lies on the design of new methodologies as well as on the applicability of the algorithms in real-life environments. The main contributions include a new decomposition approach for a particular class of staff scheduling problems, an extensive study of master surgery scheduling algorithms that aim at leveling the resultant bed occupancy and an innovative method for integrating nurse and surgery scheduling.      

On the choice of explicit stabilizing terms in column generation

Column generation algorithms are instrumental in many areas of applied optimization, where linear programs with an enormous number of columns need to be solved. Although successfully employed in many applications, these approaches suffer from well-known instability issues that somewhat limit their efficiency. Building on the theory developed for nondifferentiable optimization algorithms, a large class of stabilized column generation algorithms can be defined which avoid the instability issues by using an explicit stabilizing term in the dual; this amounts at considering a (generalized) augmented Lagrangian of the primal master problem. Since the theory allows for a great degree of flexibility in the choice and in the management of the stabilizing term, one can use piecewise-linear or quadratic functions that can be efficiently dealt with using off-the-shelf solvers. The practical effectiveness of this approach is demonstrated by extensive computational experiments on large-scale Vehicle and Crew Scheduling problems. Also, the results of a detailed computational study on the impact of the different choices in the stabilization term (shape of the function, parameters), and their relationships with the quality of the initial dual estimates, on the overall effectiveness of the approach are reported, providing practical guidelines for selecting the most appropriate variant in different situations.