Reducing QUBO Complexity in Drone Delivery Through Classical Feasibility Preprocessing

기술 요약: 클래식 타당성 전처리를 통한 드론 배송의 QUBO 복잡도 감소

문제 정의

드론 배송 계획은 경로 결정과 페이로드 용량 및 제한된 탑재 에너지와 같은 엄격한 운영 제약을 통합하는 조합 최적화 문제를 포함합니다. 이러한 문제를 이차 무제약 이진 최적화(Quadratic Unconstrained Binary Optimization, QUBO) 모델로 직접 인코딩하면 대규모 정식화가 발생하는 경우가 많습니다. 경로 선택, 고객 할당 및 보조 제약 항을 나타내는 데 필요한 이진 변수는 현재 양자 하드웨어의 용량을 빠르게 초과할 수 있으며, 상태 벡터 시뮬레이션의 계산 비용을 증가시킵니다. 또한, 이론적으로 가능한 많은 경로가 페이로드나 에너지 제한으로 인해 물리적으로 불가능함에도 불구하고, 직접적인 QUBO 인코딩은 이를 모두 표현해야 하므로 탐색 공간이 비대해집니다.

방법론

저자들은 결정론적 타당성 검사와 조합 선택 문제를 분리하는 하이브리드 양자-클래식 분해(hybrid quantum–classical decomposition) 방方案을 제안합니다. 워크플로우는 다음과 같이 진행됩니다:

1. 클래식 후보 생성: 클래식 방식으로 후보 드론 미션(데포에서 출발하여 최대 $k$개의 정지를 거쳐 다시 데포로 돌아오는 경로)을 생성합니다.
2. 타당성 전처리: QUBO를 구성하기 전에 미션을 물리적 제약 조건에 따라 평가합니다:
   • 페이로드 제약: 미션 내 패키지의 총 중량은 드론의 최대 페이로드($W_{max}$)를 초과해서는 안 됩니다.
   • 에너지 제약: 거리와 각 구간별로 운반되는 페이로드(배송이 진행됨에 따라 감소함)의 함수로 모델링된 총 에너지 소비량은 가용 에너지($E_{max}$)를 초과해서는 안 됩니다.
   • 이러한 제약을 위반하는 미션은 폐기됩니다.
3. QUBO 정식화: 남은 타당한 미션들이 결정 공간을 형성합니다. 각 유지된 미션에 이진 변수 $x_r$이 할당됩니다. 목표는 모든 고객이 정확히 한 번씩 서비스되도록 하는 제약 조건을 이차 페널티 항을 통해 목적 함수에 포함시켜 총 비용(거리, 에너지 및 고정 미션 비용)을 최소화하는 것입니다.
4. 솔버(Solvers): 결과물인 QUBO는 다음을 사용하여 해결됩니다:
   • MILP (혼합 정수 선형 계획법): 최적성을 위한 클래식 참조 모델로 사용됩니다.
   • 정밀 열거(Exact Enumeration): QUBO 재정식화가 MILP 최적값을 보존하는지 확인하기 위해 작은 인스턴스에 사용됩니다.
   • 시뮬레이티드 어닐링 (SA): 클래식 휴리스틱 베이스라인으로 사용됩니다.
   • 양자 근사 최적화 알고리즘 (QAOA): 작은 인스턴스에 대한 양자 접근 방식을 평가하기 위해 깊이 $p=1$인 상태 벡터 시뮬레이터와 함께 구현되었습니다.

주요 기여

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

1. 하이브리드 정식화: 에너지 제약이 있는 멀티 드론 배송을 위해, QUBO 기반의 미션 선택 단계 이전에 후보 미션을 클래식하게 생성하고 필터링하는 특정 하이브리드 아키텍처를 도입했습니다.
2. 전처리 분석: 페이로드 및 에너지 전처리가 QUBO 크기(변수 개수), 연결성(이차 상호작용), 솔버 실행 시간 및 솔루션 품질에 미치는 영향을 평가합니다.
3. 비교 평가: 공통된 합성 드론 배송 인스턴스에 대해 MILP, 정밀 QUBO, SA, QAOA를 비교 분석합니다.
4. 재현 가능한 프레임워크: 제약이 있는 드론 배송을 위한 하이브리드 최적화의 동작과 현재의 한계를 연구하기 위한 재현 가능한 실험 프레임워크를 구축합니다.

결과

실험은 $10 \times 10$ km 영역 내에서 다양한 고객 수(4~12명)를 가진 합성 배송 인스턴스를 대상으로 수행되었습니다.

• 솔루션 품질 (RQ1):

  • 정밀 QUBO 최적화는 평가된 모든 작은 인스턴스에서 MILP 최적값을 재현하여 이진 재정식화의 유효성을 확인했습니다.
  • 시뮬레이티드 어닐링(SA)은 100%의 타당성(feasibility)과 중앙값 최적성 격차(optimality gap) 0%를 달ek성했습니다.
  • 평가된 얕은 QAOA 구성($p=1$)은 37.7%의 타당성 비율만을 달성했으며, 타당한 솔루션들 사이에서 8.09%의 중앙값 최적성 격차를 보였습니다.

• 전처리의 효과 (RQ2):

  • 페이로드와 에너지를 결합한 전처리는 필터링되지 않은 정식화와 비교했을 때 평균 QUBO 변수 수를 29.60%, 이차 상호작용을 49.20% 감소시켰습니다.
  • 이러한 감소는 평균 SA 실행 시간을 31.26% 단축시켰습니다.
  • 결정적으로, 전처리는 SA의 솔루션 타당성을 66.25%(필터링 전)에서 100%(필터링 후)로 높였으며, 테스트된 모든 케이스에서 MILP 최적값에 해당하는 미션 조합을 보존했습니다.

• 계산 확장성 (RQ3):

  • 솔버 실행 시간은 후보 경로 캡핑 전략으로 인해 원시 고객 수보다 결과적인 QUBO 차원(변수 수)과 더 강하게 상관관계가 있었습니다.
  • 상태 벡터 기반 QAOA는 지수적인 메모리 스케일링으로 인해 매우 작은 인스턴스(최대 16개 변수)로 제한되었으며, 이는 본 연구에서의 적용 가능성을 제한했습니다.

의의 및 주장

본 논문은 현재 설정에서 제안된 하이브리드 아키텍처의 주요 실질적 이점은 양자 솔버 자체보다는 클래식 타당성 전처리에서 온다고 결론짓습니다.

• 클래식 전처리가 핵심 동력: 본 연구는 결정론적 클래식 검사가 최적해를 제거하지 않으면서도 이진 탐색 공간(차원 및 연결성)을 효과적으로 줄일 수 있음을 입증합니다. 이는 후속 최적화 문제를 클래식 휴리스틱과 양자 알고리즘 모두에 더 다루기 쉽게 만듭니다.
• 현재 양자 접근 방식의 한계: 결과에 따르면 평가된 얕은 QAOA 구성은 클래식 방법(MILP 및 SA)에 비해 타당성과 최적성 확보에 어려움을 겪으며, 시뮬레이션 제약으로 인해 작은 문제 크기로 제한됩니다.
• 전략적 시사점: 근시일 내의 드론 배송을 위한 하이브리드 양자-클래식 워크플로우의 경우, 가장 효과적인 전략은 양자 최적화를 시도하기 전에 클래식 구성 요소를 공격적으로 사용하여 이진 문제의 크기를 줄이는 것입니다. QUBO 정식화는 솔버를 비교하기 위한 공통 표현 역할을 하지만, 즉각적인 가치는 문제 공간의 클래식한 축소에 있습니다.

저자들은 자신들의 결과가 양자 컴퓨팅 우위를 입증하는 것이 아니라, 얕은 변분 회로(variational circuits)를 사용하여 제약된 미션 선택 문제를 해결하는 것의 어려움을 강조하며, 이는 더 깊은 회로, 더 나은 파라미터 최적화 및 하드웨어 구현에 대한 추가 연구를 촉발하는 데 목적이 있다고 명시했습니다.