2013年12月08日

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


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

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

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

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

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

route.PNG
posted by 開発G at 17:59| Comment(0) | TrackBack(0) | アルゴリズム
この記事へのコメント
コメントを書く
お名前: [必須入力]

メールアドレス: [必須入力]

ホームページアドレス: [必須入力]

コメント: [必須入力]

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.sakura.ne.jp/tb/82118058
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック