4_OSRM

OSRM(Open Source Routing Machine)

OSRM 개념

• OSRM은 개방형 지리적 데이터 OSM(Open Street Map)을 활용하여 자동차 자전거, 보행자의 라우팅 프로필을 제공하는 라우팅 엔진으로, 최단경로탐색_알고리즘 중 Customizable Contraction(CH) 알고리즘 기반이다.
• OSRM은 도로 유형별 가중치, 시설물 진입 패널티, 실시간 도로 정보(road network), 차량 회전(turn costs) 등을 고려하여 목적지까지 최적 경로를 탐색한다. 또한, 사용자가 원하는 logic으로 라우팅 알고리즘과 가중치를 customization 하는 기능을 제공하여, 특정 도로 조건, 교통 패턴, 또는 지리적 특성에 따라 최적 경로를 조정할 수 있다.

관련 서비스에서의 CH, CCH

• 네이버 지도

  • 2020년부터, 네이버 지도는 도보 경로 탐색 기능에 OSRM(Open Source Routing Machine)을 활용하고 있다. 네이버 지도는 이용자 중심 기획을 핵심 원칙으로 삼아, 보행자가 도보로 이동할 때 마주할 수 있는 신호등, 골목길 등 다양한 도로 상황을 고려하여 최적의 경로를 제공한다. 최적 경로와 최단 경로가 항상 일치하지 않을 수 있기 때문에, 네이버 지도는 OSRM을 활용하여 도로 유형별로 가중치를 부여하고, 시설물 진입시 패널티 적용, 다중 입구점을 고려한 경로 안내, 특정 도로에서의 회전 가중치를 달리하였다.
  • 이석원, (2020, ). 주니어 개발자의 도보 길찾기 서버 개발기

• 카카오 맵

  • 카카오맵도 CCH 알고리즘을 활용하여 경로 제공 서비스를 개편하였지만 custom한 방법에 대한 구체적인 정보는 공개하지 않았다.
  • CCH의 성능(shortcut 개수, Elimination Tree 깊이)은 Contraction의 node ordering을 어떻게 하느냐에 크게 좌우된다. 카카오맵에서는 오픈소스인 Inertial Flow Cutter를 사용하여 ordering을 하고 있다.
  • Wade.Lim (2021.05). 카카오맵이 빠르게 길을 찾아주는 방법: CCH를 이용한 개편기
  • rjwltakf090 (2024.01). 카카오맵에서는 가중치를 어떻게 관리하나요?

• 티맵

  • 티맵은 CCH 알고리즘 기반, Thor라는 자체 엔진을 개발하였고 Inertial Flow로 ordering 하였다.
  • 2주에 한번씩 shortcut을 만드는 Metric-Independent Preprocessing을 진행하고, 교통 정보, 유고 정보 등 다양한 정보로 인한 arc의 비용 변화로 인한 업데이트, Metric-Dependent Customization은 수시로 진행하고 있다.
  • 티맵은 도로 유형별, 어린이 보호 구역 등을 고려하며 거리와 시간에 대한 가중치를 달리하여 경로를 제공하고 있다.
  • T map Trend Map (2020. ). T맵 경로 추천의 비밀

• 배달의 민족

  • 배달의 민족에서는 2021.12에 배달료를 직선거리가 아닌 내비게이션 실거리로 산정하기 위해 OSRM을 도입하였다. OSRM은 API 호출 건수에 따른 비용이 없고, 서버 운영 비용만 부담하면 되며, 트래픽도 줄일 수 있어 이러한 결정을 내렸다. 하지만 좌회전 금지, 유턴 금지, P턴과 등의 교통 규제를 제대로 반영하지 못해, 2023.02에 내비게이션 엔진을 아이나비시스템즈로 교체하였다.
  • 고급협동조합의 OSM (2022. 10). 배달의 민족 내비게이션에 숨어 있는 오픈스트리트맵과 개방형 데이터가 추구하는 이상적인 선순환
  • 전남혁 (2021.12). 배민 배달료, 직선거리→내비 실거리로 기준 변경
  • 윤지혜 (2022.09). 배민 ‘라이더 내비’ 바꾼다는데…소비자 배달비 오르나

뽀송길에서의 OSRM

• 시스템 아키텍처

  
  • 본 프로젝트에서는 뽀송 도보 경로가 포함된 대중교통 경로를 제공하는 서비스 개발을 목표로 한다. 이를 위해 비를 막아주는 구조물이 있는 길, 예를 들어 터널(수로, 산사태 방지 통로, 파이프를 제외한 사람이 지나갈 수 있는 건축물 통로)이나 covered 속성(사람이 지나갈 수 있으며 부스, 아치형 지붕, 가로수, 지붕있는 통행로 등 비를 막아주는 객체)을 가진 길의 가중치를 낮추고, 어드밴티지를 부여하는 시스템을 구현한다. 이 시스템을 Docker를 활용하여 서버에 구축함으로써, 이용자들에게 비의 영향이 최소화된 최적의 대중교통 경로를 안내한다.

• 시스템 구조도

  
  • 기상 정보 관리 모듈과 경로 생성 모듈 등으로 구성된 시스템 구조도를 설계하였다.
  • 경로 생성 모듈에서는 기상 정보 관리 모듈에서 데이터베이스에 저장한 강수 정보를 활용하여, 강수에 최소한으로 노출되는 출발 시각과 대중교통 경로를 탐색한다. 강수의 영향을 최소화하기 위해 도로 유형별에 따라 가중치를 조정하고, 시설물 및 도로 진입에 패널티를 부여할 수 있는 OSRM을 활용한다. OSRM에서 사용하는 지도 레이어는 JOSM(Java OpenStreetMap Editor)을 이용하여 서울의 linestrings.shp만 추출하고, 교량, 터널 레이어를 병합하였다.(서울시_지리공간_데이터_만들기)

• 경로 안내 프로세스

  
  • 사용자가 KAKAO API를 이용하여 출발지와 목적지를 입력하면, ODsay API를 통해 대중교통 경로를 탐색한다. 이렇게 전처리된 데이터를 바탕으로 대중교통 경로 내 각 도보 구간에서 비를 덜 맞는 경로를 탐색한다.
  • setup 단계에서는 사람이 통행할 수 없는 교량과 터널을 제외하도록 처리하였다.
  • process_way 단계에서는 일반 도보 경로의 속도를 낮추어 가중치를 높이고, 비를 막아주는 구조물이 있는 도보 경로의 속도를 높이고 어드밴티지를 부여하여 가중치를 낮추는 방식으로 데이터를 전처리 하였다.
  • 안내 생성 단계 에서는 각 도보 구간의 소요 시간과 강수 정보를 결합하여 예상 강수량을 산출한다. 이 정보를 통해 2시간 이내에 강수에 최소한으로 노출되는 출발 시각을 결정한다.

• 뽀송 경로 가중치

  
  • 뽀송_가중치_설정_과정을 통해 가중치를 다음과 같이 설정 하였다.
  • $facto{r}_1$은 도로의 폭에 따른 보정 계수를 나타내며, 대로인 경우에는 1.1을, 골목길인 경우에는 1.0을 사용하여 도로 폭이 넓은 경로를 우선적으로 탐색한다.
  • $facto{r}_2$은 도로의 특성을 나타내며, 터널인 경우에 는 12.0을, 구조물이 있는 경우에는 10.0을, 그 외 일반 경로인 경우에는 0.1을 사용하며 터널이나 구조물 특성이 있는 경로에는 추가적으로 60의 어드밴티지를 부여하였다.
  • 이를 통해 비를 완전히 피할 수 있는 터널 도로나 비를 피하는데 도움이 되는 구조물이 있는 도로, 일반 도로의 속도를 다르게 설정하고, 구조물 특성이 있는 경로에는 60의 어드밴티지를 부여하여 해당 경로를 우선적으로 탐색하도록 구현하였다.

• 경로 탐색 시나리오

  
  1. 뽀송길 시스템에 요청을 하면 현재 세션이 인증된 세션인지 확인한다. 저장된 세션일 경우 바로 메인페이지로 이동한다. 그렇지 않을경우 인증 도메인으로 이동하여 인증을 수행하도록 한다. 이때, 회원가입, 비밀번호 변경 을 추가적으로 수행할 수 있다.
  2. 메인 페이지에서는 서울시 전체 시간별 강수정보, 현재 위치의 상세 기상정보를 확인할 수 있다.
  3. KAKAO API 장소 검색(POI)을 통해, 또는 즐겨찾기에 저장된 데이터로 출발지와 도착지를 지정한다.
  4. 지정된 출발지 도착지 간의 대중교통 경로를 ODsay API와 도보 경로 OSRM API를 이용해 탐색한다.
  5. 탐색한 경로들 중 하나를 사용자가 선택할 수 있다. 사용자가 경로를 선택하면 해당 경로에서 도보 구간의 강수량을 계산하여 지도상 아이콘으로 표시해준다.