Almost 20 years after the pioneer publications of column generation applied to airline crew pairing, the limitations and challenges to airline planning problems resolution are a reality. Some of these issues will be presented, with efficient ways to overcome them, when they exist. Degeneracy or non additive cost functions are good examples, among others. The presentation is based on various major and mid-size carriers fleet and crew planning problems.

We propose a generalization of the proximal point algorithm. We use penalty functions having full-dimensional trust regions. Finite convergence is established under the assumptions that all subproblems are solved to optimality. We use piecewise linear penalty functions for column generation stabilization. The method is applied to two well known problems: the Multiple-Depot Vehicle Scheduling Problem (MDVSP) and the Cutting Stock Problem (CSP).

Pour résoudre le problème de découpe à capacités variables, nous avons recours au modèle de Gilmore-Gomory renforcé à l’aide de contraintes valides. Nous utilisons un algorithme exact de séparation et génération de colonnes à convergence finie. Des colonnes sont introduites pour accélérer la convergence du processus de génération de colonnes.

In this talk, we will discuss the Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW), a variant of the well-known Vehicle Routing Problem with Time Windows in which a customer's demand can be split among several vehicles. We will first examine some properties of split delivery solutions and restate a direct mixed integer programming formulation for the problem. The main part of the presentation will be devoted to the description of a new column generation approach for solving the SDVRPTW without imposing any restrictions on the split delivery options. Computational results on problems with up to 50 customers will be reported and analyzed.