1M-02
遺伝的アルゴリズムによる一般化警察官巡回問題の解法
○工藤史登,遠山宏明,冨澤眞樹(前橋工科大)
我々は2022年に警察官巡回問題(Police Officer Patrol Problem)がNP完全であることを証明した.一般化警察官巡回問題は,この問題をより実用的に拡張した問題であり,道路(含む一方通行)と交差点で表される地域の巡回経路を見つける問題である.このとき,必ず通過して巡回する道路だけでなく,通過しないで目視だけでの巡回も認める.目視により巡回経路を短くできるが,巡回範囲は小さくなってしまう.すなわち,一般化警察官巡回問題は巡回経路の最小化と巡回範囲の最大化を含む2目的最適化問題である.本研究では,この問題に対する遺伝的アルゴリズムを提案し,数値実験により,その有効性を示した.