2D 불규칙 네스팅

정의

불규칙한(비직사각형) 2D 부품들을 원자재 위에 겹치지 않게, 시트 경계 안에 배치하여 재료 활용도를 최대화한다.

예시

예컨대 “L”자 부품 두 개를 각자의 바운딩 박스대로 따로 놓으면 두 사각형이 차지하는 면적이 크다. 그러나 한 부품을 180° 돌려 다른 부품의 오목한 부분에 끼워 맞추면(맞물림), 같은 시트에서 훨씬 작은 영역에 들어간다. 이렇게 직사각형 근사 대신 부품의 실제 윤곽(true shape)을 활용해 빈틈을 줄이는 것이 불규칙 네스팅의 핵심 이득이다.

산업별 명칭

같은 기하학적 핵심이 여러 산업 명칭으로 나타난다:

• 조선(Shipbuilding) — 강재판 네스팅(plate nesting), 강판 부품 네스팅
• 의류(Apparel) — 마커 메이킹(marker making), 레이 플래닝(lay planning)
• 판금(Sheet-metal fabrication) — 트루셰이프 네스팅(true-shape nesting)

이들은 느슨한 유추가 아니라, 하나의 추상 문제의 산업적 사례이며, 주로 부가 제약(side constraints) 에서 차이가 난다(아래 “교차 도메인 유사물” 참고).

형식 모델

• 입력: 다각형 부품 집합(구멍이 있을 수 있음), 하나 이상의 원자재 시트, 부품별 허용 회전.
• 결정 변수: 각 부품 $i$의 배치 위치 $(x_i, y_i)$와 방향 $\theta_i$.
• 목적: 보통 사용 시트 길이(스트립 변형)나 시트 개수를 최소화 — 즉 활용도 최대화.
• 제약: 쌍별 비겹침; 시트 내 포함; 허용 회전 집합; (산업에 따라) 간격·결 방향·절단 제약.

복잡도

불규칙 네스팅은 NP-난해(NP-hard)다. 소규모 인스턴스에는 정확해법(exact)이 존재하지만, 산업 규모 인스턴스는 최적성을 보장하는 솔버보다 구성적 휴리스틱과 메타휴리스틱으로 다룬다. [등급 B — 서베이 수준]

핵심 제약

• 비겹침 배치 (어려운 기하학적 핵심)
• 시트 경계 내 포함(containment)
• 회전 — 자유, 이산 집합, 또는 고정(의류의 결 방향이 흔히 고정)
• 재료 방향 / 결(grain) (의류, 일부 복합재)
• 커프(kerf) 와 절단 경로 제약 (판금, 조선)
• 베벨·브리지·공통 절단(common-cut) 제조 가능성 (조선)

알고리즘 계열

• 구성적(Constructive) — 바텀-레프트 / 바텀-레프트-필 배치 규칙
• 기하 기본 연산 — 무적합 다각형(No-Fit Polygon, 겹침 판정), 민코프스키 합
• 메타휴리스틱 — 순서·방향에 대한 유전 알고리즘·시뮬레이티드 어닐링·타부 서치, 내부 루프로 배치 휴리스틱 사용
• 학습 기반 — 강화학습 접근이 최근 문헌에서 벤치마크 조건 하에 보고되었으나, 산업적 활용 성숙도는 여기서 단정하지 않는다. [미검증 — 등급 A 출처 미기록]

벤치마크

• 직접: 불규칙 네스팅을 위한 ESICUP 커뮤니티 인스턴스.
• 인접: 2DPackLib — 2차원 직교 절단·적재를 대상으로 하므로 방법론적으로는 관련 있으나 직접 불규칙 벤치마크는 아니다. has_adjacent_benchmark로 명시 기록한다.

도구

상용 트루셰이프 네스팅 도구는 벤더 보고(등급 C)이며, 추상 문제에 직접 연결되기보다 특정 응용 문제에 연결된다 — 조선 강재판 네스팅, 판금 트루셰이프 네스팅 페이지를 참고하라.

교차 도메인 유사물

조선 강재판 네스팅, 의류 마커 메이킹, 판금 트루셰이프 네스팅은 비겹침 배치라는 핵심을 공유한다(E1_variant 관계). 다른 점은 부가 제약이다: 조선은 절단 경로·브리지·베벨 제조 가능성을 더하고, 의류는 결/방향 고정과 패턴 매칭을, 판금은 커프와 공통선 절단을 더한다. 등가성 과 차이를 함께 기록하는 것이 핵심이다 — 증거 정책을 참고하라.

열린 질문

• 학습 기반 방법은 단일 벤치마크 보고를 넘어 산업별 부가 제약 집합 전반으로 얼마나 일반화되는가?
• "같은 문제, 다른 제약"(E1)과 진정으로 별개인 정식화의 경계는 어디인가?

관련 노드

아래 그래프는 직접(깊이 1) 이웃을 보여준다. 방법은 보라색, 벤치마크는 호박색이며, 점선 엣지는 인접(직접이 아닌) 벤치마크를 나타낸다.