WEKO3
アイテム
単目的問題への分割に基づく多目的分枝限定法の提案とその応用
https://doi.org/10.15118/0002000336
https://doi.org/10.15118/00020003368876d8b4-f7fa-428b-9953-d248018d9802
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
A542.pdf (4.9 MB)
|
|
|
|
A542_summary.pdf (131 KB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2025-06-11 | |||||||||
| タイトル | ||||||||||
| タイトル | 単目的問題への分割に基づく多目的分枝限定法の提案とその応用 | |||||||||
| 言語 | ja | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_db06 | |||||||||
| 資源タイプ | doctoral thesis | |||||||||
| ID登録 | ||||||||||
| ID登録 | 10.15118/0002000336 | |||||||||
| ID登録タイプ | JaLC | |||||||||
| アクセス権 | ||||||||||
| アクセス権 | open access | |||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||
| 著者 |
下保, 知輝
× 下保, 知輝
|
|||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | 現代社会において，多目的最適化はコスト・品質や効率・環境負荷など，複数の競合する 評価基準のバランスを取る上で不可欠な手法となっている．特に，意思決定に整数制約が含 まれる多目的混合整数線形計画問題（MOMILP）は，幅広い領域で応用可能である一方，解探 索空間が膨大であるため，効率的かつ厳密な解法の開発が重要な課題である． 従来の進化計算手法は多目的問題に対して計算効率が高いものの，厳密解を保証できな いという欠点がある．一方，多目的分枝限定法は厳密解を求められるが，計算コストが大き く，実問題への適用が容易ではなかった． 本論文では，これらの課題を克服するために，分解ベースのアプローチと多目的分枝限定 法を統合した新しい厳密解法「Multi-Objective Branch-and-Bound based on Decomposition（MOBB/D）」を提案する．本手法では，MOMILP を複数の単目的部分問題に分 割し，重みベクトルに基づく単目的最適化を繰り返すことでパレート最適解集合を構築す る．特に，シンプレックス表や切除平面などの探索情報を部分問題間で再利用する戦略を導 入し，計算コストを削減しながら高品質なパレートフロントの厳密解を得ることを実現し た． 提案手法の有効性を検証するため，数値実験では既存の多目的分枝限定法との比較を行 い，計算効率と解の質の両面で優位性を示した．さらに，室蘭市のごみ収集問題を対象とし た実問題への適用例においても，従来手法と比較して走行距離と住民負担のトレードオフ を高い精度で探索できることを確認した．これは，行政や住民など複数の利害関係者が協議 の上で政策立案を行う場面にも有用であり，EBPM（Evidence-Based Policy Making）の観点 からも大きな意義を持つ．また，本研究で開発したフレームワークは，重みベクトルの動的 な設計や探索空間の部分的再定式化など，さらなる機能拡張によって汎用性を高められる 可能性がある．これにより，より複雑な制約や大規模な実用問題にも対応でき，多目的最適 化の現場への普及を促進することが期待される． 以上の成果により，MOBB/D は厳密解法としての妥当性と，多目的最適化に求められる実 用的な計算効率を両立する新たな手法として位置づけられる．将来的には，探索情報の取捨 選択や列生成法などのさらなる活用，ならびに非線形計画問題への拡張など，多面的な発展 が期待される．本研究の知見は，多目的最適化分野全般において，新たな方向性を示すとと もに，実問題に対する高度な意思決定支援の可能性を大きく広げるものである． |
|||||||||
| 言語 | ja | |||||||||
| 抄録 | ||||||||||
| 内容記述タイプ | Abstract | |||||||||
| 内容記述 | In modern society, multi-objective optimization plays an indispensable role in balancing multiple competing objectives, such as cost, quality, efficiency, and environmental impact. Among these problems, multi-objective mixed-integer linear programming (MOMILP) is particularly relevant due to its applicability across various domains, although it poses formidable computational challenges. Evolutionary computation methods, while effective in handling large-scale and highdimensional problems, cannot guarantee exact solutions. Conversely, multiobjective branch-and-bound methods can offer exact Pareto-optimal solutions but often suffer from high computational cost, making them difficult to apply to realworld problems. In this dissertation, we propose a novel approach called Multi-Objective Branchand- Bound based on Decomposition (MOBB/D), which integrates a decomposition-based strategy with multi-objective branch-and-bound. Specifically, we decompose an MOMILP into multiple single-objective subproblems, each parameterized by a weight vector. By repeatedly solving these subproblems with exact optimization techniques, we collectively construct the Pareto-optimal solution set. Furthermore, we introduce a key innovation of reusing exploration information, such as simplex tables and cutting planes, across the subproblems to significantly reduce overall computational effort without compromising precision. To validate the effectiveness of MOBB/D, we conducted a series of numerical experiments that compared it with existing multi-objective branch-and-bound methods. Our results demonstrate that MOBB/D not only achieves higher computational efficiency but also ensures the quality of its solutions. Additionally, we applied the proposed framework to a real-world case study involving waste collection in the city of Muroran, where we aimed to balance operational efficiency (e.g., total vehicle distance) and resident burden (e.g., walking distance to collection points). In this practical setting, MOBB/D successfully identified high-quality Paretooptimal solutions, outperforming conventional methods while remaining feasible for policymakers. This highlights its potential for supporting evidence-based policy making (EBPM), where multiple stakeholders need to collaboratively explore tradeoffs. In conclusion, MOBB/D offers a new path toward reconciling the computational costs and precision requirements inherent in MOMILP problems, representing a substantial advancement in multi-objective optimization methodology. Future work includes incorporating additional enhancements such as selective pruning of exploration data, column generation techniques, and extending the scope to nonlinear or more complex problems. Through these developments, MOBB/D can be expected to further broaden its applicability, thereby contributing to more sophisticated decision-making processes in both academic and practical realms. It stands to serve as a valuable tool in a wide range of applications, from urban planning and supply chain management to healthcare and environmental policy. MOBB/D underscores the potential for innovative, decomposition-based exact methods to reshape the landscape of multi-objective optimization. |
|||||||||
| 言語 | en | |||||||||
| 学位授与機関 | ||||||||||
| 学位授与機関識別子Scheme | kakenhi | |||||||||
| 学位授与機関識別子 | 10103 | |||||||||
| 言語 | ja | |||||||||
| 学位授与機関名 | 室蘭工業大学 | |||||||||
| 言語 | en | |||||||||
| 学位授与機関名 | Muroran Institute of Technology | |||||||||
| 学位名 | ||||||||||
| 言語 | ja | |||||||||
| 学位名 | 博士（工学） | |||||||||
| 学位の種別 | ||||||||||
| 言語 | ja | |||||||||
| 値 | 課程博士 | |||||||||
| 学位授与番号 | ||||||||||
| 学位授与番号 | 甲第542号 | |||||||||
| 報告番号 | ||||||||||
| 言語 | ja | |||||||||
| 値 | 甲第542号 | |||||||||
| 学位記番号 | ||||||||||
| 言語 | ja | |||||||||
| 値 | 博甲第542号 | |||||||||
| 研究科・専攻 | ||||||||||
| 言語 | ja | |||||||||
| 値 | 工学研究科 | |||||||||
| 学位授与年月日 | ||||||||||
| 学位授与年月日 | 2025-03-24 | |||||||||
| 著者版フラグ | ||||||||||
| 出版タイプ | VoR | |||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||
