대중교통 길찾기 알고리즘 개발

General Transit Feed Specification (GTFS)

미국을 포함한 많은 나라들이 GTFS 포멧으로 대중교통 정보를 제공한다. GTFS란 쉽게 말해 대중교통 정류장 위치, 출발/도착 시간을 포함한 스케쥴 정보를 표현하는 표준화된 대중교통 정보이다. 대중교통을 운영하는 기관들이 작성해서 google 등의 사기업들로 넘겨주는 것으로 구글맵은 이 정보를 가공하고 알고리즘을 제공해 대중교통 경로 정보를 제공하는 것이다. 

출발지 A에서 도착지 B까지 가는 최적 대중교통 경로 정보를 알고자 할때 구글 direction api 를 이용하면 쉽다. 

youngseokim.tistory.com/100

구글 대중교통 경로 api 이용하기 google transit direction api

하지만 API 사용료를 지불해야하기 때문에 제약이 있다. 직접 대중교통 최적 경로를 찾는 알고리즘을 개발할 수는 없을까? 

 

도로 네크워크에서 최적 경로를 찾는 문제는 비교적 간단하다. 도로 네트워크를 node, edge로 구성된 graph로 표현하고 다익스트라 (Dijkstra) 알고리즘 (혹은 그의 변형 ex. A* 알고리즘)을 적용하는 방식이 국룰이다. python의 Networkx 라이브러리를 이용하면 간단하게 구현할 수 있다.  

 

하지만 대중교통 네트워크의 경우 조금 더 복잡한데, 버스와 지하철 등 대중교통은 정해진 시간표를 따라 운행하기 때문에 고도화된 모델링이 필요하다.

 

 

아래 포스팅은 파이썬 예제 코드와 함께 최적 대중교통 경로를 찾는 한가지 방식을 제시한다.

kuanbutts.com/2020/09/12/raptor-simple-example/

RAPTOR transit routing algorithm basics