トラベルセールスマン/ビークルルーティングユースケースの最善の実装

Question

解決されるように求められたユースケースが、旅行セールスマン問題/車両ルーティング問題に属する場合、インタビューのケースが最近出ました。私は、実際の問題が何であるか、問題に数学が関与していることを教えてくれました。私は、下記のユースケースがHadoopのMapReduceパラダイム部分を使って解決できることを説明しました。 （ジムリンとクリス・ダイアーによる「本書のデータ集約型テキスト処理」を参照してください）

私はgoogleに関するいくつかの調査を行いました 問題は、（x、y）形式で述べた都市の座標と私がgoogleで見た多くの解決策がユニット距離のような他の要素を考慮しているかどうかを質問されました、負の/正の単位の測定などが含まれますので、私は研究と読書をしましたが、もっと混乱しました。 em。経験豊富な人がこれにいくつかの光を当てることができれば、私の混乱を解消し、より良い方法で解決策を理解することが役に立ちます。

会社はのために最善の最適解を見つけようとしている。インタビューで尋ねた

ユースケース（私はもっと混乱して探検全体のソリューションの海を取得しないように）、または誰かが正しい方向に私を指示することができた場合300人の顧客基盤に12人の従業員を奉仕しています。 彼らは、ビジネスが成長し、顧客の変化の場所、新しい場所が追加されるなどの変化に伴い、顧客の要求をどのように満たすことができるかを示す技術ソリューションを求めています。

問題は基本的に、トラベリングセールスマン問題（TSP）または車両ルーティング問題（VSP）の一形態です。以下のことをここで完了する必要があります。

開始座標は（0,0）で、都市座標の例は以下のとおりです。ここ は、入力としてテキストファイルで提供ワーキング溶液が期待している座標である：

このNP困難問題かそうでない場合は異なる可能性がどのような権利 方法を処理するための正しい方法することができ何

X coordinate Y Coordinate 
420 278 
421 40 
29 178 
350 47 
298 201 
417 186 
378 134 
447 239 
42 114 
45 199 
362 195 
381 243 
429 1 
338 209 
176 9 
364 26 
326 182 
500 129 
190 51 
489 103 
368 142 
132 260 
305 200 
446 137 
375 154 
440 190 
9 118 
437 32 
383 266 

1. 彼らの長所/短所とアプローチ。

2. 解析に基づく問題の多くは、これを解決するために何らかの視覚化を行うことができるため、 です。いくつかのグラフやR /アナリティクスツールのようなもの

さらに詳しい情報が必要な場合や、私が読んで理解しやすい箇所があれば教えてください。私は「事前

Answer 1

で

おかげで何の専門家でありませんが、あなたはちょうどあなたが、すべてをカバーするまで、そのポイントのプロセスを繰り返し、起源と他のすべての点の間の距離を計算し、最も近い点を見つけることができませんでしたポイント？

Answer 2

NP問題を解決する正しい方法はありません。複雑さは指数関数的であるため、簡単な例以外のものには非常に長い時間がかかるでしょう。

しかし、実際の答えにかなり近づく可能性があり、アプリケーションには十分に良い近​​似値があります（最短経路ではなく、その相対的範囲内です）。

wikipedia pageをご確認ください。彼らにはいくつかの例があります。

Answer 3

私はインタビューでこの質問をしました - このpaperに記載されているようなものを提案します。あなたの仕事の処方に最もよく似ています。このホワイトペーパーでは、すべてのセールスマンが1つの点から始まって複数のセールスマンの問題を解決するための最適化された近似アプローチを見つけることができます。特定のセールスマンの自宅/自宅で始まる、個々のトラベルセールスマンのサブ問題を解決することによって、従業員がどこに残っているかを知ることができます（クラスタリングは主要問題を古典的問題に分割します）。

座標の入力だけでなく、場所のグラフがある場合、k-meansをMCLのようなグラフクラスタリングアルゴリズムに置き換えることができます。

Answer 4

実際、ドミトリー（Dmitry）は、これは多重走行セールスマンの事例であると言います。 自然にNP困難であることから、面接者は自然界の最適化アルゴリズムを提案することを当然望んでいます。

私は、この場合のキーは、宛先の数と場所の変更にリアルタイムで更新できるアルゴリズムを探していることだと思います。アリコロニーoptimisaiton（粒子群最適化の形態）は、実際に、最初の紙とウィキペディアを参照して、巡回セールスマン問題のために製剤化した：

https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

「M. Dorigo、V. ManiezzoらA. Colorni、 Antシステム：協力エージェントのコロニーによる最適化、Systems、Man、and Cyber​​neticsのIEEE Transactions - Part B、volume 26、numéro1、pages 29-41、1996。

複数の旅行saleman問題に、その中にいくつかの素晴らしい仕事のために、たとえば、この論文（オープンソース）を参照してくださいので、これは一般化されています：インタビューの状況で

http://www.researchgate.net/publication/263389346_Multi-type_ant_colony_system_for_solving_the_multiple_traveling_salesman_problem

を、それが持っている私は詳しくだろう、 1.効率的な発見的解法であること。 2.グラフ内の両方の変化をリアルタイムに更新することができる。 3.ボーナスポイントについては、in silicoの合理的に効率的な解決策が得られると、ドライバー自体にわずかな確率で経路を割り当てることができ、続いて実際のデータで駆動される最適化を実行することができました。

ドミトリーが示唆したように、検索スペースを最初に減らす問題と比べて、合理的に大量の処理能力が必要になる可能性があります。第二に、もし彼らがあなたに実際に同性愛者を描きたければ、これはインタビューの場面ではかなり難しいかもしれません。

興味深い質問:)