O PROBLEMA DO CAIXEIRO VIAJANTE

1. INTRODUÇÃO

Na atualidade percebemos que cada vez mais os conceitos e métodos de otimização de processos estão ligados e incorporados nos sistemas de produção e dentro dos processos produtivos. A lógica computacional algorítmica nos dá suporte e embasamento na solução de problemas que parece não ter saída, nos dando uma solução otimizada, ou seja, a melhor maneira que determinado pode ser resolvido evitando custos e desperdícios. A escolha de um método depende muito do tipo de problema em questão, tais conceitos se relacionam à computação, mais especificamente à linguagem algorítmica.

O algoritmo é um conjunto de passos ou etapas que interagem entre si através de uma sequência lógica, tendo como foco a resolução de algum problema. Dentro dessa linguagem, temos o conceito de heurística que é um método que direciona a solução de um problema, entretanto esse método quando usado sozinho não garante uma solução otimizada do problema. As heurísticas nada mais são do que premissas que dão suporte e base para a meta-heurística que utiliza alterações e modificações dentro da heurística que podem ser aplicadas para resolver algum tipo de problema que muitas das vezes está ligado à otimização de processos.

2. HEURÍSTICAS E META-HEURÍSTICA

Tendo por embasamento os estudos de FOULDS (1984), temos que heurística descreve um método, que baseado na experiência ou julgamento, parece conduzir a uma boa solução de um problema, mas não garante produzir uma solução ótima, no caso, um conhecimento circunstancial e não verificável. Já para descrever a meta-heurística, recorremos aos estudos de BECCENERI (2008), no qual utilizando por base conceitos computacionais, tem-se que meta-heurística como um conjunto de conceitos que podem ser utilizados para diferenciar os métodos heurísticos, os quais podem ser utilizados a um determinado conjunto de problemas, ou seja, pode ser aplicada a diferentes problemas relacionados a otimização, com alterações consideravelmente pequenas para torna-lo adaptável a um problema específico.

Tais conceitos se relacionam à computação, mais em específico, a linguagem algorítmica, devido fato de o algoritmo ser um conjunto de etapas, relacionadas por uma sentença lógica, para a resolução de determinado problemas. Heurísticas são premissas que, selecionadas e modificadas pela meta-heurística, podem ser aplicadas para um problema específico, normalmente relacionado a otimização de processos. É comum ouvir-se o termo “heurística gulosa”, essa em específico, busca otimização a cada interação de processos, reduzindo o custo total naquele momento e tornando o processo mais rápido e eficiente.

Uma forma de classificação da meta-heurísticas, seria através de características como, se são inspiradas ou não na natureza, também chamada de bio-inspirada, pois é quando suas regras tentam simular alguns aspectos dos problemas dos seres vivos. Outra classificação seria se são baseadas em populações ou baseadas em pontos simples, baseada em populações seria o fato de partirem de um conjunto inicial, considerada população inicial e tentam encontrar soluções alterando elementos dessa população, já a baseada em pontos simples, partem de um conjunto solução vazio em que se segue acrescentando elementos até se obter uma solução razoável.

Agora baseado em estudos de VIEIRA (2013), podemos citar alguns tipos de heurísticas conhecidas, tendo por base o problema logístico de roteamento de veículos:

Heurísticas de construção se enquadram em baseadas em pontos simples, são:

• Economias: tem por finalidade conectar rotas viáveis, de modo a se formar uma única rota, a escolha das duas rotas é de modo que resulte em uma rota com menor custos;

• Varredura: em relação ao roteamento de veículos, temos que esta heurística trata da capacidade de carga de cada veículo e da distância máxima a ser percorrida em cada rota, no casa, levando em consideração o posicionamento de cada cliente em relação ao ponto referencial de abastecimento de caminhão;

• Vizinho mais próximo: nesta a casa entrega feita, a mais próxima seria adicionada a rota, caso não pudesse ser efetuado a entrega para a mais próxima, uma nova rota seria iniciada;

• Inserção mais barata: uma solução de forma sequencial, adotando como critério o menor custo para a seleção dos clientes;

Heurísticas de refinamento, no caso, as que são baseadas em uma população inicial, e destas vão alterando características para melhor atender aos problemas, são elas:

• K-opt: consiste em remover k arestas da rota e selecionar outras k novas arestas dentre as possíveis, a fim de formar um novo circuito de custo menor;

• Or-pt: consiste em escolher aleatoriamente três vértices consecutivos, extraí-los da rota, e então reinseri-los no percurso restante, de modo que fique mais viável e com uma solução melhor;

• 2-opt: consiste na retirada de duas retas da rota e depois reinseri-las em duas rotas diferentes conectando-as, mantendo a viabilidade e preservando a orientação;

• Cadeias de ejeção: estrutura é formada de modo que uma estrutura de flor seja formada, no caso a rota não terá mais de duas ligações com o depósito, no caso, somente saída e chegada.

Estas são algumas dentre muitas heurísticas que podem ser aplicadas a esse modelo-base de problema.

3. GRASP

Para fins de solução do Problema do Caixeiro Viajante, utilizou-se o GRASP (Greedy Randomized Adaptive Search Procedures), que é uma metaheurística constituída por heurísticas construtivas e busca local. Consiste de múltiplas aplicações de busca local, cada uma iniciando de uma solução diferente, as soluções iniciais são geradas por algum tipo de construção randômica gulosa.

Nota-se que há duas fases: a construção de uma solução e a aplicação de uma busca local pela melhor solução nesta primeira etapa.

Além disso, o algoritmo armazena a melhor ou as melhores soluções encontradas. Essa memória com as melhores soluções pode ser utilizada para encontrar outras soluções utilizando outras metaheurísticas. A seguir, o algoritmo GRASP em pseudocódigo é apresentado.

Enquanto “critério de parada não for satisfeito” faça

s <- ConstruçãoSolução ( );

s’ <- BuscaLocal (s);