SISTEMA DE DEFINIÇÃO DE ROTAS PARA SERVIÇOS DE ENTREGA EXPRESSA

1

ATC - TIDIR IV

INSTITUTO POLITÉCNICO – Centro Universitário UNA

SISTEMA DE DEFINIÇÃO DE ROTAS PARA SERVIÇOS DE

ENTREGA EXPRESSA

CURSO: Sistemas de Informação TURMA: SII2BN-RJA

Professor: Rafael Pinheiro Amantéa

Guilherme Junio Silva de Oliveira, John Vaz de Souza, Júlio César Ferreira D’Agostini,

Leandro Chaves Alves Araújo, Paulo Henrique Almeida de Souza, Rafael Pimenta de

Oliveira, Vaniélli Maria César Jardim

RESUMO: Este artigo mostra a comparação dos algoritmos Busca Tabu e Força

Bruta para o problema do caixeiro viajante. Tais algoritmos foram implementados em

um variado número de cidades, a fim de determinar a menor rota a ser utilizada para

o percurso através do resultado de tempo e custo obtidos. Verifica-se que

o algoritmo Busca Tabu apresentou o melhor resultado, considerando-se o tempo de

execução e o custo. Enquanto o algoritmo de Força Bruta tornou-se inviável pelo seu

grau de complexidade fatorial.

Palavras Chaves: Busca Tabu, Problema do Caixeiro Viajante, Heurística, Meta-

Heurística, Pesquisa Operacional.

1 INTRODUÇÃO

A otimização combinatória é um ramo da Pesquisa Operacional (PO) que

estuda problemas de otimização em conjuntos finitos com dificuldade não

polinomiais NP, os quais são problemas que possuem uma forte evidência da não

existência de um algoritmo cujo tempo de solução seja uma função polinomial do

tamanho da entrada.

Quando se sabe que um problema de otimização é NP - difícil, tem-se a

certeza de que nem sempre a solução ótima será encontrada. Portanto, tem-se

aplicado métodos heurísticos, como por exemplo, a Busca Tabu, os algoritmos

genéticos, os algoritmos da colônia de formiga, arrefecimento simulado, dentre

outros.

O modelo do Problema do Caixeiro Viajante (PCV) é descrito por Hillier e

Lieberman (2013) como uma situação em que um vendedor deve visitar cada cidade

de um circuito exatamente uma vez retornando à cidade de origem, para tanto deve2

se encontrar a menor rota, de modo a minimizar o comprimento total do circuito,

sendo este modelo de otimização combinatória. Convém citar as diversas aplicações

para este modelo, assim como: projeto genoma, ensalamento em escolas e

universidades, corte de materiais, escalonamento de trabalho humano, planejamento

de produção, roteirização de veículos entre outros.

O PCV é um problema de otimização que, apesar de parecer modesto é, na

realidade, muito investigado por cientistas, matemáticos e investigadores de

diversas áreas (Applegate, 2006).

Segundo Helsgaun (2000), não há como achar a solução ótima sem o uso da

Força Bruta, ou algum algoritmo exato, que normalmente é de complexa

programação, com códigos da ordem de 10.000 linhas e exagerado tempo de

execução. Portanto, será implementado o método heurístico, de otimização

combinatória, a Busca Tabu para o PCV.

Para tanto, um protótipo para calcular a menor distância foi desenvolvido

através da Heurística Busca Tabu para o PCV aplicado a uma empresa de expresso,

além disso, os requisitos foram levantados e descritos e, a bibliografia de

modelagem da linguagem de programação orientada a objetos foi revisada.

2 REVISÃO BIBLIOGRÁFICA

A PO pode ser definida, conforme Ehrlich (1985), como um conjunto de

técnicas quantitativas com o intuito de auxiliar o processo de decisão dentro de uma

filosofia de modelagem e, preferivelmente, de otimização.

A Heurística é uma área da PO para resolver problemas. Não é uma "ciência"

no sentido usual da palavra, pois não há regras definidas que nos levem, diante de

um problema, a saber solucioná-lo.

Heurísticas são procedimentos de solução que muitas vezes se apoiam em uma

abordagem intuitiva, na qual a estrutura particular do problema possa ser

considerada e explorada de forma inteligente, para a obtenção de uma solução

adequada (CUNHA, 1997, p. 38).

A Busca Tabu para Laguna (1997) é uma Meta-Heurística que consiste em

explorar o espaço de soluções de um problema combinatório utilizando um

mecanismo de memória adaptativa. Durante o processo de busca, dependendo do

3

conteúdo da memória adaptativa, determinados movimentos são definidos como

proibidos (ou tabus).

Ao rever a funcionalidade desse método Glover (1997) diz que a Busca Tabu

consiste num procedimento adaptativo que guia um algoritmo de busca local na

exploração contínua