问题
因工作需要，开始向算法的深水区迈进，其中就涉及到一种混合整数优化问题：CVRPTW 问题
cvrptw问题示例
顾名思义，CVRPTW 就是指带限制条件和时间窗口约束的车辆路径规划问题，而加入了时间窗口的约束条件后，优化目标已不再是简单的凹凸函数，这就意味着不能使用梯度下降、牛顿法等确定函数方法求解该问题（决策树、神经网络统统用不上了）
如果可以将CVRPTW的问题空间可视化的话，想象一下整个场景就是一个“喀斯特地貌”
之前习惯了确定方法求解凹凸问题，突然发现没有“套路”可循后，顿时思维陷入了混乱
而一般的动态规划问题求解器，或者混合整数求解器(google ortools、cplex等)，只能处理小规模(<100)的约束优化问题
而市面上能快速处理1000个节点的求解器已经算是优秀了，但往往都是收费且价格不菲
随着节点数的增长，需要探索的路径，也会呈几何级数增长，所以传统的运筹学求解器，已在性能上无法满足需求
进化算法
EA进化算法 是一类算法的统称（包含遗传算法、粒子群算法、蚁群算法、鱼群算法、蝙蝠算法等等）
通过人工产生上千个种群个体、每一个体探索不同的路径，通过上百次迭代，从而找到帕累托最优解（有限组合方案最优）
进化算法示例
这种设计模式，充分的利用了分析主机多核并行的能力，加快了求解的速度，在性能上能满足大规模全局优化的需求
在解空间较小时，求解速度也很可观，兼顾了求解的准确性
关于进化算法，网上已经有了很详尽的资料，但信息太多反而容易造成信息过载，说多了等于没说
所以进化算法推荐看如下两篇文章就够了：
http://geatpy.com/index.php/2019/07/28/%e7%ac%ac%e4%b8%80%e7%ab%a0%ef%bc%9a%e6%a6%82%e8%bf%b0/
https://www.jianshu.com/p/8fa044ed9267
其他的文章不是摆公式就是摆代码，没什么意思
如果你觉得看这些文章也太麻烦，那我们就来个极简版的白话进化算法入门：
这个世界上总有一类很难搞的问题，乍一看没什么规律，但各种限制，数学家称之为NP hard问题
求解NP hard问题，就只能像探索迷宫一样，在指定的范围内不断探索，速度和方向可能是不断变化的
指定的范围就是搜索空间
而探索可以是多线程的
探索的过程也可以是在之前经验的基础上不断累加的这就是进化算法最直观的理解
不管它套上什么“遗传”、“粒子群”、“蚁群”等等的现实类比的外衣，都改变不了上述工作原理的本质
这样看来，进化算法的原理其实是很简单的
搜索设计
所以整个进化算法应用的关键，就是如何设计搜索空间和搜索行为
搜索空间设计的大小，直接决定了计算量的大小
搜索行为策略设计的好坏，直接决定了系统的搜索效率
搜索设计示例
回到我们最初的话题，CVRPTW 问题该如何设计呢？
谈到具体的问题，网上就很少有相关介绍资料了，设计思想大多隐藏在比较学术论文里，也让我苦恼了一阵子
CVRPTW 搜索设计
有几种主流设计方法：
1.将VRP问题转换为TSP问题，然后所有目标点逐一排列，形成一个庞大的排序空间，例如：[1,2,3,4,5,……]，然后不断随机搜索
显然，这样导致的结果就是会有n!种组合方案，n越大越糟糕，而且没有考虑到TW时间窗口的限制
2.将VRP问题转换为QAP问题，通过就近原则等一系列贪婪规则，形成初始可行解，然后不断随机交换
这样导致的问题也是显而易见的，贪婪规则的主观性很强，很有可能漏掉部分解
一般设计思路示例
我的设计思路：
1.结合上述两种思想，将CVRPTW问题转换为约束优化问题；
2.最大限度的利用约束条件，形成尽可能小的搜索空间；
3.最大限度的减小系统随机性，搜索的每一步都尽可能的命中可行解；
4.在代价和目标之间做一个相对平衡的取舍；总结
说了以上一堆，你也许觉得我啥都没说 :-)
是的，遇到NP hard问题，是没有万金油的，只能自己coding去尝试
关键把握住进化的四个阶段，一切就都清洗了：
1.搜索空间设计；2.搜索策略设计；3.评价方法；4.新搜索空间生成；
对应到术语层面就是：
1.种群初始化；2.基因编码、种群选择；3.评价函数设计；4.交换、变异；
最后推荐两款框架，大家可以自行搜索：deap, geat
https://github.com/geatpy-dev/geatpy
这两款框架都能很方便的实现你想要的进化算法
个人推荐deap,各个模块的设计相对宽松和灵活
遗留问题
1.进化算法的搜索速度：
迭代次数越多，找到的帕累托最优解更好，但很多生产场景其实是没有足够的时间留给模型慢慢摸索的
我也在不断尝试加速的可能
之前研究了AlphaGo及AlphaZero等技术，发现也是不能应用的，毕竟下棋或游戏是确定性策略的动作，而车辆路径中的上车点却是不确定的
2.进化算法的计算规模：
不管进化算法怎么迭代，总会受到计算规模的限制，缩小计算规模是是重中之重的工作
我也在不断寻找有没有可靠的降维策略理论和依据
以上，大家如有更好的解法，也请不吝赐教！
最后，祝大家在NP hard难搞的世界里好运！;->
