Use este identificador para citar ou linkar para este item: https://locus.ufv.br//handle/123456789/11651
Tipo: Dissertação
Título: Algoritmos exatos e heurísticos para o problema de roteamento duplo de veículos com múltiplas pilhas e demanda heterogênea
Exact and heuristic algorithms for the double vehicle routing problem with multiple stacks and heterogeneous demand
Autor(es): Chagas, Jonatas Batista Costa das
Abstract: Este trabalho aborda dois problemas de roteamento de veículos de coleta e entrega com restrições de carregamento. Primeiramente foi tratado o Problema de Rotea- mento Duplo de Veículos com Múltiplas Pilhas (Double Vehicle Routing Problem with Multiple Stacks - DVRPMS). Posteriormente foi formulado e proposto o Problema de Roteamento Duplo de Veículos com Múltiplas Pilhas e Demanda Heterogênea (Double Vehicle Routing Problem with Multiple Stacks and Heterogeneous Demand - DVRPMSHD), se referindo a um caso mais realista do DVRPMS, quando os clientes têm demandas múltiplas e heterogêneas, sendo que toda a demanda de um mesmo cliente deve ser transportada por um único veículo. Em ambos os problemas, o objetivo é determinar rotas para uma frota de veículos a fim de atender a demanda de um conjunto de clientes de forma que a distância percorrida pelos veículos seja a mínima possível, respeitando algumas restrições de carregamento impostas pelas pilhas de armazenamento dos veículos. Todos os produtos localizados em uma região de coleta devem ser coletados e depois entregues em uma região de entrega pelos veículos. As regiões de coleta e entrega são largamente separadas, portanto todos os produtos devem ser carregados antes de qualquer descarregamento. O DVRPMS foi abordado principalmente por quatro métodos heurísticos, os quais foram testados em diversas instâncias e comparados aos métodos exatos e heurísticos já existentes na literatura. Os experimentos computacionais mostraram a eficiência dos algorit- mos propostos, obtendo soluções de melhor qualidade que as soluções apresentadas na literatura para a maioria dos casos de teste com baixo tempo computacional. Já o DVRPMSHD foi abordado de forma exata e heurística. Inicialmente, foi desen- volvido um método exato branch-and-price que apresentou maior eficiência quando comparado à formulação matemática também proposta para o problema. O método heurístico superou os resultados alcançados pelo branch-and-price para a maioria das instâncias de teste formuladas.
In this work we address two vehicle routing problems with pickup and delivery and loading constraints. Firstly, this work addresses the Double Vehicle Routing Pro- blem with Multiple Stacks (DVRPMS). Posteriorly we formulate and propose the Double Routing Vehicle Problem with Multiple Stacks and Heterogeneous Demand (DVRPMSHD), referring to a more realistic case of the DVRPMS in which custo- mers have multiple and heterogeneous demands and all demand of a same client must be transported by a single vehicle. In both problems, the objective is to de- termine routes for a fleet of vehicles to meet the demand of a set of customers so that the distance travelled by the vehicles is the minimum possible, respecting some loading constraints imposed by the vehicles’ storage stacks. All products located in a pickup region must be collected and then delivered to a delivery region by vehicles. The pickup and delivery regions are largely separated so that all products must be loaded before any unloading. The DVRPMS was approached mainly by four heuristic methods, which were tested in several instances and compared to the exact and heuristic methods already present in literature. The computational experiments showed the efficiency of the proposed algorithms, obtaining solutions of better quality than those presented in the literature for most of the instances and with low computational time. The DVRPMSHD was approached by an exact method and a heuristic method. Initially, the implemented branch-and-price exact method presented higher efficiency compared to the proposed mathematical formu- lation for the problem. The heuristic method overcame the results achieved by the branch-and-price for most of the created instances.
Palavras-chave: Pesquisa operacional
Otimização combinatória
Otimização matemática
Programação heurística
Logística
CNPq: Ciência da Computação
Editor: Universidade Federal de Viçosa
Citação: CHAGAS, Jonatas Batista Costa das. Algoritmos exatos e heurísticos para o problema de roteamento duplo de veículos com múltiplas pilhas e demanda heterogênea. 2017. 139 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Viçosa, Viçosa. 2017.
Tipo de Acesso: Acesso Aberto
URI: http://www.locus.ufv.br/handle/123456789/11651
Data do documento: 7-Mar-2017
Aparece nas coleções:Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
texto completo.pdftexto completo2,79 MBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.