旅行商/车辆路径用例的最佳可能实现

我最近在面试时遇到了一个要求解决的用例属于旅行商问题/车辆路径问题的案例。我能够告诉他们实际问题是什么以及数学涉及到什么问题。我曾经解释过如何使用Hadoop的MapReduce范例部分解决下面提到的用例问题。（解释了如何使用多重映射减少工作能够解决这个问题），使用本书中提到的Graph算法用MapReduce进行数据密集型文本处理（作者：Jimmy Lin和Chris Dyer）旅行商/车辆路径用例的最佳可能实现

出于好奇，我做了一些关于谷歌我可以看到大量的实施和研究已经在不同的口味中解决了这个问题我被问到的问题有（x，y）格式的城市坐标，我在google上看到的很多解决方案都考虑了一些其他因素，比如单位距离，负面/正面的计量单位等等，所以总之我做了更多的研究和阅读，我得到了更多的困惑，

我在这里的问题是对于下面的用例什么是可能的解决方案和什么将是最好的解决方案EM。如果一些有经验的人可以对此有所了解，那么以更好的方式澄清我的困惑并理解解决方案将会很有帮助。或者，如果有人能告诉我到正确的方向（让我不明白的解决方案较为迷茫探索整个海洋）

使用情况，接受采访时问：

的公司是在试图找到最佳的最佳解决方案为12名员工服务他的300名客户群。他们想要一个技术解决方案，告诉他们如何随着业务增长和其他变化（如客户变更的位置，新增地点等）如何满足客户需求。

问题基本上是旅行商问题（TSP）或车辆路径问题（VSP）的一种形式。以下事情需要在这里完成。

起始坐标为（0,0），城市坐标示例如下所述。下面是与工作的解决方案是在文本文件中预期提供作为输入坐标：

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

什么可以处理这个NP-hard问题，或者如果不对方式有什么可以是不同的正确方法他们的优点/缺点的方法。
由于其更多的基于分析的问题可以通过某种形式的可视化来解决这个问题。像一些图表或使用R /分析工具

或者让我知道，如果你需要更多的细节，如果你可以建议在那里我可以阅读和理解更多。

在此先感谢

来源

2015-11-08 user1188611

我不是你要找的专家，所以我也不敢张贴作为回答这个问题过于简单化评论。基本上，你可以描述你的坐标之间的路径，然后找到哈密尔顿周期。许多通用库可以计算这些周期，例如[igraph]（http://stackoverflow.com/questions/26557533/hamiltonian-path-using-igraph）（我不知道hadoop虽然）。 [这个问题]（http://stackoverflow.com/questions/16115942/finding-all-hamiltonian-cycles）是指java中的解决方案。希望能帮助到你。 – lrnzcig

员工人数可能暗示他们希望讨论多个业务场所。“最好”和“最优”都需要一个目标和一些成本函数。 – greybeard

我不是专家，但不能你刚才计算的起源和所有其他点之间的距离，并找到最近的点，然后重复上述过程对于这一点，直到你已经覆盖每点？

来源

2015-11-15 13:36:33 Paul

否。对于某些示例，您可能会收到可怕的结果。你可能会在同一点上来回走动，只是因为下一个比另一个更远。 – Sorin

然后你可以计算所有可能的路径，并采取距离最短的路径？ – Paul

是的，但你有'n！'可能的路径。 – Sorin

解决NP问题没有正确的方法。由于复杂性是指数级的，除了微不足道的例子之外，其他任何事情都需要很长时间。

但是，有近似值可以非常接近真实答案，并且可能对您的应用程序足够好（因为它不是最短路径，但它在它的某个相对范围内）。我们的wikipedia page。他们甚至有一些例子。

来源

2015-11-18 15:16:38 Sorin

据我所知，话题开始有一个mTSP问题。（m - 倍），这些销售人员从不同的角度出发（例如从他们的家庭或家庭办公室）。在这种情况下，我们绝对不会谈论这个问题的最佳解决方案，需要一些近似值。 Wiki页面只包含或多或少古典配方/解决方案。 –

我已经清楚地说明你想说什么。我的问题是，任何人都可以在此提出最佳解决方案。 – user1188611

如果我会在面试时问这个问题 - 我会提出类似于paper中描述的内容，看起来就像是您的任务制定的最佳匹配。在本文中，您将找到优化的近似方法来解决所有销售人员在一个点上开始的多个销售员问题。如果我们通过解决每个单独的旅行推销员子问题（聚类将主要问题分解为经典问题）以及在特定推销员的家庭/家庭办公室开始时知道员工离开哪里，那么可以采用这种方法。

如果我们将地点图作为输入，而不仅仅是坐标 - 我们可以用图像聚类算法（如MCL）替换k-均值。

来源

2015-11-19 23:52:24

与上述其他答案相同的评论，你能否建议对问题的回答问题不建议修改问题，然后回答 – user1188611

“一家公司正在试图找到最佳的最佳解决方案，为12名员工服务他的300客户群”+提到它是TSP的变体。我们有多个“推销员”，这是公司的雇员。它们在逻辑上具有一个或多个“家庭办公室”。他们需要根据TSP的模型访问点。所以，我们有经典的mTSP问题或mTSP，针对不同的销售人员的起点来自您的描述。这只是一个问题。 +如果输入是距离（不是坐标） - 我建议用MCL绘制图形。我没有建议对问题定义进行任何修改。 –

@ user1188611总的来说 - 我真的不理解你的评论。它只是为您的问题提供正式版本的选择，为您提供相关论文。顺便说一句，幸运的是，这个强大的公式（mTSP）完全符合你的描述:) –

事实上，德米特里提到这是一个多旅行商的象征。作为NP-hard，面试官自然会在寻找你建议的heursitic优化算法。

我认为这种情况下的关键是他们正在寻找一种能够实时更新目的地数量和位置变化的算法。蚁群optimisaiton（粒子群优化形式）实际上最初配制用于旅行推销员问题，请参阅纸和Wikipedia：

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

“M.里戈，V. Maniezzo，等A. Colorni，蚂蚁系统：通过合作代理的群体优化，IEEE Transactions on Systems，Man，and Cybernetics-B部分，第26卷，numéro1，第29-41页，1996。

这一点，因为到多个行进推销员问题例如参见本文（开源）的一些不错的工作到它已经被泛化：

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

在接受记者采访时的情况，我会详细它有优点如下：1.是一个有效的启发式解决方案; 2.能够实时更新图表中的两个变化; 3.对于奖励点我提到，一旦已经获得了合理有效的解决方案in silico，驾驶员本身可以以稍微概率的方式分配路线，随后可以执行由真实数据驱动的优化。

与德米特里所说的首先缩小搜索空间的问题相比，缺点是可能需要相当大的处理能力。其次，如果他们希望你实际上制定一个计划，那么在面试的时候这可能会非常具有挑战性。

有趣的问题:)

来源

2015-11-20 16:55:55 samocooper

你给我英文版的问题在我上面的问题。我的问题清楚地表明，如果你能提出不同的解决问题的方法，而不是采用不同的方法来回答我不知道的面试问题。 – user1188611

旅行商/车辆路径用例的最佳可能实现

回答

相关问题