Long-term open-pit planning by ant colony optimization [Elektronische Ressource] / Javad Sattarvand

Javad Sattarvand

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2012
• Nombre de lectures: 24
• Langue: Deutsch
• Poids de l'ouvrage: 3 Mo

Extrait

 
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 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 s 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
hig