Uma solução heurística com iterated local search para o problema de roteamento de veículos de frota heterogênea e entregas fracionárias

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorOchi, Luiz Satoru-
Autor(es): dc.contributorhttp://lattes.cnpq.br/9171815778534257-
Autor(es): dc.contributorCoelho, Igor Machado-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5298061910591710-
Autor(es): dc.contributorBoeres, Maria Claudia Silva-
Autor(es): dc.contributorhttp://lattes.cnpq.br/0528154281423964-
Autor(es): dc.contributorhttp://lattes.cnpq.br/5681867374331123-
Autor(es): dc.creatorPlouvier, Luciano Ferreira-
Data de aceite: dc.date.accessioned2024-07-11T17:48:29Z-
Data de disponibilização: dc.date.available2024-07-11T17:48:29Z-
Data de envio: dc.date.issued2022-11-21-
Data de envio: dc.date.issued2022-11-21-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/27038-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/757911-
Descrição: dc.descriptionO Problema de Roteamento de Veículos – PRV é um problema clássico na computação. Sua importância tanto acadêmica como na prática se deve principalmente à sua grande aplicabilidade. Este é um problema de elevada complexidade computacional, considerando que o PRV é um problema NP-Difícil, quando não se conhece uma solução em tempo polinomial, por ser uma generalização do Traveling Salesman Problem – TSP. Existe na literatura uma grande quantidade de variações do modelo básico do PRV, entretanto alguns modelos embora possuam aplicações em muitas situações reais, ainda não são muito exploradas pela literatura afim. Uma delas é o foco deste trabalho; conhecido como o Problema de Roteamento de Veículos de Frota Heterogênea e Entregas Fracionárias - PRVFHEF. A cada ano observa-se um grande aumento no número de compras online, cuja característica principal, é o cliente efetuar essa compra em diversos sites de empresas como: Mercado Livre, Amazon.com, Americanas.com entre outros, além de que cada item adquirido usualmente é fabricado num local específico do Brasil, ou do exterior. Essa diversidade nos locais de fabricação dos itens normalmente acarreta num processo de entregas fracionadas (split delivery), uma estratégia de logística e transporte muito utilizada pelas grandes empresas de vendas/entregas de mercadorias. O aumento das compras (principalmente online) também ocasiona um aumento no número de arrependimentos e retorno de pedidos, chamado de logística reversa, aumentando ainda mais a necessidade de transporte de carga eficiente. Todos estes requisitos criam a necessidade de usar diversos veículos de características diferentes para serem atendidos. Mesmo com a grande importância deste problema, observamos que ainda não existem muitas contribuições deste segmento na literatura. Neste trabalho é efetuado um resumo parcial destes problemas, e é proposto um novo algoritmo heurístico multistart, baseado no Iterated Local Search – ILS, para solucionar este problema. Além dos métodos de buscas locais comuns na literatura para resolver os PRVs básicos, também são aplicados métodos específicos para solucionar a divisão das demandas e lidar com as limitações dos veículos. O algoritmo desenvolvido foi testado com instâncias do problema encontrados na literatura, obtendo resultados próximos às melhores soluções conhecidas em boa quantidade dos casos.-
Descrição: dc.descriptionThe Vehicle Routing Problem – VRP is an important classic computational problem due to its academical and pratical aplicability, considering the VRP is a NP-Hard problem, which means a polinomial solution to solve it is not known, as the VRP is a generalization of the Traveling Salesman Problem – TSP. Although there are many variations of the basic VRP model, some of the models that can be applied to real problems have not been explored very much by the literature. One of these problems is the Split Delivery Heterogeneous Fleet Vehicle Routing Problem – SDHFVRP. Every year there is a significant increase in online sales, whose principal characteristic is the client buying at sites like Mercado Livre, Amazon.com, Americanas.com and others. Also, every item acquired is usually produced in a specific location in Brazil or internationally. This diversity in the fabrication locations normally entails in a process of split delivery, which is a common strategy in logistics and transport, utilized by big delivery companies. The increase in purchacing (specially online sales) also increases the number of Purchase Returns, known as Reverse Logistics, which increases even more the need of efficient transportation. All of these requirements create the necessity of using different vehicles for delivering requests. Even with the relevance of this problem, there are not many studies directed at this subject. In this work a partial resume of the problem is presented, and a new multistart algorithm is proposed, based in Iterated Local Search – ILS, to solve this problem. In addition to the local search methods common to the basic VRPs, specific methods to solve the Split Delivery and to manage the specific properties of the heterogeneous vehicle fleet are applied. The algorithm developed was tested with known problems of fixed and variable costs, finding solutions close to the best known solutions in a good amount of cases.-
Descrição: dc.description55 f.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectProblema de roteamento de veículos-
Palavras-chave: dc.subjectEntrega fracionária-
Palavras-chave: dc.subjectFrota heterogênea-
Palavras-chave: dc.subjectIterated local search-
Palavras-chave: dc.subjectLogística-
Palavras-chave: dc.subjectOtimização combinatória (Computação)-
Palavras-chave: dc.subjectAlgoritmo heurístico-
Palavras-chave: dc.subjectBusca local iterativa-
Palavras-chave: dc.subjectProblema de roteamento de veículo-
Palavras-chave: dc.subjectVehicle routing problem-
Palavras-chave: dc.subjectSplit delivery-
Palavras-chave: dc.subjectHeterogeneous fleet-
Palavras-chave: dc.subjectLogistics-
Título: dc.titleUma solução heurística com iterated local search para o problema de roteamento de veículos de frota heterogênea e entregas fracionárias-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.