[Navigation] #2 OSRM을 알아보자

이번 글에서는 직접 경로 탐색을 실습해보기 위해 오픈소스 경로 탐색 엔진을 살펴보고자 한다.

대표적인 오픈소스 경로 탐색 엔진으로는 OSRM, GraphHopper, Valhalla 가 있다.

이 중 OSRM (Open Source Routing Machine) 을 알아보자

 

OSRM 이란?

지도 데이터를 바탕으로 출발지와 목적지 사이의 최적 경로를 빠르게 계산해주는 오픈소스 라우팅 엔진이다.

지도 데이터는 주로 OpenStreetMap을사용한다.

C++ 로 구현되어 있으며, 다양한 교통 프로파일 지원 (car, bike, foot 등) 한다.

OSRM의 기본 알고리즘은 MLD (Multi-Level Dijkstra)이며 CH(Contraction Hierarchies)도 사용가능하다.

 

https://project-osrm.org/

Project OSRM

OSRM Project 의 공식 웹사이트이다.

OSRM의 개요, 문서(API 문서), 사용 방법, 데모 서버, 그리고 GitHub 저장소 링크 등을 제공한다.

Project OSRM에서 VIEW DEMO로 서울에서 부산까지 차로 이동하는 경로를 검색한 결과이다🚗

Project OSRM에서 VIEW DEMO로 서울에서 부산까지 도보로 이동하는 경로를 검색한 결과이다🚶‍♂️

Project OSRM에서 VIEW DEMO로 서울에서 부산까지 자전거로 이동하는 경로를 검색한 결과이다🚲

 

OSRM 데모 지도에서 진한 파란색 선은 실제 도로 네트워크를 기반으로 계산된 "이동 가능한 경로"를 의미하고, 흐린 보라색 선은 라우팅 그래프가 끊긴 구간을 직선으로 보조 연결한 표시선이다.
즉, 진한 선은 알고리즘이 실제로 통과할 수 있다고 판단한 길이고, 흐린 선은 지도 데이터상 연결 가능한 경로가 부족하거나 제한되어 임시로 이어 보여주는 구간이다.
이 두 선이 이동 방식(자동차, 도보, 자전거)에 따라 다르게 나타나는 이유는 프로파일별로 사용할 수 있는 도로 종류와 제한 규칙이 서로 다르기 때문이다.
예를 들어 자동차는 고속도로와 차량 도로 중심으로, 도보는 보행 가능한 길 중심으로 서로 다른 도로 그래프를 사용해 경로를 계산한다.
OSRM은 주로 OpenStreetMap 데이터를 기반으로 각 이동 수단별 접근 가능 여부를 다르게 해석하기 때문에 동일한 출발지와 목적지라도 경로 구조가 달라진다.
그 결과 실제로 연결 가능한 구간(진한 선)과 그래프가 단절된 구간(흐린 선)의 위치와 형태가 이동 방식마다 다르게 표시된다.

 

OSRM 동작

OSRM은 MLD (Multi-Level Dijkstra) , CH (Contraction Hierarchies) 두 가지 알고리즘을 지원한다.
기본값이 MLD이며, CH로도 운영할 수 있다.

알고리즘에 따라 전처리 단계가 달라진다.

MLD 사용 시 동작

OSRM은 MLD 알고리즘을 사용할 경우 크게 4단계로 동작하며, 전처리와 가중치 반영이 분리된 구조가 특징이다.

 

1. Extract

osrm-extract map.osm.pbf

• OSM 데이터를 파싱하여 도로 네트워크 그래프를 생성
• Lua 프로파일(car.lua, bike.lua, foot.lua 등)을 적용
• 도로의 속도, 통행 가능 여부, 방향성(일방통행) 등의 가중치 설정
• 이후 라우팅에 사용될 기본 그래프(.osrm 파일) 생성
  (지도 데이터는 주로 OpenStreetMap 기반)

2. Partition

osrm-partition map.osrm

• 그래프를 여러 개의 셀(Cell) 단위로 공간 분할
• 다단계(Multi-Level) 탐색을 위한 계층 구조 생성
• 장거리 경로 탐색 시 상위 레벨 셀을 우선 탐색하도록 준비
• 이후 탐색 범위를 크게 줄여 성능을 향상시키는 역할 수행

3. Customize

osrm-customize map.osrm

• Partition 단계에서 생성된 셀 구조 위에 실제 가중치를 반영
• 프로파일 변경, 속도 변경 등 가중치 재계산 수행
• 교통 정보나 비용 함수가 변경될 경우 이 단계만 재실행 가능
• CH와 달리 전체 전처리를 다시 하지 않아도 되는 것이 큰 장점

4. Routed

osrm-routed --algorithm mld map.osrm

• HTTP 라우팅 서버 실행
• 셀 기반 다단계 탐색(MLD)으로 경로 계산 수행
• /route, /table, /match, /nearest 등의 API 제공

 

MLD에서 다시 전처리해야 하는 경우

1. extract부터 다시 해야 하는 경우

그래프 구조가 바뀔 때, "도로 네트워크 자체"가 달라지는 상황

예들 들어 다음과 같은 경우이다.

• .osm.pbf 지도 데이터가 변경됨 (e.g. south-korea 최신 데이터로 교체)
• Lua 프로파일 수정 (car.lua, bike.lua, foot.lua)
• 도로 필터링 로직 변경 (e.g. 골목길 제외 정책)
• oneway, 접근 가능 도로 규칙 수정
• 속도 계산 로직 자체 변경 (e.g. maxspeed 처리 방식 수정)
• e.g. car.lua에서 residential 도로 속도를 30 → 10으로 수정 → extract 다시 필요

Lua 프로파일은 도로 선택 + 기본 가중치 + 접근 가능 여부를 결정한다.

즉 내부 그래프(edge)가 새로 생성되기 때문에 Lua 프로파일이 수정됬을때 extract부터 다시 전처리를 해야한다.

extract가 바뀌면 → partition + customize도 반드시 다시 수행

 

2. partition부터 다시 해야 하는 경우

그래프 구조는 같지만, 분할 구조를 다시 만들어야 할 때

• extract 다시 수행했을 때
• 분할 전략 변경했을 때
• e.g. 지도 데이터 교체 → extract 다시 실행됨 → 기존 partition 무효 → partition 다시 필요

partition → customize 다시

 

3. customize만 다시 하면 되는 경우

• 실시간 교통 반영
• 속도 값 변경
• 시간대별 가중치 변경
• e.g. 정체 구간 속도 60km/h → 20km/h로 변경 → customize만 다시 실행

customize만 실행

 

OSRM의 전체 구조 (CH 사용 시)

OSRM은 CH알고리즘을 사용할 경우 크게 3단계로 동작한다.

1. Extract

osrm-extract map.osm.pbf

• OSM 데이터를 파싱
• Lua 프로파일(car.lua, bike.lua 등)을 적용
• 도로 그래프 생성
• 각 도로의 가중치(속도, 접근 가능 여부 등) 결정
  (지도 데이터는 주로 OpenStreetMap 기반)

2. Contract

osrm-contract map.osrm

• 그래프의 노드를 중요도 순으로 축소(Contraction)
• Shortcut(지름길 간선) 생성
• 초고속 경로 탐색을 위한 계층적 그래프 구조 생성
• 이후 라우팅 속도가 매우 빨라지는 핵심 단계

3. Routed

osrm-routed --algorithm ch map.osrm

• HTTP 라우팅 서버 실행
• 전처리된 CH 그래프를 기반으로 초고속 경로 탐색 수행
• /route, /table, /match 등 API 제공

CH에서 다시 전처리해야 하는 경우

1. extract를 다시 해야 하는 경우

그래프 구조 자체가 바뀌는 경우에는 extract부터 다시 수행해야 한다.
이 경우 contract도 함께 다시 실행해야 한다.

대표적인 경우는 다음과 같다.

• 지도 데이터(.osm.pbf) 변경
• 새로운 지도 버전 사용
• Lua 프로파일 변경 (car.lua, foot.lua, bike.lua)
• 도로 접근 규칙 변경 (e.g. 특정 도로 차량 통행 가능 여부 변경)
• 태그 해석 로직 변경 (highway, oneway, access 등)
• turn restriction 처리 로직 변경
• 프로파일을 car → bike 등으로 변경

이러한 변경은 그래프의 노드/엣지 구조 자체를 바꾸기 때문에 다음과 같이 전체 전처리를 다시 수행해야 한다.

osrm-extract → osrm-contract

 

 

 2. contract만 다시 해야 하는 경우

그래프 구조는 그대로지만 가중치(Weight)만 변경되는 경우에는 extract는 생략하고 contract만 다시 수행할 수 있다.

예를 들어 다음과 같은 경우다.

• 도로 속도 값 변경
• 프로파일에서 속도 계산 로직 수정
• turn penalty 값 변경
• 특정 도로 비용(weight) 조정

이 경우 그래프의 노드와 엣지는 동일하지만 비용 계산이 달라지므로, shortcut 비용을 다시 계산해야 한다.

따라서 다음 단계만 다시 실행하면 된다.

osrm-contract

 

💡왜 MLD, CH 중 MLD가 OSRM의 기본 알고리즘일까?

1. CH 전처리 비용이 MLD보다 더 큼

• contract 단계가 무겁다
• 메모리 사용량 증가

2. 가중치 변경 유연성

• CH는 가중치 변경 시 재계약(contract) 필요
• MLD는 customize 단계만 다시 실행하면 됨

3. 다양한 프로파일 지원

• OSRM은 자동차/도보/자전거 등 다양한 모드를 지원
• MLD 구조가 이런 확장에 더 유리

OSRM은 CH와 MLD를 모두 지원하지만, 전처리 부담과 가중치 갱신 유연성을 고려해 MLD를 기본 알고리즘으로 채택하고 있는 것으로 보인다.

 

OSRM의 장점

• 매우 빠른 응답 속도
• OSM 기반으로 전 세계 적용 가능
• Lua 프로파일을 통한 가중치 커스터마이징
• HTTP API 제공으로 서비스 연동 용이

 

OSRM의 한계

• 기본적으로 정적 그래프 기반
• 실시간 교통 반영은 추가 구현 필요
• 상용 네비게이션 수준의 분산 전략은 별도 설계 필요

 

💡OSRM은 OSM 전용인가? 다른 지도 데이터도 사용할 수 있을까?

결론부터 말하면 OSRM은 OpenStreetMap(OSM)을 기본 입력 데이터로 설계되었지만,
반드시 OSM 데이터만 사용해야 하는 것은 아니다.

다만 실제 파이프라인 구조상 OSM 형식에 맞춘 데이터가 필요하다.

 

1. OSRM이 OSM 데이터를 기본 전제로 설계된 이유

Open Source Routing Machine(OSRM)은 초기 설계부터 OpenStreetMap 데이터를 입력으로 사용하도록 만들어진 라우팅 엔진이다.

OSRM의 전처리 파이프라인을 보면 다음과 같은 특징이 있다.

• osrm-extract 단계는 OSM PBF 파일을 직접 입력으로 사용
• Lua Profile이 OSM 태그(예: highway, oneway, maxspeed)를 기반으로 가중치 생성
• 도로 그래프 생성 과정이 OSM 노드/웨이 구조를 기준으로 구성됨

즉, OSRM은 특정 지도 공급자가 아니라 OSM 데이터 구조와 태그 스키마를 기준으로 동작하는 구조라고 보는 것이 더 정확하다.

여기서 중요한 점은 "OSM 서비스 전용"이 아니라 "OSM 형식의 도로 네트워크를 입력으로 요구하는 엔진"이라는 것이다.

 

2. OSM이 아닌 지도 데이터도 사용할 수 있는가?

가능하다. 다만 직접 입력하는 것이 아니라 OSM 호환 형식으로 변환하는 과정이 필요하다.

실무에서 사용하는 대표적인 방법은 다음과 같다.

 

(1) 외부 지도 데이터를 OSM 형식으로 변환

가장 현실적이고 일반적인 방법이다.

예를 들어 자체 구축한 지도 DB, 정부 제공 도로 네트워크 데이터, 상용 지도 벤더 데이터와 같은 데이터를

• OSM XML 또는 PBF 형식으로 변환
• OSM 태그 스키마로 매핑
• 이후 OSRM 전처리 파이프라인에 입력

하는 방식으로 활용할 수 있다.

실제로 OSRM 공식 문서와 커뮤니티에서도
"커스텀 데이터를 사용할 경우 OSM과 유사한 구조로 변환하여 사용" 하는 방식이 일반적인 접근으로 안내된다.

 

3. OSRM 코드를 수정해서 다른 포맷을 직접 지원할 수 있을까?

이론적으로는 가능하다. 하지만 현실적으로는 거의 선택되지 않는 방법이다.

필요한 수정 범위는 다음과 같다.

• extractor 모듈 수정
• 태그 파싱 로직 재구현
• 내부 그래프 생성 구조 변경

문제는 OSRM의 전처리 파이프라인이 OSM 데이터 구조와 강하게 결합되어 있기 때문에 직접 포맷을 확장하면 유지보수 난이도가 매우 높아진다는 점이다.

특히 업스트림 업데이트와 충돌 가능성, 커스텀 포크 유지 비용 증가, 테스트 복잡도 증가 등의 이유로 상용 서비스 환경에서도 엔진 수정 방식보다는 데이터 변환 방식을 선호한다.

 

즉 OSRM은 기본적으로 OSM 데이터를 전제로 설계되었지만, 다른 지도 데이터도 OSM 형식으로 변환하면 사용할 수 있다.

 

마무리..

이번 글에서는 오픈소스 라우팅 엔진인 OSRM를 이론 중심으로 살펴보았다.
다음 글에서는 실제 환경에서 OSRM을 구축하고 경로 탐색을 수행하는 실습 과정을 이어서 다뤄보도록 하겠다.