本研究ではQUBO定式化された時間制約付き経路最適化問題(STSP : Selective Traveling Salesman Problem)を対象に、アニーリングマシンを活用した効率的な解法を提案する。STSPは、制約条件下で満足度を最大化する最適な経路を求める組合せ最適化問題であり、QUBO定式化により高速に満足度の高い経路を求めることができる。しかし、現在利用可能なソルバーでは扱える変数の数に限りがあり、大規模問題に対しての適応が困難である。本発表では、STSPを「ブロック分割」と「ステップ分割」という2種類のアプローチを用いて問題を分割し、それぞれの性能を評価する。