与多名推销员一起旅行的推销员？
我有一个问题已被有效地简化为具有多个推销员的旅行推销员问题。我有一个要从初始位置访问的城市列表，并且必须访问销售人员数量有限的所有城市。
我正在尝试想出一个启发式方法，想知道是否有人可以帮忙。例如，如果我有 20 个城市，有 2 名销售员，我想采取的方法是两步法。首先，将 20 个城市随机分为 10 个城市，每个城市有 2 个推销员，我会发现每个城市的旅行就好像它在几次迭代中是独立的一样。之后，我想交换或分配一个城市给另一个推销员并找到旅行团。实际上，这将是一个 TSP 问题，然后是最小完工时间问题。这样做的问题是速度太慢，并且交换或分配城市的良好邻域生成很困难。
任何人都可以就如何改进上述内容提出建议吗？
编辑：
每个城市的地理位置已知，并且推销员在相同的地方开始和结束。目标是最大限度地减少最大行驶时间，从而使此类问题成为最小完工时间问题。例如，如果 salesman1 需要 10 小时，salesman2 需要 20 小时，则最大行程时间将为 20 小时。
I have a problem that has been effectively reduced to a Travelling Salesman Problem with multiple salesmen. I have a list of cities to visit from an initial location, and have to visit all cities with a limited number of salesmen.
I am trying to come up with a heuristic and was wondering if anyone could give a hand. For example, if I have 20 cities with 2 salesmen, the approach that I thought of taking is a 2 step approach. First, divide the 20 cities up randomly into 10 cities for 2 salesman each, and I'd find the tour for each as if it were independent for a few iterations. Afterwards, I'd like to either swap or assign a city to another salesman and find the tour. Effectively, it'd be a TSP and then minimum makespan problem. The problem with this is that it'd be too slow and good neighborhood generation of swapping or assigning a city is hard.
Can anyone give an advise on how I could improve the above?
EDIT:
The geo-location for each city are known, and the salesmen start and end at the same places. The goal is to minimize the max travelling time, making this sort of a minimum makespan problem. So for example, if salesman1 takes 10 hours and salesman2 takes 20 hours, the maximum travelling time would be 20 hours.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
TSP是一个难题。多 TSP 可能更糟。我不确定您是否可以使用这样的临时方法找到好的解决方案。您尝试过元启发式方法吗？我首先尝试使用交叉熵方法：使用它来解决您的问题应该不会太难。否则寻找通用算法、蚁群优化、模拟退火……
请参阅 Boer 等人的“交叉熵方法教程”。他们解释了如何在 TSP 上使用 CE 方法。针对您的问题的一个简单调整可能是为每个推销员定义不同的矩阵。
您可能想假设您只想找到销售人员之间的最佳城市划分（并将每个销售人员的最短行程委托给经典的 TSP 实现）。在这种情况下，在交叉熵设置中，您考虑每个城市 Xi 出现在推销员 A 的旅行中的概率：P(A 中的 Xi) = pi。然后你在 p = (p1, ... pn) 的空间上工作。 （我不确定它是否会很好地工作，因为您必须解决许多 TSP 问题。）
TSP is a difficult problem. Multi-TSP is probably much worse. I'm not sure you can find good solutions with ad-hoc methods like this. Have you tried meta-heuristic methods ? I'd try using the Cross Entropy method first : it shouldn't be too hard to use it for your problem. Otherwise look for Generic Algorithms, Ant Colony Optimization, Simulated Annealing ...
See "A Tutorial on the Cross-Entropy Method" from Boer et al. They explain how to use the CE method on the TSP. A simple adaptation for your problem might be to define a different matrix for each salesman.
You might want to assume that you only want to find the optimal partition of cities between the salesmen (and delegate the shortest tour for each salesman to a classic TSP implementation). In this case, in the Cross Entropy setting, you consider a probability for each city Xi to be in the tour of salesman A : P(Xi in A) = pi. And you work, on the space of p = (p1, ... pn). (I'm not sure it will work very well, because you will have to solve many TSP problems.)
当你开始谈论多个推销员时，我开始考虑粒子群优化。我使用引力搜索算法在这方面取得了很多成功。这是我发现的一篇涵盖该主题的（冗长的）论文。 http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf
When you start talking about multiple salesmen I start thinking about particle swarm optimization. I've found a lot of success with this using a gravitational search algorithm. Here's a (lengthy) paper I found covering the topic. http://eprints.utm.my/11060/1/AmirAtapourAbarghoueiMFSKSM2010.pdf
为什么不将多个 TSP 转换为传统 TSP？
这是一个众所周知的问题（将多个推销员 TSP 转换为 TSP），您可以找到几篇关于它的文章。
对于大多数转换，您基本上将您的仓库（销售人员开始和结束的地方）复制到多个仓库（在您的情况下为 2），以强制 TSP 返回仓库两次的方式设置边缘权重，然后删除将两个仓库合二为一。
瞧！获得了两分钟成本的旅行，只覆盖了一次顶点。
Why don't you convert your multiple TSP into the traditional TSP?
This is a well-known problem (transforming multiple salesman TSP into TSP) and you can find several articles on it.
For most transformations, you basically copy your depot (where the salesmen start and finish) into several depots (in your case 2), make the edge weights in a way to force a TSP to come back to the depot twice, and then remove the two depots and turn them into one.
Voila! got two min cost tours that cover the vertices exactly once.
我不会开始为如此复杂的问题编写算法（除非那是我的日常工作 - 编写优化算法）。为什么不转向像 http://www.optaplanner.org/ 这样的通用解决方案？您必须定义您的问题，并且该程序使用顶级开发人员花费数年时间创建和优化的算法。
I wouldn't start writing an algorythm for such complicated issue (unless that's my day job - to write optimization algorythms). Why don't you turn to a generic solution like http://www.optaplanner.org/ ? You have to define your problem and the program uses algorithms that top developers took years to create and optimize.
阅读问题描述时，我的第一个想法是使用标准方法来解决推销员问题（通过谷歌搜索合适的方法，因为我实际上从未需要为其编写代码）；然后取出结果并将其分成两半。然后，您的算法可能会决定“一半”在哪里 - 也许是城市的一半，或者可能是基于距离，或者可能是某种组合。或者在结果中搜索两个城市之间的最大距离，并选择该距离作为推销员#1 的最后一个城市和推销员#2 的第一个城市之间的间隔。当然不限于两个推销员，你会分成x块；但总体而言，您的标准 1 推销员 TSP 解决方案应该已经在旅行图中获得了彼此相邻的“附近”城市，因此您不必提出单独的分组算法......
无论如何，我我确信有更好的解决方案，但这对我来说似乎是一个很好的第一个方法。
My first thought on reading the problem description would be to use a standard approach for the salesman problem (googling for an appropriate one as I've never actually had to write code for it); Then take the result and split it in half. Your algorithm then could be to decide where "half" is -- maybe it is half of the cities, or maybe it is based on distance, or maybe some combination. Or search the result for the largest distance between two cities and choose that as the separation between salesman #1's last city and salesman #2's first city. Of course it does not limit to two salesman, you would break into x pieces; But overall the idea is that your standard 1 salesman TSP solution should have already gotten the "nearby" cities next to each other in the travel graph, so you don't have to come up with a separate grouping algorithm...
Anyway, I'm sure there are better solutions, but this seems like a good first approach to me.
看看这个问题（562904） - 虽然与你的不一样，但应该为进一步学习提供一些很好的思考和参考。
Have a look at this question (562904) - while not identical to yours there should be some good food for thought and references for further study.
正如上面的答案中提到的，分层集群解决方案将非常适合您的问题。然而，不要继续分解集群直到找到一条路径，而是在有 n 时停止，其中 n 是您拥有的销售人员数量。您可以通过添加一些“假”停靠点来改进它，以提高如果初始集群过于分散，集群最终与初始目的地均匀分布的可能性。这不是最佳的 - 但您不会为这样的问题获得最佳解决方案。我会创建一个应用程序来可视化问题，然后测试解决方案的许多变体，以了解您的启发式是否足够最佳。
无论如何，我都不会随机化集群，这会导致大多数集群不是最优的。
As mentioned in the answer above the hierarchical clustering solution will work very well for your problem. Instead of continuing to dissolve clusters until you have a single path, however, stop when you have n, where n is the number of salesmen you have. You can probably improve it some by adding in some "fake" stops to improve the likelihood that your clusters end up evenly spaced from the initial destination if the initial clusters are too disparate. It's not optimal - but you're not going to get an optimal solution for a problem like this. I'd create an app that visualizes the problem and then test many variants of the solution to get a feel for whether your heuristic is optimal enough.
In any case I would not randomize the clusters, that would cause the majority of the clusters to be sub-optimal.
刚开始使用遗传算法阅读你的问题就出现在我的脑海中。只需同时使用两种遗传算法，一种可以解决如何为销售员分配城市，另一种可以解决每个销售员的 TSP。
just by starting to read your question using genetic algorithm came to my head. just use two genetic algorithm in the same time one can solve how to assign cities to salesmen and the other can solve the TSP for each salesman you have.