複数人複数車両割当問題の制約無し二次形式最適化問題による定式化と量子近似解法の適用

• Item type: Symposium(1)
• 公開日: 2023-10-18
• タイトル: 複数人複数車両割当問題の制約無し二次形式最適化問題による定式化と量子近似解法の適用
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: QUBO，QAOA，TW-TSP
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: 花園, 智行; 天野, 辰哉; 山口, 弘純
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 現在の日本では，高齢人口の急速な増加によりデイケアサービスなどの介護施設への需要が高まっ ている.この中で，介護事業者が運営する介護タクシーは，被介護者の自宅から介護施設への移動を補助 する重要なサービスである．しかし，一般に車両数やドライバの数は限られており，また高齢者一人一人 の送迎希望時間は身体の状態などによって異なる場合が多い.このため効率的な送迎ルートの計画と車 両・ドライバの割り当ては重要な課題となっている．本研究では，この問題を時間制約付き巡回セールスマン問題 (TW-TSP) と車両割当問題 (VAP) として定式化し，量子近似解法 (QAOA) により解く手法 を提案する.提案手法では，TW-TSP および VAP を制約無し二次形式最適化問題に変換し，Qiskit ライブラリを用いて量子回路にマッピングする．得られた回路を量子回路シミュレータである Matrix Product State Simulator に入力し解を得る．時間制約付き巡回セールスマン問題においては，ノード数が 3 までの 場合に限り，厳密解と同等の結果を得ることができた．さらに，車両割当問題では，ノード数が 5，ドライ バー数が 2 の場合に解を見つけることができた．
• 書誌情報: 第31回マルチメディア通信と分散処理ワークショップ論文集; p. 82-89, 発行日 2023-10-18
• 出版者 / 言語: ja
• 出版者: 情報処理学会