2D 빈 패킹

직사각형을 최소 개수의 고정 크기 빈에 채우기.

다른 이름: 2D Bin Packing · 이차원 빈 패킹 · 2BP · 직사각형 빈 패킹

정의

축 정렬 직사각형을 겹치지 않게 동일한 고정 크기 빈에 채워, 사용 빈 개수를 최소화한다.

예시

빈 크기 $4\times4$ , 부품이 $4\times2$ 두 개와 $2\times2$ 두 개라고 하자. 한 빈에 $4\times2$ 두 개를 위아래로 쌓으면 정확히 가득 차고( $4\times4$ ), 나머지 $2\times2$ 두 개는 두 번째 빈 바닥에 나란히 놓인다. 최소 사용 빈은 2개다 — 총 면적이 $8+8+4+4=24$ 로 빈 한 개의 16을 넘어 1개로는 불가능하다.

계열

2D 스트립 패킹, 2D 배낭과 함께 Wäscher 외 분류 체계의 핵심 직교 절단·적재 문제 중 하나다. 기하(직사각형 한정)에서 불규칙 네스팅과 대비되지만, 해법 방법론의 일부는 공유한다.

벤치마크

2DPackLib이 직접 벤치마크다(등급 A).

주장 & 증거

모든 관계는 증거 등급을 가진 하나의 주장이고, 문제 간 관계에는 해당되는 경우 등가 수준도 표시합니다. 증거 정책을 참고하세요.

A–X는 근거의 신뢰도, E0–E4는 문제 사이의 수학적 유사도입니다. 두 축은 서로 독립적입니다.

이 항목에서 나가는 관계 9

방법 공유
2D 빈 패킹에서 2D 스트립 패킹로
2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
직접 벤치마크
2D 빈 패킹에서 2DPackLib로
2DPackLib은 2차원 직교 빈 패킹의 표준 인스턴스를 제공한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library
  서지정보
  Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
사용 방법
2D 빈 패킹에서 분기 한정 (Branch and Bound)로
2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 빈 패킹에서 감소 우선 적합 (First-Fit Decreasing)로
감소 우선 적합(FFD) 계열의 구성적 휴리스틱이 빈 패킹의 빠른 근사해에 널리 쓰인다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 빈 패킹에서 유전 알고리즘 (Genetic Algorithm)로
2D 빈 패킹은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 빈 패킹에서 정수 선형 계획법 (Integer Linear Programming)로
2D 빈 패킹은 정수 선형 계획(ILP) 모델로 정식화되며, 이는 분기 한정·분기-가격 같은 정확 해법의 출발점이다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 빈 패킹에서 하한 (Lower Bounds)로
2D 빈 패킹의 정확 해법은 면적 하한과 Martello–Toth류 이산 하한 등 강한 하한으로 탐색을 가지친다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법
2D 빈 패킹에서 열 생성 (Column Generation)로
2D 빈 패킹의 정확 접근은 열 생성/분기-가격으로 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem
  서지정보
  Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
사용 방법
2D 빈 패킹에서 타부 서치 (Tabu Search)로
2D 빈 패킹은 타부 서치 기반 탐색으로도 보고되어 왔다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey
  서지정보
  Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

이 항목에서 나가는 관계
관계	주장	증거	등가	출처
방법 공유 2D 빈 패킹에서 2D 스트립 패킹로	2D 빈 패킹과 스트립 패킹은 구성적·정확 방법을 공유하며, 단일 빈을 채울 때 스트립 패킹이 부분문제로 자주 등장한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
직접 벤치마크 2D 빈 패킹에서 2DPackLib로	2DPackLib은 2차원 직교 빈 패킹의 표준 인스턴스를 제공한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서2DPackLib: a two-dimensional cutting and packing library 서지정보 Iori, M., de Lima, V.L., Martello, S., Monaci, M. (2022). 2DPackLib: a two-dimensional cutting and packing library. Optimization Letters. Focuses on two-dimensional orthogonal cutting and packing instances.
사용 방법 2D 빈 패킹에서 분기 한정 (Branch and Bound)로	2D 빈 패킹의 정확 접근은 분기 한정(및 분기-가격) 정식화로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 빈 패킹에서 감소 우선 적합 (First-Fit Decreasing)로	감소 우선 적합(FFD) 계열의 구성적 휴리스틱이 빈 패킹의 빠른 근사해에 널리 쓰인다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 빈 패킹에서 유전 알고리즘 (Genetic Algorithm)로	2D 빈 패킹은 유전 알고리즘 등 메타휴리스틱으로도 다뤄져 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 빈 패킹에서 정수 선형 계획법 (Integer Linear Programming)로	2D 빈 패킹은 정수 선형 계획(ILP) 모델로 정식화되며, 이는 분기 한정·분기-가격 같은 정확 해법의 출발점이다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 빈 패킹에서 하한 (Lower Bounds)로	2D 빈 패킹의 정확 해법은 면적 하한과 Martello–Toth류 이산 하한 등 강한 하한으로 탐색을 가지친다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.
사용 방법 2D 빈 패킹에서 열 생성 (Column Generation)로	2D 빈 패킹의 정확 접근은 열 생성/분기-가격으로 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem 서지정보 Pisinger, D., Sigurd, M. (2007). Using Decomposition Techniques and Constraint Programming for Solving the Two-Dimensional Bin-Packing Problem. INFORMS Journal on Computing 19(1):36-51. A Dantzig-Wolfe / branch-and-price-and-cut exact method for 2D bin packing.
사용 방법 2D 빈 패킹에서 타부 서치 (Tabu Search)로	2D 빈 패킹은 타부 서치 기반 탐색으로도 보고되어 왔다.	B · 서베이 / 튜토리얼 / 커뮤니티	—	출처 등급: A — 동료심사 논문 / 공식 문서Two-dimensional packing problems: A survey 서지정보 Lodi, A., Martello, S., Monaci, M. (2002). Two-dimensional packing problems: A survey. EJOR 141(2):241-252. Surveys lower bounds, exact (branch-and-bound), shelf/heuristic, and metaheuristic methods for two-dimensional bin packing and strip packing.

이 항목으로 들어오는 관계 8

방법 공유
1D 절단 재고에서 2D 빈 패킹로
1D 절단 재고와 빈 패킹은 같은 절단·적재 계열의 밀접한 구성원이며, 둘 다 패턴/구성 정식화로 다뤄진다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E3 · 구조적 유추
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유
2D 불규칙 네스팅에서 2D 빈 패킹로
불규칙 네스팅과 2D 빈 패킹은 같은 절단·적재 계열로서 메타휴리스틱 탐색 방법론을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유
2D 배낭 (직사각형)에서 2D 빈 패킹로
2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화
3D 빈 패킹에서 2D 빈 패킹로
3D 빈 패킹은 2D 빈 패킹의 고차원 일반화이며, 다수의 구성적·탐색 방법을 공유한다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계
길로틴 절단에서 2D 빈 패킹로
길로틴 절단은 절단이 변에서 변까지 직선이어야 한다는 추가 제약이 붙은 2D 직교 절단·적재의 변형이다.
증거A · 동료심사 논문 / 공식 문서
등가E1 · 같은 기반, 다른 부가 제약
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계
팔레트 적재에서 2D 빈 패킹로
(제조사) 팔레트 적재는 동일 직사각형을 단일 영역에 채우는 구조화된 변형으로, 2D 직교 적재와 가깝다.
증거B · 서베이 / 튜토리얼 / 커뮤니티
등가E2 · 방법론 공유
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계
가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 2D 빈 패킹로
가변 크기 빈 패킹은 빈이 여러 크기·비용으로 주어지는 빈 패킹 변형으로, 빈 개수가 아니라 총 빈 비용을 최소화한다 — Wäscher 외 유형론의 '빈 구색' 차원에서 갈린다.
증거A · 동료심사 논문 / 공식 문서
등가E1 · 같은 기반, 다른 부가 제약
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
언급
Wäscher 절단·적재 유형론 (Wäscher Typology)에서 2D 빈 패킹로
유형론은 2D 빈 패킹을 '입력 최소화'(모든 항목을 담되 사용 빈을 최소화) 유형으로 분류한다.
증거A · 동료심사 논문 / 공식 문서
출처
- 출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems
  서지정보
  Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.

이 항목으로 들어오는 관계
관계	주장	증거	등가	출처
방법 공유 1D 절단 재고에서 2D 빈 패킹로	1D 절단 재고와 빈 패킹은 같은 절단·적재 계열의 밀접한 구성원이며, 둘 다 패턴/구성 정식화로 다뤄진다.	B · 서베이 / 튜토리얼 / 커뮤니티	E3 · 구조적 유추	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유 2D 불규칙 네스팅에서 2D 빈 패킹로	불규칙 네스팅과 2D 빈 패킹은 같은 절단·적재 계열로서 메타휴리스틱 탐색 방법론을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
방법 공유 2D 배낭 (직사각형)에서 2D 빈 패킹로	2D 배낭과 빈 패킹은 직교 배치 핵심과 다수의 정확·휴리스틱 방법을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
일반화 3D 빈 패킹에서 2D 빈 패킹로	3D 빈 패킹은 2D 빈 패킹의 고차원 일반화이며, 다수의 구성적·탐색 방법을 공유한다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계 길로틴 절단에서 2D 빈 패킹로	길로틴 절단은 절단이 변에서 변까지 직선이어야 한다는 추가 제약이 붙은 2D 직교 절단·적재의 변형이다.	A · 동료심사 논문 / 공식 문서	E1 · 같은 기반, 다른 부가 제약	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계 팔레트 적재에서 2D 빈 패킹로	(제조사) 팔레트 적재는 동일 직사각형을 단일 영역에 채우는 구조화된 변형으로, 2D 직교 적재와 가깝다.	B · 서베이 / 튜토리얼 / 커뮤니티	E2 · 방법론 공유	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
변형 관계 가변 크기 빈 패킹 (Variable-Sized Bin Packing)에서 2D 빈 패킹로	가변 크기 빈 패킹은 빈이 여러 크기·비용으로 주어지는 빈 패킹 변형으로, 빈 개수가 아니라 총 빈 비용을 최소화한다 — Wäscher 외 유형론의 '빈 구색' 차원에서 갈린다.	A · 동료심사 논문 / 공식 문서	E1 · 같은 기반, 다른 부가 제약	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.
언급 Wäscher 절단·적재 유형론 (Wäscher Typology)에서 2D 빈 패킹로	유형론은 2D 빈 패킹을 '입력 최소화'(모든 항목을 담되 사용 빈을 최소화) 유형으로 분류한다.	A · 동료심사 논문 / 공식 문서	—	출처 등급: A — 동료심사 논문 / 공식 문서An improved typology of cutting and packing problems 서지정보 Wäscher, G., Haußner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. EJOR 183(3):1109-1130.