Uma heurística para o problema de distribuição de cargas perecíveis

• Ano de defesa: 1984
• Autor(a) principal: Acioli Antonio de Olivo
• Orientador(a): Horácio Hideki Yanasse
• Banca de defesa: Michal Gartenkraut, Flávio Freitas Faria, Oscar Pereira Dias
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Análise de Sistemas e Aplicações
• País: BR
• Resumo em Inglês: This work is concerned with the fleet routing problem for pershible loads. The objective is to minimize the distribution costs of the load. Costs taken into consideration include fleet´s size and the transportation costs. In addition to satisfying the demand requeriments, there are further restrictions on vehicles capacites and delivery times. Sampron developed a mathematical model for this problem without worrying too much with its solutions. So, even for problems with only nine delivery points using the Burroughs MPS-TEMPO package, he found only an approximate solution after more than two hours of CPU time. Due to the computational difficulties faced in finding the optimal solution to the routing problem, we seeked an alternative way to find a solution to it. An heuristic algorithm has been developed to solve this problem which has been performing quite satisfactory in the tests performed, in terms of the solution found and the computational time. This solution given the heuristic method can be used directly for the vehicle routigs or can be used as an intermediate step in an exact method (like Branch-and-Bound) to accelerate the branch and bound process and consequently decrease the computational time.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m18@80/2009/07.23.14.41

Este trabalho aborda o roteamento de uma frota de veículos transportando cargas perecíveis. Tem-se como objetivo minimizar o custo de distribuição desta carga. São considerados, para efeito de calculo de custo, o tamanho da frota e os custos de transporte. Além das restrições normais de satisfação da demanda, existem também restrições adicionais de capacidade dos veículos e prazos de entrega que devem ser obedecidos. Sampron desenvolveu um modelo para este problema sem grandes preocupações com sua resolução. Assim sendo, mesmo para problemas com nove pontos de entrega, usando o pacote MPS-TEMPO da Burroughs, ele encontrou apenas uma solução aproximada após mais de duas horas de CPU as dificuldades computacionais encontradas na resolução do problema de roteamento procurou-se uma maneira alternativa de solucioná-lo. Optou-se por desenvolver um algorítmo heurístico, que se mostrou bastante satisfatório nos testes realizados, em termos de solução encontrada e do tempo de computação. A solução dada por esta heurística poderá ser utilizada diretamente para o roteamento dos veículos, ou poderá servir num passo intermediário de um método exato (do tipo "Branch-and-Bound") para agilizar o processo de poda e busca e, consequentemente, diminuir o tempo de computação.