5만 개의 배달이 존재하고 5만 명의 라이더가 활동 중이라고 가정했을 때, 단순히 경우의 수를 계산하면 배차시스템은 25억 건의 계산을 수행해야 합니다. 그러나 현실적으로 매 배차 사이클마다 25억 건을 모두 계산하는 것은 불가능하므로, 이를 최적화하는 과정을 거치게 됩니다. 따라서 배차시스템은 다음과 같은 과정을 통해 배차를 최적화합니다.

ㅤ

라이더의 상태를 수치화하는 방법

앞서 소개드린 배차 과정에서는 ‘비용 계산’이라는 용어가 등장합니다. 배차 최적화 과정은 배달과 라이더의 매칭 문제를 수리 최적화로 해결하기 때문에, 현재 라이더의 상태와 신규 배차를 반영한 상태 변화를 수치적으로 모델링해야 합니다. 배달과 라이더의 특성에는 다양한 속성이 있지만, 그중 가장 중요한 속성은 다음과 같습니다:

• 라이더의 속도
• 라이더가 이미 수행 중인 배달들의 거리 및 소요 시간
• 라이더가 새로 배차받을 배달들의 예상 거리 및 소요 시간

이 세 가지 속성을 종합해보면, 결국 라이더가 배달을 어떤 순서로, 얼마나 빠르게 수행하는지가 배차에서 매우 중요한 요소가 됩니다.

다음은 오토바이 라이더와 자전거 라이더가 동일한 경로를 수행하는 예시입니다.

ㅤ

A와 B 두 개의 배달 건을 위와 같은 순서로 평균 시속 30km로 주행하는 오토바이 라이더가 수행한다면, 주행 시간만 약 4분 36초가 걸립니다. 같은 상황에서 평균 시속 5km인 자전거 라이더가 수행한다면 약 13분 48초가 걸립니다. 그러나 오토바이 라이더가 더 빠르게 배달을 수행할 수 있다고 해서 무조건 오토바이 라이더에게 배차하는 것이 좋은 것은 아닙니다. 배달이 많은 상황에서는 오토바이 라이더와 자전거 라이더를 모두 활용해, 시스템 입장에서 최대한 효율적인 조합을 찾아 배차해야 합니다. 따라서 최적화 알고리즘의 입력으로 활용하기 위해, 라이더가 수행할 것으로 예상되는 배달의 진행 순서를 시퀀스화해 수치화 작업을 진행하게 됩니다.

이 글의 주제가 되는 실거리는, 이러한 수치화 작업의 성능과 정확도를 좌우하는 중요한 요소입니다. 이어서 배차시스템의 경로 문제를 설명하면서, 실거리의 중요성에 대해 자세히 이야기해보겠습니다.ㅤ

왜 실거리가 중요할까?

배차시스템의 경로 문제

배달 진행 순서의 시퀀스, 다시 말해 라이더가 배달을 수행하기 위한 위치들의 순서를 경로라고 부릅니다.

여기서 ‘배달을 수행하기 위한 위치’란 배달의 픽업지와 전달지를 의미합니다. 그렇다면, 한 명의 라이더가 배달을 수행하는 과정에서 가능한 경로의 경우의 수는 몇이나 될까요? 배달의 진행 상태와 배달 개수에 따라 가능한 경로는 매우 다양하게 달라집니다.

경로를 계산하기 위해 그래프를 한 번 그려보면, 꽤 많은 간선이 만들어집니다. 라이더에게 할당된 신규 배달이 N개라고 했을 때, 정점과 간선의 수는 다음과 같습니다.

• 정점: 픽업지와 전달지를 모두 거쳐야 하므로 2N개
• 간선: C(2N, 2)개

이때 그려본 것은 하나의 조합(라이더:매칭=1:1)에 대한 그래프에 불과합니다. 실제 최적화 과정에서는 한 명의 라이더가 수행할 수 있는 여러 배달 조합(라이더:매칭=1:N)에 대해서도 모두 수치화를 해보아야 합니다. 즉, 라이더당 배차 가능한 모든 배달 조합에 대해 경로를 계산하고 수치화하여 최적화 알고리즘에 전달해야 합니다. 그리고 이 수치화를 위해서는 각 간선에 대한 거리값을 반드시 알아야 합니다.

ㅤ

거리는 예민한 문제이다

배달 도메인에서 거리는 예민한 문제입니다. 라이더분들은 짧은 시간과 짧은 이동 거리로 최대한 많은 배달을 수행해야 하기 때문입니다. 다만 한 가지 강조할 것은, 배차 경로에서의 거리는 실제 배달료를 책정하는 데 사용되는 수행 거리는 아니라는 점입니다.

참고: 배달료 책정이나 배민커넥트 앱상에서 활용되는 거리 계산에는 상용 내비게이션이 사용됩니다.

그럼에도 거리는 중요합니다. 배차 최적화를 하려면, 거리값이 정확하고 일관돼야 합니다. 거리를 기반으로 효율적인 경로를 만들어보고, 그 경로를 기반으로 한 수치들이 최적화에 사용됩니다. 그러므로 단순히 직선거리로 셈하기보다는 가능한 현실 세계에 가까운 거리를 사용할 수 있어야 합니다.

ㅤ

작은 변화가 배차시스템 전체의 성능을 좌우한다

두 지점 간의 거리를 계산하는 일은 얼핏 단순해 보일 수 있습니다. 하지만 수많은 경우의 수에 따른 경로를 고려해야 하기 때문에, 작은 변화도 배차시스템 성능에 큰 영향을 미칠 수 있습니다. 마치 나비효과와도 같죠. 배차해야 할 배달이 많아질수록 이러한 영향은 더욱 커집니다. 이처럼 직선거리에서 실거리로의 전환은 단순한 변화가 아니라, 배차 전반의 효율성과 정확도에 영향을 미치는 중요한 변화가 될 수 있습니다.

지금까지 배차시스템에서 실거리가 왜 중요한지 설명드렸습니다. 배차시스템은 한 번의 배차 과정에서 필요한 모든 간선의 실거리를 계산합니다. 이 실거리는 배차의 정확도를 결정짓는 중요한 요소입니다. 하지만 작은 변화만으로도 시스템 성능이 쉽게 저하될 수 있는 민감한 부분이기도 합니다. 따라서 배차의 정확도와 성능을 모두 고려하기 위해 실거리 시스템을 도입했던 과정을 소개합니다.