ルートの最適化(ちょっとマニアックな話)

こんにちは、開発Gの関口です。

前回は「ルートの最適化」について説明しましたが、今回はそれを少し掘り下げてみたいと思います。

ロジアナ君の「ルートの最適化」機能は、常に最も効率的なルートを計算してくれるかというと実はそうではありません。

当初のルートに比べ、より効率的なルートは計算しますが、最も効率的なルートを計算できないことも多々あるのです。

その理由として、「巡回セールスマン問題」という組合せ最適化問題の中でも有名な難題が存在するためです。

巡回セールスマン問題とは「セールスマンがいくつかの都市を1度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題のことです。

都市数をnとすると、可能な経路の総数はn!/2n通り存在します。

nが小さいときには、全ての組み合わせを調べることができるので最短経路も分かります。

しかしnが大きくなると、この組み合わせの総数は爆発的に増加し、たとえスーパーコンピューターを用いても最適解を求めることが難しくなります。

ロジアナ君も「ピッキング者がいくつかの間口をすべて訪問して出発点まで戻る」というのはこの巡回セールスマン問題と同様の考え方ですね。

最適解のルートを計算しようとすると、図面レイアウトによっては最適解を求めるまで1時間...あるいは1日...あるいは1年...もしかしたら太陽の寿命が尽きても最適解を求めることはできないかもしれません。

そのためロジアナ君では、最適解を求める処理をある一定時間だけ行います。

もし仮に、その時間内で最適解を求められなかった場合は計算途中の中途半端なルートしか取得できません。

しかし、実はこの中途半端なルートはたとえ計算途中であっても必ず元のルートよりも最適化されているのです。

そのため、「ルートの最適化」機能では元のルートよりもかならず最適化されることは保証されます。

巡回セールスマン問題の解法としていくつかの方法があります。

その詳細を話すとあまりに難解すぎるので、それぞれの方法の特徴だけ説明します。

・最近傍検索

　現在位置から最も近い目的地を辿っていく基本的な方法。最適化率はかなり大雑把。

・局所探索法

　基準となる経路の中から適当に二つの辺を選択して、ルートを入れ替えてみる方法。

　その結果として距離が短縮されれば新ルートを採用する。

　ただし、本来はもっと効率的になるルートがあるのに、それ以上入れ替えても最適化されない

　「局所的な最適解」に陥る場合がある

・焼きなまし法

　「局所的な最適解」が起こらないようにした局所探索法の改良バージョン。

　ただし、局所探索法よりも処理が重く短時間だと局所探索法の方がいい結果がでることもある。

ロジアナ君では上記の方法のうち、「最近傍探索」と「局所探索法」を組み合わせた方法を使用しています。

この2つを利用することで現実に近しいルートを求めることができるのです。

次回は「今後ロジアナ君に追加される機能」についてお話させていただきます。