중간거리분석 알고리즘 고도화에 대한 고민

 

약속 스케쥴링 서비스 MeetHare 프로젝트를 진행하며, 유저별 출발지를 기반으로 중간거리를 분석하여 제공하는 기능을 담당하였다.

이 과정에서 중간지점 분석을 위한 알고리즘을 어떻게 고도화하여 사용자에게 가장 의미있는 데이터를 제공할 것인가에 대한 고민이 계속되었다. 아래는 기획부터 알고리즘 고도화까지 6주간의 고민과 생각의 내용을 정리한 내용이다.

 

🚇 중간거리 찾기

1차개발 : 무게중심을 활용하여 중간지점 구하기

유저별 물리적인 위치(위,경도 좌표)를 고려하여 무게중심을 구한 후, 카카오 api를 사용하여 주변 지하철 역을 찾기

 

가장 간단하지만 정확하게 물리적 위치를 계산할 수 있는 방법이라고 생각하여 위의 방법을 선택했다. 

 

아래는 카카오api 를 사용하여 주변 지하철 역 목록을 가져온 결과이다.

역삼역을 기준으로 거리를 2000km 로 설정한 결과 신논현, 언주, 선정릉, 강남, 선릉, 한티역이 출력되는 것을 확인할 수 있다. 

이때 환승역의 경우에는 2번이상 출력되는 경우가 있었기에, 뒤의 노선정보를 제외하고 역 이름만 Set에 담아서 사용하는 방식을 선택했다.

좌표사이의 거리 구하기

초기에는 위경도 좌표사이의 거리를 계산하기 위하여 지구의 곡률을 고려하여 계산했다. 

그러나 좌표값으로 계산하다보니 부동소수점 계산으로 인한 오차가 계속 발생했다. 

 

💡 해결

제공하고자 하는 서비스 특성 상 국내, 특히 수도권 지역의 유저층이 두터운만큼, 도시와 도시 사이의 적은 거리를 계산하고 오차를 줄이기위해 지구의 곡률을 고려하지 않고 평면 좌표 시스템에서 직선거리를 계산하도록 수정했다. 

 

2차개발 : 등시선도를 활용하여 중간지점 구하기

ORS Maps(Open Route Service) 에서 제공하는 등시선도를 사용하여 일정 시간동안 사용자 별 이동할 수 있는 거리를 체크한다. 생성되는 도형의 교차되는 영역(1)을 구하고, 해당 영역에 속해있는 지하철역을 구한다. 지하철역 목록데이터를 추천파트(2)로 넘긴다.

 

고민1

모든 지하철역 목록 데이터를 추천파트로 넘겨서 추천알고리즘을 통해 사용자에게 중간지점을 추천할 것인가
               VS  목록데이터를 자체적으로 우선순위를 계산한 뒤 일부의 상위 데이터만을 추천파트로 넘길것인가 에 대한 고민

우선 프로젝트가 MSA 방식으로 진행되는 만큼, 하나의 로직 안에 여러개의 도메인이 관여하지 않도록 하기 위해 후자의 경우를 선택했다. 그 이유는 외부 api사용이 증가할수록 필연적으로 로직 수행시 소요되는 시간이 증가하기 때문에, 최우선적으로 외부api 사용을 최소화 하기 위한 선택이었다. 또한 추가적으로 상위데이터를 추리는 방식으로 (1)최소시간이 가장 작은 경우 or (2)최대시간이 가장 작은 경우 or (3)평균시간이 가장 작은 경우에 대해 고민하였는데, 여기서는 평균시간이 가장 작은 경우를 기준으로 상위데이터를 추리기로 결정했다. 또한 추가적으로 크롤링을 통해 수집한 해당 역 주변의 인프라 개수도 함께 고려했다. 

 

고민2

교차되는 영역을 어떻게 구할 것인가

등시선도로 출력되는 도형의 n개의 각이 몇개나 생길지, 불확실한 상황에서 알고리즘을 구현하기에는 비용이 너무 많이 들 것이라고 판단했다. 따라서 중심(사용자위치)에서 생성되는 각의 점까지의 거리를 구한 후, 그 평균 거리를 반지름으로 설정하고 원을 그린후, 생성되는 원끼리의 교차영역을 구하기로 결정했다.

 

문제

위의 방식으로 기능을 구현한 결과, 사당역과 선릉역을 비교하면 중간지점좌표가 37.4905235, 126.9815495 가 나왔으며, 눈으로 보기에도 한쪽으로 치우친 느낌이 강했다. 위치는 서울특별시 동작구 동작대로33나길, 이수역 근처이다. 결과적으로 출력되는 추천 지하철 역 목록은 다음과 같았다.

⇒ 총신대입구역, 내방역, 동작역, 사당역, 남성역, 이수역, 구반포역

 

 

지형을 고려한 등시선도를 사용하였을 때, 불규칙한 다각형의 평균값을 구해 계산했기 때문에 오차가 심했다는 문제점을 발견했다. api를 사용했을때 반환되는 response 는 꼭짓점 좌표밖에 없기때문에 해당 등시선도가 어떤 형태를 가지고 있는지 판단이 불가했으며, 따라서 위의 알고리즘을 도입하기에는 리스크가 크다고 생각했다. 또한 짧은 시간안에 정확한 값을 도출해낼 수 있었던 무게중심을 활용한 방식이 더 효율적이었다고 판단했으며, 동시에 진행중인 지하철 역간의 교통상황과 시간을 고려한 개발 방식에 집중하는 것이 좋다고 생각했다.

따라서 등시선도를 활용한 알고리즘은 아쉽지만 실제 서비스에 도입하지는 않았다. (시간과 애정을 많이 쏟은 알고리즘이라 폐기하기에 너무 아까웠다..)

 

 

3차개발 : 실시간 교통정보를 고려, 역과 역 사이의 소요시간을 활용하여 중간지점 구하기

 

우리나라에 있는 모든 지하철역 약 800여개의 역과 역 사이의 소요시간을 모두 계산한 후 자체 Database 에 저장하였다. 계산은 간단한 코드를 통한 크롤링 방식을 사용하였으며, 결과적으로 자체 Database에는 약 65만개의 데이터가 수집되었다. 이 방법은 데이터를 수집하는 데에 6명의 팀원이 모두 참여하였는데도 불구하고 2주 가까이 시간이 소요됐다. 데이터 수집에 어려움이 있었지만, 결과적으로 완성된 DB데이터를 사용하여 유저에게 가장 빠르고 정확한 정보를 제공할 수 있었기에 보람이 있었다.