algorithm - 多起点和一个终点的旅行商

Question

我正在尝试制作一个 Google map 应用程序，该应用程序涉及从不同位置安排车辆路线。例如，假设有三辆车，每辆车都在不同的位置，它们必须覆盖 10 个位置并到达一个共同的目的地。我需要找到用 3 辆车覆盖所有 10 个点的最佳方法。我知道 Google Directions API 提供了一个“航路点”功能来解决旅行推销员问题，但这仅限于一辆车。我查看了 Vehicle Routing Problem，但无法找到解决我的问题的算法。如果有人能指出正确的方向来解决这个问题，我将不胜感激。

Answer 1

我相信这可以被定义为一个网络流问题并用线性规划来解决。大多数关于线性规划的书籍都解决了这些问题。例如这里有一个 chapter摘自一本关于优化的书

在您的情况下，我会将您的起始位置建模为源，将汽车建模为运输的产品，将城市建模为节点，将单个接收器建模为最终目的地。路线上的权重是距离。

网络流问题的一个特例是“最短路线树问题”(上面引用的论文的第 8 页)，这听起来和您的问题完全一样，只是相反:您从一个公共(public)点开始，然后移动到其他节点。您的问题的解决方案应该是相同的。