| 大会名称 |
|---|
| 2022年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2022 |
| 発行日 |
| 2022-08-30 |
| セッション番号 |
| 1a |
| セッション名 |
| アルゴリズム [選奨セッション] |
| 講演日 |
| 2022/09/13 |
| 講演場所(会議室等) |
| 12棟-101教室 |
| 講演番号 |
| CA-004 |
| タイトル |
| 最大リグレット最小化巡回セールスマン問題に対する発見的解法 |
| 著者名 |
| 長谷川和樹, 呉 偉, |
| キーワード |
| 巡回セールスマン問題, 最大リグレット最小化, ロバスト最適化, 発見的解法, 反復双対置換法 |
| 抄録 |
| 巡回セールスマン問題（TSP）は代表的なNP困難な組合せ最適化問題として知られている．本研究では各枝のコストに不確かさがあるときの最大リグレット最小化巡回セールスマン問題（MMR-TSP）を対象とする．まず，TSPに対する３つの（混合）整数計画モデルを紹介し，各モデルの下で，MMR-TSPに対する２種類の発見的解法と２種類の厳密解法を説明する．その上で，近似保証のあるシナリオ固定法で初期解を生成し，反復双対置換フレームワークを利用して解を改善していく新たな発見的解法を提案する．計算実験では，既存手法と提案手法の比較を行った上で既存研究で得られた最良値と比較し，提案手法の有用性を確認する． |
| 本文pdf |
| PDF download (309.6KB) |