(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111413700.X (22)申请日 2021.11.25 (71)申请人 电子科技大 学 地址 610000 四川省成 都市高新区 （西区） 西源大道 2006号 (72)发明人 殷允强　李冬伟　王杜娟　 (74)专利代理 机构 西安智萃知识产权代理有限 公司 612 21 代理人 方力平 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/08(2012.01) (54)发明名称 一种基于分支定价切割算法的协同配送路 径优化方法 (57)摘要 本发明公开了一种基于分支定价切割算法 的协同配送路径优化方法， 该方法包括以下步 骤： 步骤S1， 建立集合划分模型， 模型建立在可行 车辆无人机协同配送路径的基础上(可行的车辆 无人机协同路径是指在满足客户时间窗、 需求、 车辆/无人机的最大服务时长和载重的路径)， 在 满足每个客户单次服务的基础上， 最小化总配送 成本， 其中总成本包括车辆的固定使用成本F 以 及车辆无人机的配送成本。 步骤S2， 采用基于分 支定价切割的精确 式算法对集合划分模型进行 求解， 得到最优的车辆无 人机协同配送路线。 权利要求书2页 说明书10页 附图2页 CN 114037180 A 2022.02.11 CN 114037180 A 1.一种基于分支定价切割算法的协同配送路径优化方法， 其特 征在于， 包括如下步骤： 步骤S1， 构建车辆无 人机协同配送的集划分模型； 步骤S2， 采用基于分支定价切割的精确式算法对集合划分模型进行求解， 得出最优的 车辆无人机协同配送路线。 2.根据权利要求1所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述集划分模型建立在车辆无人机可行协同配送路径的基础上， 在满足每个客户访问 单次服务的基础上， 最小化总配送成本 。 3.根据权利要求2所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述车辆无人机可行协同配送路径是指在 满足客户时间窗、 需求、 车辆和无人机的最大 服务时长和载重约束的路径。 4.根据权利要求2所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述总配送成本包括车辆的固定使用成本和车辆无 人机的配送成本 。 5.根据权利要求1所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述步骤S2包括： 步骤S21， 采用贪婪算法为原问题构建一个可 行解； 步骤S22， 采用列生成算法求 解主问题(MP)的线性松弛问题； 步骤S23， 判断能否添加有效不 等式； 步骤S23的具体内容如下： 步骤S231， 判断当前解是否为整数解， 若为整数解， 结束步骤S23； 步骤S232， 判断是否存在能够切除当前分子解的有效不等式， 若不存在有效不等式， 结 束步骤S23； 步骤S233， 将有效不 等式添加进受限主问题， 转至步骤S2 2； 步骤S24， 判断经由上述步骤得到的解是否为整数解， 若为整数解， 输出最优解和最优 值， 结束步骤S2； 步骤S25， 结合分支定界框架继续 求解该问题。 6.根据权利要求5所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述步骤S22包括： 步骤S221， 使用商业求解器求解受限制主问题， 取出相应约束的对偶 变量， 表示出所述 对偶变量的检验数； 步骤S222， 使用启发式算法寻找检验数为负的路径； 步骤S223， 使用双向标号 算法寻找检验数为负的路径。 7.根据权利要求5所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 步骤S25包括： 步骤S251， 选择分支变量， 创建两个新的活跃节点； 步骤S252， 选择合 适的搜索策略； 步骤S253， 判断是否存在待求 解的活跃节点， 若不存在活跃节点， 结束步骤S25； 步骤S254， 确定待求 解的活跃节点； 步骤S255， 转至步骤S2 2， 对活跃节点 求解； 步骤S256， 判断该节点的松弛问题是否存在可行解， 若无可行解， 终止对该节点的搜权　利　要　求　书 1/2 页 2 CN 114037180 A 2索， 更改节点的活跃属性， 转至步骤S25 3； 步骤S257， 判断是否满足该节点的目标值大于上界剪枝， 若条件成立， 终止对该节点的 搜索， 更改节点的活跃属性， 转至步骤S25 3； 步骤S258， 判断是否满足整数解； 若满足整数解， 终止对该节点的搜索， 更改节点的活 跃属性； 判断该节点的目标值是否小于全局上界， 若满足则用该节点目标值更新全局上界； 步骤S259， 分支， 转至步骤S251。 8.根据权利要求6所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述步骤S222包括： 步骤S2221， 采用贪婪策略寻找检验数为负的路径， 若找出的路径集合不为空， 则将该 路径添加进受限主问题， 转至步骤S2 21； 步骤S2222， 采用禁忌搜索寻找检验数为负的路径， 若找出的路径集合不为空， 则将该 路径添加进受限主问题， 转至步骤S2 21； 步骤S2223， 采用n g‑路径松弛寻找检验数为负的路径， 若找出的路径集合不为空， 则将 该路径添加进受限主问题， 转至步骤S2 21。 9.根据权利要求8所述的基于分支定价切割算法的协同配送路径优化方法， 其特征在 于， 所述步骤S2223包括： 步骤S22231， 定义每 个客户点的邻域； 步骤S22232， 建立标签结构； 步骤S22233， 迭代地扩展所有可 行的前向标签以生成新的标签； 步骤S22234， 采用占优检验剔除不可能产生 最优解方案的标签； 步骤S22235， 根据标签反向追索出检验数小于 0的路径。 10.根据权利要求6 ‑9所述的基于分支定价切割算法的协同配送路径优化方法， 其特征 在于， 所述 步骤S223包括： 步骤S2231， 建立标签结构， 用标号 表示任意一个从顶 点0到顶点i的部分路径， v(L)＝i表 示该部分路径访问的最后一个顶 点； S(L)表 示已服务的 客户， 以及该部分路径不能继续访问的客户集； q(L)表示该部分路径上客户需求的货物量 之和； t(L)表示该部分路径上车辆在顶点i的最早服务开始时间； 表示该部分路径对应 的检验数； 同理， 用标号 表示任意一个从顶点n+1到顶点j 的部分路径， v(B)＝j表示该部分路径访问的最后一个顶点； S(B)表示已服务的客户， 以及 该部分路径不能继续访问的客户集； q(B)表示该部 分路径上车辆到达顶 点j时的剩余容量； t(B)表示该部分路径上 车辆在顶点j的最晚离开时间； 表示该部分路径对应的检验数； 步骤S2232， 迭代地扩展所有可 行的前向和后向标签以生成新的标签； 步骤S2233， 采用占优检验以剔除不可能产生优化方案的标签； 步骤S2234， 将经 过步骤S2 223后的前后标签串联起 来以获得最优的路线； 步骤S2235， 判断得到的路线是否为空， 若为空结束步骤S223； 反之， 将得到的路线添加 进受限主问题中， 转至步骤S2 221。权　利　要　求　书 2/2 页 3 CN 114037180 A 3