粒子群算法的物流配送路径优化研究

马毅

摘 要：物流配送的核心问题为配送路径优化问题，合理选择配送路径，对加快配送速度，降低配送成本以及增加经济效益都有着举足轻重的影响。粒子群优化算法（PSO）是最近出现的模拟鸟群寻找食物飞行行为的仿生算法，有着个体数目少、计算简单、速度快等优点，在辽宁物流配送路径中已得到应用，取得了不错的效果。本文分析了粒子群的快速性的优点，提出了一种用于求解物流配送路径优化问题的粒子群优化算法。

关键词：辽宁物流配送；粒子群算法；路径优化；

对于各种物流系统，其中一个关键环节为配送过程，在配送过程中，必须要求物流人员在客户要求的时间内采用合理的交通方式、合理的路径将货物送到目的地。物流配送路径问题的主要研究内容即为研究物流运输路径优化，即让货物运输成本最小，计算机理论、运筹学理论都在这个问题中得到了应用，最近几年取得了较丰硕的成果。

一、物流配送路径优化的数学模型

1.问题描述。相对于传统的车辆路径问题求解，物流配送路径优化更为复杂，其约束条件往往与配送车辆、货物数量、配送时间紧密相关。一般物流配送路径问题可以描述为：一个配送网络中共有 M 个客户点，已知每个客户点 i 的位置及需求量 qi，至多可用 K 辆车从配送中心到达这批需求点，每辆车从配送中心出发，最后返回配送中心，每辆车 k 的最大装载量为 Pk（k = 1，2，.....K），要求安排车辆行驶路线使车辆行驶总距离最少，并满足以下条件：第一，配送中心的位置已知且唯一；第二，配送中心只有一种车型，且每个客户点的需求只能由一辆车来完成；第三，每条线路上的客户点需求量之和不超过汽车载重量；第四，每条配送路径的总长度不大于汽车一次配送行驶的最大距离。

2.数学模型.按照1.1节描述建立的数学模型如式，其约束条件为：

其中 rk表示为该客户点在车辆 的配送路线中顺序为 j 。

二、粒子群优化算法及其改进

1.PSO 原理。PSO（Particle Swarm Optimization）算法受到真实世界中鸟群寻找食物飞行行为启发，提出的一套全新的智能优化算法。该算法将群体中的个体看成是多维空间的一个没有质量和体积的粒子，每个粒子代表问题的可行解，具有速度和位置两个属性，粒子根据本身和同伴的飞行经验进行动态调整，即每个粒子通过跟踪自身最优和群体最优来不断修正自己的位置和速度，并用粒子位置对应的适应度函数值来评价粒子的优劣程度。

2.粒子群优化算法。在 PSO 中，每个粒子通过个体极值 pbest 和全局极值gbest来更新自己的速度和位置。如果某个粒子搜索到一个局部最优解，各粒子由于受到这个最优解的吸引，容易快速聚集到它附近。导致算法过早收敛而陷入局部最优解。混沌是非线性系统中一种较为普遍的现象，行为复杂且类似随机。混沌优化算法的基本思想是首先产生一组与优化变量数目相同的混沌变量，把混沌运动的遍历范围放大到优化变量的取值范围，然后直接利用混沌变量具有的随机性、遍历性进行搜索。由于搜索混沌算法具有对初始条件的敏感、易跳出局部极小和搜索速度快的特点，基于混沌的搜索技术无疑会比其他搜索更具优越性。为克服经典粒子群算法（PSO）早熟的缺陷，文中在PSO中引入混沌思想，算法在每次迭代中将对 gbest 的混沌扰动作为更新的粒子位置，在一定程度上可以避免粒子位置趋同，并使粒子围绕在当前全局最优位置周围加强局部搜索。如果一个粒子的当前位置，该粒子的当前最优值和粒子群的当前最优值三者一致，该粒子不会因为它以前的惯性因子和速度不为零而远离最佳位置导致算法不能收敛。该算法通过添加扰动，并不影响整个算法的收敛性。

三、混沌粒子群优化算法在物流配送路径优化中的应用

1.粒子的编码策略。粒子群优化算法的关键是找到粒子的位置与问题的解相对应，借鉴编码思想，构造 2n 维的空间对应 n个客户点的物流配送路径优化问题，每个客户点对应完成服务的车辆和该车辆在路径中的执行次序，即粒子 i 对应的 2n维向量 Z 分成两个n 维向量Zix（表示服务任务的车辆编号）和 Zix（表示车辆在各客户点行驶的路径次序）。

2.粒子的解码策略。第一，对于服务任务的车辆编号，对粒子 i 的向量 Zix取整int （Zix） ，可得到配送中心分配给客户点的车辆 。第二，对于车辆j的行驶路径次序，可按照向量元素的大小顺序来确定，即首先寻找车辆 j 完成配送的客户点 i ，然后按照i 对应的的大小，从小到大进行排序编号，从而确定车辆 j 的行驶路径次序。例如，假如一个有7个客户点，3台车辆的物流配送问题，其第i 个粒子的位置向量 Z 如表1所示。

3.算法过程描述。

（1）步骤1算法初始化。输入配送网络相关数据；确定粒子群规模 n 和相关参数，即惯性权重因子、学习因子、最大迭代次数 。

（2）步骤2适应度评估。对粒子进行解码生成车辆配送方案，并根据各客户点的位置作为适应值函数来计算每个粒子的适应度函数值，即车辆行驶总距离，并且检查是否满足式中的约束条件，若某条路径上各客户点的总需求量超过此路径上配送车的容量或有车辆未被分配给客户点等。

（3）步骤3对粒子的全局最优极值进行混沌优化。先将全局最优极值映射到方程的定义域，再根据式进行迭代产生n个混沌变量系列，最后把这些产生的混沌变量系列通过逆映射返回到优化变量的取值区间，获得 n个粒子，计算每个粒子的适应度函数值，得到最优解 gbest′，用gbest′代替当前群体中粒子的位置。

（4）步骤4判断粒子群是否为早熟收敛，如果粒子群早熟收敛则对部分较优粒子进行混沌优化，否则继续执行粒子群算法。早熟收敛主要有两个标志：其一，粒子群严重聚集；其二，最优粒子在多次迭代后无变化或变化很小。

（5）步骤5对部分较优的粒子群进行混沌优化，其方法与全局最优极值 gbest 相同。由于部分粒子适应度较高，更接近全局最优解，对这些粒子进行混沌搜索，容易得到新的最优粒子。因此，为了加快搜索进程，仅让部分粒子参与搜索，混沌优化完成后，该部分粒子得到更新，粒子群的多样性增加，在随后的粒子群优化中容易摆脱局部极值，完成指定混沌优化迭代次数后，转到步驟6。步骤6输出最优解，算法运行结束。

为了提高快速找到物流配送路径最优配送路线，提高辽宁物流服务质量，提出一种粒子群算法的物流配送路径优化方法。首先根据物流配送路径问题的数学模型，然后全局搜索速度快的粒子群算法对模型进行求解，找到物流最优配送路线，最后通过具体实例进行仿真测试，结果表明，粒子群算法不仅能够快速找到物流配送路径最优配送路线，同时获得的路长总长度最短，有效降低辽宁物流配送成本。

参考文献：

[1]赵燕伟，吴斌，蒋丽. 车辆路径问题的双种群遗传算法求解方法[J]. 计算机集成制造系统，2010，10（3） ： 303 -306.

[2]陈建军. 蚁群算法在物流配送路径优化中的研究[J]. 计算机仿真，2011，28（2） ： 268 -271.

[3]沈学利，张红岩，张纪锁.一种新的改进粒子群优化算法[J].计算机仿真，2011，28（3） ： 246 -249.

作者简介：马 毅，男，1969.05.12，沈阳工业大学，硕士，研究方向：物流管理和数学，职称：副教授.