旅行商多个推销员？ [英] Travelling Salesman with multiple salesmen?

问题描述

我有一个问题，得到了有效的降低到旅行商问题有多个推销员。我有个城市的名单，从初始位置访问，并访问所有城市的销售人员数量有限。

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.

我想拿出一个启发，并想知道如果任何人都可以给一只手。举例来说，如果我有20个城市有2个推销员，我以为服用的方法是一种2步骤的方法。首先，随机分为20个城市分成10个城市，每次2业务员，我会发现参观的每一个，如果它是独立的几个迭代。后来，我想无论是交换或分配一个城市到另一个城市业务员，找到旅游。实际上，这将会是一个TSP，然后最小的完工时间问题。这里的问题是，它会是太慢，好邻居代交换或分配一个城市是很难的。

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?

编辑：

在地理位置每个城市是已知的，销售人员开始和结束在同一个地方。的目标是最小化的最大行进时间，使得这种最小完工时间的问题。因此，例如，如果需要salesman1 10小时，salesman2需要20个小时，最大行进时间是20小时。

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.

推荐答案

TSP是一个棘手的问题。多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 ...

这是波尔等人见的教程上的交叉熵值法。他们解释如何使用对TSP的CE方法。简单的适应您的问题可能会定义一个不同的矩阵，每个业务员。

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.

您可能要假设你只需要找到推销员城市之间的最佳分区（和最短的游览为每个业务员委托给一个经典的TSP实现）。在这种情况下，交叉熵的设置，你考虑的概率为每个城市玺是在推销员之旅：P（希在A）=圆周率。而你的工作，对P =空间（P1，... PN）。 （我不知道它会工作得很好，因为你将不得不解决许多TSP问题。）

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.)

这篇关于旅行商多个推销员？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！