라스트 마일 배송 및 경로 최적화의 AI

배달 차량 라우팅은 여행하는 판매원 문제를 일반화한 차량 라우팅 문제(VRP)의 교과서 사례입니다. 기지, 차량 및 정류장 세트가 주어지면 목표는 제약 조건을 충족하면서 총 비용을 최소화하는 경로입니다. 여기에는 차량 용량, 운전자 교대 시간, 고객 시간대, 때로는 픽업 및 배송 쌍이 포함됩니다. 문제는 NP-하드입니다. 중지 횟수가 증가함에 따라 정확한 솔루션이 실용적이지 않게 되므로 실제 시스템은 휴리스틱(보장되지 않은 최선의 답변을 찾는 경험적 법칙)에 의존합니다. 고전적인 방법에는 1964년의 Clarke-Wright 절약 알고리즘과 교차하는 경로 세그먼트를 풀어주는 2-opt와 같은 지역 검색 이동이 포함됩니다. Google의 OR-Tools와 같은 오픈 소스 도구를 포함한 최신 솔버는 이를 많은 후보 솔루션을 탐색하는 메타휴리스틱과 결합합니다. 2010년대에 출시된 UPS의 ORION 시스템이 잘 알려진 사례입니다. 각 운전자의 정차 순서를 최적화합니다. UPS는 또한 가능한 경우 좌회전을 피하고 공회전을 줄이고 위험한 회전을 줄이기 위해 약간 더 긴 거리를 거래하는 경로를 오랫동안 선호하는 것으로 알려져 있습니다. 머신러닝은 최적화 위에 예측을 추가합니다. 모델은 하루 중 시간, 각 정류장에서의 서비스 시간(주차장 찾기, 계단 오르기, 서명 받기) 및 배달 실패 가능성을 기준으로 이동 시간을 추정합니다. 2021년에 Amazon와 MIT는 숙련된 운전자가 실제로 선호하는 경로를 팀에 요청하는 연구 챌린지를 진행했습니다. 수학적으로 가장 짧은 경로가 항상 거리에서 작동하는 경로는 아니기 때문입니다. 음식 및 식료품 앱은 더 어렵고 역동적인 버전에 직면해 있습니다. 주문은 항상 도착하므로 배송팀에서는 어떤 택배사가 어떤 주문을 받을지, 주문을 묶을지 여부를 실시간으로 결정하여 택배사를 바쁘게 만드는 것과 속도의 균형을 맞춥니다. 일반적인 오해는 라우팅이 단지 최단 경로 탐색이라는 것입니다. 내비게이션은 두 지점 사이의 도로 경로를 찾습니다. 경로 최적화는 수백 개의 정류장의 순서와 할당을 결정합니다.