Métodos heurísticos aplicados ao problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados por faixas de distância.

• Ano de defesa: 2020
• Autor(a) principal: Manguino, João Luiz Veiga
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Busca Local; GRASP; Heurística; Heuristics; Híbrido; Hybrid; Local search; Mathematical model; Meta-heurística; Meta-heuristics; Modelo matemático; Programação linear inteira mista; Roteamento de veículos; Vehicle Routing Mroblem; VNS
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/3/3136/tde-04092020-090739/

Este trabalho aborda o problema de roteamento de veículos com frota mista, janelas de tempo e custos escalonados o FSMVRPTWSC (the Fleet Size and Mix Vehicle Routing Problem with Time Windows and Step Costs). Esse problema adiciona ao problema de roteamento de veículos custos fixos por faixas de distância percorridas por veículo, de acordo com o seu tipo. Essa forma de aferição de custo é possível quando a entrega é feita por um parceiro logístico e é uma prática que simplifica o cálculo e verificação da cobrança frete a pagar pela empresa contratante e contratada. Ao endereçar esse problema, este trabalho o caracteriza cuidadosamente e propõe diferentes abordagens para sua solução. Um modelo de programação linear inteira mista é apresentado; seguido por duas heurísticas construtivas, com base em inserções sequenciais, três movimentos de busca em vizinhança, duas meta-heurísticas, o VNS (Variable Neighbourhood Search) e GRASP (Greedy Randomized Adaptive Search Procedure), e um método híbrido que combina os dois. Os métodos são avaliados em instâncias geradas com base em referências na literatura, além de outras de dimensões menores, a fim de se obter resultados ótimos globais, e instâncias reais a partir de um estudo de caso. Apesar do ineditismo do problema na literatura, as comparações feitas com os resultados obtidos pelos diferentes métodos e instâncias mostram que as escolhas feitas no trabalho se justificam.