Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

본 논문은 철도 차량 계획을 최대 가중치 독립 집합 문제로 재정의하는 하이브리드 분할 정복 프레임워크를 제시하고, 클래식 시뮬레이터와 IQM 에메랄드 양자 장치 모두에서 양자 근사 최적화 알고리즘(QAOA)을 평가함으로써, 이 접근 방식 내에서 서브그래프 크기를 키우는 것이 근사 해법과 정확한 해법 사이의 간극을 효과적으로 메운다는 것을 입증한다.

핵심

당신이 거대한 철도 회사의 운전사라고 상상해 보세요. 당신에게는 이틀 동안 발생할 190개의 구체적인 열차 운행 일정이 있습니다. 당신의 임무는 어떤 물리적인 열차가 어떤 운행을 맡을지 결정하는 것입니다.

하지만 규칙이 있습니다:

1. 유지보수: 모든 열차는 몇 천 킬로미터마다 특정 역(예: 함부르크)에 들러 2시간 동안 점검을 받아야 합니다.
2. 연속성: 열차는 마법처럼 순간 이동할 수 없습니다. 즉, 한 운행을 마치고 반드시 같은 역에서 다음 운행을 시작해야 합니다.
3. 비용: 만약 열차가 다음 업무를 수행하기 위해 승객 없이 이동해야 한다면(공차 운행), 이는 비용(연료, 마모 등)을 발생시킵니다. 당신은 이러한 공차 주행 거리를 최소화하고 싶어 합니다.

이것이 바로 철도 차량 계획(Rolling Stock Planning) 문제입니다. 이것은 여러 개의 루프(사이클이라고 불림)를 만들어내는 거대한 퍼즐입니다. 이 루프들은 출발지와 도착지가 같아야 하며, 유지보수 규칙을 준수해야 하고, 비용을 가장 적게 들여야 합니다.

문제점: 너무 많은 가능성

열차를 배치하는 방법의 가짓수는 천문학적으로 많습니다. 이는 마치 규칙이 계속 바뀌는 축구장 크기의 스도쿠 퍼즐을 푸는 것과 같습니다. 가장 빠른 슈퍼컴퓨터조차 이 완벽한 배치를 찾아내는 데 어려움을 겪습니다.

해결책: 하이브리드 "분할 정복(Divide and Conquer)" 전략

저자들은 영리한 묘수를 제안합니다. 거대한 퍼즐 전체를 한꺼번에 해결하려고 노력하는 대신, 문제를 관리 가능한 작은 덩어리로 나눕니다.

거대한 도서관을 정리하는 것을 생각해 보세요. 세상의 모든 책을 한꺼번에 서가에 꽂으려 하는 대신, 당신은 다음과 같이 합니다:

1. 도서관의 작은 구역을 하나 정합니다.
2. 그 책들을 완벽하게 분류합니다.
3. 서가에 꽂습니다.
4. 다음 구역으로 이동합니다.

그들은 이를 분할 정복(Divide-and-Conquer) 알고리즘이라고 부릅니다. 그들은 큰 문제를 가져와서 작은 조각(서브그래프)으로 자르고, 그 조각을 해결한 다음 다음 단계로 넘어갑니다.

비밀 병기: 양자 컴퓨터

여기서 공상과학 영화 같은 이야기가 등장합니다. 이 작은 조각들을 해결하기 위해, 그들은 기존 방식의 컴퓨터와 양자 컴퓨터라는 새로운 유형의 컴퓨터를 혼합하여 사용합니다.

• 고전 컴퓨터 (Classical Computer): 매우 빠르고 논리적인 사서와 같습니다. 작은 퍼즐은 빠르게 풀 수 있지만, 거대한 퍼즐 앞에서는 막혀버립니다.
• 양자 컴퓨터 (QAOA): 이것은 "직관력이 뛰어난" 사서라고 생각하면 됩니다. 단순히 한 번에 하나의 경로만 보는 것이 아니라, 동시에 많은 가능성을 탐색합니다. 이들은 **양자 근사 최적화 알고 알고리즘(Quantum Approximate Optimization Algorithm, QAOA)**이라는 방법을 사용합니다.

연구진은 이 양자 사서를 실제 양자 기기(IQM Emerald)에서 테스트했을 뿐만 아니라, 고전 컴퓨터에서도 시뮬레이션했습니다.

테스트 방법

연구진은 이 작은 퍼즐 조각들을 해결하는 세 가지 방법을 비교했습니다:

1. 탐욕 알고리즘 (Greedy Approach): 앞을 내다보지 않고 현재 눈앞에 보이는 가장 좋아 보이는 옵션을 선택하는 단순하고 빠른 방법입니다. (마치 책이 장르에 맞는지 확인하지 않고 가장 가까운 책을 집는 것과 같습니다.)
2. 정밀 솔버 (Exact Solver): 절대적인 최적의 답을 찾기 위해 모든 가능성을 일일이 확인하는 느리지만 완벽한 방법입니다.
3. 양자 솔버 (QAOA): 매우 좋은 답을 빠르게 찾아내려고 시도하는 "직관적인" 접근 방식입니다.

연구 결과

1. 덩어리가 클수록 좋습니다: 퍼즐의 "작은 조각"을 더 크게 만들수록 전체적인 솔루션이 더 좋아졌습니다. 이는 책 한 선반을 정리하는 대신 책장 한 칸을 통째로 정리할 때, 더 넓은 관점을 가지고 더 현명한 선택을 할 수 있는 것과 같습니다.
2. 양자는 유망합니다: 양자 솔버(QAOA)는 느리지만 완벽한 "정밀 솔버"와 거의 대등한 성능을 보이면서도 훨씬 빨랐습니다. 비록 현재의 양자 컴퓨터는 규모가 작고 아직 완벽하지 않음에도 불구하고, 최선의 답에 매우 근접한 고품질의 솔루션을 찾아낼 수 있음을 보여주었습니다.
3. "가지치기(Pruning)" 단계: 때때로 양자 컴퓨터는 엉뚱한 답을 내놓을 수 있습니다(예: 두 대의 열차가 같은 장소에 동시에 가도록 제안하는 경우). 저자들은 이러한 오류를 정리하기 위해 "가지치기" 도구를 사용하여 충돌을 제거하고 유효한 솔루션을 만듭니다.

결론

이 논문은 양자 컴퓨터가 이미 세상의 모든 철도 문제를 해결했다고 주장하는 것이 아닙니다. 대신, 이것은 하나의 로드맵을 제시합니다.

그들은 거대하고 불가능해 보이는 문제를 작은 조각으로 나누고, 양자 컴퓨터를 사용하여 그 조각들을 해결함으로써 매우 좋은 결과를 얻을 수 있다는 것을 증명했습니다. 이는 과거의 느리지만 완벽한 방법과 미래의 빠르고 강력한 방법 사이를 잇는 가교 역할을 합니다.

요약하자면, 그들은 거대하고 복잡한 철도 일정을 가져와서, 그것을 잘게 쪼갠 뒤, 양자 컴퓨터를 사용하여 작은 조각들을 정리했고, 이러한 하이브리드 접근 방식이 단순히 추측하거나 기존의 컴퓨터만을 사용하는 것보다 더 효과적임을 보여주었습니다.

기술 요약

기술 요약: 양자 근사 최적화 알고리즘(QAOA)을 이용한 철도 차량 운행 계획

문제 정의
본 논문은 철도 관리의 복잡한 최적화 과제인 철도 차량 운행 계획(Rolling Stock Planning) 문제를 다룹니다. 목표는 스케줄된 운행 일정에 물리적인 열차를 할당하되, 운영 비용(특히 승객 없이 주행하는 '공차 킬로미터')을 최소화하는 것입니다. 고려된 문제 사례는 5개 역을 대상으로 이틀 동안 진행되는 190개의 운행(trips)을 포함하며, 다음과 같은 엄격한 제약 조건을 따릅니다:

• 순환 운행(Cyclic Operation): 각 열차는 시작 역으로 돌아오는 순환 과정을 완료해야 합니다.
• 유지보수(Maintenance): 모든 순환 과정에는 지정된 역에서 정해진 시간 동안 수행되는 의무적인 유지보수 정차가 포함되어야 합니다.
• 거리 제한: 순환 과정은 유지보수가 필요하기 전까지 최대 거리($l_{max}$)를 초과할 수 없습니다.
• 공차 운행(Empty Trips): 열차는 스케줄된 운행을 연결하거나 유지보수 역에 도달하기 위해 "공차 운행"(비정기 이동)을 수행할 수 있으며, 이는 비용을 발생시키지만 실행 가능성을 보장합니다.

저자들은 문제가 제약이 많지만, 본 연구의 범위 내에서는 네트워크 용량 제약(예: 역 주차 제한 또는 경로 혼잡)을 모델링하지 않고 무제한 용량을 가정한다고 언급했습니다.

방법론
저자들은 운행 수에 따라 지수적으로 증가하는 계산 복잡도를 해결하기 위해 하이브리드 양자-고전 분할 정복(divide-and-conquer) 알고리즘을 제안합니다.

1. 최대 가중치 독립 집합(MWIS)으로의 매핑:
   문제는 먼저 그래프 상의 MWIS 문제로 재구성됩니다.

   • 노드(Nodes): 타임테이블로부터 생성된 실행 가능한 열차 순환(cycles)을 나타냅니다.
   • 에지(Edges): 대응하는 순환들이 서로 호환되지 않는 경우(즉, 동일한 스케줄된 운행을 동시에 서비스하는 경우) 노드들을 연결합니다.
   • 가중치(Weights): 순수 비용 절감보다 승객 운행 커버리지를 우선시하는 휴리스틱 목적 함수($w_i = 2d_{full} - d_{empty}$)에 따라 노드에 할당됩니다.
   • 목표: 최대 총 가중치를 갖는 독립 집합(상충되지 않는 순환들의 집합)을 찾는 것입니다.

2. 순환 생성 전략:
   가능한 순환의 폭발적인 증가를 관리하기 위해, 저자들은 두 가지 모드의 생성 프로세스를 사용합니다.

   • 모드 1: 공차 운행 없이 스케줄된 운행만을 사용하여 순환을 생성합니다.
   • 모드 2: 미처리 운행 수가 임계값(40개 운행) 미만으로 떨어지거나 더 이상 모드 1 순환을 형성할 수 없을 때 활성화됩니다. 이 모드는 공차 운행을 허용하여 솔루션 공간을 크게 확장함으로써 남은 모든 운행이 커버될 수 있도록 보장합니다.

3. 하이브리드 분할 정복 프레임워크:
   전체 MWIS 그래프는 현재의 솔버(solver)가 처리하기에 너무 크기 때문에, 알고리즘은 더 작은 서브그래프를 반복적으로 해결합니다.

   • 서브그래프 선택: 휴리스틱을 사용하여 크기 $k$(예: 20~300개 노드)의 서브그래프를 선택합니다. 선택 전략은 솔루션의 품질과 다양성의 균형을 맞추기 위해 가장 많은 승객 운행을 서비스하는 순환을 우선시합니다.
   • 서브그래프 해결: 선택된 서브그래프의 MWIS 문제는 다양한 방법으로 해결됩니다:
     • 고전적 정확한 솔버(Classical Exact Solver): 베이스라인으로 사용됩니다.
     • 그리디 알고리즘(Greedy Algorithm): 가중치 대비 차수(weight-to-degree) 비율에 따라 노드를 선택하는 고전적 베이스라인입니다.
     • QAOA (양자 근사 최적화 알고리즘): 깊이 $p=1$ 및 $p=5$로 구현되었습니다. 문제는 에지 위반에 대한 페널티 항이 있는 대각 스핀 글래스 해밀토니안(diagonal spin-glass Hamiltonian)으로 매핑됩니다.
     • 무작위 샘의(Random Sampling): 하한선 벤치마크로 사용됩니다.
   • 가지치기(Pruning): QAOA와 무작위 샘플링은 유효하지 않은 집합(연결된 노드를 포함하는 집합)을 생성할 수 있으므로, 유효한 독립 집합이 형성될 때까지 가중치 대비 차수 비율이 낮은 노드를 제거하는 가지치기 절차를 수행합니다.
   • 글로벌 업데이트: 선택된 순환들은 글로벌 솔루션에 추가되고, 충돌하는 노드들은 글로벌 그래프에서 제거됩니다. 이 과정은 모든 운행이 서비스될 때까지 반복됩니다.

주요 결과
저자들은 고전적 시뮬레이션과 IQM Emerald 양자 장치를 이용한 실행을 통해 알고리즘을 평가했습니다.

• 솔버 비교 (고정된 서브그래프 크기): 작은 서브그래프 크기($k=20$)에서 그리디 알고리즘, 고전적 정확한 솔버, 그리고 QAOA($p=1, p=5$) 간의 성능 차이는 미미했습니다. 그러나 결과는 높은 깊이의 QAOA($p=5$)가 지수 시간 알고리즘인 정확한 솔버에 비해 다항 시간 알고리즘임에도 불구하고, 정확한 솔버의 솔루션 품질에 접근하는 경향이 있음을 보여주었습니다.
• 서브그래프 크기의 영향: 중요한 발견은 서브그래프 크기와 솔루션 품질 사이의 양의 상관관계였습니다. 서브그래프 크기가 증가함에 따라(최대 300개 노드), 공차 킬로미터가 크게 감소했습니다($p \approx 10^{-9}$의 음의 기울기). 이는 서브그래프 솔버 자체가 근사적일지라도, 더 큰 서브문제를 푸는 것이 더 나은 글로벌 솔루션을 제공한다는 것을 시사합니다.
• 양자 실행: 논문은 $p=1$ QAOA를 IQ금 Emerald 양자 컴퓨터에서 실행한 결과를 보고하며, 테스트된 파라미터에 대해 솔루션 품질이 고전적 시뮬레이션 및 무작위 샘플링과 유사했음에도 불구하고, 현재의 하드웨어에서 알고리즘을 실행하는 것이 가능하다는 점을 입증했습니다.

의의 및 주장
본 논문은 하드웨어가 전체 문제를 직접 해결할 수 있을 만큼 발전하기 전, 근접 미래의 양자 컴퓨터를 실제 산업 최적화 문제에 적용하기 위한 실질적인 경로를 제시합니다.

• 간극 메우기: 하이브리드 프레임워크는 빠른 근사 다항 시간 솔버(그리디 알고리즘 등)와 느린 정확한 지수 시간 방법 사이의 간극을 효과적으로 메웁니다.
• 확장성: 저자들은 자신들의 접근 방식이 양자 알고리즘이 현재의 하드웨어 제한에 적합한 하위 문제에 적용될 수 있도록 하면서, 고전적인 외부 루프가 전체 최적화를 조율하도록 한다고 주장합니다.
• 양자 우위 잠재력: 결과는 QAOA의 깊이($p$)가 대략적인 최적해를 얻기 위해 서브그래프 크기에 따라 다항적으로만 증가하면 된다는 시나리오를 제시하며, 이는 대규모 인스턴스에 대해 정확한 고전적 방법보다 잠재적인 양자 우위를 제공할 수 있음을 의미합니다.
• 겸허한 태도: 저자들은 현재의 순환 생성 단계가 더 큰 타임테이블에서 병목 현상이 될 수 있고, 가지치기 절차의 효과가 서브그래프 크기가 커짐에 따라 저하될 수 있다는 한계를 인정하며 신중한 태도를 보였습니다. 그들은 QAOA가 현재 전체 문제에 대해 고전적 정확한 솔버보다 우수하다고 주장하는 것이 아니라, 하이브리드 아키텍처가 양자 자원만으로는 과거에 불가능했던 더 넓은 솔루션 공간을 탐색할 수 있게 해준다는 점을 강조합니다.