Algoritmos para problemas de roteamento de veículos com entrega e coleta

´ IVAN XAVIER ARAUJO DE LIMA

Algoritmos para problemas de roteamento de veículos com entrega e coleta

´ NITEROI 2009

´ IVAN XAVIER ARAUJO DE LIMA

Algoritmos para problemas de roteamento de veículos com entrega e coleta
Disserta¸ao de Mestrado submetida ao Proc˜ grama de P´s-Gradua¸ao em Computa¸˜o da o c˜ ca Universidade Federal Fluminense como requisito parcial para a obten¸˜o do t´ ca ıtulo de ´ Mestre. Area de concentra¸ao: Otimiza¸ao c˜ c˜ Combinat´ria e Inteligˆncia Artificial. o e

Orientador:

Prof. Luiz Satoru Ochi, D. Sc.
Co-orientador:

Prof. Eduardo Uchoa Barboza, D. Sc.

Universidade Federal Fluminense

´ NITEROI 2009

Algoritmos para problemas de roteamento de ve´ ıculos com entrega e coleta Ivan Xavier Ara´jo de Lima u

Disserta¸ao de Mestrado submetida ao Proc˜ grama de P´s-Gradua¸ao em Computa¸˜o da o c˜ ca Universidade Federal Fluminense como requisito parcial para a obten¸˜o do t´ ca ıtulo de ´ Mestre. Area de concentra¸ao: Otimiza¸ao c˜ c˜ Combinat´ria e Inteligˆncia Artificial. o e

Aprovada por:

Prof. Luiz Satoru Ochi, D.Sc. / IC-UFF (Presidente)

Prof. Eduardo Uchoa Barboza, D.Sc. / TEP-UFF

Profa. Adriana C. F. Alvim, D.Sc. / DIA-UNIRIO

Prof. Artur Alves Pessoa, D.Sc. / TEP-UFF

Prof. Marcus V. S. Poggi de Arag˜o, D.Sc. / DI-PUC-Rio a

Niter´i, 17 de Abril de 2009. o

´ ´ “...E melhor tentar e falhar, que preocupar-se e ver a vida passar. E melhor tentar, ainda em v˜o, que sentar-se fazendo nada at´ o final.” a e Martin Luther King

Dedico esse trabalho a Deus. A minha esposa, meus familiares, ao Uchoa e demais amigos, por todo apoio, amor e carinho.

Agradecimentos

Acima de tudo agrade¸o a Deus que conhece o futuro desde o presente, pois toda a c sabedoria do mundo pertence a Ele, e tamb´m, por ter me enviado as pessoas certas para e poder ajudar nessa grande batalha. Um agradecimento super especial ` minha esposa Danielly quem com muito amor a me incentiva e concede for¸as me lembrando