运输管理系统司机最优配送线路问题

背景

运输管理系统(TMS)，从名字可以看出来主要是管理整个供应链的运输任务的系统，包括了配送单据管理部分和配送部分，其中配送部分包含了车辆管理、运费管理、排班、配送线路管理等等。这里只介绍最优配送线路的问题。

每个司机从库存仓库出发，需要配送多个配送点的货物，这些配送点都是随机给出，配送点个数也是随机的，可以说没有规律。所以需要通过算法快速的规划处司机本次配送任务的最优路线。

运输路线列表-1.png

运输路线列表-2.png

提到最优路径算法，首先想到的就是Dijkstra和Floyd算法，不过仔细想一下发现Dijkstra解决的是给出一个起始点到其他所有图中所在点的最短路径，Floyd是所有节点到图中其他节点的最短路径，这条最短路径可能是直达的，可能是需要经过几个中间节点到达，好像跟我们解决的问题不太一样，我们需要解决的是选定一个起始点，必须要都经过图中其他节点的最优路径，通过Dijkstra和Floyd找不到这条路径

又想到了最笨的办法，全排列循环也可以得到想要的结果，那么我们看看全排的运算次数

从上图能够看出来，如果是在少于12个节点的情况下，勉强可以用这种遍历排列组合的方式解决。

可能有同学会说了，咱们不是多核么，还有分布式计算分分钟搞定。。。，好吧当在比指数增长还要快速的全排列的情况下，再多的机器和再多的cpu也是渺小的。所以TSP问题是一个典型的NP-hard问题

上边两种办法都不行，那就寻找别的思路吧，再仔细一想，这是一个典型的动态规划问题。抽象一下看此问题跟(旅行商问题 Travelling salesman problem, TSP)类似，简单说一下就是我要从北京出发去济南、郑州、成都、西安、杭州、上海、广州、贵州等等若干城市旅游，最后回到北京，那么给我一个最合理(距离最短或者花费最低what even，就是最优)的路线

运输-3.jpeg

图是网图，大概齐能看懂意思就好了。
明确问题就好解决了，对于动态规划的问题，一般解决办法都比较多，当然也有适应的场景：分支限界法、动态规划、遗传算法、模拟退火、神经网络等等很多。
如果直接套用旅行商问题的算法，还有有个问题需要解决，就是旅行商问题是从起始点转了一圈又回到起始点，那么针对供应链配送路线问题，是不需要回到起始点的，如果按照回到起始点来算，并不是最优的路线，那么就想了一个办法，虚拟一个起始点A1，这个A1到真正起始点A的距离设置成1，到其他节点的距离设置成一个很大的值，那么在搜索距离的时候肯定是先从A1到A，同时讲其他节点到A1的距离设置成1，那么最终的路线就是一个不需要回到起始点的最优路线，也就是我们想要的最优路线。

这么多算法如何去选择呢？结合现实场景，需要考虑下边几点因素：

节点数不会太多，不超过20个
实现方便，能够快速的工程化落地
属性条件简单(两地之间的最短开车路线距离是权重)，由于一般都是半夜运货，不考虑交通状况，所以一般路线是不变的，只需要通过百度或者高德地图的api来获取到最短驾车最短路线即可。

考虑了一下用比较简单的分支限界法来做测试，发现效果不错，做了压测(模拟20多个节点计算能够很快出结果，耗时秒级别)，满足要求，那么就上线运行，效果很不错，但是遇到一个问题，平时的运输任务都是少于8个节点，上周日遇到一个16个节点的运输任务，出不来结果了，比较了一下差异，然后就开始排查。

做了一些测试，利用random的模拟数据能够很快速的出结果，但是用实际的作业任务确实出不来，基本上就是进入了死循环模式了。那就只能仔细查看算法了，发现分支限界法对于对称型TSP问题解决很容易，但是对于这种运输任务的TSP问题，几乎退化成了全排列遍历的方式，运算任务巨大，根本出不来结果。

找到问题就解决问题吧，然后选了另外一个相对简单的蚁群算法，在做相应的测试，秒出结果。为了保证结果准确，做了大量对比，由于这个是最优路线(理论上等价于最短路线)，做了平滑上线的处理。

最短路线的问题其实在各个地方都能用到，比如快递配送的最短路线(更多的是快递员通过自己的经验，当然也可以根据算法来)、外卖送餐员的送餐路线(场景更复杂，需要考虑到饭店的饭菜准备时间等等)；供应链也是一个很好的应用场景，很多的供应链公司或者如电商都有自己的配送线路优化，不过这些需要考虑很多的复杂因素。

本公司供应链配送管理随着规模增大，也需要考虑这些类似的问题，需要提供更优的算法来实现

PS：数学是基础