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