·476· 智能系统学报 第16卷 Qg:代理商g能够承担的最大运量。 和收缩因子引入PSO的速度更新公式，从而设计 4:节点i与节点j之间的距离。 收敛模糊粒子群优化算法(convergence fuzzy c:代理商g在节点i与节点j之间单位运输 particle swarm optimization,CFPSO)。CFPSO不仅 距离、单位运载量的运输成本。 可以保证算法的收敛速度，加快全局收敛，还能 :代理商g在节点i与节点j之间运输单位 丰富种群的多样性，减小搜索粒子陷入局部最优 运量货物的运输时间。 的概率，提升算法的整体运算精确度，涵盖了众 C:委托人能够承担的最大运输成本。 多改进PSO算法的优势与特点。 G:代理商的个数。 2.1基本PS0算法求解 N:网络中的节点数量。 将基本的PSO算法应用到第四方物流运输 1.2.2数学模型 时间控制问题中，在编码方面，每个粒子被设定 为一个备选方案，搜索空间的维数为运输问题中 Min (1) =111 的城市个数，粒子的位置状态信息即是从起点城 NN 市向终点城市运输货物的路径。因此，本文采用 st∑∑∑dc≤C (2) 多进制的编码方式，0表示运输路径不经过该城 市，1表示运输路径经过该城市且选择1号代理 <1iew-je.2…. 商承担此段运输任务，2、3等数字与上述意义相 (3) 同；在初始化种群方面，采用随机初始化的方式， 8∈1,2，…，G Q≤Q,g∈1,2，…，G 若有两个代理商可供选择，则粒子每一维搜索空 (4) ∫1，作业在节点与之间选代理商g 间的初始位置在0、1、2中随机产生。第一维与 0,作业在节点与之间未选代理商 (5) 最后一维空间除外，因为这两维代表的是运输路 式(1)为目标函数，表示最小化物流运输时 线的起点城市与终点城市，粒子的位置在1、2中 间；式(2)表示各段路径的运输成本之和不超过 随机选取。在选择策略方面，采取优胜劣汰的选 委托人所能承担的最大成本；式(3)表示至多有 择策略。首先，将粒子当前的适应值与自身历史 一个代理商负责节点i到节点j的运输任务；式 最优值得出的适应值进行比较，若当前的适应值 (4)表示运输货物的运量不超过代理商所能承受 优于自身历史最优值，则更新该粒子的个体历史 的最大运量；式（⑤）表示当作业在i点与j之间选 最优值。然后，对所有粒子的个体历史最优值进 择代理商g完成时，=1；否则=0。 行比较，择优选取当代全局最优值，若优于原值， 则进行更新，否则进入下次循环，并且以最大迭 2收敛模糊粒子群优化算法 代次数为终止条件。 4PL运输时间优化问题的自变量众多，且对 2.2PS0算法改进策略 算法的运行时间和运行结果的精度要求高，因此 通过加人隶属度函数和收敛因子来更新飞行 采用PSO算法进行求解。PSO算法是一种模拟 速度与状态。 自然界鸟类觅食过程的生物启发式算法21。 v=kwv+cir(p+>v(h)cara(](6) PSO初始化为一群随机粒子，这些粒子在搜索空 heBlit) 间中4处移动来寻找问题最佳的解。Shi等1引 k=2/2-φ-V2-4例，中=c1+c2 (7) 入惯性权重的概念，被大家认为是标准的粒子群 x1=+ (8) 优化算法。 式中：ω为惯性权重，在[0,1]之间取值，用来衡量 模糊粒子群优化算法(uzzy particle swarm op- 粒子i保留上一次迭代速度的大小，ω越大，本次 timization,FPSO)l通过改变影响粒子飞行速度、 迭代速度与上一次的迭代速度越接近；c1为自我 方向的状态更新公式，保持了种群的活跃度，使 学习因子；2为社会学习因子，是两个常量，使粒 得算法的精确度大大提升。但是，FPSO需要较 子具有自我总结和向群体中优秀个体学习的能 长的收敛时间。为了缩短收敛时间，可以引入收 力；1和2是两个在0~1取值的随机数；k为收敛 缩因子，形成收敛粒子群优化算法(convergence 因子；p(h)为隶属度函数。 particle swarm optimization,CPSO),相关实验表明 式(6)为粒子的速度更新公式，式(8)是粒子的 此举可以大大提升整个种群的收敛速度。本文 位置更新公式。隶属度表示为一个模糊变量，本文 考虑吸收FPSO和CPSO的长处，将隶属度函数 基于Bell函数建立隶属度函数m,如式(9)所示：Qg：代理商 g 能够承担的最大运量。 di j ：节点 i 与节点 j 之间的距离。 c g i j ：代理商 g 在节点 i 与节点 j 之间单位运输 距离、单位运载量的运输成本。 t g i j ：代理商 g 在节点 i 与节点 j 之间运输单位 运量货物的运输时间。 C ：委托人能够承担的最大运输成本。 G ：代理商的个数。 N ：网络中的节点数量。 1.2.2 数学模型 Min ∑G g=1 ∑N i=1 ∑N j=1 t g i jx g i j (1) s.t. ∑G g=1 ∑N i=1 ∑N j=1 di jc g i jQxg i j ⩽ C (2) ∑N j=1 x g i j ⩽ 1,i ∈ {N −{1}}, j ∈ {1,2,··· ,N}, g ∈ {1,2,··· ,G} (3) Q ⩽ Qg,g ∈ {1,2,··· ,G} (4) { 1, 作业在节点i与j之间选代理商g 0, 作业在节点i与j之间未选代理商 (5) i j i j g x g i j = 1 x g i j = 0 式 (1) 为目标函数，表示最小化物流运输时 间；式 (2) 表示各段路径的运输成本之和不超过 委托人所能承担的最大成本；式 (3) 表示至多有 一个代理商负责节点 到节点 的运输任务；式 (4) 表示运输货物的运量不超过代理商所能承受 的最大运量；式 (5) 表示当作业在 点与 之间选 择代理商 完成时， ；否则 。 2 收敛模糊粒子群优化算法 4PL 运输时间优化问题的自变量众多，且对 算法的运行时间和运行结果的精度要求高，因此 采用 PSO 算法进行求解。PSO 算法是一种模拟 自然界鸟类觅食过程的生物启发式算法[ 1 2 - 1 3 ]。 PSO 初始化为一群随机粒子，这些粒子在搜索空 间中 4 处移动来寻找问题最佳的解。Shi 等 [14] 引 入惯性权重的概念，被大家认为是标准的粒子群 优化算法。 模糊粒子群优化算法 (fuzzy particle swarm op￾timization, FPSO)[15] 通过改变影响粒子飞行速度、 方向的状态更新公式，保持了种群的活跃度，使 得算法的精确度大大提升。但是，FPSO 需要较 长的收敛时间。为了缩短收敛时间，可以引入收 缩因子，形成收敛粒子群优化算法 (convergence particle swarm optimization, CPSO)，相关实验表明 此举可以大大提升整个种群的收敛速度[16]。本文 考虑吸收 FPSO 和 CPSO 的长处，将隶属度函数 和收缩因子引入 PSO 的速度更新公式，从而设计 收敛模糊粒子群优化算法 (convergence fuzzy particle swarm optimization, CFPSO)。CFPSO 不仅 可以保证算法的收敛速度，加快全局收敛，还能 丰富种群的多样性，减小搜索粒子陷入局部最优 的概率，提升算法的整体运算精确度，涵盖了众 多改进 PSO 算法的优势与特点。 2.1 基本 PSO 算法求解 将基本的 PSO 算法应用到第四方物流运输 时间控制问题中，在编码方面，每个粒子被设定 为一个备选方案，搜索空间的维数为运输问题中 的城市个数，粒子的位置状态信息即是从起点城 市向终点城市运输货物的路径。因此，本文采用 多进制的编码方式，0 表示运输路径不经过该城 市，1 表示运输路径经过该城市且选择 1 号代理 商承担此段运输任务，2、3 等数字与上述意义相 同；在初始化种群方面，采用随机初始化的方式， 若有两个代理商可供选择，则粒子每一维搜索空 间的初始位置在 0、1、2 中随机产生。第一维与 最后一维空间除外，因为这两维代表的是运输路 线的起点城市与终点城市，粒子的位置在 1、2 中 随机选取。在选择策略方面，采取优胜劣汰的选 择策略。首先，将粒子当前的适应值与自身历史 最优值得出的适应值进行比较，若当前的适应值 优于自身历史最优值，则更新该粒子的个体历史 最优值。然后，对所有粒子的个体历史最优值进 行比较，择优选取当代全局最优值，若优于原值， 则进行更新，否则进入下次循环，并且以最大迭 代次数为终止条件。 2.2 PSO 算法改进策略 通过加入隶属度函数和收敛因子来更新飞行 速度与状态。 v t+1 i = k [ ωv t i +c1r1 ( p t i − x t i ) + ∑ h∈B(i,k) φ(h) c2r2 ( p t h − x t i ) ] (6) k = 2/   2−ϕ− √ |ϕ 2 −4ϕ|   , ϕ = c1 +c2 (7) x t+1 i = x t i +v t+1 i (8) ω i ω c1 c2 r1 r2 k φ(h) 式中： 为惯性权重，在 [0,1] 之间取值，用来衡量 粒子 保留上一次迭代速度的大小， 越大，本次 迭代速度与上一次的迭代速度越接近； 为自我 学习因子； 为社会学习因子，是两个常量，使粒 子具有自我总结和向群体中优秀个体学习的能 力； 和 是两个在 0~1 取值的随机数； 为收敛 因子； 为隶属度函数。 式 (6) 为粒子的速度更新公式，式 (8) 是粒子的 位置更新公式[16]。隶属度表示为一个模糊变量，本文 基于 Bell 函数建立隶属度函数[17] ，如式 (9) 所示： ·476· 智 能 系 统 学 报 第 16 卷