Skip navigation

Use este identificador para citar ou linkar para este item: https://repositorio.ufpb.br/jspui/handle/123456789/25260
Tipo: Dissertação
Título: Uma abordagem exata unificada para uma classe de problemas de roteamento de veículos com coleta e entrega simultâneas
Autor(es): Praxedes, Rafael Maranhão Rego
Primeiro Orientador: Subramanian, Anand
Primeiro Coorientador: Bulhões Júnior, Teobaldo Leite
Resumo: O Problema de Roteamento de Veículos (PRV) é um problema de otimização combinat ória clássico amplamente estudado na literatura. Por de nição, consiste em determinar as rotas de menor custo, que são iniciadas e nalizadas no mesmo depósito, de modo a atender as demandas de um conjunto de clientes. Há uma diversidade de variantes desse problema, as quais podem incluir atributos adicionais, tais como frota de veículos heterogênea, janelas de tempo, entre outros. Dentre esses problemas, há o PRV com Coleta e Entrega Simultâneas (PRVCES), que considera o fato dos clientes possuírem tanto demandas de entrega quanto de coleta a serem satisfeitas em uma única visita. Nesse contexto, este trabalho tem como objetivo propor uma abordagem exata uni - cada baseada em geração de colunas e de cortes para resolver dez variantes do PRVCES, incluindo a versão clássica do problema. Essa abordagem faz uso do VRPSolver, um resolvedor branch-cut-and-price estado-da-arte para problemas de roteamento e a ns. Os resultados mostram que a abordagem proposta é bastante efetiva na obtenção de solu ções ótimas ou aprimoramento dos limites duais para muitas instâncias da literatura em aberto.
Abstract: The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem widely studied in the literature. By de nition, it consists in determining least-cost routes, starting and ending at the depot, to meet the demands of a set of customers. There is a substantial number of variants of the problem, which might include additional attributes such as a heterogeneous eet of vehicles, time windows, and so on. Among them, there is the VRP with Simultaneous Pickup and Delivery (VRPSPD), where customers have both pickup and delivery demands to be satis ed in a single visit. In this context, this work aims at proposing a uni ed exact approach based on column generation and cutting planes to solve ten VRPSPD variants including the classic version of the problem. This approach uses the VRPSolver, which is a state-of-the-art branch-cut-and-price solver for routing and similar problems. The results show that the proposed approach is highly e ective in obtaining the optimal solutions or improving the dual bounds for many open benchmark instances.
Palavras-chave: Roteamento de veículos
Coleta e entrega simultâneas
Geração de colunas
Planos de corte
Vehicle routing
Simultaneous pickup and delivery
Column generation
Cutting planes
CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Idioma: por
País: Brasil
Editor: Universidade Federal da Paraíba
Sigla da Instituição: UFPB
Departamento: Informática
Programa: Programa de Pós-Graduação em Informática
Tipo de Acesso: Acesso aberto
Attribution-NoDerivs 3.0 Brazil
URI: http://creativecommons.org/licenses/by-nd/3.0/br/
URI: https://repositorio.ufpb.br/jspui/handle/123456789/25260
Data do documento: 19-Ago-2022
Aparece nas coleções:Centro de Informática (CI) - Programa de Pós-Graduação em Informática

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
RafaelMaranhãoRegoPraxedes_Dissert.pdf904,25 kBAdobe PDFVisualizar/Abrir


Este item está licenciada sob uma Licença Creative Commons Creative Commons