Maximal Covering Location Problem(MCLP) 알고리즘

최근 COMPAS에서 주관한 "광양시 자동분리수거기 최적의 위치 선정" 공모전에 참여하였다. 
최종 입지 선정 과정에서 사용한 MCLP 알고리즘에 대해 자세히 알아보려고 한다. 

 

 

공간 입지 모델링이란? 

시설물의 입지 결정에 영향을 주는 요인은 다양하지만, 그중 수요의 분포, 서비스의 도달 범위 같이 양적으로 측정할 수

있는 요인도 있고, 정치적 요인, 공공성, 형평성, 시설물 또는 서비스 운영 요원의 숙련도와 같이 질적 측면의 요인도 존재한다. 시설물의 적합한 입지를 결정하기 위해서는 양적 인자와 질적 인자를 모두 고려해야 한다. 

 

이때, 공간 입지 모델링을 통한 입지 선정은 양적인 측면과 여러 제약 조건을 동시게 고려하여 최적에 가까운 입지를 선정하는 훌륭한 수단이다. 

즉, 공간 입지 모델링은 시설물 서비스의 도달 범위, 지역에 분포하는 수요, 서비스의 도달 시간, 설치 가능한 시설물의 개수를 동시에 고려하여 설치 가능한 경우의 수에 따라 조건을 계산하여 최적의 입지를 선택해준다. 

=> 계량화할 수 있는 변수들을 동시에 고려하는 많은 경우의 수에 대한 모델링이 가능하다. 

 

 

공간 입지 모델링 효과 

1. 모델의 제작 과정을 통해 그 전에는 인식할 수 없었던 프로세스 내부의 관계를 알 수 있다. 

   => 계량적 모델링이 양적인 측면 이외에도 질적 의사 결정에 필요한 지식을 제공할 수 있다. 

 

2. 실제로는 실험할 수 없거나 어려운 대상에 대한 실험을 모델을 통해 수행할 수 있다. 

   => 특히 시설물의 입지는 실세계에 대한 실험이 불가능한 의사 결정이므로 모델의 사용은 큰 도움이 된다. 

 

3. 여러 가지 가상 시나리오의 결과를 빠르고 효과적으로 알아볼 수 있으며, 그 결과를 시각화할 수 있다. 

 

 

공공 부문의 입지의 중요한 기준 

* 민간 부문과는 다를 수 있음. 이 포스팅에서는 공공 부문 기준으로 설명 

공공 부문의 입지에서 중요한 기준이 되는 사회적 비용, 효율성과 형평성 등은 양적으로 측정하기 어렵다. 

그래서 양적으로 측정될 수 있는 간접적 대체 기준을 사용해야 한다. 

입지 모델에서는 형평성 측정의 대체 도구로 일반적으로 접근성을 사용한다. 

즉, 입지 모델상에서의 형평성 달성을 위해서는 수요자들의 접근성을 최대화할 수 있는 시설물의 서비스 영역 설정이 이루어져야 한다. 

=> 공공 부문의 입지의 중요한 기준은 접근성의 최대화! 

 

 

접근성을 측정하는 기준 3가지 

1. 수요자와 시설물 사이의 평균 거리 

    => 이 때 거리는 공간상의 거리 또는 시간상의 거리이며, 거리가 짧을수록 접근성이 더 큰 시설이 된다. 

2. 공간상에 존재하는 서비스의 수요를 재현하여 이 수요를 각 시설물에 할당

    => 하나의 시설물에 더 많은 수요가 할당될수록 효과적인 입지가 된다. 

3. 수요자와 시설물 간의 최대 도달 거리를 특정하는 방법 

    => 최대 도달거리 짧을수록 접근성이 큰 시설 

 

=> 접근성을 최대화하기 위해서는 평균 도달 거리 또는 최대 도달거리를 줄이거나,

      각 시설물에 할당되는 수요를 최대화할 수 있는 입지를 선정해야 한다. 

 

 

서비스 영역 사용 입지 모델 

입지 모델에서는 시설물의 서비스 영역을 결정하는 방법은 2가지로 나눌 수 있다. 

첫째, 모든 지역에 서비스가 제공되나 도달 거리 또는 도달 시간에 따라 서비스의 질적인 차이가 발생하는 경우 

 => 쉽게 예를 들어, 와이파이는  거리가 멀수록 서비스 질적 부분이 떨어진다. 

둘째, 일정한 도달거리/시간을 기준으로 하여 설정된 서비스 영역이 있고, 그 내부에는 서비스가 제공되나 바깥으로는 서비스가 제공되지 않는 방법. 이 경우 서비스 영역 내에서는 서비스의 질적인 차이는 존재하지 않는다. 

 

 

서비스 영역 기반 대표적인 입지 모델 

(1). SCLP; Set Covering Location Problem 

 

최소한의 비용으로 정의된 지역 내의 모든 수요 지점에 서비스를 공급할 수 있는 시설물의 입지를 찾는 것 

장점). 대상 영역 전체에 서비스를 제공하므로 접근성의 측면에서 공간적 형평성 확보 가능 

단점). 대부분 예산 등의 제약으로 대상 지역 전체에 대한 서비스를 제공하는 것은 불가능

 

=>  SCLP의 비용적 제약을 보완하기 위해 MCLP를 사용할 수 있다. 

 

(2). MCLP; Maximal Covering Location Problem

 

시설물의 개수 혹은 예산 비용이 제한되었을 때, 시설물의 서비스 수준을 높이기 위하여 주어진 제약조건 하에서 시설물이 커버하는 수요량을 최대화하는 위치를 선정하는 것 

SLCP에 비하여 현실적인 방법이다. ( 반드시 모든 수요 지점에 서비스를 공급할 필요가 없기 때문에 )

수요가 많은 지점을 우선으로 하여 입지 선택이 이루어지게 된다. 

 

MCLP의 목적 함수와 제약조건은 아래와 같습니다. 

 

목적함수의 yi는 결정변수로, 수요 지점 i가 서비스를 제공받으면 1, 아니면 0을 부여한다. 

               ai는 수요지점 i의 존재하는 수요의 양을 의미한다. 

즉, 목적함수 Z는 시설물에 의해 커버되는 총수요를 최대화시키는 것이 입지 목적임을 명시한다. 

 

제약조건 1은 수요 지점 i에서 지리적 커버리지 내에 시설물이 입지 했을 때만 수요 지점 i가 커버되도록 한다. 

=> 예를 들어, 와이파이의 커버리지가 500m일 때, A지점과 600m 떨어진 곳에 와이파이가 설치되었다면, A지점은 

     커버리지 내에 존재하지 않으니 와이파이 서비스가 제공되지 않는다. 

=> 즉, 좌변의 x의 합이 0이면 시설물이 수요지점 i를 포함하지 않는 것을 의미

=> 좌변의 x의 합이 1 이거나, 더 큰 경우에는 하나 혹은 그 이상의 시설물이 입지 하고 있다는 것을 의미 

 

제약조건 2는 시설물이 j 지역에 설치되어 있으면 1, 설치되어 있지 않으면 0 값을 나타낸다. 

제약조건 3은 커버리지가 수요 지점을 포함하는지 여부를 나타낸다. 

제약조건 4는 입지 할 시설물 수의 총합이 P개로 제한되는 것이다. P는 사전에 지정된 시설물의 수이다. 

 

 

휴리스틱 접근법 

만약 10,000개의 입지 후보지 중 50개의 시설물을 설치해야 한다면, 모든 경우의 수를 계산해야 할까?

10000! / 50!(10000-50)! 가지를....? 이건 거의 불가능하다. 

 

MCLP는 모든 경우의 수를 따려 정확한 최적지를 찾아내는 알고리즘이 아니다. 

따라서 최적지는 아니더라도 최적지에 가까운 입지를 상식적인 시간 내에 찾을 수 있는 솔루션이 필요한데, 여러 솔루션 중 휴리스틱(heuristic)을 설명하려 한다. 

 

휴리스틱이란?

오늘날에는 "문제 해결에 있어서 평균적인 정도의 성능을 발휘하지만 최악의 경우도 발생할 수 있는 기법"을 통칭

- 휴리스틱 접근법을 사용하면 솔루션 찾는 데 걸리는 시간을 줄일 수 있다. 

- 단축된 시간을 통해 가능한 여러 시나리오를 시험해 볼 수 있다. 

- 하지만 얻어낸 솔루션이 최적해는 아니다. 

그럼에도 불구하고 대부분의 경우는 비교적 짧은 시간 내에 받아들일 만한 솔루션을 찾아준다. 

 

입지 모델링에서 주요 이용되는 휴리스틱 기법에는 

lagrangian relaxation, interchange algorithm, tabu search, genetic algorithm, simulated annealing 등이 있다. 

여기에서는 interchange algorithm(인터체인지 알고리즘), simulated annealing을 결합한 알고리즘을 설명하려 한다. 

 

휴리스틱 기법(1). 인터체인지 알고리즘 

반복적 향상 알고리즘의 일종이다. 

즉, 임의의 솔루션을 선정하여 거기에서부터 알고리즘을 시작하여 반복적인 솔루션의 수정을 통해 조금씩 솔루션을 향상해가는 방법, 솔루션의 현재 상태에만 관심을 두고 바로 앞에 올 다음 상태는 고려하지 않는다. 

=> 앞만 보고 간다! 이전의 솔루션보다 더 나아진 것만을 받아들이고, 향상이 없으면 즉시 멈춘다. 

( 개념이gradient descent 랑 비슷한 느낌이 든다. 개인적인 생각으로는! )

 

 

< MCLP에 대한 인터체인지 알고리즘 > 

1. 임의로 p개의 시설물 위치를 선택하여 시작 솔루션으로 정한다. 

2. MCLP 목적함수 값을 계산하여 O_Old에 할당

3. 선택되지 않은 다른 모든 후보 지역 중 하나를 골라, 선택되어 있는 솔루션 중에서 가장 낮은 목적함수 값을 가진 지역과 교체한다. 

4. 새로 바뀐 솔루션의 목적함수 값을 계산하여 O_New에 할당한다. 

5. O_New > O_Old 라면 O_Old = O_New로 목적함수 값을 업데이트한다. 

6. 초기 솔루션의 p개 시설물 전부에 대해 동일한 교환을 실시하여 검증과정을 반복한다. 

7. 그 중에서 하나라도 발전된 목적함수 값이 등장했다면 솔루션을 수정한 수, 선택되지 않은 다른 후보 지역으로 넘어가 동일한 과정을 수행하고, 발전된 목적함수 값이 등장하지 않았다면 알고리즘을 중단한다. 

 

이 알고리즘의 단점은 7번에서 확인할 수 있다. 

솔루션이 향상되지 않으면 바로 알고리즘을 중단한다. 

즉, Local optima라는 것이다. 

 

이를 보완하기 위해서는 로컬 옵티멈에 빠지지 않기 위한 별도의 장치가 필요하며, 이런 장치가 바로 

"Simulated annealing" 이다. 

 

휴리스틱 기법(2). Sumulated Annealing(SA)

SA 알고리즘은 쉽게 말해, 로컬 옵티마에 빠지지 않고 글로벌 옵티멈을 찾을 수 있도록 도와주는 역할을 한다. 

인터체인지 알고리즘은 새로운 솔루션이 기존 솔루션보다 향상된 경우 계속 진행을 하며, 향상되지 않을 경우 바로 종료를 한다. 

SA 알고리즘 경우는 새로운 솔루션이 기존 솔루션보다 향상된 것이라면 확률에 관계없이 받아들이지만, 

향상되지 않은 경우에는, 기존 목적함수 값과 새로운 목적함수의 값의 차이에 따라 달라지는 확률에 의거하여 받아들일지 여부를 결정한다. 

 

 

COMPAS 공모전 분석 결과

* 시설물의 개수가 사전에 정해졌기 때문에, 최종 자동분리수거기 후보지의 수요량 총합을 최대화하는 입지를 선정하기 위해 MCLP 알고리즘을 사용 

* 수요지I와 후보지J는 다르게 설정할 수 있지만, 우리는 같다고 설정하였다.

* 아파트 동 하나를 수요지 및 후보지로 설정하였고

* 하나의 자동분리수거기가 cover 가능한 범위도 구해주었다. 

=> S는 도메인 지식을 활용할 수 있고, 도메인 지식이 없을 경우 다른 분석을 통해 분석가가 정해야 한다. 

* 중요한 파라미터 중 목적함수에 있는 ai를 설정해줘야 한다. 

  우리는 각 동별 재활용품 분리수거 적극성을 대표하는 값을 회귀분석을 통해 예측하였고, 그 값을 수요량으로 사용하    였다. 

* 수요지(I) 및 후보지(J) / 커버리지 거리(S) / 수요량(ai) / 분석 목적에 맞는 제약조건들 / 시설물 개수(P)를 설정해준 후

알고리즘을 돌리면 결과가 위와 같이 나온다. 데이터 수가 많이 없어서 그런지 결과가 바로 나온 편이다. 

 

 

 

COMPAS 공모전을 끝내면서 아쉬운 점이 있다면

수요량을 회귀분석을 통해 예측하는 부분에서 신뢰성이 좀 떨어지는 결과를 얻은 부분과 

MCLP 기법을 통해 나온 최종 입지가 좋은 입지인지 사후 평가하는 부분이 미흡했던 것 같다. 

다음에 기회가 된다면 이런 부분들을 더 보충해서 더 좋은 결과물을 내야겠다! 화이팅! 

 

 

 

 

< 참고 자료 >

홍인주, "공간 입지 모델링을 이용한 도시 재난 대응 시설물의 입지 최적화 연구 : 부산 지역의 해일 재난 대응 시설을 중심으로", 서울대학교, 2009, p20-27.

 

이민정, 김영호, "유동인구 및 인구밀도를 활용한 안산시 방범용 CCTV의 입지모델링 연구", 국토지리학회지 제48권 4호, 2014 (533~546)