介護タクシー配車最適化のための巡回セールスマン問題のQUBO定式化手法による性能評価

国内会議 · 2024

介護タクシー配車最適化のための巡回セールスマン問題のQUBO定式化手法による性能評価

Keywords

量子コンピュータ組み合わせ最適化QUBOQAOA複数人時間制約付き巡回セールスマン問題TW-TSP量子近似アルゴリズム制約なし二次形式最適化問題グラフニューラルネットワークGCN運搬経路問題

花園 智行 , 天野 辰哉 , 山口 弘純

研究報告高度交通システムとスマートコミュニティ（ITS）,2024-ITS-97(4),1-8 (2024-05-08) , 2188-8965

Award 優秀論文賞

解説

日本では高齢化が進み、デイサービスなどの介護施設を利用する高齢者が増えている。介護施設へ高齢者を送迎するサービスである介護タクシーは、車両やドライバーの数が限られており、効率的なルート計画が必要になる。また、高齢者の送迎時間は身体の状況によって異なるため、送迎希望時刻の枠内に送迎に行かなければならないという制約もある。
この問題を「時間制約付き巡回セールスマン問題（TW-TSP）」として定式化し、量子コンピュータと古典コンピュータそれぞれで最適なルートの解を得る方法を検討している。
また、量子コンピュータを使ったアプローチではQiskitを使ってTW-TSPを量子回路に変換し、シミュレーターで解を求める実験を行った。小規模なケースでは、従来の方法（CPLEX）と同等の精度でルートを計算できることを確認している。
さらに、古典コンピュータを使ったアプローチでは、2段階で解を求める。グラフ畳み込みネットワーク（GCN）を活用し、高齢者の送迎スケジュールのパターンを学習し、グループ分けを行った開放も検討している。




発表論文:

  • 花園, 智行, 天野, 辰哉, 山口, 弘純 , "複数人複数車両割当問題の制約無し二次形式最適化問題による定式化と量子近似解法の適用", 第31回マルチメディア通信と分散処理ワークショップ論文集, pp.82-89, 2023-10-18, https://ipsj.ixsq.nii.ac.jp/records/228511
  • 花園智行, 天野辰哉, 山口弘純 , "介護タクシー配車最適化のための巡回セールスマン問題のQUBO定式化手法による性能評価", 情報処理学会研究報告(Web), vol.2024, no.DPS-199, 2024 (優秀論文賞), https://ipsj.ixsq.nii.ac.jp/records/233934

関連する研究室活動

関連プロジェクト

地域を支える知のデジタライゼーションと共有基盤

地域を支える知のデジタライゼーションと共有基盤

JST（科学技術振興機構） 戦略的創造研究推進事業 CREST
「基礎理論とシステム基盤技術の融合によるSociety 5.0のための基盤ソフトウェアの創出」領域

Other Research Topics

災害時LoRaネットワークのための環境認識型分散スケジューリング

Yuto Inaba, Tatsuya Amano, Akihito Hiromori, Hirozumi Yamaguchi

2026 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), SPT-IoT 2026, pp. 1366–1371

DOI 10.1109/PerComWorkshops68308.2026.11585469

災害通信LoRa +4

災害現場画像要約のための軽量Vision-Language Model

Hibiki Yoshizaki, Akira Uchiyama, Akihito Hiromori, Mineo Takai, Hirozumi Yamaguchi

2026 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), PerconAI 2026, pp. 1203–1208

DOI 10.1109/PerComWorkshops68308.2026.11585419

セマンティック通信災害対応 +4

物理モデル統合型深層学習による都市の土砂災害予測

Ren Ozeki, Hamada Rizk, Hirozumi Yamaguchi

2026 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), URBSENSE 2026, pp. 1094–1099

DOI 10.1109/PerComWorkshops68308.2026.11585337

土砂災害予測物理モデル統合学習 +3

超大規模衛星群の精密編隊飛行に向けたシミュレーションフレームワーク

Tatsuya Amano, Akihito Hiromori, Hirozumi Yamaguchi, Sumio Morioka

2026 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), PerVehicle , pp. 230–235

DOI 10.1109/PerComWorkshops68308.2026.11585321

衛星編隊飛行分散シミュレーション +4

レイトレーシング駆動型ISACレーダによるパターンベース車両認識

Heetae Jin, Akira Uchiyama

2026 IEEE International Conference on Pervasive Computing and Communications Workshops and other Affiliated Events (PerCom Workshops), PerRad 2026, pp. 328–333

DOI 10.1109/PerComWorkshops68308.2026.11585327

ISACBeyond 5G +4

A Questionnaire-Only Counterfactual Machine Learning Approach to Assess the Spatial Impact of Green Mobility Vehicles in Urban Parks

Rami Naeem, Srikant Manas, Tatsuya Amano, Hirozumi Yamaguchi

ICDCN 2026 Workshop: IWNDSC2026

DOI 10.1145/3737611.3776620