Long-term open-pit planning by ant colony optimization
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 trail with a chemical 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 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. ASrank is the third method in which only a 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.
info:eu-repo/classification/ddc/620, Tagebau, Planung, Ameisenalgorithmus, Optimierung, Ingenieurwissenschaften, Tagebauplanung, open-pit planning, ant colony optimization, optimization
Networked Digital Library of Theses and Dissertations