存在一个可能包含双向边的未加权有向图。有固定数量的推销员。每个销售人员都可以从任何节点开始。每个节点应至少访问一次。我需要尽量减少每个销售人员的路径。我可以用哪种算法来解决这个问题？
此问题是旅行推销员问题(TSP(的变体，称为多重旅行推销员问题，或mTSP。更准确地说，它是MDVRP，用于多个车辆段的车辆路线问题
这个问题是TSP问题的推广，也是NP难问题。
有几种方法可以解决这个问题，每种方法都有其优缺点。这取决于你选择一个。
首先，您必须回答一个简单的问题：您需要一个最优解，还是一个近似值可以接受？如果你的输入相对较大(比如说，几十辆车访问数百个节点(，那么最优算法是不可能的(世界上可能没有足够的能量来计算一个世纪内的最优解(
近似算法可以非常高效，并且可以提出非常好的近似。
当谈到算法时，以下是您可以考虑的算法/方法列表：
- 蛮力：有几辆车和几个节点，它将是完美的。否则，你可以忘记它
- 分支和绑定：这可能是解决一些优化问题的有效方法，但在您的情况下，我不建议将其作为高级解决方案
- 元启发式：这个术语包括一系列非常有效的方法，如局部搜索、遗传算法、模拟退火、蚁群。。。。它们是近似算法，但它们的优势是能够处理非常大的输入，并快速提供不错的近似。它们通常不太难实现，尤其是在图形问题上
- 混合整数线性规划(MILP(：由于mTSP问题可以写成MILP，您可以使用MILP求解器，如CPLEX、Gurobi或LocalSolver来找到解决方案。这种方法有几个优点：考虑到你在数学编程方面有一点经验，它们非常容易编写，而且通常具有非常好的性能。出于几个原因，我建议采用这种方法而不是其他方法。首先，我相信你会得到最好的权衡"工作时间与溶液质量的关系"；。其次，你可以添加一些其他限制(比如说，车辆不应该连续行驶15小时，因为人类驾驶员是人类(。第三，你可以运行求解器一分钟或一小时，这是你的选择。在运行过程中，您会得到越来越好的解决方案，并有一个界限(例如，您会知道您的解决方案最多比最佳解决方案差8.7%，向管理层报告总是很好的(。如果您对此方法有任何疑问，可以在OR stackexchange上询问
- 如果你有足够的专业知识阅读科学论文，有足够的时间和技能去阅读，你可以深入研究文献，编写自己的算法。如果我们谈论的是一家非常大的公司，这将是一个很好的解决方案，在该公司，从该解决方案中获得的每一个百分比都代表着一大笔钱(例如，一家在国家一级拥有数百/数千辆汽车的公司(。如果你决定去做，你可能会得到更好的解决方案，但对于一个经验丰富的小团队来说，这可能需要(至少(几个月的时间。你可以从这项调查开始了解情况(不过要注意，这项调查是14年前的，更好的方法可以在最近的论文中描述(。为了寻找非常相似的问题；MDVRP"；是你的朋友
TL；DR：把你的问题写成MILP，并把它交给求解器。这是TSP变体的最佳权衡，尤其是因为许多求解器都有面向TSP的优化。