大会名称 |
---|
2019年 情報科学技術フォーラム(FIT) |
大会コ-ド |
F |
開催年 |
2019 |
発行日 |
2019-08-20 |
セッション番号 |
5d |
セッション名 |
MPS(2) |
講演日 |
2019/09/04 |
講演場所(会議室等) |
一般教育棟 A棟 A35 |
講演番号 |
A-013 |
タイトル |
容量制約付きp-メディアン問題に対するk-opt局所探索法の性能評価 |
著者名 |
三宅孝史, 片山謙吾, 金原一歩, 岡野傑士, 西原典孝, |
キーワード |
容量制約付きp-メディアン問題, k-opt局所探索法, 組合せ最適化, メタ戦略, 遺伝的アルゴリズム |
抄録 |
災害時の避難計画策定等の重要な応用を有する組合せ最適化問題の1つに容量制約付きp-メディアン問題(CPMP)があげられる.CPMPはp-メディアン問題(PMP)を拡張したものである.これまでにPMPに対する解法の研究は盛んに行われているがCPMPに対する研究はPMPほど多くない.多くの組合せ最適化問題に対する有効な局所探索法にk-opt局所探索法(KLS)が知られている.KLSは可変深度探索のアイデアに基づくアルゴリズムであり,単純な近傍操作を連鎖的に複数回行うことで 生成される解集合を改めて大きな近傍とみなす局所探索法である.本研究ではCPMPに対するKLSを設計し,代表的なメタ戦略である遺伝的アルゴリズム(GA)の枠組みの下で探索性能を評価し,その有効性を示す. |
本文pdf |
PDF download (288.7KB) |