物流の今と未来

長年数学者を悩ませるもの

巡回セールスマン問題とは、あるセールスマンが、いくつかの都市を一筆書きで書くように回っていくという条件で、どのような回り方が最短で行けるかという問題があります。

一番確実なのが、すべての組み合わせを試し、その中から最短ルートを探せばよいのですが、実はこれが長年数学者たちを悩ませているのです。なぜなら、すべての組み合わせを求めるのにとてつもない時間が必要なのです。

「そんなものコンピューターに任せればいいじゃん」と思う方もいるでしょう。しかし、回る箇所が30件ぐらいになってくると、いくらコンピューターといえど、すべての組み合わせを求め、それを順番通りにしていくには、100億年以上かかるといわれています。

宇宙が誕生して、まだ137億年経ったぐらいですからとてつもない時間になるのです。

さあ、では組み合わせ数がどのくらい恐ろしいものなのか

試しに表計算ソフト、Microsoft　office365 Excelを使用し、都市数20まで調べてみました。

すると、ある地点で、組み合わせ数が急増していることが、グラフから読み取れると思います。

まるで爆発のごとく数値が増えたので「組み合わせ爆発」などと呼ばれています。

これらの組み合わせすべてを順番に並び替え、そこから最適地を求めようとなると、気が遠くなってしまいます。

では、この問題を解決するにはどうすればよいのでしょうか？

もちろん前述のとおり、一つ一つ調べていくのには、かなりの時間を費やすのこととなるので、私たちが生きている間に解が求まることはないでしょう。

そこで、完璧な一つの解を求めることはできませんが、AIの一種と定義されている「遺伝アルゴリズム」というものを用いることにより、近似解は求めることができます。

では、なぜここで「巡回セールスマン問題」を取り上げたのか。

最近ニュースなどで、近年における、宅配ドライバーへの負担増加などというようなものを聞いたことがあるのではないでしょうか。

そこには、再配達の問題、注文数の増加なども一因となっています。

よって、ドライバー負担軽減には、それらの問題の解決が欠かせないということになります。

そこで着目したのが,遺伝アルゴリズムやAIによる、配達ルートの短縮です。

もちろん。現在の物流業界においても、過去のデータなどをもとにして、ルートの最適化などは行われています。(特に最近ではヤマトが試験的に一部で導入)

そこで私たちが疑問に感じたのは、どのようにすれば良い解(ここではルートの距離)が出せるのではと思いました。

よって今回私たちは、実際に「遺伝アルゴリズム」を使い、どのような方法でそれを改良し、良い解を求められるのか検証してみました。

「遺伝アルゴリズム」とは、読んでその名のごとく生物学における遺伝の仕組みをもとにしております。

つまり、一言で言ってしまえば優秀なデータを様々な方法を使い選択し、それらが生物学上で言うところの、交叉・突然変異を行い、それらを次の世代に引き継ぎ、それらの作業を繰り返していくことで、優秀なデータを作っていく、といったものです。

また、先ほども述べた通り、上の図でいういくつかの親データの選択方法・次の世代のために交叉をどのくらいの割合で行うのか・・・など、「遺伝アルゴリズム」には解を求めるための、様々な学習方法が存在しています。

次の世代のための親データを、字のごとく、適合度に関係なく無作為に選び出すこと

次の世代のための親データを、任意の数で選び出していき、その中から最も適合度が高いものを選び出します。なお、この動作は集団数が得られるまで行われます。

次の世代のための親データを、適合度に比例した割合で選び出すこと

次の世代のビット列のデータが、ある一点を境に入れ替えられること。つまり、2つの親データを元に、データが生成されること。

次の世代のデータが、ランダムに変化されること

ある世代の上位の適合度のデータのうち、どのくらいの割合で、エリート選択や交叉などを起こされず、次の世代へ引き継がれるのかを定めるもの。

まとめ