Programação por restrições aplicada ao agrupamento de blocos no planejamento de lavra

Abstract

O problema mais importante do planejamento de lavra é a definição do sequenciamento de lavra (production scheduling problem), quando deve-se decidir quando cada porção do depósito mineral será extraída e qual sua destinação. Entretanto, este é um problema em que os algoritmos conhecidos não são capazes de resolvê-lo de forma exata em tempo polinomial, sendo classificado como NP-difícil. Consequentemente, algumas estratégias são empregadas para simplificá-lo, como a definição prévia de uma cava final (ultimate pit problem) e a subdivisão do problema do sequenciamento sob as ópticas do longo, médio e curto prazo, que apresentam suas próprias particularidades, objetivos e restrições. Outra maneira de simplificar este problema é o agrupamento (clustering) de blocos em polígonos de lavra (mining cuts) com base em algum critério de similaridade, reduzindo assim o tamanho do problema do sequenciamento e adicionando restrições operacionais à solução, como largura mínima da cava e dimensão do equipamento de lavra. O problema do agrupamento também é NP-difícil, sendo frequentemente abordado por heurísticas, metaheurísticas e técnicas baseadas em aprendizado de máquina, geralmente prescindindo da definição formal de um modelo matemático. Neste estudo, é apresentada uma formulação matemática para o problema do agrupamento de polígonos de lavra em minas a céu aberto. Essa proposta baseia-se em Programação Inteira Mista (Mixed-Integer Linear Programming, MILP) e é projetada para ser abordada de forma independente do problema do sequenciamento de produção. Além disso, o problema é resolvido por programação por restrições (Constraint Programming, CP), que possibilita a obtenção de um conjunto de soluções viáveis ao amostrar o espaço de soluções a partir do modelo de otimização Constraint Satisfaction Problem (CSP). Por outro lado, o modelo Constraint Optimization Problem (COP) obtém soluções ótimas para o problema, podendo até encontrar soluções que são ótimos globais. Como a solução direta do modelo proposto pode ainda gerar uma solução inviável do ponto de vista operacional, este estudo propõe ainda uma otimização multiestágio baseada em programação por restrições. Foi proposta ainda a heurística de propagação geométrica (geometric propagation heuristic, GPH), capaz de efetuar o refinamento dos clusters gerados e garantir que a solução respeite a dimensão do equipamento de lavra. Para ilustrar a metodologia proposta, são apresentados dois estudos de caso em bancos de dados reais, um consistindo na aplicação direta das abordagens CSP e COP, ao passo que o outro aplica a otimização multiestágio e a GPH em três cenários com diferentes parâmetros. Por fim, uma metodologia multiestágio reduzida composta de uma etapa empregando k-means e outra etapa empregando a GPH foi proposta, cujos resultados foram comparados aos obtidos pela metodologia multiestágio baseada em programação por restrições. Os resultados comprovam que as técnicas empregadas neste estudo foram capazes de gerar polígonos de lavra que são ótimos locais em um tempo aceitável, além de ressaltarem o potencial da heurística de propagação geométrica, algoritmo capaz de rapidamente refinar a geometria de clusters.

The most important problem in mining planning is the definition of the mining sequencing, when it must be decided when each portion of the mineral deposit will be extracted and what its destination will be. However, this is a problem in which known algorithms are not able to solve it exactly in polynomial time, being classified as NP-hard. Consequently, some strategies are employed to simplify it, such as the prior definition of an ultimate pit and the subdivision of the sequencing problem from the perspective of long-, medium- and short-term, which present their own particularities, objectives and constraints. Another way to simplify this problem is to aggregate blocks into mining cuts based on a similarity criterion, reducing the size of the sequencing problem and adding operational criteria to the solution, such as the minimum pit width and size of mining equipment. The clustering problem is also NP-hard, and is often addressed by heuristics, metaheuristics and techniques based on machine learning, generally dispensing with the formal definition of a mathematical model. In this study, a mathematical formulation is presented for the mining cut clustering problem in open-pit mines. This proposal is based on Mixed-Integer Linear Programming (MILP) and is designed to be approached independently of the production scheduling problem. Furthermore, the problem is solved by Constraint Programming (CP), which makes it possible to obtain a set of feasible solutions by sampling the solution space using the Constraint Satisfaction Problem (CSP) optimization model. On the other hand, the Constraint Optimization Problem (COP) model obtains optimal solutions to the problem, and can even find solutions that are global optima. As the direct solution of the proposed model can still generate an unfeasible solution from an operational point of view, this study also proposes a multi-stage optimization based on Constraint Programming. The geometric propagation heuristic (GPH) was also proposed, capable of refining the generated clusters and ensuring that the solution respects the size of the mining equipment. To illustrate the proposed methodology, two case studies on real databases are presented, one consisting of the direct application of the CSP and COP approaches, while the other applies multistage optimization and GPH in three scenarios with different parameters. Finally, a reduced multi-stage methodology composed of a k-means step and a GPH step was proposed, the results of which were compared to those obtained by the multi-stage optimization based on Constraint Programming. The results prove that the techniques used in this study were capable of generating mining cuts that are local optima in an acceptable time, in addition to highlighting the potential of the geometric propagation heuristic, an algorithm capable of quickly refining the geometry of clusters.