Skip to Main content Skip to Navigation

Quelques Algorithmes pour des problèmes de plus court chemin et d'opérations aériennes

Abstract : This thesis develops algorithms for resource constrained shortest path problems, and uses them to solve the pricing subproblems of column generation approaches to some airline operations problems.Resource constrained shortest path problems are usually solved using a smart enumeration of the non-dominated paths. Recent improvements of these enumeration algorithms rely on the use of bounds on path resources to discard partial solutions. The quality of the bounds determines the performance of the algorithm. Our main contribution to the topic is to introduce a standard procedure to generate bounds on paths resources in a general setting which covers most resource constrained shortest path problems, among which stochastic versions. In that purpose, we introduce a generalization of the resource constrained shortest path problem where the resources are taken in a lattice ordered monoid. The resource of a path is the monoid sum of the resources of its arcs. The problem consists in finding a path whose resource minimizes a non-decreasing cost function of the path resource among the paths that satisfy a given constraint. Enumeration algorithms are generalized to this framework. We use lattice theory to provide polynomial procedures to find good quality bounds. The efficiency of the approach is proved through an extensive numerical study on deterministic and stochastic path problems. Interestingly, the bounding procedures can be seen as generalizations to lattice ordered monoids of some algebraic path problem algorithms which initially work with resources in a semiring.Given a set of flight legs operated by an airline, the aircraft routing and the crew pairing problem build respectively the sequences of flight legs operated by airplanes and crews at minimum cost. As some sequences of flight legs can be operated by crews only if they stay in the same aircraft, the two problems are linked. The current practice in the industry is to solve first the aircraft routing, and then the crew pairing problem, leading to a non-optimal solution. During the last decade, solution schemes for the integrated problem have been developed. We propose a solution scheme for the integrated problem based on two new ingredients: a compact integer program approach to the aircraft routing problem, and a new algorithm for the pricing subproblem of the usual column generation approach to the crew pairing problem, which is based on our resource constrained shortest path framework. We then generalize the algorithm to take into account delay propagation through probabilistic constraints. The algorithms enable to solve to near optimality Air France industrial instances
Document type :
Complete list of metadatas

Cited literature [174 references]  Display  Hide  Download
Contributor : Abes Star :  Contact
Submitted on : Tuesday, May 23, 2017 - 3:05:08 PM
Last modification on : Monday, July 10, 2017 - 10:30:51 AM
Long-term archiving on: : Friday, August 25, 2017 - 12:46:26 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01526771, version 1



Axel Parmentier. Quelques Algorithmes pour des problèmes de plus court chemin et d'opérations aériennes. Mathématiques générales [math.GM]. Université Paris-Est, 2016. Français. ⟨NNT : 2016PESC1060⟩. ⟨tel-01526771⟩



Record views


Files downloads