CVRP (容量制約有りの配送計画問題)は、積載容量に制約のある車両で効率よく荷物を配送することを目的とした問題です。CVRPは、NP困難な問題であり、顧客の数が増えると組合せも爆発的に増加するため、全探索を用いて最適解を求めるには限界があります。そのため、古典的な手法では近似解を求めるのが主流です。この論文では、CVRPを小さな問題に分割し、量子アニーリングマシンと古典コンピュータの両方を用いたハイブリッドな手法を用いて解きます。そして、解の質や計算時間について古典的な手法との比較、および量子アニーリングマシン(D-Wave 2000Q)の性能の評価を行っています。

D-Wave Systemsによって開発が行われている量子アニーリングマシンは、組合せ最適化を高速に解くソルバーとして活発な分析が行われています。本論文では、渋滞解消を目的とした自動車の移動経路割当を組合せ最適化問題として定式化します。連続的な経路割当を実現するには最適化の高速性が求められるが、北京首都国際空港近辺における過去のドライブデータを用いてシミュレーションを行った結果、量子アニーリングは有効的な手法の一つであることを示しています。

本記事で紹介する論文では、D-Waveマシンを用いた量子アニーリングにより二値変数制約のついた 非負値行列分解 の手法と顔画像認識に応用した結果を示している。速度性能評価のために、古典的アルゴリズムを用いるGurobiと […]

本記事で取り上げる論文では 迷路 における最短経路を求める問題をイジングスピングラスとして定式化し、D-Wave 2Xを用いて解いた結果を示している。補助ツールとして、問題を小問題に分割し、D-Waveマシンのキメラグラ […]

与えられたグラフを, 切断する辺の数を最小にしていくつかの部分グラフに分割する（最小カット問題） グラフ分割問題 をイジングスピングラス表現で定式化し, D-Wave 2Xにより解いた。グラフ分割問題 はKarpの21の […]

文献情報 タイトル Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management 著者 Tobia […]

文献情報 概要 組合せ最適化問題の一つであるジョブショップスケジューリング問題を定式化し、これをD-Wave Twoにより解いた。 問題 ジョブショップスケジューリング問題(JSP:Job Shop Scheduling […]

文献情報 タイトル: Ising formulations of many NP problems 著者: Andrew Lucas (Google Scholar) 書誌情報: Frontiers in Ph […]

文献 概要 あるグラフの部分グラフのうち、それに含まれる任意の二点間に辺があるような部分グラフで最大のものを最大クリークと呼ぶ。与えられたグラフから最大クリークを発見する問題は最大クリーク問題と呼ばれており、これはNP困 […]

文献情報 概要 組合せ最適化問題の類型のひとつにナップサック問題がある。これをIsing模型（変数が1 or -1）と等価な形式であるQUBO形式（変数が1 or 0）によって表現した。 ナップサック問題とは 導入 ナッ […]