講演情報
[4M1-GS-2a-01]多目的巡回問題に対するハイブリッド進化的アプローチ
〇山中 赳瑠1、工藤 史登1、大島 宗哲2、冨澤 眞樹1、遠山 宏明1 (1. 前橋工科大学、2. 育英短期大学)
キーワード：
アークルーティング問題、警察官巡回問題、多目的最適化問題、進化アルゴリズム、遺伝的アルゴリズム
頂点被覆はグラフで表される地域の各道路を警察官（または固定監視カメラ）が移動することなく目視で確認できるような配置とみなせる．著者らは頂点被覆問題に関連した辺の周遊問題である警察官巡回問題（POPP）を導入し，混合グラフ上のPOPPがNP完全であることを示した．近年，POPPをもとに一般化警察官巡回問題（GPOPP）を導入し，進化計算とJayaアルゴリズムを統合したハイブリッドヒューリスティック手法を開発した．本研究は，頂点の接続構造に基づく突然変異操作および分離型Jayaアルゴリズムを導入し，数値実験によりそれらの効果を確認した．