(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211085468.6 (22)申请日 2022.09.06 (71)申请人 浙江百世技 术有限公司 地址 310000 浙江省杭州市滨江区江南大 道3850号3楼307室 (72)发明人 周韶宁　张砚冰　张芒粒　丁聪　 诸伊娜　 (74)专利代理 机构 杭州信与义专利代理有限公 司 33450 专利代理师 马育妙 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 考虑路线形状的车辆路径优化方法 (57)摘要 本发明公开了一种考虑路线形状的车辆路 径优化方法， 属于路径规划技术领域。 本发明在 车辆路径规划中考虑了 路线形状， 使得形成的路 径规划方案更容易被调度员和司机接受。 针对现 实中的路线形状要求， 定义了紧凑度和重叠度两 种指标， 通过加权平均的方式与车辆费用结合起 来， 从而将多目标问题转换为单目标问题， 简化 了路径规划算法， 使得路径规划更加高效。 采用 插入算法构造初始解， 可以在较短时间内得到质 量很高的解。 权利要求书2页 说明书8页 附图5页 CN 115470982 A 2022.12.13 CN 115470982 A 1.一种考虑路线形状的车辆路径优化方法， 其特 征在于， 步骤 包括： S1， 收集客户需求及车辆资源信息； S2， 以仓库和每 个客户所在位置为节点， 计算任意节点间的距离； S3， 定义路线形状指标及构建优化目标函数； S4， 使用插入算法构造初始解， 并将所述初始解和所述初始解对应的所述优化目标函 数的目标值作为车辆路径的优化结果。 2.根据权利要求1所述的考虑路线形状的车辆路径优化方法， 其特征在于， 客户需求信 息包括客户编号、 客户地址、 客户地址经度、 客户地址纬度、 货物需求量； 车辆 资源信息包括 车辆类型、 最大装载量、 起 步费和每公里费用。 3.根据权利要求1所述的考虑路线形状的车辆路径优化方法， 其特征在于， 步骤S3中， 构建的所述优化目标函数通过以下公式(1)表达： F＝f+α∑CI+β ∑OI 公式(1) 公式(1)中， F表示所述优化目标函数； f表示车辆执 行各路线产生的总费用； ∑CI表示各路线的紧凑度之和， 所述紧凑度用于表征客户在路线 I围合的区域内的集中 程度； α 表示∑CI在路线优化时所占的权 重； ∑OI表示各路线的重 叠度之和， 所述重 叠度用于表征不同路线覆盖的区域的重 叠程度； β 表示∑OI在路线优化时所占的权 重。 4.根据权利要求3所述的考虑路线形状的车辆路径优化方法， 其特征在于， 步骤S3中， 定义的所述路线 形状指标包括所述紧凑度， 所述路线I的所述紧凑度通过以下公式(2)计算 而得： CI＝∑idist(i,MI)  公式(2) 公式(2)中， CI表示所述路线I的所述紧凑度； i表示所述路线I中的第i个客户节点； MI表示当所述路线I中的客户节点数量N为奇数时， 派送顺序为 的客户节点， 当N为偶 数时， 派送顺序为 的客户节点； dist(i,MI)表示第i个客户节点到中心客户节点MI的距离。 5.根据权利要求3或4所述的考虑路线形状的车辆路径优化方法， 其特征在于， 步骤S3 中， 定义的所述路线形状指标包括所述重叠度， 所述路线I的所述重叠度为所述路线I中的 客户节点 落入到其 他路线覆盖的区域内的次数。 6.根据权利要求1所述的考虑路线形状的车辆路径优化方法， 其特征在于， 步骤S4中， 使用所述插 入算法构造所述优化目标函数的所述初始解的方法步骤具体包括： S41， 记仓库节点 为w， 所有客户节点 集合为C； S42， 从C中选择距离w 最远的客户节点作为种子客户节点cs， 并将其从C中移除； S43， 构建当前路线的途经顺序为w ‑cs‑w的初始路线， 并从可用车辆资源中选择执行当 前路线运输任务的车辆；权　利　要　求　书 1/2 页 2 CN 115470982 A 2S44， 对集合C中的客户节点按照距cs的距离由近及远排序； S45， 按照步骤S44的排序顺序依次检查C中的每个客户， 并判断将该客户的需求货量加 上所述当前路线中的所有客户的需求货量后， 所述当前路线的总需求货量是否大于步骤 S43选定的车辆的最大装载量， 若是， 则判定该客户对应的客户节点cn无法插入到所述当前路线， 并继续检查集合C中 位于该客户的下一个客户； 若否， 则计算将该客户对应的客户节点cn插入到所述当前路线中的最优位置， 并将其插 入到所述 最优位置以更新所述当前路线， 然后将其从C中移除； S46， 从可执行所述当前路线的运输任务的各车辆中， 筛选出最大装载量大于所述当前 路线中各客户节点的总需求货量的车辆， 并从 中选择运输费用最少的车辆作为执行所述当 前路线的运输任务的最终车辆； S47， 判断集 合C是否为空， 若是， 则将步骤S46确定的所述 最终车辆执 行的所述当前路线加入到所述初始解中； 若否， 则返回步骤S42， 构造下一条路线。 7.根据权利要求6所述的考虑 路线形状的车辆路径优化方法， 其特征在于， 步骤S45中， 计算所述 客户节点cn插入到所述当前路线中的所述 最优位置的方法包括 步骤： S451， 对于所述当前路线中的每对相邻的节点ci和cj， 计算将cn插入到ci和cj间的里程 增加值d， 计算方式通过以下公式(3)表达； d＝dist(ci,cn)+dist(cn,cj)‑dist(ci,cj) 公式(3) 公式(3)中， dist(ci,cn)表示ci与cn之间的距离； dist(cn,cj)表示cn与cj之间的距离； dist(ci,cj)表示ci和cj之间的距离； S452， 将cn插入到d最小的ci和cj之间。权　利　要　求　书 2/2 页 3 CN 115470982 A 3