CRAFT 알고리즘 (CRAFT (Computerized Relative Allocation of Facilities Technique))

한 줄 정의: 초기 배치안을 입력으로 받아 부서 쌍의 위치를 교환하며 물류 이동비용(거리×물동량×단위비용의 합)을 줄여 나가는 개선형 컴퓨터 설비배치 기법입니다.

쉽게 풀면

공장의 부서들을 어떻게 놓아야 물건이 오가는 거리가 짧아질까를 다루는 방법입니다. CRAFT는 일단 현재 배치에서 시작해 '두 부서의 자리를 바꾸면 총 이동비용이 얼마나 줄까'를 모든 쌍에 대해 계산하고, 가장 많이 줄어드는 교환을 실행합니다. 더 이상 나아지지 않을 때까지 이를 반복합니다.

왜 중요한가

1963년 Armour와 Buffa가 개발한 CRAFT는 설비배치에 컴퓨터 최적화를 도입한 선구적 기법으로, 이후 개선형 배치 알고리즘(COFAD, MULTIPLE 등)의 기준점이 되었습니다. 출발-도착표와 거리 행렬만 있으면 적용할 수 있어 교육과 실무에서 지금도 널리 쓰입니다.

논문에서는 이렇게 쓰입니다

"현 배치를 초기해로 CRAFT 알고리즘(CRAFT algorithm)을 적용하여 부서 간 총 자재이동비용을 14.2% 절감하는 개선안을 도출하였다."

현재 배치에서 출발해 부서 자리를 바꿔 가며 운반비용을 줄이는 안을 얻었다는 뜻입니다.

"CRAFT는 초기해 의존성이 커 서로 다른 세 개의 초기 배치에서 출발한 결과를 비교하였다."

출발점에 따라 결과가 달라지므로 여러 출발점을 시험했다는 의미입니다.

조금 더 깊게 보면

CRAFT는 부서 면적이 같거나 인접한 부서 쌍만 교환 대상으로 삼고, 부서 중심 간 직선거리(또는 직교거리)로 비용을 추정하므로 교환 후 실제 형상이 불규칙해질 수 있습니다. 이는 이차할당문제(QAP)에 대한 쌍교환 국소탐색 휴리스틱으로 해석되며, 국소최적에 빠지기 쉬워 이후 타부탐색, 담금질 기법과 결합한 변형이 제안되었습니다. 두 부서(또는 세 부서)의 위치를 교환했을 때 총 운반비용이 줄어드는지 계산해 개선하는 교환기반 휴리스틱으로, 국소최적해에 쉽게 수렴하므로 여러 초기해에서 반복 실행하는 것이 일반적입니다.

주의할 점

정량적 물류비용만 고려하므로 활동상관관계도표로 표현되는 정성적 근접 요구(소음, 안전 등)는 반영되지 않습니다. 결과 배치의 부서 형상이 실제로 사용 가능한지 사후 조정이 반드시 필요하며, 개선형 기법이므로 초기해 품질에 크게 좌우됩니다. 교환 결과 나온 부서 형태가 실제로 시공 불가능한 비정형 형상일 수 있어, 출력은 실현 가능성을 사람이 재검토해 최종안으로 다듬어야 합니다.