Long‐Term Open‐Pit Planning by Ant Colony Optimization  2. Revised Edition  The Faculty of Georesources and Materials Engineering of the   RWTH Aachen University    submitted by  Javad, Sattarvand, M.Sc.  from (Marand‐Iran)  in respect of the academic degree of   Doctor of Engineering    approved thesis    Advisors: Univ.‐Prof. Dr.‐Ing. Christian Niemann‐Delius        Univ.‐Prof. Dr.‐Ing. F. Ludwig Wilke      Date of the oral examination: 06.02.2009 Zusammenfassung ZUSAMMENFASSUNG Die Aufgabenstellung einer langfristigen Planung von Festgesteinstagebauen mit diskontinuierlicher Gewinnung ist eine große kombinatorische Herausforderung, die nicht durch mathematische Programmierung in angemessener Zeit gelöst werden kann. Diese Dissertation stellt einen neuentwickelten metaheuristischen Algorithmus vor, der auf den Theorien des Ameisenalgorithmus (Ant Colony Optimization, ACO) basiert. Darüber hinaus wird die Anwendung des entwickelten Modells anhand einer langfristigen Planung eines zwei-dimensionalen hypothetischen Block-Modells untersucht verifiziert. ACO beschreibt das natürliche Verhalten von Ameisen bei der Futtersuche, das die kürzeste Strecke zwischen Kolonie und Nahrungsquelle zum Ziel und bereits mehrfach erfolgreich zur Lösung anderer kombinatorischer Probleme beigetragen hat. In der Natur wird das Problem der optimalen Routenfindung mittels Pheromonen, die eine Nachricht von einer Ameise an die nächste übertragen, gelöst. Die Pheromone steuern die Wegfindung der Ameisen, so dass sie nicht nach dem Zufallsprinzip wandern, sondern den Pheromonspuren folgen. Mit der Zeit verdunsten die Pheromone von der Spur, die selten oder gar nicht mehr genutzt wird, währenddessen die Route mit der kürzesten Strecke erhalten bleibt. Um mit der ACO-Theorie eine langfristige Planung eines Festgesteins-tagebaus zu simulieren, wird die Anzahl der Pheromonspuren jedes Blocks mit der Anzahl der Planungsperioden gleichgesetzt. Die Pheromonspuren, die einem Block zugeordnet werden können, stellen die maximale Abbauteufe einer jeden Blockspalte pro Abbauperiode dar. Die Form eines bestimmten Tagebaus kann, unter Beachtung der Böschungswinkel, durch ein einfaches Datenfeld von ganzen Zahlen dargestellt werden. Dabei stellt jedes Element dieses Datenfeldes die Tiefe des Tagebaus in einer einzelnen Spalte des Block-Modells dar. Wenn dieses Konzept zu einer langfristigen Produktionsplanung erweitert wird, wird jeder Produktionsplan durch ein Datenfeld dargestellt, dass mehrere Abbauteufen für jede Spalte des Blockmodells in Relation zu den verschiedenen Produktionsperioden aufweist. Am Anfang wird eine initiale Tagebauplanung anhand des Lerchs-Grossmann Algorithmuses und den von Wang & Sevim entwickelten Algorithmus „Alternative zur Parametrisierung Algorithmus“ erstellt und die Werte der Pheromon Werte entsprechend initialisiert. Basierend auf der Tagebauplanung werden den Blöcken, die in direkter Nähe zu den Blöcken des tiefsten Punkts liegen, während der Initialisierung höhere Pheromonwerte zugeordnet. i Long-Term Open-Pit Planning by Ant Colony Optimization Diese Vorgehensweise erzeugt eine Reihe von zufälligen Zeitplänen, die nicht weit von der ursprünglichen Lösung sind. In jeder ACO-Iteration werden basierend auf den aktuellen Pheromonmengen zuerst mehrere Tagebaupläne erstellt. Dieser Prozess wird als “Bestimmung der Teufe“ gekennzeichnet und implementiert. Während des Prozesses wird die Teufe in jeder Periode für jede Spalte des Blockmodells bestimmt. Je höher der Wert der Pheromonspur eines Blocks ausfällt, desto größer ist die Möglichkeit, dass der Block als maximale Abbauteufe für die jeweilige Periode gewählt wird. Anschließend werden die Pheromonwerte aller Blöcke um einen gewissen Betrag durch Evaporation verringert. Im nächsten Schritt werden die Pheromonwerte der Blöcke, die den Abbaustand zur jeweiligen Periode begrenzen, je nach Qualität der Lösung des folgenden Abbaustands erhöht. Durch wiederholte Iterationen werden die Pheromonwerte der Blöcke, die die Form der optimalen Lösung definieren erhöht, während die Werte der anderen Blöcke signifikant verkleinert werden. Die ACO Optimierung Iterationen können auf verschiedene Arten implementiert werden. In der ersten und einfachsten Methode, Ant System (AS), dürfen alle konstruierten Tagebaustände zur Pheromonablagerung beitragen. Die zweite Methode, elitäres Ant- System (EAS) zeichnet sich dadurch aus, dass der optimale Plan zusätzlich Pheromone in jeder Iteration ablegt. AS ist die dritte Methode in der nur eine geringe Anzahl von guten rank Tagebauplänen Pheromon hinzufügen kann. Die weiteren Varianten, Max-Min Ant System (MMAS) und Ant Colony System (ACS), erlauben nur den bis zu diesem Zeitpunkt besten Abbauplanungen Pheromone abzulegen und nutzen zusätzlich spezielle Pheromoneinschränkungen, die eine Stagnation im lokalen Optimum verhindern. Um die Effizienz des Algorithmus zu überprüfen wurde ein Computerprogramm entwickelt, dass auf Visual Basic 2005 als Programmiersprache aufbaut. In einer Fallstudie wurde ein Blockmodell einer hypothetischen Eisenerzlagerstätte mit 1000 Blöcken erstellt. Anhand des Blockmodells wurden die verschiedenen Varianten der ACO analysiert, um die beste Kombination der ACO-Parameter zu identifizieren. Die Analyse zeigte, dass die ACO den Wert der ersten Tagebauplanungen bis zu 34 % in einer akzeptablen Rechenzeit verbessern kann. Diese Verbesserung ist vor allem der Berücksichtigung von evtl. Einbußen zuzuschreiben, die aus einer Überschreitung von Kapazitätsgrenzen oder Produktqualitäten resultiert. Es konnte bewiesen werden, dass die MMAS Variante, die Variante mit der größten Exploartion von Lösungen ist, währenddessen die AVS Variante die schnellste Methode ist. Diese beiden Varianten sind die Einzigen, die sich aufgrund des Speicherbedarfs von Rechnern auf große Blockmodelle anwenden lassen. ii Abstract ABSTRACT The problem of long-term planning of a hard rock open pit mine (discontinuous exploitation operation) is a large combinatorial problem which cannot be solved in a reasonable amount of time through mathematical programming models because of its large size. In this thesis, a new metaheuristic algorithm has been developed based on the Ant Colony Optimization (ACO) and its application in long-term scheduling of a two dimensional hypothetical block model has been analysed. ACO is inspired by the foraging behaviour of ants (i.e. finding the shortest way from the colony to the food source), and has been successfully implemented in several combinatorial optimization problems. In nature, ants transmit a message to other members by laying down a chemical trail called pheromones. Instead of travelling in a random manner, the pheromone trail allows the ants to trace the path. Over time, the pheromones layed over longer paths evaporate, whereas those over shorter routes continue to be marched over. In order to simulate the ACO process for long-term planning of a hard rock open-pit mine, various programming variables have been considered for each block as the pheromone trails. The number of these variables is equal to the number of planning periods. In fact these pheromone trails represent the desirability of the block for being the deepest point of the mine in that column for the given mining period. The shape of any given pit (in respect to the slope angles) can be represented by means of a simple array of integer numbers. Each element in this array shows the depth of the pit in an individual column of block model. Extending this concept to a long-term production planning, a mine schedule would be represented by an array that has several mine depths at each column of block model related to different production periods. At the beginning, the values of the pheromone trails are initialized according to a mine schedule generated by Lerchs-Grossmann’s algorithm and the alternative to parameterization algorithm of Wang & Sevim. During initialization, relatively higher values of pheromones are assigned to those blocks that are close to the deepest points of the push backs in the initial mine schedule. This leads the procedure to construct a series of random schedules which are not far from the initial solution. In each ACO iteration, several mine schedules are constructed based on current pheromone trails. This is implemented through a process called “depth determination”. In this process the depth of a mine in each period is determined for each column of the block model. The iii Long-Term Open-Pit Planning by Ant Colony Optimization higher the value of the pheromone trail of a particular block, the higher the possibility of selecting that block as the pit depth in that period. Subsequently the pheromone values of all blocks are reduced to a certain percentage (evaporation) and additionally the pheromone value of the participating blocks used in defining the constructed schedules are increased according to the quality of the generated solutions. Through repeated iterations, the pheromone values of the blocks which define the shape of the optimum solution are increased whereas those of the others have been significantly evaporated. The ACO optimization iterations could be implemented in a variety of ways. The Ant System (AS) is the first and simplest method, whereby all of the constructed schedules are allowed to contribute in the pheromone deposition. In each iteration of the second method, the Elitist Ant System (EAS), the best schedule found up to that iteration (the best-so-far schedule) is also allowed to deposit pheromones. AS is the third method in which only a rank few good schedules are able to add pheromones. The other variants are the Max-Min Ant System (MMAS) and the Ant Colony System (ACS), which allow only the best-so-far schedule to deposit pheromones and utilise special pheromone limitations in order to prevent the stagnation in local optimums. To test the efficiency of the algorithm, a computer program has been developed in Visual Basic 2005 programming language. As a case study, the block model of a hypothetical iron ore deposit with 1000 blocks was considered and different variants of ACO had been analysed in order to find the best combination of ACO parameters. The analysis revealed that the ACO is able to improve the value of the initial mining schedule by up to 34% in a reasonable computational time. This is mainly contributed to the consideration of the penalties to the deviations of the capacities and the production qualities from their permitted limits. It had also been proved that the MMAS is the most explorative variant, while ACS is the fastest method. These two variants also count as the only variants which could be applied to a large block model in respect to the amount of memory needed. iv Table of Contents TABLE OF CONTENTS LIST OF FIGURES ............................................................................................................................................. IX LIST OF TABLES .............................................................................................................................................. XI LIST OF ABBREVIATIONS ........................................................................................................................... XII 1 INTRODUCTION ......................................................................................................................... 1 1.1 Complexity of pit optimization .......................................................................................................... 2 1.2 Numerical example ........................................................................................................................... 4 1.3 A brief review of the literature .......................................................................................................... 6 1.4 Structure of the research ................................................................................................................... 9 2 THE PROBLEM OF LONG-TERM OPEN PIT PRODUCTION PLANNING .................. 11 2.1 Mathematical programming models ................................................................................................ 11 2.1.1 Integer linear programming (IP) .......................................................................................................... 11 Objective function ........................................................................................................................................ 11 Mining capacity constraints ......................................................................................................................... 12 Processing capacity constraints.................................................................................................................... 12 Constraints for the average grade of products ............................................................................................ 12 Reserve constraints ...................................................................................................................................... 13 Sequencing constraints ................................................................................................................................ 13 Binary variables ............................................................................................................................................ 14 2.1.2 The linear programming (LP) formulization of the model ................................................................... 14 2.2 Mathematical approaches for solution of the model ........................................................................ 15 2.2.1 Lagrangian Parameterization ............................................................................................................... 15 Ultimate Pit Limit (UPL) Problem ................................................................................................................. 15 Understanding Lagrangian parameterization .............................................................................................. 16 2.2.2 Clustering approach ............................................................................................................................. 16 2.2.3 Branch and cut technique .................................................................................................................... 19 2.2.4 Dynamic programming (DP) formulation ............................................................................................ 19 2.3 Heuristic algorithms ........................................................................................................................ 21 2.3.1 Whittle’s optimization process ............................................................................................................ 21 Definition of UPL problem ............................................................................................................................ 22 Lerchs-Grossmann algorithm ....................................................................................................................... 23 Steps of the algorithm .................................................................................................................................. 24 v Long-Term Open-Pit Planning by Ant Colony Optimization Step 2 in a closer look: ................................................................................................................................. 25 Numerical example ...................................................................................................................................... 27 Construction of nested pits .......................................................................................................................... 31 The best and worst case mining scenarios ................................................................................................... 32 UPL selection based on the NPV-Tonnage graph ......................................................................................... 32 Mine scheduling ........................................................................................................................................... 33 2.3.2 Sevim’s suggested approach ............................................................................................................... 36 Nested-pits creation algorithm .................................................................................................................... 37 Dynamic programming based search algorithm .......................................................................................... 41 Considering working-slope angles ................................................................................................................ 43 2.4 Metaheuristic methods ................................................................................................................... 46 2.4.1 Introduction ......................................................................................................................................... 46 Combinatorial optimization ......................................................................................................................... 46 Metaheuristics .............................................................................................................................................. 46 2.4.2 Genetic algorithm (GA) ........................................................................................................................ 47 Chromosome representation of the pits ...................................................................................................... 48 Initial population .......................................................................................................................................... 48 Assessment of pit fitness .............................................................................................................................. 49 Reproduction of pit population .................................................................................................................... 49 Termination condition of the algorithm ....................................................................................................... 50 2.4.3 Simulated annealing (SA) ..................................................................................................................... 51 Objective function ........................................................................................................................................ 51 Constraints ................................................................................................................................................... 54 Initial solution ............................................................................................................................................... 54 Perturbation mechanism .............................................................................................................................. 55 Acceptance criterion .................................................................................................................................... 56 Cooling schedule .......................................................................................................................................... 57 Initial temperature ....................................................................................................................................... 57 3 ANT COLONY OPTIMIZATION (ACO) ............................................................................... 59 3.1 TSP Definition ................................................................................................................................. 60 3.2 Basic elements in solution of TSP by ACO ........................................................................................ 60 3.2.1 Construction graph .............................................................................................................................. 60 3.2.2 Constraints ........................................................................................................................................... 61 3.2.3 Pheromone trails and heuristic information ....................................................................................... 61 3.3 Variants of ACO algorithm for TSP ................................................................................................... 61 3.3.1 Ant System (AS) ................................................................................................................................... 61 Pheromone Initialization .............................................................................................................................. 61 Solution construction ................................................................................................................................... 62 vi Table of Contents Update of Pheromone Trails ........................................................................................................................ 63 3.3.2 Elitist Ant System (EAS) ........................................................................................................................ 64 3.3.3 Rank-Based Ant System (AS ) ........................................................................................................... 64 rank 3.3.4 MAX–MIN Ant System (MMAS) ........................................................................................................... 65 Pheromone Trail Limits ................................................................................................................................ 66 Pheromone Trail Initialization and Re-initialization ..................................................................................... 66 3.3.5 Ant Colony System (ACS) ..................................................................................................................... 66 Tour Construction ........................................................................................................................................ 67 Global Pheromone Trail Update ................................................................................................................... 67 Local Pheromone Trail Update ..................................................................................................................... 67 Additional Remarks ...................................................................................................................................... 68 3.3.6 Approximate Nondeterministic Tree Search (ANTS) ........................................................................... 69 Use of Lower Bounds .................................................................................................................................... 70 Solution Construction ................................................................................................................................... 70 Pheromone Trail Update .............................................................................................................................. 71 3.3.7 Hyper-Cube Framework ACO ............................................................................................................... 71 Pheromone Trail Update Rules .................................................................................................................... 72 3.4 Adding local search to ACO .............................................................................................................. 73 3.5 Implementing ACO algorithms for TSP ............................................................................................. 73 3.5.1 Data Structures .................................................................................................................................... 73 Intercity distances ........................................................................................................................................ 73 Nearest-Neighbour Lists ............................................................................................................................... 73 Pheromone Trails ......................................................................................................................................... 74 Combining Pheromone and Heuristic Information ...................................................................................... 74 Pheromone Update ...................................................................................................................................... 74 Representing Ants ........................................................................................................................................ 74 Overall Memory Requirement ..................................................................................................................... 75 3.5.2 Algorithm steps ................................................................................................................................... 75 Data Initialization ......................................................................................................................................... 75 Termination Condition ................................................................................................................................. 76 Solution Construction ................................................................................................................................... 76 Local Search .................................................................................................................................................. 76 Pheromone Update ...................................................................................................................................... 76 3.5.3 Changes for implementing other variants of ACO ............................................................................... 77 4 ACO APPROACH FOR THE LONG-TERM SCHEDULING OF OPEN PIT MINES ....... 79 4.1 Pheromone Initialization ................................................................................................................. 79 4.2 Construction of schedules ............................................................................................................... 80 4.2.1 The process of depth determination ................................................................................................... 80 vii Long-Term Open-Pit Planning by Ant Colony Optimization 4.2.2 Pit generation according to the selected depths (normalization) ....................................................... 82 4.2.3 Mine schedule construction from generated pits ............................................................................... 83 4.3 Pheromone update ......................................................................................................................... 83 4.3.1 Pheromone Evaporation ...................................................................................................................... 84 4.3.2 Pheromone Deposition ........................................................................................................................ 85 4.4 Implementation tool ....................................................................................................................... 85 4.4.1 Input block model tab.......................................................................................................................... 85 4.4.2 Input parameters tab ........................................................................................................................... 86 4.4.3 Initial solution tab ................................................................................................................................ 87 4.4.4 ACO optimizer tab ............................................................................................................................... 88 4.5 Case study ....................................................................................................................................... 90 4.6 ACO variants and setting of parameters .......................................................................................... 91 4.6.1 Ant system (AS).................................................................................................................................... 91 Number of ants in each iteration ................................................................................................................. 94 Initial pheromone value ............................................................................................................................... 95 Priority factors of pheromone and heuristic information ............................................................................ 95 4.6.2 Elitist Ant System (EAS) ........................................................................................................................ 96 4.6.3 Rank Based Ant Szstem (AS ) ........................................................................................................... 99 rank 4.6.4 Max-Min Ant System (MMAS) ............................................................................................................. 99 4.6.5 Ant Colony System (ACS) ................................................................................................................... 101 5 CONCLUSION .......................................................................................................................... 103 5.1 Discussion ..................................................................................................................................... 104 5.2 Perspective research ..................................................................................................................... 106 REFERENCES .................................................................................................................................. 107 viii