p-중앙값 문제 (P-Median Problem)
한 줄 정의: p-중앙값 문제는 정해진 개수(p개)의 시설을 배치할 때, 수요 지점들과 가장 가까운 시설 사이의 총 이동 거리(또는 비용)의 합을 최소화하는 입지를 찾는 대표적인 입지-배분 최적화 문제입니다.
쉽게 풀면
한 지역에 병원을 3곳만 새로 지을 수 있다고 할 때, 어디에 지어야 주민들이 가장 가까운 병원까지 이동하는 평균 거리가 짧아질까요? p-중앙값 문제는 바로 이런 질문에 답하는 수학적 틀입니다. "p"는 지을 수 있는 시설의 개수를 뜻하며, 이 개수가 정해진 상태에서 전체 이용자의 이동 거리 합을 최소로 만드는 위치 조합을 찾는 것이 목표입니다. 마치 한정된 개수의 우체통을 마을 곳곳에 배치할 때, 모든 주민이 최대한 가까운 우체통을 이용할 수 있도록 위치를 고민하는 것과 같습니다.
왜 중요한가
제한된 예산으로 시설을 설치해야 하는 현실적인 상황에서, p-중앙값 문제는 자원을 가장 효율적으로 배분하는 방법을 제시해 줍니다. 이 때문에 지도학과 도시계획, 공공시설 입지 연구 논문에서 시설 배치 문제를 다루는 대표적인 이론적 틀로 널리 인용됩니다.
논문에서는 이렇게 쓰입니다
"응급의료 취약 지역을 대상으로 p-중앙값 문제를 적용하여 신규 구급차 대기소의 최적 입지를 도출하였다."
정해진 수의 시설을 어디에 배치할지 결정하기 위해 p-중앙값 문제를 활용했다는 의미입니다.
"p-중앙값 문제의 해법으로 도출된 배치안은 기존 시설 배치보다 평균 접근 거리를 상당히 단축시켰다."
최적화 결과가 기존 배치보다 개선되었음을 보여주는 사례입니다.
조금 더 깊게 보면
p-중앙값 문제는 수요 지점과 후보 입지 간의 거리 행렬을 기반으로 정수계획법 형태로 정식화되며, 문제의 규모가 커지면 최적해를 정확히 구하기 어려워 유전 알고리즘이나 지역 탐색과 같은 휴리스틱 기법이 함께 활용되기도 합니다.
주의할 점
p-중앙값 문제는 이동 거리의 총합 또는 평균을 최소화하는 데 초점을 두므로, 최대 이동 거리를 제한하려는 목적의 문제(예: p-센터 문제)와는 목적 함수가 다르다는 점에 유의해야 합니다.