2013年12月08日

巡回セールスマン問題への対応


複数の顧客などを順番に一筆書きのようにまわって戻ってくるのは、巡回セールスマン問題(Traveling Salesman Problem) と呼ばれ、昔からAIなどを使って様々な解法が研究されてきました。

どの解法も最適解を見つけようとすると相当な時間がかかってしまい、システムとして使う場合はあまり有効ではありません。ここで開発したアルゴリズムは最適解に近い答えを高速に計算することができる方法で、インタラクティブなシステムに組み込めるほど短時間に、巡回ルートを求めることができるようになっています。

実際の問題では、担当者が1人とは限らず、複数の担当者が顧客のところへ行ける場合には、まず適切な担当者数を決めて、全顧客をグループ(クラスタ)化するところから始めます。より具体的な問題では、顧客への訪問時間の制約条件なども入るので、もっと複雑になります。

距離と時間と担当者数が最小(最適)になるようにするには、評価関数の取り方も課題になり、何を持って最適というのかを先に考える必要がでてきます。

以下の例は、複数の制約条件を考慮して、巡回セールスマン問題を解けるようにした例です。様々な応用が可能ですが、評価関数や条件を自由に設定できるようなことも考えられるかもしれません。

route.PNG
posted by 開発G at 17:59| Comment(0) | TrackBack(0) | アルゴリズム