[데이터 엔지니어링] ETA(Estimated Time of Arrival) 모델 설계

택시 운행에 있 도착 예정 시간(ETA)은 중요한 정보이다.

ETA 정보는 특히 카카오 택시 배차 알고리즘에서도 주요 정보로 사용되며, ETA score가 낮은(고객에게 가장 빠르게 도달할 수 있는) 기사에게 우선 배차된다.

Kakao mobility AI 배차 시스템

크게 경로 설정, 그리고 해당 경로에 해당하는 소요 시간을 계산하는 과정으로 모델이 구성되며, ETA는 실시간 예측이 필요한 태스크로, latency 최적화도 모델 설계에 중요하게 고려되어야 한다.

각 구역 별로, 아침, 점심, 저녁과 같은 시간대에 따른 거리 당 time duration 값을 batch 학습으로 주기적으로 업데이트되어 저장하는 것을 제안한다. 각 구역 별로 거리 당 이동 시간이 정의되므로, 실제 ETA 예측에서는 이동 경로 내 존재하는 육각형 구역 N개에 대해, O(N)의 시간 복잡도를 가져 연산 시간이 수용 가능한 수준으로 떨어질 것이라 예상된다. 

 

1. feature: Rush hour 혼잡 시간 지표

고객 운송 여정 시간표 What's you ETA? (NEMO 2023, 카카오 모빌리티 최원석)

 

우선 Rush hour라 불리는 출퇴근 시간, 점심 또는 저녁 시간 대에 차량 이동량은 크게 증가한다. 같은 거리라도 이와 같은 특정 시간대에서는 이동 시간이 증가할 것이기 때문에 우리가 찾고자 하는 것은 각 구역의 시간 별 time scaling factor (s>0)이다.

 

구역 A에 대한 time scaling distribution (예시 이미지)

초기 모델에는 상식적으로 출퇴근, 식사 시간을 지정하고 이 때의 scaling factor를 2, 1.5 등으로 경험적으로 지정한다. 

이후 정확한 distribution을 추정하기 위한 방법은 혼잡 구역 지표의 추정 방법과 함께 후술하고자 한다.

 

2. feature: 혼잡 구역 지표

그리고 특징 구역은 인구 밀도 대비 도로가 넓지 않거나, 유동 인구가 많아 특히 막힐 수 있다.

예를 들어, 지방 소도시의 경우에는 도시 끝에서 끝까지 가는 데에 1시간이 채 걸리지 않지만 서울의 경우 유동 인구가 많아 훨씬 짧은 지하철 역 5 정거장 이내의 거리에서도 동일한 시간이 걸리는 경우가 있다.

 

이러한 지표를 ETA에 반영하기 위해서는 전체 지역을 작은 구역으로 쪼개고 각 지역별로 scailing factor를 찾아야 한다.

아래와 같이 육각형 구역으로 나누고, 택시의 여정 과정에 실시간 GPS 좌표 값을 수집하여 이 값을 바탕으로, 실시간 위치 구역 번호를 생성 이 데이터로 구역 별로 gpa 들어간 시간, 나온 시간, 그리고 이동 거리 세 가지 feature를 생성한다. 

실시간 정보 수집 timestamp 별 [x, y] 값으로부터 [구역 번호, 들어간 시간, 나온 시간, 이동 거리, 이동 시간]의 feature를 생성할 수 있고, 혼잡 시간 지표는 [들어간 시간, 나온 시간, 이동 시간] 그리고 혼잡 구역 지표는 [구역 번호, 이동 거리, 이동 시간] 를 입력값으로 예측될 것이다. 

 

probabilistic graphical models, 딥러닝 기반의 Variational Autoemcoders(VAE), Gaussian Mixture Models(GMM), Kernel Density Estimation(KDE)와 같은 분포 추정 기법, 회귀 분석과 같은 여러 모델 알고리즘 옵션들을 고려하였다.

데이터 차원이 크지 않아, 데이터로부터 distribution을 추정하는 unsupervised learning 방법인 커널 밀도 추정 방식으로 모델을 설계하는 방식을 제안한다.

모델 output 시각화 자료, 각 구역에 시간대 별 1m 당 소요 시간이 예측된다.

3. 후순위 feature: 날씨, 과거 운전자 데이터

추가적으로 모델 성능을 높이기 위해서 날씨 정보와 운전자의 과거 운전 데이터를 사용할 수 있다.

날씨의 경우에는 눈이나 비가 올 때, 차가 더 막히는 경향이 있다는 점, 그리고 운전자마다 운행 속도에 차이가 있어 ETA에 반영하였을 때 결과 정확도에 긍정적인 역할을 할 것이라 예상했다.

 

날씨의 경우, 기상청의 동네예보 API가 국소적 지역 그리고 30분이라는 짧은 주의 강수량, 강수 확률, 기온, 풍향, 풍속, 습도를 가지고 있어 학습 데이터로 가장 적합할 것으로 보인다.

{
...
"T1H": 26,
"REH": 10,
"SKY": 3,
"RN1": 0
...
}

 

T1H: 기온
REH: 습도
SKY: 하늘상태
RN1: 강수량

 

운전자 운행 속도는 각 구역 통과 시간 데이터를 가질텐데, 예측 운행 시간보다 크거나 작다면 이에 맞춘 보정 scaling factor를 정의할 수 있을 것이다. 하지만, 빨리 가야하거나 천천히 가도 되는 상황에 따라 운전자의 속도가 유동적으로 변할 수 있기 때문에 소극적으로 예측값에 반영되어야 한다고 생각한다.

 

4. 다익스트라 알고리즘으로 택시의 최단 경로 예측

잘게 쪼갠 육각형 구역들은, 인접한 육각형에 간선이 연결된 무향 그래프에 각 구역 노드 별로 육각형 두 변 길이의 이동 시간의 크기의 값을 가진 그래프로 이해할 수 있다. 육각형 한 변 길이의 이동 시간은 해당 구역을 지나는 최소 시간이므로 적절히 두 개 변의 길이로 이동 거리의 기준을 잡았다.

 

 

이후 특정 노드에서 다른 노드로 이동하는 간선의 가중치를 이동하려는 노드의 가중치로 해석하면 택시의 최단 거리는 정의한 그래프에의 다익스트라 알고리즘의 문제로 치환할 수 있다. 물론 자세한 도로망 정보가 있다면 더 정확한 알고리즘을 만들 수 있을 것이다.

 

5. spatial data 관리 방법: 차량이 속한 구역 판별

앞서 소개한 모델 설계에서 전체 구역을 작은 구역으로 나눈 뒤, 데이터 수집 과정에서 차량이 해당 구역이 속해 있는지를 확인해야 한다.

 

우선 구역은 6개의 (x, y) 좌표 값을 가지고 있고, 중심점 (cx, cy)를 가질 수 있다. 초기 위치는 가장 중심점과 가까운 구역으로 설정한 뒤에 이후에는 중심점을 기준으로 6변을 linear equation으로 정의한 뒤, 중심점과 택시의 현재 위치를 연결한 선분이 6변 중 하나와 교차했을 때, 해당 방향으로 인접한 구역으로 이동한 것으로 업데이트하고 이를 반복하며 spatial data를 관리할 수 있을 것이다.

 

# 두 점을 지나는 직선의 방정식 계산
def line_equation(x1, y1, x2, y2):
	slope=(x1-x2)/(y1-y2)
    intercept=y1-slope*x1
    return slope, intercept
    
# 두 직선이 교차하는지 판별
def is_intersect(x1, y1, x2, y2, x3, y3, x4, y4):
	slope1, intercept1=line_equation(x1, y1, x2, y2)
    slope2, intercept2=line_equation(x3, y3, x4, y4)
    
    if slope1==slope2:
    	return False
        
    intersection_x=(intercept1-intercept2) / (slope2-slope1)
    intersection_y=slope1*intersection_x +intercept1
    
    if min(x1, x2) <= intersection_x <= max(x1, x2) and \
       min(y1, y2) <= intersection_y <= max(y1, y2) and \
       min(x3, x4) <= intersection_x <= max(x3, x4) and \
       min(y3, y4) <= intersection_y <= max(y3, y4):
       	return True
    return False