Program > By speacker > Diarrassouba Ibrahima

Dans ce papier, nous nous intéressons au problème de séparation des contraintes dites de Coupe-Capacité Arrondies qui sont valides pour le polytope du CVRP (Capacitated Vehicle Routing Problem). Ces contraintes, ainsi que leur problème de séparation, présentent un intérêt particulier dans la résolution du CVRP, surtout dans le cadre d'algorithmes de Coupes et Branchements. A notre connaissance, la complexité du problème de séparation associé à ces contraintes n'est pas connu dans la litérature, et plusieurs auteurs ont proposé des algorithmes heuristiques pour les séparer. Dans ce travail, nous étudions une généralisation des Contraintes de Coupe-Capacité Arrondies et montrons que ces contraintes peuvent être séparées en temps polynomial. Nous donnons aussi un algorithme de séparation en (n-1)E(n,m+n) où E(n,m+n) peut être borné par O(n4) (ici n et m désigne respectivement le nombre de sommets et d'arêtes du graphe support du CVRP). Comme conséquence, nous répondons à la question de la complexité du problème de séparation des Contraintes de Coupe-Capacité Arrondies.

Puis, nous nous intéressons aux applications du résultat précédent au problème de séparation des contraintes dites de Partitions Routées. Ces contraintes sont valides pour le polytope du problème de Conception de Réseau Fiables avec Chemin de Longueur Bornée. Nous montrons que, dans un cas particulier où elles définissent des facettes, les Contraintes de Partitions Routées peuvent être séparées en temps polynomial. Enfin, nous discutons d'autres applications des Contraintes de Coupe-Capacité Arrondies.