基于混合粒子群算法的物流配送路径优化问题研究

郭美，肖敏

（湘南学院软件与通信工程学院，湖南 郴州 4230000）

0 引言

标准的车辆路径问题（VRP）意味着物流中心可以为多个客户提供服务。每个用户都有一定的需求，但只能可以获得一部车服务。车辆从配送中心开始，最终返回配送中心。运送车辆不可避免的面临装载量、运送时长、运送路程等方面的限制，物流公司对这些因素充分关注的目标是使总运输成本或总时间最小化。对于这类组合问题，很难获得最优解，特别是对于大尺寸问题，要在合理的时间内获得最优解是不可能的。针对这种情况相关研究人员尝试了模拟退火算法、遗传算法等各种启发式方法来解决该问题，取得了一定成果。然而，关于车辆路径选择中多目标问题的研究很少，只有很少的研究是通过权重的方法来解决的[1-2]。

1 配送车辆路径问题

车辆配送路径的优化方案繁琐且形式多样，不同的优化方案具有不同的要素，这些要素影响着不同方案的分类标准。优化配送车辆路径时要将同批次每个客户的货物同等对待。此外，还应该将运输车辆的运送时间、客户收货时间等综合纳入路径优化的考量内容。配送中心是车辆的起点和终点，某一区域的物流配送中心可以有多个，位置也可以相对不确定，而且配送的货物也可以涉及到更多种类，以此来提升配送中心的经济和社会功能。

当多辆配送运输车从物流配送中心出发以后，其方向和行程皆不相同，每辆运输车都具有独立的行驶路线，这些不同分支的车辆行驶路线相互交叉连接就形成了物流交通网络。在整体的交通网络中，要根据路径优化问题的具体状况来因地制宜地设置满足优化方案的条件，可以根据用户对货物的种类、数目和规格的需求来设置商品的交货期限，在交付过程中要确保货物的实际负荷既在运送车辆和物流中心的承受范围内，又要确保满足不同客户的个性化需求。

2 物流配送指标体系建立

在实际物流配送中，影响因素很多，包括配送货物的重量、配送及时性、客户的不同要求和需要、总运送路径和耗油量等，这些都与物流配送路径的改善有着密切的关系。因此需要建立科学合理的物流配送指标体系，来准确的反应路径优化的不同阶段存在的具体问题。

图1 物流配送指标体系

物流配送指标体系的建立是在集合物流配送评估指标中具体影响因子的基础上完成的，体系内主要包括以下指标：商品质量水平、货物配送时效性水平、用户对配送产业的重要程度、用户取件时间安排、总配送路线、总配送油耗等。

3 粒子群优化算法及其改进

3.1 混合粒子群算法

基础的混合粒子群算法（PSO）根据不同数据组之间的交叉对比和分析来在问题空间中寻求最优化的解决方案。粒子本身不存在选择、交叉和变异等能力，因此当粒子簇位于某个局部极值附近时就不可能搜索问题空间的其余位置，混合PSO采取更改总体初始化方案并导入交叉、突变等功能来提高基本PSO的算力。将基本PSO与其他的算法进行高效有机融合不仅能够增加粒子群的多样化程度，也能够提高粒子算力以及准确性。算法结合一般有两种方法：一种是使用其他优化手段调整惯性权重和加速度等数值；另外一种则是把PSO与其他优化算法方案或其他技术手段进行有机融合。如果使用基本PSO，则其速度难以表达，因此使用遗传算法对其进行求解[3]。

3.2 算法过程描述

（1）算法初始化。导入配送物流网络中的有关数据信息，计算不同粒子群的规模与有关参数，也就是惯性权重因子、学习因子和最大迭代次数。

（2）初始化粒子群。随机产生多个n维向量，利用混沌的特征对初始值敏感，在初始值上分配很小的差异以获得初始粒子群。

（3）将混沌变量反向映射到发货的值区间。

（4）适应性评估。通过解码粒子来制定车辆运送计划，并基于每个客户点的方位来计算每个粒子的适应度函数值，也就是运输车辆需要经过的总路程，计算完成后需要核验计算结果是否满足算法的约束条件。客户点的总需求超出了此路线上送货车辆的容量，或者有尚未分配给客户点的车辆等，需要再次搜索。

（5）若是粒子的适应性高于单个极值，就把单个极值设定成系统的新数值。若是粒子的适应性高于整体极值，就把整体极值设定成系统的新数值。

（6）对粒子群的整体最优化数值做混合优化处理。首先把整体最优化数值导入进粒子群算法的定义域，然后迭代生成n个混合变量序列，最后通过逆映射将得到的变量序列反回到最优数值区间内，获得n个新粒子，然后对每个粒子进行适应性函数运算来获得系统最优解，并用其替代混合粒子群中的任一粒子的位置。

（7）确定粒子群是否会过早收敛。粒子群过早收敛后选取优等粒子进行优化，未收敛则进行粒子群算法。过早收敛主要体现在以下两个方面：一是粒子群存在紧密聚集现象；二是最优化粒子群在经过若干次迭代算法之不受影响或受影响极小。计算全局最优粒子位置不连续变化的迭代次数，当达到预设阈值时，意味着粒子群的进化缓慢而停滞。过早收敛进行步骤8；否则，请转到步骤9。

（8）一些更好的粒子群的混沌优化与全局最优极值相同。由于某些粒子适应性很强并且几乎达到最优解，因此通过对这些粒子做混合演算就很方便地获得全新的优化粒子。因此，为了加快搜索过程，只允许部分粒子参与搜索。混沌优化完成后，这部分粒子将更新，粒子群的多样性增加。在经过数次迭代演算后，转到步骤9。

（9）输出最佳解，算法操作结束。

4 建立物流配送路径优化目标函数

图2 基于混合PSO的配送车辆路径优化流程

落实物流配送路径优化方案的核心问题就是建立客观的、科学的、能够反映真实物流配送信息的数字模型，即建立综合、合理、高效的路径优化目标函数。物流配送路径优化目标函数的构建需要以物流配送评估的指标体系为基础，同时也要注重考虑实际运送过程可能会出现的问题，如天气和交通路况干扰等。配送指标体系中，商品质量水平、货物配送时效性水平、用户对配送产业的重要程度、用户取件时间安排和配送货物或用户的客观属性相关。一旦具体的商品或用户确定以后，这些参数就固定不变了。但是分配顺序的变化会影响总体目标函数，并且总体路径指标是可变的，与货物配送次序和货物的种类性质直接相关[4]。

4.1 物流配送指标函数

（1）商品质量水平。货物的质量是在运送过程中必须考虑的影响因素。通常，如果条件允许，应首先派遣重物以减少总燃料消耗。

（2）货物配送时效性指标。随着电商的飞速发展和物流运输网络的深入建设，以及人们对冷鲜类物品需求量的不断增加，物流配送行业及工作人员面临的挑战日益严峻，如何提高配送效率、减少配送时间是每个从业者都应思考的，这直接影响着物流业的未来发展。

（3）用户对配送产业的重要程度。用户的多少与消费水平对配送产业具有深刻的影响，为了提高用户对物流配送公司的消费率，提升物流公司的口碑，在货物运输过程中要优先派送高级客户的物品。

（4）用户取件时间安排。该指标能够反映每个客户的取件时间要求，有益于提升物流企业的派件精确度和用户的取件成功率，确保客户保持对物流公司的消费满意度，因此具体货物的物流交付必须考虑到客户的时间安排。

（5）总配送路线。不同地区、不同时间的具体物流配送的路线是不尽相同的，因此总配送路线里程也存在差异，如果想增加物流配送工作的实际效率，总路程是不得不考虑的方面之一。

（6）总配送油耗。物流配送路程中的总耗油量也是配送产业需要考虑的指标之一。油耗水平直接影响到配送所需要的资金，这和配送车辆的载货量、配送里程，以及配送过程中的路况、天气等客观因素相关[5]。

4.2 物流配送路径优化目标函数

该目标函数是根据配送指标评估函数和权重信息来建立的，它能够将商品质量水平、货物配送时效性水平、用户对配送产业的重要程度、用户取件时间安排、总配送路线、总配送油耗等指标的权重信息和正比例增益数值进行综合运算，并通过混合粒子群算法做一定的优化，以此来设计出最优的物流配送路径。

5 结语

本文提出了一种新的混合粒子群算法来解决物流配送路线优化问题，以期为该问题的改进研究提供研究思路和理论支持。与其他算法的计算结果相比，混合粒子群算法在提高解的质量和速度方面优于单独的PS0算法和其他算法，是解决物流配送路线优化问题的较好方法。