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

粒子群算法的物流配送路径优化研究摘要：物流配送的核心问题为配送路径优化问题合理选择配送路径对加快配送速度降低配送成本以及增加经济效益都有着举足轻重的影响。粒子群优化算法（PSO）是最近出现的模拟鸟群寻找食物飞行行为的仿生算法有着个体数目少、计算简单、速度快等优点在辽宁物流配送路径中已得到应用取得了不错的效果。本文分析了粒子群的快速性的优点提出了一种用于求解物流配送路径优化问题的粒子群优化算法。关键词：辽宁物流配送；粒子群算法；路径优化；对于各种物流系统其中一个关键环节为配送过程在配送过程中必须要求物流人员在客户要求的时间内采用合理的交通方式、合理的路径将货物送到目的地。物流配送路径问题的主要研究内容即为研究物流运输路径优化即让货物运输成本最小计算机理论、运筹学理论都在这个问题中得到了应用最近几年取得了较丰硕的成果。一、物流配送路径优化的数学模型1.问题描述。相对于传统的车辆路径问题求解物流配送路径优化更为复杂其约束条件往往与配送车辆、货物数量、配送时间紧密相关。一般物流配送路径问题可以描述为：一个配送网络中共有M个客户点已知每个客户点i的位置及需求量qi至多可用K辆车从配送中心到达这批需求点每辆车从配送中心出发最后返回配送中心每辆车k的最大装载量为Pk（k=12.....K）要求安排车辆行驶路线使车辆行驶总距离最少并满足以下条件：第一配送中心的位置已知且唯一；第二配送中心只有一种车型且每个客户点的需求只能由一辆车来完成；第三每条线路上的客户点需求量之和不超过汽车载重量；第四每条配送路径的总长度不大于汽车一次配送行驶的最大距离。2.数学模型.按照1.1节描述建立的数学模型如式其约束条件为：其中rk表示为该客户点在车辆的配送路线中顺序为j。二、粒子群优化算法及其改进1.PSO原理。PSO（ParticleSwarmOptimization）算法受到真实世界中鸟群寻找食物飞行行为启发提出的一套全新的智能优化算法。该算法将群体中的个体看成是多维空间的一个没有质量和体积的粒子每个粒子代表问题的可行解具有速度和位置两个属性粒子根据本身和同伴的飞行经验进行动态调整即每个粒子通过跟踪自身最优和群体最优来不断修正自己的位置和速度并用粒子位置对应的适应度函数值来评价粒子的优劣程度。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适应度评