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

谁借莪１个温暖的怀抱￠ 2024-04-17 13:56 41阅读 0赞

> tsp领域的问题, 并不都是tsp问题, 但是, tsp相关的算法一般都能解决, 只要你能为某一个充满个性的问题儿子找到他亲生的解决方案爸爸.

###### 问题概述 ######

1.  作为一家新兴微(蟹)商, 你有一个仓库/发货点, 每天要进行全城配送, 你面临的问题和传统快递业终端网点面临的几乎一样的问题,
2.  区别在于, 传统网点容量有限, 人肉分配是常态, 并且实际上人肉分配是最高效的方案. 但是, 你的微(蟹)商发货, 每天要达到>300单, 如果人肉分配, 那么需要一组人, 大半夜的就开干, 还很容易出现各种问题.
3.  有传统的围栏是一个解决方案, 但是, 他的成本不是最优的, 会导致你在微(蟹)商的竞争中处于劣势.
4.  再考虑一种情况, 你是一个在集散地做配送的物流公司, 如何合理的调度车辆, 成为你最核心的竞争力.

###### 建模和思考 ######

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

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

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

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

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

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

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

我们逐一介绍一下:

克鲁斯卡尔

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

普利姆

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

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

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

###### 这次的算法设计是一次正常的设计: 数据结构引领算法 ######

整体算法的思路是:

*  从起点开始, 用普利姆构造一棵树.
 *  在对这个树的遍历过程中, 按照每个司机的工作量, 拆分这棵树为一段一段的子树.
 *  树分完为止, 或者司机耗尽.

###### 后记: ######

1.  这个分配是非常快速的, 实际测试中可以发现即便在普通的开发机上, 也可以秒分1万单.
2.  貌似我们随手就解决了一个很大的问题, 别急伙伴们, 现实问题永远比数学问题复杂, 我们的系列讲解才刚刚开始.
3.  这个算法最大的感触就是: 没有废的算法, 只有对的算法, 比如我们可以用很多精确算法来做这件事, 但是没必要, 而且, 路径算法直接映射到我们这个分配问题上, 还有很大的困难, 我们需要对问题做转化才行.

> 这篇分享一气呵成, 总共只花了半小时, 因为它起源于我的实际项目, 在复杂的现实问题中, 敏锐的把握了核心业务, 我都佩服自己了. 转载请附上本文链接, 首发掘金.

转载于:https://juejin.im/post/5d1c6dff518825771b04c5ab