情報処理学会 第86回全国大会 会期:2024年3月15日~17日

6K-08
ドローンを用いた地方郵便配達問題に対する、グラフ縮小を用いた発見的解法
○宮川啓吾,呉  偉(静岡大),谢 艾伶,柳浦睦憲(名大)
本研究では,ドローンを用いた地方郵便配達問題(drone rural postman problem, DRPP)を対象とする.従来の地方郵便配達問題の車両と異なり,ドローンは,1. グラフの辺なしでも任意の2点間を直線で移動でき,2. 辺の任意の位置でサービスを開始・終了できる.本研究では,グラフの縮小に基づく発見的解法を提案する.提案手法で得られる実行可能解の長さは,最適値の2倍以内であることを示す.また,計算実験ではベンチマーク問題例の他に,大規模な問題例を生成し,既存研究と比較して短い計算時間でより良い実行可能解を得られることを示す.