Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
ALGORITMO EVOLUCIONÁRIO APLICADO AO PROBLEMA DE DESPACHO DE
CAMINHÕES EM MINAS A CÉU ABERTO
João Batista Mendes∗ , Renato Dourado Maia, Marcos Flávio Silveira Vasconcelos
D’Angelo∗, João Antônio de Vasconcelos†
∗
Universidade Estadual de Montes Claros
UNIMONTES
Montes Claros, MG, Brasil
†
Universidade Federal de Minas Gerais
UFMG
Belo Horizonte, MG, Brasil
Emails: [email protected], [email protected],
[email protected], [email protected]
Abstract— In this paper we presented a multiobjective evolutionary algorithm for applying in the truck
dispatching problem in open pit mining. The proposed algorithm implements a specific routine for generating
initial solution set and a crossover operator adapted for this problem. To validate the algorithm, it is compared
with another version that evolves a random initial solution set. The results showed that the algorithm may
be applied to the presented problem. Also, we formulated a multiobjective model with some specifities for the
proposed problem.
Keywords—
Generating initial solutions, truck dispatching problem, multi-objective evolutionary algorithms.
Resumo— Neste trabalho é descrito um algoritmo evolutionário multiobjetivo para aplicação no problema
de despacho de caminhões em minas a céu aberto. O algoritmo proposto utiliza uma rotina para geração da
população inicial e um operador de cruzamento adaptados para o problema. Para validar o algoritmo, ele foi
comparado com uma versão do algoritmo que evolui a partir de uma população inicial aleatória. Os resultados
mostraram que o algoritmo proposto se aplica ao problema apresentado. Ademais, foi formulado um modelo
multiobjetivo com algumas particularidades para o problema delineado no trabalho.
Palavras-chave— Geração da população inicial, problema de despacho de caminhões em minas a céu aberto,
algoritmos evolucionários multiobjetivos.
1
Introdução
Uma mina a céu aberto, ilustrada na Figura 1, é
um tipo de mina de superfı́cie composta por: um
conjunto de frentes de lavra para extração de material (minério e estéril), uma frota de caminhões
(muitas vezes com capacidades de transporte e velocidade distintas) e equipamentos de carga (com
taxas de produção diferenciadas) (Bastos (2010)).
Os equipamentos de carga (pás carregadeiras e escavadeiras) são alocados nas frentes de lavra para
extração de material que é carregado em caminhões. Os caminhões, por sua vez, transportam
o material para um britador (quando o material
é minério) ou pilha de estéril (quando o material é estéril) onde ele é descarregado. Quando
destinado ao britador, o material é processado e
homogeneizado para atingir propriedades fı́sicoquı́micas desejadas.
Particularmente, a operação de transporte de
material numa mina a céu aberto tem custo elevado, chegando a representar de 50 a 60% do custo
operacional total da mina. Por isso, é importante
alocar e despachar os veı́culos de maneira eficiente
(Ercelebi and Bascetin (2009)).
Em resumo, o problema de despacho de caminhões em minas a céu aberto é um problema NPDifı́cil (Golden et al. (2008)) de escalonamento de
Figura 1: Ilustração de uma mina a céu aberto
com: 02 frentes de minério (F r1 e F r2 ), 01 frente
de estéril (FE ), 01 pilha de estéril (PE ) e 01 britador primário (BR).
tarefas de natureza combinatória no qual o objetivo é identificar um plano de rotas de custo mı́nimo a ser percorrida por uma frota de caminhões
(homogênea ou não). Neste tipo de problema,
geralmente se visa otimizar, por exemplo, produção de material, qualidade do minério produzido,
distância percorrida pelos veı́culos, tempo de fila
dos veı́culos, etc.... Porém, existem diversos fa-
4300
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
tores (por exemplo, relação estéril/minério, qualidade do minério produzido, compatibilidade entre
os equipamentos) que interferem na produção da
mina e que devem ser considerados na resolução
do problema.
Neste trabalho, formulou-se um modelo matemático multiobjetivo para o problema de despacho de caminhões em minas a céu aberto. Além
disso, foi desenvolvido um algoritmo multiobjetivo para resolução do problema que implementa
uma rotina, baseada em busca local, para geração da população inicial. Na comparação com o
mecanismo de geração aleatória da população, o
método proposto apresentou resultados melhores
quando aplicado na resolução do problema delineado no trabalho.
O restante do artigo tem a seguinte organização: Na seção 2, são relacionados diversos trabalhos que estudaram alguns problemas encontrados
no contexto de minas a céu aberto. A seguir, na
seção 3, detalha-se o modelo multiobjetivo formulado para resolução do problema de despacho de
caminhões em minas à céu aberto com alocação
dinâmica de veı́culos. Em 4, faz-se a descrição da
rotina de geração da população inicial proposta
no trabalho. Na seção 5, faz-se uma comparação
entre dois algoritmos evolucionários: um que utiliza a rotina proposta neste trabalho para geração
da população inicial e outro que evolui uma população inicial gerada aleatoriamente. Por último,
na seção 6, são apresentadas algumas conclusões
acerca do trabalho desenvolvido.
2
resolução do problema de despacho de caminhões
em minas a céu aberto com otimização dos seguintes objetivos: tempo de fila dos caminhões,
metas de produção e qualidade de minério. Foi
proposto um modelo no qual é atribuı́do um peso
para cada objetivo, indicando a sua relevância em
relação aos demais, sendo que a função objetivo é
determinada pelo somatório dos objetivos ponderados.
Pinto and Merschmann (2001) propuseram
dois modelos para o problema de otimização da
produção de minério numa mina a céu aberto: um
baseado na alocação estática de veı́culos e outro
na alocação dinâmica. Ambos os modelos utilizam
o mesmo conjunto de restrições.
Costa et al. (2005) apresentaram um modelo
de programação por metas para planejamento da
produção e da qualidade do minério. O trabalho
combina ideias extraı́das das pesquisas de Chanda
and Dagdelen (1995) e Pinto et al. (2003). Em resumo, os autores trataram da alocação de equipamentos de carga nas frentes de lavra, da alocação
de caminhões e do controle do teor quı́mico do
minério.
Ta et al. (2005) abordaram o problema de minimizar o tamanho da frota de veı́culos de uma
mina sujeito à restrição de capacidade da pilha
de Surge (pilha de minério de capacidade limitada que recebe o produto gerado no britamento
no qual o minério é preparado antes de ser destinado para a planta de extração). Foi proposto um
modelo de otimização com restrição probabilı́stica
para o problema de alocação de veı́culos no qual
as variáveis de decisão correspondem ao número e
ao tipo dos veı́culos alocados a cada equipamento
de carga. O modelo permite que a solução ótima
seja um número fracionário de veı́culos. Para obter uma solução discreta, definiu-se um segundo
modelo que discretiza a quantidade de veı́culos
gerada no primeiro modelo. O modelo descrito
no trabalho não contemplou restrições referentes
à qualidade do minério e da produção de estéril,
apesar de ambas as questões terem sido abordadas
no texto.
No trabalho de Fioroni et al. (2008), abordouse o problema de planejamento mensal da produção de minério. Elaborou-se um modelo para minimização do custo de alocação dos equipamentos
de carga nas frentes de minério que foi usado como
um processo de um simulador de eventos discretos, implementado no software ARENA. O modelo retrata a alocação dos equipamentos de carga
nas frentes de lavra (visando atender as metas de
produção e qualidade) e determina o número de
viagens de cada veı́culo em cada ponto de carregamento. Por sua vez, o simulador avalia o plano
de extração de material gerado pelo otimizador.
Li et al. (2009) utilizaram uma abordagem
multiobjetivo para o problema da mistura de minério. Foi proposto um modelo com três objetivos,
Revisão bibliográfica
A seguir são relacionados alguns trabalhos, encontrados na literatura especializada, que abordam
problemas encontrados no contexto de minas a céu
aberto. Maior atenção é dada aos trabalhos que
tratam do problema de despacho de veı́culos em
minas a céu aberto.
White and Olson (1986) propuseram um algoritmo (que é a base do sistema DISPATCH utilizado em diversas minas no mundo) para despacho
de veı́culos que opera em 2 fases: a primeira utiliza programação linear para otimizar a mistura
de minério e a segunda utiliza programação dinâmica para otimizar o transporte de material por
meio da minimização do volume de material transportado.
Chanda and Dagdelen (1995) aplicaram programação por metas (Goal Programming) na resolução do problema da mistura de minérios numa
mina de carvão. Foi proposto um modelo com
função objetivo definida com ponderação dos seguintes objetivos: maximização do lucro, minimização dos desvios de produção e de qualidade em
relação às metas de produção e qualidade.
Alvarenga (1997) desenvolveu um algoritno
genético (AG) com processamento paralelo para
4301
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
representados por três funções lineares: minimizar
o consumo de energia e maximizar o lucro e a utilização dos recursos. Utilizou-se lógica fuzzy para
atribuir nı́veis de preferência para cada objetivo.
O modelo apresentado no trabalho não contempla
nenhuma restrição referente à produção ou propriedades do minério produzido.
Ercelebi and Bascetin (2009) trataram o problema de identificação do número de viagens realizadas pelos veı́culos em cada frente de duas formas
distintas: numa abordagem, aplicou-se a teoria de
filas para determinar o número de viagens de cada
veı́culo nos pontos de lavra; noutra abordagem, os
veı́culos são despachados para os equipamentos de
carga seguindo dados oriundos da otimização de
um modelo de programação linear que minimiza
o tamanho da frota. Ambas as propostas foram
aplicadas num mesmo cenário de mina e, na comparação dos resultados, verificou-se que os custos
de carregamento e basculamento gerados por cada
proposta são similares.
Souza et al. (2010) desenvolveram um algoritmo, chamado GGVNS, para aplicação no problema de planejamento da operação de minas a
céu aberto com alocação dinâmica de veı́culos. O
GGVNS combina técnicas de Busca Adaptativa
Aleatória Gulosa (Greedy Randomized Adaptive
Search Procedures-GRASP ) com Busca em Vizinhança Variável (General Variable Neighborhood
Search-GVNS) para otimizar a produção, a qualidade do minério e o tamanho da frota. O algoritmo foi aplicado em oito cenários de mina a céu
aberto e os resultados obtidos com o algoritmo
se mostraram superiores aos gerados por um modelo de programação inteira mista implementado
no CPLEX.
No trabalho de He et al. (2010) otimizou-se
o tamanho da frota de veı́culos de uma mina por
meio da minimização dos custos de transporte e
manutenção utilizando AG. O algoritmo implementou o método da roleta para seleção dos indivı́duos e cruzamento com um ponto de corte. Apesar de obter resultados satisfatórios, o modelo empregado não contemplou diversas restrições (compatibilidade entre veı́culos, relação minério estéril,
mistura de minérios, etc.) presentes em problemas
de despacho de veı́culos em minas a céu aberto.
Amaral and Pinto (2010) desenvolveram uma
heurı́stica para aplicação no problema de planejamento da operação de lavra em minas a céu aberto
com alocação dos equipamentos de carga e transporte para cada ordem de lavra (perı́odo de tempo
entre a alocação dos equipamentos e o término da
lavra de um bloco). A programação por metas é
utilizada para alocação dos equipamentos de carga
e transporte. O resultado da otimização é utilizado pela heurı́stica para cálculo da ordem de lavra e penalização das soluções quando as metas de
qualidade não são atendidas. O software CPLEX
foi utilizado pela heurı́stica para otimização do
modelo apresentado no trabalho. A heurı́stica foi
aplicada em 04 minas, sendo relatado que a resolução do modelo de alocação dos equipamentos
de carga e transporte consumiu aproximadamente
80% do tempo de execução da heurı́stica.
3
Desenvolvimento
No trabalho abordou-se, de forma multiobjetivo,
o problema de despacho de caminhões em minas a
céu aberto com alocação dinâmica dos veı́culos. O
seguinte modelo matemático foi desenvolvido para
descrever o problema:
• M (E) – Conjunto de frentes de lavra de minério (estéril) ativas (ou em operação). |M|(|E|)
– Total de frentes de minério (estéril) ativas;
• F = M U E – Conjunto de frentes de lavra
ativas (estéril e minério);
• K – Conjunto de pás carregadeiras ativas (em
operação). |K| – Total de equipamentos ativos;
• Ck - Produção (ton/h) do equipamento k
(k ∈ K) ;
• T – Conjunto dos caminhões ativos (em operação). |T| – Tamanho da frota;
• B – Conjunto de britadores em operação. |B|
– Total de britadores em operação;
• O – Conjunto de pilhas de estéril ativas;
• Z = B U O – Locais disponı́veis para descarregamento de material;
• R – Conjunto de rotas da mina. Cada rota
indica um local para carregamento e outro
para descarregamento de material;
• S= (s1 , · · · , sn ) – Escala com n despachos,
sedo que cada despacho si (1 ≤ i ≤ n) identifica: uma rota, um equipamento de carga e
um tipo de veı́culo de transporte.|S| Total de
despachos da escala S;
• V – Conjunto dos elementos (ou variáveis)
quı́micos presentes nas frentes de minério;
• Rf : Ritmo (ton/h) de lavra na frente f (f ∈
F );
• gk,t = 1: se o equipamento k(k ∈ K) é compatı́vel com o veı́culo t(t ∈ T ); 0: caso contrário.
• at,s =1: Se o veı́culo t (t ∈ T ) foi alocado ao
despacho s (s ∈ S); 0: Caso contrário.
Os tempos envolvidos na realização de um
despacho s(s ∈ S) por um veı́culo t(t ∈ T ), conforme ilustrado na Figura 2, são:
4302
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
• T at,S – Conjunto de despachos de S, executados pelo veı́culo t(t ∈ T ), ordenados pelo
horário de inı́cio de cada despacho. |T at,S | –
Total de despachos de S realizados por t;
• ds – Distância (km) entre os locais de carregamento e descarregamento indicados na rota
da escala s(s ∈ S);
Figura 2: Descrição dos principais componentes
temporais presentes na realização de um despacho
s por um veı́culo t.
• ds,t – Distância (Km) entre a localização do
veı́culo t(t ∈ T ), antes de iniciar o despacho
s(s ∈ T at,S ), até o ponto de carregamento
indicado em s. Convencionou-se que, inicialmente, todos os veı́culos estão localizados
num mesmo ponto de britamento da mina.
• T st,s – Horário (h:m:s) em que t inicia o
deslocamento para carregamento no equipamento definido em s;
Adicionalmente, o problema abordado no trabalho contempla o seguinte conjunto de restrições:
X
1≤
gk,t ≤ |K|, ∀t ∈ T ;
(1)
• T at,s – Horário (h:m:s) em que t chega na
frente de lavra. T dvt,s = T at,s − T st,s :
Tempo (min) de deslocamento do veı́culo até
a frente de lavra;
k∈K
1≤
X
gk,t ≤ |T |, ∀k ∈ K;
(2)
t∈T
• T ct,s e T et,s – Indicam, respectivamento, o
horário (h:m:s) em que t inicia e conclui a
operação de carregamento na realização de s.
T krt,s = T et,s − T ct,s : Tempo (min) para
carregamento de t;
As restrições 1 e 2 verificam a compatibilidade
entre equipamentos de carga e transporte.
X
at,s = 1, ∀s ∈ S;
(3)
t∈T
• T dt,s – Horário (h:m:s) em que t chega ao
local de descarregamento. T dct,s = T dt,s −
T et,s : Tempo (min) de deslocamento do veı́culo até o local de descarregamento;
1≤
at,s ≤ |S|, ∀t ∈ T ;
(4)
s∈S
Enquanto as restrições 3 restringem um caminhão por despacho, 4 limitam o total de despachos
que podem ser atribuı́dos a cada veı́culo.
• T bt,s e T ft,s – Especificam, respectivamente,
o horário (h:m:s) em que t inicia e conclui a
operação de descarregamento de material na
realização de s. T bst,s = T ft,s −T bt,s : Tempo
(min) de descarregamento de t.
3.1
X
X
yk,f Knk ≤ Rf ≤
k∈K
X
yk,f Kxk , ∀f ∈ F ; (5)
k∈K
Knk ≤ Ck ≤ Kxk , ∀k ∈ K;
(6)
As restrições 5 limitam a produção de cada
frente de lavra à produção do(s) equipamento(s)
de carga alocado(s) à frente e 6 estabelecem limites de produção para cada equipamento.
Função multiobjetivo
A seguinte função bi-objetivo foi formulada para
o problema de despacho de caminhões em minas
a céu aberto com alocação dinâmica dos veı́culos:
F (S) = M inimizar[F1 (S), F2 (S)],
em que: P
P
F1 (S) = t∈T (TL − s∈S at,s × T opt,s ) descreve o tempo (min) total que cada veı́culo permanece em fila e/ou inoperante, nos locais de carregamento e descarregamento de material, durante
a realização dos despachos de S, sendo:
P
f ∈E
Rf
P
f ∈M
Rf
P
f ∈E
− Remx ≤ 0 e P
f ∈M
Rf
Rf
− Remn ≥ 0;
(7)
As restrições 7 definem limites mı́nimos e máximos aceitáveis para a relação entre a produção
de estéril e de minério.
X
• TL – Tempo (Min) limite para realização dos
despachos da escala S;
(Cv,f − V xv,b )Rf,b ≤ 0, ∀v ∈ V, b ∈ B; (8)
f ∈M
• T opt,s – Tempo (Min) de operação do veı́culo
t (t ∈ T ) na realização do despacho s (s ∈ S):
T dvt,s + T krt,s + T dct,s + T bst,s .
P
P
F2 (S) =
t∈T
s∈T at,s (ds,t + ds ) expressa
a distância (Km) percorrida pelos caminhões durante a realização da cadeia S, sendo:
X
(Cv,f − V nv,b )Rf,b ≥ 0, ∀v ∈ V, b ∈ B. (9)
f ∈M
As restrições 8 e 9 verificam se o valor de cada
parâmetro de qualidade v (v ∈ V) no produto final
obtido em cada britador está dentro do intervalo
aceitável.
4303
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
3.2
Simulador de despachos de caminhões
A rotina tem como parâmetros uma solução
não viável s e o tamanho da busca k na vizinhança
de s e funciona da seguinte forma:
Neste trabalho, desenvolveu-se um simulador de
despacho de caminhões em minas a céu aberto.
Ele recebe uma solução (cadeia de despachos)
como entrada e processa os diversos despachos
da cadeia dentro de um perı́odo de simulação
(turno). Ao final, os seguintes dados são retornados: quantidade de material produzido, tempo
de fila e distância percorrida pelos veı́culos, produção e tempo total de operação dos equipamentos
de carga, caracterı́sticas e quantidade de minério
produzido no(s) britador(es) e total de estéril depositado em cada pilha de estéril. Esses dados
permitem computar os objetivos e restrições contempladas no problema estudado no trabalho.
4
• Inicialmente, pesquisa-se a vizinhança da solução s. Essa etapa é realizada pela rotina
searchNeighborHood, que é uma adaptação
da estratégia first improvement (Hoos and
Stutzle (2005)) e funciona do seguinte modo:
– Um dos operadores Lsho ou Lshu , selecionado aleatoriamente, modifica np despachos da solução corrente, resultando
no vizinho s’ ;
– O processo é finalizado quando: i). O
valor total de restrições violadas de s’ é
inferior ao de s (s’ é melhor do que s), ou
ii). Após gerar k soluções vizinhas de s.
Nesse caso, se s não foi melhorada, ela é
retornada;
Método proposto para geração da
população inicial
Normalmente, os algoritmos evolucionários (AEs)
evoluem um conjunto de soluções iniciais gerado
de forma aleatória. O conjunto de soluções é evoluı́do durante várias gerações até que uma condição de parada seja atendida. Uma outra alternativa explorada por alguns autores (vide, por exemplo, Santos et al. (2006), Alvarenga et al. (2007),
Souza et al. (2010)) consiste na implementação de
heurı́sticas para construção do conjunto de soluções iniciais. Essa abordagem se mostra interessante, visto que, despender algum esforço na geração da população inicial pode melhorar a convergência do algoritmo (Haubelt et al. (2005)).
Especificamente no problema de despacho de
veı́culos em minas a céu aberto, diante da complexidade e variedade do conjunto de restrições, a
geração aleatória de um conjunto de soluções resulta numa população composta basicamente de
soluções não viáveis. Diante disso, desenvolveu-se
uma heurı́stica, denominada OptNonfeasibleSolution, para minimizar o valor total das restrições
violadas por uma solução não viável da população
inicial. Em resumo, a rotina, cujo pseudocódigo
é descrito pelo Algoritmo 1, realiza várias buscas
na vizinhança de uma solução não viável, tentando
viabilizá-la.
A rotina implementa os seguintes operadores
de movimento:
• Se a solução s’, retornada anteriormente, é
melhor do que s, os seguintes passos são executados na ordem listada:
1. s’ substitui a solução corrente s;
2. Se s foi viabilizada, ela é retornada e
o processo é concluı́do. Caso contrário,
seta-se um flag (gIn) para indicar que
uma solução melhor que a original foi
encontrada;
• Se s não foi melhorada, np é reduzido. Se np
é igual a zero e nenhuma melhoria foi verificada anteriormente, o processo é concluı́do e
a solução corrente é retornada.
Dois algoritmos, denominados hNSGA e
hN SGA⊗ , foram desenvolvidos neste trabalho.
Ambos são adaptações do NSGA-II (Deb et al.
(2002)) e apresentam as seguintes particularidades:
• O hN SGA⊗ evolue uma população inicial
gerada aleatoriamente, enquanto o hNSGA
aplica a rotina OptNonfeasibleSolution em
cada solução inicial não viável gerada de
forma aleatória;
• O operador de cruzamento implementado em
ambos combina caracterı́sticas dos operadores Partially Mapped (PMX)(Goldberg and
Lingle (1985)) e Order (OX) (Davis (1985));
• Shovel-Lsho (s,d) : d (definido aleatoriamente) despachos distintos da escala s têm
sua rota e equipamento de carga alterados.
A compatibilidade entre os equipamentos é
garantida pelo operador;
• Ambas as implementações utilizam um operador de mutação que se assemelha ao operador simple remove and reinsert (RAR) (Gendreau et al. (1999));
• Shuffle-Lshu (s): Um tipo de veı́culo t é selecionado e um equipamento de carga k da
escala s, compatı́vel com t, também é selecionado. Todos os despachos de s, associados
à k, são removidos e inseridos em novas posições da escala;
5
Resultados
Nesta seção são analisados os desempenhos dos
algoritmos hNSGA e hN SGA⊗ . Em resumo, é
4304
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
Algorithm 1 OptNonfeasibleSolution ()
Require: s, k
Ensure: s
ND ← s.NDispatches();
np ← bN D/log(N D)c;
gIn ← no;
repeat
s’ ← s.searchNeighborHood(k,np,[Lsho , Lshu ]);
if s’ is BETTER THAN s then
s ← s’;
if s.isFeasible solution () then
return s;
else
gIn ← yes;
end if
else
np ← bnp − np/3c;
if (np =0) and (gIn=yes) then
np ← bN D/log(N D)c;
gIn ← no;
end if
end if
until (np < 1);
return s;
Mina
Opm1
Opm2
Opm5
Opm6
Veı́culos
(15:50) (11:80)
(15:50) (13:80)
(15:50) (11:80)
(15:50) (13:80)
EC
8
8
8
8
VQ
10
10
5
5
FM (FE)
6 (2)
6 (2)
6 (2)
6 (2)
Tabela 1: Detalhes dos cenários de mina utilizados nos experimentos. Cada par (entre parênteses) da coluna Veı́culos informa o total de veı́culos
e a sua capacidade (ton) de transporte. A coluna
EC identifica o total de equipamentos de carga
da mina. VQ corresponde ao número de variáveis quı́micas analisadas e FM(FE) identificam,
respectivamente, o total de frentes de minério e
estéril da mina.
Parâmetro
Taxa de cruzamento (pc )
Taxa de mutação (pm )
Tamanho da população (Npop )
Repetições por experimento
Elitismo
Número de avaliações da FO
Turno (ℵ)
Valor
0,80
1
n∗
100
20
70%
20.000
4 Horas
Tabela 2: Parâmetros do experimento. n∗ corresponde ao tamanho do cromossomo.
verificado se a rotina proposta para perturbação
do conjunto de soluções iniciais gera ganhos significativos em algoritmos multiobjetivo, no caso
especı́fico deste trabalho, com funcionamento semelhante ao do NSGA-II.
A linguagem Java (versão 1.7.0 03) foi utilizada no desenvolvimento do simulador e dos algoritmos em um equipamento com processador Intel
core I5 2.67 GHz com 4 GB RAM com o sistema
Windows 7.
Para avaliação dos algoritmos, foram utilizados 04 (quatro) cenários de minas a céu aberto,
adaptados dos cenários opm1 , opm2 , opm5 e
opm6 , apresentados em Souza et al. (2010). Esses cenários foram escolhidos de um conjunto
de 08 (oito) cenários porque somente eles consideram mais de um tipo distinto de veı́culo.
Os cenários escolhidos, apresentados na Tabela
1, estão disponı́veis (em formato XML) em
www.cpdee.ufmg.br/ jbm/ITOR/. As adaptações
feitas nos cenários comprendem informações do
tipo: distância entre os locais de carregamento e
basculamento e velocidade dos veı́culos, ambas necessárias para o simulador.
Os indicadores de qualidade: Distância geracional invertida (Inverted Generational Distance
– IGD) (Coello and Cortés (2005)) e Cobertura
entre conjuntos (Two Set Coverage – CS) (Zitzler
et al. (Summer 2000)) foram utilizados na avaliação dos dois algoritmos. O conceito de dominância Pareto (Coello et al. (2002)) foi empregado no
desenvolvimento de ambos os algoritmos.
Para computar o IGD dos algoritmos, o seguinte procedimento foi executado para constru-
ção da fronteira Pareto estimada (FPE) para os
04 cenários de mina: os algoritmos hNSGA e
hN SGA⊗ foram executados 20 (vinte) vezes cada
com Npop = 500 e tendo como condição de parada número de gerações = 300. Cada solução
não dominada s, obtida ao final de cada execução,
é gravada num banco de dados (BD) se nenhuma
solução do banco a domina. Ademais, as soluções
que são dominadas por s são removidas do BD.
Além disso, para uma justa comparação, ambas as implementações utilizaram a mesma codificação dos indivı́duos e o mesmo conjunto de parâmetros (descritos na Tabela 2).
Também foram geradas 20 populações de
forma aleatória e cada uma foi processada por ambos os algoritmos. No final, computou-se o valor
médio dos indicadores IGD e CS, exibidos nas Tabelas 3 e 4, utilizando o conjunto de soluções não
dominadas obtidas na última iteração de cada implementação. O desvio padrão (DP) é destacado
entre parênteses.
Pelos dados apresentados na Tabela 3, notase que nos 04 cenários de mina, o IGD médio obtido com o hNSGA é inferior ao IGD médio do
hN SGA⊗ . Ou seja, as soluções da FPE estão
mais próximas das soluções geradas pelo hNSGA
do que as soluções produzidas pelo hN SGA⊗ .
Além disso, nota-se que o DP relativo ao IGD do
hN SGA é menor do que o DP do hN SGA⊗ para
os 04 cenários de mina.
Analisando os dados da Tabela 4, percebese que a cobertura média do hNSGA so-
4305
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
Cenário
Opm1
Opm2
Opm5
Opm6
Algoritmo
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
IGD Médio (DP)
0,385
0,223
0,180
0,112
0,267
0,141
0,199
0,136
nas a céu aberto com alocação dinâmica dos
veı́culos que: i). Contempla mais de um local para britamento de minério e ii). Permite
alocar até dois equipamentos de carga numa
frente de lavra em operação;
(0,07)
(0,02)
(0,05)
(0,01)
(0,04)
(0,01)
(0,06)
(0,03)
• Desenvolvimento de i). Simulador para despacho de caminhões em minas a céu aberto e
ii). Rotina para geração da população inicial
baseada em mecanismos de busca local. A
rotina proposta apresentou resultados satisfatórios em comparação ao procedimento de
geração aleatória da população.
Tabela 3: IGD médio calculado para os algoritmos
hN SGA⊗ e hNSGA nos 04 cenários de mina.
Cenário
Opm1
Opm2
Opm5
Opm6
Algoritmo
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
hN SGA⊗
hN SGA
hN SGA⊗
hNSGA
0,143(0,11)
0,471(0,17)
0,123(0,06)
0,323(0,11)
0,170(0,10)
0,436(0,15)
0,234(0,13)
0,249(0,11)
Tabela 4: CS média calculada para os algoritmos
hN SGA⊗ e hNSGA nos 04 cenários de mina.
• Comparação do algoritmo apresentado com
outros algoritmos encontrados na literatura
pesquisada. Na comparação das implementações, serão avaliados o desempenhos dos algoritmos para problemas com 1, 2 e 3 objetivos;
• Implementação de outros indicadores (por
exemplo, tempo de processamento, valores
mı́nimos e máximos dos objetivos) para avaliação dos algoritmos.
bre o hN SGA⊗ (representado por CS(hNSGA,
hN SGA⊗ )) está acima de 40% nos cenários Opm1
e Opm5 (chega a 47% em Opm1 ). Ainda em
ambos os cenários, a CS(hN SGA⊗ , hNSGA) fica
abaixo de 18%. Observa-se fato similar no cenário
Opm2, no qual a CS(hNSGA, hN SGA⊗ ) é superior a 32% e a CS(hN SGA⊗ , hNSGA) não atinge
13%. Somente no cenário Opm6 os valores computados para ambas as coberturas são próximos.
Porém, ainda assim, a CS(hNSGA, hN SGA⊗ ) é
ligeiramente superior à CS(hN SGA⊗ , hNSGA).
Fato interessante ocorre com o desvio padrão relativo ao indicador de cobertura. O DP
das soluções geradas pelo hN SGA é maior que o
DP relativo às soluções geradas pelo hN SGA⊗
nos cenários Opm1, Opm2 e Opm5.
Como
verificado anteriormente, nesses três cenários a
CS(hNSGA, hN SGA⊗ )) é superior em mais de
100% à CS(hN SGA⊗ , hNSGA)). Porém, para o
cenário Opm6, o DP do hN SGA é inferior ao
do hN SGA⊗ e, nesse caso especı́fico, os valores
da CS(hNSGA, hN SGA⊗ ) e da CS(hN SGA⊗ ,
hNSGA)) são bastante próximos.
Pelos resultados produzidos com os indicadores IGD e CS para ambos os algoritmos, observa-se
que as soluções produzidas pelo hNSGA são superiores às geradas pelo hN SGA⊗ .
6
Algumas atividades se mostraram relevantes
para continuidade da pesquisa e serão desenvolvidas posteriormente. Dentre as principais atividades tem-se:
Agradecimentos
Agradeçemos às agências de fomento FAPEMIG e
CNPq pelo apoio financeiro.
Referências
Alvarenga, G. B. (1997). Despacho Ótimo de caminhões numa mineração de ferro utilizando
o algoritmo genético com processamento paralelo. Universidade Federal de Minas Gerais
- UFMG (Trabalho de Mestrado ).
Alvarenga, G. B., Mateus, G. R. and de Tomi, G.
(2007). A genetic and set partitioning twophase approach for the vehicle routing problem with time windows, Computers & Operations Research 34(6): 1561–1584.
Amaral, M. D. and Pinto, L. R. (2010). Planejamento de operações de lavra em minas
a céu aberto com alocação de equipamentos
de carga e de transporte, Anais XLII Simpósio Brasileiro de Pesquisa Operacional, Bento
Goncalves (RS), pp. 1177–1188.
Conclusões
Bastos, G. S. (2010). Methods for truck dispatching in open pit mining, Thesis of doctor in
science, Aeronautics Institute of Technology
- São José dos Campos.
As principais contribuições deste trabalho são:
• Formulação de um modelo multiobjetivo para
o problema de despacho de veı́culos em mi-
4306
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
Chanda, E. K. C. and Dagdelen, K. (1995).
Optimal blending of mine production using
goal programming and interactive graphics
systems, International Journal of surface
Mining, Reclamation and the Environment
9(4): 203–208.
Haubelt, C., Gamenik, J. and Teich, J. (2005).
Initial population construction for convergence improvement of moeas, Lecture Notes
in Computer Science (LNCS) 3410: 191–205.
He, M.-X., Wei, J.-C., Lu, X.-M. and Huang, B.X. (2010). The genetic algorithm for truck
dispatching problems in surface mine, Journal Information Technologyh 9: 710–714.
Coello, C. A. C. and Cortés, N. C. (2005). Solving
multiobjective optimization problems using
an artificial immune system, Genetic Programming and Evolvable Machines 6(2): 163–
190.
Hoos, H. H. and Stutzle, T. (2005). Stochastic
Local Search: Foundations and Applications,
MORGAN KAUFMANN PUBLISHERS.
Coello, C. A. C., Lamont, G. B. and Veldhuizen,
D. A. V. (2002). Evolutionary Algoriths for
Solving Multi-objective Problems, Vol. 242,
Springer.
Li, L., Xu, T. and Liu, Z. (2009). A fuzzy multiobjective optimization algorithm in mine ore
blending, International Joint Conference on
Computational Sciences and Optimization,
IEEE Computer Society, Sanya, Hainan,
pp. 773–776.
Costa, F. P., Souza, M. J. F. and Pinto, L. R.
(2005). Um modelo de programação matemática para alocação estática de caminhões
visando ao atendimento de metas de produção e qualidade, Rem: Revista Escola de Minas 58(1): 77–81.
Pinto, L. R., Biajoli, F. L. and Mine, O. M. (2003).
Uso de otimizador em planilhas eletrônicas
para auxı́lio ao planejamento de lavra. Universidade Federal de Ouro Preto.
Davis, L. (1985). Applying adaptive algorithms
to epistatic domains, 9th international joint
conference on Artificial intelligence-IJCAI,
Vol. 85, pp. 162–164.
Pinto, L. R. and Merschmann, L. H. C. (2001).
Planejamento operacional da lavra de mina
usando modelos matemáticos, Rem: Revista
Escola de Minas 54(3): 211–214.
Deb, K., Pratap, A., Agarwal, S. and Meyarivan,
T. (2002). A fast and elitist multiobjective
genetic algorithm:nsga-ii, IEEE Transactions
on Evolutionary Computation 6(2): 182–197.
Santos, H. G., Ochi, L. S., Marinho, E. H. and
Drummond, L. M. A. (2006). Combining an
evolutionary algorithm with data mining to
solve a single-vehicle routing problem, Neurocomputing 70(1): 70–77.
Ercelebi, S. G. and Bascetin, A. (2009). Optimization of shovel-truck system for surface mining, The Journal of The Southern African
Institute of Mining and Metallurgy 109: 433–
439.
Souza, M. J. F., Coelho, I. M., Ribas, S.,
Santos, H. G. and Merschmann, L. H. C.
(2010). A hybrid heuristic algorithm for the
open-pit-mining operational planning problem, European Journal of Operational Research 207(2): 1041–1051.
Fioroni, M. M., Franzese, L. A. G., Bianchi, T. J.,
Ezawa, L., Pinto, L. R. and Jr., G. M. (2008).
Concurrent simulation and optimization models for mining planning, Simulation Conference, pp. 759 –767.
Ta, C. H., Kresta, J. V., Forbes, J. F. and Marquez, H. J. (2005). A stochastic optimization
approach to mine truck allocation, International Journal of Surface Mining, Reclamation
and Environment 19(3): 162–175.
Gendreau, M., Laporte, G. and Potvin, J.-Y.
(1999). Metaheuristics for the vehicle routing problem, Technical report, University of
Montreal, Canada, Les Cahiers du GERAD
G-98-52.
White, J. W. and Olson, J. P. (1986). Computerbased dispatching in mines with concurrent operating objectives, Mining Engineering 38(11): 1045–1054.
Goldberg, D. E. and Lingle, R. (1985). alleles, loci,
and the traveling salesman problem, in J. J.
Grefenstette (ed.), Proceedings of the First
International Conference on Genetic Algorithms and Their Applications, Lawrence Erlbaum Associates, Publishers.
Zitzler, E., Deb, K. and Thiele., L. (Summer
2000). Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary Computation 8(2): 173–195.
Golden, B. L., RaghHava, S. and Wasil, E. A.
(2008). The vehicle routing problem: latest
advances and new challenges, Vol. 43, Springer.
4307