Baixar Slides
Transcrição
Baixar Slides
UMA ABORDAGEM COMPUTACIONAL PARA UMA NOVA VARIANTE DO PROBLEMA DO CARTEIRO CHINÊS RURAL Diego Luchi SUMÁRIO Introdução Motivação Objetivos INTRODUÇÃO Métodos de otimização Fermat (Ponto crítico/estácionário); Gauss (Método dos mínimos quadrados); Método de Newton. INTRODUÇÃO Programação linear Simplex (George Dantzig, 1947); Ponto interior (Narendra Karmarkar, 1984). INTRODUÇÃO Programação linear Simplex (George Dantzig, 1947); Ponto interior (Narendra Karmarkar, 1984). Programação inteira Branch-and-Bound (cut | price); Método de Balas. INTRODUÇÃO Sete pontes de Königsberg INTRODUÇÃO Sete pontes de Königsberg INTRODUÇÃO Problema do carteiro chinês (Kwan, 1962) Algoritmo polinomial (Edmonds, 1965); Baixa aplicabilidade. INTRODUÇÃO Problema do carteiro chinês (Kwan, 1962) Algoritmo polinomial (Edmonds, 1965); Baixa aplicabilidade. Problema do carteiro chinês rural (Orloff, 1974) Caso geral carteiro chinês; Maior aplicabilidade (cartas, onibus, etc…); NP-Completo (Orloff, 1976). INTRODUÇÃO Muitas aplicações não podem ser modelados pelas formulações canônicas (Eiselt et al., 1995b). MOTIVAÇÃO Roteamento de leituristas de consumo de energia elétrica. MOTIVAÇÃO Considerações: Pode determinar ponto de inicial e final do percurso; Restrição custo máximo da rota; M leituristas para cobrir as arestas; Rotas em zig-zags; Etc. MOTIVAÇÃO Considerações: Pode determinar ponto de inicial e final do percurso; Restrição custo máximo da rota; M leituristas para cobrir as arestas; Rotas em zig-zags; Etc. Problema similar descrito por (Stern, 1979). MOTIVAÇÃO “This chapter is concerned with the generalized directed rural postman problem (GDRPP). This problem has not yet been described in the literature, i.e., there are neither formulations nor heuristic or exact solution procedures, but, as its name implies, the problem is a straightforward generalization of the directed rural postman problem (DRPP).” (Drexl, 2007). MOTIVAÇÃO “The main advantage of the GDRPP model is its genericity. It constitutes a unified model for many types of uncapacitated routing problem and is therefore able to serve as a flexible framework for representing and solving practical problems.” (Drexl, 2007). MOTIVAÇÃO Custos das arestas Diversas variáveis constituem o custo dos arcos; Dificuldade de estimar quais variáveis; Dificuldade de estimar o quanto cada variável impacta no custo. MOTIVAÇÃO Custos das arestas Diversas variáveis constituem o custo dos arcos; Dificuldade de estimar quais variáveis; Dificuldade de estimar o quanto cada variável impacta no custo. Aprendizado não supervisionado OBJETIVOS Formulação de uma versão com maior grau de liberdade para problemas de roteamento. OBJETIVOS Formulação de uma versão com maior grau de liberdade para problemas de roteamento. Desenvolver métodos heurísticos para resolução do problema. OBJETIVOS Formulação de uma versão com maior grau de liberdade para problemas de roteamento. Desenvolver métodos heurísticos para resolução do problema. Método para o ajuste dos custos das arestas utilizando métodos de aprendizagem de máquina. OBJETIVOS Comparar os métodos existentes aplicados a problemas mais específicos com o método desenvolvido. Aplicar no problema de roteamento de leituristas da EDP. FIM