이차할당문제 (Quadratic Assignment Problem)
한 줄 정의: 여러 시설을 여러 후보 위치에 배정할 때, 시설 간 이동량과 위치 간 거리의 곱의 합을 최소화하는 배정을 찾는 조합최적화 문제입니다.
쉽게 풀면
공장에 여러 부서를 배치해야 하는데, 자리는 정해져 있고 부서도 정해져 있다고 해봅시다. 부서끼리 물건을 많이 주고받을수록 가깝게 배치해야 이동이 줄어듭니다. 이차할당문제는 "어느 부서를 어느 자리에 놓아야 전체 이동량이 최소가 될까"를 수학적으로 푸는 문제입니다. 마치 교실에서 자주 대화하는 친구들끼리 가까운 자리에 앉히려는 자리 배치 퍼즐과 비슷합니다.
왜 중요한가
설비배치 문제를 수학적으로 정식화하는 가장 대표적인 모형으로, 블록배치설계나 자재운반시스템 설계의 이론적 기반이 됩니다. 조합의 수가 매우 빠르게 증가하는 대표적인 NP-hard 문제로 알려져 있어, 최적화 알고리즘 연구의 단골 벤치마크로도 사용됩니다.
논문에서는 이렇게 쓰입니다
"설비배치 문제를 이차할당문제(quadratic assignment problem)로 정식화하고, 메타휴리스틱 기법을 적용해 해를 도출하였다."
실제 배치 문제를 이차할당문제 형태로 수식화하는 전형적인 사용 예입니다.
"제안된 유전 알고리즘은 표준 이차할당문제 벤치마크에서 기존 기법 대비 우수한 성능을 보였다."
알고리즘 성능 평가를 위한 표준 문제 집합으로 이차할당문제가 활용된 예입니다.
조금 더 깊게 보면
이차할당문제는 시설 간 흐름량 행렬과 위치 간 거리 행렬이라는 두 행렬의 곱을 목적함수로 다루기 때문에 이름에 "이차(quadratic)"라는 표현이 붙습니다. 문제 규모가 커지면 정확해를 구하기 어려워, 실무에서는 유전 알고리즘, 시뮬레이티드 어닐링 등 발견적(휴리스틱) 기법으로 근사해를 구하는 경우가 많습니다.
주의할 점
시설 수가 늘어날수록 계산 복잡도가 급격히 커지므로, 대규모 문제에서는 정확한 최적해보다 실행 가능한 우수해를 목표로 하는 접근이 일반적입니다.