CN115146866B 一种考虑实际多约束的多条等效最优路径规划方法 （江南大学）

一种考虑实际多约束的多条等效最优路径本发明公开了一种考虑实际多约束的多条等效最优路径规划方法，属于交通运输科技领虑更加符合现实生活的复杂路网约束、负载约2考虑符合实际的多约束条件并构造对应的目标函数；所采用改进差分进化算法EIDSDE求解得到物流配送的多条等效最优路所述方法考虑4种约束下所构造对应的目标函fdij为顾客点i到顾客点j的配送距离，表示第r条路线中车辆是否通过弧(i,j)，间而产生的时间成本系数，z;e0,}wreR,iec,表示i)表示顾客i的坐标；3vme1,2,…,D},f(·)为候选解的目标函数适应值，则P则zn=random(Lnsun),若f(D)<f(p),则表示比P具有更好的适应在差分进化算法中嵌入基于欧几里德距离的小生境方法，根据F是用于缩放差分向量的比例因子；计算首次越界个体与其他变异完成个体之间的平均欧在解空间内取距首次越界个体欧式距离为d的个体x'；44.根据权利要求3所述的方法，其特征在于，所述缩放差分6.权利要求1_4任一所述的考虑实际多约束的多条等效最优路径规划方法在物流配送5于能够模拟各种领域的实际应用而获得了广泛的普及。面向实际多约束的VRP(RichVRP，流企业或配送中心，每次的运输任务可支配的车辆数量以及配送人员等资源都是有限的。[0005]现有技术中，GauravSrivastava等人提出了一种带有目标特定变异算子的非支模型进行优化求解(SrivastavaG,SinghA,MallipeddiR(2021).NSGA_IIwithobjective_specificvariationoperatorsformulti_objectivevehicleroutingproblemwithtimewindows.ExpertSystemswithApplications,176:114779.)。CaitongYue等人提出了一种改进拥挤距离的差分多模态多目标差分进化算法(Multi_modalMulti_objectiveDifferentialEvolutionAlgorithmUsingImproved6C,SuganthanPN,LiangJ,etal.(2021)DifferentialEvolutionUsingImprovedCrowdingDistanceforMulti_modalMulti_objectiveOptimization.SwarmandEvolutionaryComputation,62(9):100849.)。这些算法在一定程度上[0006]为了更加实际地反映车辆路径问题，同时满足不同决策者对车辆路径的规划需改进差分进化算法EIDSDE在种群初始化阶段引入广义反向学习策略约束种群的搜索空间；r1表示向上取整；7配送时间而产生的时间成本系数，Z;e(0,}wreR,iec,表示配送任务是否有时间要求，1m,Um]，vmef1,2,…,D},f(·)为候选解的值，则P的反向点为其中zn=k(Ln+un)-zn,k＝random(0,1)，若zn<Lnorzn>um,则zn=random(Lnrun),若则表示p比P具有更好的适应8F是用于缩放差分向量的比例因子；[0032]在解空间内取距首次越界个体欧式距[0039]本申请还提供上述考虑实际多约束的多条等效最优路径规划方法在物流配送领策略生成反向顾客种群，采用转换搜索空间技术把当前空间的解转换到一个新的空间去，空间中生成差分向量顾客个体，对被选择的所有个体进行拥挤距离和特殊拥挤距离的计9t代种群中第i个0,1]为介于0到1之间的一个均匀分布随机异被看作是某个元素发生改变。在差分进化算法中，以最简单的变异操作(DE/rand/1)为i为顾客i的需求量。[0080]x;ei),reR,ijec'为决策变量，当且仅当第r条路线中车辆通过弧(i,j)∈R且zm∈[Lm,Um]，vme(1,2,…,D},f(·)为候选解的目标函其中zn=k(Ln+un)-zn,k＝random(0,1)，若n<Lnorzm>un,则zn=random(L,:un),若f(D)<f(p),则表示p比P具有更好的适应值，此时选择p代替P，[0095](5.2)在解空间内取距首次越界个体欧式距离[0102]对所选个体的比例按照进行[0106]本实施例利用MATLAB2020a进行仿真实验，实验设备为具有i7_75002.90GHzCPU的电脑。由于Solomon数据集(Solomon数据集是一个公开的数据集)不能代表本发明所提出的RVRP的理想基准场景，而在本发明所提出的RVRP中时间窗约束具有一定的主导地位，因此本发明使用了与ZhouandWang(ZhouY,WangJ.ALocalSearchobjectiveOptimizationAlgorithmforMulti_objectiveVehicleRoutingProblemWithTimeWindows(2017).IEEESystemsJournal,9(3):1100_1113.)以及CastroGutierrezetal.(JPCGutiérrez,Landa_SilvaD,JAMoreno_Pérez.Natureofreal_worldmulti_objectivevehicleroutingwithevolutionaryalgorithms(2011).IEEE可从/psxjpc/[0107]本实施例将本申请方法EIDSDE和现有的INSGA_II和MMODE_ICD进行了对比，这两[0108]INSGA_II可参考“SrivastavaG,SinghA,MallipeddiR.NSGA_IIwithobjective_specificvariationoperatorsformulti_objectivevehicleroutingproblemwithtimewindows[J].ExpertSystemswithApplications,2021,176:114779.力[0109]MMODE_ICD可参考“YueC,SuganthanPN,LiangJ,etal.DifferentialEvolutionUsingImprovedCrowdingDistanceforMulti_modalMulti_objectiveOptimization[J].SwarmandEvolutionaryComputation,2021,62(9):100849.力4以接受的最晚服务时间可以延后5～15分