介護タクシー配車問題に対する量子近似解法とニューラル融合型の数理最適化アルゴリズムの提案
Quantum Approximation Method and Neural-Integrated Mathematical Optimization Algorithm for Elderly Care Taxi Dispatch Problem
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
Other Research Topics
A Digital Twin Approach for Crowd Flow Modeling on Railway Station Platforms
Effective crowd tracking at railway station platforms is essential for ensuring passenger safety and optimizing pedestri...
Efficient Machine Unlearning for Mobility Logs with Spatio-Temporal and Natural-Language Data
Modern mobility platforms store vast streams of GPS trajectories, temporal metadata, free-form textual notes, and other ...
Adaptive Message Scheduling Assisted by Natural Language Processing Models
This study proposes an adaptive message delivery mechanism for a broker in the WMO Information System 2.0 (WIS2.0), a ne...
Indoor Object Recognition with WiFi RSSI-Integrated Visual-Language Models
This study proposes a novel method for automatic object recognition and classification in indoor environments using visu...
Victim Detection Based on Shape Features from 3D Point Clouds
Japan experiences frequent natural disasters, including large-scale earthquakes. As seen in the case of the Great Hanshi...
Map-Aware Super-Resolution GPS Trajectory Reconstruction via Machine Learning
This research aims to realize a novel system for reconstructing high-resolution GPS trajectory data from truncated or lo...