Use este identificador para citar ou linkar para este item:
http://repositorio.ufgd.edu.br/jspui/handle/prefix/2993
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.contributor.advisor1 | Hoshino, Edna Ayako | - |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/9160943574918408 | pt_BR |
dc.creator | Abe, Fabio Henrique Noboru | - |
dc.creator.Lattes | http://lattes.cnpq.br/0784752520103819 | pt_BR |
dc.date.accessioned | 2020-05-11T13:44:40Z | - |
dc.date.available | 2020-05-11T13:44:40Z | - |
dc.date.issued | 2016-07-22 | - |
dc.identifier.citation | ABE, Fabio Henrique Noboru. Problema das pseudo-arborescências capacitadas com localização de facilidades. 2016. Dissertação (Mestrado em Ciência da Computação) – Faculdade de Computação, Universidade Federal do Mato Grosso do Sul, Dourados, MS, 2016. | pt_BR |
dc.identifier.uri | http://repositorio.ufgd.edu.br/jspui/handle/prefix/2993 | - |
dc.description.abstract | In this work, we present the capacitated pseudo arborescences with facility location problem, which is a new problem related to two classical problems: the capacitated vehicle routing problem and the capacitated facility location problem. The proposed problem generalizes the capacitated ring tree problem. We propose in this study two integer programming formulations to model the problem. The first one is an extended formulation based on set partition and the second one is a compact formulation based on flow models. We also propose two exact algorithms to solve the problem. One of them uses the branch-and-price algorithm with the extended formulation and the other one is a branch-and-bound algorithm based on the compact formulation. We also implemented a primal heuristic and a pricing heuristic aiming to improve the performance of exact methods. Computational experiments shown that the extended formulation provides tighter bounds than the compact formulation. Additionally, we observed that the heuristics were relevant to accelerate the branch-and-price and the branch-and-bound algorithms, mainly the primal heuristic. | en |
dc.description.resumo | Neste trabalho apresentamos o problema das pseudo-arborescências capacitadas com localização de facilidades, um problema novo e relacionado a dois outros problemas clássicos: o problema do roteamento de veículos capacitado e o problema da localização de facilidade capacitada. O problema estudado é uma generalização do problema da pseudo-arborescência capacitada, em inglês capacitated ring tree problem. Propomos neste estudo duas formulações em programação linear inteira para modelar o problema. A primeira é uma formulação estendida baseada em partição de conjuntos e a segunda é uma formulação compacta baseada em fluxos. Propomos também dois algoritmos exatos para resolver o problema. Um deles utiliza a técnica de branch-and-price com a formulação estendida e o outro é um algoritmo do tipo branch-and-bound baseado na formulação compacta. Implementamos também uma heurística primal e uma heurística de pricing com o objetivo de melhorar o desempenho dos métodos exatos. Experimentos computacionais realizados em um grupo de instâncias testes mostram que a formulação estendida fornece limitantes muito mais apertados do que a formulação compacta. Além disso, as heurísticas foram relevantes para acelerar os métodos de branch-and-price e branch-and-bound, em especial a heurística primal. | pt_BR |
dc.description.provenance | Submitted by Alison Souza (alisonsouza@ufgd.edu.br) on 2020-05-11T13:44:40Z No. of bitstreams: 1 UFMS - FabioHenriqueNoboruAbe.pdf: 583468 bytes, checksum: 88422983d403cd93ed4d15d7e66c19ea (MD5) | en |
dc.description.provenance | Made available in DSpace on 2020-05-11T13:44:40Z (GMT). No. of bitstreams: 1 UFMS - FabioHenriqueNoboruAbe.pdf: 583468 bytes, checksum: 88422983d403cd93ed4d15d7e66c19ea (MD5) Previous issue date: 2016-07-22 | en |
dc.description.sponsorship | Fundação de Apoio ao Desenvolvimento do Ensino, Ciência e Tecnologia do Estado de Mato Grosso do Sul (FUNDECT) | pt_BR |
dc.language | por | pt_BR |
dc.publisher | Universidade Federal de Mato Grosso do Sul | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | Faculdade de Computação | pt_BR |
dc.publisher.program | Programa de pós-graduação em Ciência da Computação | pt_BR |
dc.publisher.initials | UFMS | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Pseudo-arborescência capacitada | pt_BR |
dc.subject | Capacitated pseudo arborescence | en |
dc.subject | Otimização combinatória | pt_BR |
dc.subject | Combinatorial optimization | en |
dc.subject | Heurística | pt_BR |
dc.subject | Heuristic | en |
dc.subject | Programação linear | pt_BR |
dc.subject | Linear programming | en |
dc.subject.cnpq | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO | pt_BR |
dc.title | Problema das pseudo-arborescências capacitadas com localização de facilidades | pt_BR |
dc.type | Dissertação | pt_BR |
Aparece nas coleções: | Dissertações |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
UFMS - FabioHenriqueNoboruAbe.pdf | 569,79 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.