라스트 마일 배송 시스템은 거의 멈추지 않는 세상에서 운영됩니다. 트럭이 이미 움직이고 있는 동안에도 주문이 도착하고, 교통 상황은 수시로 변하며, 배송 시간대(delivery window)는 종종 매우 촉박합니다. 이러한 환경에서 하루의 시작 단계에서 한 번 계산된 정적인 계획은 충분하지 않은 경우가 많습니다. 대신, 배송 관리자는 기존 경로에 새로운 경유지를 삽입하거나, 고객이 취소하거나 차량이 고장 났을 때 경로를 재배치하는 등 계획을 끊임없이 업데이트해야 합니다. 이러한 지속적인 재최적화의 필요성은 어려운 계산적 과제를 만들어냅니다. 즉, 시스템은 단 몇 초 만에 새로운 유효한 경유지 배열을 찾아내야 합니다. 컴퓨터가 생각하는 데 너무 오래 걸리면 배송 시간대를 놓치거나 운전자가 공회하며 기다리게 됩니다. 만약 컴퓨터가 트럭의 과적이나 도착 지연과 같은 규칙을 위반하는 새로운 경로를 추측한다면, 전체 계획은 무너지고 시스템은 처음부터 다시 시작해야 합니다. 목표는 단순히 최단 경로를 찾는 것이 아니라, 즉각적으로 실행 가능한 경로를 찾는 것입니다.

후베이 자동차 공과대학교(Hubei University of Automotive Technology)의 연구진은 이러한 문제를 해결하기 위해 인공지능 세계의 전략을 빌려와 초 단위의 결정을 더 신뢰성 있게 만드는 새로운 접근 방식을 개발했습니다. 그들은 이 시스템을 SRI-ECR-balanced라고 부릅니다. 새로운 주문이 들어올 때마다 매번 완벽한 경로를 처음부터 계산하려 하기보다, 이 시스템은 숙련된 편집자가 몇 문장을 초안으로 작성하고, 오류를 점검하고, 좋은 부분은 남겨두며, 잘못된 부분은 즉시 수정하는 방식처럼 작동합니다. 투기적 실행(speculative execution)이라고 알려진 이 방법은 시스템이 한 번에 여러 개의 미래 경유지를 제안하고, 어떤 것들이 안전한지 검증한 뒤, 문제가 발생하기 전에 나머지를 버릴 수 있게 해줍니다. 이를 통해 시스템은 전통적인 방식보다 훨씬 빠르게 충돌에서 회복할 수 있으며, 상황이 급변하더라도 배송 계획이 실행 가능성을 유지하도록 보장합니다.

이 새로운 프레임워크의 핵심은 초안 작성, 검증, 그리고 수리의 순환입니다. 새로운 주문이 들어오면 '초안 생성기(draft generator)'가 트럭의 경로에 추가할 짧은 고객 시퀀스를 제안합니다. 과거의 시스템들은 한 번에 한 명의 고객만 삽입하려고 하여 속도가 느렸거나, 혹은 긴 고객 목록을 한꺼번에 삽입하려다 실수를 저지르곤 했습니다. 이 새로운 시스템은 그 사이에서 균형을 잡습니다. 즉, 한 번에 약 5개 정도의 작은 그룹을 제안합니다. 그다음 별도의 '검증기(verifier)'가 트럭의 무게 제한이나 고객의 시간대와 같은 도로 규칙에 대해 이 그룹을 검사합니다. 시스템은 제안된 그룹 중 규칙에 부합하는 가장 긴 구간을 수용하고 나머지는 즉시 버립니다. 만약 제안된 그룹의 첫 세 곳은 괜찮지만 네 번째 곳이 트럭에 너무 무겁다면, 시스템은 첫 세 곳은 유지하고 네 번째 곳은 롤백(되돌리기)합니다. 전체 계획을 통째로 버리는 것이 아니라, 규칙을 어긴 부분만을 제거하는 것입니다.

무효한 경유지들이 롤백되면, 전문적인 '수리 전문가(repair expert)'가 개입하여 문제를 해결합니다. 이것은 일반적인 해결사가 아닙니다. 시스템은 정확히 무엇이 잘못되었는지 진단합니다. 만약 트로가 너무 가득 찬 것이 문제라면, 전문가는 공간이 더 있는 다른 트럭을 찾는 것을 우선시합니다. 만약 좁은 시간대 때문에 고객을 놓치는 것이 문제라면, 전문가는 더 일찍 도착할 수 있는 경로를 찾습니다. 이러한 표적 접근 방식은 매우 중요합니다. 연구진은 이러한 특정적이고 충돌을 인지하는 수리 단계가 없다면, 스트레스가 심한 상황에서 시스템이 유효한 경로를 찾지 못한다는 것을 발견했습니다. 시스템이 전문가 방식 대신 무작위 수리 방식을 사용하도록 강제되었을 때, 시스템은 문제의 약 3분의 1만을 해결할 수 있었고 많은 주문이 처리되지 못한 채 남겨졌습니다. 하지만 전문가형 라우터를 사용했을 때, 시스템은 테스트에서 모든 충돌을 성공적으로 수리하며 실행 가능한 계획에 대한 완벽한 기록을 유지했습니다.

이 과정을 실시간 사용이 가능할 만큼 빠르게 만들기 위해, 시스템은 '경로 접두사 캐시(route-prefix cache)'라고 불리는 형태의 메모리도 사용합니다. 역동적인 환경에서 트럭 경로의 대부분은 한 순간에서 다음 순간으로 넘어가도 동일하게 유지되며, 오직 경로의 끝부분만 변합니다. 전통적인 시스템은 작은 변화가 생길 때마다 여정 전체를 재계산하여 변하지 않은 부분에 시간을 낭비하곤 합니다. 이 새로운 시스템은 이미 확인된 경로 부분에 대한 계산을 기억합니다. 새로운 경유지를 확인해야 할 때, 시스템은 저장된 데이터를 재사용하여 새로운 부분만을 계산합니다. 이 간단한 기술은 잠재적 경로를 평가하는 속도를 3배 이상 높였습니다. 100명의 고객을 대상으로 한 표준 테스트에서, 이 캐싱 기술은 처음부터 시작할 때보다 경로를 3.12배 더 빠르게 평가할 수 있게 해주었습니다. 200명의 고객을 대상으로 한 더 큰 테스트에서도 속도는 3.08배 향상되었습니다.

연구진은 이 시스템을 물류 기업들이 사용하는 기존 도구들, 즉 최단 경로를 찾는 데 강력한 솔버인 OR-Tools 및 PyVRP와 비교하여 테스트했습니다. 그들은 새로운 주문이 끊임없이 도착하고 시간대가 인위적으로 매우 좁게 설정되어 스트레스를 유발하는 시뮬레이션을 실행했습니다. 이러한 어려운 조건에서 전통적인 솔버들은 하나의 결정을 내리기 위해 허용된 3초를 거의 다 써서 해결책을 찾아냈으며, 그럼에도 불구하고 때때로 계산 시간이 더 오래 걸리는 약간 더 짧은 경로를 만들어내기도 했습니다. 반면, 이 새로운 시스템은 평균적으로 0.5초 미만 만에 유효한 해결책을 찾아냈습니다. 이 시스템이 생성한 경로는 강력한 솔버들이 찾은 경로보다 총 거리가 약 7.8% 더 길었지만, 이는 의도된 트레이드오프였습니다. 실제 배송 시나리오에서는, 완벽한 경로가 너무 늦게 도착하는 것보다 즉시 준비되는 약간 더 긴 경로가 더 가치 있는 경우가 많습니다. 시스템은 마지막 1마일의 효율성을 쥐어짜는 것보다 실행 가능한 계획을 내보내는 것을 우선시했습니다.

연구진은 또한 시스템이 다양한 위험 수준 하에서 어떻게 작동하는지 탐구했습니다. 그들은 새로운 경유지를 추가하는 위험을 신중하게 따지는 '균형 잡힌(balanced)' 접근 방식과, 확인하기 전에 가능한 한 많은 경유지를 추가하려는 '공격적인(aggressive)' 접근 방식을 비교했습니다. 공격적인 방식은 시스템이 많은 실수를 저지르게 하여 롤백 횟수를 늘렸고, 이는 속도를 크게 저하시켰습니다. 균형 잡힌 방식은 위험한 움직임을 제안하기도 전에 미리 페널티를 부여함으로써 실수를 줄이고 시스템이 원활하게 움직이도록 유지했습니다. 이는 시스템이 신중하게 투기할 때, 즉 몇 단계 앞을 예측하되 확정하기 전에 엄격하게 검증할 때 가장 잘 작동한다는 것을 확인시켜 주었습니다.

연구진은 자신들의 시스템이 시간이 고려되지 않는 정적인 세계에서 가장 짧은 경로를 찾는 데 최고라고 주장하지 않았습니다. 그들은 오직 거리 최소화가 목표이고 컴퓨터가 몇 초 동안 생각할 시간이 있는 문제의 경우, 전통적인 솔버들이 여전히 승리한다고 명시적으로 밝혔습니다. 이 새로운 프레임워크의 가치는 구체적으로 동적 배송의 혼란스럽고 시간 압박이 심한 세계에 있습니다. 이러한 시나리오에서는 완발한 경로를 찾는 것보다 충돌로부터 즉각적으로 회복하고 유효한 계획을 유지하는 능력이 더 중요합니다. 시스템은 가장 스트레스가 심한 테스트 시나리오에서 탈락된 주문 없이 100%의 고객을 서비스함으로써 그 가치를 입증했으며, 실시간 배송 센터에서 사용하기에 충분히 낮은 응답 시간을 유지했습니다.

연구진이 예측 불가능한 교통 지연을 시뮬레이션하기 위해 무작위 노이즈를 도입했을 때도 시스템은 잘 버텨냈습니다. 시스템은 모든 고객을 서비스하고 충돌을 성공적으로 수리하며, 이 방법이 현실 세계의 불확실성을 처리할 만큼 견고하다는 것을 보여주었습니다. 또한 그들은 실제 드롭오프 좌표를 사용하여 주요 물류 회사의 실제 배송 데이터 조각을 대상으로 시스템을 테스트했습니다. 시스템은 이 실제 데이터에서도 성공적으로 작동하여 테스트 세트의 80개 지점을 모두 서비스했습니다. 그러나 연구진은 현재 설계의 한계를 주의 깊게 언급했습니다. 400명의 고객을 대상으로 훨씬 더 큰 시나리오를 테스트했을 때, 시스템은 시간 제한 내에 완벽한 해결책을 찾지 못해 약 4분의 3의 주문만을 처리했습니다. 이는 이 방법이 중간 규모의 함대에는 잘 작동하지만, 더 큰 규모의 운영에는 문제를 더 작은 조각으로 나누는 추가적인 전략이 필요함을 시사합니다.

궁극적으로, 이 연구는 우리가 경로 문제를 해결하는 방식에 대한 인식의 전환을 보여줍니다. 컴퓨터를 단 하나의 최선의 답을 찾아야 하는 계산기로 보는 대신, 연구진은 컴퓨터를 빠르고 신뢰성 있게 좋은 답을 찾아야 하는 의사 결정자로 취급했습니다. 현대 인공지능에서 사용되는 투기적 패턴—초안 작성, 검증, 캐싱—을 채택함으로써, 시스템은 동적인 배송의 불확실성을 신속하고 안정적으로 헤쳐 나갈 수 있습니다. 이 연구 결과는 많은 현실 세계의 물류 과제에 있어, 수학적으로 완벽한 경로를 찾는 것보다 즉각적으로 적응하는 능력이 진정한 성공의 척도라는 점을 시사합니다. 이 시스템은 모든 지연을 없애거나 매번 최단 경로를 찾는다고 약속하지는 않지만, 새로운 주문이 들어왔을 때 즉시 실행 가능한 계획이 준비되어 배송 네트워크의 바퀴가 계속 돌아가도록 보장합니다.