{"created":"2025-06-11T04:41:49.089857+00:00","id":2000336,"links":{},"metadata":{"_buckets":{"deposit":"a45d6eb5-ee18-46fc-9f16-805153e0545a"},"_deposit":{"created_by":20,"id":"2000336","owner":"20","owners":[20],"pid":{"revision_id":0,"type":"depid","value":"2000336"},"status":"published"},"_oai":{"id":"oai:muroran-it.repo.nii.ac.jp:02000336","sets":["41:227"]},"author_link":[],"control_number":"2000336","item_81_date_granted_17":{"attribute_name":"学位授与年月日","attribute_value_mlt":[{"subitem_dategranted":"2025-03-24"}]},"item_81_degree_grantor_10":{"attribute_name":"学位授与機関","attribute_value_mlt":[{"subitem_degreegrantor":[{"subitem_degreegrantor_language":"ja","subitem_degreegrantor_name":"室蘭工業大学"},{"subitem_degreegrantor_language":"en","subitem_degreegrantor_name":"Muroran Institute of Technology"}],"subitem_degreegrantor_identifier":[{"subitem_degreegrantor_identifier_name":"10103","subitem_degreegrantor_identifier_scheme":"kakenhi"}]}]},"item_81_degree_name_11":{"attribute_name":"学位名","attribute_value_mlt":[{"subitem_degreename":"博士（工学）","subitem_degreename_language":"ja"}]},"item_81_description_7":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"現代社会において，多目的最適化はコスト・品質や効率・環境負荷など，複数の競合する\n評価基準のバランスを取る上で不可欠な手法となっている．特に，意思決定に整数制約が含\nまれる多目的混合整数線形計画問題（MOMILP）は，幅広い領域で応用可能である一方，解探\n索空間が膨大であるため，効率的かつ厳密な解法の開発が重要な課題である．\n従来の進化計算手法は多目的問題に対して計算効率が高いものの，厳密解を保証できな\nいという欠点がある．一方，多目的分枝限定法は厳密解を求められるが，計算コストが大き\nく，実問題への適用が容易ではなかった．\n本論文では，これらの課題を克服するために，分解ベースのアプローチと多目的分枝限定\n法を統合した新しい厳密解法「Multi-Objective Branch-and-Bound based on\nDecomposition（MOBB/D）」を提案する．本手法では，MOMILP を複数の単目的部分問題に分\n割し，重みベクトルに基づく単目的最適化を繰り返すことでパレート最適解集合を構築す\nる．特に，シンプレックス表や切除平面などの探索情報を部分問題間で再利用する戦略を導\n入し，計算コストを削減しながら高品質なパレートフロントの厳密解を得ることを実現し\nた．\n提案手法の有効性を検証するため，数値実験では既存の多目的分枝限定法との比較を行\nい，計算効率と解の質の両面で優位性を示した．さらに，室蘭市のごみ収集問題を対象とし\nた実問題への適用例においても，従来手法と比較して走行距離と住民負担のトレードオフ\nを高い精度で探索できることを確認した．これは，行政や住民など複数の利害関係者が協議\nの上で政策立案を行う場面にも有用であり，EBPM（Evidence-Based Policy Making）の観点\nからも大きな意義を持つ．また，本研究で開発したフレームワークは，重みベクトルの動的\nな設計や探索空間の部分的再定式化など，さらなる機能拡張によって汎用性を高められる\n可能性がある．これにより，より複雑な制約や大規模な実用問題にも対応でき，多目的最適\n化の現場への普及を促進することが期待される．\n以上の成果により，MOBB/D は厳密解法としての妥当性と，多目的最適化に求められる実\n用的な計算効率を両立する新たな手法として位置づけられる．将来的には，探索情報の取捨\n選択や列生成法などのさらなる活用，ならびに非線形計画問題への拡張など，多面的な発展\nが期待される．本研究の知見は，多目的最適化分野全般において，新たな方向性を示すとと\nもに，実問題に対する高度な意思決定支援の可能性を大きく広げるものである．","subitem_description_language":"ja","subitem_description_type":"Abstract"},{"subitem_description":"In modern society, multi-objective optimization plays an indispensable role in\nbalancing multiple competing objectives, such as cost, quality, efficiency, and\nenvironmental impact. Among these problems, multi-objective mixed-integer linear\nprogramming (MOMILP) is particularly relevant due to its applicability across\nvarious domains, although it poses formidable computational challenges.\nEvolutionary computation methods, while effective in handling large-scale and highdimensional\nproblems, cannot guarantee exact solutions. Conversely, multiobjective\nbranch-and-bound methods can offer exact Pareto-optimal solutions but\noften suffer from high computational cost, making them difficult to apply to realworld\nproblems.\nIn this dissertation, we propose a novel approach called Multi-Objective Branchand-\nBound based on Decomposition (MOBB/D), which integrates a decomposition-based\nstrategy with multi-objective branch-and-bound. Specifically, we decompose an\nMOMILP into multiple single-objective subproblems, each parameterized by a weight\nvector. By repeatedly solving these subproblems with exact optimization techniques,\nwe collectively construct the Pareto-optimal solution set. Furthermore, we\nintroduce a key innovation of reusing exploration information, such as simplex\ntables and cutting planes, across the subproblems to significantly reduce overall\ncomputational effort without compromising precision.\nTo validate the effectiveness of MOBB/D, we conducted a series of numerical\nexperiments that compared it with existing multi-objective branch-and-bound\nmethods. Our results demonstrate that MOBB/D not only achieves higher computational\nefficiency but also ensures the quality of its solutions. Additionally, we applied\nthe proposed framework to a real-world case study involving waste collection in\nthe city of Muroran, where we aimed to balance operational efficiency (e.g., total\nvehicle distance) and resident burden (e.g., walking distance to collection points).\nIn this practical setting, MOBB/D successfully identified high-quality Paretooptimal\nsolutions, outperforming conventional methods while remaining feasible for\npolicymakers. This highlights its potential for supporting evidence-based policy\nmaking (EBPM), where multiple stakeholders need to collaboratively explore tradeoffs.\nIn conclusion, MOBB/D offers a new path toward reconciling the computational\ncosts and precision requirements inherent in MOMILP problems, representing a\nsubstantial advancement in multi-objective optimization methodology. Future work\nincludes incorporating additional enhancements such as selective pruning of\nexploration data, column generation techniques, and extending the scope to nonlinear\nor more complex problems. Through these developments, MOBB/D can be expected\nto further broaden its applicability, thereby contributing to more sophisticated\ndecision-making processes in both academic and practical realms. It stands to serve\nas a valuable tool in a wide range of applications, from urban planning and supply\nchain management to healthcare and environmental policy. MOBB/D underscores the\npotential for innovative, decomposition-based exact methods to reshape the\nlandscape of multi-objective optimization.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_81_dissertation_number_13":{"attribute_name":"学位授与番号","attribute_value_mlt":[{"subitem_dissertationnumber":"甲第542号"}]},"item_81_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.15118/0002000336","subitem_identifier_reg_type":"JaLC"}]},"item_81_text_12":{"attribute_name":"学位の種別","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"課程博士"}]},"item_81_text_14":{"attribute_name":"報告番号","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"甲第542号"}]},"item_81_text_15":{"attribute_name":"学位記番号","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"博甲第542号"}]},"item_81_text_16":{"attribute_name":"研究科・専攻","attribute_value_mlt":[{"subitem_text_language":"ja","subitem_text_value":"工学研究科"}]},"item_81_version_type_24":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorAffiliations":[{"affiliationNames":[{"affiliationName":"室蘭工業大学","affiliationNameLang":"ja"},{"affiliationName":"Muroran Institute of Technology","affiliationNameLang":"en"}]}],"creatorNames":[{"creatorName":"下保, 知輝","creatorNameLang":"ja"}],"familyNames":[{"familyName":"下保","familyNameLang":"ja"}],"givenNames":[{"givenName":"知輝","givenNameLang":"ja"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_access","date":[{"dateType":"Available","dateValue":"2025-06-11"}],"filename":"A542.pdf","filesize":[{"value":"4.9 MB"}],"format":"application/pdf","mimetype":"application/pdf","url":{"objectType":"fulltext","url":"https://muroran-it.repo.nii.ac.jp/record/2000336/files/A542.pdf"},"version_id":"e5156d09-77ed-4a27-a957-8958e41f1971"},{"accessrole":"open_access","date":[{"dateType":"Available","dateValue":"2025-06-11"}],"filename":"A542_summary.pdf","filesize":[{"value":"131 KB"}],"format":"application/pdf","mimetype":"application/pdf","url":{"objectType":"abstract","url":"https://muroran-it.repo.nii.ac.jp/record/2000336/files/A542_summary.pdf"},"version_id":"9fca2769-e183-4864-ac44-12ed1ffe7939"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"doctoral thesis","resourceuri":"http://purl.org/coar/resource_type/c_db06"}]},"item_title":"単目的問題への分割に基づく多目的分枝限定法の提案とその応用","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"単目的問題への分割に基づく多目的分枝限定法の提案とその応用","subitem_title_language":"ja"}]},"item_type_id":"81","owner":"20","path":["227"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2025-06-11"},"publish_date":"2025-06-11","publish_status":"0","recid":"2000336","relation_version_is_last":true,"title":["単目的問題への分割に基づく多目的分枝限定法の提案とその応用"],"weko_creator_id":"20","weko_shared_id":-1},"updated":"2025-06-11T06:10:51.016352+00:00"}