MilleMiglia: A realistic instance generator for middle-mile logistics

🖼️ 인포그래픽

🖼️ 4컷 인포그래픽

💡 한 줄 요약

MilleMiglia는 공개 데이터 부족으로 연구가 제한된 미들마일 물류를 위해 실제 운영 제약을 반영한 합성 벤치마크를 만드는 오픈소스 C++ 인스턴스 생성기다.

📌 핵심 요약

• 미들마일은 지역·대륙 규모의 물류센터 간 대량 운송을 담당하며 물류비의 상당 부분을 차지하지만, 기업의 네트워크 구조와 수요 정보가 비공개여서 고품질 공개 데이터를 확보하기 어렵다.
• 미들마일 화물은 여러 차량과 중간 물류센터를 거쳐 며칠에 걸쳐 이동할 수 있으므로, 고정 차량 시간표·물류센터 처리량 한계·환적 동기화를 함께 다뤄야 한다.
• MilleMiglia는 공간 분포, 화물의 출발지·도착지와 부피·중량 분포, 구조화된 차량 운행 일정에 관한 통계적 모델로 현실적인 합성 데이터를 생성하면서 비공개 정보를 보호하도록 설계됐다.
• C++로 구현된 MilleMiglia는 Protocol Buffers로 각 인스턴스의 데이터와 제약을 하나의 파일에 저장하며, 정확 알고리즘용 소규모 문제부터 대륙 규모 문제와 ML 학습용 대규모 데이터 세트까지 생성할 수 있다.
• Google·UniBrescia·ENPC Paris의 협력으로 개발된 MilleMiglia는 표준 벤치마크 체계의 첫 단계이며, 미들마일 전용 솔버와 API는 개발 중이고 연구 참여를 확대할 챌린지도 희망하고 있다.

🧩 주요 포인트

1. 여러 차량을 잇는 환적과 시간 의존성 → 개별 차량의 방문 순서 최적화를 넘어 시공간 그래프의 다중 상품 흐름으로 문제를 모델링한다.
2. 현실적인 합성 분포와 통합 제약 형식 → 민감한 운영 데이터를 직접 공개하지 않고도 실제 미들마일 문제에 가까운 연구 기반을 제공한다.
3. 소규모부터 대륙 규모까지 조절 가능한 인스턴스 → 정확 알고리즘·휴리스틱·메타휴리스틱·ML을 연구할 수 있지만, 생성기 공개와 전용 솔버의 완성은 구분해야 한다.

🧠 상세 정리

1. 미들마일 연구를 가로막는 데이터 부족

글은 네덜란드의 poffert가 450마일, 약 700km 떨어진 집에 다음 날 도착할 수 있는 배경으로 물류 최적화, 특히 미들마일의 역할을 제시한다. 미들마일은 운송 여정에서 가장 긴 거리를 담당하고 전체 비용의 큰 비중을 차지하며, 식품이 신선하게 도착하는지에도 영향을 준다. 그러나 기존 물류 연구는 생산자에서 초기 집결지로 이동하는 퍼스트마일과 소비자에게 배송하는 라스트마일에 집중했고, 지역·대륙 규모의 물류센터 간 대량 운송은 상대적으로 관심을 덜 받았다. 물류 기업이 네트워크 구조와 수요량을 민감한 독점 정보로 취급하기 때문에 고품질 공개 데이터가 부족하다는 점이 학술적 진전을 막는 핵심 요인으로 설명된다. 적용 분야는 전자상거래와 도심 소매점 공급, 자동차 생산·정비용 부품 이동, 보관 시설과 병원 사이의 온도 관리 의약품 운송까지 폭넓다.

2. 단일 차량 배송에서 여러 차량의 연결로

퍼스트마일과 라스트마일에서는 개별 화물이 출발지에서 목적지까지 하나의 차량에 실려 이동하며, 보통 하루 정도의 제한된 시간 범위에서 여러 차량을 최적화한다. 따라서 주요 과제는 어떤 차량에 어떤 화물을 배정하고 어느 순서로 지점을 방문하게 할지 결정하는 것이다. 반면 미들마일은 여러 차량이 화물을 이어 나르는 릴레이에 가깝고, 대륙 규모의 네트워크를 통과하는 데 일주일이 걸릴 수도 있다. 중간 물류센터에서는 화물을 내리고 목적지별로 분류한 뒤 다른 화물과 합쳐 다음 차량에 싣기 때문에 차량 간 연결 시점을 맞추는 일이 중요해진다. 예정된 출발 차량에 실리려면 특정 시간 구간 안에 센터에 도착해야 하며, 연결을 놓치면 다음 운행 주기까지 기다려 상당한 지연이 발생할 수 있다.

3. 네덜란드에서 프랑스로 이동하는 화물의 예

원문은 Groningen의 제조업체에서 Versailles의 소비자에게 상품을 보내는 사례로 물류 단계와 환적 과정을 구체화한다. 상품은 먼저 Utrecht의 지역 물류센터로 이동하고, 미들마일을 통해 Paris의 물류센터에 도착한 다음 소비자에게 최종 배송된다. 상세 예시에서는 Utrecht에서 Antwerp행 첫 트럭에 실려 당일 도착하지만, 가장 빠른 Paris행 트럭은 이미 가득 차 있고 소비자는 일반 배송을 선택했다고 가정한다. 이에 따라 화물은 다음 날 Antwerp에서 Paris로 출발하는 두 번째 트럭을 이용하며, 둘째 날 밤에 Paris에 도착해 다음 날 라스트마일 배송으로 이어진다. 이 사례는 최종 도착 시점이 거리뿐 아니라 연결 차량의 적재 여유와 출발 일정, 선택한 배송 방식에도 좌우된다는 점을 보여준다.

4. 시공간 그래프와 완화하기 어려운 운영 제약

OR-Tools나 Google Maps Platform Route Optimization(GMPRO) 같은 도구가 다루는 전통적인 차량 경로 문제(VRP)는 일반적으로 차량별 운행 경로와 방문 순서를 최적화해 고객의 촉박한 기한을 맞추는 데 초점을 둔다. 원문은 미들마일의 차량 간 화물 이동을 추가 차원으로 보고, 이를 시공간 그래프 위의 다중 상품 흐름 문제로 모델링한다. 노드는 특정 시간 구간의 특정 물류센터를 나타내며, 아크는 시간에 따른 차량 이동이나 센터에서의 화물 보관·목적지별 분류를 나타낸다. 고정 차량 시간표, 시간당 분류·크로스도킹 처리량의 물리적 한계, 한 차량의 도착이 다른 차량에 실릴 화물의 출발 전제가 되는 동기화 조건은 문제의 구조를 왜곡하지 않고 완화하기 어렵다. 저자들은 이러한 의존성 때문에 기존 VRP 솔버를 미들마일에 그대로 적용할 수 없으며, 여러 날에 걸친 중간 센터의 경유 순서와 복수 차량 배정을 함께 처리해야 한다고 설명한다.

5. 현실성을 반영하는 합성 네트워크 생성

논문 「A Novel Instance Generator for Simulating Middle-Mile Logistics Networks」에서 소개한 MilleMiglia는 미들마일 배송 문제에 현실적인 벤치마크를 제공하려는 C++ 인스턴스 생성기다. 물류센터의 위치는 중력 모형이나 공간 군집화를 이용해 실제 인구 밀도와 산업 밀도를 반영하도록 배치한다. 화물은 출발지·도착지 쌍과 함께 생성되며, 부피와 중량도 현실적인 분포를 따르도록 구성한다. 차량 운행은 노드 사이를 임의로 연결하는 대신 주요 물류센터 두 곳을 잇거나 주요 센터와 주변의 소규모 센터를 연결하는 구조화된 일정으로 만든다. 이러한 통계적 분포는 산업계의 공개 정보와 비공개로 제공된 데이터 사이를 보간하며, 실제 네트워크와 닮은 합성 데이터를 만들면서 개별 비공개 정보를 드러내지 않는 것이 설계 목적이다.

6. 하나의 파일에 담는 데이터와 제약

MilleMiglia는 C++로 작성됐으며 Protocol Buffers를 사용해 다양한 인스턴스 데이터를 직렬화하고 인스턴스마다 하나의 파일에 저장한다. 원문은 이 방식으로 생성된 인스턴스가 간결한 크기를 유지하며, 서로 다른 프로그래밍 언어로 작성한 솔버에서도 쉽게 사용할 수 있다고 설명한다. 전통적인 VRP에는 용량을 다루는 CVRP, 시간 창을 다루는 VRPTW, 시간 창이 있는 픽업·배송을 다루는 PDPTW처럼 운영 요구를 구분하는 여러 변형이 있다. 이에 비해 제안된 미들마일 데이터 형식은 고정 차량 일정, 물류센터 처리량 한계, 복잡한 동기화 전제조건을 동일한 파일 형식의 기본 요소로 포함한다. 이는 해당 제약들을 개별적인 부가 조건으로 취급하기보다 미들마일 운영 문제를 구성하는 본질적인 구조로 표현하려는 접근이다.

7. 정확 알고리즘부터 산업 규모와 ML 학습까지

MilleMiglia가 제공하려는 인스턴스 범위는 학술적인 소규모 예제부터 대륙 전체를 다루는 산업 규모의 대형 문제까지 이어진다. 작은 인스턴스는 정확 알고리즘을 시험하는 용도로 사용하며, 큰 산업 인스턴스에서는 좋은 해를 찾기 위해 고급 휴리스틱이나 메타휴리스틱이 필요하다고 설명한다. 두 극단 사이에서도 크기나 난도가 중간 수준인 문제를 생성할 수 있어 연구 목적에 맞는 다양한 조건을 구성할 수 있다. 또한 방대한 데이터 세트를 만들어 ML 알고리즘을 학습시키는 시나리오도 지원한다. 원문이 제시하는 성과는 이러한 연구용 문제를 생성할 수 있는 기반이며, 특정 솔버의 성능 향상 수치나 실제 물류비 절감 결과가 제시된 것은 아니다.

8. 공동 연구와 전용 솔버의 향후 방향

저자들은 MilleMiglia를 VRP 연구 커뮤니티의 CVRPLIB와 유사한 미들마일 표준 벤치마크 체계를 구축하기 위한 첫 단계로 규정한다. 이 프로젝트는 Google과 UniBrescia, ENPC Paris의 지속적인 협력에서 나왔으며, 연구는 주로 Google의 Student Researcher였던 Aymane Lotfi와 현재 ENPC Paris에 있는 Matteo Petris가 수행했다. 인스턴스 생성 외에도 미들마일 흐름의 고유한 구조를 활용하는 전용 솔버와 API를 개발 중이라고 밝히지만, 완성이나 공개가 이뤄졌다고 주장하지는 않는다. 생성기의 소스 코드와 문서는 GitHub에 공개돼 있고, 관심 있는 연구자는 저장소에 있는 예제 인스턴스부터 살펴볼 수 있다. 저자들은 향후 미들마일 문제 챌린지를 열어 학계와 산업계 솔버 개발자의 관심을 높이고, 궁극적으로 더 견고하고 효율적인 글로벌 공급망에 기여하기를 희망한다.

🧾 핵심 주장 / 시사점

• 미들마일의 핵심 난점은 장거리 운송 자체뿐 아니라 여러 차량의 일정과 물류센터 처리 능력이 서로 의존한다는 데 있다.
• 현실적인 합성 데이터는 기업의 민감한 정보를 보호하면서도 공개 데이터 부족으로 막혀 있던 연구를 진행할 수 있게 하는 기반으로 제시된다.
• MilleMiglia의 현재 가치는 다양한 규모의 연구 문제를 생성하는 데 있으며, 전용 솔버의 실효성과 공급망 개선 효과는 향후 검증할 영역이다.

✅ 액션 아이템

• 미들마일 모델링에서 고정 차량 시간표·물류센터 처리량 한계·환적 동기화를 함께 반영할 필요성 검토.
• MilleMiglia의 소규모·대륙 규모 인스턴스를 정확 알고리즘·휴리스틱·메타휴리스틱 연구 목적에 맞춰 활용하는 방안 검토.
• MilleMiglia 생성기의 활용 가능성과 개발 중인 전용 솔버·API의 완성 여부를 구분해 평가.

❓ 열린 질문

• MilleMiglia의 합성 분포는 실제 미들마일 네트워크의 공간 분포와 화물 부피·중량을 어느 정도 충실하게 재현하는가?
• 고정 차량 시간표·물류센터 처리량 한계·환적 동기화가 함께 적용될 때 대륙 규모 문제에서 좋은 해를 찾는 데 가장 큰 제약은 무엇인가?
• 개발 중인 미들마일 전용 솔버와 API는 언제 어떤 범위로 제공될 예정인가?