T-QARD Harbor

現在使われている信号制御では、局所的にしか渋滞を解消できません。しかし、全体制御の計算量は指数関数的に増大してしまいます。そこで、本論文ではD-Wave2000Qを用いた全体制御手法を提案しています。また、局所制御と比べてどれだけ優位なのかを紹介しています。

医療現場では人の命に関わる業務を行っているため、看護師の勤務の質が厳しく求められています。しかし、看護師の生活の質も守らなければいけないため、勤務表の作成が困難になっています。ナーススケジューリング問題 (Nurse scheduling Problem, NSP)とは、複数の制約の下で看護師に最適なシフトを割り当てる問題です。NSPは1969年以前より研究されており、NP困難であることが知られています。

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

文献情報 概要 組合せ最適化問題の一つであるジョブショップスケジューリング問題を定式化し、これを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）によって表現した。 ナップサック問題とは 導入 ナッ […]