TSP旅行商问题，多个取件点，可返回，不一定回原点算法

Question

我是一个送货员，我想计算出一日工作的最短路程。
具体：

1. 公司有多个取件点，而我每天早上可以随意选从哪一个取件点开始配送
2. 每一个配送点要送的包裹都有对应的单个或多个取件点（可能一个送货点有来自取件点A和B甚至更多不同地方的包裹要取），要保证去配送的时候手里有对应的包裹（就是之前去过对应包裹的取件点）
3. 可多次去一个送货点
4. 每天不用回到初始点，只要回到任意取件点就行
5. 包裹不限重量，默认去一个取件点就把所有包裹都带上
6. 每日的送货点不会超过250个

背景：之前做了一个GIS系统，需要加上这个送货员功能，目前可以计算两点之间的最短路线，在这里我用的是C++
个人初步搜索：我浏览了网络上的TSP旅行商问题，也大致了解了解法（但不明白原理所以不知道怎么自己修改）。在想是忽略取货问题先找出所有点的最短路径，然后以那个基础上去改进路线比较好，还是这样子算走远了。如果可以的话，那我该怎么优化路径我也不知道。

想问一下在这个条件下该怎么算会更快，谢谢大家

Answer 1

类似于“有限制条件的动态规划旅行商问题”的方法，我们需要定义一个状态 (S, i, p)，其中S是已访问过的顶点集合（包括取件点和送货点），i是当前所在的顶点，p表示当前手中的包裹来源（取件点集合）。转移方程

```
dp[S, i, p] = min(dp[S, i, p], dp[S-{i}, j, p-{i}] + dist(j, i))

```j是S中的一个顶点，且满足以下条件：若i是一个送货点，则j必须是与i对应的取件点之一。在递推的过程中，需要保证p始终包含了当前所在的送货点所需的包裹来源初。始化状态和边界条件。dp[S, i, p]初始化为无穷大（表示不可达）。边界条件为：当S只包含一个顶点（即某个取件点）时，dp[S, i, p]为0，其中i表示该取件点。

最后，遍历所有状态并更新动态规划数组，通过回溯法找到最短路径。
送货点数量不会超过250个，可以试试看这个。