물류 운영 제약을 고려한 HIDO-VRP : 사전식 재군집화와 형상 제약 기반 차량경로 최적화

2.1 군집 기반 차량경로 탐색

차량경로문제(VRP)는 Dantzig와 Ramser가 제시한 트럭 배차 문제에서 출발하였다[1]. 이후 차량 용량, 시간창, 이종 차량 및 수거·배송 조건을 포함하는 다양한 형태로 확장되었다. 최근 VRP 연구는 고전적인 구성 휴리스틱에서 하이브리드 메타휴리스틱, 동적 경로계획 및 학습 기반 탐색으로 범위를 넓히고 있다[2]. VRP는 대표적인 NP-hard 문제이므로 문제 규모가 증가할수록 제한된 시간 안에 최적해를 구하기 어렵다. 이에 따라 실제 적용에서는 계산시간과 해 품질을 함께 고려한 휴리스틱 및 메타휴리스틱이 널리 사용된다.

대표적인 초기 휴리스틱으로는 Clarke와 Wright[3]의 savings 알고리즘, Gillett과 Miller[4]의 Sweep 알고리즘, Fisher와 Jaikumar[5]의 일반화 할당 기반 휴리스틱이 있다. 이들 방법은 고객을 차량별 군집으로 나눈 뒤 각 군집의 방문 순서를 결정하는 군집화 우선–경로 생성 후속(CFRS) 방식으로 볼 수 있다. CFRS는 전체 문제를 여러 부분문제로 분할하여 계산량을 줄일 수 있다는 장점이 있다.

반면 초기 군집화에서 결정된 고객 배정이 후속 경로 최적화 단계에서도 그대로 유지되면 차량별 부하 불균형이나 필요 차량 수의 과다 산정이 발생할 수 있다. 특히 고객의 좌표나 직선거리만을 기준으로 군집을 구성하면 실제 도로망 이동시간, 작업시간, 휴게시간 및 지역별 우회 특성이 충분히 반영되지 않을 수 있다. 본 연구는 초기 군집화 결과를 최종 배정으로 고정하지 않고, 실제 경로 평가 결과에 따라 차량 간 고객 배정을 다시 조정한다는 점에서 단순 CFRS 방식과 차이가 있다.

2.2 경로 개선을 위한 메타휴리스틱

차량별 방문 순서를 개선하기 위한 대표적인 방법으로는 2-Opt[6], Simulated Annealing[7], LNS(Large Neighborhood Search)[8]가 있다. 2-Opt는 경로를 구성하는 두 연결을 교환하여 불필요한 교차와 우회를 줄이는 국소 탐색 방법이다. Simulated Annealing은 탐색 과정에서 일정 확률로 현재 해보다 좋지 않은 해도 수용함으로써 지역 최적해에서 벗어나도록 한다.

LNS는 현재 해에서 일부 고객을 제거한 뒤 다시 삽입하여 비교적 넓은 해 공간을 탐색한다. Shaw는 제약 프로그래밍과 국소 탐색을 결합한 LNS를 차량경로문제에 적용하였다[8]. 이후 Ropke와 Pisinger는 여러 제거 및 삽입 연산자의 선택 확률을 탐색 과정에서 조정하는 ALNS(Adaptive Large Neighborhood Search)를 제안하였다[9]. 최근에는 ALNS의 연산자 선택, 수락 기준 및 종료 조건을 모듈화한 공개 구현도 제시되었다[10].

여러 탐색 방법을 결합한 하이브리드 메타휴리스틱도 차량경로문제에 널리 적용되고 있다. Vidal et al.[11]은 유전 탐색, 국소 개선 및 적응형 다양성 관리를 결합한 하이브리드 유전 알고리즘을 제안하였다. 이후 Vidal[12]은 CVRP에 특화된 공개 HGS 구현과 SWAP* 이웃 연산자를 제시하였다. 한편 LNS의 복구 연산 일부를 신경망으로 학습하는 Neural LNS도 제안되어 전통적인 메타휴리스틱과 학습 기반 탐색을 결합하려는 연구가 진행되고 있다[13].

Uchoa et al.[14]은 고객 수, 공간 분포 및 차량 용량 조건을 다양화한 대규모 CVRP 벤치마크를 제시하여 알고리즘의 확장성과 일반성을 평가할 수 있도록 하였다. 이러한 연구는 표준 CVRP에서 높은 해 품질을 확보하는 데 초점을 두지만, 실제 배송 환경에서는 근무시간, 휴게시간, 중량과 부피 및 반복 실행에 필요한 계산시간도 함께 고려해야 한다.

본 연구의 경로 최적화 단계에서는 Simulated Annealing, 2-Opt 및 LNS를 함께 사용한다. 이후 재군집화 단계에서는 차량 간 고객 이동과 군집 통합을 수행하며, 제약 위반 감소, 사용 차량 수 및 차량 간 부하 균형을 정해진 우선순위에 따라 평가한다.

2.3 실제 도로망과 운영 제약을 고려한 경로 최적화

표준 CVRP에서는 고객 간 이동비용을 좌표 기반의 유클리드 거리로 계산하는 경우가 많다. 그러나 실제 배송 환경에서는 도로 연결 구조, 일방통행, 우회 구간 및 진입 제한 등의 영향으로 직선거리와 실제 이동시간 사이에 차이가 발생한다. 따라서 고객 위치만을 이용해 생성한 군집이 실제 도로망에서는 비효율적인 경로로 이어질 수 있다.

OSRM(Open Source Routing Machine)은 OpenStreetMap 도로 데이터를 이용하여 실제 도로망상의 경로와 이동시간을 계산할 수 있는 경로 엔진이다[15]. 실제 이동시간을 사용하면 직선거리 기반 계산보다 현실적인 경로 평가가 가능하지만, 고객 쌍마다 경로 엔진을 반복 호출하면 문제 규모에 따라 실행시간과 질의 비용이 증가할 수 있다. 특히 국소 탐색이나 재군집화 과정에서는 동일한 노드 쌍의 이동시간이 여러 차례 사용되므로 이미 계산된 이동시간을 저장하고 재사용할 필요가 있다.

실제 배송 운영에서는 총 이동거리뿐 아니라 근무시간, 휴게시간, 물품의 중량과 부피, 사용 차량 수 및 경로 생성 응답시간을 함께 고려해야 한다. 본 연구는 초기 군집화 이후 실제 도로망 이동시간을 기준으로 경로를 다시 평가하고, 근무시간 위반이나 차량 간 부하 불균형이 발생한 경우 고객을 다른 차량으로 이동하거나 저활용 차량을 통합한다. 또한 고객 이동 과정에서 수신 군집의 공간적 분포와 지나치게 어긋나는 후보를 제한하기 위해 원형통계 기반 형상 제약을 적용한다.

국방 물류의 수송계획은 제한된 차량 자원과 운행시간 내에서 다수의 보급 지점에 물자를 전달해야 한다는 점에서 차량경로문제와 유사한 구조를 갖는다. 특히 군용 지상차량의 수송계획에서는 제한된 차량 수로 정해진 시간 안에 화물을 전달하기 위한 차량 규모 산정과 운행계획이 중요하게 다루어진다[16]. 또한 군수 공급망에서는 수요 발생 시점, 정비 일정, 수송시간과 같은 운영 조건을 함께 고려해야 하며, 이러한 조건을 통합한 수송계획은 일반적인 거리 최소화 문제보다 복잡한 형태를 갖는다[17]. 적대적이거나 불확실한 환경에서는 차량과 도로망의 가용 상태가 변할 수 있으므로, 초기 계획을 고정하기보다 운용 상황에 따라 경로와 공급계획을 조정할 수 있는 절차가 요구된다[18]. 따라서 국방 물류에 적용되는 차량경로 최적화는 거리뿐 아니라 차량 가용성, 시간 제약, 적재 한계 및 상황 변화에 대한 대응성을 함께 고려할 필요가 있다.

2.4 문제 정의 및 제약

기존 군집 기반 차량경로 연구는 계산량을 줄이는 데 효과적이지만, 초기 고객 배정이 후속 단계에서 고정되기 때문에 실제 도로망 이동시간을 반영한 이후 발생하는 근무시간 초과와 차량 간 부하 불균형을 조정하는 데 한계가 있다. 또한 표준 벤치마크 중심의 연구만으로는 휴게시간, 중량과 부피, 도로망 질의 비용 및 반복 실행시간과 같은 실제 운영 조건을 충분히 반영하기 어렵다. 따라서 초기 해를 실제 경로 기준으로 재평가하고, 제약 위반과 차량 수 과다 산정을 사후에 보정할 수 있는 경량화된 재군집화 절차가 요구된다. 이에 본 연구에서는 사전식 재군집화와 형상 제약을 결합한 HIDO-VRP 프레임워크를 제안하였다.

노드 집합을 V={0,1,⋯,n}라 정의하며, 노드 0은 물류센터(Depot), V\{0}는 배송지 집합을 나타낸다. 차량 집합을 K라 하고, 차량 k에 배정된 배송지 군집을 C_k로 정의한다. 각 배송지 i는 서비스 시간 s_i, 중량 수요 w_i, 부피 v_i를 갖는다. 각 차량에는 최대 근무시간 T_max, 최대 적재중량 W_max, 최대 적재부피인 V_max가 적용된다.

전체 HIDO-VRP의 처리 절차는 알고리즘 1과 같다. 알고리즘 1은 초기 군집화, 군집별 경로 최적화, 사전식 재군집화 및 최종 경로 생성으로 이어지는 전체 파이프라인을 나타낸다.

Algorithm 1.

① HIDO-VRP pipeline

본 연구에서는 계산 목적에 따라 두 종류의 이동시간을 구분하여 사용한다. 초기 군집화와 재배치 후보 평가에는 계산 비용이 낮은 직선거리 기반 추정치를 사용하고, 최종 경로 평가에는 OSRM으로 산출한 실제 도로망 이동시간을 적용한다. 이러한 이중 시간 모델은 반복적인 경로 탐색에서 계산 부담을 줄이기 위한 것이다. 다만 직선거리 기반 추정치와 실제 도로망 이동시간 사이의 차이로 인해 초기 군집화 결과가 최대 근무시간을 초과할 수 있으므로, 후속 재군집화 단계에서 차량 간 배송지 재배치를 수행한다.

차량 k에 할당된 군집 C_k는 적재중량과 적재부피에 관한 제약을 만족해야 하며, 초기 군집화 단계에서는 근사 이동시간과 서비스 시간을 이용하여 예상 작업시간을 산정한다. 이때 $$ {\widehat{t}}_i$$는 직선거리 기반 이동시간 추정치이며, α는 초기 군집화 단계에서 적용되는 완화 계수이다. 초기 단계에서 완화된 기준에 따라 배송지를 배정한 후, 실제 도로망 이동시간을 이용한 경로 평가와 재군집화를 통해 제약 위반을 보정한다.

식 (1)은 차량별 적재중량과 적재부피의 상한 제약을 나타내며, 식 (2)는 초기 군집화 단계에서 적용되는 완화된 작업시간 제약을 나타낸다.

3.1 HIDO-VRP 전체 구조

HIDO-VRP는 세 단계로 구성된다. Phase 1에서는 선택된 초기 군집화 전략에 따라 배송지를 차량 단위의 군집으로 분할한다. Phase 2에서는 각 군집에 대해 SA(Simulated Annealing), 2-Opt 및 LNS(Large Neighborhood Search)를 적용하여 차량별 방문 순서를 최적화한다. Phase 3에서는 전체 차량 경로를 재평가하고, 과부하 차량과 저활용 차량을 조정하며 통합 가능한 차량을 탐색한다. 이 과정에서 배송지 이동으로 구성이 변경된 군집에 대해서는 Phase 2의 경로 최적화를 다시 수행한 뒤 해를 재평가한다.

3.2 군집별 경로 최적화

군집 C_k에 대한 방문 순서를 π라 할 때, 경로 소요시간은 노드 간 실제 도로망 이동시간 $$ t_{ij}^{\text{real }}$$과 각 배송지의 서비스 시간을 합산하여 계산한다.

제약 위반은 소프트 페널티 방식으로 처리한다. 목적함수는 최종 경로 소요시간에 최대 근무시간, 적재중량 및 적재부피 초과에 따른 페널티를 추가하는 형태로 구성한다. 휴게시간은 누적 도착시각이 사전에 설정된 기준시각에 도달하면 1회 적용한다. 기본 휴게시간은 60분으로 설정하되, 해당 휴게시간을 적용할 경우 최대 근무시간을 초과하는 경로에는 20분의 단축 휴게를 적용한다. 목적함수에는 단축 휴게 사용에 대한 추가 페널티를 부여하여 가능한 경우 기본 휴게시간이 유지되도록 한다.

식 (3)은 실제 도로망 이동시간과 배송지별 서비스 시간을 합산하여 차량 경로의 총 소요시간을 산정한다. 식 (4)는 경로 소요시간에 최대 근무시간, 적재중량 및 적재부피 초과에 따른 페널티와 단축 휴게 사용에 대한 페널티를 반영한 목적함수를 나타낸다.

목적함수의 페널티 계수는 별도의 하이퍼파라미터 탐색을 통해 최적화한 값이 아니라, 제약 위반의 상대적 중요도를 반영하여 설정하였다. 최대 근무시간 위반은 실행 불가능 해를 발생시키는 주요 제약으로 판단하여 λ_T = 1000으로 설정하였으며, 적재중량 및 적재부피 위반에는 λ_W=λ_V=500을 적용하였다. 단축 휴게에 대한 페널티는 실행 가능성을 제한하는 제약보다 낮은 수준인 βq=50으로 설정하였다. 따라서 페널티 계수는 시간 제약, 적재 제약 및 단축 휴게의 순으로 상대적 중요도가 반영되도록 설정하였으며, 별도의 자동화된 파라미터 튜닝은 수행하지 않았다.

각 반복 단계에서는 2-Opt 구간 반전 또는 LNS의 파괴·복구 연산을 통해 이웃해를 생성한다. 생성된 이웃해는 Simulated Annealing의 확률적 수락 기준에 따라 채택하며, 이 과정을 반복하여 현재 해를 개선한다.

3.3 사전식 재군집화

사전식 재군집화 단계에서는 현재 해 S를 식 (5)의 요약 벡터Φ(S)로 나타낸다. 이 벡터는 제약 위반 차량 수, 시간·중량·부피 초과량, 사용 차량 수, 저활용 차량 수 및 차량별 운행시간 분포를 포함한다.

사전식 비교에서는 제약 위반 차량 수의 감소를 가장 우선적으로 고려한다. 이후 시간·중량·부피 초과량의 감소, 사용 차량 수의 감소, 저활용 차량 수의 감소, 차량 간 부하 균형의 개선 순으로 해의 우열을 판단한다. 이러한 우선순위는 차량 수가 적더라도 제약을 위반하는 해보다, 제약을 만족하는 운영 가능한 해를 우선한다는 실제 배송 운영 원칙을 반영한다.

사전식 재군집화의 세부 절차는 알고리즘 2와 같다. 과부하 차량에서 재배치 후보를 선별하여 저활용 차량으로 이동시키고, 필요한 경우 차량 통합과 영향 경로의 재최적화를 수행한다. 생성된 해는 식 (5)의 평가 벡터를 기준으로 비교하며, 사전식 우선순위가 개선되는 경우에만 현재 해를 갱신한다.

Algorithm 2.

② lexicographic reclustering

3.4 형상 제약 기반 안티스네이킹 필터

재군집화 과정에서 차량 간 부하 균형만을 기준으로 배송지를 이동하면, 수신 군집의 공간적 분포와 어긋나는 노드가 포함되어 경로가 과도하게 굴절되거나 불필요한 교차가 발생할 수 있다. 본 연구에서는 이러한 형상 왜곡을 줄이기 위해 후보 노드의 이동적합도를 평가하기 전에 형상 제약 기반 필터를 적용한다.

군집 C의 중심을 μ, 강건 반경을 σ라 하고, depot을 기준으로 계산한 방위각의 원형 평균과 표준편차를 각각 $$ \stackrel{-}{\theta }$$, σ_θ라 한다. 식 (6)은 강건 반경과 depot 기준 방위각을 정의하며, 식 (7)는 방위각의 원형 평균, 방향 집중도 및 원형 표준편차를 산정한다. 후보 노드 u는 식 (8)의 반경, 각도 및 근접 조건을 모두 만족하는 경우에만 재배치 후보로 유지한다. 식 (9)는 방향 집중도에 따라 적응형 각도 임계값 ϕ_adapt를 결정한다. σ_θ가 작을수록 허용 각도가 좁아져 보다 엄격한 후보 선별이 이루어진다. 세 조건 중 하나라도 만족하지 못하면 해당 후보를 제외하며, 모든 조건을 통과한 후보에는 동일 점수 후보의 우선순위 결정을 위해 연속형 페널티 P_snake를 적용한다. 식 (10)는 형상 제약을 통과한 후보의 공간적 편차를 반영하기 위한 연속형 페널티를 나타낸다.

이상의 형상 제약을 이용한 후보 노드의 판정 절차는 알고리즘 3과 같다. 알고리즘 3에서는 수신 군집의 중심, 강건 반경 및 방위각 통계를 계산한 후 반경, 각도 및 근접 조건을 순차적으로 검사하여 후보 노드의 수용 여부와 P_snake를 결정한다.

여기서 μ는 군집 중심, σ는 이상치에 둔감한 강건 반경(중심으로부터 거리의 상위 80% 분위수)이다. R은 방향 집중도로 1에 가까울수록 방위각이 한 방향에 모여 있음을 의미하며, σ_θ는 이에 대응하는 원형 표준편차이다. ϕ_adapt는 방향이 집중될수록 좁아지는 적응형 각도 임계값이다. ρ_max와 ϕ_max는 각각 반경과 각도의 허용 상한이고, ρ와 a는 정규화된 반경 및 각도 편차이며, P_snake는 편차가 클수록 커지는 벌점이다.

Algorithm 3.

③ anti-snaking candidate gate

3.5 이동시간 행렬 캐시

도로망 기반 이동시간은 OSRM Table API를 이용하여 계산한다. 동일하거나 유사한 인스턴스를 반복 처리하는 운영 환경에서는 동일한 노드 쌍의 이동시간이 여러 차례 요청될 수 있다. 이에 따라 본 연구에서는 이미 계산된 노드 간 이동시간을 저장하고 재사용하는 전역 이동시간 캐시를 적용한다.

캐시에 해당 노드 쌍의 값이 존재하면 별도의 경로 엔진 호출 없이 저장된 이동시간을 사용한다. 값이 존재하지 않는 경우에만 OSRM에 질의하고, 반환된 결과를 캐시에 저장한다. 캐시 적용 효과는 적용 및 미적용 조건의 실행시간을 비교하여 평가하였다.

4.1 실험 설계

실험은 일곱 가지 항목으로 구성하였다. 첫째, 실제 배송 운영 데이터베이스의 4개 인스턴스를 대상으로 Phase 3 적용 여부에 따른 해의 변화를 비교하였다. 둘째, 동일한 입력 및 제약조건에서 FSM과 OR-Tools를 반복 실행하여 총 이동거리, 이동시간 및 실행시간을 정량적으로 비교하였다. 셋째, 사전식 우선순위 설정에 따른 영향을 분석하기 위해 LEXICOGRAPHIC, WEIGHTED_SUM_BALANCED 및 WEIGHTED_SUM_EFFICIENCY_FIRST의 세 가지 수용 규칙을 비교하였다. 넷째, 안티스네이킹 필터의 적용 여부가 경로 자기교차 수와 볼록껍질 비율에 미치는 영향을 분석하고, Welch의 t-검정을 통해 차이의 통계적 유의성을 검토하였다. 다섯째, CVRPLIB Augerat Set A/B의 6개 표준 인스턴스를 이용하여 알려진 최선해(BKS, Best Known Solution) 대비 gap을 측정하였다. 여섯째, 이동시간 캐시의 적용 여부에 따른 실행시간 변화를 비교하였다. 일곱째, 고객 수 (n)과 초기 군집 수 (k)의 변화에 따른 실행시간을 측정하여 확장성을 분석하였다.

앞서 3.4절에서 설명한 안티스네이킹 후보 판정 절차는 알고리즘 3과 같이 구현하였다.

제안 방법의 재현성을 확보하기 위해 실험에 사용한 주요 파라미터와 설정값은 표 1과 같다. 초기 군집화의 완화계수, 경로 평가 목적함수의 페널티 계수, 형상 제약 임계값, SA 및 LNS의 탐색 설정과 재군집화 최대 반복 횟수는 모든 실험에서 동일하게 적용하였다. 별도의 변경이 명시되지 않은 경우 표 1의 설정을 기본값으로 사용하였다.

Table 1.

Main parameter settings of HIDO-VRP (Based on the implementation)

4.2 해 품질 분석

4.2.1 Phase 3 효과

표 2는 Phase 3 적용 전후의 차량 수와 부하 불균형 계수(CV)를 비교한 결과이다. K-Means 전략에서는 세 인스턴스 모두 차량 수와 CV가 감소하였다. 특히 n=82 인스턴스에서는 차량 수가 6대에서 2대로 감소하였고, CV도 0.576에서 0.128로 낮아졌다.

Table 2.

Comparison with and without phase 3 on real-world delivery database instances

반면 일부 Centroid, Sweep 및 Basic-NN 조건에서는 Phase 3 적용 후 차량 수와 CV가 증가하였다. 로그 분석 결과, 해당 조건의 초기 해는 최대 근무시간 540분을 초과한 실행 불가능 해였으며, Phase 3는 차량을 추가하여 시간 제약을 만족하도록 해를 교정하였다. 따라서 Phase 3는 차량 수 감소뿐 아니라 초기 해의 제약 위반을 해소하는 사후 보정 단계로 기능한다.

4.2.2 FSM과 OR-Tools 반복 가능한 정량 비교

4절의 기존 기법과의 정량 비교는 실제 운영 대시보드 스냅샷 2건에 기반하였기 때문에 표준편차를 산출할 수 없고, 반복 실험으로 보기 어려운 한계가 존재하여 이를 보완하기 위해 본 연구에서는 FSM과 OR-Tools를 동일한 입력 조건에서 반복 비교하는 추가 실험을 수행하였다. 표 3은 동일한 입력 조건에서 FSM과 OR-Tools를 반복 실행하여 총 이동거리, 이동시간 및 실행시간을 비교한 결과이다.

Table 3.

Repeated quantitative comparison results between FSM and OR-Tools

4개 인스턴스 모두에서 FSM의 총 이동거리와 이동시간이 OR-Tools보다 짧게 나타났다. 거리 개선율은 7.27~21.20%, 시간 개선율은 0.50~1.86%였다. 실행시간은 depot 23, 26, 29에서 FSM이 더 짧았으나 depot 32에서는 OR-Tools가 더 짧게 나타났다.

4.2.3 사전식 우선순위 민감도 분석

사전식 우선순위 설정이 최종 해에 미치는 영향을 확인하기 위해 LEXICOGRAPHIC, WEIGHTED_SUM_BALANCED 및 WEIGHTED_SUM_EFFICIENCY_FIRST의 세 가지 수용 규칙을 적용하여 민감도 분석을 수행하였다. 표 4는 세 가지 수용 규칙의 우선순위 설정과 각 규칙에서 관찰된 해의 특성을 요약한 것이다.

Table 4.

Summary of scenario Interpretations

민감도 분석 결과, depot 23과 depot 26에서는 세 시나리오에서 동일한 해가 도출되어 판정 방식의 변화에 따른 영향이 나타나지 않았다.

반면 depot 32와 depot 29에서는 EFFICIENCY_FIRST 적용 시 결과가 달라졌다.

depot 32에서는 차량 수가 3대에서 2대로 감소하였으나 최대 운행시간이 585분으로 증가하여 근무시간 제한 540분을 45분 초과하였고, 제약 위반 차량도 1대 발생하였다.

depot 29에서는 차량 수가 5대로 유지되었으나 근무시간 초과 차량이 3대 발생하였으며, 운행시간 CV가 0.193에서 0.432로 증가하였다. 표 5는 세 가지 수용 규칙을 적용했을 때 인스턴스별 차량 수, 제약 위반 차량 수, 운행시간 CV 및 최대 운행시간의 변화를 비교한 결과이다.

Table 5.

Sensitivity analysis results of lexicographic priority and weighted-sum decision rules

WEIGHTED_SUM_BALANCED는 모든 인스턴스에서 LEXICOGRAPHIC과 동일한 결과를 보였다. 이는 가중합 방식 자체보다 각 평가 항목에 부여되는 가중치 설정이 최종 해의 실행 가능성에 영향을 줄 수 있음을 보여준다. 특히 차량 수 감소의 가중치가 높아질 경우 차량 수 또는 효율성 지표는 개선될 수 있으나, 근무시간 제약 위반이나 부하 불균형이 증가할 수 있다. 따라서 본 연구에서는 제약 위반 감소를 우선하는 사전식 평가 기준을 기본 수용 규칙으로 적용하였다.

다만 본 민감도 분석은 세 가지 수용 규칙과 네 개 인스턴스를 대상으로 수행되어 결과의 일반화에는 한계가 있다. WEIGHTED_SUM_BALANCED가 LEXICOGRAPHIC과 동일한 결과를 보인 것도 본 실험에서 적용한 가중치와 인스턴스 범위에서 확인된 결과이다. 보다 일반적인 경향을 확인하기 위해서는 다양한 인스턴스를 대상으로 연속적인 가중치 변화 실험을 수행할 필요가 있다.

4.2.4 형상제약 효과와 한계

표 6는 안티스네이킹 필터 적용 여부에 따른 자기교차 수와 Convex-Hull 비율을 비교한 결과이다. n=25 조건에서는 필터 적용 시 평균 자기교차 수가 감소하였으나, 다른 인스턴스에서는 개선 효과가 일관되게 나타나지 않았다.

Table 6.

Comparison with and without the anti-snaking filter

또한, 필터 적용 여부에 따른 자기교차 수의 차이를 검증하기 위해 각 인스턴스에 대해 Welch의 t-검정을 수행하였다. 표 7은 각 인스턴스의 반복 횟수와 안티스네이킹 필터 적용 여부에 따른 자기교차 수의 Welch t-검정 결과를 나타낸다.

Table 7.

Welch’s t-test results for the number of self-intersections with and without the anti-snaking filter

반복 횟수는 n=25,100,200,82에서 각각 20, 40, 50, 5회로 설정하였으며, 적용군과 미적용군에 동일하게 적용하였다. Welch의 양측 t-검정을 유의수준 α=0.05에서 수행한 결과, 모든 인스턴스에서 p>0.05로 나타나 자기교차 수의 차이는 통계적으로 유의하지 않았다.

따라서 형상 제약 필터는 자기교차 감소를 보장하는 기법이라기보다, 재군집화 과정에서 공간적으로 부자연스러운 후보 이동을 제한하는 보조적 필터로 해석하는 것이 적절하다. 소규모에서는 자기교차 감소 경향이 나타났으나, 중간 규모에서는 차이가 작았고 대규모·고밀도 조건에서는 성능 저하 가능성이 관찰되었다. 이는 군집의 강건 반경 σ와 방위각 원형표준편차 σ_θ에 따라 반경 및 각도 조건의 강도가 달라지기 때문으로 볼 수 있다.

이에 필터 적용 후 자기교차 수와 경로시간을 함께 확인하도록 표 8에 잠정적 운용 가이드라인을 제시하였다. 다만 통계적으로 유의한 차이가 확인되지 않았으므로, 해당 기준은 확정적 임계값으로 해석하지 않는다.

Table 8.

Practical guidelines for the anti-snaking filter

4.2.5 CVRPLIB 표준 벤치마크

CVRPLIB Augerat Set A/B의 6개 인스턴스를 대상으로 Centroid 전략의 성능을 평가하였다. 표 9에 제시한 바와 같이 평균 gap은 약 10.46%였으며, 6개 인스턴스 중 5개에서 BKS와 동일한 차량 수를 사용하였다. 이 결과는 실서비스 운영 제약을 고려하도록 구성된 제안 휴리스틱이 표준 CVRP의 알려진 최선해와 비교하여 어느 정도의 품질 차이를 갖는지 보여준다.

Table 9.

CVRPLIB benchmark results based on the centroid strategy

네 가지 초기 군집화 전략을 비교한 결과, Centroid의 평균 gap이 가장 낮았고, Basic-NN, Sweep, K-Means 순으로 나타났다. K-Means는 Phase 3를 적용하지 않은 경우 모든 인스턴스에서 BKS보다 많은 차량을 사용하였다. 반면 Phase 3 적용 후 평균 gap이 27.07%에서 20.45%로 감소하였다. 이는 Phase 3가 K-Means 초기 군집화에서 발생한 차량 수 과다 산정을 사후에 조정했음을 의미한다. 표 10은 네 가지 초기 군집화 전략에 대해 Phase 3 적용 전후의 평균 gap과 개선 폭을 비교한 결과이다.

Table 10.

Comparison of CVRPLIB strategies and phase 3

4.3 실행 성능 분석

4.3.2 이동시간 캐시의 효과

표 11는 이동시간 캐시 적용 여부에 따른 평균 실행시간을 비교한 결과이다. n=100 인스턴스에서는 캐시 적용 시 실행시간이 약 16% 감소하였으며, n=1000에서는 약 43% 감소하였다. 대규모 인스턴스에서는 반복당 캐시 적중 수가 11만~23만 건으로 나타났다. 이는 반복적인 도로망 이동시간 조회가 발생하는 환경에서 캐시가 실행시간 단축에 효과적임을 보여준다.

Table 11.

Effect of the travel-time cache with and without caching

4.4 종합 논의

실험 결과를 종합하면, HIDO-VRP의 주된 목적은 전역 최적해를 보장하는 데 있지 않고, 제한된 실행시간 내에서 배송 운영 제약을 만족하는 해를 생성하고 초기 해의 결함을 보정하는 데 있다. 사전식 재군집화는 K-Means에서 발생한 차량 수 과다 산정을 완화하였으며, 일부 Centroid, Sweep 및 Basic-NN 조건에서는 근무시간을 초과한 초기 해에 차량을 추가하여 실행 가능한 해로 변환하였다. 이는 차량 수 최소화보다 제약 만족을 우선하는 사전식 평가 기준이 실제 배송 운영의 요구와 부합함을 시사한다.

형상 제약 기반 안티스네이킹 필터의 효과는 인스턴스에 따라 다르게 나타났다. 소규모 조건에서는 자기교차 수가 감소하였으나, 중·대규모 조건에서는 일관된 개선이 확인되지 않았다. 따라서 해당 필터를 보편적인 해 품질 개선 기법으로 보기보다는, 재군집화 후보의 지리적 적합성을 평가하는 보조 장치로 해석하는 것이 적절하다.

실행 성능 측면에서는 이동시간 캐시와 군집별 병렬 처리가 반복 실행시간을 단축하는 데 기여하였다. 대규모 인스턴스에서 이동시간 캐시는 반복적인 도로망 질의를 줄였으며, 병렬 실행은 순차 실행보다 짧은 처리시간을 보였다. 반면 시간 제한을 증가시켜도 CVRPLIB의 BKS 대비 gap이 거의 변하지 않았다는 점은, 해당 gap이 시간 예산보다 초기 군집화와 경로 개선 구조의 영향을 크게 받았음을 시사한다.

OR-Tools 비교는 표본 수와 반복 실험 횟수가 제한적이므로 일반적인 성능 우월성을 주장하는 근거로 사용하기 어렵다. 또한 실제 배송 인스턴스와 표준 벤치마크의 수가 제한적이라는 점도 본 연구의 한계이다. 따라서 제안 방법의 일반성을 확인하기 위해서는 다양한 공간 분포와 운영 조건을 포함하는 추가 실험이 필요하다.