巡回セールスマン問題(TSP)はNP困難な組合せ最適化問題のひとつとして盛んに研究が行われている．一方で，車両計画問題（VRP）など，このTSPを現実の問題に適用する試みもいくつか行われており，時間依存TSP（TDTSP）もそのひとつである．この問題においては，都市間のコストが時間によって動的に変化するため，現実世界の渋滞や混雑を反映していると考えられている．しかし，TDTSPについての研究は，国内外において活発には行われていない．
本研究では，このTDTSPに対して動的なコスト変動に追従しやすい蟻コロニー最適化とオリジナルの局所探索法を併用した新しい近似解法を提案する．