Methodes hybrides basees sur la generation de colonnes pour des problemes de tournees de vehicules avec fenetres de temps

In this thesis, we present an efficient heuristic method for solving a number of large-scale vehicle routing problems with time windows. The problems tackled are rich in the sense that they contain many non-conventional complex characteristics arising in real applications. We propose a hybrid between a large neighborhood search metaheuristic and a column generation exact method, hitherto the most efficient to solve constrained vehicle routing problems exactly.;Several operators are defined to select elements that will be removed from the incumbent solution in the destruction phase. At every iteration, an operator is randomly selected favoring those who managed to improve the incumbent solution in the past iterations. Afterwards, column generation is used to explore the neighborhood defined by the operator (reconstruction phase). Many aspects of the column generation approach are managed heuristically in order to obtain good solutions in reasonable time at the expense of ensuring optimality. The subproblems are solved by means of a tabu search algorithm and the column generation is stopped if the value of the solution of the linear relaxation does not improve enough over the last iterations. An aggressive branching scheme is used to derive integer solutions. Branching is done on the variable with the highest fractional value, which is fixed at 1 without the possibility to backtrack.;The proposed method is first developed in Chapter 4 for the vehicle routing problem with time windows. The objective is to minimize first the number of vehicles, and then the total distance traveled. That is why the method is adapted in two phases, one for each objective. At time of experimentation, the method managed to improve the best known solutions of 106 over 356 instances of size going from 100 to 1000 customers.;In order to put the method to the test on a more complex problem with real applications, European rules on driver working hours are added to the problem in Chapter 5. Indeed, as of April 2007, an update of the rules governing the driver working hours is in place in the European Union. Even though the rules have a concrete and very practical aspect, very few scientific papers were published on the subject from an optimization point of view. To check the feasibility of a route, a label-setting algorithm is proposed. The driver rules are modeled using complex resource extension functions that can generate multiple labels from one source label. Every time an insertion is evaluated by the tabu search solving the subproblem, the resulting route is checked for feasibility. We also demonstrate how to consider multiple insertions at once by bounding the resource values at each node of the current route of the tabu search. The computed bounds are also used to limit the domain of the label-setting algorithm. The method proposed to check the feasibility of the routes is generic for any algorithm using insertion movements. Compared to two other methods on academic instances, ours is definitely superior.;Finally, the method is generalized in Chapter 6 to a real problem arising in the heating oil distribution industry. Much more complex, the column generation formulation of the problem requires multiple subproblems. In addition, there is a heterogeneous fleet, start and end time of working shifts, multiple depots, intra-route replenishments and optional customers. It is however possible to had a move to the tabu search algorithm solving the subproblems, in order to switch between subproblems without slowing down the method too much. A concurrent tabu search is also presented to solve the whole problem. This method is also inserted into the large neighborhood search algorithm to explore the neighborhoods instead of the heuristic column generation. Computational results show that the large neighborhood search can be a good guiding mechanism for a metaheuristic. However the column generation reconstruction outperforms its tabu search counterpart over the solved instances. (Abstract shortened by UMI.)...