Algorithmes de resolution du probleme de plus court chemin avec contraintes de ressources

The shortest path problem with resource constraints consists in finding a path from an origin point to a destination point at minimum cost while respecting constraints on the use of resources on each node. This problem appears as a subproblem in a large number of column generation algorithms. When we solve large-scale industrial problems, using a column generation algorithm, we can have hundreds of subproblems with thousands of nodes and hundreds thousands of arcs.; An efficient algorithm for solving this problem is a label setting algorithm belonging to the class of dynamical programming algorithms. This algorithm associates a label (state) to every path, prolongs every label to the successor nodes and eliminates the dominated labels. The complexity of a dynamic programming algorithm increases exponentially with the number of resources. In the large-scale industrial applications, solving those problems usually takes a long time and in many cases we are not able to solve them to optimality.; A first heuristic currently used to quickly produce feasible solutions consists in dominating only on a subset of resources. This method is static and doesn't provide a good quality solutions. Our goal in this work is to explore new methods to improve the latter heuristic and provide better solutions in the column generation algorithm context. Moreover the approaches we want to develop have to be relatively low time consuming.; In the first part of this thesis we study the method proposed by Nagih and Soumis (2006). This method consists of aggregating resources at each node by projecting them on a vector of smaller dimension and using a Lagrangian relaxation algorithm to determine the coefficients of the projection. We then evaluate the method described by Nagih and Soumis (2006) by proving that the method for selecting the multipliers of the projection at the nodes does not give results as good as the heuristic that it proposes to improve and that it is sensitive to random parameters. Moreover, we explain why the results obtained are very unstable. Then we provide some numerical results.; In the second part, we propose a flexible and dynamic algorithm for solving the shortest path problem with time windows (one resource only). This method consists of starting with an upper bound obtained by solving a shortest path problem on a restrained state space. Then we gradually increase the size of this network by applying update operations on the nodes, which decreases the bound value. In the end of this part, we present some numerical results based on some heuristics of this method.; In the third part we propose an improvement of the latter method by introducing dual variables on the nodes. This improvement insures that the upper bound will decrease at every iteration of the method. At the end of this part, we support these improvements with few numerical results.; Finally, we propose a Lagrangian method which gives a good lower bound. This method, which is inspired by the first part of this work, will lead to reducing the state space and consequently having less iterations in the method we already proposed. We also propose some extensions of the method to the general ease of the shortest path problem with resources constraints and for any type of extension functions. We prove that the size of the state space networks increase linearly along the iterations.