論文の概要: Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm
- arxiv url: http://arxiv.org/abs/2606.11383v1
- Date: Tue, 09 Jun 2026 19:06:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-11 16:42:38.151383
- Title: Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm
- Title（参考訳）: 量子近似最適化アルゴリズムを用いた転がりストックプランニング
- Authors: Jiří Guth Jarkovský, Patricia Bickert, Elisabeth Wybo, Martin Leib,
- Abstract要約: 転がりストックプランニングは、鉄道経営における複雑な最適化問題である。
ノードが実行可能な列車周期を表すグラフ上での最大ウェイト独立集合 (MWIS) 問題として問題を再構成する。
大規模探索空間の計算複雑性に対処するため,ハイブリッド分割・コンカレントアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Rolling stock planning is a complex optimization problem in railway management that involves assigning physical trains to scheduled trips while minimizing operational costs. In this work, we address a specific instance of this problem featuring 190 trips over two days, subject to constraints such as mandatory maintenance stops. We reformulate the problem as a Maximum-Weight Independent Set (MWIS) problem on a graph where nodes represent feasible train cycles. To handle the computational complexity of the large search space, we propose a hybrid divide-and-conquer algorithm. This approach iteratively selects subgraphs and solves the MWIS problem using various solvers, including exact classical methods and the Quantum Approximate Optimization Algorithm (QAOA). We evaluate the algorithm's performance by comparing these methods and analyzing the scaling with respect to subgraph size, with QAOA assessed through both classical simulation and execution on a quantum device (IQM Emerald). Our results indicate that increasing the subgraph size generally improves solution quality, demonstrating that the hybrid framework can effectively bridge the gap between polynomial-time approximate solvers and exponential-time exact methods.
- Abstract（参考訳）: 転がりストックプランニング(英語: Rolling Stock Planning)は、鉄道経営における複雑な最適化問題であり、運行コストを最小化しながら、定期列車に物理的列車を割り当てることである。
本研究は,2日間にわたる190回の旅行を含む,この問題の特定の事例に対処するものである。
ノードが実行可能な列車周期を表すグラフ上での最大ウェイト独立集合 (MWIS) 問題として問題を再構成する。
大規模探索空間の計算複雑性に対処するため,ハイブリッド分割・コンカレントアルゴリズムを提案する。
このアプローチは,古典的手法や量子近似最適化アルゴリズム(QAOA)など,様々な解法を用いて,サブグラフを反復的に選択し,MWIS問題を解く。
従来のシミュレーションと量子デバイス(IQM Emerald)上での実行の両方により評価されたQAOAと比較し,これらの手法とサブグラフサイズに関するスケーリングを解析することにより,アルゴリズムの性能を評価する。
以上の結果から,指数時間近似解法と多項式時間近似解法とのギャップを効果的に橋渡しできることが示唆された。
関連論文リスト
- A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
短期的ハードウェア制限を軽減するために設計されたQAOAの変種であるIterative-QAOAを紹介する。
我々は,Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) のインスタンスをIonQ Forte Generation QPU上でベンチマークする。
反復-QAOAは、評価された全ての問題インスタンスに対して、最適解と高品質でほぼ最適解を見つけるために、しっかりと収束していることがわかった。
論文 参考訳（メタデータ） (2025-10-30T16:14:13Z) - Quantum Annealing for Minimum Bisection Problem: A Machine Learning-based Approach for Penalty Parameter Tuning [0.39325957466009204]
ペナルティパラメータの適応的チューニングのための機械学習に基づく新しいアプローチを提案する。
我々は、最大4,000ノードのランダムに生成されたErdHos-R'enyiグラフの大規模なデータセット上で、我々のアプローチをテストする。
論文 参考訳（メタデータ） (2025-09-23T13:49:18Z) - Evaluating the Practicality of Quantum Optimization Algorithms for
Prototypical Industrial Applications [44.88678858860675]
本稿では,量子近似最適化アルゴリズム (QAOA) と量子断熱アルゴリズム (QAA) の応用について検討する。
我々は,これらの2つのアルゴリズムの性能を,選択した評価指標を用いて,ソリューションの品質の観点から比較する。
論文 参考訳（メタデータ） (2023-11-20T09:09:55Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
量子近似最適化アルゴリズム(Quantum Approximate Optimization Algorithm、QAOA)は、難解な最適化問題を解くことを目的とした、非常に有望な変分量子アルゴリズムである。
この総合的なレビューは、様々なシナリオにおけるパフォーマンス分析を含む、QAOAの現状の概要を提供する。
我々は,提案アルゴリズムの今後の展望と方向性を探りながら,選択したQAOA拡張と変種の比較研究を行う。
論文 参考訳（メタデータ） (2023-06-15T15:28:12Z) - Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
提案されたハイブリッドアルゴリズムは、コスト関数をハミルトニアン問題にエンコードし、回路の複雑さの低い一連の状態によってエネルギーを最適化する。
レベル$p=2,ldots, 6$の場合、予想される近似比をほぼ維持しながら、レベル$p$を1に減らすことができる。
論文 参考訳（メタデータ） (2022-03-01T19:47:16Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - Quantum constraint learning for quantum approximate optimization
algorithm [0.0]
本稿では,探索部分空間を厳しく制約するミキサーハミルトンを学習するための量子機械学習手法を提案する。
学習したユニタリを直接適応可能なアンサッツを使用してQAOAフレームワークにプラグインすることができる。
また,Wasserstein距離を用いた近似最適化アルゴリズムの性能を,制約なしで評価する直感的計量法を開発した。
論文 参考訳（メタデータ） (2021-05-14T11:31:14Z) - TIGER: Topology-aware Assignment using Ising machines Application to
Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
ゲートベースの量子コンピューティングでは、トポロジー的な方法でタスクをゲートにマップすることを目的とするマッピング問題が存在する。
既存のタスクアプローチは、物理最適化アルゴリズムのいずれかに基づいており、異なるスピードとソリューション品質のトレードオフを提供する。
本稿では,Ising マシンを用いてトポロジ対応の代入問題を解くアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-21T19:46:59Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - A Study of Performance of Optimal Transport [16.847501106437534]
本稿では,ネットワークの単純化と拡張パスに基づくアルゴリズムが,数値行列スケーリング法より一貫して優れていることを示す。
古典的なKuhn-Munkresアルゴリズムを改良した新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-03T20:37:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。