[2022 강서구 공모전] #4.1 알고리즘 및 방법론 [가로 쓰레기통]

 

알고리즘 및 방법론 :　가로 쓰레기통

0. 개요

사람들이 무단투기하는 가장 근본적인 이유는 가로 쓰레기통이 없기 때문이다. 현주 인구가 활동하는 장소와 가까운 곳에 쓰레기통을 추가 설치해야 하는데 이것은 공간 접근성에 관한 얘기다. 즉 공간 접근성을 최대화시킬 수 있다면 쓰레기통의 설치 위치를 합리적, 효율적으로 정할 수 있을 것이다.

 

1. GIS 공간분석

GIS 공간분석을 위해 Google의 ‘Geocoding API’로 좌표 추출 및 지형을 코드화시켜 각 시설물과 후보지에 대한 코드를 부여하였고 이에 따른 가중치를 부여해 가로 쓰레기통 위치 설정을 하였다. 본 분석과 같이 분석 대상의 위치를 이용하여 새로운 시설물의 설치 장소를 분석하는데 용이하다.

 

2. P-median 알고리즘

A. p-median 변수 설정

p-median은 공공시설 등을 설치할 수 있는 후보 입지와 수요지 간의 거리를 최소화하는 해를 도출하여 결정하는 최소합 문제 알고리즘의 일종이다.

본 연구에서는 가로 쓰레기통의 편의성을 구체화한 공간 접근성을 최대화하는데 p-median 알고리즘이 가장 적합하다고 판단했다.

이를 본 연구에 적용시키면 생활인구가 쓰레기통에 도달할 수 있는 거리적 마찰이 비용에 해당하며 거리적 마찰을 최소화시키는 것이 가로 쓰레기통의 접근성을 최대화하는 것을 의미한다.

p-median 문제의 전형적인 정수 선형 계획법은 다음과 같이 공식화할 수 있다.

목적함수 Z는 모든 수요 지점과 가로 쓰레기통 간의 가중화된 거리를 최소화함으로써 시민들의 쓰레기통에 대한 접근성을 최대화한다.

본 연구에서 p-median 모델을 그대로 적용시키면 정확한 해를 도출할 수 없기 때문에 한계가 있다. 이에 대한 대안으로 최적해에 근접한 준최적해를 빠르게 찾아주는 휴리스틱 방법을 사용한다.

그 중 최적해를 찾는데 효과적이라고 알려진 교환 알고리즘(Teitz-Bart)을 기반으로 문제를 해결하였다.

3. Filter 적용

본 연구에서는 각 구청의 쓰레기통 간 거리 정책을 고려해 신규 최적 입지와 기존 가로 쓰레기통 위치의 거리가 100m 미만이라면 해당 신규 최적 입지는 채택하지 않기로 했다.

분석모델수립 시각화

 

관련 github code

https://github.com/rootofdata/Gangseo-gu_contest.git

GitHub - rootofdata/Gangseo-gu_contest