Optimização da Diversidade e
Distribuição de Cablagens para a
Indústria Automóvel
Agostinho Agra (Universidade de Aveiro)
Domingos Cardoso (Universidade de Aveiro)
Jorge Orestes Cerdeira (Universidade Técnica de Lisboa)
Miguel Miranda (Yazaki)
Eugénio Rocha (Universidade de Aveiro)
Outline
Descrição do problema
Modelação do problema
O problema anterior ao problema
Técnicas de optimização implementadas
Experiência computacional
Descrição do problema
Descrição do problema
Opções:
airbags
ar condicionado
auto-rádio
sensores de estacionamento
sensores de chuva
......
Descrição do problema
 Há um conjunto de “módulos obrigatórios”
(volante do lado direito ou do lado esquerdo, caixa
de velocidades manual ou automática)
...
 Há o conjunto de “módulos opcionais”
Descrição do problema
1 opção = 1 ligação física (fio de cobre)
Cada cliente escolhe um conjunto de opções
que designamos por configuração
Há restrições técnicas que impedem a
ocorrência de certas opções em simultâneo ou
que obrigam a que certas opções só possam ser
seleccionadas simultaneamente.
Descrição do problema
O número de configurações possíveis (e mesmo o número
de configurações que ocorrem na prática) é elevado
Nº de opções
10
20
30
40
Nº de configurações
1.000
1.000.000
1.000.000.000
1.000.000.000.000
Descrição do problema
Existe um limite máximo no número de
configurações distintas que é possível produzir
Em geral os cabos são produzidos com mais
configurações do que as necessárias
Globalmente, essas ligações físicas que não são
necessárias representam um elevado custo para a
indústria automóvel
Descrição do problema
O problema da Diversidade e Distribuição de
Cablagens consiste em determinar, face aos
pedidos dos clientes (ou previsão desses pedidos),
quais as configurações de cablagem que devem ser
produzidas e, para cada configuração pedida, qual
a configuração a entregar de modo a minimizar o
custo global associado às ligações desnecessárias
Modelação do problema
O problema pode ser modelado como um problema
da p-mediana onde:
 p representa o número máximo de configurações
distintas que é possível produzir
 Cada nodo do grafo representa uma configuração
distinta
Modelação do problema
 Existe um arco do nodo i para o nodo j se a configuração i
inclui todas as opções da configuração j.
 O custo associado a cada arco é dado pela soma do custo
de cada fio de cobre que está na configuração i e não está
na j vezes a procura da configuração j.
Modelação do problema
(1,1,1)
(1,1,0)
(1,0,0)
(1,0,1)
(0,1,0)
(0,1,1)
(0,0,1)
(0,0,0)
Modelação do problema
Custo do arco (1,1,1) - (0,1,0)
= (custo das opções 1 e 3)* procura da configuração (0,1,0)
(1,1,1)
(0,1,0)
Modelação do problema
Solução com p=2
(1,1,1)
(1,1,0)
(1,0,0)
(1,0,1)
(0,1,0)
(0,1,1)
(0,0,1)
(0,0,0)
Modelação do problema
Referências:
 Briant, O. And Naddef, D. “The optimal Diversity
Management Problem”, Operations Research, 2004
 Olivier Briant, “Étude théoric et numérique du problème de la
gestion de la diversité”, (Institut d’Informatique et de
Mathemétiques Appliquées de Grenoble, 2000
NP-díficil (J. Orestes Cerdeira)
O problema anterior ao problema
Quando a procura não é conhecida como estimá-la?
Nesse caso, como gerar de forma eficiente uma
representação do grafo (matriz de adjacência)
preservando a ordem parcial dos nodos e
aplicando restrições às técnicas que eliminam
certas configurações?
Técnicas de Optimização
implementadas
Particularidades:
Em geral, p não é superior a 60
O número de componentes conexas é elevado
(superior a 20)
É desejável ter estimativas de custos para vários
valores de p
Técnicas de Optimização
implementadas
k = nº de componentes conexas do grafo (diversidade
mínima)
p = nº máximo de configurações a produzir
N= conjunto das configurações (nodos do grafo)
1ª Solução: Usar um algoritmo greedy:
Técnicas de Optimização
implementadas
Algoritmo greedy:
Inicialização: considerar a solução S com k configurações
(inclui, para cada componente, a única configuração que
contém todas as opções nessa componente)
Passo iteractivo: Para i=k+1 até p
(i) Seleccionar de entre as configurações em N\S
aquela que maximiza a poupança resultante da
sua inclusão em S
(ii) Incluir essa configuração em S
Técnicas de Optimização
implementadas
2ª Solução: Decompor o problema em duas fases:
Fase 1: para cada componente calcular, usando o
algoritmo Greedy, o custo da solução com 1,2
até p-k+1 medianas
Fase 2: Escolher a melhor combinação de pmedianas (algoritmo genético)
Técnicas de Optimização
implementadas
Exemplo: k=3 e p=6
Componente 1
Componente 2
Componente 3
1 configuração
C11
C12
C13
2 configurações
C21
C22
C23
3 configurações
C31
C32
C33
4 configurações
C41
C42
C43
Técnicas de Optimização
implementadas
Exemplo: k=3 e p=6
Componente 1
Componente 2
Componente 3
1 configuração
20
30
25
2 configurações
18
21
18
3 configurações
11
17
15
4 configurações
10
15
13
Experiência computacional
(com base em dados reais)
Greedy
2 fases
# nodos
K
min
K
max
# carros
tempo
(seg.)
% give
away
tempo
(seg.)
% give
away
166
33
65
38.910
5
0,68
2
0,68
239
24
60
38.910
5,5
1,72
3
1,72
317
47
65
38.733
3
1,32
1
1,32
584
16
20
30.500
3
1
1
1
Experiência computacional
(com base em previsões)
Greedy
2 fases
% give tempo
away (horas)
% give
away
# nodos
K
min
K
max
# carros
tempo
(horas)
2.354.688
16
150
1.844.000
234
14,28
80
14,28
1.118.208
14
150
1.800.000
57
13,07
21
13.07
829.440
6
150
1.800.000
96
10,62
38
10,62
393.216
16
60
1.800.000
1
5,17
0,5
5,17