Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional
| dc.contributor.advisor1 | Queiroz, Thiago Alves de | |
| dc.contributor.advisor1Lattes | http://lattes.cnpq.br/8041183668335400 | eng |
| dc.contributor.referee1 | Toledo, Franklina Maria Bragion de | |
| dc.contributor.referee2 | Silva, Sérgio Francisco da | |
| dc.creator | Silva, Lorrany Cristina da | |
| dc.creator.Lattes | http://lattes.cnpq.br/1781234164900622 | eng |
| dc.date.accessioned | 2017-10-23T10:05:52Z | |
| dc.date.accessioned | 2022-04-26T13:40:08Z | |
| dc.date.available | 2022-04-26T13:40:08Z | |
| dc.date.issued | 2017-06-28 | |
| dc.description.abstract | 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. | eng |
| dc.description.resumo | 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. | eng |
| dc.description.sponsorship | Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES | eng |
| dc.format | application/pdf | * |
| dc.identifier.citation | SILVA, Lorrany Cristina da. Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional. 2017. 89 f. Dissertação (Mestrado em Modelagem e Otimização) - Universidade Federal de Goiás, Catalão, 2017. | eng |
| dc.identifier.uri | http://repositorio.ufcat.edu.br/tede/handle/tede/7899 | |
| dc.language | por | eng |
| dc.publisher | Universidade Federal de Goiás | eng |
| dc.publisher.country | Brasil | eng |
| dc.publisher.department | Regional Catalão (RC) | eng |
| dc.publisher.initials | UFG | eng |
| dc.publisher.program | Programa de Pós-graduação em Modelagem e Otimização (RC) | eng |
| dc.rights | Acesso Aberto | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Problema integrado | por |
| dc.subject | Problema de roteamento de veículos | por |
| dc.subject | Problema de empacotamento ortogonal bidimensional | por |
| dc.subject | Programação linear inteira | por |
| dc.subject | Planos de corte | por |
| dc.subject | Integrated problem | eng |
| dc.subject | Vehicle routing problem | eng |
| dc.subject | Two-dimensional orthogonal packing problem | eng |
| dc.subject | Integer linear programmig | eng |
| dc.subject.cnpq | CIENCIAS EXATAS E DA TERRA::MATEMATICA | eng |
| dc.title | Modelos para o problema de roteamento de veículos com restrições de empacotamento bidimensional | eng |
| dc.title.alternative | Models for the vehicle routing problem with two-dimensional loading constraints | eng |
| dc.type | Dissertação | eng |