Show item record

dc.contributor.advisorGendron, Bernard
dc.contributor.authorLarose, Mathieu
dc.date.accessioned2012-09-07T18:30:27Z
dc.date.availableNO_RESTRICTIONen
dc.date.available2012-09-07T18:30:27Z
dc.date.issued2012-07-05
dc.date.submitted2011-12
dc.identifier.urihttp://hdl.handle.net/1866/8476
dc.subjectProblème de conception de réseauen
dc.subjectGénération de colonnesen
dc.subjectGénération de coupesen
dc.subjectMulticommodity network design problemen
dc.subjectBranch-and-bounden
dc.subjectColumn generationen
dc.subjectCutting-plane methoden
dc.subject.otherApplied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)en
dc.titleDé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ésen
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiqueen
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sen
etd.degree.nameM. Sc.en
dcterms.abstractDe 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.en
dcterms.abstractMany problems in transportation and logistics can be formulated as network design models. They usually require to transport commodities, passengers or data in a network to satisfy a certain demand while minimizing the costs. In this work, we focus on the multicommodity capacited fixed-charge network design problem which consists of opening a subset of the links in the network to satisfy the demand. Each link has a capacity and a fixed cost that is paid if it is opened. The objective is to minimize the fixed costs of the opened links and the transportation costs of the commodities. We present an exact method to solve this problem based on mixed integer programming techniques. Our method is a specialization of the branch-and-bound algorithm, called branch-and-price-and-cut, in which we use column generation and cutting-plane method to solve large-scale instances. We compare our method with CPLEX, currently one of the best solver. Numerical results show that our method is competitive on medium-scale instances and better on large-scale instances.en
dcterms.languagefraen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record


DSpace software [version 5.8 XMLUI], copyright © 2002-2015  DuraSpace