(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111471121.0 (22)申请日 2021.12.0 3 (71)申请人 上海发网供应链管理有限公司 地址 200000 上海市宝山区呼兰西路10 0号 12号楼 (72)发明人 肖勇民　傅俊　 (74)专利代理 机构 北京方韬法业专利代理事务 所(普通合伙) 11303 代理人 党小林 (51)Int.Cl. G06F 30/20(2020.01) G06F 17/10(2006.01) G06F 119/02(2020.01) (54)发明名称 基于自适应大规模领域搜索算法的车辆路 径问题方法及系统 (57)摘要 本发明提供了一种基于自适应大规模领域 搜索算法的车辆路径问题方法及系统。 该方法包 括： 使用一定的规则构造一个初始解； 基于算子 的权重， 选 择此次迭代过程中使用的ruin算子和 insert算子； 对此次迭代的初始解执行ruin操 作， 使得初始解成为一个不可行解； 对不可行解 执行insert操作， 尽量获得一个可行解； 基于优 化目标函数评估 可行解， 并根据预设策略决定是 否接受该可行解； 重复执行上述操作， 直至达到 终止条件， 并在达到终止条件时， 返回当前找到 的最优解。 本发 明提供的基于自适应大规模领域 搜索算法的车辆路径问题方法及系统能够对车 辆路径问题进行求 解。 权利要求书2页 说明书5页 附图1页 CN 114139392 A 2022.03.04 CN 114139392 A 1.一种基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 包括： 使用一定的规则构造一个初始解； 基于算子的权 重， 选择此次迭代过程中使用的rui n算子和insert算子； 对此次迭代的初始解执 行ruin操作， 使得初始解成为 一个不可 行解； 对不可行解执行insert操作， 尽量获得一个可 行解； 基于优化目标函数评估可 行解， 并根据预设策略决定是否 接受该可行解； 重复执行上述操作， 直至达到终止条件， 并在达到终止条件时， 返回当前找到的最优 解。 2.根据权利要求1所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 初始解、 不可 行解及可 行解具有如下 形式： 3.根据权利要求1所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 车辆 到达客户j的时间由如下公式给 出： 其中， tij表示车辆从客户i到客户j的行驶时间， i,j∈{0,1, …,N}； si表示客户i的服务 (装/卸货)时， i∈{i, …,N}； t0＝0； s0＝0。 4.根据权利要求1所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 待求 解的问题由如下公式给 出： 权　利　要　求　书 1/2 页 2 CN 114139392 A 2ai≤ti≤bi i∈{1， 2， …， N}    (10) 其中， dij表示i到客户j的距离 。 5.根据权利要求4所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 式(3),(4)代 表目标函数， 分别是最短路径长度， 最少车辆数。 6.根据权利要求4所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 式(5)表示派出 车辆的数目不能超过中心仓库所拥有的车辆数。 7.根据权利要求4所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 式(6)确保车辆都是从仓库出发， 并回到 仓库。 8.根据权利要求1所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 式(7)、 (8)保证 每个客户只能被一辆车服 务一次。 9.根据权利要求1所述的基于自适应大规模领域搜索算法的车辆路径问题方法， 其特 征在于， 式(9)定义了车辆容 量约束， 式(10)是时间窗约束。 10.一种基于自适应大规模领域搜索算法的车辆路径问题系统， 其特 征在于， 包括： 一个或多个处 理器； 存储装置， 用于存 储一个或多个程序； 当所述一个或多个程序被所述一个或多个处理器执行， 使得所述一个或多个处理器实 现根据权利要求1至9任意一项所述的基于 自适应大规模领域搜索算法的车辆路径问题方 法。权　利　要　求　书 2/2 页 3 CN 114139392 A 3