휴리스틱 외판원 문제 알고리즘을 이용한 노천광산 보조 작업 차량의 최적 이동경로 분석 = Optimal Routes Analysis of Vehicles for Auxiliary Operations in Open-pit Mines using a Heuristic Algorithm for the Traveling Salesman Problem

국문 초록 (Abstract)

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

다국어 초록 (Multilingual Abstract)

This study analyzed the optimal routes of auxiliary vehicles in an open-pit mine that need to traverse the 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 of auxiliary vehicles could be determined by considering the visiting order of multiple working points. A case study at the Pasir open-pit coal mine, Indonesia was conducted to analyze the travel route of an auxiliary vehicle that monitors the working condition by traversing the entire mine without stopping. As a result, we could know that the heuristic TSP algorithm is more efficient than intuitive judgment in determining the optimal travel route; 20 minutes can be shortened when the auxiliary vehicle traverses the entire mine through 25 working points according to the route determined by the heuristic TSP algorithm. It is expected that the results of this study can be utilized as a basis to set the direction of future research for the system optimization of auxiliary vehicles in open-pit mines.

목차 (Table of Contents)

• Abstract
• 초록
• 1. 서론
• 2. 연구지역
• 3. 연구방법
• 4. 알고리즘 적용 및 결과
• 5. 결론
• References

참고문헌 (Reference)

1 최요순, "대규모 노천광산의 운반 효율성 향상을 위한 덤프트럭의 최적 운반경로 분석" 한국자원공학회 44 (44): 477-491, 2007

2 최요순, "노천광산의 관측점 선정 및 운반도로 가시거리 안전성 평가를 위한 GIS기반 가시구역 분석기법의 적용" 한국자원공학회 45 (45): 265-275, 2008

3 박보영, "노천광산 덤프트럭의 최적 운반경로 분석을 위한 지형경사가고려된 벡터 네트워크 자료의 생성 방법" 한국암반공학회 23 (23): 353-361, 2013

4 최요순, "광해방지를 위한 대규모 석탄 노천광의 배수설계 최적화" 한국자원공학회 43 (43): 429-438, 2006

5 Christofides, N., "Worst-case analysis of a new heuristic for the travelling salesman problem" Graduate School of Industrial Administration, Carnegie-Mellon University 5-, 1976

6 Golden, B. L., "Using simulated annealing to solve routing and location problems" 33 (33): 261-279, 1986

7 Bonomi, E., "The N-City traveling salesman problem: statistical mechanics and the metropolis algorithm" 26 (26): 551-568, 1984

8 Hays, R. M., "Surface mining" Society for Mining, Metallurgy, and Exploration 672-691, 1990

9 Malek, M., "Serial and parallel simulated annealing and tabu search algorithms for the travelling salesman problem" 21 : 59-84, 1989

10 Alarie, S., "Overview of solution strategies used in truck dispatching systems for open pit mines" 16 (16): 55-76, 2002

11 Ercelebi, S. G., "Optimization of shovel-truck system for surface mining" 109 : 433-439, 2009

12 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" 20 (20): 982-997, 2011

13 Choi, Y., "Multi-criteria evaluation and least-cost path analysis for optimal haulage routing of dump trucks in large scale open-pit mines" 23 (23): 1541-1567, 2009

14 Thompson R. J., "Mine haul road maintenance management systems" 103 (103): 303-312, 2003

15 Suboleski, S. C., "Mine Systems Engineering Lecture Notes" The Pennsylvania State University 1975

16 Niemann-Delius, C., "Mine Planning and Equipment Selection 2004" Taylor & Francis Group 579-584, 2004

17 Bonates, E. J. L., "Mine Planning and Equipment Selection 1996" Balkema 51-57, 1996

18 Kim, Y., "Meta Heuristic" Youngji Publishers 452-, 1997

19 Hartman, H. L., "Introductory Mining Engineering" John Wiley & Sons 108-, 2002

20 Tannant, D. D., "Guidelines for mine haul road design" University of Alberta Press 52-53, 2001

21 선우춘, "GIS에 의한 대규모 노천광에서의 배수처리 및 사면안정 예측" 한국암반공학회 17 (17): 360-371, 2007

22 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!" Springer 2570 : 185-207, 2003

23 Rosenkrantz, D. J., "An analysis of several heuristics for the traveling salesman problem" 6 (6): 563-581, 1977

24 Fiechter, C. N., "A parallel tabu search algorithm for large traveling salesman problems" 51 (51): 243-267, 1994

25 Dijkstra, E. W., "A note on two problems in connection with graphs" 1 : 269-271, 1959

26 Hart, P. E., "A formal basis for the heuristic determination of minimum cost paths" 4 (4): 100-107, 1968

27 Temeng, V. A., "A computerized model for truck dispatching in open pit mines" Michigan Technological University 1997