Show item record

dc.contributor.advisorGendron, Bernard
dc.contributor.authorEl Filali, Souhaïla
dc.date.accessioned2014-09-30T18:44:35Z
dc.date.availableNO_RESTRICTIONfr
dc.date.available2014-09-30T18:44:35Z
dc.date.issued2014-09-29
dc.date.submitted2014-05
dc.identifier.urihttp://hdl.handle.net/1866/11037
dc.subjectProblème de conception de réseauxfr
dc.subjectCoûts d’ajout de capacitéfr
dc.subjectReformulation 0-1fr
dc.subjectGénération de colonnesfr
dc.subjectMéthodes de coupesfr
dc.subjectBranch-and-boundfr
dc.subjectMulticommodity capacitated network design problemfr
dc.subjectCapacity expansion costsfr
dc.subject0-1 reformulationfr
dc.subjectColumn generationfr
dc.subjectCutting-plane methodsfr
dc.subject.otherApplied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796)fr
dc.titleMéthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacitéfr
dc.typeThèse ou mémoire / Thesis or Dissertation
etd.degree.disciplineInformatiquefr
etd.degree.grantorUniversité de Montréalfr
etd.degree.levelMaîtrise / Master'sfr
etd.degree.nameM. Sc.fr
dcterms.abstractLes problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.fr
dcterms.abstractNetwork design problems received a particular interest and have been widely studied because of their many applications in different areas, such as logistics and telecommunications. We focus in this work on the multicommodity capacitated network design problem with capacity expansion costs. It consists in opening a set of facilities on a network in order to meet the demand of some commodities, while respecting the capacity constraints. Each arc can admit several facilities. The objective is to minimize the commodities transportation costs, and the fixed costs of opening or increasing the capacity of the facilities. The method we are using to solve this problem is based on techniques used in integer programming, including column generation and cutting-plane methods. These methods are introduced into a general branch-and-bound algorithm, based on linear relaxation. We test our method on four groups of instances of different sizes, and we compare it with CPLEX, which is one of the best solvers available for optimization problems. We compare it also with an existing method in the literature, combining exact and heuristic methods. Numerical results show that our method was able to outperform both methods, especially when tested on large scale instances.fr
dcterms.languagefrafr


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show item record