A Two-Stage Scenario-Based Robust Optimization Model and a Column-Row Generation Method for Integrated Aircraft Maintenance-Routing and Crew Rostering

Motivated by a critical issue of airline planning process,this paper addresses a new two-stage scenario-based robust optimization in operational airline planning to cope with uncertainty and possible flight disruptions.Following the route network scheme and generated flight timetables,aircraft maintenance routing and crew scheduling are critical factors in airline planning and operations cost management.This study considers the simultaneous assignment of aircraft fleet and crew to the scheduled flight while satisfying a set of operational constraints,rules,and regulations.Considering multiple locations for airline maintenance and crew bases,we solve the problem of integrated Aircraft Maintenance Routing and Crew Rostering(AMRCR)to achieve the minimum airline cost.One real challenge to the efficiency of the planning results is the possible disruptions in the initial scheduled flights.Due to the fact that disruption scenarios are expressed discretely with a specified probability,and we provide adjustable decisions under disruption to deal with this disruption risk,we provide a Two-Stage Scenario-Based Robust Optimization(TSRO)model.In this model,here-and-now or first-stage variables are the initial resource assignment.Furthermore,to adapt itself to different disruption scenarios,the model considers some adjustable variables,such as the decision to cancel the flight in case of disruption,as wait-and-see or second-stage variables.Considering the complexity of integrated models,and the scenario-based decomposable structure of the TRSO model to solve it with better computational performance,we apply the column and row generation(CRG)method that iteratively considers the disruption scenarios.The numerical results confirm the applicability of the proposed TSRO model in providing the AMRCR problem with an integrated and robust solution with an acceptable level of computational tractability.To evaluate the proposed TSRO model,which solves the AMRCR problem in an integrated and robust manner,five Key Performance Indicators(KPIs)like Number of delayed/canceled flights,Average delay time,and Average profit are taken into account.As key results driven by conducting a case study,we show the proposed TSRO model has substantially improved the solutions at all indicators compared with those of the sequential/non-integrated and nominal/non-robust models.The simulated instances used to assess the performance of the proposed model and CRG method reveal that both CPLEX and the CRG method exhibit comparable and nearly optimal performance for small-scale problems.However,for large-scale instances the proposed TSRO model falls short in terms of computational efficiency.Conversely,the proposed CRG method is capable of significantly reducing computational time and the optimality gap to an acceptable level.

Using Differential Evolution Method to Solve Crew Rostering Problem

Airline crew rostering is the assignment problem of crew members to planned rotations/pairings for certain month. Airline companies have the monthly task of constructing personalized monthly schedules (roster) for crew members. This problem became more complex and difficult while the aspirations/criterias to assess the quality of roster grew and the constraints increased excessively. This paper proposed the differential evolution (DE) method to solve the airline rostering problem. Different from the common DE, this paper presented random swap as mutation operator. The DE algorithm is proven to be able to find the near optimal solution accurately for the optimization problem. Through numerical experiments with some real datasets, DE showed more competitive results than two other methods, column generation and MOSI (the one used by the Airline). DE produced good results for small and medium datasets, but it still showed reasonable results for large dataset. For large crew rostering problem, we proposed decomposition procedure to solve it in more efficient manner using DE.

Annealing Harmony Search Algorithm to Solve the Nurse Rostering Problem

A real-life problem is the rostering of nurses at hospitals.It is a famous nondeterministic,polynomial time(NP)-hard combinatorial optimization problem.Handling the real-world nurse rostering problem(NRP)constraints in distributing workload equally between available nurses is still a difficult task to achieve.The international shortage of nurses,in addition to the spread of COVID-19,has made it more difficult to provide convenient rosters for nurses.Based on the literature,heuristic-based methods are the most commonly used methods to solve the NRP due to its computational complexity,especially for large rosters.Heuristic-based algorithms in general have problems striking the balance between diversification and intensification.Therefore,this paper aims to introduce a novel metaheuristic hybridization that combines the enhanced harmony search algorithm(EHSA)with the simulated annealing(SA)algorithm called the annealing harmony search algorithm(AHSA).The AHSA is used to solve NRP from a Malaysian hospital.The AHSA performance is compared to the EHSA,climbing harmony search algorithm(CHSA),deluge harmony search algorithm(DHSA),and harmony annealing search algorithm(HAS).The results show that the AHSA performs better than the other compared algorithms for all the tested instances where the best ever results reported for the UKMMC dataset.

Quantitative Approaches on Staff Scheduling and Rostering in Hospitality Management: An Overview

Staff scheduling and rostering problems, with application in several application areas, from transportation systems to hospitals, have been widely addressed by researchers. This is not the case of hospitality services, which have been forgotten by the quantitative research literature. The purpose of this paper is to provide some insights on the application of staff scheduling and rostering problems to hospitality management operations, reviewing existing approaches developed in other similar areas, such as nurse rostering or examining adaptable problem models, such as the tour scheduling.

GASA Hybird Algorithm Applied in Airline Crew Rostering System

Crew rostering system is a daily grind in the management of both corporation and enterprise. A fair and reasonable rostering method plays a very important role in the arousing worker’s enthusiasm and improving the work efficiency. This paper presents a method of building models for automatic crew rostering mode with computer and advancing the multi-objective optimum scheme. The method to build models for crew rostering system is also discussed. The question to crew rostering system model is solved by genetic algorithms and simulated annealing algorithms. Simulation results show the correctness of algorithms. The actual data of the airways have justified its reasonability and efficiency.

Artificial intelligence and end user tools to develop a nurse duty roster scheduling system

Objectives A nurse duty roster is usually prepared monthly in a hospital ward.It is common for nurses to make duty shift requests prior to scheduling.A ward manager normally spends more than a working day to manually prepare and subsequently to optimally adjust the schedule upon staff requests and hospital policies.This study aimed to develop an automatic nurse roster scheduling system with the use of open-source operational research tools by taking into account the hospital standards and the constraints from nurses.Methods Artificial intelligence and end user tools operational research tools were used to develop the code for the nurse duty roster scheduling system.To compare with previous research on various heuristics in employee scheduling,the current system was developed on open architecture and adopted with real shift duty requirements in a hospital ward.Results The schedule can be generated within 1 min under both hard and soft constraint optimization.All hard constraints are fulfilled and most nurse soft constraints could be met.Compared with those schedules prepared manually,the computer-generated schedules were more optimally adjusted as real time interaction among nurses and management personnel.The generated schedules were flexible to cope with daily and hourly duty changes by redeploying ward staff in order to maintain safe staffing levels.Conclusions An economical but yet highly efficient and user friendly solution to nurse roster scheduling system has been developed and adopted using open-source operational research methodology.The open-source platform is found to perform satisfactorily in scheduling application.The system can be implemented to different wards in hospitals and be regularly updated with new hospital polices and nurse manpower by hospital information personnel with training in artificial intelligence.

DYNAMIC RESOURCE ALLOCATION FOR EFFICIENT PATIENT SCHEDULING： A DATA-DRIVEN APPROACH

Efficient staff rostering and patient scheduling to meet outpatient demand is a very complex and dynamic task. Due to fluctuations in demand and specialist availability, specialist allocation must be very flexible and non-myopic. Medical specialists are typically restricted in sub-specialization, serve several patient groups and are the key resource in a chain of patient visits to the clinic and operating room （OR）. To overcome a myopic view of once-off appointment scheduling, we address the patient flow through a chain of patient appointments when allocating key resources to different patient groups. We present a new, data-driven algorithmic approach to automatic allocation of specialists to roster activities and patient groups. By their very nature, simplified mathematical models cannot capture the complexity that is characteristic to the system being modeled. In our approach, the allocation of specialists to their day-to-day activities is flexible and responsive to past and present key resource availability, as well as to past resource allocation. Variability in roster activities is actively minimized, in order to enhance the supply chain flow. With discrete-event simulation of the application case using empirical data, we illustrate how our approach improves patient Service Level （SL, percentage of patients served on-time） as well as Wait Time （days）, without change in resource capacity.

Airline planning and scheduling: Models and solution methodologies

The airline industry is a representative industry with high cost and low profitability.Therefore,airlines should carefully plan their schedules to ensure that overall profit is maximized.We review the literature on airline planning and scheduling and focus on mathematical formulations and solution methodologies.Our research framework is anchored on three major problems in the airline scheduling,namely,fleet assignment,aircraft routing,and crew scheduling.General formulation,widely used solution approaches,and important extensions are presented for each problem and integrated problems.We conclude the review by identifying promising areas for further research.