Reduction des sauts d'integrite dans les problemes d'affectation de locomotives pour un transporteur de marchandises (French text)

This thesis presents a number of techniques that improve the computation times and the quality of integer solutions obtained for assignment problems that can be represented as multicommodity network flow problems with linking constraints. Among these problems, we focus more specifically on a generalized set covering problem, i.e. the locomotive assignment problem for freight trains. An industrial problem of this kind is of such magnitude that listing every solution is impossible and we must limit ourselves to investigate a fraction of a search tree, our tools are thus developed within the framework of an incomplete systematic search using a heuristic branch-and-price implicit enumeration. We apply three different scenarios to our typical railway problem and validate the developed techniques either to perfect the tactics of branching at the nodes of the search tree or to accelerate the exploration of the same search tree.; Chapter 1 provides a definition of the locomotive assignment problem in freight trains, the problem we use as reference throughout this work. First, the multicommodity network flow problem with additional constraints is formulated, tailored to the locomotive assignment problem. The next section explains the angular block structure specific to this type of formulation: a master problem and several subproblems (one per commodity). This structure allows for solving a linear relaxation of the problem by a column generation process. The last section shows how these linear relaxations can be embedded in an implicit enumeration in order to explore a fraction of the solution tree.; Chapter 2 lists the main publications in this field. A few reminders of fundamental solution approaches to obtain integer solutions precede the sections presenting the literature on branching tactics and exploration strategies.; Chapter 3 studies branching tactics in the context of shortest path subproblems with forbidden paths. Indeed in the case at hand, the subproblems obtained for every commodity by the Dantzig-Wolfe decomposition are shortest path problems.; Chapter 4 presents another investigation strategy called exploration by best expectations.; Chapter 5 considers the cost structure of the generalized set covering problem to improve the branching.; Chapter 6 describes the steps for building a predictor-corrector branching scheme search for the solution tree. (Abstract shortened by UMI.)...