Maximal Covering Location Problem (MCLP) 알고리즘

김죠·2023년 5월 20일

mclp

머신러닝

목록 보기

8/9

공간 입지 모델링이란?

시설물의 입지를 결정하는 요인은 다양하지만, 그 중 수요의 분포, 서비스의 도달 범위와 같은 양적 요인이 있고, 정치적 요인, 형평성 등 질척 요인이 존재한다.
시설물의 적절한 입지를 결정하기 위해서는 양적 요인과 질적 요인을 모두 고려해야 한다.

공간 입지 모델링을 통한 입지 선정은 양적 요인과 여러 제약 조건을 동시에 고려하여 최적에 가까운 입지를 선정하는 훌륭한 수단이다.
즉, 계량화할 수 있는 변수들을 동시에 고려하는 많은 경우의 수에 대한 모델링이 가능하다.

공간 입지 모델링의 효과
- 모델을 제작함으로써, 그 전에는 인식할 수 없었던 프로세스 내부의 관계를 알 수 있다.
  즉, 계량적 모델링이 양적인 측면 외에도 질적 의사 결정에 필요한 지식을 제공할 수 있다.
- 실제로는 실험할 수 없거나, 어려운 대상에 대한 실험을 모델링을 통해 수행할 수 있다.
  특히, 시설물의 입지는 실세계에 대한 실험이 불가능하므로 모델 사용은 큰 도움이 된다.
- 여러 가상 시나리오의 결과를 빠르고 효과적으로 알아볼 수 있고, 그 결과를 시각화할 수 있다.

공공 부문의 입지의 중요한 기준
- 공공 부문의 입지에서 중요한 기준이 되는 사회적 비용, 효율성, 형평성 등은 양적으로 측정하기 어렵다. 따라서, 양적으로 측정될 수 있는 간접적 대체 기준이 필요하다.
  입지 모델에서는 형평성 측정의 대체 도구로 접근성을 사용한다.
  즉, 입지 모델상에서의 형평성 달성을 위해 수요자들의 접근성을 최대화할 수 있는 시설물의 서비스 영역 설정이 이루어져야 한다.
  $\rightarrow$ 공공 부문 입지의 중요한 기준은 접근성의 최대화

접근성을 측정하는 기준 3가지
- 수요자와 시설물 사이의 평균 거리
  $\rightarrow$ 거리는 공간상 또는 시간상의 거리이며, 거리가 짧을수록 접근성이 더 큰 시설이다.
- 공간상에 존재하는 서비스의 수요를 재현하여 이 수요를 각 시설물에 할당
  $\rightarrow$ 하나의 시설물에 더 많은 수요가 할당될수록 효과적인 입지가 된다.
- 수요자와 시설물 간의 최대 도달 거리를 특정
  $\rightarrow$ 최대 도달거리가 짧을수록 접근성이 큰 시설 (첫번째는 모든 거리의 평균이며 세번째는 모든 거리 중 가장 긴 거리를 특정)
$\rightarrow$ 접근성을 최대화하기 위해서는 평균 도달 거리 또는 최대 도달 거리를 줄이거나, 각 시설물에 할당되는 수요를 최대화할 수 있는 입지를 선정해야 한다.

서비스 영역 사용 입지 모델

입지 모델에서는 시설물의 서비스 영역을 결정하는 방법을 2가지로 나눌 수 있다.
- 모든 지역에 서비스가 제동되나, 도달 거리 또는 도달 시간에 따라 서비스의 질적인 차이가 발생하는 경우
  $\rightarrow$ 예를 들어, 와이파이는 거리가 멀수록 서비스 질적 부분이 떨어진다.
- 일정한 도달거리 / 시간 을 기준으로 설정된 서비스 영역이 있고, 그 내부에는 서비스가 제공되나, 바깥으로는 서비스가 제공되지 않는 방법
  $\rightarrow$ 이 경우, 서비스 영역 내에서는 서비스의 질적인 차이는 존재하지 않는다.'

서비스 영역 기반 대표적인 입지 모델
- SCLP (Set Covering Location Problem)
  
  최소한의 비용으로 정의된 지역 내의 모든 수요 지점에 서비스를 공급할 수 있는 시설물의 입지를 찾는 방법
  
  장점 : 대상 영역 전체에 서비스를 제공하므로 접근성의 측면에서 공간적 형평성 확보 가능
  
  단점 : 대부분 예산 등의 제약으로 전체 지역에 대한 서비스를 제공하는 것은 불가능
  
  $\rightarrow$ SCLP의 비용적 제약을 보완하기 위해 MCLP를 사용할 수 있다.
- MCLP (Maximal Covering Location Problem)
  
  시설물의 개수 혹은 예산 비용이 제한되었을 때, 시설물의 서비스 수준을 높이기 위해 주어진 제약조건 하에서 시설물이 커버하는 수요량을 최대화하는 위치를 선정하는 것
  이는 SCLP에 비해 현실적인 방법이다. 반드시 모든 수요 지점에 서비스를 공급할 필요가 없기 때문이다. 수요가 많은 지점을 우선으로 하여 입지 선택이 이루어진다.
  MCLP의 목적 함수와 제약조건은 아래와 같다.
  
  목적함수의 $y_i$ 는 결정변수로, 수요 지점 $i$ 가 서비스를 제공받으면 1, 아니면 0을 부여한다.
  $a_i$ 는 수요 지점 $i$ 에 존재하는 수요의 양을 의미한다.
  즉, 목적함수 Z는 시설물에 의해 커버되는 총 수요를 최대화시키는 것이 입지 목적임을 명시한다.
  
  제약조건 1은, 수요 지점 $i$ 에서 지리적 커버리지 내에 시설물이 입지했을 때만 수요 지점 $i$ 가 커버되도록 한다.
  $\rightarrow$ 예를 들어, 와이파이의 커버리지가 500m일 때, A 지점과 600m 떨어진 곳에 와이파이가 설치되었다면, A 지점은 커버리지 내에 존재하지 않으니 와이파기 서비스가 제공되지 않는다.
  $\rightarrow$ 즉, 좌변의 $x$ 의 합이 0이면, 시설물이 수요지점 $i$ 를 포함하지 않는 것을 의미
  $\rightarrow$ 좌변의 $x$ 의 합이 1이거나, 더 큰 경우에는 하나 혹은 그 이상의 시설물이 입지하고 있다는 것을 의미
  
  제약조건 2는, 커버리지가 수요 지점을 포함하는지 여부를 나타낸다.
  제약조건 3은, 시설물이 $j$ 지역에 설치되어 있으면 1, 설치되어 있지 않으면 0을 나타낸다.
  제약조건 4는, 입지할 시설물 수의 총합이 P개로 제한되는 것이다. P는 사전에 지정된 시설물의 수이다.
휴리스틱 (heuristic) 접근법

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

MCLP는 모든 경우의 수를 따져 정확한 최적지를 찾아내는 알고리즘이 아니다. 최적지는 아니더라도 최적지에 가까운 입지를 상식적인 시간 내에 찾을 수 있는 솔루션이 필요한데, 이에 사용하는 것이 휴리스틱 (heuristic) 이다.

휴리스틱이란, "문제 해결에 있어서 평균적인 정도의 성능을 발휘하지만, 최악의 경우도 발생할 수 있는 기법"을 통칭한다.
- 휴리스틱 접근법을 사용하면 솔루션을 찾는데 걸리는 시간을 줄일 수 있다.
- 단축된 시간을 통해 가능한 여러 시나리오를 시험해볼 수 있다.
- 그러나, 얻어낸 솔루션이 최적해는 아니다.
그럼에도 불구하고, 대부분의 경우 비교적 짧은 시간 내에 받아들일 만한 솔루션을 찾아준다.

입지 모델링에서 주요 이용되는 휴리스틱 기법에는 lagrangian relaxation, interchange algorithm, tabu search, genetic algorithm, simulated annealing 이 있다.
여기에서는, interchange algorithm, simulated annealing 을 결합한 알고리즘을 설명하려 한다.
휴리스틱 기법 (1). interchange algorithm

반복적 향상 알고리즘의 일종이다.
즉, 임의의 솔루션을 선정하여, 거기에서부터 알고리즘을 시작하여 반복적인 솔루션의 수정을 통해 조금씩 솔루션을 향상해가는 방법, 솔루션의 현재 상태에만 관심을 두고 바로 앞에 올 다음 상태는 고려하지 않는다.
$\rightarrow$ 앞만 보고 간다! 이전의 솔루션보다 더 나아진 것만을 받아들이고, 향상이 없으면 즉시 멈춘다. (gradient descent, greedy algorithm 과 유사)
MCLP에 대한 interchange algorithm
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 라는 것이다.

이를 보안하기 위해서는 Local Optima 에 빠지지 않기 위한 별도의 장치가 필요하며, 이러한 장치가 바로 Simulated annealing 이다.
휴리스틱 기법 (2). Simulated Annealing (SA)

SA 알고리즘은 쉽게 말해, Local Optima 에 빠지지 않고 Global Optimum 을 찾을 수 있도록 도와주는 역할을 한다.
인터체인지 알고리즘은 새로운 솔루션이 기존 솔루션보다 향상된 경우에만 진행을 하며, 향상되지 않을 겨우 바로 종료한다.
SA 알고리즘의 경우 새로운 솔루션이 기존 솔루션보다 향상된 것이라면 확률에 관계없이 받아들이지만, 향상되지 않은 경우에는, 기존 목적함수 값과 새로운 목적함수 값의 차이에 따라 달라지는 확률에 의거하여 받아들일지 여부를 결정한다.