T-QARD Harbor

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

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