番茄路径优化系统介绍
番茄路径优化系统的核心算法引擎基于启发式算法开发，具有比较优秀的性能。
大家好，最近消失了一阵子。因为这两周一直在折腾一款产品。事情是这样的，此前搞算法一直是和命令行打交道基本上，搞得心烦，然后前阵子上头条偶然看到一些前端框架做的系统，感觉还挺好看的，也蛮有趣的。于是就跃跃欲试想尝试下新的东西，加上此前不是做了很多算法嘛，有了一定的基础积累，于是想着把算法和UI结合起来，搞款能用的算法产品试试。
1、问题背景
整个项目还是基于VRP的一个背景，处理的问题在涵盖经典VRPTW的基础上，还包括了处理以下约束的能力：
－ 多时间窗（一般由于客户营业休息时间等安排，会允许出现多个配送时间窗）
－ 多车型（涵盖冷链车型和常规车型，大型车辆和小型车辆等，能够进行混合配送）
－ 交通管制约束（有些地方不允许大型的车辆进入，只能安排小型车进行配送）
－ 时间窗为硬时间窗（早到等待，不允许晚到）
－ 客户需求多样化（常规的货物，冷链配送要求的货物）
－ 等等
2、算法性能
系统的核心算法引擎基于启发式算法开发，具有比较优秀的性能。不过口说无凭，将我们的算法和cplex进行对比，首先是小规模算例上的对比（规定了CPLEX求解时间上限为1小时）：
可以看到，相比较cplex而言，我们的算法有以下特点：
小规模算例对比
－ 质量更高：算例（1－7）我们的算法均取得了与CPLEX同样的最优解，在算例（8－11）上我们的算法取得了比CPLEX在1小时内求得的可行解更优的解（表中值越低越好）
－ 时间更快：除了算例1时间略高于CPLEX外，其余算例时间均比CPLEX低。且CPLEX的求解时间随着问题规模增加呈指数增长。当规模变大时，问题的求解时间急剧增加，在现实中很难应用。而我们的算法求解时间随问题规模增长呈线性增长，能够在较快的时间内求解较大规模的问题（分钟级）。
在大规模算例下（客户节点60－200时），我们的算法求解结果与CPLEX在1小时内求得的可行解进行对比：
大规模算例下对比
－相比商业求解器CPLEX在1小时内求得的可行解，我们的算法得出的解成本更低。
－如图所示（时间越少越好），可以看出，在客户规模为60－200的算例下，我们算法的求解时间远低于CPLEX的求解时间。
同时为了弥补启发式算法在求解质量上的不足，我在算法中应用了一种全新的“邻域搜索多样化”技术
相关文章
AIGC热点
热点
-
19打开，有戏
