배달기사도 공정해야 한다: 배달 주문의 공정 배분 연구

플랫폼 시대에 우리가 당연하게 누리는 것 중 하나가 바로 ‘빠른 배달 서비스’다. 클릭 몇 번이면 음식이든 택배든 몇 시간 만에 문 앞에 도착한다. 그런데 그 이면에는 늘 시간에 쫓기며 달리는 배달기사들이 있다. 효율성을 극대화한 배달 시스템은 과연 기사들에게도 공정할까? 최근 「Fair Distribution of Delivery Orders」라는 흥미로운 논문은 이 질문을 과감하게 파고들었다.

왜 ‘공정한 배달’이 필요한가?

대부분의 배달 최적화 연구는 ‘얼마나 빠르게, 얼마만큼 짧은 거리로 배달할 것인가’를 중심으로 발전했다. 이는 소비자에게는 좋지만, 기사들에게는 그렇지 않을 수 있다. 특히 여러 기사들이 같은 지역을 돌며 배달해야 할 때, 누군가는 먼 거리까지 여러 번 다녀오고 누군가는 비교적 쉬운 동선을 배정받게 된다. 이 차이는 때론 수익과 직결되고, 더 나아가 직업 만족도와 이탈률에도 영향을 준다.

연구의 핵심 질문: 효율과 공정은 양립할 수 있을까?

이 논문은 배달 주문을 그래프(Graph) 위의 노드로 보고, 허브(예: 물류창고)를 중심으로 기사들이 각 주문을 어떻게 나눠 가질지 설계한다. 여기서 두 가지 목표가 충돌한다.

효율성: 전체 배달 거리(총 비용)를 최소화한다.
공정성: 모든 기사들이 비슷한 거리와 노력을 분담하도록 한다.

논문은 특히 EF1(Envy-Freeness up to one item)와 MMS(Minimax Share)라는 공정성 개념을 적용했다. 쉽게 말해, 한 기사가 다른 기사를 질투하더라도 ‘한 주문만 빼면 질투가 사라진다(EF1)’거나, 최소한 각자가 원하는 최악의 시나리오보다 나쁘지 않은 배정을 받는다(MMS)는 것이다.

흥미로운 실험: 트리 구조 위의 배달

연구팀은 현실성이 높은 가정으로 트리 구조를 채택했다. 트리는 동네 골목길 구조나 전형적인 미국 교외의 ‘막다른 길(Cul-de-sac)’ 구조와 유사하다.

예컨대 허브에서 각 집까지 배달하는 길은 트리의 가지처럼 뻗어 있다. 연구팀은 이런 트리에서 배달 노드를 어떻게 배분하면 공정성과 효율성을 동시에 만족시킬 수 있는지를 분석했다.

놀라운 결과: 항상 공정하면서 효율적일 수는 없다

연구는 중요한 현실을 보여줬다. 배달을 완벽하게 효율적으로 하려면 한 사람이 모든 주문을 몰아서 처리하는 게 제일 좋다. 하지만 이건 공정하지 않다. 반대로, EF1이나 MMS 조건을 만족시키면 효율성(최소 거리)이 떨어질 수밖에 없다.

그래서 연구팀은 ‘어디까지 양립할 수 있나’를 컴퓨터 실험과 수학적 분석으로 살폈다. 흥미롭게도 트리 구조에서는 EF1은 언제나 만족할 수 있고, MMS도 가능하다. 그러나 두 조건을 동시에 만족하면서 파레토 최적(Pareto Optimal)까지 달성하는 것은 일반적으로 어렵고, 심지어 NP-Hard 문제로 판명됐다.

연구진의 해법: 실현 가능한 알고리즘

이 논문은 현실적인 해결책도 제시했다. ‘완전한 최적화’는 어렵지만, XP 알고리즘(에이전트 수에 따라 연산 가능)이 있으면 트리 구조에서는 EF1과 MMS, 파레토 최적 조건을 찾아낼 수 있다.

이 알고리즘은 각 배달 노드가 포함된 가지(branch)를 어떻게 나눌지 계산해, 기사들 간 비용 차이가 최소화되도록 한다. 논문에서는 이걸 Pareto Frontier라 부르고, 가능한 조합을 모두 살펴 가장 균형 잡힌 배분을 찾아낸다.

실험적으로 본 공정성의 대가: Price of Fairness

연구는 ‘공정성의 대가(Price of Fairness)’도 분석했다. 즉, 공정하게 배분하면 얼마나 더 많은 거리(비용)를 치러야 하는지 수학적으로 계산했다.

예컨대 1명의 기사가 다 돌면 10km면 될 거리를, 2명이 공정하게 나눠 돌면 12km가 될 수도 있다. 연구에 따르면 EF1 조건에서는 최대 약 2배까지 비용이 늘어날 수 있다. 현실에서는 이는 추가 인건비와 시간으로 직결된다.

개인적 시각: 앞으로 배달 플랫폼이 배워야 할 점

나는 이 연구가 단순히 이론적 논문에 머물지 않길 바란다. 한국에서도 배달 라이더의 공정 배차는 큰 이슈다. 특정 지역에서 주문 밀도가 높으면 누구는 수익이 높고, 누구는 길거리에서 대기만 하다 허탕을 친다.

또한 자율주행 로봇이나 드론이 배달을 맡게 되는 미래에는 공정성과 효율성을 동시에 관리하는 알고리즘이 필수가 될 것이다. 더 많은 기사가 만족하는 배달 시스템은 더 많은 소비자와 기업에게도 이득이다.

결론: 효율과 공정, 둘 다 잡을 수 있을까?

이 논문이 던진 메시지는 분명하다. ‘효율=공정함’은 아니다. 빠른 배달 뒤에는 불균형한 노동이 숨겨져 있을 수 있다. 하지만 기술과 알고리즘으로 이 균형을 다시 설계할 수 있다는 점에서 희망이 있다.

플랫폼 기업은 이제 ‘최저 수수료’ ‘최단 거리’뿐 아니라 ‘최적의 공정 배분’을 설계할 수 있는지 고민해야 한다. 이 연구는 그 출발선에 선 소중한 시도라 할 만하다.

논문:

Hosseini, H., Narang, S., & Wąs, T. (2025). Fair Distribution of Delivery Orders. Artificial Intelligence. doi: 10.1016/j.artint.2025.104389