본문 바로가기
KERD
논문KCI 등재

휴리스틱 외판원 문제 알고리즘을 이용한 노천광산보조 작업 차량의 최적 이동경로 분석

Optimal Routes Analysis of Vehicles for Auxiliary Operations in Open-pit Mines using a Heuristic Algorithm for the Traveling Salesman Problem

박한수|최요순|박보영
한국암반공학회 (Korean Society for Rock Mechanics and Rock Engineering)|2014.02|터널과 지하공간 (TUNNEL AND UNDERGROUND SPACE)|제24권 제1호|pp. 11-20

1

조회

0

다운로드

3

인용

0

참고문헌

키워드

Optimal route노천광산Open-pit mine보조 작업 차량최적 이동경로휴리스틱 외판원 문제 알고리즘Auxiliary vehicleHeuristic TSP algorithm
주제분류자원공학

초록

본 연구에서는 노천광산에서 다수의 작업 지점들을 경유하며 광산 전역을 순회해야하는 보조 작업 차량의최적 이동경로를 분석하였다. Dijkstra‘s 알고리즘을 사용했던 기존의 연구들과 달리 휴리스틱 외판원 문제 알고리즘을 이용한 결과 다수의 작업지점들의 방문 순서까지 고려하여 보조 작업 차량의 최적 이동경로를 분석할수 있다. 인도네시아 파시르 석탄 노천광산의 로또 채광장을 대상으로 광산 전역을 정차 없이 순회하는 보조작업 차량의 최적 이동경로를 분석하였다. 그 결과 분석자의 직관에 따라 작업지점들의 방문 순서를 결정하는것보다 휴리스틱 TSP 알고리즘을 적용해 분석하는 것이 25개 지점 경유시 20분 정도의 이동시간을 단축할 수있는 것으로 분석되었다. 본 연구에서 제시한 결과가 노천광산 보조 작업 차량들의 시스템 최적화와 관련된향후 연구들의 방향설정 위해 기초자료로 활용될 수 있을 것이라 기대한다.

Abstract

This study analyzed the optimal routes of auxiliary vehicles in an open-pit mine that need to traversethe entire mine through many working points. Unlike previous studies which usually used the Dijkstra‘s algorithm,this study utilized a heuristic algorithm for the Traveling Salesman Problem(TSP). Thus, the optimal routes ofauxiliary vehicles could be determined by considering the visiting order of multiple working points. A case studyat the Pasir open-pit coal mine, Indonesia was conducted to analyze the travel route of an auxiliary vehicle thatmonitors the working condition by traversing the entire mine without stopping. As a result, we could know thatthe heuristic TSP algorithm is more efficient than intuitive judgment in determining the optimal travel route; 20minutes can be shortened when the auxiliary vehicle traverses the entire mine through 25 working points accordingto the route determined by the heuristic TSP algorithm. It is expected that the results of this study can be utilizedas a basis to set the direction of future research for the system optimization of auxiliary vehicles in open-pit mines.

참고문헌 (27)

  1. Alarie, S., "Overview of solution strategies used in truck dispatching systems for open pit mines", International Joural of Surface Mining, Reclamation and Environment, 16(1), pp.55~76 (2002)
  2. Bonates, E. J. L., "Mine Planning and Equipment Selection 1996", pp.51~57 (1996), Balkema
  3. Bonomi, E., "The N-City traveling salesman problem: statistical mechanics and the metropolis algorithm", SIAM Rev, 26(4), pp.551~568 (1984)
  4. 최요순, "광해방지를 위한 대규모 석탄 노천광의 배수설계 최적화", 한국자원공학회지, 43(5), pp.429~438 (2006), 한국자원공학회
  5. 최요순, "대규모 노천광산의 운반 효율성 향상을 위한 덤프트럭의 최적 운반경로 분석", 한국자원공학회지, 44(6), pp.477~491 (2007), 한국자원공학회
  6. 최요순, "노천광산의 관측점 선정 및 운반도로 가시거리 안전성 평가를 위한 GIS기반 가시구역 분석기법의 적용", 한국자원공학회지, 45(3), pp.265~275 (2008), 한국자원공학회
  7. Choi, Y., "Multi-criteria evaluation and least-cost path analysis for optimal haulage routing of dump trucks in large scale open-pit mines", International Journal of Geographical Information Science, 23(12), pp.1541~1567 (2009)
  8. Choi, Y., "Optimal haulage routing of off-road dump trucks in construction and mining sites using Google Earth and a modified least-cost path algorithm", Automation in Construction, 20(7), pp.982~997 (2011)
  9. Worst-case analysis of a new heuristic for the travelling salesman problem, "Christofides, N.", Graduate School of Industrial Administration, Carnegie-Mellon University, 5~, pp.Report 388 (1976)
  10. Dijkstra, E. W., "A note on two problems in connection with graphs", Numerische Mathmatik, 1, pp.269~271 (1959)
  11. Ercelebi, S. G., "Optimization of shovel-truck system for surface mining", The Journal of the Southern African Institute of Mining and Metallurgy, 109, pp.433~439 (2009)
  12. Fiechter, C. N., "A parallel tabu search algorithm for large traveling salesman problems", Discrete Applied Mathematics, 51(3), pp.243~267 (1994)
  13. Golden, B. L., "Using simulated annealing to solve routing and location problems", Naval Research Logistics Quarterly, 33(2), pp.261~279 (1986)
  14. Hart, P. E., "A formal basis for the heuristic determination of minimum cost paths", IEEE Transactions on Systems Science and Cybernetics, 4(2), pp.100~107 (1968)
  15. Hartman, H. L., "Introductory Mining Engineering", pp.108~ (2002), John Wiley & Sons
  16. Hays, R. M., "Surface mining", pp.672~691 (1990), Society for Mining, Metallurgy, and Exploration
  17. Kim, Y., "Meta Heuristic", pp.452~ (1997), Youngji Publishers
  18. Malek, M., "Serial and parallel simulated annealing and tabu search algorithms for the travelling salesman problem", Annals of Operations Research, 21, pp.59~84 (1989)
  19. Niemann-Delius, C., "Mine Planning and Equipment Selection 2004", pp.579~584 (2004), Taylor & Francis Group
  20. 박보영, "노천광산 덤프트럭의 최적 운반경로 분석을 위한 지형경사가고려된 벡터 네트워크 자료의 생성 방법", 터널과 지하공간, 23(5), pp.353~361 (2013), 한국암반공학회
  21. Rosenkrantz, D. J., "An analysis of several heuristics for the traveling salesman problem", SIAM Journal on Computing, 6(5), pp.563~581 (1977)
  22. Suboleski, S. C., "Mine Systems Engineering Lecture Notes", pp.1975
  23. 선우춘, "GIS에 의한 대규모 노천광에서의 배수처리 및 사면안정 예측", 터널과 지하공간, 17(5), pp.360~371 (2007), 한국암반공학회
  24. Tannant, D. D., "Guidelines for mine haul road design", pp.52~53 (2001), University of Alberta Press
  25. Temeng, V. A., "A computerized model for truck dispatching in open pit mines", 박사, pp.1997
  26. Thompson R. J., "Mine haul road maintenance management systems", Journal of the South African Institute of Mining and Metallurgy, 103(5), pp.303~312 (2003)
  27. Woeginger, G. J., "Exact algorithms for NP-hard problems: a survey, In: Jünger, M., Reinelt, G. and Rinaldi, G. (eds), Combinatorial Optimization — Eureka, You Shrink!", Lecture Notes in Computer Science, 2570, pp.185~207 (2003), Springer

관련 논문AI추천

대규모 노천광산의 운반 효율성 향상을 위한 덤프트럭의 최적 운반경로 분석박형동, 선우춘, 최요순한국자원공학회 · 한국자원공학회지2007 · 제44권 제6호노천광산 덤프트럭의 최적 운반경로 분석을 위한 지형경사가고려된 벡터 네트워크 자료의 생성 방법박보영, 박한수, 최요순한국암반공학회 · 터널과 지하공간2013 · 제23권 제5호트럭 고장 및 파쇄기 처리용량을 고려한 노천광산 쇼밸-트럭운반 시뮬레이션박세범, 박한수, 최요순한국암반공학회 · 터널과 지하공간2014 · 제24권 제1호트럭배차 방식을 고려한 노천광산 쇼밸-트럭 운반 시스템의 시뮬레이션박세범, 최요순한국자원공학회 · 한국자원공학회지2013 · 제50권 제4호노천광산의 관측점 선정 및 운반도로 가시거리 안전성 평가를 위한 GIS기반 가시구역 분석기법의 적용박형동, 서장원, 선우춘, 최요순한국자원공학회 · 한국자원공학회지2008 · 제45권 제3호GIS를 이용한 지하광산 디젤 차량의 운반작업 시 탄소배출량 산정박보영, 박세범, 박한수, 최요순한국암반공학회 · 터널과 지하공간2015 · 제25권 제4호

이 간행물의 다른 논문 (9건)

트럭 고장 및 파쇄기 처리용량을 고려한 노천광산 쇼밸-트럭운반 시뮬레이션최요순, 박한수, 박세범pp. 1-10EGS 실증연구사례 - 영국 Rosemanowes 프로젝트와 호주 Cooper Basin 프로젝트이재원, 김한나, 민기복, xielinmaopp. 21-31화강암 시험편의 광물조성과 기본마찰각의 상관성에 관한 연구최성웅, 이봉현, 이승중pp. 32-453DEC을 이용한 일정수직하중 조건에서의 전단강도에 관한 연구장원일, 김기호, 문홍주, 노영목pp. 46-54사진측량기법에 의한 절리조사 시스템 개발김기석, 김재동, 손영진, 정완순, 김종훈pp. 55-66
원문 보기