Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

Abstract

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Many problems in transportation, telecommunications and logistics can be formulated as network design problems. The general problem consists in identifying a subgraph of the network on which facilities are to be built, and the quantities of products to transport on it, subject to a set of constraints, with the objective of minimizing total costs. In this dissertation, the aim is to adress the capacitated network design problem with fixed costs and a single commodity, that we transform into a muticommodity network design problem in order to improve the value of the lower bound of the relaxed model. The proposed method is a branch-and-price-and-cut algorithm with stopping criterion that combines column generation, cutting-plane and branch-and-bound methods. Numerical tests are performed using two groups of instances with different sizes, large and very large. The results are compared to those given by CPLEX, one of the most efficient software tools for integer programming, and to a branch-and-cut algorithm. It is shown that the method we adopted is competitive in particular for very large instances.