[공간최적화] 커버링 문제, 메디언 문제, 센터 문제

공공 시설물은 접근하기 편해야 하며(공간효율성), 서비스에 있어 소외받는 사람이 없도록 해야한다(공간형평성).

 

이러한 공익을 지향하는 입지 문제는 주로 커버링 문제, 메디언 문제, 센터 문제로 연구된다.

 

 

 

 

1. 커버링 문제 (covering problem)

목적 : 제한된 서비스 도달범위(물리적 거리 또는 시간거리)를 가진 시설물의 서비스를 받을 수 있 는 수요를 최대화시키도록 시설물을 입지시키는 것

 

종류

1) LSCP(Location Set Covering Problem)

제한된 도달범위를 가지는 서비스 시설물이 모든 수요지점을 포괄하면서 최소 개수의 시설물 입지를 구함

 

2) MCLP(Maximal Covering Location Problem) (Church and ReVelle, 1974)

모든 수요지점이 아니라 최대한 많은 수요지점에 서비스를 제공하도록 입지시킴

 

활용

장문석 외(2013)은 공공자전거 추가 정류소 개수 산정 시 LSCP를 이용하였으며, 정수계획법을 응용한 수리모형을 제시하여 서초구 공공 자전거 정류소 추가 설립방안을 모색하였다.

Ye et al. (2011)은 대만의 재활용 센터 입지선정 관련하여 커버 링 문제를 활용하였다.

 

* 메디언, 센터 

- 메디언, 센터 문제는 Hakimi(1965)에 의해 노드와 아크로 연결된 네트워크 공간에서 명시적으로 논의됨

- 여러 개의 시설물 입지에 대한 최적해를 찾는 p-Median, p-Center 모델로 많이 활용됨

 

2. 메디언 문제 (median problem)

- 메디언 문제는 Weber(1929)의 입지 문제로 많이 알려져 있으며, 수요지점과의 총거리(또는 평균거리)를 최소화시키는 문제로 Minisum 입지 문제의 한 유형

- 시설물과 수요지점과의 평균적인 거리 또는 합계된 거리를 최소화시킨다는 점에서 공간적인 효율성을 강조함

- 메디언 지점의 입지는 원거리의 인구가 희박한 지역이 상대적으로 인구가 많고 시설물과 가까운 지역에 비해 차별적인 공간적 접근성을 가지게 되어 공간적 형평성의 저해를 가져옴

 

최근 공간정보 분야의 연구들은 p-median으로 대표되는 미디언 문제를 통해 최적 입지를 찾거나 이를 커버링 방법과 혼합하여 최적해를 도출하는 방안을 많이 사용

최돈정･박정환(2018)은 p-median 방법 에 의해 충청남도 화재 출동거점을 선정

송하진･이건학(2017) 역시 이를 통해 서울 서초구와 강남구의 사전투표소 최적 입지 모델링을 실시

Park et al.(2017)은 공공자전거 정류소의 최적입지 선정을 위해 MCLP와 p-median 방법을 혼합하여 사용

이향숙 외(2017)도 set-covering 모형과 p-median 모형을 적용하여 무인택배함의 설치개수와 최적 입지를 결정

 

 

 

 

3. 센터 문제 (center problem)

- 센터 문제는 가장 멀리 떨어져 있는 수요지점과의 거리를 최소화시키는 입지 지점을 찾는 Minimax 입지 문제의 유형

 

- 모든 수요에 대한 평균적인 거리보다 원 거리에 있는 수요지점의 접근성을 가장 고려하므로 공간적인 형평성과 밀접히 관련됨

- 의료보건, 화재, 치안, 구조 등과 같은 긴급 서비스 시스템에 특히 중요성을 가짐.

- 센터 지점에 시설물을 입지시키는 것은 일반적으로 시설물과 수요지점간의 총거리를 증가시키므로 공간적 효율성 관점에서 많은 손실을 가져옴

 

 

 

4. 센디언 문제 (cendian problem)

- 공간적 효율성과 형평성 사이의 이러한 상충관계에 대한 대안적인 접근법으로 제안된 것이 센디언 문제(centdian problem).

- 센디언은 상충관계에 있는 공간적 효율성과 형평성에 대한 절충해(compromising solution)를 구하는 문제로 Halpern(1976)에 의해 처음으로 소개됨

- Halpern(1976)은 메디언과 센터 모델을 선형조합으로 결합한 이목적 최적화 모델(bi-objective optimization model)의 접근방법을 제시

 

 

출처

이건학. (2010). 동통폐합에 따른 동주민센터의 입지 변화 분석과 최적 입지 모델링. 대한지리학회지, 45(4), 521-539.

이지원, 김지영, 유기윤 and 양성철, 지적과 국토정보 2019 Vol. 49 Issue 2 Pages 109-122

 

 

 

=================================

 

전형적인 최적화 접근 입지 문제로는 입지-배분 문제(location- allocation problem), 커버링 문제(covering problem), 센터 및 메디 안 문제(center and median problem) 등이 있다. 

 

입지-배분 문제는 특정 시설물과 사용자 간의 이동 비용 을 최소화하면서 시설물에 모든 사용자를 배분시키는 문제로 물류 센터, 배송 센터, 소매 상권 분석 등에 유용 하게 적용되고 있다.

입지-배분 문제에 있어 입지하고 자 하는 시설물이 다중 시설일 경우 Hakimi(1965)에 의 해 공식화된 p-median 문제로 해결할 수 있다. p-median 은 목적함수인 총이동 시간 또는 비용을 최소화시키는 최소합(MINSUM) 문제의 한 유형으로 볼 수 있으며, 조 합 최적화(combinatorial optimization)로 일반적으로 풀기 가어려운 NP-hard(Non-deterministicPolynomial-time hard) 문제로 인식되고 있다(Current et al., 1990).

이는 결정해야할 입지 수가 증가할수록 합리적인 시간 내에 정확 한 해를 찾기 어렵거나 비효율적임을 의미한다.

이를 해결하기 위해 후보지의 수를 연속적인 면상의 점이 아닌 이산적인 점의 형태로 하여 사례수를 감소시킴 으로써 정확한 해를 찾는 방법이 고안되거나, 정확하 진 않을 수 있지만 효율적인 해를 도출하는 방법인 휴리스틱 기법이 다양하게 활용되고 있다(Mladenovic´ et al., 2007).

 

출처

이건학 진찬우 행복주택 최적 입지 선정에 관한 연구: 다목적 공간 최적화 접근. 한국도시지리학회지 제18권 2호 2015 (81~95)