多链路竞合式优化算法

摘要

本发明涉及路径规划方法领域，具体涉及多链路竞合式优化算法，通过利用现有的多种路径规划的算法生成较为稳定可靠的初始的多个底胚方案，同时引入多条相对独立的链路分别对每一个底胚方案进行优化，打破原有方案的部分路线进行局部优化，然后交由评审程序评估效果，进行对比竞赛，无法达到理想效果的方案即行丢弃，转而以其他方案作为底胚方案继续优化。高并发和高起点保障收敛速度，同时引入生命周期管理，底胚达到存活年限亦会被淘汰，以帮助跳出局部最优解。

说明书

技术领域

本发明涉及路径规划方法领域，具体是多链路竞合式优化算法。

背景技术

有行业数据显示我国城配市场超万亿，且每年增幅10％以上，但绝大多数企业仍然依赖人工排线。随着运输需求的增加，一次排线耗费数小时几天已成常态，时效性差，甚至等人工排完，因需求或车辆资源已发生变更导致返工。排线结果不稳定，运输成本不可控，方案所需费用严重依赖排线人员的经验和运气。客户体验差，时间窗要求，同行要求、拆分次数限制、行驶时长限制、途经点限制、拼载延时限制、多车型、多温区等等需求难以面面俱到，排出一个优秀的方案成为一个难以完成的NP难题。即使是借助计算机运算的传统排线算法，比如遗传算法、蚁群算法等，也存在收敛速度慢、容易陷入局部最优的问题，计算时间长和费用节省效果不理想成为影响算法实际应用的两大重要因素。

发明内容

有鉴于此，本发明的目的是提供多链路竞合式优化算法，能够解决背景技术中的问题。

本发明的多链路竞合式优化算法，包括步骤：

底胚方案的快速初始化，采用局部搜索、切平面法、描算法、C-W节约法、由远及近启发聚类和旅行商规划方法快速生成符合时间窗要求、同行要求、拆分次数限制、行驶时长限制、途经点限制、拼载延时限制、多车型和多温区约束条件的初始方案；

使用多个相互独立的优化处理程序单元对多个初始方案进行优化；

使用仲裁程序单元对优化后的多个方案进行评审，并且保留其中的符合评审标准的多个方案；

对每一个底胚方案设置年龄属性，并且在每次底胚方案和优化后的方案得以保留后年龄加n，并设置存活年限m，当底胚方案和优化后的方案的年龄达到存活年限后，则优先采用年龄更小的底胚方案和优化后的方案；

扫描整个路线方案，采用贪心算法，去掉最影响费用和服务效果的路线或者服务点进行重新拼接规划，对局部路线进行调整。

进一步，所述优化处理程序对初始方案的优化遵循局部搜索和贪心算法。

进一步，所述仲裁程序单元的评审标准包括需求满足率、形式时长、运送及时率和时间倍数。

本发明的有益效果是：本发明的多链路竞合式优化算法，通过利用现有的多种路径规划的算法生成较为稳定可靠的初始的多个底胚方案，同时引入多条相对独立的链路分别对每一个底胚方案进行优化，打破原有方案的部分路线进行局部优化，然后交由评审程序评估效果，进行对比竞赛，无法达到理想效果的方案即行丢弃，转而以其他方案作为底胚方案继续优化。高并发和高起点保障收敛速度，同时引入生命周期管理，底胚达到存活年限亦会被淘汰，以帮助跳出局部最优解。

附图说明

为了更清楚地说明本申请实施例的技术方案，下面将对实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本申请的某些实施例，因此不应被看作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其它相关的附图。

图1为本发明的方法流程图；

图2为本发明的实施例的收敛曲线示意图。

具体实施方式

为使本申请实施例的目的、技术方案和优点更加清楚，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本申请实施例的组件可以以各种不同的配置来布置和设计。

因此，以下对在附图中提供的本申请的实施例的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

如图1所示：本实施例的多链路竞合式优化算法，包括步骤：

(1)底胚方案的快速初始化，采用局部搜索(两阶段法)、切平面法、描算法、C-W节约法、由远及近启发聚类和旅行商规划方法快速生成符合时间窗要求、同行要求、拆分次数限制、行驶时长限制、途经点限制、拼载延时限制、多车型和多温区约束条件的初始方案，使得初始化方案就具有很好的经济性和高质量。

(2)使用多个相互独立的优化处理程序单元对多个初始方案进行优化，优化处理程序单元会按优化逻辑各自去对整体的规划线路方案进行局部的删减和添加节点，使整个路径规划往更优的方向进化。总的优化逻辑是遵循局部搜索和贪心算法，局部搜索带有一定的随机性，这样可以增加跳出局部最优找到全局最优的可能性，贪心算法寻找那些对成本影响最大的节点，从原有路径中删除，然后将节点添加到对成本增加最小的路径中。

(3)使用仲裁程序单元对优化后的多个方案进行评审，并且保留其中的符合评审标准的多个方案，评审时要综合计算费用节省情况和客户服务质量，包括硬性指标(如需求满足率、行驶时长等)和软性指标(运送及时率、时间倍数等)。

(4)对每一个底胚方案设置年龄属性，并且在每次底胚方案和优化后的方案得以保留后年龄加n，并设置存活年限m，当底胚方案和优化后的方案的年龄达到存活年限后，则优先采用年龄更小的底胚方案和优化后的方案，设置合理的年龄对收敛结果有很大的影响。

(5)扫描整个路线方案，采用贪心算法，去掉最影响费用和服务效果的路线或者服务点进行重新拼接规划，对局部路线进行调整，使每次调整都往优化效果最好的方向进行。

真实场景和数据下的效果对比：

1、人工排线耗时2天，费用216824.5元。

2、传统局部搜索算法在耗时17小时32分钟左右时费用比人工排线节省10247元，之后不再变化。费用是省了，但收敛慢，计算时间太长。

3、如图2所示，本算法同等环境和配置5秒内生成初始化方案，费用比人工排线节省2823元；精算4分37秒时，费用节省10367.5元；精算10分钟能节省11524.5元；精算20分钟能节省13978元。

从实际数据的对比上看，通过多链路竞合式机制算法的引入，使得收敛速度和费用节省都大幅提升，效果非常理想，完全满足一般企业对大批次排线调度的实用要求。

本发明的多链路竞合式优化算法，通过利用现有的多种路径规划的算法生成较为稳定可靠的初始的多个底胚方案，同时引入多条相对独立的链路分别对每一个底胚方案进行优化，打破原有方案的部分路线进行局部优化，然后交由评审程序评估效果，进行对比竞赛，无法达到理想效果的方案即行丢弃，转而以其他方案作为底胚方案继续优化。高并发和高起点保障收敛速度，同时引入生命周期管理，底胚达到存活年限亦会被淘汰，以帮助跳出局部最优解。

最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的宗旨和范围，其均应涵盖在本发明的权利要求范围当中。