tsp的理论与实践系列(4)单起点的任务分配

面临这样一个问题, 粗略一看就是tsp问题, 你只要保证分配好的所有配送员的总路线最短就可以了. 但是, 实际上, 我们可以简化问题. 这里我们要引入一个前提和一个猜想.

• 前提: tps问题可以和最小生成树对应起来, 对于最小生成树的遍历, 就自动形成一条路径, 而且这条路径可以保证<2倍的最短路径. 因为最小生成树的深度遍历导致走了两边. 而最小生成树本身的总长度肯定小于最短路径. 如下图示意.

• 猜想: 那么我们可以认为, 一组点, 他们的最小生成树比较小, 那么他们的路径在很大的概率上也会比较短.

方案: 我们可以使用最小生成树做订单分配

因为, 最小生成树有好几个多项式时间的算法, 因此, 我们这次不仅仅解决了300单的分配问题, 3000单, 30000单, 都没有问题了. 只要满足单一起点(仓库/发货点)这个条件.

最小生成树的主力算法有两个:

• 克鲁斯卡尔kruskal
• 普利姆prim

我们逐一介绍一下:

克鲁斯卡尔

• 从一个点集中找到最短的路线, 加到树里面,
• 然后剩下的里面继续找最短的, 如果能连在一起就连在一起, 否则就保持森林状态,
• 直到某一个线段加进来之后, 森林里面的最后两棵树也连在一起形成一棵大树, 那么算法停止.

普利姆

• 从一个点集中任意找一段路线, 加到树里面
• 然后, 此时树里面有2个点, 那么查找距离这两个点最近的点, 把他加到树里面.
• 此时树里面有3个点, 再加入离这三个点最近的点.
• 直到所有点都加入, 算法终止.

从描述我们可以看出来, 克鲁斯卡尔的开销要大一些, 因为他要做所有距离的排序, 而普利姆每次都是一个不大的范围里面找最近的一个值. 不过克鲁斯卡尔其实有很大的优化空间, 这里要引入一个概念: 邻域.

• 邻域: 一个点相邻的一个或者多个点组成的一组点就是一个邻域.
• 克鲁斯卡尔可以只保留每个点最近的3-5个距离进行排序, 最终组成树, 不过这样可能形成森林, 但是, 没关系, 最后再补充需要的几个距离就可以了. 这个思路非常有用, 未来的线性规划方案就用到了这个思路.