Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

Planification en contexte mégaévénementiel et reconversion urbaine : le cas du Green Point Urban Park à Cape Town en Afrique du Sud


Depuis les années 2000, nous observons de plus en plus de pays en développement (PED) hôtes de mégaévénements. En accueillant un mégaévénement en leur sol, les PED espèrent améliorer leur cadre urbain et attirer des investissements étrangers. Ceci étant dit, les retards en termes d’infrastructures et d’équipements que connaissent ces pays et les stricts cadres normatifs imposés par des organismes internationaux comme la FIFA, nous amènent à questionner la possibilité d’intégrer les aménagements mégaévénementiels, à leur contexte local. En ce sens, le processus de planification, dans lequel les cadres normatifs externes et locaux sont négociés, peut être vu comme un moment charnière ayant une incidence sur le potentiel de reconversion. Dans le cadre de ce mémoire, nous avons entamé une réflexion à ce sujet en examinant le processus de planification d’un aménagement mégaévénementiel, le Green Point Urban Park (GPUP) à Cape Town, et son incidence sur son potentiel de reconversion. Plus précisément, nous allons, en premier lieu, décrire le processus de planification du site, nous allons par la suite évaluer son potentiel de reconversion, puis nous allons faire ressortir des liens entre le processus de planification et le potentiel de reconversion des aménagements mégaévénementiels. En somme, notre travail met en évidence une relation entre, d’une part, la prépondérance du cadre normatif imposé par l’organisme international et la dynamique du système d’acteurs au moment de la planification du GPUP et, d’autre part, la difficile reconversion de ce dernier après la Coupe du monde de 2010.

L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

The green economy challenge to IPE

Note d'analyse