Roteirizao de veculosBruno de Athayde Prata

Setembro de 2011

Estrutura da apresentao Introduo; Problema do caminho mais curto; Problema do Carteiro Chins; Problema do Caixeiro Viajante; Problema de Roteamento de Veculos; Concluses; Referncias bibliogrficas.

IntroduoUm estudo de roteirizao consiste no estabelecimento de itinerrios para o atendimento de clientes.

Deciso operacional. Processo complexo, devido aos diversos critrios envolvidos e ao elevado nmero de combinaes. Problema de deciso com forte componente geogrfica.

IntroduoTaxonomia dos problemas de roteirizao: localizao da demanda (vrtices/arestas); origens/destinos; restrio de capacidade; coleta/entrega; janela de tempo.

IntroduoProblemas clssicos: Problema do caminho mais curto Problema do Carteiro Chins Problema do Caixeiro Viajante Problema de Roteamento de Veculos

IntroduoAplicaes: distribuio de mercadorias; coleta de embalagens/resduos; transporte escolar rural; mquinas de terraplenagem; Logstica de atendimento emergencial (ambulncias, viaturas, etc.).

Problema do caminho mais curto

Shortest Path Problem (SPP) Definio do problema clssico:

Uma origem e um destino; Demanda em um dos vrtices; Capacidade do veculo suficiente para atender a demanda.

Obter o percurso de menor custo entre um par origem-destino. Exemplos: caminho betoneira, ambulncia.

Problema do caminho mais curto

Shortest Path Problem (SPP)

Problema do caminho mais curto

Problema do caminho mais curto

Problema fcil! Os algoritmos de Dijkstra e Floyd garantem a obteno da soluo tima em tempo polinomial.

Dijkstra: caminho mais curto entre um par de ns. Floyd: caminho mais curto entre qualquer par de vrtices.

Problema do caminho mais curto

As solues obtidas por sistemas tipo SIG certamente so solues timas. O uso do modelo matemtico (mtodo exato) no se mostra justificado. Variantes mais complexas, advindas de problemas reais, podem exigir novos mtodos.

Problema do Carteiro Chins

Chinese Postman Problem (CPP) Definio do problema clssico:

Uma origem e mltiplos destinos; Demanda nas arestas; Capacidade do veculo suficiente para atender a demanda.

Obter o ciclo euleriano de menor custo em um grafo. Exemplos: entrega de gs, coleta de lixo.

Problema do Carteiro Chins

Problema do Caixeiro Viajante

Traveling Salesman Problem (TSP) Definio do problema clssico:

Uma origem e mltiplos destinos; Demanda nos vrtices; Capacidade do veculo suficiente para atender a demanda.

Obter o ciclo hamiltoniano de menor custo em um grafo. Exemplos: entrega de jornais, entrega postal.

Problema do Caixeiro Viajante

Traveling Salesman Problem (TSP)

Problema do Caixeiro Viajante

Traveling Salesman Problem (TSP) Exploso combinatria:

Problema do Caixeiro Viajante

Traveling Salesman Problem (TSP) Casos importantes:

Simtrico: tranporte de longo curso; Assimtrico: transporte de carga urbana.

O caso simtrico mais simples de resolver, pois: (i) o nmero de solues possveis se reduz metade; e (ii) utiliza-se menos memria.

Problema do Caixeiro Viajante

Traveling Salesman Problem (TSP) Exemplos de heursticas:

Vizinho mais prximo; Insero mais distante.

Mtodos de melhoria das solues. Estratgias first improvement e best improvement.

Problema do Caixeiro Viajante

ponto 1 2 3 4 5 6 x -2 10 -6 4 0 8

Exemplo:y 3 -14 7 5 -11 7

10

5

0 -8 -6 -4 -2 0 2 4 6 8 10 12

-5

Matriz de distncias1 2 3 4 5 6 1 -1 20,8 5,7 6,3 14,1 10,8 2 20,8 -1 26,4 19,9 10,4 21,1 3 5,7 26,4 -1 10,2 19 14 4 6,3 19,9 10,2 -1 16,5 4,5 5 14,1 10,4 19 16,5 -1 19,7 6 10,8 21,1 14 4,5 19,7 -1

-10

-15

-20

Representao grfica dos pontos

Problema de Roteamento de veculos

Vehicle Routing Problem (VRP) Definio do problema clssico:

Uma origem e mltiplos destinos; Demanda nos vrtices; Capacidade do veculo insuficiente para atender a demanda, sendo requeridos mltiplos veculos.

Exemplos: distribuio de bebidas, transporte escolar. Combinao do TSP com o problema de empacotamento.

Problema de Roteamento de veculos

Vehicle Routing Problem (VRP)

Problema de Roteamento de veculos

Vehicle Routing Problem (VRP) Casos importantes:

Vehicle Routing Problem with Time Windows (VRPTW); Vehicle Routing Problem with Simultaneous Delivery and Pick-up Points (VRPSDP); Location and Routing Problem (LRP).

Problema de Roteamento de veculos

Vehicle Routing Problem (VRP) Heursticas:

Gillet & Miller; Clarke & Wright.

Mtodos de melhoria das solues. Estratgias first improvement e best improvement.

Problema de Roteamento de veculos

ponto 1 2 3 4 5 6 7 8 9 10 CD

Exemplo:x -3 8 -14 -12 4 1 10 12 -5 -3 1 y -4 4 -3 8 2 9 8 14 -7 3 1 demanda 6 4 9 7 3 4 12 5 6 4 -

Concluses Importncia dos problemas de roteirizao. Compreender a complexidade dos problemas. Nem sempre se deve confiar nos softwares comerciais. A necessidade de meta-heursticas. Variantes reais incorrem em diversas oportunidades de investigao.

Bibliografia consultadaGOLDBARG, M. C.; LUNA, H. P. L. Otimizao combinatria e programao linear modelos e algoritmos. Rio de Janeiro: Elsevier, 2005. NOVAES, A. R. Sistemas logsticos: transporte, armazenagem e distribuio fsica de produtos. So Paulo: Edgard Blcher, 1989. NOVAES, A. R. Logstica e gerenciamento da cadeia de distribuio. Rio de Janeiro: Elsevier/Campus, 2007. VIANA, V. Meta-heursticas e programao paralela em otimizao combinatria. Fortaleza: Edies UFC, 1998.

Obrigado pela ateno!baprata@ufc.br baprata.blogspot.com