摂動レベルと後悔の度合いを考慮した組合せ最適化問題に対するロバスト最適化

前年度は，0-1組合せ問題のロバスト最適化に対する汎用解法（iDS法）を提案し，代表的な問題に対して大規模実験を行いました．今年度は，ロバスト巡回セールスマン問題へのiDS法の適用を検討しました．巡回セールスマン問題は，重要な実用例が多い問題ですが，多項式サイズの0-1整数計画モデルの構築が困難な問題として知られているため，今まで提案したiDS法の適用ができません．iDS法を改良・拡張し，ロバスト巡回セールスマン問題に適用しました．また，ロバスト巡回セールスマン問題に対する新しい発見的手法として，コア選択法を提案し，優れた性能を示しました．さらに，単一機械スケジューリング問題の一般化であるバッチスケジューリング問題を対象として処理時間が不確定な場合のロバスト最適化問題に対して多項式時間厳密解法を提案しました．具体的には遅延ジョブの発生数の上限がΓのとき，最大滞留時間最小化バッチスケジューリング問題に対して，並列バッチの状況および直列バッチの状況をそれぞれ考慮し，どちらの場合でも多項式時間で解けることを示しました．

前年度は，0-1組合せ問題のロバスト最適化に対する汎用解法（iDS法）を提案し，代表的な問題に対して大規模実験を行いました．今年度は，ロバスト巡回セールスマン問題へのiDS法の適用を検討しました．巡回セールスマン問題は，重要な実用例が多い問題ですが，多項式サイズの0-1整数計画モデルの構築が困難な問題として知られているため，今まで提案したiDS法の適用ができません．iDS法を改良・拡張し，ロバスト巡回セールスマン問題に適用しました．また，ロバスト巡回セールスマン問題に対する新しい発見的手法として，コア選択法を提案し，優れた性能を示しました．さらに，単一機械スケジューリング問題の一般化であるバッチスケジューリング問題を対象として処理時間が不確定な場合のロバスト最適化問題に対して多項式時間厳密解法を提案しました．具体的には遅延ジョブの発生数の上限がΓのとき，最大滞留時間最小化バッチスケジューリング問題に対して，並列バッチの状況および直列バッチの状況をそれぞれ考慮し，どちらの場合でも多項式時間で解けることを示しました．