Modelagem e Desenvolvimento de Algoritmo para o Problema de Roteamento Dinâmico de Veículos

Detalhes bibliográficos
Ano de defesa: 2022
Autor(a) principal: WILTON GUSTAVO GOMES DA COSTA
Orientador(a): Ricardo Ribeiro dos Santos
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Fundação Universidade Federal de Mato Grosso do Sul
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Brasil
Palavras-chave em Português:
Link de acesso: https://repositorio.ufms.br/handle/123456789/5173
Resumo: Finding efficient routes for a vehicle fleet to minimize distance and time and maximizing service profit are some of the goals pursued in solving the Vehicle Routing Problem (VRP). The VRP and its variants are widely studied in the area, with several proposals for models, algorithms, and techniques (methods). The goal of this work is to present an approach named Dynamic Vehicle Routing Problem (DVRP). In the DVRP the set of items to be delivered are not known in advance. This is a current problem targeted to logistics companies, especially those whose focus is on marketplace, that should manage thousands of products to be delivered along a working day subject to constraints on vehicle fleets and service hours. In this work, dynamic and static routing algorithms, named Dynamic Search per Neighbors Routes (DSNR) and Kmeans, Relax-and-Fix and Optimizations (K-RFO), respectively, are proposed. The scenery for the dynamic algorithm is the routing of batches of packages (items) to be delivered at the same working day. The DVRP algorithm is based on a local search together with a 2-Opt** heuristic aiming to re-optimize neighboring routes to accommodate dynamic packages. The DSNR algorithm has been evaluated and compared to dynamic algorithms QRP-Sweep (QRPS) and Kmeans-Greedy (KG), achieving up to 17% of operational costs savings.