Frédéric Meunier

Crew scheduling and crew rostering are two key stages in the design of yearly plannings for train drivers. These stages are usually handled sequentially, which may lead to suboptimal solutions. In this work, we address the two stages in an integrated manner for an application to rail freight at the SNCF, the main French railway operator, and propose a method based on column generation that solves both stages simultaneously, while taking into account all the eighteen working rules. We demonstrate the practical relevance of our approach on real freight instances from the SNCF, by displaying substantial cost reductions.Integrating the two stages also makes it possible to better account for uncertainty. We introduce a simple metric to measure the ``fragility'' of rosters with respect to train delays, and we incorporate a stochastic constraint based on this metric into the integrated formulation. Our approach successfully handles this constraint, and experiments on real instances show that the resilience to delays can be improved while maintaining costs at least as good as those obtained with the standard sequential approach in the deterministic setting.

Dividing a multilayered cake under nonoverlapping constraints captures several scenarios (e.g., allocating multiple facilities over time where each agent can utilize at most one facility simultaneously). We establish the existence of an envy-free multidivision that is nonoverlapping and contiguous within each layer when the number of agents is a prime power, solving partially an open question by Hosseini et al. [Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Proc. 29th Internat. Joint Conf. Artificial Intelligence (IJCAI), 182–188; Hosseini H, Igarashi A, Searns A (2020) Fair division of time: Multi-layered cake cutting. Preprint, submitted April 28, http://arxiv.org/abs/2004.13397 ]. Our approach follows an idea proposed by Jojić et al. [Jojić D, Panina G, Živaljević R (2021) Splitting necklaces, with constraints. SIAM J. Discrete Math. 35(2):1268–1286] for envy-free divisions, relying on a general fixed-point theorem. We further design a fully polynomial-time approximation scheme for the two-layer, three-agent case, with monotone preferences. All results are actually established for divisions among groups of almost the same size. In the one-layer, three-group case, our algorithm is able to deal with any predetermined sizes, still with monotone preferences. For three groups, this provides an algorithmic version of a recent theorem by Segal-Halevi and Suksompong [Segal-Halevi E, Suksompong W (2021) How to cut a cake fairly: A generalization to groups. Amer. Math. Monthly 128(1):79–83]. Funding: This work was partially supported by the Japan Science and Technology Agency [Grant JPMJPR20C], Fusion Oriented REsearch for disruptive Science and Technology [Grant JPMJFR226O], and Exploratory Research for Advanced Technology [Grant JPMJER2301].

In a digraph, a kernel is a subset of vertices that is both independent and absorbing. Kernels have important applications in combinatorics and outside. Kernels do not always exist and finding sufficient conditions ensuring their existence is a key theoretical challenge. In this work, we revisit and generalize a few classical results of this sort, especially the Sands--Sauer--Woodrow theorem and the Galeana-Sánchez--Neumann-Lara theorem.

Some airlines use the preferential bidding system to construct the schedules of their pilots. In this system, the pilots bid on the different activities and the schedules that lexicographically maximize the scores of the pilots according to their seniority are selected. A sequential approach to solve this maximization problem is natural: The problem is first solved with the bids of the most senior pilot, and then it is solved with those of the second most senior without decreasing the score of the most senior, and so on. The literature admits that the structure of the problem somehow imposes such an approach. The problem can be modeled as an integer linear lexicographic program. We propose a new efficient method, which relies on column generation for solving its continuous relaxation and returns proven optimality gaps. To design this column generation, we prove that bounded linear lexicographic programs admit “primal-dual” feasible bases, and we show how to compute such bases efficiently. Another contribution on which our method relies is the extension of standard tools for resource-constrained longest path problems to their lexicographic versions. This is useful in our context because the generation of new columns is modeled as a lexicographic resource-constrained longest path problem. Numerical experiments show that this new method is already able to solve to proven optimality industrial instances provided by Air France, with up to 150 pilots. By adding a last ingredient in the resolution of the longest path problems, which exploits the specificity of the preferential bidding system, the method achieves for these instances computational times that are compatible with operational constraints. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0372 .