今天把OR-tools的VRP问题的demo继续完善。
通过查看google的文档后，发现可以通过选择参数，选择使用启发式算法求解VRP问题。
1
采用启发式算法求解的结果：
2
把算法的运行时间限制改为5秒后，发现运行结果与30秒时一致，说明google的算法运行还是很快的。
3
甚至改为3秒还是可以与30秒的结果一致。
当使用OR-tools的默认求解器，设置的工作时长3个工人就可以完成时，得到的方案如下：
4
改为启发式算法，时间限制为3秒时，得到如下方案：
5
当把时间限制改为8秒后，可以得到和默认求解器相同的方案：
6
以上的元启发式算法使用引导式局部搜索（GUIDE_LOCAL_SEARCH）来避开局部最小值，这通常是车辆路由最有效的元启发式搜索。
求解器还有以下方法可以选择：
7
选择AUTOMATIC方式后，12毫秒就得到了最佳解！！！
8
选用模拟退火算法（SIMULATED_ANNEALING）也可以3秒得到最佳解。
9
网友评论