맵 매칭(Map Matching)

맵 매칭(map matching)은 GPS처럼 측정된 궤적(trajectory)을, 노드와 링크로 구성된 기존의 지도(map)에 맞추는(matching) 작업이다. 차량 내비게이션의 경우에도 GPS의 궤적들을 기존에 입력된 지도 위에 매칭시킴으로써 주행하고 있는 도로의 전방 상황을 미리 안내해주기도 한다. 간혹 안내된 경로 밖으로 벗어나서 주행할 경우, 일정 시간이 지나면 경로 이탈을 인지한 후 다시 돌아가는 길을 안내해 주기도 하는데, 이는 측정된 궤적을 토대로 가장 그럴법한 링크들로 매칭시키는 작업이 끊임없이 반복되고 있기 때문이다.

 

가장 쉽게 해 볼 수 있는 맵 매칭 방식은 측정된 점으로부터 가장 가까운 링크에 곧바로 점들을 수선을 내려 투영시켜주는 방식이다. GPS 측정 주기가 매우 짧고 보행처럼 속도가 느릴 경우에는 사실 이렇게 매칭시켜도 대부분 잘 맞는다. 가끔 GPS가 튀는 경우에만 별도로 잡아주면 된다. 

그러나 실제 측정 데이터는 그렇게 깔끔하지 않은 경우가 대부분이다. 약간 튀기도 하는데 10m 혹은 그 이상의 오차가 발생할 때도 있다. 고층 빌딩 사이에 있을 때도 반사때문에 이런 현상이 심하게 나타난다. 차량으로 고속도로를 빠져나가려고 원형의 도로를 돌아 나갈 때 측정값이 충분히 남지 않는 경우도 있다. 그래서 좀 더 고도화된 알고리즘들이 시도되는데, 최근에는 HMM(Hidden Markov Model, 은닉 마르코프 모델)이 많이 사용된다.

'은닉'이란, 진짜 상태는 숨겨져 있고 우리가 알 수 있는 것은 관찰값들일뿐이라는 의미다. 즉, 차량은 실제로 어떤 도로 위를 지나갔지만, 우리는 그 실제 경로는 알지 못하고 GPS 기기로 측정된 위치만 알고 있다. 실제 움직임과 어느정도 오차가 있는 그 관찰값을 통해 가장 그럴법한 확률이 나오는 경로들을 추정하는 작업이 바로 맵 매칭 작업이고, 여기에 사용되는 로직은 비터비(Viterbi) 알고리즘이다.

 

 

카카오 모빌리티 데이터랩에서 발표한 슬라이드는 맵 매칭이 어떤 과정을 거치는지 개략적으로 잘 설명하고 있다.

 

맵매칭 (부정확한 GPS포인트들로부터 경로 추정하기)

 

 

비터비 알고리즘(Viterbi Algorithm)

 

맵 매칭에 실제로 사용되는 핵심 알고리즘은 비터비 알고리즘이다. 은닉 마르코프 모델 개념을 바탕으로 풀 수 있는 몇 가지 대표적 유형의 문제 중 한 종류를 풀 때 사용되는 비터비 알고리즘은, 뼈대가 되는 원리 자체는 매우 간결하고 직관적이다. 

아래 글에서 예시를 들어 그 개념을 쉽게 설명하고 있다.

HMM과 비터비 알고리즘(Viterbi Algorithm) | 마케터 루시씨 블로그

 

아래 글은 또 다른 설명인데, 그림 예시가 좋다.

Viterbi Decoding

위 글에 등장하는 GIF가 그 개념을 명료하게 이해시켜준다. 원 출처는  이 곳.

 

위의 그림에는 k-3, k-2, ... k+2 까지 총 6개의 단계가 있다. 맵 매칭이라고 한다면, 총 6개의 GPS 측정값이 있는 경우다. k-3번째 측정값을 매칭시킬 수 있는 도로 링크는 5개, k-2번째 측정값을 매칭시킬 수 있는 도로 링크는 6개, k-1번째 측정값의 경우 5개, k번째의 경우 7개다.

이렇게 연쇄적인 모든 쌍을 계산하려면 경우의 수가 너무 많아진다. 위의 경우에도 5 x 6 x 5 x 7 x 4 x 5 = 21000가지가 되는데, 물론 이 정도는 요새 컴퓨터에서 1초도 안 걸리긴 한다. 그렇지만 측정 점이 20개고, 각 경우에서 24개의 후보링크를 둔다면, 24 ^ 20 = 4,019,988,717,840,603,673,710,821,376 이 되어... 계산 불가능한 양이 되어버린다.

 

비터비 알고리즘은 계산량을 줄여준다. 특정 단계와 그 이후 단계사이의 쌍만 계산하여 최적 후보만을 남기고, 거꾸로 추적해가면서 경로를 취하게 된다. 계산해야 하는 경우의 수는 위의 그림이라면 (5x6) + (6x5) + (5x7) + (7x4) + (4x5) = 143가지뿐이다. 측정 점 20개에서 각각 24개의 후보 링크를 두더라도 (24 x 24) x (20-1) = 10944 가지만 계산하면 된다.

단계가 진행되면서 아예 가능성의 고리가 끊겨버리는 후보들도 있다.

 

 

아래 글은 품사 태깅에 적용한 예시이지만, 역추적(backtracking / backtracing) 과 같은 핵심 개념들을 잘 설명해준다.

Viterbi 알고리즘 (feat. 품사태깅)

 

 

 

 

 

FMM : Fast Map Matching (by  Can Yang)

 

깃헙에서 C++로 구현된 알고리즘을 하나 찾았다. 계속되는 글에서는 이 구현방식을 토대로 설명하려고 한다.

 

GitHub - cyang-kth/fmm: Fast map matching, an open source framework in C++

아파치 2.0 라이센스가 적용된 오픈소스다. 

아래 페이지 중 <PDF Postprint>로 링크된 논문에 전체 작동 원리를 가장 자세히 설명하고 있다. 아래에서는 몇몇 중요한 원리들만 설명할 예정이다.

Reference

 

원래 소스는 GDAL이나 Boost등 덩치가 크면서 연쇄적인 의존성을 가진 라이브러리들을 사용하는 바람에 최초 빌드에 애를 좀 많이 먹었다. 그래서 몇 가지 기능과 무거운 라이브러리들을 덜어내고 header-only 들로 정리해서 아래 링크에 올렸다.

GitHub - vuski/fmm: Fast map matching, an open source framework in C++

 

 

물론 정리하는 과정에서 일부는 입맛대로 변형하고 편의기능들을 많이 삭제했으므로, 원래 소스에서 많이 축약된 버젼이라고 보면 된다. 공유 자체를 목적으로 변형한 것이 아니라, 실제 특정 업무에서 사용하기 위해 변형했기 때문에 EPSG:5179 좌표계와 특정 컬럼 형식의 네트워크에 맞춰져 있기도 하므로 사용에 있어 주의를 기울여야 한다. 원래 소스는 주피터 노트북에서 사용할 수 있는 코드도 있고 리눅스, 윈도우, 맥 모두 사용 가능하며 웹 데모 버젼도 있지만, 변형해서 올린 버젼은 윈도우의 Visual Studio에서만 테스트된 cpp 버젼이다. 리눅스나 맥에서 돌아갈 수 없는 함수도 약간 들어가 있다.

 

 

 

 

 

맵 매칭 함수들 사용하기 : 실행 절차

 

축약해서 올려놓은 깃헙의 코드를 중심으로 맵 매칭 단계를 설명해보겠다. test.cpp 파일이다.

 

 

1. 준비 단계

#include "fmm/fmm_algorithm.hpp"

using namespace FMM;
using std::cout;
using std::endl;

size_t Network::calcCount = 0;
size_t FastMapMatch::ubodtCount = 0;
size_t Network::calcDuration = 0;
size_t FastMapMatch::calcDuration = 0;
size_t FastMapMatch::loopCount = 0; //루프 수
size_t FastMapMatch::updateTGDuration = 0; //루프 수
size_t Network::calcDuration_bg = 0; //루프 수
size_t Network::calcDuration_thst = 0; //루프 수

깃헙에 올려놓은 include 하위 폴더들 밑의 헤더 파일들을, 현재 사용하고 있는 include 에 그대로 복사하고 경로지정만 해주면 된다. 모두 다 헤더 온리 파일들로만 이루어져 있으므로 별도의 lib나 dll 링킹 작업은 필요 없다. 

우선 라이브러리를 불러온다. fmm_algorithm.hpp 하나만 include 하면 된다. cpp 내장 include 대상 라이브러리들이나,필요한 다른 모든 라이브러리들을 fmm_algorithm.hpp 하위에 연쇄적으로 물리도록 했다.

 

이어지는 일련의 변수들은 세부 항목들의 소요시간 및 계산시간 측정에 사용된다. 꼭 필요한건 아닌데 비활성화 시키는 변수를 넣어놓지는 않았다.

 

 

 

 

2. 네트워트 읽고 UBODT 구축

 

bool timeCalc = true;
int srid = 5179;
Network network("..\\testData\\2019_network.geojson",
    "id", "source", "target",
    (timeCalc ? "timeFT" : ""),
    srid);

//네트워크 계산을 위한 부스트 그래프 형식
network.initNetworkGraph(); //특별한 것은 없고, 앞에서 설정한 거리가 그대로 들어간다.

//ubodt 파일을 만든다. 저장하고 끝난다.

int threads = 30;

std::string status = UBODT::generate_ubodt_new(
    (timeCalc ? "..\\testData\\ubodt1_time" :
        "..\\testData\\ubodt1_dist"),
    (timeCalc ? 5.0 : 1000.0),// <-- 각각의 점에서 어느 반경까지 ubodt를 저장할 것인가. 시간이 될 수도 있음
    network,
    threads);

이제 네트워크를 입력하고 UBODT를 만든다. 

원본 라이브러리는 특정 좌표계에 구애받지 않는데, vuski 계정에 올린 라이브러리는 EPSG:5179 좌표계 기준으로 맞춰져 있다. srid에 다른 숫자를 넣어도 동작하지 않는다.(매개변수 자리는 만들어 놓았는데 함수 안에서는 쓰이지 않는다. )

timeCalc 를 true로 설정하면 네트워크에 입력된 timeFT 속성에서 링크의 소요시간(min)을 읽은 후 시간 기반으로 맵 매칭을 시도한다. false로 설정하면 시간속성은 무시하고 거리 기준으로 맵 매칭 작업을 수행하게 된다.

 

샘플로, 한국교통연구원의 도로망과 철도망을 결합시킨 후 서울 주변 지역을 testData 폴더에 넣어놓았다. 

 

 

 

원본 라이브러리는 네트워크 파일을 두 가지 용도로 사용한다. 첫 번째 용도는 공간좌표를 지닌 물리적인 도로망으로 이용한다. R-tree에 넣어놓은 후 GPS궤적 각각의 점에서 매칭 가능한 후보군을 선별하는 용도로 사용되는 등 공간 연산 작업에 쓰인다.

다른 용도는 길찾기 용이다. 노드와 링크라는 추상적 그래프 구조로 변환하여 다익스트라 알고리즘 등 길찾기에 활용한다. 원본 라이브러리의 그래프 형식 대신 vuski 계정에서는 CSR 형식으로 변환시킨다. 입력된 네트워크를 그래프 형식으로 변환하는 함수가 바로 network.initNetworkGraph( ) 부분이다.

 

이제 변환된 그래프 형식을 기반으로 precomputation을 한다. 계산 값을 시간으로 설정할 경우 각각의 노드에서 5.0분 이하에 도달하는 노드들에 대해 미리 길찾기 작업을 해서 저장해놓는다. 거리로 설정할 경우 각각의 노드에서 길 따라 1000m 안쪽에 있는 노드들까지 미리 길찾기 작업을 해서 저장해놓는다. dat 확장자의 바이너리 파일로, 위에 설정한 경로와 파일이름으로 저장된다.

한계 시간/거리 값들은 당연히 바꿀 수 있는데, 5분을 10분, 15분, 20분으로 차차 늘여가다보면 전체 UBODT 크기가 꽤 많이 늘어나므로 자신의 컴퓨터 사양을 고려해서 잡아야 한다.

원본 라이브러리는 UBODT에서 설정한 거리 이상은 탐색이 안되도록 해 놓았고, vuski 계정에 올린 라이브러리에서는 새로 길찾기를 해서 찾아갈 수 있도록 했다. 새로 길찾기를 하는 순간 작업 수행 시간이 대략 10000배 이상 증가하게 된다. 자세한 내용은 뒤에 UBODT 항목에서 다시 설명하기로 한다.

 

 

3. UBODT를 다시 읽고 맵 매칭 작업 본격 준비

//다시 저장된 ubodt읽는다.   
clock_t timeT = clock();
std::shared_ptr<UBODT> ubodt = UBODT::read_ubodt_binary_new(
    (timeCalc ? "..\\testData\\ubodt1_time.dat" :
        "..\\testData\\ubodt1_dist.dat"),
    network);

SPDLOG_INFO("time : {}ms", clock() - timeT);

//모델 구성
timeT = clock();
//앞에서 읽은 세 형식을 저장한다. 그대로 옮기기만 함
FastMapMatch model;
model.init(network, ubodt);


//
FastMapMatchConfig config{
    48,      // 후보군 수, 궤적에 근접한 네트워크 선분들 <-- 이게 모자라면 복잡하게 꼬일 수 있다.
    1000,    // search Radius --> cost가 무엇이든, 실제 거리로 찾는다.
    2000,     //gps_error -> gps error --> emission 확률을 계산하는데 쓰이며, gps 점과 네트워크의 실제 거리로 비교하는게 맞다.
    0.0 //reverse tolerance는 0~1사이가 되어야 함. fmm_algorithm 의 validate 함수에 0~1 사이임을 체크하고 있음
}; 
SPDLOG_INFO("model loaded : {}ms", clock() - timeT);

네트워크가 동일하다면 UBODT는 한 번만 만들어서 저장해두면 된다. 여기서는 저장해 둔 UBODT를 읽고, FastMapMatch  클래스의 model 인스턴스에 네트워크(그래프 포함)와 UBODT를 준비해둔다.

 

config 변수에는 중요한 설정값들을 넣는다.

두 번째 변수는 각각의 GPS 측정값에 대한 매칭 후보군들을 주변의 네트워크에서 찾을 때 몇 m 반경까지 찾을 것인지에 대한 변수다. 여기서는 1000m 까지 찾도록 했다. 시간 기반이든, 거리 기반이든 여기서는 무조건 거리 기준으로 검색한다. 

첫 번째 변수는 이 때, 몇 개의 링크들을 후보군으로 둘 것인지에 대한 내용이다. 1000m 반경에서 60개를 찾았다면, 가까운 순으로 48개만 취한다. 비터비 알고리즘의 시간 복잡도는 M x M x N 이라고 할 수 있는데, 여기서 M이 바로 이 후보군 숫자가 되고, N은 GPS의 궤적 점의 수가 된다. 하나를 증가시켜도 제곱으로 늘어나므로 신중하게 결정해야 한다. 적게 넣어서 실제 매칭시켰어야 할 링크가 후보군에 아예 안들어오게 되면 제대로 길 찾기를 해 줄 수가 없다. gps가 멀리 튀지 않았다면 약간 적게 넣어주는게 좋다. 무한정 많이 넣을 수는 없으므로 반복적으로 결과를 보면서 최적 값을 조정해봐야 한다.

세 번째 변수는 gps 에러의 허용치를 설정한다. 이 허용치는 비터비 알고리즘에서 방사 확률(Emission Prob.)에 사용된다. 설정한 거리가 크면 약간 튄 값도 관대하게 받아주고, 거리를 300m 로 설정했는데, 두 배(600m) 튄 값이 나오면 emission prob.이 0.13정도로 낮게 되어 비터비 알고리즘에서 채택될 확률이 낮아진다. 사실 gps의 경우 300m 오차는 거의 없다. 그렇지만 기지국 기반의 휴대폰 신호의 경우에는 300m 정도는 쉽게 튀기 때문에 관측값으로부터 500m 떨어진 링크가 채택될 경우도 염두에 두려면 1000m 이상으로 관대하게 잡아주는 것이 좋다.

네 번째 변수는 역방향 진행의 허용치인데, 0~1의 값을 지닐 수 있다. 점 A, B, C가 시간 순서대로 있을 때, 거리상으로 A~B 사이의 거리보다 A~C 사이의 거리가 더 짧을 때, 즉 B와 C의 공간적 순서가 뒤바뀐 경우로서 역주행(U턴 등) 했을 경우와 관련된다.  0으로 두면 이런 역주행을 곧이 곧대로 역주행이라고 해석한다. 1로 두면, B와 C가 한 선분에 연결되었을 경우 B와 C의 거리가 완전히 끝과 끝으로 뒤바뀌더라도 역주행으로 해석하지 않고 순방향 진행이라고 해석하게 된다. 

 

 

 

4. 사용자 로그 읽기

//사용자 로그 읽기
std::vector<Trajectory> trajectories;

SignalReader::convertAndreadData("..\\testData\\testdata.geojson",
    trajectories, SignalReader::GEOJSON, SignalReader::YMDHMS);
		

clock_t startT = clock();
//결과 쓰기 준비
size_t calcCnt = 0;
size_t calcDur = 0;
ResultConfig result_config;
result_config.output_config.write_cpath = true;
CSVMatchResultWriter writer("..\\testData\\result.tsv",	result_config.output_config);

이제 GPS 궤적을 읽는다. 여기서는 손으로 대강 찍은 geojson 경로를 읽어들인다.

 

 

준비한 파일에는 시간 속성은 없는데, 위처럼 geojson을 읽을 경우에는 어차피 시간 변수를 읽지 않으므로 큰 상관이 없다. convertAndreadData 함수 구현을 살펴보면 그리 어렵지 않게 해석하거나 변형할 수 있을 것 같다.

 

그리고, 맵 매칭 결과를 저장할 파일을 준비한다. result.tsv 파일로 저장될 예정이다.

 

 

5. 본격 맵 매칭

int numThreads = 30;

int cnt = 0;
omp_set_num_threads(numThreads);
#pragma omp parallel
{
    int threadNum = omp_get_thread_num();

#pragma omp for schedule(dynamic, 1) nowait
    for (int i = 0; i < trajectories.size(); i++)
    {
        Trajectory& trajectory = trajectories[i];
        Network::calcCount = 0;
        FastMapMatch::ubodtCount = 0;
        Network::calcDuration = 0;
        FastMapMatch::calcDuration = 0;
        FastMapMatch::loopCount = 0;
        FastMapMatch::updateTGDuration = 0;

        ////맵 매칭 계산
        auto startTime = std::chrono::high_resolution_clock::now();
        MatchResult result = model.match_traj(trajectory, config);  // <-------- 맵 매칭 계산
        auto endTime = std::chrono::high_resolution_clock::now();


        double durTotal = std::chrono::duration_cast<std::chrono::microseconds>(endTime - startTime).count() / 1000.0;
        double countSP = Network::calcCount;
        double countUbodt = FastMapMatch::ubodtCount;
        double durSP = (double)Network::calcDuration / 1000.0;
        double durSearchCddt = FastMapMatch::calcDuration / 1000.0;
        double durUpdateTg = FastMapMatch::updateTGDuration / 1000.0;

#pragma omp critical
        writer.write_result(trajectory, result);
#pragma omp critical
        cnt++;				
#pragma omp critical
        SPDLOG_INFO("no: {} fmm done: {}ms   {}번째 / {}s / {}%  ubodt사용 : {}회  길찾기 : {}회  길찾기 시간 : {}ms   후보찾기 : {}ms  비터비 루프 : {}회   updateTg : {}ms  나머지 시간 {}ms",
            i,
            durTotal,
            cnt,
            (int)((clock() - startT) / 1000),
            (int)((double)i / trajectories.size() * 100000) / 1000.0,
            countUbodt,
            countSP,
            durSP,
            durSearchCddt,
            FastMapMatch::loopCount,
            durUpdateTg,
            durTotal - durSearchCddt - durUpdateTg);

    }
} //#pragma omp parallel

 

코드는 길지만 대부분 시간/횟수 재는 변수들에 대한 내용이고, 핵심 내용은 아래와 같다.

 

for (int i = 0; i < trajectories.size(); i++)
{
    Trajectory& trajectory = trajectories[i];      
    MatchResult result = model.match_traj(trajectory, config);  // <-------- 맵 매칭
    writer.write_result(trajectory, result);
} //#pragma omp parallel

 

여기서는 준비한 궤적들이 6세트 있다. 

궤적 하나씩 돌면서 model.match_traj( ) 함수로 맵 매칭 작업을 한 뒤 결과를 writer.write_result( ) 로 저장한다.

각각의 궤적들은 서로 독립적이고, 내부 함수들도 병렬 처리가 가능하도록 구현되어 있으므로 openMP 방식을 사용하여 다수의 cpu 자원을 이용할 수 있도록 했다.

 

결과 파일은 다음과 같은 형식이다. 

쎄미콜론이 구분자로 된 파일인데, QGIS 에서 wkt 형식으로 읽어들일 수 있다.

 

QGIS의 레이어 -> 레이어 추가 메뉴 중 '구분자로 분리된 텍스트 레이어 추가'를 선택한 후, 다음과 같이 WKT 형식을 선택해서 불러들일 수 있다.

 

아래와 같은 맵 매칭 결과를 보여준다. 주황색이 찍어서 입력한 궤적, 빨간색이 매칭된 결과값이다.

 

 

 

 

맵 매칭 구현 프로그램을 사용하기 전에 

 

실제 데이터를 '제대로' 사용하려면 최소한 원 저작자인 Can Yang의 논문을 한번은 찬찬히 읽어봐야 한다. 

https://people.kth.se/~cyang/bib/fmm.pdf

 

이 논문에서 강조하는 점은 퍼포먼스다. 위의 저자 이전에도 비터비 알고리즘을 사용해서 맵 매칭을 구현한 사례들이 많이 있는데, Can Yang 의 경우 미리 계산된 UBODT 를 도입해서 실행 속도를 획기적으로 개선했다. 

 

 

아래처럼 순서도로 전체 과정을 잘 설명하고 있다.

 

 

https://people.kth.se/~cyang/bib/fmm.pdf

 

여러가지 삽도를 통해 중요한 부분들을 상세히 설명하고 있다. 

 

https://people.kth.se/~cyang/bib/fmm.pdf

 

 

 

 

 

알고 있어야 할 기본 알고리즘

 

여기부터는 위의 논문을 읽고 전체적인 흐름을 이해했다는 가정 하에, 부분적으로 중요한 내용들만 설명해보겠다.

우선 알고리즘.

FMM에 사용된 알고리즘은 여러개가 있다.

 

1. 비터비 알고리즘(Viterbi algorithm)

 

경로 추정에 핵심이 되는 알고리즘이다. 앞서 간단히 설명했다.

 

 

 

2. 길찾기 알고리즘

 

다익스트라 알고리즘이나 A* (A star) 알고리즘을 이용한 최단 경로 찾기를 알고 있어야 한다. 비터비 알고리즘 각 단계에서 아주 빈번하게 사용되는 알고리즘이다. 

 

 

3. UBODT (Upper-Bounded Origin-Destination Table)

 

이 알고리즘은 그냥 Map Matching이 아니라 'Fast' Map Matching 인 이유의 근간이 된다. 네트워크에 존재하는 길찾기 경로 쌍 일부를 미리 계산해 둠으로써(precomputation) 비터비 알고리즘의 수행시간을 획기적으로 단축시키고 있다.

 

 

4. R-tree

 

측정된 궤적 점들을 토대로, 네트워크 중 매칭 대상이 될 수 있는 링크 후보군을 찾을 때 사용된다. 한 점으로부터 가장 가까운 선분들을 찾아내는데 쓰인다.

 

 

5. Hash Map 알고리즘

 

UBODT에서 경로 쌍들을 찾아나가는데 사용된다. 최적화된 성능을 위해 원 저작자가 직접 구현했다. 일반적인 경우 굳이 몰라도 되는데, 네트워크가 커지면 버킷 수 설정하는 부분에 한해 원본에서 약간 수정해야 한다.

 

 

 

 

사실, 라이브러리를 만들고 실행할 수 있는 함수를 만드는 이유는, 굳이 내부 작동원리를 몰라도 매개변수만 넣으면 결과값을 받을 수 있도록 하기 위함이다. 그렇지만 맵 매칭 자체가 워낙 데이터 특성을 타는 작업이라 세세한 부분들을 조금씩 수정해주지 않으면 종종 엉뚱한 결과를 받게 된다. 하고 있는 일에서 한 번은 넘어가야 하는 고개였던 탓에 시간을 들여 구현 코드들을 하나씩 따라가 봤다.

 

이제 전체 프로세스에서 중요한 부분들 위주로 설명해보겠다.

 

 

UBODT : Upper Bounded Origin Destination Table

 

네트워크를 읽어들인 후 가장 처음 하는 작업 중 하나는 미리 계산된 길찾기 테이블을 만드는 일이다. 

여기서는 UBODT (Upper Bounded Origin Destination Table) 라고 이름붙인 방식으로 길찾기 테이블을 만들어둔다. 최단경로 찾기와 해시맵 알고리즘을 알고 있어야 세부적인 코드 진행을 따라갈 수 있다.

 

UBODT 계산 결과는 아래와 같은 구조체에 저장된다. 맨 아래의 Record* next 변수는 하나의 버킷에 중복값이 발생했을 때 리스트 방식으로 적재해주기 위한 포인터 변수다.

ubodt.hpp

 

만들어진 UBODT를 텍스트 형식으로 바꿔보면 다음과 같다.

예를 들어 16번 노드에서 34번 노드까지 가는 길은, 우선 (16,34)를 인풋으로 넣어 해시테이블을 통해 (위 그림에서) 4번 행을 찾아낸다. edge인 5672번 링크와 그 링크의 시간거리인 2.20581분은 진행 첫 링크에 대한 값이다. source인 16과 바로 이어진 링크에 해당한다. 

최단경로상의 그 다음 순번은 next_n으로 표시된 14번이다. 그러므로 이번에는 (14,34)를 인풋으로 넣어 해시값을 얻은 후 위치를 찾아 값을 읽는다.

아래처럼 14번 노드에서 34번 노드까지의 최단 경로 중 진행 첫 링크는 543번이고 소요시간은 1.12346분이다. 이 값을 취하고 경로의 다음 순번으로 진행한다. next_e 값인 34를 보니 최종 목적지 노드와 같다. 그러므로 여기에서 종료한다. 여기서 든 예는 링크 두개로 이루어진 최단경로에 해당한다.

 

이 테이블은 1-3-7-2-5-9 번 노드들로 이루어진, 1번에서 9번 노드로 가는 어떤 최단 경로가 있다고 할 때, 그 경로상에서 취한 임의의 노드 2개 역시 최단경로가 된다는 논리를 바탕으로 만들어졌다. 따라서 (1,9)의 해시테이블을 찾고, 그 다음에는 next_n으로 표시되어 있는 3번을 취한 후, (3,9)의 해시테이블을 찾고... 다시 (5,9)의 해시테이블까지 찾으면 최단경로상의 모든 점들을 순서대로 짚어온 셈이 된다. 

 

다익스트라 혹은 A star 알고리즘을 이용해서 매번 길찾기를 하게 되면 많은 링크들을 순회하면서 비교해나가야 한다. 경우의 수가 매우 많아서 시간도 오래 걸리는데, UBODT의 경우 그런 작업을 한번만 해 두면, 그 다음에는 여기서 직접 구현된 해싱 함수를 재귀적으로 따라가면서 헤매지 않고 원하는 값과 경로들을 찾을 수 있다.

 

그리고, 모든 경우의 수 마다 모든 경로를 일일이 저장하지 않고 두 쌍만 저장함으로써, 메모리도 비교적 효율적으로 사용한다. 바로 앞에서 든 예시인 1번 에서 9번으로 가는 최단 경로인 1-3-7-2-5-9를 저장하는 과정에서 사용된 값들은, 3번에서 9번으로 가는 최단경로를 찾는데도 그대로 이용할 수 있다. 혹은 4번 노드에서 9번 노드로 가는 최단 경로가 4-6-7-2-5-9라고 할 때, 7-2-5-9 부분은 중복 기록으로 메모리를 낭비하지 않고 한 번만 기록함으로써 여러 경로에서 그대로 재활용할 수 있다. 

 

이렇게 경로들을 재활용할 수 있다는 특징에도 불구하고, 노드가 40만개가 넘는 전국 네트워크를 넣고 모든 네트워크에서 2000m 반경 혹은 10분 반경으로 UBODT를 만들게 되면, 저장되는 바이너리 용량이 10기가 이상으로 넘어가게 된다. 따라서 무한정 값을 키울 수는 없다. 만약 맵 매칭 시킬 GPS값들 사이의 간격이 모두 시간거리 5분 이상을 넘지 않는다는 확신이 있으면(혹은 그렇게 전처리 했으면) UBODT의 생성값은 모든 점으로부터 '5분 거리'로 해도 충분하다. 

 

 

이제 UBODT가 구축되었다고 할 때, 최단경로를 찾아가는 과정을 잠시 살펴보자.

ubodt.hpp

다른 함수에서 look_sp_path를 호출하게 되면 이 함수는 while 구문을 돌면서 next_n == target이 될 때 까지 look_up 함수를 반복하면서 값들을 읽어내려간다. loop_up 함수는 미리 구현된 해시함수를 이용하여 source-target의 key로 하는 데이터가 위치하는 곳을 찾아낸다. 만약 해시 값이 중복될 경우, Record 구조체의 next 변수를 이용해서 미리 연결된 병렬 저장 공간을 검토하게 된다. 

저장될 방들을 충분히 마련하고 해싱 값이 겹치면 순차적으로 포인터를 따라가면서 원하는 값을 찾아내는, 일반적인 해싱 함수의 방법론 중 하나를 직접 구현해서 사용하고 있다. 원 저작자는 이렇게 직접 구현하는 방식이 매우 빠르다고 주장하는데, unordered_map이나 hopscotch map 등, 다른 해시맵 구현방식과 비교해보지는 못했다.

 

1차 해싱의 결과로 값이 중복일 경우 2차적으로 같은 해시 값 아래에 적재된 리스트들을 훑어가는 방식이 일반적인 해시맵의 방식인데 여기서도 이 방식을 적용하고 있다. 그런데 1차 해싱 과정에서 중복된 값이 많아지면 리스트를 순차적으로 훑는 작업을 많이 하기 때문에 아무래도 검색 성능이 떨어질 수 밖에 없다. 따라서, 메모리만 허용한다면 LOAD_FACTOR를 1로 두어 1차적 버킷 공간을 충분히 마련함으로써, 중복값이 되도록 발생하지 않도록 해 줄 필요가 있다.

ubodt.hpp

 

 

 

최단경로 찾기 (Shortest Path Algorithm)

 

최단경로 찾기 알고리즘은 매우 간단하고 구현도 복잡하지 않다. 3년 전 쯤 관련된 글을 올려둔 적이 있다.

 

실시간 반응형 등시선도(Realtime Interactive Isochrone Map) 그리기

가장 기본이 되는 다익스트라(Dijkstra) 알고리즘은 다음과 같은 과정으로 이루어진다. 일단 물리적 거리 중심으로 써 보자면, 

 

1. 출발점과 1차적으로 연결된 주변의 모든 점들을 탐색한다.

2. 거리가 짧은 순서로 정렬해서 리스트로 늘어놓는다.

3. 다시 그 리스트의 최우선순위 점을 선택한다. 만약 그 최우선순위 점이 도착점이면 종료한다.

4. 도착점이 아니면, 그 점에서 1차적으로 연결된 주변의 모든 점들을 탐색한다. 탐색한 점은 리스트에서 제거한다.

6. 방금 전의 리스트에 넣고, 거리가 가장 짧은 순서로 정렬한다.

7. 다시 3번으로 돌아가서 끝날때까지 계속 반복한다. 

참고로, 리스트에 넣고 정렬하는 과정은 우선순위 큐(priority queue)로 대체할 수 있다.

 

다익스트라 알고리즘은 도착점이 최우선순위로 등장할 때까지 모든 방향으로 점들을 더듬어나가는데, 이러한 방식 때문에 비효율적인 면도 있다. 예를 들어 대전에서 부산 가는 최단경로를 찾는다면, 어떤 탐색루트는 부산 방향으로 한걸음씩 다가가는데 반해 또 다른 탐색루트는 거의 반대 방향인 서울 방향으로도 계속 탐색 범위를 넓혀가게 되기 때문이다. 

 

이런 비효율성을 조금이라도 줄여보고자 등장한 것이 A*(A star) 알고리즘이다. 

기본적인 순서는 위의 일곱 단계와 똑같은데, 거리를 저장할 때 거리에 h, 즉 휴리스틱(heuristic) 거리를 더해서 저장하게 된다.

물리적 거리 기준의 최단경로일 경우 휴리스틱 거리는 해당 노드와 최종 목적지 간의 직선 거리를 설정하면 된다. 예를 들어 현재 탐색 출발점이 A이고, 목적지가 Z라고 할 때, A와 인접한 점들 B, C, D 를 탐색할 때, A~B의 경로 거리, A~C의 경로 거리, A~D의 경로 거리만 더해서 우선순위 큐에 넣어놓는게 아니라 A~B의 경로 거리를 더할 때 B~Z의 직선 거리도 함께 더해서 저장하는 방식이다. 공간상의 두 점에서 직선거리보다 가까운 거리는 없다. 따라서 이렇게 휴리스틱 거리를 더해서 계산하면, A에서 Z로 탐색을 해 나갈 때 A와 Z를 직선으로 이은 방향의 탐색에 가중치를 부여하게 된다. 즉, 대전에서 부산 가는 길을 탐색할 때 서울 방향으로 탐색하는 길들은 우선순위 큐에서 계속 뒤로 밀리게 된다.

 

위의 그림처럼 다익스트라 알고리즘으로 계산할 때, B와 C는 O로부터 동일한 거리 100 만큼 떨어져 있지만, A star 알고리즘으로 계산하면 휴리스틱 거리가 덧붙게 되어 500과 300으로 차이가 나게 된다. 이러한 차이는 우선순위 큐에서 목적지와 반대로 진행하는 방향의 탐색에 대해 패널티를 주게 된다. 

 

다익스트라 알고리즘을 약간 수정해서 구현한 A stat 알고리즘은 다음과 같다.

network.hpp

원 저작자의 코드에서 Boost 라이브러리를 떼어내고 fiboheap 대신 std::priority queue를 사용해서 약간의 차이가 있다. 좀 느리더라도 외부 라이브러리를 떼어낼 목적으로 fiboheap 대신 std::priority_queue 로 바꿔봤는데 의외로 좀 더 빨라서 그대로 사용하게 되었다.

 

휴리스틱 거리를 구하는 함수는 아래와 같다.

network.hpp

물리적 거리 기준으로 최단거리를 찾을 때는 앞서 언급한대로 대상 노드와 최종 목적지 간의 직선 거리를 리턴해준다. 그런데 경로의 시간 기준으로 최단거리를 찾을 때는 그대로 두면 안된다. 우선 미터와 분으로 수의 단위 자체가 다르기 때문에 당연히 수정해야 하는데, 어떻게 수정할지 약간 고민을 해야 한다.

 

거리 기준일 때는 직선에 가까운 경로가 당연히 더 빠르지만, 시간 기준일 때는 약간 돌아가더라도 고속도로를 타고 가는게 더 빠를 수 있기 때문이다. 고속도로 진입로가, 패널티를 크게 받는 진행 반대 방향에 위치할 경우 고속도로 진입  노드 자체가 우선순위 큐에서 계속 뒤 순위로 밀려서 탐색 받을 기회 조차 없어질 수도 있기 때문이다. 

 

이 때는 거리 기준일 때 직선거리 즉 어떻게 해도 그보다 더 가까울 수 없는 기준을 찾은 것처럼, 시간 기준일 때는 네트워크에 존재하는 가장 빠른 속력을 찾아 적용시키면 되는 것 같다. 지금의 예시에서는 KTX와 도로망이 결합되어 있기 때문에 300km/h 로 두어 분속으로 변환해서 적용해 두었다. 만약 항공경로까지 결합된 multi modal 네트워크라면 국내 항공노선의 속도를 찾아서 적용시켜야 할 것 같다. 물론 휴리스틱 함수 값이 전체적으로 작아져서 A star 알고리즘의 효율은 좀 떨어지겠지만, 엉뚱한 경로를 찾지 않도록 하려면 어쩔 수 없다.

 

 

네트워크의 준비

 

네트워크를 읽어들이고 UBODT까지 준비되었다면, 이제 사용자가 측정한 GPS 경로를 입력할 차례다. GPS 혹은 다른 측정기기로 측정된 경로들은 분당 미터 속도(m/min)로 변환시켜 준비해야 한다. 그리고 여기서는 단방향 네트워크로 한정되어 있으므로, 양방향 통행과 단방향 통행이 섞여 있을 경우 링크를 두 번 넣되, 진행 방향을 바꿔서 만들어줘야 한다. 

 

 

여기서 준비한 2019_network.geojson의 경우 위처럼 반대 방향의 진행을 겹쳐서 넣어주되, id에 1,000,000,000을 더해서 구분할 수 있도록 했다. 물론, 모든 기본 id 중 1,000,000,000이 넘는 것이 없어야 한다.  10억을 더함으로써 32비트 Integer 범위 안에 들어올 수 있도록 했다.

***. network.hpp의 read_geojson_file( ) 함수에서 id에 1,000,000,000 을 더하는 부분은 현재 testData로 올려놓은 2019_network.geojson 파일에만 적용 가능한 방식이다. 다른 네트워크 데이터의 경우에는 해당 부분을 수정해야 한다.

 

 

 

네트워크를 Rtree 구조 안에 인덱싱

 

 

네트워크가 입력되면 FastMapMatch 클래스를 초기화한다.

network.hpp

init 함수 내부를 보면 마지막 단계에 build_rtree_index( ) 를 호출해서 네트워크 선분들의 검색이 쉽도록 rtree 방식으로 인덱싱하고 있다.

network.hpp

 

원 저작자의 코드에서는 Boost 라이브러리를 사용했고, Boost를 전체적으로 떼어내느라 THST 라이브러리로 대체했다.

 

GitHub - tuxalin/THST: Templated hierarchical spatial trees designed for high-peformance.

 

Rtree는 어떤 점을 입력했을 때 그 점 반경안에 들어오는 폴리곤을 찾는데 유용하다. 점을 찾는 경우에는 quadtree도 좋지만, 선분이나 폴리곤을 넣어놓고 찾을 때는 해당 도형을 둘러싼 Bounding Box를 검색할 수 있는 Rtree가 좀 더 효과적이다. 

위의 코드에서도 Rtree 안에 Bounding Box와 실제 선분을 동시에 넣고 있다.

 

 

본격 맵 매칭 : 개요

 

하나의 궤적을 읽어서 다음의 함수를 호출하게 되면 본격 맵 매칭 작업이 수행된다.

 

test.cpp

config 변수를 통해 중요한 설정값들을 넣어 두어야 한다.

test.cpp

 

match_traj( ) 함수 안에서는 벌어지는 일들은 크게 다음의 항목으로 구분해 볼 수 있다.

 

1. 각각의 관측점마다 주변의 네트워크 링크들을 검색해서 매칭될 후보군에 올려놓는다.

2. 비터비 알고리즘을 이용해서 매칭 점수들을 계산한다.

3. 역추적 방식을 통해 매칭시킬 링크들을 결정한다. (맵 매칭 완료)

4. 매칭된 링크들간의 최단경로를 검색해서 전체 맵 매칭 경로를 완성한다.

 

 

 

본격 맵 매칭 : 매칭될 후보군 찾기

 

맵 매칭의 첫번째 단계는 비터비 알고리즘에 넣을 매칭 후보군들을 찾는 일이다. 

 

아래 그림에서 검은 선들이 입력한 네트워크, 붉은 선이 관찰된 궤적이라고 할 때, 붉은 동그라미 반경 r 안쪽에서 설정된 개수 k 만큼의 링크를 검색해서 후보군으로 올려두게 된다. 

 

r과 k 값은, 앞에서 언급한 config 변수의 두번째, 첫번째 값에서 설정할 수 있다.

 

관측값이 가지고 있는 오차보다 반경 r을 너무 크게 잡으면 불필요하게 많은 연산을 하게 된다. 반대로 관측값이 통상적으로 가지고 있는 오차보다 r을 너무 작게 잡으면 은닉되어 있는 실제 주행 경로는 후보군에 오르지도 못하게 된다. 따라서 이 경우에 (참 값을 알고 있다는 가정 하에) 맵 매칭 결과와 참 값을 비교해보면 당연히 같을 수가 없다. 

 

후보군 수 k 역시 중요하다. 반경을 아무리 크게 잡더라도 후보군의 수가 적어서 참 값에 해당하는 경로가 우선순위에서 밀림으로써 후보군에 오르지 못하면, 결국 반경을 작게 잡은 것과 같은 결과를 가져온다.

 

일반적인 GPS처럼 오차가 크지 않으면, 반경을 몇백m 안쪽으로 잡고, 후보군 수도 10개 내외로 잡아도 된다. 그렇지만 휴대폰 기지국 데이터처럼 오차가 클 경우에는 반경과 후보군 수도 크게 잡아줘야 한다. 이 경우에는 네트워크가 아주 상세해도 오히려 방해가 되는데, 반경을 넓혀도 근처의 상세 경로들이 후보군에 우선 순위로 올라가기 때문이다. 먼 거리에 있는 (아직은 모르는) 참값은 우선순위에서 밀려나서 후보군에 오를 기회를 가지지 못하게 된다.

 

 

여기서 사용하는 맵 매칭 알고리즘은 약간 튄 값의 경우 반경 안에 들어온 참 값을 찾아주는 능력을 가지고 있지만, 아예 멀리 튄 값은 정제해주지 못한다. 

위의 그림은 눈으로 보면 확실하게 값이 튀었다는 것을 알 수 있지만, 맵 매칭 알고리즘에서는 정상적인 점으로 간주해서 빙 돌아가는 결과값을 받게 된다. 따라서 설정한 r 값보다 더 참값에서 벗어나는 관측값들이 존재한다고 판단될 경우 전처리를 통해 걸러내야 한다.

 

 

 

비터비 알고리즘을 이용해서 선행 후행 노드간의 최우선 값 찾기

 

 

비터비 알고리즘은 글의 전반부에서 설명했다. 다시 보면 다음과 같다.

https://www.researchgate.net/publication/273123953_Animation_of_the_Viterbi_algorithm_on_a_trellis_illustrating_the_data_association_process

 

 

맵 매칭 과정의 예시를 통해 보면, 아래와 같다.

파란 선들이 한 관측점과 그 다음 관측점 사이에 선정된 후보군 간에 가능한 계산 조합들의 일부다. 이렇게 시도한 후, 하나의 후행 링크 기준으로 선행 링크들 중 하나를 선택해서 결정하게 된다.

 

비터비 알고리즘에서 각각의 확률은 선행노드가 가지고 있는 이제까지의 누적 확률에, 선행 노드와 후행노드의 전이 확률(transition probability), 그리고 후행 노드의 방사 확률(emission probability)을 곱해서 결정된다.  여기서는 로그 값을 씌워서 곱셉을 덧셈으로 만들었다. 너무 작은 수가 되어버리는 것을 방지하는 장치인듯 하다.

fmm_algorithm.hpp

그렇다면 중요한 것은 transition probability(이하 tp) 와 emission probability(이하 ep)다. 

 

tp는 선택한 두 링크가 경로상으로 연결되어 있을 확률, 그래서 자연스럽게 전이가 일어날 확률이라고 생각하면 된다. 아래의 함수에서 결정된다.

transition_graph.hpp

eu_dist(euclidean 거리) 즉 두 관측점 사이의 직선 거리를, sp_dist(shortest path) 임시 연결된 두 링크 사이의 최단거리로 나누어주면 tp가 된다. 1.0을 넘지 않도록 했다.

 

소요시간 값으로 맵 매칭을 할 때 sp_dist는 실제 거리로 계산하면 명확하지만, eu_dist 는 조금 고민을 해봐야 한다.

 

geom_algorithm.hpp

 

여기서는 우선 거리를 구한 후, 모두 시속 100km, 즉 동일한 속도를 적용해서 계산했다. 실제 관측된 시간을 토대로 시도해보았는데, 길이 막히는 등 지속적으로 주행하지 않았을 경우 엉뚱한 경로를 선택하는 결과를 가져왔다. 길이 막혀서 평소보다 5배 많이 걸렸을 경우, 그 정도 시간에 상응하는 거리만큼 돌아가는 경로와 매칭되곤 했다.

eu_dist 를 계산함에 있어 동일한 속도를 적용시켜 주었을 경우 좋은 결과값을 받을 수 있었다. 관측된 시간값을 라이브러리에 녹여내는건 쉽지 않은 일 같다.

 

sp_dist를 구하는 부분은 생각보다 조금 더 정교하게 구한다. 원 저작자의 논문에서도 이 부분을 상세히 설명하고 있다. 관측값 중 선행 노드와 후행 노드가 같은 링크에 매칭되었을 경우, 역방향 진행으로 생각될 경우 등 세분화시켜 판단하고 있다.

fmm_algorithm.hpp

원 저작자의 코드에는 UBODT에 없을 때 항상 무한대값을 반환하도록 하고 있다. UBODT에 없을 때는 원래 두 점이 네트워크 상에서 연결되어 있지 않거나, 초기에 설정한 UBODT 탐색 값을 벗어나는 위치에 있을 경우다. 수정된 코드에는 UBODT 탐색 범위를 벗어나는 경우를 고려하도록 했다. 즉, UBODT에 없더라도 다시 최단경로 거리를 찾을 수 있도록 했다.

 

 

 

 

 

ep는 아래와 같이 구한다. 

transition_graph.hpp

여기서 dist는 관측점과 해당 링크까지의 거리에 해당하고, error는 config에서 직접 입력한 값이다. 시간거리로 계산하든 물리적 거리로 계산하든 ep는 항상 물리적 거리 기준으로 계산해야 한다.

 

관측점과 링크 사이의 거리가 가까울수록 높은 점수를 주고, 멀 수록 낮은 점수를 준다.  dist/error 비에 따른 ep는 다음과 같다.

설정한 error 한계 만큼 떨어질때 ep는 0.60 정도의 값을 가진다. error보다 두 배 만큼 떨어지면 0.13 의 확률을 가진다. 채택될 확률이 매우 낮아지게 된다. 만약 관측값 자체가 원래 오차가 크다고 판단될 경우 두 가지 정도의 조치를 쉽게 할 수 있다. 

우선 config 값에서 gps_error 값을 크게 입력해볼 수 있다.

혹은 아래처럼 일정부분 오차까지는 무시하고 진행하는 방법이 있다.

 

다시 종합 확률로 돌아가보면,확률은 tp와 ep를 곱해서 결정된다. 그런데, ep의 경우 사용자의 입력값에 의해 크게 변화할 수 있으므로 자칫 너무 작은 값을 입력하면 전체 확률에서 영향을 끼치는 정도가 매우 커지게 된다. 이렇게 되면 tp가 어떻게 나오든 ep값의 지배적인 영향하에 놓인다. 즉 연결 관계보다는 관측점과 가까운 링크를 우선적으로 선택하게 되는 결과를 가져온다. 다양한 값을 설정해서 실험해보고 신중하게 gps_error 값을 결정해야 한다.

 

 

마지막으로, 전체 경로 구하기

 

맵 매칭의 결과는 아래 그림과 같다. 매칭된 링크, 즉 보라색 선들을 찾아내는게 바로 맵 매칭이다.

 

관측값들이 촘촘할 경우에는 그 선들만 이어도 전체 경로들이 완성되겠지만, 관측값들이 듬성듬성 있을 경우 그 사이사이를 이어주어야 한다.

 

model.match_traj( ) 함수의 마지막 부분이 바로 이 작업을 해주는 부분이다. 새로운 알고리즘이 쓰이는건 아니고, 다시 최단경로 혹은 UBODT 테이블을 사용해서 최단거리로 각 링크들을 이어주게 된다.

 

그렇게 해서 위 그림처럼 전체 경로가 완성된다. 맵 매칭 과정은 이렇게 모두 끝났다.

그런데 사실, 맵 매칭은 이제부터다. 실전 적용을 위해 실제 데이터를 돌려보면 부족한 점들이 많이 보일 것 같다. 알고리즘은 항상 명쾌하지만 실제 데이터는 예상을 뛰어넘는 노이즈가 많이 포함되어 있기 때문이다. 

 

 

주의할 부분 + 더 생각해 볼 부분

 

 

*.

퍼포먼스를 위해서는 관측값들의 간격이 모두 UBODT안에 포함되도록 셋팅해줘야 한다. 알고리즘 수행 중에 최단경로를 찾게 되면서부터 퍼포먼스가 눈에 띄게 저하된다. 모두 UBODT로만 계산하면 1초에 몇 만건의 경로를 맵 매칭 시키지만, 최단경로 검색이 들어가기 시작하면 한 건 매칭시키는데 몇 십초 걸리는 경우도 있다. 작업 소요 시간을 상세하게 살펴보면 전체 수행시간의 99% 이상이 최단경로 검색이 되는 경우도 있기 때문이다.

 

*. 

전처리 중 가장 중요한 부분은 이상치의 제거다. 즉 GPS가 멀리 튀었다 오는 부분을 제거해주는 작업을 해야 한다. 여러가지 방법으로 시도해볼 수 있는데, 이 글에서는 생략한다. 글의 맨 앞에 링크된 카카오 모빌리티 문서의 65페이지 부근에 한 가지 방법이 간단히 소개되어 있다.

 

*. 

촘촘한 GPS 경로라고 하더라도 지하철이나 지하도처럼 지하로 들어갈 경우 기록되지 않는다. 이 경우가 많이 까다로운데, 일단 궤적의 간격이 벌어지기 때문이다. 여러가지 다른 종류의 교통수단이 결합된 multi-modal 네트워크 맵 매칭의 경우 상황은 더 복잡해진다. 전처리로 해결하기 힘들고, 위의 알고리즘 속에서 하나씩 판단하면서 구분해야할 일이 생긴다.

 

*.

좋은 맵 매칭 알고리즘만큼 중요한 것은 좋은 네트워크다. 노드에서의 회전 정보도 정확히 들어가 있어야 한다. 지하철의 경우 역간 환승이나 도로~철도 간의 전이 링크 등 시간 값이 잘 들어가 있어야 맵 매칭도 잘 된다. multi-modal 맵 매칭이나 고속도로와 일반도로 등 속도가 크게 차이나는 링크들이 섞여 있을 경우 물리적 거리보다는 시간으로 계산해야 매칭이 잘 되는 것 같다. 이 때, 앞에서 sp_dist를 구할 때 일괄적으로 100km/h를 적용시킨 부분을 좀 더 고도화해볼 수 있다. 단, 도로의 정체 등 똑같은 구간을 가더라도 소요시간이 달라지는 경우가 있으므로 쉽지는 않을 것 같다.