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

考虑扰动水平和后悔程度的组合优化问题的鲁棒优化

• 批准号: 21K14367
• 负责人: 呉 偉
• 金额: $ 2.41万
• 依托单位: Shizuoka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K14367/
• 关键词: ロバスト最適化; 組合せ最適化; 反復双対置換法; 最大後悔最小化; 発見的解法; 後悔の度合い最小化; 摂動レベル

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

去年，我们提出了0-1组合问题鲁棒优化的通用求解方法（iDS方法），并针对代表性问题进行了大规模实验。今年，我们考虑将 iDS 方法应用于鲁棒旅行商问题。旅行商问题是一个具有许多重要实际例子的问题，但众所周知，该问题很难构造具有多项式大小的0-1整数规划模型，因此迄今为止提出的iDS方法无法应用到它。我们改进和扩展了 iDS 方法，并将其应用于鲁棒旅行商问题。我们还提出了一种核心选择方法作为鲁棒旅行商问题的新启发式，并展示了出色的性能。此外，我们提出了一种处理时间不确定时鲁棒优化问题的多项式时间精确求解方法，针对批量调度问题（单机调度问题的推广）。具体来说，当延迟作业数量的上限为 Γ 时，我们考虑了最大停留时间最小化批量调度问题的并行批量情况和串行批量情况，并在这两种情况下以多项式时间求解。

项目成果

最大納期遅れ最小化基準におけるロバストバッチスケジューリング

具有最大交付延迟最小化标准的稳健批量调度

• 发表时间: 2022
• 作者: 呉偉;梅野慶人;渡邉夢大
• 通讯作者: 渡邉夢大

工事立会者手配問題に対する制約生成法および集合被覆アプローチ

施工见证排列问题的约束生成方法和集合覆盖方法

• 发表时间: 2022
• 期刊: 情報処理学会論文誌 数理モデル化と応用
• 作者: 高須賀将秀;呉偉;柳浦睦憲
• 通讯作者: 柳浦睦憲

多様な最適解の間の推移

各种最优解之间的过渡

• 发表时间: 2022
• 作者: Hirotoshi Honma;Yuya Sato;Yoko Nakajima;市来嵜治，菊地宥人，高木聡，池上 敦子，篠田 心治;加藤尚瑛，池上敦子;加藤尚瑛，呉偉，池上敦子
• 通讯作者: 加藤尚瑛，呉偉，池上敦子

Generating diverse solutions for nurse scheduling

为护士调度生成多样化的解决方案

• 发表时间: 2021
• 作者: N. Katoh;W. Wu;A. Ikegami
• 通讯作者: A. Ikegami

An exact algorithm for the robust serial batching problem to minimize maximum lateness

用于最小化最大延迟的鲁棒串行批处理问题的精确算法

• 发表时间: 2022
• 作者: Keigo Miyagawa;Katsuki Hasegawa;Tang Liang and Wei Wu;Wei Wu and Liang Tang
• 通讯作者: Wei Wu and Liang Tang