電車の路線検索に使われる「産業数学」とは

おもしろい事例をご紹介したい。最適化というのは高度な数学を使ったほうがベストのこともあれば、単純な方法がよいこともある。その代表例が「巡回セールスマン問題」だ。たとえば、あなたが営業マンで、100人の顧客を訪問するとしよう。各顧客間の移動にかかる時間は事前に与えられている。要は、どの順番で回れば、最も効率的かという問題である。

100人の顧客を回る順番の組合せは、100の階乗通りある。5の階乗の場合、「5×4×3×2×1＝120通り」ある。100の階乗は、「100×99×……2×1」で、158桁の巨大な整数となる。パソコンを使っても1日でしらみつぶしに計算できるのは、16の階乗通りくらいが限界だ。

そこで「数理最適化」の出番となるのだが、実は中学生にも理解できる方法が有効であることがわかっている。その手法を「局所探索法」と呼ぶ。

具体的には、4つのステップを踏む（図）。
（1）まず任意に巡回路をつくる。
（2）その中から適当に2つの線を選び（赤）、付け替える（青）。
（3）そうして巡回路が短くなれば更新する。
（4）この（2）（3）を巡回路が、それ以上改善できなくなるまで繰り返す。

非常に単純な方法だが、これは高度な数理最適化の手法で時間をかけて求めた真にベストな訪問順（最適解）と比較して、経験的誤差は8％である。つまり、最適解の1.08倍程度の移動時間しかかからない（準最適解）。この局所探索法を使うと、顧客が1000人になっても、準最適解をパソコンであっという間に、数秒で算出することができるのだ。