그래프 기술로 보행흐름 예측 분석하기 - Part. 2

사람들의 군집 현상, 교통 체증, 인터넷 사용량 증가, 전력의 과부하 같은 어떤 매체가 한곳에 집중되어 제 기능을 수행하지 못하게 되는 현상은 우리 사회의 큰 문제점으로 자리 잡고 있다. 그래서 비트나인은 그래프 데이터를 기반으로 현상에 대한 분석뿐 아니라 모델링을 통해 향후 발생 가능성이 있는 집단 현상에 대하여 매체 분산을 목적으로 하는 해결책을 제시해본다.

 

포스팅 Part 1에 이어서 도로에서 정체가 발생했을 때, 상황 해결을 위한 판단 조건을 부여했다면, 이번 글에서는 조금 더 큰 차원인 도로·교차로로 이루어진 그래프 모델로 알아보고자 한다.

도로 그래프 모델링

대중에게 인기 있는 지역은 더 집중되고 자주 거쳐야 하는 곳의 통행을 선호한다는 가정을 기반으로 그래프 데이터에 대한 조건은 다음과 같다. 

 

1. 통행량이 많은 도로로 이동한다.
2. 어떤 지점으로 갈 때(= 어느 출발점에서 도착점으로 갈 때) 거쳐 가야 하는 정도가 높은 곳으로 이동한다.

 

위의 두 조건을 적용한 지역의 통행 상황을 그래프화 하기 위해 교차로를 노드(점), 도로를 엣지(점 간의 연결선)로 구성하였다. 간단한 모델 구성을 위해 방향성이 없는 그래프를 사용하였으며 각 도로의 최대 통행량을 설정하였다. 그리고 통행에 대한 집중도 지표를 제공하기 위해 그래프 이론에서 널리 쓰이는 betweenness centrality (B.C)를 사용하였다. B.C는 임의의 서로 다른 두 노드 간의 최단 거리 위에 해당 노드가 얼마나 자주 있는지를 표현하는 지표이다. 아래 예시를 참고하여 설명될 수 있다.

 

Betweenness Centrality 

위 예시 그래프에서 노드 C의 B.C는 얼마일까? 
A->B로 가는 최단 거리 :  A->C->B
A->D로 가는 최단 거리 :  A->C->D
A->E로 가는 최단 거리 : A->C->D->E 
노드 C는 3가지 서로 다른 최단 경로에에 속하기 때문에 C노드의 B.C는 3이 된다. 
즉, 최단 경로 문제에 있어 중요한 노드로 인식된다. 

명동 지역에서의 그래프 시뮬레이션

 

명동은 다가오는 성탄절에 많은 사람이 찾는 명소로 알려져 있다. 그러므로 장시간에 걸쳐 보행 효율성을 저하시키는 구간의 군집 분산 문제는 해결책이 필요하다. 정체 부분을 해결할 수 있는 몇 가지 방법을 제시하기 위해 우선 도로 그래프 모델링에 제시한 기본 모델의 시뮬레이션을 수행한다.

그림 1. 명동 번화가의 교차로와 도로에 대한 그래프

 

 

기본 모델의 시뮬레이션을 위해 초기 조건을 설계가 필요하다. 그림 1에서와 같이 명동 번화가의 각 노드(교차로)들의 중심성을 계산한 후 상대적으로 더 잘 표현할 수 있도록 정규화하였다. 정규화 수치가 약 0.5 이상이며 중심성이 비교적 높은 12개의 노드(교차로 전체의 약 30%)를 중심으로 연쇄적인 정체에 의한 현상을 보기 위해서 초기 모든 도로의 통행량을 같은 값으로 설정한다.

그림 2. 통행량과 어느 지점을 가야할 때 거쳐야 하는 정도에 대한 모델 시뮬레이션 결과

 

그림 2는 초기 조건에 대한 모델로 시뮬레이션한 결과로 통행량은 두 조건에 따라 통행량이 많은 곳으로 유도되며 도로상에서 매개 중심성이 높은 노드가 선호되는 양상을 확인할 수 있다. 연결선이 굵을수록 많은 통행량이 발생함을 의미하며, 빨간색으로 표기된 도로는 통행량이 최대 통행량의 90% 이상(=가중치 9 이상) 초과하는 것을 뜻한다. 

 

또한 중심성이 높은 노드로 분류되지 않은 [2-10] 구간이 높은 통행량을 보이는데, 이는 인접 도로의 통행량이 정체됨에 따라 발생하는 연쇄적인 효과라고 할 수 있다. 기본 모델의 결과로부터 적용해볼 수 있는 길 찾기와 정체 구간의 해소 방법으로부터 얻을 수 있는 의미를 살펴본다.

정체 상황에서 최단거리 탐색

교차로의 신호등과 관계없이 통행량과 소요 시간은 양의 상관관계를 갖는다고 가정한다. 지도에서 굵은 연결선일수록 통행량이 많고 통행 시간이 오래 걸린다는 것을 의미한다. 아래 그림 3에서 37번 노드에서 4번 노드까지 갈 수 있는 최단 거리를 통행량 유무에 대해 비교해봤다. 

 

신호로 인해 걸리는 시간을 고려하지 않는 해당 모델에서, 37번에서 4번까지 가는 최단 거리(빨간색 경로)는 [28, 23, 13] 교차로를 통과하는 경로이다. 그러나 통행하는 경로의 최소 비용을 계산하는 짧은 거리 탐색 알고리즘을 적용하면 37번에서 4번까지 가는 모든 경로를 비교하여 최소 비용이 가장 작은 경로를 선택한다. 그 결과 38번에서 5번까지 통행이 원활한 경로를 탐색하는 것을 확인했다.

그림 3. 37번에서 출발하여 4번 교차로까지 가는 최단 경로 탐색

 

통행량과 걸리는 시간이 비례하다는 가정하에, 통행하기 위한 최소 시간은 상대적으로 최단 경로보다 교차로를 많이 거쳐 가지만 짧다는 것을 확인했다. 이러한 방법은 소요 시간에 대한 통행량의 실제 영향 정도를 고려해야 할 부분이 필요하지만, 정체 구간을 피해 효율적으로 이동하는 경로를 제시해줄 수 있다. 

정체 현상 해결을 위한 조건 제시

특정 도로에서 발생하는 통행 장애 해결을 위해 아래와 같은 두 조건을 적용했다.

 

1. 현재 교차로에서 인접한 교차로들의 통행 정보 추가
2. 자주 막히는 교차로에 통제조건 추가 (교통경찰 배치에 관한 문제 해결 제시) 

 

그림 4. 인접 교차로의 상황을 추가한 모델의 시뮬레이션 결과

 

그림 5. 기본 모델과 인접 도로 정보를 추가한 모델의 통행량에 대한 엣지들의 분포

 

첫 번째로, 현재 교차로에서 다음 교차로의 상황을 식별하는 다음의 조건을 추가하였다. 

 

[조건 1] 임의의 한 교차로를 선택했을 때, 인접 교차로들의 도로 상황이 상대적으로 원활한 교차로로 갈 수 있도록 조절한다. 

 

그림 4의 시뮬레이션에서 기본 모델을 나타내는 보조 그림과 비교하면 정체 구간이 확연하게 줄어들었다. 그림 5의 통행량 9~10 부분을 통해서 수치상으로 확인했다. 정체 상황을 뜻할 수 있는 통행량이 9 이상인 엣지들의 수가 기본 모델보다 줄어든 것을 확인할 수 있다.

그림 6. 정체가 발생되는 도로를 가진 교차로에 통제 조건을 추가한 모델의 시뮬레이션 결과

 

[조건 2] 통행의 흐름에서 정체가 발생하는 도로를 가진 교차로를 통제한다. 임의의 교차로를 선택했을 때 교차로에 연결되어있는 도로들의 통행량 차이가 상대적으로 큰 경우, 많은 통행량을 가진 도로에서 적은 통행량의 도로로 흐름을 유도하도록 조절한다. 

 

그러므로 그림 6의 시뮬레이션 결과는 정체된 구간이 해소되며 기존에 통행량이 적었던 부분의 유입이 발생하고, 보조 그림에 대하여 28번과 37번 교차로 인근을 비교하면 주변 도로로 통행량이 잘 분배되는 결과를 보인다. 

 

시뮬레이션을 100회 반복한 결과, 각 시뮬레이션마다 통제조건을 평균 약 73회 실시하며, 표 1에서 확인해보면, 통제 조건을 가장 많이 시행한 교차로는 37번(6.44회), 39번(6.11회), 28번(4.86회) 교차로 순으로 높은 것을 확인하였다. 

 

정리하면 통제 조건을 많이 시행한 교차로일수록 원활한 도로를 위한 관리가 필요하기 때문에 도로 통제를 위해서는 교통경찰을 적절한 위치에 배치해야 한다는 기대를 암시한다.

교차로	37	39	28	9	40	…
시행 횟 수 (평균)	6.44	6.11	4.86	3.78	3.65

표 1. 인접한 도로 중, 통행량이 가장 많은 도로와 가장 적은 도로의 차이가 7.5이상인 교차로에 대한 통제 조건으로 시뮬레이션 결과, 내림 차순으로 각 교차로 별 통제 조건을 시행한 평균 횟수

 

결론 및 보행 흐름에서의 GDB 활용성

아래 연구 결과는 그래프 데이터를 통해 조건 탐색과 효율적이고 안정적인 관리를 위한 방향성을 제시한다. 

 

1. 특정 상황을 가정한 그래프 데이터 기반의 모델링을 통해 통행량 해소 조건을 고려한 시뮬레이션을 수행했다. 
2. 중심성이 높은 도로로 통행량이 집중되도록 설정한 기본 모델에서는 특정 구간에서 군집 현상이 나타남을 보였다. 
3. 모델에서 인접한 교차로의 도로 상황에 대한 정보와 밀도가 높은 통행을 원활한 도로로 유도하기 위한 조건을 통해 정체를 해소할 수 있었고, 그 조건이 많이 적용된 교차로(정체 구간)도 찾아낼 수 있었다. 

 

 

그림 7. 도로·교차로 정보를 포함하는 GDB 구성과 활용 예시

 

기존 시뮬레이션에서 그래프 알고리즘을 통해 보행 흐름을 해소시킬 수 있는 이론에 대해 알아봤지만, 이 그래프 모델에 신호, 방향성 등의 도로상 환경과 같은 조건들을 추가하면 기존 모델을 넘어 더 고도화된 관리 시스템을 구현해볼 수 있을 것이다. 이러한 시스템은 그래프 DB로 구현하는 것이 그래프 데이터 활용과 그래프 분석에서의 조회 및 시간 로그 활용 방면 등에서 가장 적합하다.

 

기술로 사회적 문제를 해결하다

특정 행사, 혹은 특정 지역의 예상 통행량은 매해, 매번 예상 범위를 넘어서고 있다. 최근 들어서 더욱 그렇고, 과밀화된 서울을 비롯한 수도권에서 더욱 그렇다. 

 

이와 같은 문제의 해결을 위해서는 막대한 예산과 인력의 투입이 불가피하다. 그러나 자원이 한정된 상황에서 모든 부분들을 예측해 사전에 관리 및 통제하는 것 또한 매우 어려운 일이다.

 

이를 위해서는 그래프 기술의 힘이 절대적으로 필요하다. 한정된 자원을 가장 적재적소에 활용할 수 있도록 하는 가이드라인과 고도화된 운영 매뉴얼을 확립하고, 또 이를 바탕으로 직접적인 문제 해결을 돕는 방향이 가장 바람직할 것이다. 

 

글: 비트나인 그래프 사이언스 R&D 센터

 

---

 

트렌디한 그래프 기술과 IT 소식을 뉴스레터로 받아보세요!

https://bitnine.net/ko/subscribe/

 

제품 및 기술문의

070-4800-3517  |   agens@bitnine.net