arXiv:2606.06543v1 quant-ph

QUBO 및 하이브리드 양자 알고리즘 기반 철도 단기 집중 출발 시나리오의 출발 순서와 구간-선로 할당 조율 최적화

Coordinated optimization of departure sequencing and section-track allocation in railway short-term concentrated departure scenarios based on qubo and hybrid quantum algorithms

Xiaobin Li, Yanbin Gao, Weiguang Wang, Xuechen Liang

제출 2026-06-04

한국어 초록

본 연구는 철도 단기 집중 출발 시나리오에서 출발 순서와 구간-선로 할당의 조율 최적화를 다룬다. 통합 이진 프레임워크 내에서 출발 위치 할당과 구간-선로 선택을 표현하기 위해 이차 무제약 이진 최적화(quadratic unconstrained binary optimization, QUBO) 모델을 수립한다. 디스패칭 방안의 품질은 정적 조합 모델로 완전히 포착할 수 없는 시간 의존적 운영 상호작용에 달려 있으므로, 구간 점유, 중간역 대기, 승강장 용량 압력, 운행 시간 변동, 지연 전파를 평가하기 위해 시뮬레이션 기반 평가 층을 도입한다. 이 계층적 프레임워크 안에서 기존 휴리스틱, 양자 영감(quantum-inspired) 알고리즘, 하이브리드 알고리즘을 동일한 의사결정 구조 위에서 비교한다. 결과에 따르면 QUBO 모델은 디코딩 후 실행 가능한 후보 방안을 생성할 수 있으며, 시뮬레이션 층은 정상 및 교란 조건 모두에서 경쟁 알고리즘의 운영 성능을 명확히 구분한다. 시험 시나리오에서 QPSO-QAOA는 정상 조건에서 가장 우수한 성능을 보였으며, 양자 강화 방법은 동적 조건에서 기존 대응 방법 대비 종합 비용을 평균 4.28%--26.26%, 총 지연을 평균 4.37%--24.25% 감소시켰다. 이러한 결과는 QUBO 기반 모델링과 시뮬레이션 기반 평가의 통합이 철도 단기 집중 출발 스케줄링을 위한 유용한 방법론적 프레임워크를 제공함을 시사하지만, 실제 운영 데이터를 이용한 검증은 여전히 필요하다.

원문 초록

This study examines the coordinated optimization of departure sequencing and section-track allocation in railway short-term concentrated departure scenarios. A quadratic unconstrained binary optimization (QUBO) model is formulated to represent departure-position assignment and section-track selection within a unified binary framework. Because the quality of a dispatching scheme depends on time-dependent operational interactions that cannot be fully captured by a static combinatorial model, a simulation-based evaluation layer is introduced to assess section occupation, intermediate-station waiting, platform-capacity pressure, running-time fluctuations, and delay propagation. Within this layered framework, conventional heuristics, quantum-inspired algorithms, and hybrid algorithms are compared on the same decision structure. The results show that the QUBO model can generate feasible candidate schemes after decoding, while the simulation layer clearly differentiates the operational performance of the competing algorithms under both normal and disturbed conditions. In the tested scenarios, QPSO-QAOA performs best under normal conditions, and the quantum-enhanced methods reduce comprehensive cost by 4.28\%--26.26\% and total delay by 4.37\%--24.25\% on average under dynamic conditions relative to their conventional counterparts. These findings suggest that the integration of QUBO-based modeling and simulation-based evaluation provides a useful methodological framework for railway short-term concentrated departure scheduling, although validation with real operational data remains necessary.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.06543v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.09737v2physics.chem-ph공통 태그 Combinatorial Optimization, quantum computing, qaoa

Q-Score: 분자 도킹을 위한 양자 네이티브 스코어링 함수

Q-Score: A Quantum-Native Scoring Function for Molecular Docking

분자 도킹은 소분자가 단백질에 결합하는 방식을 예측하며, 신약 개발의 핵심 병목 단계이다. 고전적인 스코어링 함수는 경험적 쌍별 접촉을 합산하는 방식으로, 결합 특이성을 결정하는 궤도 전하 이동과 같은 양자역학적 효과를 반영하지 못한다. 본 연구에서는 Q-Score를 제안한다. Q-Score는 GNN으로 예측된 궤도 전자 공여-수용 에너지를 가중 그래프로 인코딩하고, Digitized-Counterdiabatic QAOA를 통해 최대 가중치 정점 클리크 문제를 풀어 결합을 스코어링한다. 각 상호작용 앵커는 하나의 큐비트에 대응되며, 호환성 제약 조건은 에지로 표현된다. 11개의 단백질 타겟에 대해 DC-QAOA는 10큐비트에서 8개의 타겟에서 정확한 최적해를 복원한다. AI 생성 분자 1,000개에 대해 Q-Score는 Spearman rho 0.05로 고전적 스코어링과 직교하며, rho 0.90으로 궤도 품질에 의해 주도되고, 분자량 바이어스가 없으며, 무작위 대비 두 배의 비율로 강한 궤도 상호작용을 농축시킨다. DC-QAOA는 52%의 정확률과 함께 평균 근사 비율 0.94를 달성한다. IBM Eagle에서 1,000개의 회로 실행을 통해 NISQ 하드웨어상 6큐비트 문제의 해결 가능성이 확인되었다.

arXiv:2607.02622v1quant-ph공통 태그 Combinatorial Optimization, quantum computing, qaoa

COMET: 제약 보존 QAOA를 통한 멀티플렉스 편집 타겟을 위한 조합 최적화

COMET: Combinatorial Optimization for Multiplex Editing Targets Via Constraint-Preserving QAOA

멀티플렉스 CRISPR-Cas9 유전자 편집은 유전자 간 상호작용이 존재하는 상황에서 각 타겟 유전자마다 하나의 가이드 RNA를 선택해야 하는 제약 조합 문제로, 이는 이차 비제약 이진 최적화(QUBO)로 정식화하여 양자 근사 최적화 알고리즘(QAOA)으로 풀 수 있다. 유전자당 원-핫(one-hot) 제약은 통상적으로 비용 해밀토니안에 이차 패널티 항을 추가하는 방식으로 적용되지만, 패널티 계수 선택은 휴리스틱에 의존하며 패널티가 하드웨어 노이즈를 증폭시키는 문제가 있다. 대안으로, 구조적으로 제약을 적용하는 XY-믹서를 사용하면 설계 단계에서 실현 가능성을 보장할 수 있다. 본 논문에서는 면역 체크포인트 유전자 PDCD1, LAG3, HAVCR2를 타겟으로 하는 3개 유전자, 12큐비트 멀티플렉스 편집 인스턴스에서 패널티 기반 QAOA와 XY-믹서 QAOA를 체계적으로 비교한 COMET을 제시한다. 시뮬레이션에서 XY-믹서는 QAOA 깊이 p=3에서 최적값의 확률 95% 이상을 달성한 반면, 패널티 계수를 한 자릿수 범위로 변화시킨 세 가지 패널티 변형은 모든 깊이에서 6% 미만에 머물렀다. IBM의 ibm_kingston(Heron r2) 프로세서에서 XY-믹서의 시뮬레이터-하드웨어 에너지 차이는 모든 깊이에서 |0.8| 이내를 유지한 반면, 가장 잘못 조정된 패널티 변형의 차이는 +53.9에 달했다. 또한 게이트 수준 노이즈 하에서 구조적 보장이 부분적으로 깨지는 상황에 대해서도 솔직하게 분석한다. 12큐비트 인스턴스는 고전적으로 자명한 문제이나, 본 연구의 기여는 실제 하드웨어 검증을 포함하여 생물학적으로 동기화된 영역에서 제약 적용 전략에 대한 방법론적 비교를 제공하는 데 있다.

arXiv:2607.23316v2cs.NE공통 태그 Scheduling, Combinatorial Optimization

학생 학습 자원 배분을 위한 유전 알고리즘

A genetic algorithm for student academic resource allocation

개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.

arXiv:2610.03316v2cs.AI공통 태그 Scheduling, Combinatorial Optimization

LLM을 활용한 제로샷 교차 문제 일반화를 위한 다중 작업 진화

Multi-Task Evolution for Zero-Shot Cross-Problem Generalization using LLMs

다양한 조합 최적화(combinatorial optimization) 문제를 위한 효과적인 휴리스틱(heuristic)을 설계하는 것은 상당한 전문성과 반복적인 탐색을 필요로 합니다. 대규모 언어 모델(LLM)은 휴리스틱 생성과 개선을 자동화하지만, 휴리스틱 탐색은 일반적으로 최적화 대상 문제의 평가 피드백에 의존합니다. 따라서 소스 작업 피드백만을 사용하여 새로운 문제 정의로 일반화하는 것은 여전히 핵심적인 과제로 남아 있습니다. 본 논문에서는 제로샷(zero-shot) 교차 문제 일반화를 위한 LLM 기반 다중 작업 진화 프레임워크인 MECo를 소개합니다. MECo는 작업 조건부 휴리스틱 개체군을 유지하며, 교차 작업 개체군 성능에 기반한 전이 격차(transfer gap)를 활용해 이들의 상호작용을 유도합니다. 이러한 상호작용은 휴리스틱의 전이와 재조합을 가능하게 합니다. 그런 다음 상호보완적 선택 기준을 통해 각 개체가 소스 조합에 대해 제공하는 추가적인 커버리지를 보상함으로써 간결한 휴리스틱 세트를 구성합니다. 선택된 세트는 추가적인 탐색이나 적응 과정 없이 타깃 문제에 바로 적용됩니다. 차량 경로 문제(VRP) 및 유연한 잡숍 스케줄링(FJSP) 전반에 걸친 32가지 변형 문제를 대상으로 한 실험에서, MECo는 동일한 예산 하에 8개의 자동화된 휴리스틱 설계(AHD) 기준선과 비교해 가장 낮은 평균 비용을 달성함을 보여줍니다. 도메인 외(OOD) 문제에서도 각 제품군에서 가장 강력한 기준선을 능가합니다. 나아가 MECo 프레임워크를 서로 다른 AHD 방법들과 통합했을 때 두 제품군 모두에서 ID 및 OOD 성능이 향상되어, 여러 방법 전반에 걸친 유효성을 뒷받침합니다.

arXiv:2610.03296v1cs.AI공통 태그 Scheduling, Combinatorial Optimization

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2610.03312v1cs.AI공통 태그 Scheduling, Combinatorial Optimization

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.