Optimizing the exploratory drilling rig route based on the Multi-Objective Multiple Traveling Salesman Problem

Document Type : Research Paper

Authors

Department of Mining Engineering, University of Kashan, Kashan. Iran.

Abstract

Exploratory drilling is one of the most important and costly stages of mineral exploration procedures, so the continuation of mining activities depends on the gathered data during this stage. Due to the importance of cost and time-saving in the performance of mineral exploration projects, the effective parameters for reducing the cost and time of drilling activities should be investigated and optimized. Road construction and the sequence of the drilling boreholes by drilling rigs are among these parameters. The main objectives of this research were to optimize the overall road construction cost and the difference in length drilled by each drilling rig. The problem has been modeled as a Multi-Objective Multiple Traveling Salesman Problem (MOmTSP) and solved by the Non-dominated Sorting Genetic Algorithm-II (NSGA-II). Finally; the Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) method has been used to find the optimal solution among the solutions obtained by the NSGA-II.

Keywords

Main Subjects

References

[1]    Chou, D. (1982) Optimizing exploratory drilling locations.
[2]    Scheck, D.E. and Chou, D.-R. (1983) Optimum locations for exploratory drill holes. International Journal of Mining Engineering, Springer. 1, 343–55.
[3]    Liao, X., Khandelwal, M., Yang, H., Koopialipoor, M. and Murlidhar, B.R. (2020) Effects of a proper feature selection on prediction and optimization of drilling rate using intelligent techniques. Engineering with Computers, Springer. 36, 499–510.
[4]    Moon, C.J., Whateley, M.K.G. and Evans, A.M. (2006) Introduction to mineral exploration. Blackwell publishing.
[5]    Irawan, S., Rahman, A. and Tunio, S. (2012) Optimization of weight on bit during drilling operation based on rate of penetration model. Research Journal of Applied Sciences, Engineering and Technology, 4, 1690–5.
[6]    Derdour, F.Z., Kezzar, M. and Khochemane, L. (2018) Optimization of penetration rate in rotary percussive drilling using two techniques: Taguchi analysis and response surface methodology (RMS). Powder Technology, Elsevier. 339, 846–53.
[7]    Drew, L.J. (1967) Grid-drilling exploration and its application to the search for petroleum. Economic Geology, Society of Economic Geologists. 62, 698–710.
[8]    Drew, L.J. (1979) Pattern drilling exploration: Optimum pattern types and hole spacings when searching for elliptical shaped targets. Journal of the International Association for Mathematical Geology, Kluwer Academic Publishers-Plenum Publishers. 11, 223–54. https://doi.org/10.1007/BF01028966
[9]    Griffiths, J.C. and Drew, L.J. (1966) Grid spacing and success ratios in exploration for natural resources: The Pennsylvania State Univ. Min Ind Expmt Stat, Special Publ.
[10]  Soltani, S., Hezarkhani, A., Tercan, A.E. and Karimi, B. (2011) Use of genetic algorithm in optimally locating additional drill holes. Journal of Mining Science, Springer. 47, 62–72.
[11]   Lamas, L.F., Botechia, V.E., Schiozer, D.J. and Delshad, M. (2017) Optimization for drilling schedule of wells in the development of heavy oil reservoirs. Brazilian Journal of Petroleum and Gas, 11.
[12]  Wang, L. and Oliver, D.S. (2019) Efficient Optimization of Well-Drilling Sequence with Learned Heuristics. SPE Journal, OnePetro. 24, 2111–34.
[13]  Kulachenko, I. and Kononova, P. (2020) A matheuristic for the drilling rig routing problem. International Conference on Mathematical Optimization Theory and Operations Research, Springer.  p. 343–58.
[14]  Kulachenko, I.N. and Kononova, P.A. (2021) A hybrid algorithm for the drilling rig routing problem. Journal of Applied and Industrial Mathematics, Springer. 15, 261–76.
[15]  Bektas, T. (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega, Elsevier. 34, 209–19.
[16]  Carter, A.E. and Ragsdale, C.T. (2006) A new approach to solving the multiple traveling salesperson problem using genetic algorithms. European Journal of Operational Research, Elsevier. 175, 246–57.
[17]  Tang, L., Liu, J., Rong, A. and Yang, Z. (2000) A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. European Journal of Operational Research, Elsevier. 124, 267–82.
[18]  Király, A. and Abonyi, J. (2010) A novel approach to solve multiple traveling salesmen problem by genetic algorithm. Computational Intelligence in Engineering, Springer.  p. 141–51.
[19]  Singh, A. (2016) A review on algorithms used to solve multiple travelling salesman problem. International Research Journal of Engineering and Technology (IRJET), 3, 598–603.
[20] Alves, R.M.F. and Lopes, C.R. (2015) Using genetic algorithms to minimize the distance and balance the routes for the multiple traveling salesman problem. 2015 IEEE Congress on Evolutionary Computation (CEC), IEEE.  p. 3171–8.
[21]  Xu, Z., Li, Y. and Feng, X. (2008) Constrained multi-objective task assignment for UUVs using multiple ant colonies system. 2008 ISECS International Colloquium on Computing, Communication, Control, and Management, IEEE.  p. 462–6.
[22] Chang, T.-S. and Yen, H.-M. (2012) City-courier routing and scheduling problems. European Journal of Operational Research, Elsevier. 223, 489–98.
[23]  Bolaños, R., Echeverry, M. and Escobar, J. (2015) A multiobjective non-dominated sorting genetic algorithm (NSGA-II) for the Multiple Traveling Salesman Problem. Decision Science Letters, 4, 559–68.
[24] Shuai, Y., Yunfeng, S. and Kai, Z. (2019) An effective method for solving multiple travelling salesman problem based on NSGA-II. Systems Science & Control Engineering, Taylor & Francis. 7, 108–16.
[25]  Wei, C., Ji, Z. and Cai, B. (2020) Particle swarm optimization for cooperative multi-robot task allocation: a multi-objective approach. IEEE Robotics and Automation Letters, IEEE. 5, 2530–7.
[26]  Necula, R., Breaban, M. and Raschip, M. (2015) Tackling the bi-criteria facet of multiple traveling salesman problem with ant colony systems. 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), IEEE.  p. 873–80.
[27]  Wang, X., Gu, X., Liu, Z., Wang, Q., Xu, X. and Zheng, M. (2018) Production process optimization of metal mines considering economic benefit and resource efficiency using an NSGA-II model. Processes, Multidisciplinary Digital Publishing Institute. 6, 228.
[28] Gu, X., Wang, X., Liu, Z., Zha, W., Xu, X. and Zheng, M. (2020) A multi-objective optimization model using improved NSGA-II for optimizing metal mines production process. IEEE Access, IEEE. 8, 28847–58.
[29] Foroughi, S., Hamidi, J.K., Monjezi, M. and Nehring, M. (2019) The integrated optimization of underground stope layout designing and production scheduling incorporating a non-dominated sorting genetic algorithm (NSGA-II). Resources Policy, Elsevier. 63, 101408.
[30]  Zhang, W., Yuan, Q., Jia, S., Li, Z.S. and Yin, X. (2021) Multi-Objective Optimization of Froth Flotation Process: An Application in Gold Ore. Sustainability, Multidisciplinary Digital Publishing Institute. 13, 8314.
[31]  Holland, J.H. (1975) Adaptation in Natural and Artificial Systems.
[32]  Malmborg, C.J. (1996) A genetic algorithm for service level based vehicle scheduling. European Journal of Operational Research, Elsevier. 93, 121–34.
[33]  Singamsetty, P. and Thenepalle, J. (2021) An efficient genetic algorithm for solving open multiple travelling salesman problem with load balancing constraint. Decision Science Letters, 10, 525–34.
[34]  De Jong, K.A. (1975) An analysis of the behavior of a class of genetic adaptive systems. University of Michigan.
[35]  Davis, L. (1985) Applying adaptive algorithms to epistatic domains. IJCAI, p. 162–4.
[36]  Goldberg, D.E. and Lingle, R. (1985) Alleles, loci, and the traveling salesman problem. Proceedings of an International Conference on Genetic Algorithms and Their Applications, Carnegie-Mellon University Pittsburgh, PA.  p. 154–9.
[37] Yang, S. (2002) Adaptive non-uniform mutation based on statistics for genetic algorithms. ACM.
[38]  Albayrak, M. and Allahverdi, N. (2011) Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms. Expert Systems with Applications, 38, 1313–20. https://doi.org/10.1016/j.eswa.2010.07.006
[39]  Abdoun, O., Abouchabaka, J. and Tajani, C. (2012) Analyzing the Performance of Mutation Operators to Solve the Travelling Salesman Problem.
[40] Deep, K. and Mebrahtu, H. (2011) Combined mutation operators of genetic algorithm for the travelling salesman problem. International Journal of Combinatorial Optimization Problems and Informatics, International Journal of Combinatorial Optimization Problems and Informatics. 2, 1–23.
[41]  Eiben, A.E. and Smith, J.E. (2003) Introduction to evolutionary computing. Springer.
[42] Oliver, I.M., Smith, D.J. and Holland, J.R.C. (1987) A study of permutation crossover operators on the TSP, genetic algorithms and their applications. Proceedings of the Second International Conference on Genetic Algorithms, p. 224–30.
[43]  Fogel, D.B. (1988) An evolutionary approach to the traveling salesman problem. Biological Cybernetics, Springer. 60, 139–44.
[44] Fogel, D.B. (1990) A parallel processing approach to a multiple travelling salesman problem using evolutionary programming. Proceedings of the Fourth Annual Symposium on Parallel Processing, Fullerton, CA.  p. 318–26.
[45]  Fogel, D.B. (1993) Applying evolutionary programming to selected traveling salesman problems. Cybernetics and Systems, Taylor & Francis. 24, 27–36.
[46]  Michalewicz, Z. (1992) Genetic Algorithms + Data Structures = Evolution Programs. Springer Berlin Heidelberg, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-02830-8
[47]  Deb, K., Agrawal, S., Pratap, A. and Meyarivan, T. (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. International Conference on Parallel Problem Solving from Nature, Springer.  p. 849–58.
[48] Hwang, C.-L. and Yoon, K. (1981) Multiple Attribute Decision Making. Springer Berlin Heidelberg, Berlin, Heidelberg. 186. https://doi.org/10.1007/978-3-642-48318-9
International Journal of Mining and Geo-Engineering
Volume 56, Issue 4
December 2022
Pages 331-337

Files

Share

How to cite

Statistics