文献

J-GLOBAL ID：202402259117089494   整理番号：24A0174043

補正処理を導入した部分QUBOアニーリングによる複数日旅程最適化

著者 (4件)： 野口竜弥 (早稲田大 大学院基幹理工学研究科) ,  深田佳佑 (早稲田大 大学院基幹理工学研究科) ,  鮑思雅 (早稲田大 大学院基幹理工学研究科) ,  戸川望 (早稲田大 大学院基幹理工学研究科)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 123  号： 258(VLD2023 30-79)  ページ： 37-42 (WEB ONLY)  発行年： 2023年11月08日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 複数日旅程最適化問題とは,複数日に亘って観光スポットやホテルを巡回する最適な経路を探索する組合せ最適化問題である.組合せ最適化問題を効率よく求解する計算機として,量子アニーラやイジングマシンが研究されている.量子アニーラは,組合せ最適化問題をQuadratic Unconstrained Binary Optimization(QUBO)モデルにマッピングすることで問題を求解できるが,ハードウェアの制約により入力できる問題サイズに上限があるため,問題サイズによってはQUBOモデルをそのまま求解することが困難な場合がある.そこで,QUBOモデルを量子アニーラに入力可能なサイズの部分QUBOに分割することで,大きなサイズの組合せ最適化問題を求解することができるが,量子アニーラは必ずしも問題の制約を満たす解を出力するとは限らない.そこで本稿では,量子アニーラによる部分QUBOアニーリングによって複数日旅程最適化問題の制約を満たさない解が得られた場合,問題の制約を満たすように解を補正する補正処理を部分QUBOアニーリング中に導入する手法を提案する.量子アニーラを用いた実験の結果,補正処理の導入により複数日旅程最適化問題の解が改善されることを確認した.(著者抄録)

シソーラス用語： 最適化問題 ,  *量子計算 ,  補正 ,  名所旧跡 ,  観光 ,  *組合せ最適化問題 ,  観光スポット ,  *量子アニーリング

分類 (1件)： 数値計算  (JE02000J)

引用文献 (16件)：

• B. H. Korte, J. Vygen, B. Korte, and J. Vygen, Combinatorial optimization. Springer, 2011, vol. 1, pp. 1-12.
• T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, and K. Enbutsu, “A coherent Ising machine for 2000-node optimization problems,” Science, vol. 354, no. 6312, pp. 603-606, 2016.
• T. Wang and J. Roychowdhury, “Oim: Oscillator-based Ising machines for solving combinatorial optimisation problems,” in Prod. of International Conference on Unconventional Computation and Natural Computation. Springer, 2019, pp. 232-256.
• T. Wang and J. Roychowdhury, “Oscillator-based Ising machine,” arXiv preprint arXiv:1709.08102, 2017.
• N. Mohseni, P. L. McMahon, and T. Byrnes, “Ising machines as hardware solvers of combinatorial optimization problems,” Nature Reviews Physics, vol. 4, no. 6, pp. 363-379, 2022.

タイトルに関連する用語 (3件)： 補正処理 ,  アニーリング ,  最適化