Resolution du probleme de decoupe unidimensionnelle par une methode de generation de colonnes (French text)

The aim of this thesis is solving the cutting stock problem (CSP) as a constrained vehicle routing problem. The problem is formulated as multi-commodity flow problem where the cutting patterns are represented on an acyclic network.; We apply the Dantzig-Wolfe decomposition technique on this formulation to obtain a master problem formulated in terms of pattern variables and a shortest path problem with capacity constraint as a subproblem. Branching is performed on flow variables.; We first test our approach on the binary cutting stock problem. Branch-and-bound decisions are dealt with by eliminating arcs from the subproblem network. Then, we propose some acceleration techniques in order to improve the performance of the linear relaxation optimization and the branch-and-bound process. We show then that if the constraints corresponding to items of equal length are aggregated, the solution process of the linear relaxation is much faster.; For the general case, considering branching decisions within the subproblem would destroy its structure. Therefore, we had to add new constraints to the master problem so that the subproblem structure is preserved. Preliminary results for this approach are presented and some enhancement features are proposed.; Although the cutting stock problem is easy to solve and its integrality gap is very small, it presents a lot of symmetry which affects the stability of the solution process. Several conclusions on routing problems raised from this work. Good lower bounds and heuristic initialization may be very beneficial to the problem optimization. More efficient branching can be obtained by taking in account item attributes or by taking several decisions simultaneously. Also, the dual problem degeneracy may affect the stability of a colonm generation solving process. Hence, stabilization techniques would be very beneficial for hard problems solution.