(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210662261.4 (22)申请日 2022.06.13 (71)申请人 合肥工业大 学 地址 230009 安徽省合肥市包河区屯溪路 193号 (72)发明人 夏维　姜春雨　罗贺　马华伟　 李思齐　宋洋　 (74)专利代理 机构 北京久诚知识产权代理事务 所(特殊普通 合伙) 11542 专利代理师 王云海 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06Q 50/06(2012.01) G06F 30/15(2020.01)G06F 30/20(2020.01) G06F 111/04(2020.01) G06F 111/06(2020.01) (54)发明名称 电动汽车与燃油汽车联合送货的路径规划 方法和系统 (57)摘要 本发明提供一种电动汽车与燃油汽车联合 送货的路径规划方法、 系统、 存储介质和电子设 备， 涉及车辆路径规划技术领域。 本发明获取车 辆、 充电站、 配送中心、 客户节点的任务数据； 根 据所述任务数据， 构建考虑交通拥堵的混合车辆 联合配送模 型； 采用模拟退火算法求解所述混合 车辆协同配送模型， 获取混合车辆路径优化方 案； 混合车辆路径优化方案包括插入充电站的电 动汽车配送方案。 在考虑交通拥堵状况的混合车 队配送问题的数学模型基础上提出了模拟退火 算法， 在该算法的支持下， 混合车 队配送效率可 以进一步提高， 降低物流配送成本 。 权利要求书4页 说明书13页 附图2页 CN 115099474 A 2022.09.23 CN 115099474 A 1.一种电动汽车与燃油汽车 联合送货的路径规划方法， 其特 征在于， 包括： S1、 获取车辆、 充电站、 配送中心、 客户节点的任务数据； S2、 根据所述任务数据， 构建考虑交通拥堵的混合车辆联合配送模型； S3、 采用模拟退火算法求 解所述混合车辆协同配送模型， 获取混合车辆路径优化方案； 混合车辆路径优化方案包括插 入充电站的电动汽车配送方案： 计算优化方案 中任一电动汽车到每一个节点所需的电量， 若当前电动汽车到达某一节 点的电量小于等于零， 且在该节点的上一节点的剩余电量满足到达距离最近的充电站， 则 在该节点和其上一节点之间插 入所述距离最近的充电站。 2.如权利要求1所述的路径规划方法， 其特征在于， 所述S2的混合车辆联合配送模型包 括目标函数： min z＝fd+ft 其中， fd表示路程成本： ft表示时间成本： K表示车辆集合， 下标为k； Ke表示电动汽车集合； Kf表示燃油汽车集合； S表示充电设施 集合， 下标为s； {o}表 示配送中心； C为客户节 点集合， 下标为c； V表 示所有节 点集合， V ＝C∪ S∪{o}； xghk为决策变量， 如果车辆从g点经过h点， 则为1， 否则为0； yk为决策变量， 如果车辆 是电 动汽车， 则为1， 否则为0； ce表示电动汽车单位里程行驶成本； cf表示燃油汽车单位里程行驶成本； 表示电动汽 车单位时间行驶成本； 表示燃油汽车 单位时间行驶成本； dgh表示任意两个节点g、 h之间的距 离； tgh表示车辆从g节点行驶到h节点实际所需时间， 通过道路阻抗 函数BRP求 解： 表示车辆从g节点到h节点的自由行驶时间； θgh表示路径xgh的交通量； pgh表示路径 xgh的通行能力； α 和β 为常数。 3.如权利要求2所述的路径规划方法， 其特征在于， 所述S2的混合车辆联合配送模型包 括约束条件： (1)∑g∈V， g≠i∑k∈Kxgik＝1， 约束条件(1)保障每一个客户节点仅有一辆汽车访问； (2)∑h∈V， h≠0X0hk≤1， 约束条件(2)每辆汽车在规划期内只能被使用1次； (3)∑g∈V， g≠vxgvk＝∑h∈V， h≠vxvhk， k∈K权　利　要　求　书 1/4 页 2 CN 115099474 A 2约束条件(3)表示进入某节点的车辆必须离开， 保障离开配送中心的车辆最终回到配 送中心， 保障车辆在客户节点的流 量平衡； (4)∑i∈Iqi∑v∈Vxvik≤u， 约束条件(4)保障每辆汽车服 务的客户总需求 不能超过 车载容量u； (5) 约束条件(5)表示车辆k从g节点到h节点的电量消耗关系； 表示车辆k到达k时剩余 电量； 表示车辆k离开g时剩余电量； Q表示电动汽车电池容量； μ表示单位路程电动车耗 电率； (6) 约束条件(6)设定 到达i节点和离开 i节点时电动汽车的电量 不变； (7) 约束条件(7)设定电动汽车在充电站s满充； (8) 约束条件(8)表示电动汽车在充电站的充电量； (9) 约束条件(9)保障电车车辆CO2排放量要小于总CO2排放量上限值H； mk表示单位路程电 动汽车的CO2排 放量； mf表示单位路程燃油汽车的CO2排 放量； (10)thk≥tgk+sg+tgh·xghk‑l0·(1‑xghk)， 约束条件(10)满足车辆从g节点到h节点的时间逻辑 关系； sg表示客户节点g所需的服务 时间； (11) 约束条件(11)满足车辆从充电站s到节点h的时间逻辑关系； r表示单位时间电池充电 率； l0表示一个大数。 4.如权利要求1～3任一项所述的路径规划方法， 其特 征在于， 所述S3具体包括： S31、 初始化参数： 外层最大循环次数MaxOutIter、 里层最大循环次数MaxInIter、 外层 循环计数器OutIter、 里层循环计数器I nIter、 初始温度T＝T0、 冷却因子alpha； S32、 根据所述混合车辆协同配送模型生成初始解Sinit， 令当前解Scurr＝Sinit， 其目标函 数值为f(Scurr)； S33、 令全局最优解Sbest＝Scurr， f(Sbest)＝f(Scurr)； S34、 判断外层循环计数器是否小于等于外层最大循环次数； 若是则进入下一步， 若否 则进入S318； S35、 判断里层循环计数器是否小于等于里层最大循环次数； 若是则进入下一步， 若否 则进入S316； S36、 轮盘赌选择邻域结构； S37、 产生当前邻域结构下当前解Scurr的新解Snew S38、 判断目标函数f(Snew)是否小于等于f(Scurr)； 若否则进入下一 步， 若是则进入S312；权　利　要　求　书 2/4 页 3 CN 115099474 A 3