Logiciel de generation de colonnes (French and English text)

This dissertation is about the efficient solution of very large scale vehicle routing and crew scheduling problems using column generation. These problems consist in assigning a fixed set of tasks to crew members or vehicles at minimal cost. In 1998, Desaulniers, Desrosiers, Ioachim, Solomon, Soumis and the author proposed a generic nonlinear multicommodity network flow model, called the unified model, for analyzing a large class of deterministic vehicle routing and crew scheduling problems.; The dissertation is divided into a theoretical part and an experimental part. First, the theoretical objective consists in analyzing equivalence conditions between a block angular formulation of a nonlinear problem and a column generation formulation associated with its oracle. The experimental objective consists in developing a software library for solving very large scale vehicle routing and crew scheduling problems from a large subset of the unified model.; On the theoretical side, one contribution resides in the clarification of the relations between compact and column generation formulations of a mixed integer problem. We show how to retrieve, under relatively weak conditions, a compact formulation equivalent to the initial column generation one.; On the experimental side, this dissertation contributes to the structuring of research and development activities around the unified model by releasing the two most recent versions of the GENCOL software library.; Moreover, the dissertation presents two novel algorithmic approaches for coping with a very large number of global linear constraints in column generation problems. We propose a stabilization process that combines a perturbation method and an exact penalty method.; Finally, we develop two algorithmic strategies for reducing the number of set partitioning constraints that are active at the same time in the column generation formulation of a problem formulated using the unified model. First, we present several static aggregation algorithms for identifying and eliminating redundant set partitioning constraints in a preprocessing step. Next, we develop a dynamic aggregation algorithm to control the number of set partitioning constraints active at each iteration of the column generation process. (Abstract shortened by UMI.)...