EURO 2025 Leeds
Abstract Submission

2344. Linear Lexicographic Optimization and Preferential Bidding System

Invited abstract in session TD-57: Air transportation II, stream Transportation.

Tuesday, 14:30-16:00
Room: Liberty 1.12

Authors (first author is the speaker)

1. Nour Elhouda Tellache
Department of Informatics, University of Fribourg
2. Frédéric Meunier
LVMT, Ecole Nationale des Ponts et Chaussées
3. Axel Parmentier
CERMICS, Ecole des Ponts ParisTech

Abstract

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 con­tinuous relaxation and returns proven optimality gaps. To design this column genera­tion, we prove that bounded linear lexicographic programs admit “primal-dual” feasible bases, and we show how to compute such bases efficiently. Another contribu­tion 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.

Keywords

Status: accepted

Back to the list of papers