2D 불규칙 네스팅

정의

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

산업별 명칭

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

• 조선(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) 이웃을 보여준다. 방법은 보라색, 벤치마크는 호박색이며, 점선 엣지는 인접(직접이 아닌) 벤치마크를 나타낸다.