tsp目录
- 最简单的实践 juejin.cn/post/684490…
- 最简单的理论 juejin.cn/post/684490…
- 当前tsp的现状 juejin.cn/post/684490…
- 单起点任务分配 juejin.cn/post/684490…
- 多起点任务分配 juejin.cn/post/684490…
- 更简洁的多起点分配 juejin.cn/post/684490…
- 起点时间窗 juejin.cn/post/684490…
- 终点时间窗和hk juejin.cn/post/684490…
- LK简介 juejin.cn/post/684490…
- tsp系列暂停一下 juejin.cn/post/684490…
货郎担又名旅行商, 英文缩写tsp, 它描述的是这样一个问题: 一个商人从起点出发, 顺序经过所有点之后回到起点的最短路径(哈密尔顿回路)
问题的背景和限制条件
- 作为一家物流公司的CTO, 咱们遇到的第一个问题是: 配送员如何能够在8小时内配送更多的货物, 因此, 寻找一条配送的最短路径就是现实的问题.
- 实际空间的点都用经纬度表示, 因为地图厂商对于大量的查询会收取响应的费用, 更为关键的是每次对于地图厂商的接口调用都会形成相当的时间开销, 这个是配送系统无法忍受的. 因此只能采用直线距离或者直角距离(又名闵可夫斯基一阶距离, 闵可夫斯基是一个伟大的人, 在理论篇会有着重的描写)
- 一个配送员一个时间段(或者说一车)配送的单量大约在20-50之间, 数量级不会大于100.
曲折的解决方案和结论
当时, 我们采用的是蚁群算法, 最终我们抛弃了它, 因为:
- 他的收敛的随机性太大.
- 他的算法精度再某些情况下会特别的有问题, 尤其是点之间的距离差距很大的情况下, 大尺度的点距完全会掩盖掉那些比较近的点之间的线路的优化, 也就是说, 比较近的点之间的线路是混乱的.
当然, 经过简单的一点点修正, 他的精度会大幅提升, 但是, 我们不如用更节省时间和空间的算法来搞定. 比如最远插入法. 本文末尾会再介绍优化算法, 这个优化对于所有的不准确算法都是有用的(其实是一个简单且不充分的LK算法 - 没错就是HLK的基础算法, 用在这种条件下刚刚好)
最远插入法
所以, 这种情况下, 我的建议是使用最远插入法, 最远插入的规则是:
- 找到起点和距离起点最远的点, 如果没有起点, 就找点集中最远的两个点.
- 再找点集中距离这两个点最远的点. 然后判断这个新点插入哪个位置更好.
- 重复找距离已选择点集最远的点, 再判断位置.
- 最后一次点集包含了n-1个点, 外面只有一个点, 因此他要判断n-1次找到最合理的位置.
这个算法的开销: 判断位置=1+2+3+…..(n-1), 总开销=n*n/2, 一个相当快速的多项式时间算法, 可惜他的结果并不是精确解. 具体理由可以参考理论篇.
算法的核心是数据结构, 不给数据结构的算法都是耍流氓, 好怀念上学时看的俄国大叔的算法书, 都是数据结构引领算法的. 这个算法也是一样的, 要达到理论开销, 咱们要解决的核心问题是: 排序以及用什么数据结构去排序. 这里考虑最直观的数据结构矩阵(也就是二维数组)
二维数组d[x][y]存储从x到y的距离, x, y是一维数组配送点的集合.
那么d[0]就是0到所有点的距离的集合(一个数组): d[0][1],d[0][2].....d[0][n]
注意, 深度分析之后, 我们发现, 其实咱们不需要排序, 咱们只需找到最远距离就好了.
1. 在第一步, 我们只需给起点数组排序, 比如起点是0号点, d[0]里面的元素找到最远距离. 这里面比如d[0][5]是最远的.
2. 第二步, 此时我们需要一个数据结构, 保存所有点到我们路径里面的点的距离, 这个用一个键值对就可以了, 再js里面这是一个对象, 比如 var ld={}, 这里面的每个键都是不在路径中的点. 我们目前需要合并d[0]和d[5]里面的距离, 直接保留小(小的才是距离)的那个在ld这个键值对里面.
3. 然后, 再ld里面找到最大的值, 这个值的键就是距离 ( 0, 5), 最远的的那个点, 比如是 3, 然后再把 3 插入到( 0, 5)这个路径里面, 路径建议使用一个链表保存(因为有顺序并且要经常做插入操作).
4. 每一步都是这样的, 每一步都引入一个数组, 然后合并到键值对里面, 拿到距离, 然后, 把距离最远的点跳出来, 插入路径链表里面.
所以这个算法需要的数据结构:
- 距离矩阵, 可以直接使用二维数组.
- 路径距离的键值对, 可以使用js对象(map也可以).
- 生成的路径使用链表, 这个造一个带指针(引用)的对象就可以了, 或者引入一个类似Lodash这样的库.
算法的最终结构要平衡几个方面:
- 数据结构清晰合理(不见得利于理解, 但是一定要保持最简模型).
- 算法快速准确, 保持足够的快速并且足够的精确.
- 整体逻辑和思路简洁, 内聚高, 外延少, 最好能成为一个封闭系统, 外部调用不需要理解他的内部结构.
小数量级情况下最简单的LK交换优化方案
- 蚁群算法搭配这个之后, 最终路径主要是这个算法决定的, 蚁群其实只是给出一个基础的能跑通的就行, 因此蚁群的循环次数甚至可以设为一, 也就是只要能跑出一个通路就OK, 那么既然如此, 为啥要用蚁群这么复杂的方案呢? 直接最远插入就好了.
- 简单的说就是做两次循环, 然后交换点尝试, 贴个代码进来吧:
while(这里设置一个合理的轮次数或者判断标准, 因为每次交换之后都需要再重头尝试交换) {
for (i = 1; i < pointCount - 1; ++i) {
for (j = i + 1; j < pointCount; ++j) {
//这里把i,j两个点交换, 然后计算新的路径总长度.
if (newLength < length) {
//这个把这次成功的交换记录到最终结果.然后开始下一轮尝试
break;
}
}
}
}
