소요시간을 기준으로 중간 역을 검색하는 과정

개요

해당 포스팅에서는 오디고(ODEEGO) 프로젝트를 할 때, 중간 역을 산출하는 어떻게 산출하는지 과정을 서술할 예정입니다. 

 

저희 프로젝트에서 중간 지점을 찾는 기준은 시간입니다. 약속을 잡을 때  직선 거리나 다른 기준보다는 시간이 비슷한 곳에서 약속 장소가 정해진다고 생각했습니다.

 

시간으로 중간역을 검색하기 위해서는 각 역과 역사이의 소요시간을 알 필요가 있었습니다. 소요시간들을 바탕으로 합리적인 기준을 통해 중간 역을 찾을 수 있기 때문입니다. (합리적인 기준에 대해서는 밑에서 후술하겠습니다.)

 

그래프 알고리즘 이용

역과 역의 소요시간을 구하기 위해 가장 먼저 그래프 알고리즘으로 시도했습니다. 그래프 알고리즘은 말 그대로 먼저 그래프라는 자료구조가 있어야 합니다. 현재 MySQL 을 사용하여 지하철 노선도를 모두 저장하기에 큰 한계를 느꼈습니다. 역을 저장하고, 역과 역 사이의 간선의 소요시간 정보 등등이 RDBMS 에 넣기에 적합하지 않았습니다. 물론 NoSQL 의 Neo4j 등 그래프 데이터베이스가 있지만 러닝 커브와 프로젝트 마감 기한이 얼마 남지 않은 것을 고려하여 선택에서 제외되었습니다.

스크래핑 이용

그래프 구조의 한계를 느껴 이번에는 네이버 맵의 지하철을 스크래핑하여 소요시간만 구하는 것으로 진로를 변경하였습니다. 이는 모든 역과 역 사이의 소요시간을 구하여 미리 저장해 놓고 계산 요청이 들어오면 꺼내쓰는 방식입니다. 

합리적인 기준

이제 소요시간이 있다고 가정하고 진행해보겠습니다. 출발역부터 다른 모든 역까지의 소요시간이 있고 이를 바탕으로 합리적인 기준을 통해 역을 선출합니다.

여기서 합리적인 기준을 처음에는 평균을 이용하였습니다. 한 개의 도착역 후보지에는 n 개의 출발지로부터 오는 경로가 n 개가 존재하는데, 이 경로들의 소요시간의 평균을 이용하는 아이디어였습니다. 평균이 가장 낮은 것부터 중간 역으로 제출하여 사용자에게 보여주는 것입니다. 

하지만 평균은 모든 사람이 공평하지 않는 문제가 있었습니다. 소요시간이 1, 16, 1 과 7, 7, 7 처럼 전자처럼 한명이 극단적으로 소요시간이 긴 경우가 존재할 수 있었습니다.

이 문제를 보완하기 위해 표준편차도 같이 고려하는 아이디어가 나왔습니다. 극단적으로 값이 튀는 것을 방지하고자 표준편차를 도입했지만, 문제는 구현의 어려움에 있었습니다. 경로들을 정렬할 때 한번에 2가지 기준으로 정렬할 수 있지만, 한번에 두가지 기준을 고려한다는 뜻은 아닙니다. 하나의 기준이 같아야 그 다음 기준을 고려하기 때문에 원하는 대로 정렬이 되지 않았습니다.

마지막으로 나온 아이디어는 둘을 정규화하여, 더한 후 이 값으로 정렬하는 것이었습니다. 정규화를 하여 0에서 1 사이 값으로 각각 만들면 모든 경로에 대해 0에서 2 사이 값이 나오게 됩니다. 이 값이 가장 작은 것이 의도했던 결과가 될 것입니다.

정리

정리하면 스크래핑을 통해 소요시간들을 찾고, 출발역부터 모든 역까지의 소요시간을 가져온 다음 평균과 표준편차를 이용하여 중간 역을 찾는 것입니다.