文献

J-GLOBAL ID：202302266585481561   整理番号：23A0653917

部分QUBOアニーリングによる複数日旅程最適化問題の解法

クリップ

著者 (4件)： 野口竜弥 (早稲田大 基幹理工) ,  深田佳佑 (早稲田大 大学院基幹理工学研究科) ,  鮑思雅 (早稲田大 大学院基幹理工学研究科) ,  戸川望 (早稲田大 大学院基幹理工学研究科)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2023  号： ITS-92  ページ： Vol.2023-ITS-92,No.4,1-8 (WEB ONLY)  発行年： 2023年03月01日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 複数日旅程最適化問題とは,観光スポットやホテルを巡回する最適な経路を探索する組合せ最適化問題である.一方,組合せ最適化問題を効率よく解法する計算機として実イジングマシンが注目されている.ところが,実イジングマシンはハードウェアの制約により入力できる問題サイズに制限があり,観光スポットやホテルの数が多くなると複数日旅程最適化問題を直接実イジングマシンで解くのが難しくなる.本稿では,複数日旅程最適化問題をイジングモデルと等価なQuadratic Unconstrained Binary Optimization(QUBO)モデルに変換し,QUBOモデルを部分QUBOへ分割することで,複数日旅程最適化問題を求解する手法を提案する.提案手法では,問題全体を表すQUBOモデルから偏差による変数選択とランダムな変数選択を組み合わせて部分QUBOを抽出する.これらの手順を繰り返すことで,複数日程旅程最適化問題の準最適解を得る.提案手法を評価するために,東京周辺の複数日旅程最適化問題を対象に実イジングマシンにより評価実験を行い,既存手法より良い解が得られたことを確認した.(著者抄録)

シソーラス用語： *組合せ最適化問題 ,  Ising模型 ,  *旅行 ,  *経路探索
準シソーラス用語： Isingモデル ,  QUBOモデル ,  実イジングマシン ,  巡回 ,  複数日旅程最適化問題 ,  旅程

分類 (2件)： 運輸交通・サービス一般  (TA01010L) ,  人工知能  (JE08000Z)

引用文献 (17件)：

• Wang, T. and Roychowdhury, J.: Oscillator-based Ising machine, arXiv preprint arXiv:1709.08102 (2017).
• Inagaki, T., Haribara, Y., Igarashi, K., Sonobe, T., Tamate, S., Honjo, T., Marandi, A., McMahon, P. L., Umeki, T. and Enbutsu, K.: A coherent Ising machine for 2000-node optimization problems, Science, Vol. 354, No. 6312, pp. 603-606 (2016).
• Wang, T. and Roychowdhury, J.: OIM: Oscillator-based Ising machines for solving combinatorial optimisation problems, Prod. of International Conference on Unconventional Computation and Natural Computation, Springer, pp. 232-256 (2019).
• Wang, Z., Marandi, A., Wen, K., Byer, R. L. and Yamamoto, Y.: Coherent Ising machine based on degenerate optical parametric oscillators, Physical Review A, Vol. 88, No. 6, p. 063853 (2013).
• Lewis, M. and Glover, F.: Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis, Networks, Vol. 70, No. 2, pp. 79-97(2017).

タイトルに関連する用語 (3件)： アニーリング ,  最適化問題 ,  解法