Thober Coradi Detofeno Msc. – “Otimização das Rotas de Coleta de Resíduos Urbanos, utilizando Técnicas de Pesquisa Operacional”

Na noite de ontem recebemos o Sr. Thober Coradi Detofeno, que apresentou seu trabalho “Otimização das Rotas de Coleta de Resíduos Urbanos, utilizando Técnicas de Pesquisa Operacional”. A apresentação se deu de forma clara e objetiva, ressaltando as técnicas da pesquisa operacional.

Palestra Sociesc

Palestra Thober Detofeno - Turma EGP Sociesc

O trabalho apresenta uma metodologia para a obtenção de uma solução otimizada do problema de geração de rotas na coleta de resíduos urbanos. Este problema se caracteriza como sendo de cobertura de arcos e, para o seu desenvolvimento, foi utilizada uma combinação de técnicas da área de Pesquisa Operacional. Entre elas, está a utilização da heurística de Teitz e Bart para a obtenção das p-medianas necessárias para o problema. A
partir da definição das p-medianas determina-se os grupos (clusters) de pontos a serem designados a cada mediana através do algoritmo de Gillett e Jonhson adaptado. Já o algoritmo do carteiro chinês foi utilizado para se obter, a partir da definição dos grupos, o roteamento em cada um dos grupos de atendimento. São apresentados os resultados obtidos para um estudo de caso, utilizando dados reais.

Conforme a apresentação, “O trabalho apresenta uma metodologia para a obtenção de uma solução otimizada do problema de geração de rotas na coleta de resíduos urbanos. Este problema se caracteriza como sendo de cobertura de arcos e, para o seu desenvolvimento, foi utilizada uma combinação de técnicas da área de Pesquisa Operacional. Entre elas, está a utilização da heurística de Teitz e Bart para a obtenção das p-medianas necessárias para o problema. A partir da definição das p-medianas determina-se os grupos (clusters) de pontos a serem designados a cada mediana através do algoritmo de Gillett e Jonhson adaptado. Já o algoritmo do carteiro chinês foi utilizado para se obter, a partir da definição dos grupos, o roteamento em cada um dos grupos de atendimento. São apresentados os resultados obtidos para um estudo de caso, utilizando dados reais.”

Clique no link abaixo para baixar o trabalho mais detalhado, conforme apresentação

ThoberDetofeno

Definições:

Heurística:

As pesquisas por heurísticas é uma pesquisa realizada por meio da quantificação de proximidade a um determinado objectivo. Diz-se que se tem uma boa (ou alta) heurística se o objecto de avaliação está muito próximo do objectivo; diz-se de  (ou baixa) heurística se o objecto avaliado estiver muito longe do objectivo. Etimologicamente a palavra heurística vem da palavra grega Heuriskein, que significa descobrir (e que deu origem também ao termo Eureca).

Um algoritmo aproximativo (ou algoritmo de aproximação) é heurístico, ou seja, utiliza informação e intuição a respeito da instância do problema e da sua estrutura para resolvê-lo de forma rápida.

Entretanto, nem todo algoritmo heurístico é aproximativo, ou seja, nem toda heurística tem uma razão de qualidade comprovada matematicamente ou prova formal de convergência. Por este motivo, em várias referências bibliográficas distingue-se os termos algoritmo aproximativo e heurística:

  • aproximativo é a denominação do algoritmo que fornece soluções dentro de um limite de qualidade absoluto ou assintótico, assim como um limite assintótico polinomial de complexidade (pior caso) comprovado matematicamente;
  • heurísticamétodo heurístico são denominações para o algoritmo que fornece soluções sem um limite formal de qualidade, tipicamente avaliado empiricamente em termos de complexidade (média) e qualidade das soluções.

A heurística é um conjunto de regras e métodos que conduzem à descoberta, à invenção e à resolução de problemas. Também é uma ciencia auxiliar da História que estuda a pesquisa das fontes. (fonte: Wikipedia, 2009)

p-medianas:

Mediana ou centróide de um grafo G(V, E) é um vértice para o qual a soma das distâncias aos demais vértices é mínima. Existem problemas que tem como solução uma única mediana (um único vértice), chamada de 1-mediana, que será abordada nesta seção. Porém, há casos em que existem mais de uma mediana como solução, chamados de 2 – mediana, 3 – mediana, ou p – mediana de um modo geral. (fonte: Site da Universidade Estadual do Oeste do Paraná,2009 http://www.unioeste.br)

Algoritmo do Carteiro Chinês:

Técnica utilizada para encontrar o circuito ou ciclo de menor comprimento que “cubra”cada arco ao menos uma vez. (Fonte: Universia,2009 http://www.universia.com.br)

por André Amante Postado em Textos

2 comentários em “Thober Coradi Detofeno Msc. – “Otimização das Rotas de Coleta de Resíduos Urbanos, utilizando Técnicas de Pesquisa Operacional”

Deixe seu comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s