1.一种基于改进多目标粒子群算法的物流系统设计方法,其特征在于,包括如下步骤:
(1)把n个快递点的位置存入[X,Y]中,其中X=[x1,x2,…,xi,…,xn],Y=[y1,y2,…,yi,…,yn],xi表示第i个快递点的横坐标,yi表示第i个快递点的纵坐标,用矩阵C存放所有快递点之间运输费用,用矩阵T存放各快递点之间运输时间,用一个1*n的行向量F存放在各个快递点位置建立物流中心的费用,二进制的列向量H(h1,h2,…hi,…,hn)中各元素表示各快递点是否为物流中心,当hi=1,则快递点i为物流中心,准备建立物流中心的个数用p表示;解决方案,即粒子,为一个n*n的二进制矩阵,该矩阵中对角线上值为1所在的行或列为物流中心,矩阵中每列指物流系统中的一个快递点,每列中数值为1所在的行为该快递点所隶属的物流中心的编号;将解决方案中所有的快递点所隶属的物流中心存入数组hub中,数组的下标对应快递点编号,hub(i)表示快递点i隶属的物流中心;
(2)物流系统目标函数的搭建如下:
其中,i和j为快递点的编号,k和l分别为快递点i和j所隶属的物流中心,快递点和物流中心的对应关系为hub;各物流中心之间的运输费用和运输时间都乘以一个折扣因子β,0<β<1;f1中的前半部分为整个物流系统的运输费用,其中Cik+βCkl+Clj表示快递点i到物流中心k、物流中心k到物流中心l、物流中心l到快递点j的运输费用之和,f1的后半部分F*H为建立物流中心的费用;f2为整个物流系统货物运输时间;
(3)随机初始化nPOP个粒子的位置信息即解决方案,这些粒子的位置信息集合记为POP,随机初始化nPOP个速度,这些速度集合记为V,初始化最大迭代次数gmax、外部存档容量nRep、目标空间中每一维网格划分数nGrid,目标函数的个数为2、当前迭代次数为t;
(4)计算所有粒子的目标函数值,用Epa表示,令每个粒子个体最优为其自身;接着筛选出Pareto最优粒子存入外部存档中,位置信息记为APOP,对应的目标函数值记为Arc;
(5)利用外部存档中的粒子进行网格搭建,然后计算目标空间中点的网格坐标;
所述的网格搭建,按下述步骤操作:
(2.1)利用外部存档中的粒子进行网格搭建,外部存档中所有粒子函数值的上限记为CU=(fu1,fu2),下限记为CL=(fl1,fl2),其中fu1和fu2分别为两个目标函数的最大值,fl1和fl2分别为两个目标函数的最小值,整个网格的跨度为DC=(dc1,dc2),其中dci=fui‑fli,i=1,2;
(2.2)利用扩容率α,α=0.1,对外部存档中粒子的目标函数值的上下限进行扩容,得到新上限为CU'=(fu′1,fu′2),fu′i=fui+α*dci,新下限为CL'=(fl′1,fl′2),fl′i=fli‑α*dci,i=1,2,根据以下公式将外部存档中粒子函数值在目标空间中的对应点映射到网格中:其中,G(X)为粒子的网格坐标,di为目标空间中第i维上每个小网格的宽度,nGrid为目标空间中每一维度上小网格的个数,各维度网格坐标从1开始计数;
(6)通过双距离决策方法进行引导粒子筛选操作;选出引导粒子后,利用粒子群算法更新公式产生新的粒子,然后生成随机数r,当r>0.8时,对产生的新粒子进行差分变异,否则不进行变异操作;当产生的新粒子支配当前粒子时,则将新粒子替换对应的个体最优粒子;
新生成种群代替当前的POP,计算POP的目标函数并取代当前的Epa集合;粒子群算法公式如下:其中,k指粒子群中的第k个粒子,t为当前迭代次数,w为权衡局部搜索和全局搜索的参数,c1、c2为学习因子,r1、r2为0,1之间的随机数,Pk为粒子k的个体最好位置,G指引导粒子的位置, 指在第t次迭代时,粒子k的速度, 指在第t次迭代时,粒子k的位置;
所述的双距离决策方法,按下述步骤操作:
(3.1)对于每个小网格中的粒子定义两个距离:一个是粒子函数值在目标空间中的对应点到其当前所在小网格的最优点的距离d1;另一个是该粒子函数值的对应点到理想点的距离d2;
(3.2)基于d1和d2的双距离决策:某小网格中所有粒子函数值在目标空间中对应点的集合记为P,d1(pi)和d2(pi)分别表示当前小网格中粒子i函数值对应点pi的d1和d2值;某小网格中两个粒子函数值的对应点p1,p2∈P,当p1,p2满足下面两个条件时:则p1双距离支配p2,记p1<p2,p1为支配点,p2为被支配点;
(7)外部存档的更新,分别将POP和APOP、Epa和Arc合并,然后挑选出Pareto最优粒子,更新之前的外部存档,当外部存档的粒子数超过nRep时,进行外部存档删除操作,删除多余的粒子;
(8)当t>gmax时,输出Arc、APOP,否则转至步骤(5)进行循环操作;
(9)最后通过客户的需求,从外部存档中选择合适的方案。
2.根据权利要求1所述的物流系统设计方法,其特征在于,步骤(6)所述的引导粒子筛选,按下述步骤操作:(4.1)用轮盘赌方法选出密集程度小的小网格;
(4.2)在确定好小网格之后,接着计算该小网格中每个粒子函数值的d1和d2值;
(4.3)最后,通过双距离支配方法筛选出支配粒子作为引导粒子,当有多个支配粒子时,则根据Pareto最优的定义选出Pareto最优粒子,再从中随机选出一个作为引导粒子。
3.根据权利要求1或2所述的物流系统设计方法,其特征在于,步骤(7)所述的外部存档删除操作,按下述步骤操作:(5.1)通过轮盘赌方法选出密集程度大的小网格;
(5.2)在确定好小网格之后,接着计算该小网格中每个粒子目标函数值点的d1、d2的值;
(5.3)最后,通过这两个距离性质筛选出被支配的粒子作为被删除的劣质粒子;当有多个被支配的粒子时,则从中随机选择一个被支配的粒子作为劣质粒子,当没有被支配的粒子时,则在此区域中随机选择一个作为劣质粒子进行删除。