時間枠制約付き配送計画問題に対するカオスダイナミックスを用いたメタヒューリスティック解法

摘要

巡回セールスマン問題，二次割当問題などのNP困難な組合せ最適化問題に対して，カオスダイナミックスを用いた解法が良好な解を効率的に探索することが報告されている．そこで本論文では，組合せ最適化問題の一種であり，巡回セールスマン問題の実務的拡張とされる時間枠制約付き配送計画問題に対する，カオスダイナミックスを用いた新たな解法を提案する．まずはじめに，CROSS-exchangeと呼ばれる解探索基盤によるローカルサーチをニューロンの発火?非発火を用いて実現する．次に過去の発火情報を一定期間記憶させることにより，タブーサーチと等価なダイナミックスを実現する．更に，ニューロンモデルをカオスニューロンモデルへと拡張し，カオスニューラルネットワークを形成することにより，カオスダイナミックスを用いた解法を実現する．数値実験の結果，カオスダイナミックスを用いた解法が，時間枠制約付き配送計画問題の良好な解を効率的に探索することを確認した．