社長ヨシアキ成長記録

とらべりんぐ　せーるすまん　ぷろぶれむ。
巡回　セールスマン　問題。

昔なつかし、Operations Researchとかの本を読むと良く出てくるやつです。

セールスマンがいろんなところを訪問するときに、どういう経路をたどるともっとも短い距離で行って帰ってこれるか、を最適化する問題。


オイラーが解いたケーニヒスベルク橋の問題と混同しないでくださいね。


学生時代とかにはORとかは興味があってよく勉強してましたが、それが使われているところってのは間近で見たことがなくて、いまいち実感湧きませんでした。


だいたいがエレガントでないものが多く、コンピューティングのゴリ押しで解決するものばかりです。


Traveling Salesman Problemも数学的に最適解ってものは求められず、ある程度演算したところまでの近似値解でお茶をにごします。


行列の計算なので、対象となる訪問先が増えるとアホほど時間がかかるから仕方がないものと考えるのです。


何でこんなことを書き始めたかというと、使われているところを見ちゃったから。





「白銅」さんの納品書。
非鉄金属なんかを仕入れるときに使ってるサプライヤさんです。


で、

便=332
順番=317

て書いてあります。
写真ピンボケだから読めないですが。

これはどう見てもTraveling Salesman Problemを計算した結果でしょう。

さすが、でかい会社はやることが違う。

白銅さんは自社便で、運送会社をあまり使いません。

商品受け取り時にサインを必要としないので置き逃げ配送できます。

普通の運送会社みたいにサインがもらえないから、配達できなくて予定が立たないということがありません。

そういうノイズの少ない前提条件下なら、計算はしやすいと思われます。

「最適」解ではなくても、会社側は最少のトラック便数ですむし、配送ドライバーは計算結果にもとづいて配達するだけで、効率の良いルートをたどれます。


やるとやらんとではおーくせんまん♪おーくせんまん♪のコストの開きがでますからね。。。

効果さえでれば、エレガントでなくてもかまわん、ということですね。

見習おう、パワーコンピューティングのゴリ押しも悪くない、と。