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

Research Note

In Japan, the aging population is increasing, leading to a growing number of elderly individuals utilizing nursing care facilities such as day services. Care taxis, which transport elderly individuals to and from these facilities, face constraints due to the limited number of available vehicles and drivers, necessitating efficient route planning. Additionally, since pickup and drop-off times vary depending on the physical condition of each individual, the service must adhere to specific time windows for transportation.
To address this issue, we formulate the problem as a Time-Window Constrained Traveling Salesman Problem (TW-TSP) and explore methods for obtaining optimal routing solutions using both quantum and classical computers.
In the quantum computing approach, we employ Qiskit to convert the TW-TSP into a quantum circuit and conduct experiments using a simulator to obtain solutions. In small-scale cases, we have confirmed that our method achieves routing accuracy comparable to traditional optimization methods such as CPLEX.
Furthermore, in the classical computing approach, we adopt a two-step solution method. We utilize a Graph Convolutional Network (GCN) to learn scheduling patterns for elderly transportation and explore a grouping-based approach to improve efficiency.

Published Papers:

• 花園, 智行, 天野, 辰哉, 山口, 弘純 , "複数人複数車両割当問題の制約無し二次形式最適化問題による定式化と量子近似解法の適用", 第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