我有一个问题已被有效地简化为具有多个推销员的旅行推销员问题。我有一个要从初始位置访问的城市列表，并且必须访问销售人员数量有限的所有城市。
我正在尝试想出一个启发式方法，想知道是否有人可以帮忙。例如，如果我有 20 个城市，有 2 名销售员，我想采取的方法是两步法。首先，将 20 个城市随机分为 10 个城市，每个城市有 2 个推销员，我会发现每个城市的旅行就好像它在几次迭代中是独立的一样。之后，我想交换或分配一个城市给另一个推销员并找到旅游团。实际上，这将是一个 TSP 问题，然后是最小完工时间问题。这样做的问题是速度太慢，并且交换或分配城市的良好邻域生成很困难。
任何人都可以就如何改进上述内容提出建议吗？
EDIT:
每个城市的地理位置都是已知的，推销员的起点和终点都是相同的。目标是最大限度地减少最大行驶时间，从而使此类问题成为最小完工时间问题。例如，如果 salesman1 需要 10 小时，salesman2 需要 20 小时，则最大行程时间将为 20 小时。
TSP是一个难题。多 TSP 可能更糟。我不确定您是否可以使用这样的临时方法找到好的解决方案。您尝试过元启发式方法吗？我首先尝试使用交叉熵方法：使用它来解决您的问题应该不会太难。否则寻找通用算法、蚁群优化、模拟退火......
请参阅 Boer 等人的“交叉熵方法教程”。他们解释了如何在 TSP 上使用 CE 方法。针对您的问题的一个简单调整可能是为每个推销员定义不同的矩阵。
您可能想假设您只想找到销售人员之间的最佳城市划分（并将每个销售人员的最短行程委托给经典的 TSP 实现）。在本例中，在交叉熵设置中，您考虑每个城市 Xi 出现在推销员 A 的旅行中的概率：P(A 中的 Xi) = pi。然后你在 p = (p1, ... pn) 的空间上工作。 （我不确定它是否会很好地工作，因为您必须解决许多 TSP 问题。）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
