💻 computer science

A Metaheuristic Solution for the Capacitated Vehicle Routing Problem: Empirical Evaluation of Flexible Capacity Constraints via Ant Colony Optimisation

본 연구는 유연한 용량 제약을 결합한 개미 군집 최적화 방식이 실제 콜롬비아 인바운드 물류 네트워크에서 지리적 클러스터링 기준 모델을 크게 상회하며, 차량 이용률을 극대화하는 동시에 차량 대수, 이동 거리 및 운영 비용을 상당 부분 절감함을 입증한다.

원저자: Joseph Javier Sánchez Acuña

게시일 2026-06-29

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Joseph Javier Sánchez Acuña

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신은 콜롬비아의 한 물류 회사 매니저라고 상상해 보십시오. 당신은 '과달라하라 데 부가(Guadalajara de Buga)'라는 마을에 중앙 창고를 두고 있으며, 해안 항구부터 산악 마을까지 전국 각지에 흩어져 있는 30개의 서로 다른 지점에서 화물을 수거해야 합니다. 당신에게는 10대의 동일한 트럭이 있으며, 각 트럭의 공식 적재 용량은 150개의 화물입니다.

하지만 당신의 회사는 스마트한 규칙을 가지고 있습니다. 만약 계산이 완벽하게 맞아떨어진다면, 트럭이 법을 어기거나 차량에 무리를 주지 않는 선에서 최대 5%(약 157개)의 화물을 더 실을 수 있는 '유연한 용량(flexible capacity)'을 허용한다는 것입니다.

문제는 현재 사용 중인 경로 계획 시스템인 '라우트 나우(Rout Now)'가 다소 경직되어 있다는 점입니다. 이 시스템은 마치 교실에서 서로 가까이 앉은 학생들을 기준으로 그룹을 나누는 선생님처럼 작동합니다(직선 거리 지도 기준). 일단 그룹이 형성되면, 그 그룹을 수거하기 위해 트럭을 보냅니다. 하지만 이 시스템은 실제 도로가 아닌 '직선 거리'를 기준으로 그룹을 묶기 때문에, 어떤 트럭은 절반이나 비어 있고 어떤 트럭은 과적되는 일이 빈번히 발생하며, 이로 인해 실제로는 8대만 있어도 될 상황임에도 불구하고 10대의 트 l럭을 모두 사용하게 만듭니다.

새로운 솔루션: "개미 군집" 방식

저자인 조셉 하비에르 산체스 아쿠냐(Joseph Javier Sánchez Acuña)는 개미가 먹이를 찾는 방식에서 영감을 얻은 컴퓨터 프로그램인 **개미 군집 최적화(Ant Colony Optimisation, ACO)**를 사용하여 경로를 계획하는 더 스마트한 방법을 테스트했습니다.

논문은 이 차이점을 다음과 같이 쉬운 개념을 사용하여 설명합니다.

1. "직선" 대 "실제 도로"

기존 방식 (Rout Now): 종이 위에 직선을 그려서 로드트립을 계획하는 것과 같습니다. 지도를 보면 두 마을이 옆에 있기 때문에 가깝다고 생각할 수 있습니다. 하지만 실제로 그 사이를 이동하려면 거대한 산을 넘거나 긴 우회로를 지나야 할 수도 있습니다. 기존 시스템은 실제 도로를 무시하고 평면 지도상의 위치만을 기준으로 지점들을 그룹화합니다.
새로운 방식 (개미): 새로운 시스템은 실제 도로 네트워크(OpenStreetMap이라는 디지털 지도 사용)를 살펴봅니다. 이 시스템은 지도상에서 "가까운" 마을이 실제 도로로는 도달하기 가장 어려운 곳일 수 있다는 점을 알고 있습니다.

2. "짐 싸기" 비유

기존 방식: 기존 시스템은 가장 가까운 이웃을 먼저 집어 드는 방식으로 트럭을 채우려 합니다. 이는 가방의 모양을 고려하지 않고 가장 가까운 물건들을 가방에 던져 넣는 것과 같습니다. 결국 빈 공간이 생기고 공간이 낭비되어, 첫 번째 가방에 여유 공간이 있음에도 불구하고 두 번째 가방(두 번째 트럭)을 열게 만듭니다.
새로운 방식: 개미 알고리즘은 숙련된 짐 싸기 전문가와 같습니다. 단순히 가장 가까운 것을 집는 것이 아니라, 가방 전체를 봅니다. "여기에 무거운 상자를 넣으면, 저기에 가벼운 상자를 여전히 넣을 수 있을까?"라고 자문합니다. 또한 '유연한 용량'(5%의 추가 공간)을 매우 정교하게 사용합니다. 이 시스템은 경로를 하나씩 구축하면서 트럭이 너무 꽉 차고 있지는 않은지 끊임없이 확인합니다. 만약 트럭이 거의 다 찼지만 한 번의 정거지를 더 수행할 수 있는 충분한 공간이 있다면, 개미는 그 정거지를 선택합니다. 그렇지 않다면 그 트럭을 닫고 새로운 트럭을 시작합니다.

3. 결과: 더 효율적인 적재

저자는 이 새로운 시스템을 실제 데이터가 담긴 10개의 바쁜 날을 대상으로 기존 방식과 비교 실험했습니다. 특히 가장 바빴던 날(시나리오 S-3)의 결과는 다음과 같았습니다.

트럭 감소: 기존 시스템은 10대의 트럭을 사용했습니다. 새로운 개미 시스템은 8대의 트럭만 필요했습니다. 이는 필요한 차량 대수가 20% 감소했음을 의미합니다.
주행 거리 감소: 트럭들이 20% 적게 주행했습니다(약 2,232km 절감).
비용 절감: 주행 거리가 줄고 사용하는 트럭 수가 적어졌기 때문에 연료비가 16% 감소했습니다.
더 꽉 찬 트럭: 기존 시스템은 트럭을 약 79%의 용량으로 운행하여 빈 공간이 많았습니다. 반면 새 시스템은 **99.5%**까지 채워, 트럭의 거의 모든 공간을 알뜰하게 사용했습니다.

4. 왜 성공했는가 (비결)

논문은 새로운 시스템이 단순히 일반적인 의미에서 "더 똑똑해서"가 아니라고 주장합니다. 핵심은 유연한 용량(5%의 추가 공간)을 조율된 방식으로 사용할 수 있었다는 점입니다.

기존 시스템은 경로를 계획하기도 전에 지리적 그룹을 먼저 확정해 버리기 때문에 이를 수행할 수 없었습니다. 그것은 마치 벽지를 다 칠한 후에 방 안의 가구를 재배치하려는 것과 같습니다. 그룹이 고정되어 있었던 것입니다. 반면, 개미 시스템은 경로와 그룹을 동시에 구축했습니다. 이 시스템은 "이 트럭은 가득 찼지만, 5%의 여유 공간을 활용해 이 정거지를 하나 더 끼워 넣는다면 트레일러 한 대를 통째로 아낄 수 있다"라고 판단할 수 있었습니다.

결론

이 연구는 굴곡진 도로(콜롬비아의 산악 지형과 같은)가 있는 지역의 물류 회사에서, 실제 도로 거리를 존중하고 유연한 적재 규칙을 사용하는 생체 모사 컴퓨터 프로그램(개미 군집 최적화)을 사용하는 것이 직선 거리 기반의 기존 방식보다 훨씬 더 효과적임을 입증합니다.

저자는 이것이 단순히 운이 좋았던 것이 아니라, 새로운 방식이 시나리오당 20번씩 테스트되었으며 통계적으로 유의미한 결과임을 확인했다고 결론짓습니다. 새로운 방식은 "가방"(트럭)을 더 지능적으로 챙김으로써 돈과 연료를 아끼고 필요한 트럭의 수를 줄여줍니다.

기술 요약: 용량 제한 차량 경로 문제(CVRP)를 위한 메타휴리스틱 솔루션

1. 문제 정의 및 배경
본 연구는 콜롬비아의 원자재 수집 운영에서 발생하는 실제 용량 제한 차량 경로 문제(CVACRP)를 다룬다. 물류 네트워크는 과달라하라 데 부가(Guadalajara de Buga, Valle del Cauca)에 위치한 중앙 데포를 중심으로 하며, 콜롬비아의 다양한 지역(해안, 안데스 고산 지대, 산업 지대)에 위치한 30개의 유통 센터를 대상으로 한다. 운영 체계는 가변적인 수요 주기(주기당 643~1,192개 패키지)를 가지며, 10대의 동일한 규격의 Foton FRR Cummins 트럭 함대를 활용한다.

핵심적인 운영 제약 조건은 유연한 용량 정책이다. 명목 차량 용량은 $Q = 150$ 패키지이지만, 기업 정책에 따라 통제된 5%의 과적을 허용하여, 유효 계획 용량을 $Q_{eff} = 157.5$ 패키지로 설정하였다. 경로는 OpenStreetMap(OSMNx를 통해 추출) 기반의 비유클리드 도로 네트워크 상에서 수행되어야 한다. 이러한 지형적 복잡성(산악 회랑, 일방통행 도로 등)은 유클리드 거리와 실제 이동 비용 사이의 상당한 비대칭성을 유발한다.

기존의 계획 시스템인 "Rout Now"는 "클러스터 우선, 경로 생성 후순위(cluster-first, route-second)" 구조를 채택하고 있다. 이 방식은 k-means(평면 좌표 기준)를 사용하여 노드들을 10개의 지리적 클러스터로 분할한 뒤, 각 클러스터를 독립적으로 시뮬레이티드 어닐링(SA)을 통해 순차적으로 구성한다. 이 접근 방식은 이질적인 함대 활용률(35%~~90%)을 초래하며, 이론적 하한선이 6~~8대의 차량만으로도 충분함을 시사함에도 불구하고 항상 10대의 차량을 모두 투입하는 결과를 낳는다.

2. 방법론
본 연구는 사전 지리적 분할 없이 활성 노드의 완전 그래프(complete graph) 상에서 작동하도록 설계된 개미 군집 최적화(Ant Colony Optimisation, ACO) 메타휴직을 제안하고 평가한다.

수학적 정식화: 문제는 서브투어 제거를 위한 Miller–Tucker–Zemlin(MTZ) 정식화를 사용하는 혼합 정수 선형 계획법(MILP)으로 모델링된다. 용량 제약은 과적 정책을 최적화 로직 내에 반영하기 위해 $Q_{eff} = 157.5$ 로 명시적으로 완화되었다.
ACO 구조:
- 구성(Construction): 개미들은 반복적으로 다중 차량 경로를 구축한다. 핵심 차별점은 **동적 마스킹 메커즘(dynamic masking mechanism)**이다. 가능한 다음 노드 집합( $F_k$ )은 누적 부하가 $Q_{eff}$ 를 초 exceed하지 않도록 실시간으로 필터링된다. 이를 통해 알고리즘은 새로운 경로를 여는 것을 방지하기 위해 필요한 경우에만 5%의 여유분을 활용하여 노드를 효율적으로 "패킹(packing)"할 수 있다.
- 전이 확률(Transition Probability): 노드 선택 확률은 페로몬 흔적( $\tau$ )과 휴리스틱 가시성( $\eta = 1/C_{ij}$ )에 따라 결정된다. 콜롬비아 도로 비용의 높은 변동성(평균 대비 표준 편차 47%)을 고려하여, 휴리스틱 가중치( $\beta = 2.0$ )가 페로몬 가중치( $\alpha = 1.0$ )보다 우세하도록 조정하여 즉각적인 비용 효율성을 우선시하도록 했다.
- 업데이트 메커니즘: 표준적인 증발 및 퇴적 규칙이 적용되어, 저비용 및 고밀집 솔루션에 기여하는 아크(arc)를 강화한다.
실험 설계:
- 시나리오: 실제 기업 데이터를 추출하여 한 달간의 계획 주기를 나타내는 10개의 뚜렷한 운영 시나리오(S-1 ~ S-10)를 도출했다.
- 반복 수행: 통계적 변동성을 격리하기 위해 각 시나리오를 서로 다른 난수 시드로 20회 독립적으로 실행했다.
- 베이스라인 비교: 내부 타당성을 보장하기 위해 동일한 OSMnx 거리 행렬을 사용하여 기존의 "Rout Now"(k-means + SA) 베이스라인과 ACO 결과를 비교했다.
- 통계적 검증: 시나리오당 20회 실행된 평균 총 거리에 대해 비모수 검정인 윌콕슨 부호 순위 검정(Wilcoxon signed-rank test)을 적용하여 통계적 유의성을 테스트했다.

3. 주요 결과
ACO 방식은 10개 시나리오 모두에서 베이스라인 대비 체계적이고 통계적으로 유의미한 개선을 입증했다:

함대 감소: 최고 수요 시나리오(S-3; 1,192 패키지)에서 ACO는 활성 함대를 베이스라인의 10대에서 이론적 하한선( $\lceil 1192/157.5 \rceil = 8$ )과 일치하는 8대로 줄였다. 모든 시나리오에서 활성 함대는 약 20% 감소했다.
거리 및 비용:
- 총 거리: 평균 20.05% 감소했다(범위: 19.97% ~ 20.25%). S-3의 경우, 거리가 11,023 km에서 8,790.5 km로 감소했다.
- 연료 비용: 핵심 시나리오에서 약 16.05%의 절감 효과를 보였다(주기당 약 941,340 COP).
- 운영 시간: 20.02% 감소했다.
용량 활용도: ACO는 탁월한 밀집도를 달로, S-3에서 평균 용량 활용도를 베이스라인의 ~79.47%에서 **99.50%**로 높였다. ACO 솔루션의 경로는 명목 용량의 96%에서 101% 사이에서 작동했으며, 특정 경로는 아홉 번째 차량의 필요성을 방지하기 위해 5%의 과적 여유분을 전략적으로 활용했다.
통계적 유의성: 윌콕슨 부호 순위 검정 결과 $W=0$ (모든 차이가 ACO에 유리함) 및 p-value $< 0.01$ 을 기록하여, 중앙값 동일성에 대한 귀무가설을 기각하고 개선의 견고함을 확인했다.

4. 의의 및 기여
본 논문은 세 가지 주요 과학적 기여를 주장한다:

유연한 제약 조건의 경험적 평가: 유연한 용량 제약( $Q_{eff}$ )을 구성적 메타휴리스틱 내에 명시적으로 모델링함으로써, 사전 분할 아키텍처에서는 구조적으로 불가능한 협응된 부하 밀집이 어떻게 가능한지를 입증했다. 본 연구는 5%의 허용 오차가 단순한 안전 버퍼가 아니라, 함대 감소를 위한 전략적 레버로서 관리될 수 있음을 보여준다.
실제 지형에서의 견고성: 생체 모방 메타휴리스틱(특히 ACO)이 복잡한 비유클리드 도로 네트워크에서 고전적인 "클러스터 우선, 경로 생성 후순위" 휴리스틱보다 우수함을 입증했다. 본 연구는 지리적 사전 분할(k-means)이 도로 네트워크의 비대칭성을 반영하지 못하는 반면, ACO는 실제 비용 공간 상에서 작동한다는 점을 강조한다.
인과 기제 식별: 경로 구축 과정 중 불가능한 노드를 걸러내는 "동적 마스킹(dynamic masking)"을 성공의 인과 기제로 식별했다. 이를 통해 알고리즘은 수요의 "효율적 패킹"을 수행하며, 고정된 지리적 클러스터가 가진 한계를 넘어 유기적으로 과적 여유분을 활용하여 경로 수를 최소화할 수 있다.

5. 한계 및 향러 연구
저자들은 본 연구가 시간 창(Time Windows, VRPTW)이나 운전자 근무 시간 제약이 없는 특정 산업 맥락에 국한되어 있음을 밝힌다. 향-후 연구 방향으로 다음을 제안한다:

수령 일정 등을 포함하기 위한 VRPTW로의 모델 확장.
수요 불확실성을 다루기 위한 확률적 VRP(SVRP) 도입.
진화 알고리즘을 사용한 다목적 최적화(예: CO₂ 배출량 최소화) 개발.
기존 물류 시스템 내에서 통제된 A/B 테스트를 수행하기 위한 ACO 코어의 마이크로서비스 통합.

1. "직선" 대 "실제 도로"

2. "짐 싸기" 비유

3. 결과: 더 효율적인 적재

4. 왜 성공했는가 (비결)

결론

기술 요약: 용량 제한 차량 경로 문제(CVRP)를 위한 메타휴리스틱 솔루션

유사한 논문