선박에서 수만 개의 케이블 경로를 결정하는 것은 복잡한 최적화 문제입니다. 각 케이블은 출발지(장비 A)에서 목적지(장비 B)까지 트레이 네트워크를 통해 이동해야 하며, 이 과정에서 케이블 길이 최소화, 트레이 포화 방지, 선급 분리 요건 준수를 동시에 만족해야 합니다. SEcMS는 이 문제를 Heap-Dijkstra 알고리즘으로 해결합니다.
1. 선박 케이블 라우팅 문제의 복잡성
케이블 라우팅은 단순한 최단 경로 문제가 아닙니다. 여러 제약 조건이 동시에 적용됩니다:
- 트레이 용량 제약: 충전율 한도를 초과한 트레이는 사용 불가
- 케이블 타입 분리: 전력·통신·내화 케이블은 별도 트레이 사용
- 격벽 관통 제한: A-0, A-60 격벽을 통과하는 관통부 수량 제한
- 금지 구역: 고온 구역, 폭발 위험 구역 우회 필수
- 최소 굴곡 반경: 케이블 타입별 허용 굴곡 반경 초과 불가
대형 선박에서 이 제약을 고려하면서 35,000개 케이블의 경로를 결정하는 것은 사람이 수개월을 투자해도 최적해를 보장하기 어렵습니다.
2. Dijkstra 알고리즘과 선박 적용
Dijkstra 알고리즘은 그래프에서 단일 출발점으로부터 모든 노드까지의 최단 경로를 구하는 고전적 알고리즘입니다. 선박 케이블 네트워크를 그래프로 모델링하면:
- 노드(Node): 트레이 교차점, 분기점, 장비 연결점
- 엣지(Edge): 트레이 구간 (길이 = 가중치)
- 제약(Constraint): 트레이 충전율, 케이블 타입, 금지 구역
Dijkstra 기본 동작 원리
1. 출발 노드의 거리를 0, 나머지를 무한대(∞)로 초기화
2. 최소 힙(Min-Heap)에서 최단 거리 노드 추출
3. 인접 노드의 거리를 갱신 (제약 만족 시에만)
4. 목적 노드에 도달할 때까지 2-3 반복
3. Heap 기반 최적화 — O(E log V)
기본 Dijkstra의 시간 복잡도는 O(V²)입니다. 35,000개 케이블, 수천 개 노드를 처리하려면 더 효율적인 구현이 필요합니다. SEcMS는 바이너리 힙(Binary Heap)을 사용한 Heap-Dijkstra를 구현하여 시간 복잡도를 O(E log V)로 줄였습니다.
힙 기반 구현의 핵심은 MinHeap 자료구조입니다. 각 노드를 거리 기준으로 힙에 삽입하고, 최소 거리 노드를 O(log N) 시간에 추출합니다. 이를 통해 대형 선박 규모의 네트워크도 수초 내에 처리할 수 있습니다.
4. 병렬 처리 — 4개 Web Worker
단일 스레드로 35,000개 케이블을 처리하면 브라우저 UI가 멈추는 문제가 발생합니다. SEcMS는 Web Worker 4개를 병렬로 운영하여 케이블을 분산 처리합니다.
| Worker 분류 | 대상 케이블 | 처리 우선순위 |
|---|---|---|
| HIGH Worker (2개) | 내화·비상 케이블 | 최우선 (선급 요건) |
| MID Worker (1개) | 전력·제어 케이블 | 중간 |
| LOW Worker (1개) | 통신·계장 케이블 | 낮음 |
Worker 수는 기기의 CPU 코어 수(navigator.hardwareConcurrency)를 자동 감지하여 조정됩니다. 8코어 기기에서는 최대 4개 Worker가 병렬로 동작합니다.
5. 가중치 함수 — 다목적 최적화
SEcMS의 라우팅 가중치는 단순 거리만 반영하지 않습니다. 다음 요소를 복합적으로 계산합니다:
- 기본 거리 (60%): 트레이 구간 물리적 길이
- 트레이 포화도 페널티 (25%): 충전율이 높은 트레이는 가중치 증가
- 격벽 관통 페널티 (10%): 관통부마다 추가 비용 부여
- 타입 불일치 페널티 (5%): 권장 경로 이탈 시 패널티
이 가중치 함수를 통해 케이블 길이만 최소화하는 것이 아니라 트레이 포화를 균일하게 분산하는 효과를 얻습니다.
6. 실패 경로 처리 — AI 보조
제약 조건이 너무 엄격하거나 트레이 네트워크에 단절이 있으면 일부 케이블은 경로를 찾지 못합니다(Failed Routes). SEcMS는 이를 AI 보조 모드로 처리합니다:
- 실패한 케이블 목록을 Groq AI에 전달
- AI가 제약을 완화하거나 대체 경로를 제안
- 엔지니어가 제안을 검토하고 수동으로 확인
English Summary: Cable Routing Optimization with Dijkstra
SEcMS implements a Heap-Dijkstra routing engine (O(E log V) complexity) for ship cable path optimization. The system models the cable tray network as a weighted graph where edges represent tray segments and nodes represent junction/branching points. Constraints including tray fill ratio limits, cable type segregation, and bulkhead penetration restrictions are encoded as edge weights and traversal conditions.
Parallel processing using 4 Web Workers enables routing of 35,000+ cables without blocking the browser UI. Worker assignment is based on cable priority (emergency circuits first) and dynamically scales to available CPU cores.
수동 라우팅으로 3주 걸리던 작업이 SEcMS에서는 2시간 안에 완료됩니다. 단, 결과는 항상 엔지니어가 검토하고 승인합니다.