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