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

Disponível somente no TrabalhosFeitos
  • Páginas : 116 (28794 palavras )
  • Download(s) : 0
  • Publicado : 15 de novembro de 2011
Ler documento completo
Amostra do texto
´ 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 dot´ 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 Mestradosubmetida 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 Uchoae 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 lembrandoque: “Tudo posso naquEle que me fortalece” c (Filipenses 4:13). Meus pais e familiares que mesmo distante, nunca estiveram longe de mim. Ao meu orientador Prof. Dr. Satoru por dar-me o voto de confian¸a para a realiza¸ao c c˜ deste trabalho. Ao meu coorientador Prof. Dr. Uchoa o qual com carinho, aten¸˜o e ca dedica¸ao me encaminhou para o rumo certo. c˜ A meus amigos de longo e curto prazo que nodia-a-dia, atrav´s de suas amizades, e foram me moldando e auxiliando, a ser quem eu sou e estar onde estou. N˜o citarei a nomes, mas, a todos do IC, principalmente aos que fizeram mat´ria comigo pois tivemos ` e a oportunidade de nos conhecer melhor e compartilhar experiˆncias, e aos amigos do e trabalho (Automatos e Gapso), pois tornaram agrad´vel esta forma que consegui de me a manter no rio, umgrande abra¸o. c Agrade¸o a Maria e a Angela por serem atenciosas, prestativas e colaboradoras, indo c ` ` ˆ al´m de suas obriga¸˜es para na medida do poss´ facilita nossas vidas. e co ıvel Agrade¸o aos membros da banca (Uchoa, Satoru, Artur Pessoa, Marcus Poggi e Adric ana Alvim) que dedicaram um tempo com certeza escasso a colaborar com este trabalho realizando cr´ ıticas e sugest˜es que vem aenriquece-lo. o

Resumo

Neste trabalho s˜o abordados problemas de roteamento de ve´ a ıculo com coleta e entrega. Dentre eles trabalhou-se, o problema de roteamento de ve´ ıculo com coleta e entrega, especificamente, o Roteamento de Ve´ ıculo com Coleta e Entrega e Janelas de Tempo (VRPPDTW - Vehicle Route Problem Pickup Delivery with Time Windows) e o Problema do Caixeiro Viajante com Coletae Entrega (TSPPD - Traveling Salesman Problem with Pickup and Delivery). O primeiro foi trabalho com uma abordagem heur´ ıstica, busca local interativa com movimento randˆmico de descida (ILS-MRD), e o segundo atrav´s o e por programa¸˜o inteira, com algoritmo de branch-and-cut. ca Palavras-chave: Roteamento de Ve´ ıculo, Caixeiro Viajante, Coleta e Entrega, Janelas de Tempo, Programa¸˜o...
tracking img