模糊粒子群优化算法的第四方物流运输时间优化

卢福强，刘婷，杜子超，毕华玲，黄敏

（1. 燕山大学 经济管理学院，河北 秦皇岛 066004; 2. 东北大学 信息科学与工程学院，辽宁 沈阳 816819）

随着信息技术的发展，很多制造型企业将物流业务外包给第三方物流代理商(third party logistics, 3PL)，由他们承担仓储、运输等任务。对于一些大型企业，多元化、国际化的趋势逐渐增强，供应链策略的设计、优化要与企业的竞争策略相辅相成，考虑内外环境因素的影响，这一问题已然成为一个规模庞大、构造复杂的系统工程[1]。但是3PL只承担实际的物流操作业务，在资源配置、统筹规划、集成技术、综合技能等方面存在一定的局限性，无法实现整个物流系统的优化[2]。美国埃森哲(Accenture)咨询公司在1996年最先提出了第四方物流(fourth party logistics, 4PL)的概念[3]，4PL是在3PL的基础上发展起来的，通过集合资源、技术、能力来构建一套完整的供应链解决方案[4]。与3PL相比，4PL具备获取资源和协调规划的能力[5]。企业将供应链的整体优化外包给4PL，4PL通过一系列的考察、分析、规划、设计，将具体的物流作业外包给3PL，进一步提升物流运输的效率，同时使企业能够将自身的资源用于其核心业务[6]。

4PL具有明显的优势，在物流领域中起到举足轻重的作用，得到了国内外学者的广泛研究。同时，4PL也面临着巨大挑战，归结起来可分为2个方面：1)黄敏等[7]提出4PL如何激励3PL提高物流服务质量并降低配送过程中的风险问题；2)如何对资源进一步整合优化使得3PL在可以接受的配送成本条件下提高物流服务质量，使得3PL切实感受到4PL的加入可以使它们能够将自身资源用于其核心业务。因此，考虑在委托商可接受的最大成本约束下，提高加入4PL后的3PL的物流服务质量具有重要研究价值。本文对4PL的路径优化问题进行研究，缩短配送时间，提高物流服务质量。关于4PL的运输路径优化问题，综合考虑3PL的能力、信誉、转运时间及运输成本等因素的影响，如黄敏等[7]充分考虑不确定环境的影响，将3PL代理商的配送时间设定为不确定变量，建立了4PL路径规划模型，并采用多种改进的遗传算法进行求解；崔研等[8]考虑中转发车时间，以运输时间为约束条件，以总成本最小为目标函数，建立了基于一点到多点的多任务第四方物流路径优化模型，并设计蚁群优化算法求解模型；薄桂华等[9]将嵌入删除算法和声搜索算法两阶段算法，用于加快求解带时间窗约束的4PL路径优化问题的运行时间；王勇等[10]考虑了时间和风险因素的约束，研究多任务、多代理商的4PL作业整合优化，采用柔性禁忌算法求解模型[10]；崔研等[11]结合模糊的转运时间和最小的成本约束，研究多点到单点的4PL路径优化问题，设计文化基因算法求解模型；陈建清等[12]建立了赋予多维权的有向图模型，描述第四方物流中路径优化、3PL代理商选择等问题，并提出基于Dijkstra算法的求解方法。对于4PL的路径优化问题，既要考虑委托商提出的成本约束，又要满足客户对运输时间的期望。同时，由于运输环境的不确定性，各个3PL代理商运输能力的不同，城市节点中存在的转运时间，4PL路径优化已然成为一个复杂、影响因素相互制约的系统工程问题。在一定的成本预算约束下，如何设计运输路径，选择合适的3PL代理商，形成一套完整的供应链解决方案以实现客户期望的时间，已经成为4PL亟待解决、不断优化的问题。

本文针对4PL运作中的运输时间优化问题，建立了4PL运输时间优化模型。引入收敛因子和隶属度函数，对基本粒子群优化算法(particle swarm optimization, PSO)进行改进，设计收敛模糊粒子群优化算法(convergence fuzzy particle swarm optimization, CFPSO)对4PL运输时间优化问题进行求解。通过3个规模逐渐增大的算例对CFPSO算法的性能进行验证，并且将实验结果与基本PSO、枚举算法(enumeration algorithm, EA)、遗传算法(genetic algorithm, GA)和量子粒子群优化算法(quantum-behaved particle swarm optimization,QPSO)对本问题的求解结果进行比较分析。

1 第四方物流运输时间优化问题

1.1 第四方物流运输问题

在4PL运作中，第四方物流公司通过路径网络图选择合适的路线，将货物从起点城市运输到终点城市。图1为运输路线网络图。

图1 运输路线网络Fig.1 Transport route network

图1中的每个节点表示一个城市，节点1表示起点，节点6表示终点。在物流运输路线上，每两个连通的节点之间有2个备选的代理商，分别是代理商a和代理商b。本文考虑在一定的运输成本约束下，通过选择最佳路径和合适的代理商，实现整体物流作业运输时间最短的目标。

1.2 运输时间优化模型

1.2.1 模型假设与符号定义

1)模型假设

①每个作业任务至多由一个代理商负责完成。

②本问题是单任务问题，且只有一个起点和一个终点。

③从出发点运送到终点的过程中，任务需要完成的总运输量不会改变。

2)符号定义

作业在节点i与节点j之间选择代理商g完成。

Q：从配送起点到配送终点需要被配送的总运量。

Qg：代理商g能够承担的最大运量。

dij：节点i与节点j之间的距离。

代理商g在节点i与节点j之间单位运输距离、单位运载量的运输成本。

代理商g在节点i与节点j之间运输单位运量货物的运输时间。

C：委托人能够承担的最大运输成本。

G：代理商的个数。

N：网络中的节点数量。

1.2.2 数学模型

2 收敛模糊粒子群优化算法

4PL运输时间优化问题的自变量众多，且对算法的运行时间和运行结果的精度要求高，因此采用PSO算法进行求解。PSO算法是一种模拟自然界鸟类觅食过程的生物启发式算法[12-13]。PSO初始化为一群随机粒子，这些粒子在搜索空间中4处移动来寻找问题最佳的解。Shi等[14]引入惯性权重的概念，被大家认为是标准的粒子群优化算法。

模糊粒子群优化算法(fuzzy particle swarm optimization, 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算法改进策略

通过加入隶属度函数和收敛因子来更新飞行速度与状态。

式中： ω为惯性权重，在[0,1]之间取值，用来衡量粒子i保留上一次迭代速度的大小， ω 越大，本次迭代速度与上一次的迭代速度越接近；c1为自我学习因子；c2为社会学习因子，是两个常量，使粒子具有自我总结和向群体中优秀个体学习的能力；r1和r2是两个在0～1取值的随机数；k为收敛因子； φ (h) 为隶属度函数。

式(6)为粒子的速度更新公式，式(8)是粒子的位置更新公式[16]。隶属度表示为一个模糊变量，本文基于Bell函数建立隶属度函数[17]，如式(9)所示：

式中：f(pg) 表示由全局最优粒子的位置计算得来的适应值，即最小的运输时间；f(ph) 表示某粒子的邻居粒子的适应值；β 是一个常数。由式(9)可以看出，该邻居粒子的适应值越接近于全局最优的适应值，所对应的模糊隶属度就越大，对该粒子的影响程度就越大，反之亦然。这样粒子就能够更加充分、合理地利用周围若干邻居粒子的优点。

2.3 适应度函数

设计罚函数来构造适应度函数：

式中：w1、w2、w3都为惩罚项的系数。

2.4 CFPSO算法流程

CFPSO算法流程见图2。

图2 CFPSO的流程Fig.2 Solution procedeure of the CFPSO

3 算例设计

本节给出3个不同规模的算例，某物流公司承担运量为100 t的运输任务，在3个规模不同的运输网络中，要求给出在不同的运输成本约束下最小的运输时间、运输路线方案。

3.1 算例1

运输网络有6个节点城市，起点城市是杭州，终点城市是淮安。有2种代理商可以承担每段路径具体的运输任务，代理商的运输能力、报价信息如表1所示，每两个相通城市节点之间的距离如表2所示。

表1 算例1代理商运输信息Table 1 Details of the transportation agency in case 1

表2 算例1城市间距离Table 2 Distances between cities in case 1 km

3.2 算例2

运输网络有12个节点城市，起点城市是杭州，终点城市是石家庄。有3种代理商可以承担每段路径具体的运输任务，代理商的运输能力、报价信息如表3所示，每两个相通城市节点之间的距离如表4所示。

表3 算例2代理商运输信息Table 3 Details of the transportation agency in case 2

表4 算例2城市间距离Table 4 Distances between cities in case 2 km

续表4

3.3 算例3

运输网络有18个节点城市，起点城市是杭州，终点城市是石家庄。每两个相通城市节点之间的距离如表5所示，有3种代理商可以承担每段路径具体的运输任务，代理商的运输能力、报价信息和算例2中相同。

表5 算例3城市间距离Table 5 Distances between cities in case 3 km

4 实验与结果分析

4.1 CFPSO参数设置

4.1.1 收敛因子k的确定

为了确定收敛因子k的最优取值，以算例3为例，进行数值仿真实验，设委托商提出的最大成本约束为100 000元，种群由20个粒子构成，每个粒子有18维搜索空间，代表着18个城市节点，以算法循环迭代100次为停止准则。c1和c2分别在[1,6]和[0,6]之间取值，将最小运输时间作为粒子的适应值。图3是2种学习因子的取值组合对适应值的影响。

图3 学习因子对适应值的影响Fig.3 Influence of learning factors on fitness value

可以看出，随着c1和c2取值组合的不同，测试函数的适应值存在一定的波动性，但以上的两个二维曲面图的大致趋势基本相同，当c1和c2都接近于2时，适应值即最小的运输时间明显小于其他取值范围输出的结果。

表6适应值与c1 和c2的关系Table 6 Relationshipbetweenfitnessvalues c1 andc2

4.1.2 隶属度函数中参数 β 的确定

本节仿真实验参数 β 取值为0～100，跨度为0～0.5的离散点，仍以算例3为例，设最大成本约束为100 000元，种群由20个粒子构成，每个粒子有18维搜索空间，以循环迭代100次为停止准则，计算最小的运输时间。实验结果如图4所示。

图4 参数 β 对适应值的影响Fig.4 Influence of β on fitness value

从图4中可以看出，随着参数 β 的不断变化，适应值以40为基准呈现上下波动，当β∈[26,29]时，结果最好。将 β 取值为整数，分别令 β=26、27、28、29，计算最小运输时间，得到的结果如图5所示。

图5 参数 β 对适应值的影响Fig.5 Influence of β on fitness value

从图5可以看出，当 β =28 时，在各个最大运输成本条件的约束下，CFPSO算法得到的运输时间最小，隶属度函数中的参数 β 取值为28。

4.2 实验结果

为了说明问题这里仅给出算例3的实验结果，见表7。从实验结果可以看出：1)随着运输成本约束的增加，负责每段路径的代理商在不断地变化，最小运输时间也逐渐减少，通过不同的成本约束来控制货物的运输时间；2)委托商给出的整个运输方案的成本预算越多，CFPSO算法运行出的最佳运输路径越倾向于选择速度快的代理商承担运输任务，即花更多的钱来实现运输时间的最优化。

表7 实验结果(算例3)Table 7 Experimental results (case 3)

4.3 多种算法的对比分析

为了验证CFPSO算法的性能，本节采用枚举算法(EA)、基本PSO算法、GA算法和量子粒子群优化(QPSO)算法[18-25]求解上述3个算例，并从最小运输时间、CPU时间等方面进行对比分析。各算例实验结果的对比分别列于表8、9、10中。

表8 各算法运行结果(算例1)Table 8 Results obtained from the algorithm (case 1)

表9 各算法运行结果(算例2)Table 9 Results obtained from the algorithm (case 2)

续表9

表10 各算法运行结果(算例3)Table 10 Results obtained from the algorithm (case 3)

综合以上5个算法对3个算例的实验结果，可以得出以下结论：

1)实验结果角度

当算例的规模比较小时，如算例1，根据5个算法得到的平均运输时间的优劣性，如图6所示，可以将算法按照收敛能力排序为：QPSO>EA>CFPSO>GA>基本PSO。当算例的规模增大时，如算例2，如图7所示算法收敛能力排序为：CFPSO=EA=GA>基本PSO>QPSO。当算例规模很大时，如算例3，EA已经不能在可接受的时间内运行出结果，如图8所示，其他4种算法的收敛能力排序为： CFPSO>GA>基本PSO>QPSO。

图6 算例1实验结果对比Fig.6 Comparison of experimental results in case 1

图7 算例2实验结果对比Fig.7 Comparison of experimental results in case 2

图8 算例3实验结果对比Fig.8 Comparison of experimental results in case 3

2)CPU时间角度

随着3个算例规模的逐渐增大，算法程序的复杂度也显著增加，在这里将城市个数、代理商个数这两个变量的乘积作为各算例程序的时间复杂度，即T(mn)=O(n2),m是代理商的个数，n是城市的个数。算例1、2和3的时间复杂度分别为12、36、54。从图9中可以看出，随着各算例运输方案个数的增加，EA算法的运行时间呈现快速增长的趋势，相比之下，基本PSO算法和GA算法的增长速度适中，QPSO算法的CPU运行时间较为缓慢，CFPSO算法的增长速度则最为缓慢。可见，CFPSO算法中收敛因子加快程序运行的作用比较明显，随着程序复杂度的增加，CFPSO算法的运行时间始终小于其他3种算法，具有一定的稳定性。可将4种算法的运行速度进行以下的排序： CFPSO>QPSO>GA>基本PSO>EA。

图9 各算法运行时间对比分析Fig.9 Comparison of the algorithm’s run time

综上所述，CFPSO、QPSO、GA、基本PSO和EA求解本优化问题时各有优劣。针对第四方物流运输时间控制问题，选取最适合的求解算法应从实验结果、CPU时间这两个方面来衡量。通过以上的分析，可以将这4种算法的性能进行排序：CFPSO>GA>QPSO>基本PSO>EA。

5 结束语

本文针对第四方物流运输时间优化问题，建立了数学模型，设计了收敛模糊粒子群优化算法，设计了多个算例进行实验分析。实验结果分析表明，建立的数学模型合理，能够辅助决策，提供满足运输成本和运输时间要求的决策方案。所设计的收敛模糊粒子群优化算法与枚举算法、基本粒子群优化算法、遗传算法和量子粒子群优化算法相比具有更好的收敛能力和更快的收敛速度，能够有效地解决第四方物流运输时间优化问题，具备可行性。