第1期 彭扬，等：定位运输路线安排问题的改进离散粒子群优化算法 ·77 属度为1，经过权重因子w、αB的作用后，客户服务 定义3粒子群的多样性可以通过粒子趋同度 于设施的隶属度被更新，按照隶属度的大小排序，确 认为设施所服务的客户集合；同时考虑设施的服务 p来测度p-名（®e）.显然ee【0,1,这 容量，如果最大隶属度的设施容量溢出，则依次考虑 里N表示粒子群规模， 次大隶属度的设施，完成客户点对设施的重新分配， 趋同扰动算子是在粒子趋同度下降到一定程度 即LA(location-allocation)部分. 时，按概率在粒子群中随机选择一些粒子，仿照初始 2)关于客户在设施服务序列中的顺序合成与 化粒子群的方法产生同样数量的粒子进行置换， 更新. 2.6算法流程 粒子编码中，每个客户在相应的设施中都有一 应用改进离散粒子群优化算法解决定位分 个服务的顺序数，在3个粒子（当前粒子位置x,、子 配运输路径问题的实现步骤为 群历史最优位置xm、粒子群历史最优位置xt) 1)设定参数，粒子种群规模，最大迭代次数，粒 经过权重因子、B的加成后，在已经确认的设施 子运动方程的3个权重因子；设定划分粒子子群数 服务的客户集合中，对其中每个客户的加成后的顺 和重叠粒子数，粒子增加设施开放变异率日，和关闭 序数（这时为实数）进行整数规范，并按从小到大排 设施变异率02；设定粒子趋同度阀值p和趋同扰动 序，得到更新后的顺序数. 算子粒子选择概率03. 例如，设8个客户点，4个候选设施，t时刻某粒 2)初始化操作. 子位置编码以及子群最优和全局最优的粒子位置编 设P为满足客户需求的最小设施数，随机选 码分别为 择p(这里p≥P,且p≤M)个设施开放服务，按设 23516748 施对客户的吸引度，依次插入客户点并保证满足设 x。= 11122233 施服务容量约束，如果某设施点服务的客户集合为 21313221 空，则关闭该设施.对于设施服务的客户集合，随机 /35672418Y 产生设施服务序列 11112233 3)划分粒子群的子群，并评价每个粒子的适应 13421221 度，得到每个子群的初始xt,并将种群中最高适应 23615748 值的粒子位置设为rea r中eat 11122233 4)更新粒子位置并评价， 21323121 根据粒子运动方程，更新粒子位置；计算粒子适 应值，更新各子群的xe和全局的re 设0=0.3，a=0.3,B=0.4,阈值0=0.5，在设施容 5)变异和趋同扰动. 量约束没有冲突（即只考虑最大隶属度）的情况下， 对每个粒子产生[0,1]间的随机数c1和c2,如 得到粒子位置的更新为 果c1>01则该粒子进行增加设施开放变异操作，并 23561748 同时判断如果c2>02则该粒子进行关闭设施变异 +曰 11112233 操作，产生新粒子； 21342121 计算粒子发散度”，如果”大于粒子趋同度阀 2.5 趋同扰动算子 值P,则按照趋同扰动算子的粒子选择概率选择 在进化过程中，由于粒子运动方程的作用，粒子 一定量的粒子进行趋同扰动操作，产生一批新粒子 趋同性越来越显著，而多样性则迅速下降，为了克服 并更新粒子群， 优化算法的早熟和易于陷入局部极值的缺陷，引入 6)判断是否满足终止条件或达到最大迭代次 趋同扰动算子来增加算法的全局优化能力. 数，是则进化停止并转下一步；否则回4)，重复执 定义2 粒子位置的“异或”操作，以符号“☒” 行粒子群更新. 运算表示。 7)解析粒子编码，得到近似最优解(LA和VRP x:☒x,= 2部分的)和目标函数值. r1,x:=x,这里的“=”表示2个粒子 位置向量完全一致； 3算例分析 0. 其他。 为了分析算法的有效性及可行性，本文使用