EMU circulation planning for Silesian Railways: case study and a quantum approach

본 논문은 실레지아 철도의 일일 전동차(EMU) 운행 계획에 관한 사례 연구를 제시하며, 실제 철도 최적화 분야에서 QUBO 기반 방식의 현재 한계와 잠재력을 입증하기 위해 고품질의 고전적 혼합 정수 선형 계획법 솔루션과 양자 및 양자 모사 접근 방식을 비교한다.

핵심

당신은 거대하고 분주한 오케스트라의 지휘자라고 상상해 보세요. 하지만 당신의 악기는 바이올린이나 드럼이 아니라 전기 열차입니다. 당신의 임무는 모든 열차에 운전사가 있고, 승객을 위한 충분한 좌석이 있으며, 자전거를 실을 공간도 충분하도록 보장하는 동시에, 모든 열차가 다음 날을 위해 준비될 수 있도록 각자의 "차고"(기지)로 무사히 돌아가게 만드는 것입니다.

이 논문은 이 퍼즐을 해결하기 위한 사례 연구로, 폴란드의 **실레지아 철도(Silesian Railways)**를 대상으로 합니다. 연구진은 이 문제를 해결하기 위해 두 가지 다른 방법을 시도했습니다: 전통적이고 신뢰할 수 있는 방식(고전 수학)과 미래 지향적이며 실험적인 방식(양자 컴퓨팅)입니다.

이들의 여정을 다음과 같이 정리했습니다:

1. 문제: 열차 퍼즐

철도 운영자는 매일 수백 대의 열차 일정을 계획해야 합니다. 이것은 단순히 노선에 열차를 배정하는 문제가 아니라, 추가적인 규칙이 붙은 복잡한 테트리스 게임과 같습니다:

• 결합(Coupling): 때때로 두 대의 동일한 열차를 (기차 칸처럼) 서로 연결하여 혼잡한 노선을 위해 더 큰 열차를 만들 수 있습니다.
• 자전거: 승객들의 자전거를 위한 충분한 공간을 확보해야 합니다.
• 운전사: 특정 시간에 가용한 운전사 수보다 더 많은 열차를 배정할 수 없습니다.
• 차고 균형: 매일 정해진 수의 열차가 특정 기지에서 시작하고 끝나야 합니다.

2. "전통적인" 해결책: 마스터 셰프 (ILP)

먼저, 연구팀은 고전적 수학 모델(정수 선형 계획법 또는 ILP라고 불림)을 구축했습니다.

• 비유: 이것은 모든 가능한 열차 배치 방식에 대한 레시피 북을 가진 매우 똑똑하고 초정밀하게 조직된 셰프라고 생각하면 됩니다. 셰프는 규칙(운전사, 자전거, 결합)에 따라 모든 가능성을 하나하나 확인하며 가장 완벽하고 저렴한 일정을 찾아냅니다.
• 결과: 이 방법은 완벽하게 작동했습니다. 404개의 열차 운행과 11가지 유형의 열차가 있는 상황에서도, 컴퓨터는 40분도 채 걸리지 않아 하루 전체의 일정을 해결했습니다. 이 방법은 매번 최적의 계획을 찾아냈습니다.

3. "미래 지향적인" 해결책: 양자의 주사위 던지기 (QUBO)

다음으로, 연구팀은 이 문제를 양자 컴퓨터(특히 D-Wave 머신)와 "양자 영감을 받은(Quantum-Inspired)" 소프트웨어가 이해할 수 있는 형식으로 변환하려고 시도했습니다. 그들은 열차 규칙을 QUBO(이차 무제약 이진 최적화) 문제로 전환했습니다.

• 비유: 셰프가 레시피를 하나씩 확인하는 대신, 시스템의 에너지를 "느끼며" 최적의 배치를 찾는 마법의 주사위 굴리기가 있다고 상상해 보세요. 배치가 나쁘면(예: 자전거 공간 부족) "뜨겁게"(높은 에너지) 느껴집니다. 배치가 좋으면 "차갑게"(낮은 에너지) 느껴집니다. 목표는 가장 차가운 상태를 찾는 것입니다.
• 함정: 양자 컴퓨터가 규칙을 이해할 수 있도록, 연구진은 "패널티" 가중치를 추가해야 했습니다. 이로 인해 문제의 크기가 폭발적으로 커졌습니다.
  • "폭발": 고전적 모델은 관리 가능한 수의 변수를 가졌던 반면, 양자 버전은 변수들 사이의 수백만 가지 상호작용을 고려해야 했습니다. 이는 마치 바다 전체를 찻잔에 담으려는 것과 같았습니다.

4. 맞대결: 누가 이겼나?

연구진은 실제 철도 데이터를 사용하여 두 방법을 테스트했습니다.

• 고전적 셰프 (ILP): 쉽게 승리했습니다. 이 방식은 크고 복잡한 실제 스케줄을 빠르게 처리하며 완벽한 답을 찾아냈습니다.
• 양자의 주사위 (D-Wave): 아주 작은 버전의 문제(단 3대의 열차만 있는 장난감 예시)만 해결할 수 있었습니다. 중간 규모의 스케줄을 입력하려고 하자, 컴퓨터의 "메모리"(큐비트)가 퍼즐을 담기에 충분하지 않았습니다. 그것은 마치 1,000피스짜리 퍼즐을 단 10개의 퍼즐 조각으로 풀려는 것과 같았습니다.
• 양자 영감을 받은 솔버 (VeloxQ): 이는 양자인 척하는 고전 컴퓨터입니다. 실제 양자 컴퓨터보다는 성능이 좋았고 약간 더 큰 문제들을 해결할 수 있었지만, 여전히 한계에 부딪혔습니다. 문제의 "지도"를 충분히 빠르게 생성하지 못했습니다.

5. 결론

이 논문은 오늘날의 철도 계획에 대해 다음과 같이 결론 내립니다:

• 고전적 셰프를 고수하라: 전통적인 수학 방식은 빠르고 신뢰할 수 있으며 실제 현장에서 바로 사용할 준비가 되어 있습니다.
• 양자는 아직 "장난감"이다: 현재의 양자 컴퓨터는 너무 작고, 문제를 변환하는 데 필요한 수학적 계산이 너무 무겁습니다. 양자 컴퓨터는 오직 아주 작고 단순화된 버전의 퍼즐만 해결할 수 있습니다.

미래의 아이디어:
저자들은 미래를 위한 하이브리드 접근 방식을 제안합니다. 고전적 셰프가 하루 전체를 계획하되, 양자의 주사위를 사용하여 특정하고 까다로운 지점(예: 열차의 결합 및 분리가 일어나는 혼잡한 역)을 빠르게 점검하여, 그 몇 대의 열차를 배치하는 데 더 나은 방법이 있는지 확인하는 방식입니다.

요약하자면: 연구진은 양자 컴퓨팅이 흥미롭긴 하지만, 현재 열차 일정을 계획하는 데 있어서는 구식 슈퍼컴퓨터 수학이 여전히 왕좌를 지키고 있다는 것을 증명했습니다. 양자 방식은 유망한 조력자이지만, 아직 주역이 될 준비는 되지 않았습니다.

기술 요약

기술 요약: 실레지아 철도(Silesian Railways)의 EMU 운행 계획

문제 정의

본 논문은 폴란드 실레지아 철도(Koleje Śląskie)의 지역 여객 네트워크를 대상으로 하는 전기동차(EMU)의 일일 차량 운행 계획 문제를 다룬다. 목표는 복잡한 운영 제약 조건을 충족하면서 고정된 열차 시간표에 가용 가능한 EMU를 배정하는 것이다.

문제의 주요 특징은 다음과 같다:

• 유연한 편성: 동일한 유형의 EMU는 용량을 늘리기 위해 사전 정의된 특정 운행 세트에서 쌍으로 결합될 수 있는 반면, 다른 운행은 단일 유닛으로 운행되어야 한다.
• 수요 기반 용량: 모델은 승객 좌석 용량과 자전거 적재 용량에 대한 제약 조건을 명시적으로 포함하여, 부족분이 허용 범위를 초과하지 않도록 보장한다.
• 기지 밸런스: 계획은 각 유형별 EMU가 특정 기지에서 하루를 시작하고 마치는 수량에 대해 하한 및 상한을 준수해야 하며, 이를 통해 운영 예비력을 유지한다.
• 승무원 가용성: 집계된 제약 조건은 특정 기지와 시간대의 적절한 기관사 가용성에 따라 동시에 운행되는 EMU의 수를 제한한다.
• 비순환적 호라이즌: 계획 호라이즌은 단일 일(day) 단위이므로, 순환형 주간 계획 모델과는 구별되는 비순환적 운행 구조를 가진다.

방법론

저자들은 고전적인 정수 선형 계획법(ILP) 정식화와 이차 무제약 이진 최적화(QUBO) 재정식화를 비교하는 이중 방법론을 제안한다.

1. 그래프/하이퍼 그래프 표현

문제는 다음과 같은 시점 확장 그래프(time-expanded graph)를 사용하여 모델링된다:

• **노드(Nodes)**는 열차 운행(trip) 및 보조 기지 서비스 이벤트를 나타낸다.
• **아크(Arcs)**는 단일 EMU의 운행 간 가능한 전이를 나타낸다.
• **하이퍼 아크(Hyper-arcs)**는 결합된 EMU가 포함된 전이(결합, 결합 상태에서의 이동, 분리)를 나타낸다.
  이 하이퍼 그래프 정식화는 유연한 열차 편성의 조합론적 복잡성을 자연스럽게 포착한다.

2. 고전적 ILP 접근 방식

문제는 혼합 정수 선형 계획법(MILP)으로 인코딩되며 SCIP 솔버를 사용하여 해결된다.

• 목적 함수: 운영 비용(고정 및 거리 의존 비용)과 투입된 EMU 수(예비 차량 보존을 위함)의 가중치 합을 최소화한다.
• 제약 조건: 커버리지(모든 운행이 정확히 한 번 수행됨), 흐름 균형(차량의 연속성), 기지 밸런스, 용량 제한(좌석/자전거), 승무원 가용성을 포함한다.
• 확장성: 이진 변수의 수는 최악의 경우 $|T| \cdot |T|^2 \cdot |R|$에 비례하여 증가하지만($|T|$는 운행 수, $|R|$은 EMU 유형 수), 실제 제약 조건에 의해 이 규모는 크게 축소된다.

3. 양자 및 양자 영감(Quantum-Inspired) 접근 방식 (QUBO)

양자 어닐링 및 물리 기반 휴리스틱을 활용하기 위해 ILP를 QUBO 문제로 재정식화한다.

• 변환: 제약 조건은 목적 함수에 추가되는 페널티 항으로 변환된다. 부등식 제약 조건(예: 기지 제한, 승무원 가용성)을 처리하기 위해 슬랙 변수(slack variables)가 도입된다.
• 솔버:
  • 양자 어닐링: D-Wave Advantage 시스템(Pegasus 및 Zephyr 토폴로지 모두)에서 실행된다.
  • 양자 영감: 물리 기반 휴로스틱(시뮬레이티드 바이퍼케이션/에너지 최소화)에 기반한 고전적 솔버인 VeloxQ를 사용하여 실행되며, 이는 양자 하드웨어를 필요로 하지 않는다.
• 확장성: QUBO 정식화는 이차 항(quadratic terms)의 수에서 상당한 오버헤드를 발생시키며, 최악의 경우 $|T|^5$로 확장된다. 이는 문제를 생성하고 저장하기도 전에 병목 현상을 일으킨다.

주요 기여

1. 실용적 ILP 모델: 특정 운영 요구사항(사전 정의된 운행에서의 쌍 결합 제한, 명시적인 자전거 용량 제약, 집계된 승무원 제한 등)을 통합한 유연하고 직접 해결 가능한 ILP 모델 개발.
2. QUBO 매핑: 차량 운행 문제를 QUBO로 재정식화하였으며, 변수 및 항의 확장에 대한 분석을 통해 이차 상호작용의 급격한 증가를 규명함.
3. 경험적 벤치마킹: 실레지아 철도의 실제 데이터(최대 404개 운행 및 11개 유형의 EMU)를 사용하여 다음을 평가함:
   • 고전적 ILP (SCIP).
   • 양자 어닐링 (D-Wave 하드웨어).
   • 양자 영감 휴리스틱 (VeloxQ).
4. 타당성 분석: 모델의 표현력과 계산 가능성 사이의 트레이드오프를 중심으로, QUBO 기반 방식의 현재 실질적인 한계점을 식별함.

실험 결과

고전적 ILP 성능

• 확장성: SCIP 솔버는 약 404개의 운행과 약 380,000개의 이진 변수를 포함한 가장 큰 인스턴스를 포함하여 모든 인스턴스를 성공적으로 해결했다.
• 실행 시간: 중간 규모 인스턴스에서는 수 초 내에, 가장 큰 인스상스에서는 최대 약 40분 내에 최적 또는 고품질의 해를 얻었다.
• 품질: 모델은 복잡한 결합 시나리오와 용량 제한을 포함한 모든 제약 조건을 준수하는 실행 가능하고 실용적인 운행 계획을 생성했다.

양자 및 양자 영감 성능

• 하드웨어 제한: D-Wave 양자 어닐러는 임베딩 제한과 가용 큐비트 수로 인해 가장 작은 인스턴스(약 50개 운행까지)로 제한되었다. 새로운 Advantage2 시스템(Zephyr 토폴로지)은 기존 Pegasus 기반 시스템보다 약간 더 큰 서브 인스턴스를 해결할 수 있었으나, 크기 2a 이상의 인스턴스는 처리할 수 없었다.
• QUBO 구축 병목 현상: 주요 장벽은 해결 시간 자체가 아니라 QUBO 행렬의 생성이었다. 중간 규모 인스턴스(예: 78개 운행)의 경우 이차 항의 수가 약 180만 개에 달했으며, 더 큰 인스턴스의 경우 $10^8$을 초과하여 가용 RAM(62 GB) 내에서 모델 생성이 불가능했다.
• 솔버 비교:
  • VeloxQ: 작은 인스턴스에서 D-Wave보다 우수한 성능을 보이며 최적해를 빠르게 찾아냈다. 그러나 더 큰 인스턴스에 대한 QUBO 모델 생성 시 발생하는 동일한 제한 문제에 직면했다.
  • 타당성: 양자 및 양자 영감 솔버 모두 (페널티 방식이 구조적으로 실행 가능성을 보장하지 않으므로) 소프트 제약 조건(슬랙 변수)을 위반하는 해를 걸러내기 위한 후처리 과정이 필요했다.

의의 및 주장

본 논문은 다음과 같이 주장한다:

• 고전적 ILP가 현재 우위에 있음: 고전적 접근 방식(SCIP)만이 실질적인 시간 내에 전체 규모의 실제 지역 철도 인스턴스(수백 개의 운행)를 처리하고 실행 가능성을 보장할 수 있는 유일한 방법이다.
• 양자 방법의 현재 상태: QUBO 기반 접근 방식(양자 및 양자 영감 모두)은 이차 항의 확장과 임베딩 오버헤드로 인해 현재 작은 하위 문제나 매우 제한된 인스턴스로 제한되어 있다. 이들은 아직 엔드 투 엔드 일일 계획 측면에서 고전적 솔버를 능가하지 못한다.
• 미래 방향: 결과는 하이브리드 고전-양자 아키텍처가 가장 유망한 단기 경로임을 시사한다. 이 프레임워크에서 고전적 솔버는 전역 문제를 처리하고, QUBO 기반 방식은 규모가 축소된 국지적이고 복잡도가 높은 하위 문제(예: 특정 결합 핫스팟 또는 단기 재스케줄링 윈도우)에 적용될 수 있다.
• 실용적 유용성: 연구는 전이 시간 창($\Delta$)을 제한하는 것이 솔루션 품질을 크게 저하시키지 않으면서도 고전적 솔버를 위한 모델 복잡도를 줄이는 효과적인 휴리스틱 역할을 한다는 것을 보여주며, 이는 QUBO 정식화의 희소성(sparsification)을 높이는 데에도 도움이 될 수 있다.

저자들은 양자 방법이 저에너지 상태를 샘플링하고 대안적인 실행 가능 해를 제공하는 데 잠재력이 있지만, 대규모 철도 운행 계획에 대한 적용은 하드웨어의 한계와 QUBO 재정식화의 수학적 오버헤드로 인해 제약을 받고 있다고 결론지었다.