(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211022593.2 (22)申请日 2022.08.25 (71)申请人 南开大学 地址 300350 天津市津南区同砚路38号 (72)发明人 肖建华　陈亮　肖久红　任红苗　 (74)专利代理 机构 北京高沃 律师事务所 1 1569 专利代理师 万慧华 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06Q 50/06(2012.01) (54)发明名称 一种基于移动充电的电动汽车配送路径规 划方法及系统 (57)摘要 本发明公开一种基于移动充电的电动汽车 配送路径 规划方法及系统， 涉及汽 车路径规划技 术领域， 方法包括： 根据电动汽车集合、 移动充电 车集合、 配送目标点集合、 所电动汽车集合中电 动汽车的配送成本、 移动充电车集合中移动充电 车的供电成本， 构建电动汽车配送路径规划模 型； 结合CW算法和回溯算法， 确定电动汽车配送 路径规划模 型的初始解； 基于电动汽 车配送路径 规划模型的初始解， 引入多种邻域动作， 以构造 邻域结构集； 采用变邻域深度搜索算法对所述邻 域结构集进行局部搜索， 以确定电动汽车配送路 径规划模型的初始解的最优值。 本发 明优化了电 动汽车的配送路径， 降低了 配送成本 。 权利要求书4页 说明书15页 附图2页 CN 115358471 A 2022.11.18 CN 115358471 A 1.一种基于移动充电的电动汽车配送路径规划方法， 其特征在于， 所述电动汽车配送 路径规划方法包括： 获取电动汽车集 合、 移动充电车集 合和配送目标点 集合； 获取所述电动汽车集合中电动汽车的配送成本和所述移动充电车集合中移动充电车 的供电成本； 根据所述电动汽车集合、 所述移动充电车集合、 所述配送目标点集合、 所述电动汽车集 合中电动汽车 的配送成本、 所述移动充电车集合中移动充电车的供电成本， 构建电动汽车 配送路径规划模型； 结合CW算法和回溯算法， 确定所述电动汽车配送路径规划模型的初始解； 所述电动汽 车配送路径规划模型的初始解包括所述电动汽车集合中每个电动汽车的初始配送路径和 所述移动充电车集 合中每个移动充电车的初始供电路径； 基于所述电动汽车配送路径规划模型的初始解， 引入多种邻域动作， 以构造邻域结构 集； 所述邻域动作包括移除邻域动作、 变异邻域动作、 交叉邻域动作和插入邻域动作； 所述 移除邻域动作表示移除任一邻域； 采用变邻域深度搜索算法对所述邻域结构集进行局部搜索， 以确定所述电动汽车配送 路径规划模型的初始解的最优值。 2.根据权利要求1所述的基于移动充电的电动汽车配送路径规划方法， 其特征在于， 所 述电动汽车集合中电动汽车的配送成本包括电动汽车的单位公里成本和电动汽车的单位 发车成本； 所述移动充电车集合中移动充电车的供电成本包括移动充电车的单位 公里成本 和所述移动充电车的单位发车成本； 所述电动汽车配送路径规划模型的目标函数为： 其中， c1表示电动汽车的单位公里成本， c2表示移动充电车的单位公里成本， c1'表示电 动汽车的单位发车成本， c2'表示移动充电车的单位发车成本， dij表示第i个配送目标点到 第j个配送目标点的距离值， K表 示电动汽车集合中电动汽 车总数， M表示移动充电车集合中 移动充电车总数； 为0‑1变量， 当第k个电动汽车经过第i个配送目标点到第 j个配送目标 点时， 当第k个电动汽车未经过第i个配送目标点到第j个配送目标点时， 为0‑1变量， 当第m个移动充电车经过第i个配送目标点到第j个配送目标点， 且第m个移 动充电车为第k个电动汽车提供充电服 务时， 当第m个移动充电车 未经过第i个 配送 目标点到第j个配送目标点， 或者， 第m个移动充电车没有为第k个电动汽车提供充电服务 时， V0'＝V'∪{0}， V'＝V∪R'， V表示配送目标点集合， R'表示允许多次访问的充电 需求点的集合， 所述允许多次访问的充电需求点为移动充电车的任一配送目标点； VN+1'＝ V'∪{N+1}， R0'＝R'∪{0}， RN+1′＝R′∪{N+1}， {N+1}表示作为路径终点的配送中心， {0}表权　利　要　求　书 1/4 页 2 CN 115358471 A 2示作为路径起 点的配送中心。 3.根据权利要求1所述的基于移动充电的电动汽车配送路径规划方法， 其特征在于， 所 述结合CW 算法和回溯算法， 确定所述电动汽车配送路径规划模型的初始解， 具体包括： 采用CW算法， 构造所述电动汽车集 合中每个电动汽车的初始配送路径； 基于所述电动汽车集合中每个电动汽车的充电需求， 利用回溯算法， 确定所述移动充 电车集合中每个移动充电车的初始供电路径。 4.根据权利要求3所述的基于移动充电的电动汽车配送路径规划方法， 其特征在于， 所 述采用CW 算法， 构造所述电动汽车集 合中每个电动汽车的初始配送路径， 具体包括： 获取每个配送目标点的配送信息； 所述配送信 息包括配送需求量、 配送时间窗、 配送时 间和配送位置； 根据所述配送信 息， 计算节约矩阵； 所述节约矩阵包括多个距离节约 值； 所述距离节约 值表示将任意两条配送路径的配送需求量由同一电动汽车进 行配送时节约的距离； 任一所 述配送路径至少包括 一个配送目标点； 对所述节约矩阵中的多个距离节约值进行降序； 将降序后处于第 n位和第n+1位的距离节约值所对应的配送路径进行融合， 以得到配送 子路径； n ＝1； 判断所述配送子路径对应的配送需求量是否小于所述电动汽车的容量， 以得到第 一结 果， 并且， 判断所述配送子路径中对于标记配送目标点的配送 时间是否小于或等于所述标 记配送目标点的配送 时间窗， 以得到第二结果； 所述标记配送目标点为所述配送子路径中 的任一配送目标点； 若所述第一结果表示是， 且所述第二结果表示是， 则根据所述配送子路径对所述节约 矩阵进行 更新， 然后返回至对所述节约矩阵中的多个距离节约值进行降序的步骤； 若所述第一结果表示否， 或所述第二结果表示否， 则将n更新为n+1， 然后判断更新后的 n是否等于N， 得到第三结果； N表示所述节约矩阵中距离节约值的数量； 判断所述配送子路径的距离节约值是否小于 0， 得到第四结果； 若所述第三结果表示是， 或者， 所述第四结果表示是， 则输出 所述配送子路径； 若所述第三结果表示否， 且， 所述第四结果表示否， 则返回将降序后处于第n位和第n+1 位的距离节约值所对应的配送路径进行融合， 以得到配送子路径的步骤。 5.根据权利要求3所述的基于移动充电的电动汽车配送路径规划方法， 其特征在于， 基 于所述电动汽车集合中每个电动汽车 的充电需求， 利用回溯算法， 确定所述移动充电车集 合中每个移动充电车的初始供电路径， 具体包括： 基于回溯法， 建立所述电动汽车集合对应的充电需求矩阵； 所述充电需求矩阵包括每 辆电动汽 车的充电需求； 所述充电需求包括充电需求位置、 充电需求时间窗、 充电需求电量 和充电需求时间； 根据时间顺序， 对多辆电动汽车的充电需求时间窗进行排序； 判断第m辆移动充电车是否满足排序后第f个充电需求时间窗对应的充电需求； m＝1， f ＝1； 若第m辆移动充电车不满足排序后第 f个充电需求时间窗对应的充电需求， 则将f更新 为f+1， 判断更新后的f是否小于等于电动汽车集 合中电动汽车总数， 以得到第五结果；权　利　要　求　书 2/4 页 3 CN 115358471 A 3