Caixeiro viajante

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 uma heurí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 trabalho contribui 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
Thiago Ferreira 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 deste trabalho 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 sair