Bus scheduling problem is one of the most important scheduling problems in public transit since it guarantees minimum cost running for the transportation companies. A bus schedule defines the number of trips made by a bus in a workday, from the time it leaves the depot until it returns to the depot. Our study focuses on a large-scale multiple-depot bus scheduling problem in the public bus transportation industry with homogeneous fleets of vehicles. Using a timetable of trips, this research targets finding feasible bus schedules that cover each trip exactly once. With this approach, we use a set partitioning model with side constraints, and a connection-based network. Our solution approach is based on column generation (CG) embedded in a branch and bound method. As part of CG, we use a shortest path subproblem with resource constraints, which is then solved with a labeling algorithm considering dominance rules. To speed up the solution process, we use some heuristics branching including variable fixing and inter-task fixing. Despite the complexity of our model compared to most of those in literature reviews, computational experiments show that our approach is fast.

The Crew Pairing Problem (CPP) seeks to find a set of feasible crew pairings (sequences of flight connections, and rests, forming one or several days of work for a crew) at minimum cost that cover all flights in a given period. However, some airlines are willing to sacrifice a portion of their savings to achieve regularity. This is because regular schedules are much easier to implement and manage, including booking the same hotels, rooms, and limousines for the crew. It also enhances employee satisfaction. Regularity is achieved by having pairing patterns that are repeated several times in the CPP solution.
The CPP is typically solved using a branch-and-price algorithm. However, existing mathematical models for the CPP with regularity are incompatible with branch-and-price. In this study, we propose a two-step solution method to solve the CPP with regularity. The first step consists of solving an auxiliary optimization problem called aggregated daily CPP (ADCPP). ADCPP identifies a set of highly regular, yet efficient pairings. Solving the ADCPP requires a new branch-and-bound algorithm. In the second step, the pairings created by ADCPP are given as input to a traditional branch-and-price solver. Bonuses are given to those pairings to incentivize selecting them in the final CPP solution. Preliminary results on large-scale commercial instances of the CPP are presented.

The crew rostering problem (CRP) is a complex crew scheduling task where pairings, or sequences of flights starting and ending at the same airport, are assigned to pilots. These assignments form a collection of schedules (called roster) spanning one month. The CRP typically seeks to optimize some criterion such as cost or crew satisfaction.

In this presentation, we describe a new line of research concerning the CRP. We address the possibility of generating very fast solutions to the problem with the help of machine learning (ML) techniques. Using a sequential assignment procedure whose arc weights are computed with ML weights, we generate solutions to infer about the quality of a CRP instance's configuration. We also use a partial re-optimization technique with windowing to improve the solutions. The rosters obtained in this way are high-quality and produced in 5\% to 20\% of the time normally taken by a state-of-the-art solver. In each case, the ML weights are learned with reinforcement learning and an evolutionary algorithm (CMA-ES).

We conclude with a discussion of the methodological framework introduced and outline future efforts, such as extensions of our method to other crew scheduling tasks, and its relationship with different ML models, such as GNNs.

Airline companies are constantly looking at optimizing their resources by improving their decision-making capabilities. In this context, crew scheduling significantly influences cost-saving decision-making processes. It is advantageous for airlines when their cabin crews operate in teams throughout entire pairings, which are sequences of flights, connections, and layovers, covering one or more workdays. The benefits of this approach are numerous: better cohesion between cabin crews, which increases effectiveness and boosts morale; enhanced logistical operations involved; reduced spread of delays throughout the pairings; and improved robustness of the schedules. However, maintaining the same team for consecutive flights isn't always feasible due to the different crew requirements of the various types of aircraft operated by companies in a single pairing. In these instances, using a core team to fulfill the majority of roles, supplemented by additional crew members for specific roles, can be a good strategy to use. 

In our presentation, we will introduce the Crew Split Problem (CSP), aiming at determining the optimal composition of a core team and the complementary crew members following it for each flight. The CSP is a multi-objective optimization problem that, among others, seeks to minimize the cost associated with repositioning crew members (or deadhead). Our model also considers the possibility for higher-ranked crew members to assume roles below their usual rank; this concept is called downranking. The first promising results are shown in real-world instances.