局所探索と再加熱を伴う焼きなまし法による大学時間割問題について

大学の時間割問題の解法として，焼きなまし法（Simulated Annealing）に局所探索法（Local Search）を導入した効果について検討し，さらに局所解らの脱出のための焼きなまし法の温度の再加熱（Reheating）効果についても報告している．時間割問題は，ITC（International Timetabling Competition）で公開されている例題（Instance）の一部を採用した．結果として，焼きなまし法に局所探索法を組み入れることで，効率よく実行可能な時間割の解が得られることがわかったが，再加熱の効果については特に顕著な効果は認められなかった．また，最適な時間割を得るための結果を，2002 年度のITC参加者の結果と比較すると，全問題数の半数についての比較ではあるが，最良値の場合では上位６位程度の結果になることがわかった．

A method for solving the university timetabling problems by simulated annealing（SA）with local search algorithms and reheating schedules for escaping local minima is presented. Half of the university timetabling instances presented by ITC（International Timetabling Competition）are adopted for evaluating our algorithm. From the experimental results, it is found that SA with local search is effective to obtain a feasible timetable that satisfies the hard constraints of the timetabling, but the reheating schedules are not so effective. Although only half of 20 instances have been used in our experiment, we have compared our results with those of the participants of ITC on the reduction of the penalties of the soft constraints and found that our best result has placed in 6th among the results of ITC2002 participants.