买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜北京工业大学申请的专利一种基于自适应多约束差分进化算法的车辆路径优化方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN114330810B 。

龙图腾网通过国家知识产权局官网在2025-04-01发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202111237064.X，技术领域涉及：G06Q10/047；该发明授权一种基于自适应多约束差分进化算法的车辆路径优化方法是由侯莹;吴毅琳;张嘉成;肖福霞;韩红桂设计研发完成，并于2021-10-24向国家知识产权局提交的专利申请。

本一种基于自适应多约束差分进化算法的车辆路径优化方法在说明书摘要公布了：本发明针对多约束多目标车辆路径优化问题，设计了一种基于自适应多约束差分进化算法的车辆路径优化方法，将车辆使用数目和总行驶距离作为优化目标，采用多目标差分进化算法，自适应调整多个进化机制，利用可行解引导的差分变异策略，提高解集的收敛性，设计基于约束支配准则的评估机制进行选择操作，提高最优解的多样性，获得最佳的车辆路径优化方案，降低了企业运输成本，增加了物流配送效益。

本发明授权一种基于自适应多约束差分进化算法的车辆路径优化方法在权利要求书中公布了：1.一种基于自适应多约束差分进化算法的车辆路径优化方法，其特征在于，包括以下步骤：步骤1确定车辆路径优化问题的优化目标：假设有Kmax台同一车型的运输车辆全部停在一个物流中心，准备向N个客户提供单程配送服务，车辆限载为Q，物流中心开门时间L和物流中心关门时间E；每个客户对应一条订单数据，包括客户编号i、客户位置坐标xi,yi、第i个客户的货物重量qi、第i个客户的最早开始服务时间li、第i个客户的最晚开始服务时间ei和第i个客户的服务时长si，其中i＝0表示物流中心；0Kmax50，0N200，0Q300，0L200，0E200，i＝0,…,N，0xi100，0yi100，0qi300，0li1000，0ei1440，0si200；该车辆路径优化问题的优化目标为最小化如下目标函数：f1＝K1 其中，f1为配送过程使用的车辆总数K，f2为车辆总行驶距离；0KKmax，dij为客户i与客户j之间的距离，xijk表示第k辆车是否从i行驶至j，xijk＝1为是，xijk＝0为否，j＝0,…,N,k＝1,…,K；每一辆车在配送过程中需满足以下条件，每个客户仅由一辆车完成配送服务： 每辆车从物流中心出发，按相应的客户服务顺序完成配送任务后返回物流中心： 第k辆车的客户总需求量应不超过Q： 车辆到达客户i所在位置的时间ai应在其服务时间窗内，并且车辆应在物流中心关门前回到物流中心：li≤ai≤ei8L≤a0≤E9车辆经过j到达i所在位置的时间ai为： 其中，wj为车辆等待客户j的时间，wj≥0，t0i为从物流中心行驶至客户i花费的时间，tji表示从客户j行驶至客户i花费的时间，tj0表示从客户j行驶至物流中心花费的时间；步骤2获取车辆路径优化问题的距离和时间数据：计算客户i与客户j之间的距离： 其中，xi和yi分别表示客户i位置的横坐标和纵坐标，xj和yj分别表示客户j位置的横坐标和纵坐标；根据车辆平均行驶速度v，计算对应于dij的行驶时间tij： 步骤3设计自适应多约束差分进化算法：步骤3.1参数设置及种群初始化：设定多目标差分进化算法的最大进化代数为T，T是[250,2000]范围内的整数，变异率为F，0≤F≤1，交叉率为Cr，0≤Cr≤1，种群规模为H，H是[10,500]范围内的整数，邻域规模为c，c是[1,N]范围内的整数，每个解表示一个车辆调度方案，随机产生初始种群P0： 其中，pb,0为初始种群的第b个解，b＝1,…,H；步骤3.2可行解数目的判断：第t代种群Pt表示为： 其中，pb,t为第t代种群的第b个解，pbu,t为第t代种群第b个解的第u维分量；t＝0,…,T，pbu,t＝1,…,N+Kmax,u＝1,…,N+Kmax；pbu,t＝1,…,N时表示客户，pbu,t＝N+1,…,N+Kmax时表示物流中心；在两个物流中心之间，按照客户开始服务的时间，对客户顺序进行升序排序，客户开始服务的时间从数据库中读取，得到K条配送路线rk，k是路线编号，k＝1,…,K,K≤Kmax；计算每个解的约束违反度δ： 其中，qi为第i个客户的货物重量，K为路径总数，即使用的车辆总数，Q为车辆限载，ai为第i个客户的到达时间，此值由公式10计算得到，ei为第i个客户的最晚开始服务时间，此值从数据库中读取；设定满足δ＝0的解为可行解，δ0的解为不可行解，统计Pt中可行解的总数；设定Pt中所有可行解组成的集合为Ft，β表示可行解总数，是[0,H]范围内的整数，若β＝0，则执行步骤3.3-3.4后，执行步骤3.6，若β≥2，则执行步骤3.4-3.5后，执行步骤3.6，若β＝1，则直接执行步骤3.5；步骤3.3基于DErand1变异策略的差分进化： 其中，vb,t为第t代种群的第b个变异解，prand1,t为第t代种群的第rand1个解，prand2,t为第t代种群的第rand2个解，rand1和rand2是在[1,H]中随机选取的异于b的两个互不相同的整数；pbu,t+1为第t+1代种群中第b个解的第u维分量，randbu是第b个解在第i维分量上取的随机数，0≤randbu≤1；对pb,t+1每一维分量进行向下取整： 其中，表示pb,t+1第u维分量向下取整后的数值；若N+1≤pbu,t+1≤N+Kmax，N+1≤pbu+1,t+1≤N+Kmax，且满足1≤pbu+2,t+1≤N，即pb,t+1存在空路线时，将pbu+1,t+1移出路线组，否则令u＝u+1，继续检查空路线，直至pb,t+1中的空路线全部删除；步骤3.4适应度值计算：计算候选解集中每一个解的支配强度：若p为可行解，q为不可行解，则p支配q，p的支配强度加1；若p和q均为可行解，f1p≤f1q，f2p≤f2q，则p支配q，p的支配强度加1；若p和q均为不可行解，δpδq，则p支配q，p的支配强度加1；其中，p和q是候选解集中两个相异的解，f1p和f1q分别是p对应的车辆总数和q对应的车辆总数，f2p和f2q分别是p对应的车辆总行驶距离和q对应的车辆总行驶距离，δp和δq分别是p对应的约束违反度和q对应的约束违反度；计算Pt和Pt+1构成的候选解集中每一个解的等级值：对于δ＝0的解，即可行解，其等级设定为1；对于δ0的解，即不可行解，根据δ大小对其进行升序排序，每一个不可行解的等级为可行解总数与其δ排序值之和；将每一个解的支配强度与等级值相加，得到每一个解的适应度值；步骤3.5可行解引导的差分变异操作：①根据适应度值对Ft进行升序排序，得到Ft＝p1,...,pβ；②计算p1和p2的相似度S： 其中，rp1,rand和rp2,rand分别表示从p1中随机挑选的一条配送路线和从p2中随机挑选的一条配送路线，1≤rand≤Kmax，|rp1,rand|和|rp2,rand|分别表示rp1,rand和rp2,rand的客户数目，|rp1,rand∩rp2,rand|表示同时在rp1,rand和rp2,rand中出现的客户数目，|rp1,rand∩rp2,rand|≥0；③调整Ft的顺序：p2调整为pβ，并且p3,...,pβ调整为p2,...,pβ-1；④若S≤0.5，执行步骤3.5⑤，若S0.5，返回步骤3.5②；⑤按路线编号顺序选取p1的一条路线rp1,k1，k1是p1对应的路线编号，1≤k1≤Kmax，设定c1,rp1,k1表示p1中第k1条配送路线的第一个客户，在p2中找出c1,rp1,1所在路线rp2,k2，k2是p2对应的路线编号，1≤k2≤Kmax，确定rp1,k1和rp2,k2的差分向量对： 其中，rp1,k1-rp1,k1∩rp2,k2表示在rp1,k1而不在rp2,k2上的配送路线补集，rp2,k2-rp1,k1∩rp2,k2表示在rp2,k1而不在rp1,k2上的配送路线补集，m和n分别表示rp1,k1-rp1,k1∩rp2,k2和rp2,k2-rp1,k1∩rp2,k2的第一个客户；⑥令第t+1代种群的第b个解pb,t+1＝p1，在p1中找出n所在路线rp1,k3，k3是p1中异于k1的路线编号，1≤k3≤Kmax，k3≠k1，将m和n分别从rp1,k1和rp1,k3中移除：在满足公式3-公式10的前提下，找出rp1,k3中可插入m的所有位置，使δpb,t+1＝0成立，计算所有插入位置相应的路线增量，路线增量最小对应的位置设定为m的插入位置，并将m插入该位置；在满足公式3-公式10的前提下，找出rp1,k3中可插入n的所有位置，使δpb,t+1＝0成立，计算所有插入位置相应的路线增量，路线增量最小对应的位置设定为n的插入位置，并将n插入该位置；若不存在使δpb,t+1＝0成立的可插入位置，将m或n设定为rp1,k3或rp1,k1的第一个客户，完成pb,t+1的构建；⑦令k1＝k1+1，统计第t+1代种群规模|Pt+1|，若k1＝K1，K1是p1对应的车辆数目，且|Pt+1|＝H，H是种群规模，则转到步骤3.6，若k1＝K1，且|Pt+1|H，则返回步骤3.5②；若k1K1，且|Pt+1|H，则返回步骤3.5⑤；步骤3.6大规模邻域搜索操作：在pb,w中随机选取一维表示客户的分量pbu,w，pbu,w＝i，w＝t或t+1，1pbu,wN，N是服务的客户总数，根据客户i与客户j之间的距离dij选取与客户i距离最近的c个客户，c是邻域规模，找出pb,w中对应的c维分量pbv,w，1pbv,wN，v≠u，将pbv,w和选中的c维分量从pb,t中移除；在满足公式3-公式10的前提下，找出pb,w中可插入pbu,w的所有位置，使δpb,w＝0成立，计算所有插入位置的路线增量，设定路线增量最小对应的位置为pbu,w的插入位置，并将pbu,w插入该位置；在满足公式3-公式10的前提下，找出pb,w中可插入pbv,w的所有位置，使δpb,w＝0成立，计算所有插入位置的路线增量，设定路线增量最小对应的位置为pbv,w的插入位置，并将pbv,w插入该位置；步骤3.7选择操作：若Pt+1为空，即不存在第t+1代种群，转到步骤3.8，否则根据解的适应度值对候选解集进行升序排序，选取前H个解构建Pt+1，H是种群规模；步骤3.8判断算法的终止条件：若tT，则令t＝t+1，重复步骤3.2至步骤3.7，若t＝T，则停止计算，输出最优的车辆调度方案。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人北京工业大学，其通讯地址为：100124 北京市朝阳区平乐园100号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。