하루 26,000식을 배달한다는 건가요?
이러한 물량을 위한 배달 물류는 쉽지 않습니다. 우리는 자원봉사자 운전자들이 1회 배달 시 15개의 급식 배급분(즉, 30식)을 처리할 수 있다고 가정하고 있으며, 각 운전자에게 최적화된 운전 경로를 제공하고 있습니다. 그럼에도 불구하고 배달을 완료하는 데 약 1.5~2시간이 소요되며, 이는 우리 자원봉사자들이 주 2~3일 동안 지속 가능하다고 느끼는 시간입니다.
우리의 경우 26,000식은 13,000개의 급식 배급분에 해당합니다. 이는 우리에게 약 7,000개의 정지(한 정지당 약 2개의 배급분)를 의미할 것으로 예상됩니다. 자원봉사자 운전자와 일반 승용차를 배달에 활용한다고 가정하면, 우리에게는 매일 700명의 운전자가 필요하며, 실제로는 약 2,000명의 운전자가 필요할 것입니다(우리 자원봉사자들은 매일 운전하기 위해 자원하지 않으므로).
만약 식사 공급원을 통제할 수 있다면(우리는 음식을 직접 만들지 않아 이 부분이 훨씬 어렵습니다), 단순히 주소 목록을 운전자별로 분할한 후 각 경로를 최적화하면 됩니다. 우리의 물량은 여러분보다 훨씬 적습니다(우리는 하루 2,000~3,000식, 즉 여러분 물량의 1/10을 고려하고 있습니다) 때문에 주소 목록을 자동 분할하지 않습니다. 각 배달 주소는 특정 동네에 할당되며, 우리의 디스패처들은 동네별로 배달 목록을 수동으로 분할합니다(간단한 스프레드시트 정렬입니다). 그런 다음 AWS에서 실행되는 웹 서버를 통해 각 운전자의 경로를 최적화하고, 각 운전자에게 최적화된 운전 경로를 제공합니다(간단한 순회 판매원 알고리즘).
전체 주소 목록을 자동 분할하는 방안도 고려해 보았습니다. 하지만 아직 필요하지 않고, 예산이 넉넉지 않아 AWS와 Google Maps API 비용을 낮게 유지하고 싶기 때문입니다. 일반화된 다중 차량 경로 문제(Multiple Vehicle Routing Problem)에 대해서는 사용할 수 있는 단순한 알고리즘적 해결책이 있으며, 예를 들어 다음과 같습니다:
그러나 그 정도의 배달 물량을 처리하려면 매우 넓은 지리적 영역을 커버해야 할 것 같으며, 따라서 운전자의 가정 주소도 고려해야 할 수 있습니다. 이는 일반적인 VRP의 범위를 벗어납니다. 아마도 단순한 휴리스틱을 사용하여 운전자 그룹과 배달 주소를 동일한 지리적 영역에 속하는 하위 문제로 분할할 수 있을 것이며, 이 경우 표준 VRP 솔루션을 다시 사용할 수 있을 것입니다.
참고로 우리는 GMap의 이동 시간을 점 대 점 거리로 사용하고 있습니다.