情報処理学会 第86回全国大会 会期:2024年3月15日~17日

1L-06
家庭訪問の経路作成に向けた時間枠付き巡回セールスマン問題の拡張
○久保俊幸,小出 武(甲南大)
時間枠付き巡回セールスマン問題とは、いくつかの都市と各都市間の移動時間が与えられたとき、各地点での時間枠を満たしながら、全ての都市を一度ずつ訪問して、最初の都市に戻る巡回路のうち、総移動時間が最小となるものを求める問題である。一方、家庭訪問の経路作成とは、教師が担当学級の全生徒の家庭を訪問期間中に、希望日時を満たしながら訪問する経路のうち、終了時刻が最小になる経路を作成する問題である。本研究では、時間枠付き巡回セールスマン問題を複数日にわたる経路を扱えるように拡張して、家庭訪問の経路作成に対する混合整数計画問題による厳密解法と、焼きなまし法による近似解法を提案する。