Agregation dynamique des contraintes de partitionnement en generation de colonnes

The column generation method is often used to solve vehicle routing and crew scheduling problems involving set partitioning constraints. Generally the number of these constraints is huge and the columns have many non-zero elements. So, degeneracy increases and the column generation method becomes inefficient. We present in this dissertation a new paradigm to overcome this difficulty using dynamic aggregation of constraints.;We introduce in the first part of this dissertation the basic concepts of this new technique. We also present a proof of concept. Dynamic constraint aggregation uses an equivalence relation associated with tasks. This aggregation is not static. The algorithm updates it dynamically in order to reach optimality. Even though we have used simple strategies, the results we obtained for simultaneous vehicle and crew scheduling in urban mass transit problems are very interesting. Indeed, this technique significantly reduces the master problem size as well as degeneracy and solution times especially for large instances.;In the second part we study the impact of the initial partition on solution time. We would like to check if a good initial solution implies a shorter solution time. Unfortunately, the results of this study were disappointing. Actually, the aggregated master problem gives a certain priority to compatible columns. However, the subproblems do not necessarily generate the best columns according to the aggregated master problem criterion. In fact, they can produce compatible and incompatible columns since they aim at minimizing the reduced cost. The version presented in the second part corrects this behavior by introducing the concept of multiphase dynamic constraint aggregation (MPDCA). Instead of changing the cost, we add some constraints in order to favor compatible columns. In each phase, the subproblems are restricted to generate negative reduced cost columns that satisfy a condition on the number of incompatibilities. It must not exceed a prespecified limit. At the beginning of the solution process, subproblems can only generate compatible columns. The limit is then equal to zero. The multiphase concept synchronizes the aggregated master problem and the subproblems. Hence, this new technique takes advantage of degeneracy by aggregating more constraints. This advanced version significantly improves the solution time.;In many industrial applications, we also need to reduce the subproblem sizes. The third part proposes a technique to reduce both the master problem and the subproblem sizes while using the MPDCA. The results are very interesting. The reduction factor is at least equal to 2 and as high as 4 for some instances when compared to the last version. We also present for the first time results about integrality. Indeed, the algorithm is able to solve the problem with fewer branching nodes. The reduction factor equals 4 in average when compared to the standard column generation method.;Intuitively, the idea of dynamic aggregation comes from two practical observations. First, we observe that crews often use the same paths as vehicles. Consequently, crew paths and vehicle paths have many parts in common. Second, in re-optimization the optimal solution is close to the planned one. In these two cases, many consecutive tasks (flights, bus trips) on the vehicle path or the planned solution paths might remain consecutive in an optimal solution. It will be very useful to aggregate them. These paths can be considered when creating the initial partition for the dynamic constraint aggregation algorithm.;The dynamic constraint aggregation is a new paradigm in operations research. It can be applied to solve many industrial optimization problems. The tests performed on instances of the simultaneous vehicle and crew scheduling in urban mass transit problem show that this new approach allows an important gain of efficiency. It reduces the master problem time by a factor of 300 and the total time by a factor of 60 for some instances. This approach allows to efficiently solve very large problems not solved yet by the actual methods. It is a nice contribution that opens up a new research area.