Distance Matrix란? 이동 시간, API, 라우팅 완벽 가이드

Distance matrix는 다수의 출발지와 다수의 목적지 사이의 이동 시간과 거리를 담은 격자입니다. 모든 "가장 가까운 매장" 랭킹, 모든 배달 디스패치 결정, 모든 경로 최적화 솔버 뒤에 있는 데이터 구조죠. 애플리케이션이 운전 시간으로 다수 후보 중 최선을 골라야 할 때마다 distance matrix가 그 일을 하고 있습니다.

이 가이드는 distance matrix가 실제로 무엇인지, 이동 시간이 직선 거리와 어떻게 다른지, 프로덕션 시스템 어디에 등장하는지, 그리고 입력 집합이 몇 개를 넘어서면 팀을 괴롭히는 함정이 무엇인지 설명합니다.

Distance Matrix의 본질

가장 단순한 형태로 distance matrix는 2차원 표입니다. 행은 출발지, 열은 목적지이며, 각 셀은 거리와 소요 시간 두 숫자를 담습니다. 출발지 N개와 목적지 M개일 때 matrix는 N x M개의 셀을 가집니다. 기사 25명과 작업 25개가 있는 요청은 한 번의 호출로 625개 셀을 만들어냅니다.

그 셀의 값은 실제 도로 네트워크 그래프를 탐색하는 라우팅 엔진에서 나옵니다. 각 출발지에서 각 목적지까지 가장 빠른 경로를 고르고, 구간 비용을 합산해 총합을 반환합니다. 이는 두 좌표 사이에 직선을 긋고 건물, 강, 일방통행이 존재한다는 사실을 무시하는 haversine 계산과는 근본적으로 다릅니다.

좌표 쌍은 두 점이 어디에 있는지를 알려줍니다. Distance matrix는 두 점 사이를 실제로 이동하는 비용이 얼마인지 알려줍니다.

Distance vs Duration

세 가지 다른 숫자가 종종 "distance"라고 불리는데, 이를 혼동하는 게 라우팅 코드의 가장 흔한 버그입니다.

Haversine 거리는 두 위경도 쌍 사이의 대권 거리입니다. 계산이 빠르고 네트워크 호출이 필요 없지만, 운전이 관련된 어떤 작업에서도 틀린 값입니다. 2km haversine 거리가 건널 수 없는 강을 고려하면 7km 운전 거리가 될 수 있습니다.

도로 네트워크 거리는 실제 운전 가능한 경로의 길이입니다. 일방통행, 회전 제한, 도로 그래프의 위상을 반영합니다. 이게 distance matrix API가 distance 필드로 반환하는 값입니다.

트래픽 반영 소요 시간은 현재 또는 예측 트래픽 조건에서 이동에 걸리는 시간입니다. 12km 고속도로 구간은 02:00에는 6분이지만 17:30에는 25분입니다. ETA가 중요한 프로덕션 시스템은 트래픽 인식 소요 시간을 요청하고 출발 시간을 전달해서 라우팅 엔진이 혼잡을 정확히 모델링하도록 합니다.

랭킹과 디스패치에서는 거의 항상 소요 시간이 거리보다 우선합니다. 더 가까운 작업이 800m 더 멀어도 운전에서 4분을 줄여준다면 기사 입장에서는 그게 더 좋습니다.

Distance Matrix가 등장하는 곳

Distance matrix는 대부분의 물류 및 위치 인식 기능 아래에서 조용히 돌아가고 있습니다.

• 배달 기사 배정: 각 대기 주문을 각 가용 기사와 매칭합니다. 디스패처는 차량 용량과 시프트 제약을 만족하면서 소요 시간이 가장 낮은 셀을 고릅니다
• 차량 디스패치와 리밸런싱: 라이드헤일링과 라스트마일 플랫폼은 차량과 수요 구역 사이의 matrix를 몇 초마다 계산해 차를 승객 근처에 유지합니다
• 매장과 시설 검색 랭킹: haversine으로 가장 가까운 5개 매장을 반환하는 대신, 사용자 위치에서 후보들까지 작은 matrix를 계산해 운전 시간으로 랭킹합니다
• 대규모 ETA 계산: 동시 주문이 많은 마켓플레이스는 수천 개의 단일 경로 요청 대신 ETA를 matrix 호출로 묶습니다
• VRP 솔버: vehicle routing problem 솔버(OR-Tools, jsprit, 상용 옵티마이저)는 입력으로 전체 비용 matrix를 요구합니다. 라우팅 솔루션의 품질은 입력으로 넣은 matrix의 품질로 한정됩니다
• 부지 선정과 영역 계획: 분석가들은 후보 위치와 고객 클러스터 사이의 matrix를 계산해 총 운전 시간을 최소화하는 창고를 고릅니다

이 모든 경우에서 matrix는 대량 계산 프리미티브입니다. N x M번의 개별 라우팅 호출 비용을 치르지 않고도 시스템이 "다수 중 최선"에 대해 추론할 수 있게 해주는 도구죠.

프로덕션의 함정

Distance matrix는 첫날에는 쉽지만 빠르게 어려워집니다.

비대칭이 기본값입니다. 실제 도로 네트워크는 일방통행, 분리 차도, 비대칭 회전 비용을 가집니다. (A, B) 셀이 (B, A) 셀과 같은 경우는 거의 없습니다. 메모리를 아끼려고 matrix를 대칭으로 취급하는 것은 디스패치 시스템에서 역방향 라우팅을 일으키는 고전적 원인 중 하나입니다.

N x M 비용. 100 x 100 matrix는 10,000개 셀입니다. 500 x 500 matrix는 250,000개 셀입니다. 비용과 지연은 제곱으로 늘어납니다. 대부분의 프로덕션 시스템은 matrix를 청크(50 x 50 또는 100 x 100)로 묶어 요청을 병렬화하고, 자주 바뀌지 않는 결과(고정된 창고 집합과 고정된 매장 집합 사이의 matrix 같은)는 캐시합니다.

시간대별 변동. 03:00에 계산된 matrix는 17:00에는 유효하지 않습니다. 디스패치 로직이 트래픽에 의존한다면, 의사결정 시점에 트래픽 인식 matrix를 요청하거나 시간대별로 미리 계산된 작은 matrix 집합(아침 피크, 비피크, 저녁 피크)을 만들어 적절한 것을 골라 쓰세요.

배칭과 레이트 리밋. Distance matrix API는 요청당이 아니라 element당 과금하며, 대부분의 제공자는 단일 호출 크기에 상한을 둡니다. 첫날부터 청킹과 백프레셔를 계획하세요. 규모에서 발견하는 것보다 낫습니다.

좌표 품질이 곧 결과 품질. Matrix는 입력 좌표만큼만 좋습니다. 분리된 고속도로의 잘못된 쪽에 떨어진 geocode는 엉뚱한 소요 시간을 만들어냅니다. matrix 요청에 들어가기 전에 입력 좌표를 검증하세요.

MapAtlas의 Distance Matrix

MapAtlas Distance Matrix API는 실제 유럽 및 글로벌 도로 네트워크 위에서 이동 시간과 거리의 전체 N x M matrix를 계산합니다. 자동차, 트럭, 자전거, 보행자 프로필을 지원하고, 출발 시간을 포함한 트래픽 인식 요청을 받으며, 실제 디스패치와 최적화 워크로드가 필요로 하는 배치 크기에 맞춰 만들어졌습니다.

랭킹을 넘어선 워크로드라면 Distance Matrix API는 Optimize Route API와 자연스럽게 짝을 이룹니다. Optimize Route API는 matrix와 정류장 집합을 받아 총 운전 시간을 최소화하는 순서가 정해진 경로를 반환합니다. 또한 Isochrone API와도 짝을 이뤄, "X분 안에 도달 가능한 모든 곳" 필터로 matrix 호출 전에 후보 집합을 미리 줄일 수 있습니다.

Distance matrix는 화려하지 않습니다. 그저 숫자들의 격자일 뿐입니다. 하지만 "다수 중 최선 찾기"를 N x M 라우팅 악몽에서 단일 대량 요청으로 바꿔주는 숫자 격자이고, 이 데이터 한 조각을 제대로 만드는 게 진짜 물류 제품과 지도에 핀 5개 꽂은 데모를 가르는 차이입니다.