P-median 알고리즘

입지선정문제는 일반적으로 목적함수와 제약식의 다양한 형태 에 따라 제한용량이 없는 입지선정문제(Uncapacitated Facility Location Problem : UFLP), 제한용량이 있는 입지선정문제 (Capacitated Facility Location Problem : CFLP), P-센터 문제 (P-Center Problem), P-Median 문제(P-Median Problem) 등으로 구분되어진다.

 

특히 P-Median 문제는 공장, 창고, 물류센터 또는 공공시설 등을 설치할 수 있는 후보입지가 주어져 있다고 가정하고 각 후보입지는 소비자 수요 발생지역을 나타내며 각 시설로부터 각 소비자에게 제품을 수송할 때 소요되는 단위 당 수송비와 수송거리 가 주어져 있다고 가정할 때, 최소의 수송비용으로 모든 소비자의 수요를 충족시킬 수 있는 p개 이하의 시설 설치 입지를 결정하는 문제로써, 경찰서, 소방서, 전화국, 공공의료시설, 환경처리시설 등과 같은 공공시설이나 백화점, 대형할인매장, 자동차영업소 등과 같이 경쟁사들과의 경쟁이 치열한 민간시설의 입지선정 문제나 통신 및 전력수송 집선장치 위치선정 문제, 파이프라인 시스템 설계문제 등과 같은 많은 응용분야에서 자주 발생되는 문제이다.

 

출처: Park, Bora, LEE, Kyu Jin, & Choi, Keechoo. (2013). 휴리스틱 P-Median 알고리즘을 이용한 자전거주차장 최적입지선정. 대한토목학회논문집, 33(5), 1989–1998. https://doi.org/10.12652/KSCE.2013.33.5.1989

 

 

P-Median Algorithm의 기본 모형

 

 

(1-1)에 나타난 목적함수는 시설물과 수요자간의 총 통행거리를 나타내는 것이며, 수요지 i와 시설물의 입지점 j의 거리

d_ij는 네트워크상에서 결절점 사이의 최단경로를 나타낸다.

 

(1-2)의 제약조건은 각 수요지, 즉 수요발생지점은 반드시 하나의 시설물에 의해 서비스를 받음을 의미하며, 중복 서비스나 서비스 부재지역이 존재하지 않음을 나타내는 것이다.

 

(1-3)의 제약조 건은 자신의 지역에 있는 시설물에 의해 서비스를 받는 지역(수요 지)의 수는 시설물의 수와 같음을 나타낸다.

 

(1-4)의 제약조건은 만약 x_j=0이면 j지역에 시설물이 존재하지 않으며 i지역 이용자는 j지역의 시설에 할당되지 않으므로 y_ij=0이 되고, 만약 x_j=1이면 j지역에 시설물이 존재함을 의미하므로 y_ij는 0 혹은 1의 값을 가지게 되는 두 가지 경우를 동시에 고려하여 나타낸 것이다.

 

(1-5)과 (1-6)은 결정변수 , 가 0 혹은 1의 값을 가질 수 있도록 하는 제약조건들이다.

 

 

출처: Park, Bora, LEE, Kyu Jin, & Choi, Keechoo. (2013). 휴리스틱 P-Median 알고리즘을 이용한 자전거주차장 최적입지선정. 대한토목학회논문집, 33(5), 1989–1998. https://doi.org/10.12652/KSCE.2013.33.5.1989

 

 

 

 

 

원문에 나와있는 P-median의 수학적 공식

 

출처: https://github.com/ralaruri/p_median_python