Uma abordagem heurística para o problema de otimização de distrito postal

AUTOR(ES)

Rafael Carpanedo Fiório

DATA DE PUBLICAÇÃO

2006

RESUMO

Neste trabalho é proposta uma estratégia de solução para a construção otimizada de distritos postais. Distrito Postal consiste num conjunto de segmento de eixo de logradouros conectados. Dada uma localidade formada por inúmeros segmentos de logradouros, esse trabalho propõe o arranjamento de subgrupos conexos de segmentos de eixos de logradouros de modo a compor um distrito postal. A estratégia é transformar o sistema de logradouros de uma localidade em um grafo. A partir desse grafo, extrair seus respectivos subgrafos cíclicos que são entendidos como entidades atômicas. Essas entidades atômicas passam por um processo de montagem até comporem um conjunto de distritos postais. A metodologia aqui apresentada divide o trabalho em duas fases distintas: a primeira compreende o processo de obtenção dos subgrafos cíclicos; e a segunda compreende o processo de montagem de distrito postal. O processo de obtenção de subgrafos cíclicos consiste na obtenção da envoltória convexa do grafo e posterior extração dos subgrafos cíclicos tangentes às arestas dessa. Isso de forma sequencial, ou seja, determina-se a primeira envoltória convexa do grafo e extraemse seus respectivos subgrafos tangentes; determina-se a segunda envoltória convexa e extraem-se seus subgrafos, e assim sucessivamente. O trabalho de determinação da envoltória convexa e de extração dos subgrafos cíclicos é feito através de operações da geometria computacional. O processo de construção dos distritos postais se dá através da clusterização dos subgrafos cíclicos, usando como ferramenta a meta-heurística Simulated Annealing. O problema do Carteiro Chinês e Carteiro Chinês Capacitado são formulações suporte para o presente trabalho. O objetivo principal do trabalho é obter, de forma rápida e eficiente o distrito postal otimizado, com menor percurso improdutivo possível, oferecendo agilidade no processo de distribuição domiciliária de objetos postais.

ASSUNTO(S)

teoria dos grafos engenharia de software simulated annealing (mathematics) otimização combinatória convex hull envoltória convexa postal district serviço postal simulated annealing (matemática)

Documentos Relacionados

• Uma abordagem heurística construtiva para o problema de minimização de pilhas abertas.
• UMA ABORDAGEM HEURÍSTICA PARA O PROBLEMA DE PLANEJAMENTO DA PRODUÇÃO EM FUNDIÇÕES ESTUDO DE CASO
• Uma nova heurística para o problema de minimização de trocas de ferramentas
• Uma abordagem heurística para minimizar o tempo de preparação de uma máquina tubeteira
• Uma heurística de trocas para o problema de sequenciamento de tarefas em processadores uniformes