Méthodes de décomposition basées sur la relaxation lagrangienne : cas du problème de transport avec coûts fixes

Abstract

Notre sujet de recherche porte sur la résolution du problème de transport avec coûts fixes (FCTP). Le problème de transport classique consiste à déterminer le schéma optimal de distribution dans un réseau. Le réseau est divisé en deux sous-ensembles de sommets : les origines caractérisées par une offre et les destinations caractérisées par une demande. À chaque arc reliant une origine et une destination, est associé un coût variable. L'objectif est de satisfaire toutes les demandes en minimisant la somme des coûts variables de transport. Dans le FCTP, il y a aussi des coûts fixes associés à tous les arcs, en supplément de tout ce qui décrit un problème de transport classique. Ainsi, à chaque arc, est associé un coût variable et un coût fixe qui est considéré si et seulement si l'arc est utilisé. L'objectif est désormais de minimiser la somme totale des coûts, variables et fixes. Le FCTP nous confronte donc à un modèle différent et plus complexe. La complexité de résolution est accrue pour les instances de grande taille.

Dans ce mémoire, nous étudions et présentons une nouvelle méthode de résolution pour les instances de grande taille du FCTP. Il s'agit d'une méthode de décomposition lagrangienne qui utilise la relaxation lagrangienne et un algorithme de sous-gradient pour trouver une borne inférieure au problème global. Nous avons intégré à la méthode une heuristique lagrangienne, incluant une procédure de ``slope scaling'' afin d'améliorer notre algorithme de sous-gradient et le résultat final de la méthode.

À l'issue de notre processus de résolution, nous trouvons, pour certaines instances de grande taille, un moyen d'améliorer la solution proposée par CPLEX pour le FCTP en donnant comme paramètre à CPLEX la solution finale de notre méthode.

Our research topic focuses on solving the fixed charge transportation problem (FCTP). The classic transportation problem is to determine the optimal distribution pattern in a network. The network is divided into two subsets of vertices : the origins characterized by a supply and the destinations characterized by a demand. Each arc connecting an origin and a destination has a variable cost associated with it. The objective is to satisfy all demands while minimizing the sum of variable transportation costs. In FCTP, there are also fixed costs associated with all arcs, in addition to all others things that describe a typical transportation problem. So, each arc is associated a variable cost and a fixed cost which is considered if and only if the arc is used. The objective is now to minimize the total sum of costs, variable and fixed. The FCTP therefore confronts us with a different and more complex model. The resolution complexity is even increased for large instances. In this thesis, we study and present a new resolution method for large FCTP instances. This is a lagrangian decomposition method which uses lagrangian relaxation and a subgradient algorithm to find a lower bound to the global problem. We have integrated into the method a lagrangian heuristic, including a “slope scaling” procedure in order to improve our sub-gradient algorithm and the final result of the method. At the end of our resolution process, we find, for some large instances, a way to improve the solution proposed by CPLEX for the FCTP by giving as parameter to CPLEX the final solution of our method.