💻 computer science

A Hybrid Quantum Classical Optimization Framework for Pickup and Delivery Problems with Parcel Lockers Using Quantum Graph Attention Networks

이 논문은 대규모 확률적 로커 포함 픽업 및 배송 문제(Pickup and Delivery Problems with Lockers)를 효율적으로 해결하기 위해 VQE, QAOA, 그리고 양자 그래프 어텐션 네트워크를 댄직-울프 분해 기법 내에 통합한 하이브리드 양자-고전 최적화 프레임워크인 Q-PDPL을 소개하며, 고전 알고리즘 대비 우수한 비용 절감 및 확장성을 입증한다.

원저자: Aqdas Shehzad, Zhao Dong Xu, Muhammad Aurangzeb, Wang Xiu-Xin, Muhammad Akbar, Tarek Salem Abdennaji, Aymen Flah

게시일 2026-08-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Aqdas Shehzad, Zhao Dong Xu, Muhammad Aurangzeb, Wang Xiu-Xin, Muhammad Akbar, Tarek Salem Abdennaji, Aymen Flah

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

매일 수백만 개의 택배가 도시를 가로질러 창고에서 집 앞까지 이동합니다. 이 마지막 여정인 '라스트 마일(last-mile)' 배송은 전체 과정에서 가장 비용이 많이 들고 비효율적인 부분인 경우가 많습니다. 트럭은 교통 체증에 갇히고, 운전자는 고객이 집에 있는지 찾는 데 어려움을 겪으며, 배송 실패는 연료와 시간의 낭비라는 악순환을 만듭니다. 이를 해결하기 위해 많은 기업이 사람들이 직접 택배를 찾아갈 수 있는 안전하고 자동화된 보관함인 '파셀 락커(parcel locker)'로 눈을 돌리고 있습니다. 이것이 단순해 보일 수 있지만, 락커로 향하는 트럭의 경로를 짜면서 동시에 각 가정으로의 배송도 함께 고려하는 것은 거대한 수학적 퍼즐입니다. 여기에는 차량 용량, 엄격한 시간 제한, 그리고 운전자가 도착했을 때 고객이 집에 없을 수도 있다는 예측 불가능한 사실 사이의 균형을 맞추는 작업이 포함됩니다. 전통적인 컴퓨터는 고객 수가 늘어날 때 이 퍼즐을 빠르게 해결하는 데 어려움을 겪으며, 종종 몇 시간 또는 며칠씩 걸리는 계산 과정에 빠지곤 합니다.

연구진은 고전 컴퓨터의 힘과 신흥 양자 기술을 결합하여 이 문제를 해결할 수 있는 새로운 방법을 제안했습니다. 그들은 하이브리드 접근 방식을 사용하여 배송 경로를 최적화하는 Q-PDPL이라는 시스템을 개발했습니다. 이 시스템은 단일 유형의 컴퓨터에 의존하는 대신 업무를 분담합니다. 고전 컴퓨터는 전반적인 계획을 관리하고, 양자 컴퓨터는 가장 어렵고 시간이 많이 걸리는 부분, 즉 특정 목적지들을 방문하는 단일 트럭의 가장 효율적인 경로를 찾는 문제를 해결합니다. 연구진은 수천 개의 배송 시나리오를 나타내는 시뮬레이션 데이터를 통해 이 시스템을 테스트했습니다. 결과에 따르면, 이 하이브리드 방식은 현재의 표준 방식보다 더 나은 경로를 더 빠르게 찾아낼 수 있으며, 이는 상당한 비용 절감과 배송 실패 횟수 감소로 이어질 수 있습니다.

연구진의 핵심 작업은 물류 분야의 특정 과제인 '락커를 포함한 픽업 및 배송 문제(Pickup and Delivery Problem with Lockers)'를 다룹니다. 이 시나리오에서 배송 회사는 각 고객에게 패키지를 집으로 직접 가져다줄지, 아니면 근처 락커로 보낼지를 결정해야 합니다. 이 결정은 고객이 락커에서 얼마나 떨어져 있는지, 고객이 집에 있을 가능성이 있는지, 락커가 얼마나 차 있는지 등 많은 요인에 따라 달라집니다. 만약 운전자가 집에 도착했는데 아무도 없다면 배송은 실패하며, 이는 회사에 비용을 발생시키고 고객을 불만스럽게 만듭러. 연구진은 이러한 결과를 예측하고 이를 피하도록 경로를 계획하는 모델을 구축했습니다. 그들은 양자 알고리즘을 사용하여 경로 최적화 하위 문제를 해결함으로써, 전통적인 방식으로는 허용되지 않는 훨씬 더 큰 규모의 고객 네트워크를 처리할 수 있음을 발견했습니다.

이를 달 수 있도록 팀은 여러 고급 기술을 통합했습니다. 그들은 거대한 배송 문제를 작고 관리 가능한 조각으로 나누는 '단치그-울프 분해법(Dantzig-Wolfe decomposition)'을 사용했습니다. 가장 어려운 부분인 '프라이싱 문제(pricing problem)'는 트럭이 갈 수 있는 모든 가능한 경로의 비용을 계산하여 최적의 경로를 찾는 과정을 포함합니다. 바로 이 지점에서 양자 컴퓨터가 투입됩니다. 연구진은 이 특정 문제를 해결하기 위해 변분 양자 고유값 솔버(Variational Quantum Eigensolver)와 양자 근사 최적화 알고리-리즘(Quantum Approximate Optimization Algorithm)과 같은 알고리즘을 사용했습니다. 이러한 알고리즘은 많은 가능성을 동시에 탐색함으로써 작동하며, 이러한 능력은 이와 같은 탐색 유형에서 고전 컴퓨터보다 속도 우위를 제공합니다. 또한 이 시스템은 데이터로부터 학습하고 어떤 고객이 락커를 사용할지 혹은 홈 배송을 이용할지에 대해 더 나은 결정을 내리기 위해 양자 강화 신경망을 활용합니다.

고성능 시뮬레이션을 통해 수행된 연구 결과는 기존 방식에 비해 명확한 개선을 보여줍니다. 물류 산업에서 사용되는 표준 벤치마크 데이터셋을 대상으로 테스트했을 때, 새로운 시스템은 최고의 전통적 알고리즘보다 총 배송 비용을 약 18.7% 절감했습니다. 또한 브랜치 앤 프라이스(Branch-and-Price)라고 알려진 또 다른 흔한 방식보다 약 23.4% 개선된 성능을 보였습니다. 무엇보다 중요한 점은, 이 시스템이 전통적인 방식이 적절한 시간 내에 좋은 해답을 찾지 못하는 경우가 많은 500명 이상의 고객 시나리오를 처리할 수 있었다는 것입니다. 연구진은 양자 부분이 해결하는 경로 하위 문제의 복잡도가 문제가 커짐에 따라 고전적인 방식보다 훨씬 느리게 증가한다는 점에 주목했으며, 이는 네트워크가 확장될수록 그 이점이 더욱 커질 것임을 시사합니다.

단순히 저렴한 경로를 찾는 것을 넘어, 이 시스템은 배송의 신뢰성도 향상시켰습니다. 고객이 실제로 패키지를 받기 위해 집에 있을지를 더 잘 예측함으로써, 홈 배송 실패율을 거의 12%에서 3.4%로 낮추었습니다. 이러한 감소는 낭비되는 이동을 줄이고 탄소 배출량을 줄인다는 것을 의미합니다. 또한 연구는 이 시스템이 파셀 락커를 훨씬 더 효율적으로 사용하여, 기존 방식의 약 67%에 비해 약 84%의 용량을 채운다는 것을 발견했습니다. 이러한 효율적인 공간 활용 덕분에 기업은 더 많은 락커를 짓거나 더 많은 트럭을 구입하지 않고도 더 많은 고객에게 서비스를 제공할 수 있습니다.

연구진은 자신들의 결과가 실제 양자 하드웨어에서 코드를 실행한 것이 아니라, 양자 동작을 모사하는 강력한 고전 컴퓨터에서 실행된 시뮬레이션으로부터 나왔다는 점을 주의 깊게 언급했습니다. 비록 결과는 유망하지만, 현재의 하드웨어 한계로 인해 실제 노이즈가 있는 양자 머신에서의 성능은 약간 다를 수 있습니다. 그러나 이 연구는 이론적 프레임워크가 견고하며, 하이브리드 접근 방식이 실행 가능한 길임을 입증합니다. 연구팀은 양자 하드웨어가 개선됨에 따라 이 방법이 글로벌 이커머스 경제의 복잡한 물류를 관리하는 표준 도구가 될 수 있다고 제안합니다.

결국, 이 연구는 도시 배송을 더욱 지속 가능하고 효율적으로 만드는 데 있어 중요한 진전을 의미합니다. 고전 컴퓨팅의 신뢰성과 양자 프로세싱의 독특한 속도를 결합함으로써, 연구진은 이전에는 해결하기 너무 어려웠던 물류 퍼즐을 풀 수 있는 방법을 보여주었습니다. 이 시스템은 단순히 해결책을 찾는 것이 아니라, 더 나은 해결책을 찾아내어 돈, 시간, 연료를 절약합니다. 온라인 쇼핑이 계속 성장함에 따라, 이러한 배송 네트워크를 최적화하는 능력은 점점 더 중요해질 것이며, 이 하이브리드 접근 방식은 미래의 물류가 어떻게 운영될지에 대한 전망을 제시합니다.

기술 요약: 양자 그래프 어텐션 네트워크를 이용한 택배 보관함 포함 픽업 및 배송 문제용 하이브리드 양자-고전 최적화 프레임워크

문제 정의
본 논문은 전자상거래의 급격한 성장으로 인해 발생하는 복잡한 변형 문제인 **택배 보관함 포함 픽업 및 배송 문제(PDPL)**를 다룹니다. PDPL은 택배 보관함을 대안적 배송 지점으로 통합함으로써 기존의 픽업 및 배송 시간 창 문제(PDPTW)를 확장한 것입니다. 이 문제는 다음과 같은 결합된 요인들로 인해 NP-난해(NP-hard) 특성을 가집니다:

용량 제약: 차량 용량과 보관함 칸의 용량을 모두 준수해야 합니다.
시간 창: 고객과 보관함은 특정 가용 시간대를 가집나다.
확률성: 홈 배송을 위한 고객 가용성은 확률적이며, 고객은 홈 배송과 보관함 픽업 사이에서 확률적인 선택을 합니다.
다기간 재고 관리: 보관함은 시간 경과에 따른 동적인 재고 균형 관리가 필요합니다.

혼합 정수 선형 계획법(MILP) 및 적응형 대규모 이웃 탐색(ALNS)과 같은 전통적인 최적화 방법은 높은 솔루션 품질을 유지하면서 고객 50~100명을 넘어 확장하는 데 어려움을 겪습니다. 또한, 기존의 양자 접근 방식은 소규모 인스턴스(노드 20개 미만)에 국한되어 있었으며, 보관함 네트워크나 확률적 수요와 같은 실제 제약 조건을 효과적으로 통합하지 못했습니다.

방법론: Q-PDPL 프레임워크
저자들은 택배 보관함을 활용한 라스트 마일 물류 최적화를 위해 설계된 새로운 하이브리드 양자-고전 프레임워크인 Q-PDPL을 제안합니다. 이 아키텍처는 단치히-울프 분해(Dantzig-Wolfe decomposition) 체계 내에서 세 가지 주요 구성 요소를 통합합니다:

양자 강화 프라이싱 서브문제 (VQE 및 QAOA):
- 프레임워크는 마스터 문제(경로 선택)를 프라이싱 서브문제(음의 축약 비용을 가진 새로운 경로 생성)로부터 분해합니다.
- 프라이싱 서브문제는 비용, 흐름 보존, 용량 및 시간 창 제약을 인코딩하는 양자 해밀토니안( $H_{PSP}$ )으로 매핑됩니다.
- **변분 양자 고유값 솔버(VQE)**와 **양자 근사 최적화 알고리즘(QAOA)**은 이 해밀토니안의 바닥 상태를 찾기 위해 사용되며, 이는 효과적으로 자원 제약이 있는 기본 최단 경로 문제(ESPPRC)를 해결합니다.
- 이 접근 방식은 매개변수화된 양자 회로(PQC)를 사용하여 프라이싱 단계에서 클래식한 $O(N^2)$ 또는 지수적 복잡도와 비교하여 $O(\sqrt{N} \cdot \text{poly}(\log N))$ 의 이론적 복잡도를 달나합니다.
Q-GAT 강화 심층 강화 학습 (DRL):
- 확률적인 고객 가용성과 실시간 라우팅 결정을 처리하기 위해, 시스템은 심층 강화 학습(DRL) 액터-크리틱 아키텍처 내에서 **양자 그래프 어텐션 네트워크(Q-GAT)**를 사용합니다.
- 다층 퍼셉트론(MLP)을 사용하는 클래식 그래프 어텐션 네트워크(GAT)와 달리, Q-GAT는 어텐션 메커니즘을 매개변수화된 양자 회로로 대체합니다.
- 이를 통해 모델은 47% 적은 학습 가능한 파라미터를 사용하면서도 더 복잡한 그래프 표현을 학습할 수 있으며, 라우팅 비용 효율성을 개선합니다.
- 훈련에는 확률적 환경에서 라우팅 정책을 적응시키기 위해 **근사 정책 최적화(PPO)**가 활용됩니다.
확률적 모델링 및 예측 (Q-SVM):
- 위치 및 배송 이력과 같은 특징을 기반으로 고객의 보관함 채택 확률을 예측하기 위해 양자 커널을 갖춘 **양자 서포트 벡터 머신(Q-SVM)**이 사용됩니다.
- 이러한 예측은 2단계 확률 계획법(two-stage stochastic programming) 모델로 전달됩니다. 첫 번째 단계는 초기 경로를 결정하며, 두 번째 단계는 배송 실패 시의 복구 조치(예: 재배송 또는 보관함 재할당)를 관리하여 기대 비용을 최소화합니다.

주요 기여
본 논문은 네 가지 주요 기여를 주장합니다:

새로운 하이브리드 아키텍처: 양자 회로(VQE/QAOA)가 프라이싱 서브문제를 해결하는 단치히-울프 분해를 활용한, PDPL 전용 최초의 양자 강화 알고리즘입니다.
DRL을 위한 Q-GAT: 클래식 어텐션 메커니즘을 양자 회로로 대체하여 상당한 파라미터 감소와 낮은 라우팅 비용을 달성한 새로운 모델입니다.
다기간 확률적 최적화: 동적 보관함 용량, Q-SVM 기반 채택 예측, 그리고 배송 실패 처리를 위한 2단계 확률 계획법의 통합입니다.
확장 가능한 실험적 검증: 최대 500명의 고객을 대상으로 한 데이터셋에서 프레임워크를 입증하였으며, 이는 양자 지원 라우팅 방법으로는 이전에 도달할 수 없었던 규모입니다.

실험 결과
프레임워크는 10~50개의 무작위 보관함 스테이션이 추가된 확장된 Solomon VRPTW 및 Li & Lim PDPTW 벤치마크 데이터셋을 사용하여 평가되었습니다. 주요 결과는 다음과 같습니다:

비용 절감: Q-PDPL은 클래식 ALNS 대비 18.7%의 비용 절감을, B&P(Branch-and-Price) 방법 대비 23.4%의 개선을 달성했습니다.
확장성: 시스템은 500명의 고객 사례를 성공적으로 처리하여 약 45분 만에 해결했습니다(B&P의 경우 8시간 소요). 500명 고객 인스턴스에서 솔루션 품질은 최적 경계 내 **2.1%**를 유지했으나, 클래식 ALNS는 4.8%의 격차를 보였습니다.
양자 가속: 양자 프라이싱 서브문제는 중간 규모 인스턴스(10~~15명 고객)에서 클래식 동적 계획법과 비교하여 계산 시간에서 **34~~47%의 가속**을 보여주었습니다.
Q-GAT 효율성: Q-GAT 모델은 클래식 GAT보다 23% 빠르게 수렴하였고(67 에포크 vs 87 에포크), 47% 적은 파라미터로 라우팅 비용을 8.3% 줄였습니다.
운영 영향: 전체 프레임워크는 보관함 활용도를 84.2%(ALNS의 67.3% 대비)로 높였고, 배송 실패율을 11.8%에서 **3.4%**로 낮췄습니다. 또한 홈 배송 전용 방식 대비 34.8%의 CO₂ 배출 감소를 투영했습니다.

의의 및 주장
본 논문은 Q-PDPL을 결함 허용 양자 컴퓨터의 등장 전에도 대규모 물류에 양자 컴퓨팅을 적용할 수 있는 실행 가능한 경로로 포지셔닝합니다. 잡음이 있는 중간 규모 양자(NISQ) 장치를 하이브리드 분해를 통해 활용함으로써, 저자들은 양자 이점이 특정적으로 계산 집약적인 하위 문제(프라이싱)에서 실현될 수 있는 동시에 조율을 위해 클래식 솔버에 의존할 수 있다고 주장합니다.

저자들은 본 연구가 이론적인 양자 이점과 실제 거리 물류 사이의 간극을 메우며, 최적화된 보관함 사용과 감소된 배송 실패를 통해 계산적으로 더 효율적일 뿐만 아니라 환경적으로도 우수한 솔루션을 제공한다고 주장합니다. 저자들은 현재의 한계(시뮬레이터 의존로 인한 노이즈 관련 품질 저하 5~12% 가능성)를 인정하면서도, 하이브리드 접근 방식이 미래의 지속 가능한 도시 물류를 위한 견고한 토대를 제공한다고 확언합니다.

유사한 논문