경로 최적화 문제는 오늘날 우리의 일상생활과 산업기술에 매우 많이 적용되는 문제이다. 전자회로기판 설계부터 대형 산업현장의 전력설비 설계까지 다양한 분야에서 활용되며 꾸준히 연구되고 있다. 원자력발전소 같은 대형 건설프로젝트에서는 약 8,000km가 넘는 케이블이 설계된다. 이러한 케이블의 설계는 자재비, 시공비와 프로젝트 일정관리에도 영향을 미치고 있다.
최근 유럽에서는 신재생에너지인 해상풍력발전소의 설비 배치 최적화와 송전 선로에 대한 경로 최적화 연구가 활발히 진행 중이다. 국내 대형 전력설계회사에서는 케이블 경로 설계프로그램을 개발하여 원자력발전소 등의 케이블 경로 설계에 적용하고 있다. 그러나 케이블 경로 설계 시 설비의 위치와 트레이 정보를 기반으로 휴리스틱 기법(Heuristic method)인 “A* 알고리즘”을 적용하여 케이블 경로를 설계하고 있다. 이는 트레이를 먼저 설계하고 케이블을 나중에 설계하므로 케이블과 트레이 라우팅이 최적화되었다고 볼 수는 없다. 대형 건설프로젝트에서 케이블과 트레이 라우팅은 건설비용과 일정에 많은 영향을 미치는 중요한 문제이다. 그러므로, 다중 전력케이블과 트레이 라우팅을 동시에 최적화할 필요가 있다.
본 연구에서는 3차원 공간에서 케이블과 트레이 비용을 최소화하는 다중 전력케이블과 트레이 라우팅 문제를 다루었다. 케이블과 트레이의 전반적인 라우팅을 최적화하기 위해 먼저 각각의 케이블 경로를 구한다. 그리고 최소비용 조건에서 개별 케이블들의 경로를 개선하여 케이블과 트레이 라우팅을 동시에 최적화하는 문제 모형과 알고리즘을 구현하였다. 알고리즘은 최적해 기법과 휴리스틱 기법을 적용하였다.
최적해 기법은 두 단계로 구분된다. 첫 단계는 먼저 각각의 케이블별로 비열등 경로를 모두 탐색한다. 단일 케이블의 비열등 경로에 대한 탐색 알고리즘은 다시 5개의 상세단계(Initialization, Forward, Feasibility & Dominance Test, Route Completion Test, Back-Tracking)로 구분된다. 그리고 단계별 순환 구조로 반복하여 모든 경로를 탐색한다. 두 번째 단계는 각 케이블에 대한 비열등 경로의 조합을 탐색하여 최적의 경로 조합을 찾는다.
문제의 크기가 커지면 현실적인 시간 안에 최적해를 찾을 수 없게 된다. 이때 휴리스틱 기법이 필요하다. 본 논문에서 제시한 휴리스틱 기법은 세 단계로 구분된다. 첫 단계는 앞서 언급한 최적해 기법을 통해 케이블별로 미리 설정한 수만큼 비열등 경로를 생성한다. 그리고 두 번째 단계는 각각의 케이블에 대한 비열등 경로 하나를 임의로 선택한다. 세 번째 단계는 개선규칙 3가지를 사용하여 두 번째 단계에서 구한 해를 개선한다. 그리고 두 번째와 세 번째 단계를 반복하며, 미리 정한 반복 횟수나 연산시간에 도달하면 종료한다.
모의실험은 길이의 크기() 40, 너비의 크기() 40, 높이의 크기() 8인 데이터셋(단위 길이가 1인 3차원 정육면체 격실 12,800개로 구성된 해의 공간)을 포함하여 총 4개의 데이터셋으로 실험하였다. 데이터셋별 10개의 문제를 생성하고 문제별 40개의 케이블과 트레이의 경로를 탐색하는 알고리즘의 효용성을 확인하였다.
본 연구의 중요한 성과는 3차원 공간기반 다중 전력케이블과 트레이를 동시에 최적 라우팅을 찾는 문제의 모형 및 수식화, 알고리즘 및 코딩 그리고 모의실험을 통해 중요하면서 아직 정립되지 않은 문제를 체계적으로 다룰 수 있는 해법이 개발되었다는 것이다.
본 연구에서는 학술적 연구를 위해 현장의 제약조건중 공통적인 부분을 추려 단순화하고 기본적인 연구모형을 만들어 알고리즘을 개발하였다. 그러나 실제 현장은 복잡한 제약조건을 갖고 있으므로 현장의 조건에 맞도록 제약조건과 목적함수를 조금만 수정하여 알고리즘을 보완한다면 다양한 산업 분야의 복잡한 라우팅 문제에 적용할 수 있을 것이다. 그 이유는 문제와 관련된 해의 공간은 변함이 없으므로 제안된 해법의 효용성에는 변화가 없기 때문이다.
향후 연구과제는 트레이의 허용 단면적, 다양한 케이블 크기, 트레이의 복층 구조, 특정 경로의 화재방화재(fire wrapping) 적용 그리고 더 큰 해의 영역 반영 등 현장 여건에 맞도록 제약조건과 목적함수를 수정하고 알고리즘을 구현하는 연구가 필요하다.

Routing optimization is a very common problem in our daily lives and industrial technologies today. It is utilized and researched in various fields from the printed circuit board (PCB) design in mobile phones to the design of power facilities in large industrial sites. In large construction projects, such as nuclear power plants that have over 8,000km of cable installed, bulk cables affect material costs, construction costs and project schedules.
In Europe, research on optimizing layout and cable routing for the transmission line of wind farms is being actively conducted in the field of renewable energy. A large domestic power plant design company has a cable path design program that it developed by itself. The company is applying this cable path design to nuclear power plants. In the path design, heuristic method A* algorithm is applied. The cable routing program was designed based on the location of the equipment and tray information in the power plant building. Therefore, the cable and tray path was not optimized at the same time.
In this paper, the researcher deal with the problem of multiple cable routing decisions to minimize cable and tray costs in three-dimensional space. First, each cable is routed to optimize the overall routing of cables and trays. Next, each cable path is integrated at the lowest cost to optimize the routing of the entire cable and tray.
The optimization technique is divided into two stages. The first step is to find all non-inferior paths for each cable. The process of finding a non-inferior path of a single cable is composed of five steps(Initial solution, Forward, Feasibility & Dominance Test, Route Completion Test, Back-Tracking). This process finds all paths through step-by-step cycles and iterations.
Heuristic techniques are necessary when the problem is so large that the optimal solution can be found in a reasonable amount of time. Then, the second step randomly selects a non-inferior path for each cable. The third step uses three improvement rules to improve the solution obtained in the second step. And a better solution is obtained by repeating the second and third steps. The algorithm ends when a predetermined number of iterations or the amount of time is reached.
The simulation was performed in three-dimensional space that consisted of 40 nodes on L(length)-axes, 40 nodes on W(width)-axes and 8 nodes on H(height)-axes. The researcher confirmed the effectiveness of the proposed heuristic for routing 40 cables and trays in that space.
An important result of this study is to propose a mathematical model of 3D space-based cable path problems and to propose an optimization/heuristic technique for finding multiple cables and cable trays simultaneously.
In the future, further research needs to solve the routing problem considering the limited cross-sectional area of the tray and to improve the search speed by adding realistic constraints in the larger three-dimensional space.