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