Maximal covering location problem(MCLP)

Maximal covering location problem 일명 MCLP알고리즘으로 불리운다.

 

"Maximize the amount of covered demand"

한국어로 "최대커버링 모델"을 일컫는 말로써, 제한된 시설물의 개수로 지역 수요를 최대한 커버할 수 있는지 파악하기 위한 입지 선정 모델링 방법이다.

 

즉 우선입지선정 같은 문제에 어울리는 알고리즘이다.

 

코드를 알아보기 앞서 수식을 알아보면 아래와 같다.

 

1974년 교회의 최적 입지 장소를 알아보는 코드를 만들어봅시다.

 

N은 주어진 수(여기서는 교회 주변에있는 주택 혹은 시설 같은 사용자가 정하는 것이다.) 

K는 원의 개수

r은 원의 반경(즉 커버링 범위)

M은 후보지 크기(즉 M개 중에서 K의 중심이 랜덤으로 뽑히는 것이다)

C는 영향받는 N의 수이다.

 

20개의 원이 0.1의 반경을 가지고 100개 중에서 뽑아 300개를 커버하려고 할때의 그림은

이처럼 C가 209개가 나오고

 

20개의 원이 0.1의 반경을 가지고 2000개 중에서 뽑아 300개를 커버하려고 할때의 그림은

C가 253개가 나오고

 

20개의 원이 0.1의 반경을 가지고 10000개 중에서 뽑아 300개를 커버하려고 할때의 그림은

C가 258개가 나오게 됩니다.

 

코드로 표현하면

from mclp import *
%matplotlib inline

#input data 생성

import numpy as np
Npoints = 300
# Generate points in uniform distribution 
# points = np.random.rand(Npoints,2)

# Generate points in moon distribution
from sklearn.datasets import make_moons
points,_ = make_moons(Npoints,noise=0.15)

#최적입지선정
# 선택한 장소 수
K = 20

# 각 장소의 반경
radius = 0.2

# 후보군 크기
M = 100

# Run mclp opt_sites is the location of optimal sites and f is the points covered
opt_sites,f = mclp(points,K,radius,M)

# 결과 도식화
plot_result(points,opt_sites,radius)

----- Configurations -----
  Number of points 300
  K 20
  Radius 0.2
  M 100
Academic license - for non-commercial use only
----- Output -----
  Running time : 0.063560962677 seconds
  Optimal coverage points: 208

#다른 배치
K = 20
radius = 0.2
M = 10000
opt_sites,f = mclp(points,K,radius,M)
plot_result(points,opt_sites,radius)

 

도움받은 github: https://github.com/cyang-kth