집합피복입지문제 (Set Covering Location Problem)
한 줄 정의: 모든 수요지가 정해진 서비스 거리(또는 시간) 안에 최소 하나의 시설로부터 서비스를 받을 수 있도록, 최소 개수의 시설 위치를 결정하는 최적화 문제입니다.
쉽게 풀면
소방서나 응급실을 도시 곳곳에 세울 때, "모든 지역이 몇 분 안에 도움을 받을 수 있어야 한다"는 기준이 있다고 해봅시다. 집합피복입지문제는 이 기준을 만족시키면서도 시설을 최대한 적게 지어서 비용을 아끼는 위치를 찾는 문제입니다. 마치 무선 공유기를 최소한의 개수로 설치해서 집 안 어디서든 신호가 닿게 만드는 것과 비슷합니다.
왜 중요한가
서비스 접근성이 중요한 공공시설(소방서, 병원, 콜센터 등)이나 커버리지가 핵심인 네트워크 설계 문제에서 널리 사용되며, 시설 입지 이론의 대표 모형 중 하나로 산업공학 및 운영과학 연구에서 자주 다루어집니다.
논문에서는 이렇게 쓰입니다
"본 연구는 집합피복입지문제(set covering location problem)를 활용하여 응급 서비스 시설의 최소 설치 개수를 산정하였다."
공공 서비스 시설의 최소 설치 규모를 결정하는 데 문제가 사용된 예입니다.
"제안된 정수계획 모형은 집합피복입지문제의 정형화된 형태를 따르며, 커버리지 반경을 매개변수로 두어 민감도 분석을 수행하였다."
커버리지 기준을 변화시키며 결과를 분석하는 연구에서 사용된 예문입니다.
조금 더 깊게 보면
집합피복입지문제는 0-1 정수계획법으로 정식화되며, 각 수요지가 적어도 하나의 개설된 시설로부터 서비스 거리 안에 있어야 한다는 제약을 만족시키면서 개설 시설 수를 최소화하는 목적함수를 가집니다. 유사한 문제로 정해진 시설 수 안에서 커버되는 수요를 최대화하는 최대커버리지입지문제(maximal covering location problem)가 있습니다.
주의할 점
모든 수요지를 완전히 커버하려 하면 시설 수가 지나치게 많아질 수 있어, 실무에서는 비용과 서비스 수준 사이의 절충이 필요합니다.