本发明针对同一区域多家公司需要同时处理车辆路径问题，设计了一种基于动态资源分配多任务差分进化算法的车辆路径优化方法，通过计算每个任务的复杂度，合理分配每个任务的计算资源，并为之做出资源的调整，从而在具有不同复杂度的任务前提下，获得了每家公司的最优车辆调度方案，实现了车辆使用总数和车辆总行驶距离最小，既属于智能信息领域，属于物流运输领域。
背景技术：
1、优化车辆路径对于公司来说，可以降低物流运输成本，促进物流运输业的发展，具有重要的实际意义。在传统的车辆路径优化问题中，通常只考虑单一任务。然而，在现实生活中，往往存在多个车辆路径问题需要同时执行，使得如何对其合理规划具有挑战性。虽然每家公司处理的订单各不相同，但是他们对最优调度方案的求解往往存在相似的属性，因此可以采用多任务优化的思想来同时解决多个车辆路径问题。多任务差分进化算法是一种启发式优化算法，通过模拟生物进化过程中的遗传、变异和选择来搜索最优解。通过共享信息和知识交流，多任务差分进化算法可以加快搜索过程，快速找到最优车辆调度方案。然而，解决不同的车辆路径问题的难度是不同的，若对每个任务投入同等的计算资源，则往往会造成资源的浪费，为解决该问题，本发明在解决多个车辆路径问题上具有广泛的应用前景。
2、本发明提出了一种基于动态资源分配多任务差分进化算法的车辆路径优化方法，以车辆使用数目和车辆总行驶距离最小化为优化目标，通过计算每个任务的复杂度以及进化状态，合理的调整各个任务之间的计算资源，从而获得各任务的最优车辆调度方案，为降低物流运输过程中的运输成本和提高服务质量提供了一种有效的方法。
技术实现思路
1、本发明获得了一种基于动态资源分配多任务差分进化算法的车辆路径优化方法，该方法以最小化车辆使用数目和车辆总行驶距离为优化目标，确定每个任务的车辆路径优化模型，通过计算任务的复杂度和进化状态，实时为每个任务调整计算资源，从而获得各任务的最优车辆调度方案，提高订单调度的效率，降低公司运输成本。
2、本发明采用了如下的技术方案及实现步骤：
3、1.一种基于动态资源分配机制的多任务差分进化算法，其特征在于确定车辆路径优化问题的优化目标，采用多任务差分进化算法，动态调整任务间的计算资源，获取每个任务的车辆调度方案，解决不同任务求解难度不同，造成计算资源浪费的问题，实现车辆使用数目和车辆总行驶距离同时最优，包括以下步骤：
4、步骤1确定每个任务的车辆路径问题的优化目标：
5、一共存在h个任务，假设某一家公司有lmax台车型相同的运输车辆停在一个站点，需要服务n个客户，每辆车的限载为q，站点的开门时间和关门时间分别是s和e；每个订单仅由一辆车完成服务，每辆车从站点出发，按订单服务顺序完成取件业务后都需返至站点；每个订单都包含以下属性：订单编号i、订单位置坐标(xi,yi)、第i个订单的产品重量qi、第i个客户的期望开始服务时间ai、第i个客户期望的最晚开始服务时间ei和第i个客户的服务时长si，其中i＝0表示站点；0<lmax<50，0<n<150，0<q<300，0<s<1440，0<e<1440，i＝0,…,n，0<xi<100，0<yi<100，0<ai<1440，0<ei<1440，0<si<200；
6、该车辆路径问题以车辆使用数量和车辆总行驶距离最小化为优化目标：
7、minf1＝l(1)
8、
9、其中，f1是调度过程使用的车辆数l，f2是车辆行驶总距离；0<l≤lmax，dij是订单i与订单j之间的距离，i＝0,…,n,j＝0,…,n,i＝0表示站点，i＝1,…,n表示订单，xijl表示第l辆车是否从订单i行驶至订单j，xijl＝1为是，xijl＝0为否，l＝1,…,l；
10、每一辆车在配送过程中需满足以下条件，每个客户有且仅有一辆车进行服务：
11、
12、每辆车从站点出发，按相应的客户服务顺序完成任务后返回站点：
13、
14、客户的产品重量之和不能大于车辆的最大载重；
15、
16、每辆车到达每个客户约定的地点的时间应在客户要求的时间窗以内，并且车辆应在站点关门前回到该处：
17、ti∈[ai,ei](8)
18、t0∈[s,e](9)车辆到达下一个客户约定地点的时间为：
19、tj＝ti+wi+si+tij(10)
20、其中，wi为车辆在客户i处的等待的时间，wi≥0，si为车辆在客户i处的交付时间，tij表示从客户i行驶至客户j花费的时间；
21、步骤2计算每个任务的复杂度：
22、步骤2.1计算每个任务的客户配送量的饱和度：
23、任务ti的客户配送量的饱和度yi1为：
24、
25、其中，ni为任务ti所要服务的客户数量；
26、步骤2.2计算每个任务的客户地理位置的分散度：
27、任务ti的客户地理位置的分散度为：
28、
29、其中，neark为任务ti中客户cj与其最近的客户之间的距离，fark为任务ti中客户cj与其最远的客户之间的距离；
30、步骤2.3计算每个任务的客户时间窗的宽敞度：
31、任务ti的客户时间窗的宽敞度为：
32、
33、其中，和分别为任务ti中客户cj期望的最晚服务时间和最早服务时间；
34、步骤2.4综合三个复杂度因子：
35、最终，任务ti的复杂度为yi：
36、
37、步骤3种群初始化：
38、为任务ti随机产生初始种群每个任务初始化解的数量都为np个，每个解都表示一个车辆调度方案；
39、
40、其中，pib,g为任务ti第g代种群的第b个解，为任务ti第g代种群第b个解的第u维分量；i＝1,…,k，g＝0,…,gmax，时表示客户，时表示站点；在两个站点之间，按照客户开始服务的时间，对客户顺序进行升序排序，调整客户的排列顺序，得到l条配送路线rl，l是路线编号，l＝1,…,l,l≤lmax；pib,g中第(ni+l+1)维分量至第(ni+lmax)维分量表示未使用的车辆均停在站点；
41、步骤4为每个任务分配合适的计算资源：
42、步骤4.1第一阶段根据任务的复杂度为每个任务分配计算资源：
43、当g<gen时，为第一阶段，采用以下步骤为各任务分配资源；
44、对每个任务的复杂度yi进行从大到小排序，每个任务可以获得相应的第一个秩ranki1，对于复杂度低的任务，每隔δi代为复杂度高的任务转移种群名额；
45、
46、其中，gen为第一阶段的进化代数，np是任务初始化种群规模，npm为每个任务最小种群规模，为任务ti的第一个秩，λ是一个增长系数，λ>1；
47、若g<gen且g能被δk整除，k属于第一个秩排在前一半的任务编号，δk是任务tk需要转移种群名额的间隔代数，则任务tk向其对应的复杂度高的任务(假设为tr)转移一个种群名额，即
48、步骤4.2第二阶段在复杂度的基础上根据任务的进化状态为每个任务分配计算资源：
49、当g>gen时，为第二阶段，采用以下步骤为各任务分配资源；
50、①计算每个任务的进化状态；
51、
52、其中，no为优化目标数，g是当前优化代数，β为衰减系数，0<β<1，为任务ti在第g代中的所有非支配解中对于第j个优化目标的最小值，uji是任务ti对于第j个优化目标的最优目标值从最近一次更新到当前代的迭代距离，uji≥0；
53、②每个任务根据各自的进化状态进行从小到大排序，每个任务可以获得第二个秩ranki2；
54、③每个任务根据前两个秩计算各自的综合资源分配指标ri；
55、
56、其中，ranki1和ranki2分别时任务ti第一和第二个秩；
57、④每个任务根据各自的综合资源分配指标ri进行从小到大排序，每个任务可以获得第三个秩ranki；
58、⑤根据ranki，计算每个任务的理论种群规模
59、
60、其中，npm为每个任务最小种群规模，npo为总体种群规模，h为任务数量，ranki为任务ti的第三个秩，η是资源分配系数，控制着不同任务间的种群数量差异，其不得超过每个任务的种群数量；
61、步骤五根据计算的理论种群规模调整每个任务的实际种群：
62、如果任务ti的理论种群规模大于实际种群规模则需要对任务ti进行种群扩增，扩增的额外种群是通过迁移源任务的知识构建的，额外种群构建如下；
63、①首先计算每两个任务ti和tj中订单和cjn之间的相似性
64、
65、其中dmnij为任务ti的订单和任务tj的订单cjn归一化后的距离，tmnij为任务ti的订单和任务tj的订单cjn归一化后的时间窗宽度差；
66、②计算每两个任务ti和tj间的相似性：
67、
68、其中ni是任务ti的客户数量，是订单和cjn之间的相似性；
69、③采用轮盘赌为当前任务选择一个进行知识迁移的源任务，每个任务的选择概率为：
70、
71、其中，h为任务数量；
72、④从所选的源任务中随机选取一个解，根据这个解来构造当前任务额外种群的一个解，构造解的原理为：根据该解中各订单的排列顺序，从当前任务的所有订单中依次选择与该解每个元素相似的订单组成一条序列，若还有剩余订单，则插入到使目标值最优的位置得到一条完整序列，该序列经过时间窗要求调整位置以及插入站点，最终得到所要构造的一个解；
73、⑤重复步骤④直到当前任务的种群数量达到该任务的理论种群规模为止；
74、若任务ti的理论种群规模小于实际种群规模则需要对任务ti进行删除劣质解操作，使得该任务的种群删减至
75、步骤六基于de/rand/1变异策略的差分进化更新迭代每个任务的种群：
76、
77、其中，是任务ti第g代种群的第h个变异解，是的第h个父代，和是从中随机选取的两个父代；是的子代，是的第d维分量，randih,g是第h个父代在第d维分量上取的随机数，0≤randih,g≤1；
78、对实数编码的子代进行升序排序得到整数编码的子代种群
79、步骤七环境选择：
80、步骤7.1计算每个任务各个解的适应度值：
81、①计算每个任务各个解的约束违反度δ：
82、
83、其中，qi为第i个客户的货物重量，l为路径总数，q为车辆最大载重，ti为车辆到达第i个客户的时间，ei为第i个客户的最晚开始服务时间，当δ＝0时，为可行解，当δ>0时，为不可行解；
84、②计算每个任务各个解的支配强度：
85、如果p为可行解，q为不可行解，则p支配q，p的支配强度加1；
86、如果p和q都是可行解，f1(p)≤f1(q)，f2(p)≤f2(q)，则p支配q，p的支配强度加1；
87、如果p和q都是不可行解，δ(p)<δ(q)，则p支配q，p的支配强度加1；
88、其中，p和q是各任务中两个不同的解，f1(p)和f1(q)分别是p和q对应的第一个目标值，f2(p)和f2(q)分别是p和q对应的第二个目标值，δ(p)和δ(q)分别是p和q对应的约束违反度；
89、③计算每个任务各个解的等级值：
90、当δ＝0时，即可行解，其等级值设定为1；
91、当δ>0时，即不可行解，根据δ值进行从小到大排序，不可行解的等级值为可行解总数与其δ排序值之和；
92、④每一个解的适应度值为该解的支配强度与等级值相加即可得到；
93、步骤7.2根据解的适应度值对每个任务的所有解进行升序排序，选取前个解组成
94、步骤八判断算法终止条件：
95、若g<gmax，令g＝g+1，重复步骤四-步骤七，若g＝gmax，优化停止，输出每个任务的非支配解集，将各任务每个解中表示站点的元素全部置为0，得到每个任务最优的车辆调度方案。
96、本发明的创新性体现在：
97、(1)本发明在针对多个车辆路径问题中，考虑到每个任务的求解难度不同，对每个任务进行了复杂度分析以及进化状态分析，在进化前期，资源倾向于复杂度高的任务，在进化中后期，资源倾向于进化频繁的任务，从而提高每个任务最优解的收敛性，快速获得各任务的车辆调度方案；
98、(2)本发明在针对多个车辆路径问题中，最优解多样性较差的问题，通过分析任务与任务间的相似性和任务间订单与订单的相似性，学习源任务的车辆调度方案来构造当前任务的解，从而实现知识的正向迁移，提升最优解的多样性，获得多样性好的车辆调度方案。
99、特别要注意：本发明设计了具有动态资源分配机制的多任务差分进化算法，只要采用了本发明的优化算法进行调度技术的研究都应属于本发明的范围。
1.一种基于动态资源分配多任务差分进化算法的车辆路径优化方法，其特征在于确定车辆路径问题的优化目标，采用多任务差分进化算法，动态调整任务间的计算资源，获取每个任务的车辆调度方案，解决不同任务求解难度不同，造成计算资源浪费的问题，实现车辆使用数目和车辆总行驶距离同时最优，包括以下步骤：
