Caixeiro viajante

Disponível somente no TrabalhosFeitos
  • Páginas : 37 (9082 palavras )
  • Download(s) : 0
  • Publicado : 26 de outubro de 2012
Ler documento completo
Amostra do texto
Universidade Federal de Minas Gerais

Trabalho – Heurísticas e MetaHeurísticas

Caixeiro Viajante
Por:
Michael David de Souza Dutra
Curso: Engenharia de Produção

Matrícula: 2009020019

Professor:
Thiago Ferreira de Noronha
Departamento da Ciência da Computação

Belo Horizonte, junho de 2012.

PARTE I – DADOS DE IDENTIFICAÇÃO

Resumo

1

O presente trabalho propõe umaheurística para a resolução do problema
Caixeiro Viajante (Travelling Salesman Problem – TSP). A investigação é constituída
na resolução de um problema de otimização da união de todos os vértices de um grafo
dado que não se pode visitar um vértice duas vezes e ao final do percurso é necessário
estar no mesmo vértice que se iniciou o percurso, objetivando minimizar os custos. Este
trabalhocontribui com o desenvolvimento de heurísticas e metaheurísticas para TSP.
Para tanto, o plano de trabalho constitui-se de dois estudos articulados. O Estudo I teve
como objetivo fazer um estudo bibliográfico e apresentação sucinta do problema. O
Estudo II pretende demonstrar a heurística desenvolvida neste trabalho, bem como
resultados de experimentos computacionais.

Equipe
Coordenador
ThiagoFerreira de Noronha
Aluno
Michael David de Souza Dutra
Local de Execução do Projeto
Av. Antônio Carlos, 6627 - Pampulha - Belo Horizonte
Departamento de Engenharia de Produção – DEP
Departamento de Ciência da Computação – DCC
CEP 31270-901 - Fone: +55 (31) 3409.5000
Palavras-chave
Otimização, Programação em Redes, Caixeiro Viajante

2

2

PARTE I – INTRODUÇÃO

A origem destetrabalho se fixa na tentativa de resolução do seguinte problema:
há na cidade de Barbacena uma indústria processadora de carne de frango detentora
de aproximadamente 95 contratos de integração, ou seja, que têm relações de consumo
com cerca de 95 granjas de frangos. Diariamente é necessário levar suprimentos para
todas as granjas. Tal indústria só dispõe de um veículo para tal tarefa que deve sairda
indústria pela manhã e retornar a mesma no final do dia minimizando a distância
percorrida. Este problema é, de certa forma, um problema de Caixeiro Viajante
(Travelling Salesman Problem – TSP).
Segundo Lombardo (1986), o TSP é estudado desde o início da década de 30.
Observa-se atualmente que há, ainda, espaço na academia para o desenvolvimento do
tema dada sua importância na conjecturaatual. Tal importância, segundo Morais (2010),
reside no fato de que outros problemas de otimização combinatória, tais como
roteamento de veículos, sequenciamento cíclico de tarefas em máquinas, etc., têm, de
certa forma, estreita ligação com o TSP.
O TSP, no contexto real deste trabalho, se caracteriza por, dado um conjunto de
n-1 granjas e 1 frigorífico e uma matriz de distâncias D[1..n,2..n, ..., n..n], fazer com
que seja encontrado um caminho que, partindo do frigorífico, tenha a menor distância a
ser percorrida para que sejam visitadas todas as granjas passando exatamente uma única
vez em cada uma e retornando ao frigorífico. Em termos matemáticos, o problema
consiste numa rede representada por um grafo conexo G = (N,A), onde N é o conjunto
de nós e A é o conjunto de arestasentre os nós. Em cada aresta, há um custo C ij que se
refere à ligação do vértice i ao vértice j pela aresta (i,j). O problema consiste então
determinar o grafo parcial conexo de custo mínimo respeitando a restrição de grau = 2
para todo nó, ou seja, formando uma rota hamiltoniana.
A formulação matemática para o TSP é dada pela seguinte função objetivo,
definida no Quadro 1, e sujeita asrestrições que se seguem:

Quadro 1: Formulação Matemática do TSP.

3

A variável xij = 1 representa que a cidade j é imediatamente posterior à cidade i
na rota. Caso contrário, xij = 0. O parâmetro n representa o número de nós do problema.
S é um subconjunto do conjunto {1,2,....,n} e o símbolo “| |” representa a cardinalidade
do conjunto. Mais especificadamente pode-se dizer que S ⊆ N...
tracking img