(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210874939.5 (22)申请日 2022.07.25 (71)申请人 江南大学 地址 214122 江苏省无锡市滨湖区蠡湖大 道1800号 (72)发明人 葛洪伟　张海飞　江明　李婷　 (74)专利代理 机构 哈尔滨市阳光惠远知识产权 代理有限公司 2321 1 专利代理师 吕永芳 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06N 3/00(2006.01) (54)发明名称 一种考虑实际多约束的多条等效最优路径 规划方法 (57)摘要 本发明公开了一种考虑实际多约束的多条 等效最优路径规划方法， 属于交通运输科技领 域。 该方法基于城市物流配送中的实际情况， 考 虑更加符合现实生活的复杂路网约束、 负载约 束、 时间窗约束以及需求可拆分约束， 构造对应 的目标函数； 在求解多条等效最优路径时， 设计 了一种改进差分进化算法， 首先在初始化过程中 利用广义反向学习策略生 成反向顾 客种群， 同时 搜索当前空间和转换空间的解； 且采用三种概率 方式在种群中选择生成差分向量的个体， 自适应 平衡体的探索能力和开发能力， 提高决策空间和 目标空间的多样性； 而且对产生突变的个体进行 合法化处理， 而非直接丢弃， 从而使得超出解空 间范围的个体能够得到修正， 进一步保证了可以 得到多条等效最优路径。 权利要求书3页 说明书13页 附图1页 CN 115146866 A 2022.10.04 CN 115146866 A 1.一种考虑实际多约束的多条等效最优路径规划方法， 其特 征在于， 所述方法包括： 考虑符合实际的多约束条件 并构造对应的目标函数； 所述多约束条件包括复杂路网约 束、 负载约束、 时间窗约束、 需求可拆分约束； 采用改进差分进化算法EIDSDE求解得到物流配送的多条等效最优路径规划， 所述改进 差分进化算法EIDSD E在种群初始 化阶段引入广义反向学习策略约束种群的搜索空间； 在个 体选择阶段， 以三种概率方式在种群中选择生成差分向量的个体， 并对被选择 的所有个体 进行拥挤距离和特殊拥挤距离的计算， 同时将拥挤距离的计算方式转换为相 邻欧氏距离的 加权和； 在变异阶段， 若变异产生的个体不满足边界条件， 则进行二次变异， 若二次变异的 个体仍不满足边界条件， 则按照预设修补策略进行修补使其满足边界条件； 在环境选择阶 段， 选择预定百分比的前级个 体； 所述种群中的每 个个体代表物流配送的一条 可能的路径。 2.根据权利要求1所述的方法， 其特征在于， 所述复杂路网约束指交通要素以及城市路 网拓扑结构产生的约束； 所述负载约束指车辆在进行装货时不得超过车辆的最大负载； 所 述时间窗约束指物流配送的时间上下线； 所述需求可拆分约束指配送货物是否可被拆分的 约束。 3.根据权利要求2所述的方法， 其特征在于， 所述方法考虑4种约束下所构造对应的目 标函数分别为： f1车辆数: f2总距离: f3总配送时间: f4总配送成本: 其中， R为完成配送任 务所需的车辆数， qi为顾客i的需求量， w为车辆最大运载能力， n表 示顾客的数量， 表示向上 取整； dij为顾客点i到顾客点j的配送距离， 表示第r条路线中车辆是否通过弧(i,j)， r∈R， i,j∈C'为决策变量， 当且仅当第r条路线中车辆通过 弧(i,j)时， 否 则 表示每个顾客至少 被访问1次， C＝{0,1,2,...,n}表配送中心和顾客 的集合， C'＝C /{C0}表n个顾客的集 合； Tdj为车辆在 顾客j处的等待时间， v表示配送车辆的速度， β 为违反顾客所规定的配送时 间而产生的时间成本系数， 表示配送任务是否有时间要求， bir表示 车辆r到达顾 客i处的实际时间， bor＝0表示车辆出发时刻为0， LTi表示允许配送车辆到达顾 客i处的最晚时间； FY为费用矩阵， 每条路径aij∈A对应的费用fyij∈FY， G为车辆的固定成本， l为时间延迟权　利　要　求　书 1/3 页 2 CN 115146866 A 2成本， α为单位距离对应的时间延迟成本， Sr表示 第r条路线中服务的顾客集合， 即第r辆车负责配送的顾客集合， |Sr|表示集合中包含的元 素个数， 即顾客个数， (xi,yi)表示顾客 i的坐标。 4.根据权利要求3所述的方法， 其特征在于， 所述方法中， 每个个体代表物流配送的一 条可能的路径， 对应至种群中， 每个个体对应一个点， 每个点的维度 表示该路径所经过的客 户数； 所述在种群初始化阶段引入广义反向学习策略约束种群的搜索空间包括： 假设P为候选解， 表示一条可能的路径， 假设P＝(z1,z2,...,zD)为一个D维空间的点， 其 中z1,z2,...,zD∈R且zm∈[Lm,Um]， f(·)为候选解的目标函数适应值， 则P 的 反向 点为 其中 k＝ra nd om (0 ,1) ， 若 则 若 则表示 比P具有更好的适应 值， 此时选择 代替P， 否则保持不变。 5.根据权利要求4所述的方法， 其特征在于， 所述方法在个体选择阶段， 以三种概率方 式在种群中选择生成差分向量的个 体， 包括： 第一种概率方式p1： p1＝1‑(Gc‑1)/Max_gen， 以超过0.5的概率随机选择整个种群中的 五个邻域作为 第二种概率方式p2： p2＝(1‑p1)/2， 在决策空间中选择邻域时， 根据当前个体与种群中 剩余解之 间的平均欧氏距离， 选择确定数量的邻域， 然后从该确定数量的邻域内随机选择5 个neighbors， 选择拥挤距离最大的一个作为 其余的四个为 第三种概率方式p3： p3＝1‑p1‑p2， 在目标空间中选择邻 域时， 根据 当前个体与种 群中剩 余解之间的平均欧氏距离， 选择确定数量的邻域， 然后从该确定数量的邻域内随机选择5个 neighbors， 然后选择拥挤距离最大的一个作为 其余的四个为 其中， Gc表示当前迭代的代数， Max_gen表示 最大迭代次数； 在差分进化算法中嵌入基于欧几里德距离的小生境方法， 根据决策空间或 目标空间中 相应个体的拥挤距离， 在相应 个体的邻域中选择r1,r2,r3,r4,r5。 6.根据权利要求5所述的方法， 其特征在于， 所述方法在变异阶段， 对突变的个体进行 合法化处 理， 包括： 采用DE/rand/2进行变异， 差分向量生成为： 其中， vi 表示差分向量， r1,r2,r3,r4,r5为相互不 等的整数； F 是用于缩放差分向量的比例因子； 若变异产生的个 体不满足边界条件， 则： 计算首次越界个 体与其他变异完成个 体之间的平均欧式距离davg； 在解空间内取距首次越界个 体欧式距离为davg的个体x'； 将个体x'按照Vi,m＝xr1,m‑F[(xr2,m‑xr3,m)+(xr4,m‑xr5,m)]进行二次变异； 如果经过第二次 变异后个体仍然越界， 则按照 进行修补； 其中， vi,m表示 ith个个体在mth维上的值， Um和Lm表示决策空间的上 下界。权　利　要　求　书 2/3 页 3 CN 115146866 A 3