logo标签列表

多人销售员的旅行推销员问题？

algorithmheuristicstraveling-salesman
31

我有一个问题，它已经被有效地简化为带有多个销售员的旅行商问题。我有一份从初始位置开始访问所有城市的城市列表，并且必须使用有限数量的销售员访问所有城市。

我正在尝试提出一种启发式算法，想知道是否有人能给予帮助。例如，如果我有20个城市和2个销售员，我考虑采用两步方法。首先，随机将20个城市分成每个销售员10个城市的组合，然后对于每个组合独立地进行几次迭代找到其巡回路线。之后，我会交换或重新分配一个城市给另一个销售员并找到新的巡回路线。实际上，这将是一个TSP问题和最小完工时间问题。这个方法的问题是速度太慢，并且交换或重新分配一个城市的良好邻域生成很困难。

有人可以给予关于如何改进上述方法的建议吗？

编辑：

每个城市的地理位置已知，并且销售员在同一地点开始和结束。目标是最小化最大旅行时间，使其成为一种最小完工时间问题。例如，如果销售员1花费10小时，销售员2花费20小时，最大旅行时间将是20小时。

所有的销售员都从同一个城市开始吗？ - Case
1
一些可以改善这个问题的更多信息：您是否拥有城市的地理位置信息，或者它们之间的所有距离？每个销售员的限制是什么？时间、距离？这只是像这样的问题的冰山一角。 - Bork Blatt
@dustin ledezma：刚才我提到的样例距离函数看一下就好了。在我写完第一个句子后，突然想起这个函数，然后就把它写下来作为例子的一部分了。如果这是你的距离函数（虽然在现实世界中不太可能），当你所有的推销员从城市1到城市2，然后到城市3等等，直到经过20个城市回到城市1时，你就会得到最低价格。你也可以只派遣一个推销员。还有一些城市可以让两个推销员旅行时受益，如果他们都去这个城市。我能想出一个例子，但在这里很难解释清楚。 - Ali1S232
@dustin请不要使用多个帐户重新发布您的问题。您想保留哪个帐户？我将把另一个合并到它中。 - Lasse V. Karlsen
1
@dustin 好的，我已经将旧账户合并到这个账户中，并且合并了TSP问题。那里有一个答案我在这里没有看到，所以它被移动了。现在你应该可以访问你的旧问题和旧账户上的任何声望了。此外，如果你还没有提供一些登录数据，你可能希望确保将来不会再次失去你的账户 :) 祝你在解决TSP问题时好运 :) 干杯。 - Lasse V. Karlsen
显示剩余9条评论
8个回答
12

TSP是一个困难的问题，而多TSP可能更加困难。使用像这样的特定方法可能找不到好的解决方案。您尝试过元启发式方法吗？我建议您首先尝试使用交叉熵方法：它应该不难用于您的问题。否则，请寻找通用算法、蚁群优化、模拟退火等。

请参阅Boer等人撰写的“交叉熵方法教程”。他们解释了如何在TSP上使用CE方法。对于您的问题，一个简单的适应方法可能是为每个销售员定义一个不同的矩阵。

您可能希望假设您只想在销售员之间找到最佳城市划分（并将每个销售员的最短路径委托给经典的TSP实现）。在这种情况下，在交叉熵设置中，您考虑每个城市Xi被销售员A包含的概率：P（Xi在A中）= pi。然后您可以在p =（p1，... pn）的空间中工作。（我不确定它会很有效，因为您将不得不解决许多TSP问题。）

元启发式方法正是我正在寻找的。我想尝试在我提到的“迭代”之后使用模拟退火，以期缩小搜索空间。但是，我发现很难找到一个好的邻域生成器来指导搜索。 - dustin ledezma
3
是的，我忘了说“以及粒子群优化”。 - ysdx
2
链接已失效。经过一番搜索，似乎这篇论文已被撤回（我在这里找到了同一作者关于类似主题的一篇论文的撤回通知，发表于2010年：https://ieeexplore.ieee.org/abstract/document/5486167/）。 - Deruijter
2
为什么不把多个旅行商问题转换成传统的旅行商问题呢？这是一个众所周知的问题（将多个旅行商问题转换为旅行商问题），你可以在几篇文章中找到相关内容。对于大多数转换，您只需将起点和终点（即销售员的起始和结束位置）复制到几个起点和终点（在您的情况下为2），以一种方式使边权强迫TSP两次返回起点，然后删除两个起点和终点并将它们变成一个。完成！得到了覆盖顶点的两条最小成本路径。
这可能有效，但问题也在于为仓库选择一个好的拷贝或分区。 - Micromega
2

对于如此复杂的问题，我不会开始编写算法（除非这是我的日常工作——编写优化算法）。为什么不转向像http://www.optaplanner.org/这样的通用解决方案呢？您需要定义您的问题，程序将使用顶级开发人员多年创建和优化的算法。

1
阅读问题描述后，我的第一个想法是使用标准的推销员问题方法（在谷歌上搜索适当的方法，因为我从未真正为此编写过代码）；然后将结果分成两半。你的算法可以决定“一半”在哪里——也许是城市的一半，也许是基于距离，或者可能是某种组合。或者在结果中搜索两个城市之间的最大距离，并选择作为推销员#1的最后一个城市和推销员#2的第一个城市之间的分隔符。当然，这不仅限于两个推销员，你可以将其分成x份；但总体思路是，你的标准1推销员TSP解决方案应该已经将“附近”的城市放在旅行图中相邻的位置，因此你不必想出单独的分组算法... 无论如何，我相信有更好的解决方案，但这对我来说似乎是一个不错的第一步。
1

看看这个问题（562904）-虽然不完全与您的相同，但应该有一些很好的思路和参考资料供进一步研究。

我同意...所提到的层次聚类算法是这种问题的完美启发式算法。 - Case
0
如上面的答案所提到的，分层聚类解决方案非常适合您的问题。然而，与其继续溶解聚类直到只剩下一条路径，不如在有n个销售员时停止，其中n是您拥有的销售员数量。如果初始聚类过于不同，您可以通过添加一些“虚假”站点来改善聚类最终距离初始目的地均匀分布的可能性。这并不是最优解——但对于这样的问题，您不会得到最优解。我建议创建一个可视化问题的应用程序，然后测试许多解决方案的变体，以了解您的启发式是否足够优秀。
无论如何，我都不会随机化聚类，因为这会导致大多数聚类不够优秀。
0

仅仅通过阅读您的问题，我就想到了遗传算法。只需同时使用两个遗传算法，一个可以解决如何将城市分配给销售员，另一个可以为每个销售员解决TSP问题。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接