Abordagem no problema de roteamento

i

Abordagens para Problemas de Roteamento
Marco Alves Ganhoto
Trabalho Final de Mestrado Profissional

ii

Instituto de Computação
Universidade Estadual de Campinas

ABORDAGENS PARA
PROBLEMAS DE ROTEAMENTO

Marco Alves Ganhoto dezembro de 2004

Banca Examinadora:
•

Prof. Dr. Flávio Keidi Miyazawa
Instituto de Computação, UNICAMP (Orientador)

•

Prof. Dr. Carlos Eduardo Ferreira
Instituto de Matemática e Estatística, USP

•

Prof. Dr. Orlando Lee
Instituto de Computação, UNICAMP

•

Prof. Dr. Ricardo Dahab
Instituto de Computação, UNICAMP (Suplente)

iii

FICHA CATALOGRÁFICA ELABORADA PELA
BIBLIOTECA DO IMECC DA UNICAMP

Ganhoto, Marco Alves
G155a

Abordagens para problemas de roteamento / Marco Alves Ganhoto
-- Campinas, [S.P. :s.n.], 2004.
Orientador : Flávio Keidi Miyazawa
Trabalho final (mestrado profissional) - Universidade Estadual de
Campinas, Instituto de Computação.
1. Otimização combinatória. 2. Heurística. 3. Algoritmos. 4.
Pesquisa operacional. I. Miyazawa, Flávio Keidi. II. Universidade
Estadual de Campinas. Instituto de Computação. III. Título.

iv

Abordagens para Problemas de Roteamento

Este exemplar corresponde à redação final do
Trabalho Final devidamente corrigida e defendida por Marco Alves Ganhoto e aprovada pela Banca
Examinadora.

Campinas, 15 de dezembro de 2004.

Prof. Dr. Flávio Keidi Miyazawa
Instituto de Computação, UNICAMP (Orientador)

Trabalho

Final

apresentado

ao

Instituto

de

Computação, UNICAMP, como requisito parcial para a obtenção do título de Mestre em Computação na Área de Engenharia de Software.

v

vi

© Marco Alves Ganhoto, 2004.
Todos os direitos reservados.

vii

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