Highest-Level Implementation of Push–Relabel Algorithm to Solve Ultimate Pit Limit Problem | ||
| Journal of Mining and Environment | ||
| مقاله 11، دوره 12، شماره 2، تیر 2021، صفحه 443-455 اصل مقاله (1.37 M) | ||
| نوع مقاله: Original Research Paper | ||
| شناسه دیجیتال (DOI): 10.22044/jme.2021.10481.1999 | ||
| نویسندگان | ||
| M. Talaei؛ A. Mousavi* ؛ A. R. Sayadi | ||
| Department of Mining Engineering, Faculty of Engineering, Tarbiat Modares University, Tehran, Iran | ||
| چکیده | ||
| Nowadays due to the existence of the economic and geological uncertainties and the increasing use of scenario-based project evaluation in the design of open-pit mines, it is necessary to find an exact algorithm that can determine the ultimate pit limit in a short period of time. Determining the ultimate pit limit is an important optimization problem that is solved to define what will be eventually extracted from the ground, and directly impacts the mining costs, revenue, choosing mining equipment, and approximation of surface infrastructures outside the pit. This problem is solved in order to maximize the non-discounted profit under the precedence relation (access) constraints. In this paper, the Highest-Level Push-Relabel (HI-PR) implementation of the push–relabel algorithm is discussed and applied in order to solve the ultimate pit limit optimization problem. HI-PR uses the highest-label selection rule, global update, and gap heuristics to reduce the computations. The proposed algorithm is implemented to solve the ultimate pit limit for the nine real-life benchmark case study publicly available on the Minelib website. The results obtained show that the HI-PR algorithm can reach the optimum solution in a less computational time than the currently implemented algorithms. For the largest dataset, which includes 112687 blocks and 3,035,483 constraints, the average solution time in 100 runs of the algorithm is 4 s, while IBM CPLEX, as an exact solver, could not find any feasible solution in 24 hours. This speeding-up capability can significantly improve the current challenges in the real-time mine planning and reconciliation, where fast and reliable solutions are required. | ||
| کلیدواژهها | ||
| Graph Theory؛ HI-PR؛ Push–Relabel؛ Maximum Flow؛ Open Pit | ||
| مراجع | ||
|
[1]. Mousavi, A., Sayadi, A.R., and Fathianpour, N. (2016). A comparative study of kriging and simulation-based methods in classifying ore and waste blocks. Arabian Journal of Geosciences, 9(17): p. 691-700. [2]. Bakhtavar, E., Abdollahisharif, J., and Aminzadeh, A. (2017). A stochastic mathematical model for determination of transition time in the non-simultaneous case of surface and underground mining. Journal of the Southern African Institute of Mining and Metallurgy, 117 (12): p. 1145-1153. [3]. Lerchs, H. and Grossmann, I. (1965). Optimum design of open pit mines. Transaction on CIM, LX VIII: p. 17-24. [4]. Mousavi, A., (2015). Optimisation of open pit mine block sequencing. Queensland University of Technology: Australia. [5]. Zhao, Y. and Kim, Y.C. (1992). A new optimum pit limit design algorithm, in Proceedings of 23rd APCOP. Society for Mining, Metallurgy and Exploration: Littleton, Colorado. p. 423-434. [6]. Khalokakaie, R., Dowd, P.A., and Fowell, R.J. (2000). Lerchs–Grossmann algorithm with variable slope angles. Mining Technology, 109 (2): p. 77-85. [7]. Giannini, L., (1990). Optimum design of open pit mines. Curtin University of Technology: Perth. p. 166. [8]. Underwood, R. and Tolwinski, B. (1998). A mathematical programming viewpoint for solving the ultimate pit problem. European Journal of Operational Research, 107 (1): p. 96-107. [9]. Hochbaum, D.S. and Chen, A. (2000). Performance analysis and best implementations of old and new algorithms for the open pit mining problem. Operation research, 48 (6): p. 894-914. [10]. Koenigsberg, E., (1982). The Optimum Contours of an Open Pit Mine: an Application of Dynamic Programming, in Applications of Computers and Operations Research in the Mineral Industry (17th APCOM). New York. p. 274-287. [11]. Erarslan, K. and Celebi, N. (2001). A simulative model for optimum open pit design. CIM BULLETIN, 94(1055): p. 59-68. [12]. Najafi, M., Rafiee, R., and Jalali, S.M.E. (2020). Open pit limit optimization using dijkstra’s algorithm. International Journal of Mining and Geo-Engineering, 54 (1): p. 39-43. [13]. Pana, M.T., (1965). The simulation approach to open pit design, in Proceedings of the 5th APCOM Tucson, AZ. p. 139-144. [14]. Wright, A. (1999). A simple algorithm for optimum pit limits design, in Proceedings of the 28rd APCOM, Dagdelen, K., et al., Editors. Colorado School of Mines: Golden, Colorado. p. 367-374. [15]. Achireko, P., (1998). Application of modified conditional simulation and artificial neural networks to open pit optimization. Dalhousie University: Nova Scotia. [16]. Frimpon, S. and Achireko, P. (1997). The MCS/MFNN algorithm for open pit optimization. International Journal of Surface Mining, Reclamation and Environment, 11 (1): p. 45-52. [17]. Sayadi, A.R., Fathianpour, N., and Mousavi, A.A. (2011). Open pit optimization in 3D using a new artificial neural network. Archives of Mining Sciences, 56 (3): p. 389–403. [18]. Espejo, N., Nancel-Penard, P., and Morales, N. (2020). A methodology for automatic ramp design in open pit mines. Journal of Mining Engineering and Research, 1 (2). [19]. Bakhtavar, E., Shahriar, K., and Mirhassani, A. (2012). Optimization of the transition from open-pit to underground operation in combined mining using (0-1) integer programming. Journal of the Southern African Institute of Mining and Metallurgy, 112 (12): p. 1059-1064. [20]. Mergani, H., Osanloo, M., and Parichehp, M., (2019). Ultimate Pit Limit Determination Considering Mining Royalty in Open-Pit Copper Mines, in International Symposium on Mine Planning & Equipment Selection. Springer. p. 346-358. [21]. Hay, E., Nehring, M., Knights, P., and Kizil, M. (2019). Ultimate pit limit determination for semi mobile in-pit crushing and conveying system: a case study. International Journal of Mining, Reclamation and Environment: p. 1-21. [22]. Hay, E., Nehring, M., Knights, P., and Kizil, M.S. (2019). Ultimate pit limit determination for fully mobile in-pit crushing and conveying systems. International Journal of Mining and Mineral Engineering, 10 (2-4): p. 111-130. [23]. Meyer, M. (1969). Applying linear programming to the design of ultimate pit limits. Management Science, 16(2): p. B-121-B-135. [24]. Johnson, T.B. and Sharp, W.R., (1971). A Three-dimensional dynamic programming method for optimal ultimate open pit design. Vol. 7553. Bureau of Mines, US Department of the Interior. [25]. Frimpong, S. and Achireko, P.K. (1998). Conditional LAS stochastic simulation of regionalized variables in random fields. Computational Geosciences, 2 (1): p. 37-45. [26]. Erarslan, K. and Celebi, N. (2001). A simulative model for optimum open pit design. CIM Bulletin, 94: p. 59–68. [27]. Frimpong, S., Szymanski, J., and Narsing, A. (2002). A computational intelligent algorithm for surface mine layouts optimization. Simulation, 78(10): p. 600-611. [28]. Elahi, E., Kakaie, R., and Yusefi, A. (2012). A new algorithm for optimum open pit design: Floating cone method III. Journal of Mining and environment, 2 (2): p. 118-125. [29]. Wright, A., (1990). Open pit mine design model: introduction with Fortran 77 programs. Clausthal-Zellerfeld: Trans Tech Publications. [30]. Ahuja, R.K., Magnanti, T.L., and Orlin, J.B. (1993). Network flows : theory, algorithms, and applications. Prentice Hall. [31]. Cherkassky, B.V. and Goldberg, A.V. (1995). On implementing push-relabel method for the maximum flow problem, in International Conference on Integer Programming and Combinatorial Optimization. Springer. p. 157-171. [32]. Goldberg, A.V. (2009). Two-level push-relabel algorithm for the maximum flow problem, in International Conference on Algorithmic Applications in Management. Springer. p. 212-225. [33]. Espinoza, D., Goycoolea, M., Moreno, E., and Newman, A. (2013). MineLib: a library of open pit mining problems. Annals of operations research, 206 (1): p. 93-114. | ||
|
آمار تعداد مشاهده مقاله: 786 تعداد دریافت فایل اصل مقاله: 704 |
||