Šio darbo tikslas – sukurti trimačių dėžių su papildomu orientacijos erdvėje apribojimu pakavimo optimizavimo algoritmą, o realizavus jį programinėmis priemonėmis – ištirti jo efektyvumą su atsitiktinai sugeneruotų kraunamų dėžių rinkiniais ir prie skirtingų algoritmo veikimo parametrų. Taip pat sukurti ir pakavimo optimizavimo sprendinio vizualizavimo trimatėje erdvėje programinę įrangą. / Presented work covers one of the most complex areas of combinatorial optimization – three dimensional bin packing problem. Solution methods of this problem are applied in the real world from logistics, packing optimization to VLSI circuit and automobile engineering. Several heuristic packing algorithms suggested by other authors are analyzed. Approach based on tree-search and wall building strategy is chosen to create a 3D packing optimization algorithm. A bin orientation in space restriction is added to classical 3D bin packing problem to make it more complex and more suited for real world applications. A prototype of created algorithm is created and tested with randomly generated data collections. Each data sample is processed with and without bin orientation in space restriction. Influence of restriction and maximal tree width on packing efficiency and computational time is statistically analyzed. Visualization tool based on Microsoft Direct X technology is created to view results of packing optimization.

Le problème de placement sur deux dimensions consiste à décider s’il existe un rangement d’objets rectangulaires dans une boîte donnée. C’est un problème combinatoire difficile (à la complexité du respect des capacités s’ajoute celle du positionnement des objets).Dans cette thèse, nous considérons les variantes sans rotation des objets et avec ou sansoptimisation de la valeur des objects placés.Nous menons une étude exploratoire des méthodologies qui peuvent être développéesà l’interface de la programmation mathématique, de l’optimisation combinatoire et de lathéorie des graphes. Notre objectif est aussi de développer des approches non basées surune discrétisation de la boîte, les plus performantes à l’heure actuelle.Dans ce mémoire, nous effectuons d’abord une étude théorique des qualités de bornesqui peuvent être obtenues avec les différentes formulations classiques. Au cours de cetteétude, nous renforçons certaines de ces formulations et en proposons de nouvelles formulations. Une étude qualitative des bornes issues de la relaxation linéaire des formulationstestés sur des jeux d’instances classiques de la littérature confirme l’étude théorique. Cetteétude permet de se rendre compte des facteurs déterminant la qualité des bornes et desenjeux à relever par la programmation mathématique.Par la suite, nous avons développé et testé deux approches de résolution innovantes.L’une est basée sur la décomposition de Dantzig-Wolfe associée à un branchement surles contraintes disjonctives de non recouvrement des objets. Cette approche a permis uneamélioration des résultats obtenus par la programmation mathématique.L’autre approche constitue en une approche combinatoire basée sur diverses caractérisations des graphes d’intervalles (modélisant le chevauchement des objets selon leurprojection sur chaque axe). Un premier algorithme est basé sur l’énumération de matricesde uns-consécutifs. Un autre utilise des arbres étiquetés pour éliminer plus efficacement lescas de symétries entre placements. Ces approches ont l’avantage de ne pas dépendre d’unediscrétisation du conteneur / The two dimensional orthogonal packing problem consists in deciding whether thereexists a packing of rectangular items in a given bin. This is a hard combinatorial problem(in addition to capacity constraints, one has to face the complexity of item positionning).In this thesis, we consider the case without item rotation and with or without packingvalue optimization.We explore methodologies at the interface of mathematical programming, combinatorial optimization and graph theory. Our aim is also to develop approaches not based on abin discretization (i.e. an alternative to such methods that are currently the most effective).In this work, we perform a theorical study of the quality of bounds of differents classicalformulations. We tighten some formulations and we propose new formulations. We perform a numerical study to test bound quality on classical instances. This study permits toidentify the determinant factor in the quality of mathematical programming formulations.We develop and test two resolution approaches. The first is based on Dantzig-Wolfedecomposition associated with a branching on no-overlapping disjunctive constraints. Thisapproach permits to improve results obtained by mathematical programming.The second approach establish a combinatorial approach based on multiple intervalgraph caracterization (modelling the item no-overlapping according to their projection oneach axis). The first algorithm is based on consecutive ones matrices enumeration. An otheruse labelled tree to eliminate more efficiently symmetry in packing. These approaches haveto advantage of being independent from bin discretization

Submitted by Franciele Moreira (francielemoreyra@gmail.com) on 2017-10-20T16:09:47Z No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-10-23T10:05:52Z (GMT) No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-10-23T10:05:52Z (GMT). No. of bitstreams: 2 Dissertação - Lorrany Cristina da Silva - 2017.pdf: 8394886 bytes, checksum: 9cc1461b937a65a8c50964b3dea86623 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-06-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Three different integer linear programming models for the Vehicle Routing Problem with Two-dimensional Loading Constraints are developed in this work. The version of the problem studied considers that the unloading of the rectangular items can respect or not the sequence of the clients visited on the route, that is, we solve the sequential and unrestricted versions of the problem. The first model deals with the problem completely, that is, with all constraints inserted at once. The second and third models are based, respectively, on a three- and two-index formulation. Separation routines are considered to detect violated inequalities related with packing on the second and third models, while the third model also considers cuts on connectivity and capacity. Computational experiments were carried out over instances of the literature with the quantity of customers ranging from 15 to 36 and items from 15 to 114, besides to consider the cases in which the cost of traversing an edge is integer and real. The models with cuts on demand were better in relation to the first model, besides being competitive when comparing with the results fromthe literature. The first model solved 4 of the 80 instances, the three-index model solved 7 and, the two-index model solved 53. On the sequential version, the adopted model solved 33 instances for the case with integer costs (and 37 for the case with real costs). In comparing with a recent heuristic from the literature, the best model was capable of tying in 48 instances in the unrestricted version and 24 in the sequential version. / Neste trabalho desenvolvem-se três modelos de programação linear inteira para o Problema de Roteamento de Veículos com Restrições de Empacotamento Bidimensional. A versão do problema estudado considera que o descarregamento dos itens retangulares pode respeitar (ou não) a sequência de clientes visitados na rota, ou seja, resolve-se as versões sequencial e irrestrita do problema. O primeiro modelo trata do problema de forma completa, isto é, com todas as restrições inseridas de uma só vez. O segundo e o terceiro modelo são baseados, respectivamente, em uma formulação de três e dois índices. Rotinas de separação são consideradas para detectar desigualdades violadas de empacotamento no segundo e no terceiro modelo, enquanto o último modelo considera também cortes de conectividade e capacidade. Experimentos computacionais foram realizados em instâncias da literatura com número de clientes variando de 15 a 36 e itens de 15 até 114, além de considerar os casos em que o custo da aresta é inteiro ou real. Os modelos com cortes sob demanda foram melhores em relação ao primeiro modelo, além de serem competitivos quando comparado com a literatura. O modelo completo encontrou a solução ótima em 4 das 80 instâncias, o modelo de três índices 7 e o modelo de dois índices 53. Na versão sequencial, o modelo adotado resolveu 33 instâncias para o custo inteiro (e 37 para o custo real). Na comparação com uma heurística recente da literatura, o melhor modelo conseguiu empatar em 48 instâncias na versão irrestrita e em 24 na versão sequencial.

Dans cette thèse, nous nous intéressons à trois problèmes issus de l'informatique théorique, à savoir le placement de formes rectangulaires dans un conteneur (OPP), la coloration dite "forte" d'arêtes des graphes et les codes identifiants dans les graphes. L'OPP consiste à décider si un ensemble d'items rectangulaires peut être placé sans chevauchement dans un conteneur rectangulaire et sans dépassement des bords de celui-ci. Une contrainte supplémentaire est prise en compte, à savoir l'interdiction de rotation des items. Le problème est NP-difficile même dans le cas où le conteneur et les formes sont des carrés. Nous présentons un algorithme de résolution efficace basé sur une caractérisation du problème par des graphes d'intervalles, proposée par Fekete et Schepers. L'algorithme est exact et utilise les MPQ-arbres - structures de données qui encodent ces graphes de manière compacte tout en capturant leurs propriétés remarquables. Nous montrons les résultats expérimentaux de notre approche en les comparant aux performances d'autres algorithmes existants. L'étude de la coloration forte d'arêtes et des codes identifiants porte sur les aspects structurels et de calculabilité de ces deux problèmes. Dans le cas de la coloration forte d'arêtes nous nous intéressons plus particulièrement aux familles des graphes planaires et des graphes subcubiques. Nous montrons des bornes optimales pour l'indice chromatique fort des graphes subcubiques en fonction du degré moyen maximum et montrons que tout graphe planaire subcubique sans cycles induits de longueur 4 et 5 est coloriable avec neuf couleurs. Enfin nous confirmons la difficulté du problème de décision associé, en prouvant qu'il est NP-complet dans des sous-classes restreintes des graphes planaires subcubiques.La troisième partie de la thèse est consacrée aux codes identifiants. Nous proposons une caractérisation des graphes identifiables dont la cardinalité du code identifiant minimum ID est n-1, où n est l'ordre du graphe. Nous étudions la classe des graphes adjoints et nous prouvons des bornes inférieures et supérieures serrées pour le paramètre ID dans cette classe. Finalement, nous montrons qu'il existe un algorithme linéaire de calcul de ID dans la classe des graphes adjoints L(G) où G a une largeur arborescente bornée par une constante. En revanche nous nous apercevons que le problème est NP-complet dans des sous-classes très restreintes des graphes parfaits. / In this thesis we study three theoretical computer science problems, namely the orthogonal packing problem (OPP for short), strong edge-colouring and identifying codes.OPP consists in testing whether a set of rectangular items can be packed in a rectangular container without overlapping and without exceeding the borders of this container. An additional constraint is that the rotation of the items is not allowed. The problem is NP-hard even when the problem is reduced to packing squares in a square. We propose an exact algorithm for solving OPP efficiently using the characterization of the problem by interval graphs proposed by Fekete and Schepers. For this purpose we use some compact representation of interval graphs - MPQ-trees. We show experimental results of our approach by comparing them to the results of other algorithms known in the literature. we observe promising gains.The study of strong edge-colouring and identifying codes is focused on the structural and computational aspects of these combinatorial problems. In the case of strong edge-colouring we are interested in the families of planar graphs and subcubic graphs. We show optimal upper bounds for the strong chromatic index of subcubic graphs as a function of the maximum average degree. We also show that every planar subcubic graph without induced cycles of length 4 and 5 can be strong edge-coloured with at most nine colours. Finally, we confirm the difficulty of the problem by showing that it remains NP-complete even in some restricted classes of planar subcubic graphs.For the subject of identifying codes we propose a characterization of non-trivial graphs having maximum identifying code number ID, that is n-1, where n is the number of vertices. We study the case of line graphs and prove lower and upper bounds for ID parameter in this class. At last we investigate the complexity of the corresponding decision problem and show the existence of a linear algorithm for computing ID of the line graph L(G) where G has the size of the tree-width bounded by a constant. On the other hand, we show that the identifying code problem is NP-complete in various subclasses of planar graphs.