Abordagens para problemas de roteamento

AUTOR(ES)
DATA DE PUBLICAÇÃO

2004

RESUMO

Neste trabalho, investigamos abordagens para problemas de roteamento, que têm como finalidade encontrar um melhor conjunto de rotas para que veículos possam transportar mercadorias a clientes geograficamente dispersos, respeitando certas restrições, como por exemplo, a de capacidade de carga dos veículos. Para isto, além de pesquisas em diversas fontes de informações, desenvolvemos um aplicativo para auxiliar no entendimento dos algoritmos, na ilustração do texto e na realização de experimentos. A partir de observações feitas durante as execuções do aplicativo, experimentamos combinações de critérios de seleção de localidades, utilizando tais combinações durante a realização dos movimentos de intercâmbio de vértices entre rotas de uma conhecida estratégia, a Metaheurística Busca Tabu. Foram combinados critérios baseados em distâncias com critérios baseados em ângulos, para compor algoritmos que foram testados com instâncias clássicas utilizadas por diversos pesquisadores. Os resultados obtidos foram apresentados juntamente com os de outras estratégias, fornecendo valores iguais ao melhor valor conhecido para duas instâncias, e valores intermediários para as outras cinco instâncias utilizadas nos testes In this work, we examine some approaches for vehicle routing problems, to find a best set of routes to enable companies for delivery goods or commodities to customers, respecting some constraints, such as vehicles loading capacity. To this purpose, besides researching available information sources, we have developed a software to help us to understand the algorithms issues, for enriching the text with illustrations, and for effectiving some experiments concerning to previously selected approaches. From the analysis made during running software process, we decided to arrange chosen vertices criterias, using these arrangements in the vertices interchanging movements between routes of an already know method, the Tabu Search Metaheuristic. More precisely, we have combined distances and angles criteria, to implement algorithms on which it were tested using some classical instances considered by several researchers. The obtained results are presented with those selected approaches, and it provided us two equals values to the best known solution, and five intermediate values amoung to the others used on these experiments

ASSUNTO(S)

algoritmos pesquisa operacional heuristica otimização combinatoria

ACESSO AO ARTIGO

Documentos Relacionados