A-013
容量制約付きp-メディアン問題に対するk-opt局所探索法の性能評価

◎三宅孝史・片山謙吾・金原一歩・岡野傑士・西原典孝（岡山理大）

災害時の避難計画策定等の重要な応用を有する組合せ最適化問題の1つに容量制約付きp-メディアン問題(CPMP)があげられる．CPMPはp-メディアン問題(PMP)を拡張したものである．これまでにPMPに対する解法の研究は盛んに行われているがCPMPに対する研究はPMPほど多くない．多くの組合せ最適化問題に対する有効な局所探索法にk-opt局所探索法(KLS)が知られている．KLSは可変深度探索のアイデアに基づくアルゴリズムであり，単純な近傍操作を連鎖的に複数回行うことで 生成される解集合を改めて大きな近傍とみなす局所探索法である．本研究ではCPMPに対するKLSを設計し，代表的なメタ戦略である遺伝的アルゴリズム(GA)の枠組みの下で探索性能を評価し，その有効性を示す．