基于改进粒子群算法的物流配送车辆调度优化
吴 聪1，杨建辉2
【摘 要】车辆优化调度是提高物流企业运营效益的重要因素，针对标准粒子群优化算法存在的不足，提出一种改进粒子群算法（IPSO）的物流配送车辆调度优化方法。建立物流配送车辆调度优化的数学模型，将车辆与车辆路径编码成粒子，通过粒子之间的协作找到最优物流配送车辆调度优化方案，并对粒子群算法存在的不足进行了相应的改进，最后给出仿真实验对其性能进行测试。实验结果表明，IPSO算法不仅加快了物流配送车辆调度优化问题求解的速度，而且获得了最优解的概率，具有比其他调度算法更明显的优势。 【期刊名称】计算机工程与应用 【年(卷),期】2015(000)013 【总页数】5
【关键词】物流配送；车辆路径调度问题；粒子群算法；目标函数
1 引言
随着经济全球的发展，企业之间的竞争日益激烈，对物流配送成本对企业利润具有重要的影响，合理安排物流车辆调度方案可以在满足用户满意度的条件下，降低企业运营成本，提高企业的竞争力，因此如何合理优化物流配送车辆调度，及时、科学、准确地将商品送到用户手中，提高企业的利润一直是物流管理领域研究的热点[1]。
由于物流配送车辆优化调度问题（Vehicle Routing Problem，VRP）具有的实际应用价值，引起了广泛学者和研究机构的关注，1995年，Dantzing等将物流配送车辆优化调度问题定义为，在给定物流配送的发货点和收货点，通过
合理安排的配送车辆的行驶路线，在满足一定约束条件，如货物需求量、行驶时间限制等，最可能的使行配送车辆的行程最短，费用最少[2]。当前有许多物流配送车辆调度优化算法，主要分为两类：精确算法和启发式算法[3]。精确算法主要有分枝限界法、动态规划等[4-5]，对于小规模的物流配送车辆优化调度问题，其具有求解速度快，求解精度高等优点，但是其计算复杂度与问题规模之间呈几何级数变化关系，不能满足现代物流实际应用需求[6]。相对于精确算法，启发式算法具有求解效率高等优点，已成为当前求解物流配送车辆调度问题的主要研究方向，出现了基于遗传算法、蚁群算法、粒子群算法等物流配送车辆调度优化方法[7-10]，获得了较优的调度方案，然而在实际应用中，遗传算法初始种群产生十分敏感，粒子群算法收敛后期易陷入局部最优解，蚁群算法易受参数影响，计算量大等缺陷[11]。
为了获得更加理想的物流配送车辆优化调度方案，针对标准粒子群算法的不足，提出了一种改进粒子群算法（IPSO）的物流配送车辆优化调度方法。实验结果表明，IPSO算法不仅加快了物流配送车辆优化调度问题的求解速度，而且提高了找到最优方案的成功率。
2 车辆优化调度问题的数学模型
设配送中心有M辆车，其载重量分别为qk(k=1，2，…，M)，N个收货点，其所需的货运量分别为gi(k=1，2，…，M)且，物流配送车辆优化调度的目标以总费用最小，在建立物流配送车辆优化调度问题的数学模型之前，首先做如下假设：
（1）每条路径的货物需求量总和要小于配送车辆的载重量； （2）每个收货点仅能由一辆车送货[12]。
cij为点i到点 j的费用，Z为所有车辆行驶的总费用，则物流配送车辆优化调度问题的数学模型可以描述为： 相应的限制条件为： 其中：
3 改进粒子群算法
3.1 标准粒子群算法
粒子群优化（PSO）算法是一种基于迭代的优化工具，具有实现容易，鲁棒性好，收敛快等优势，很适合在工程实践中应用。设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量 Xi=(xi1，xi2，…，xiD)，第 i个粒子迄今为止搜索到的最优位置为Pi=(pi1，pi2，…，piD)，整个粒子群迄今为止搜索到的最优位置为Pg=(pg1，pg2，…，pgD)，第i个粒子位置的变化率（速度）为向量Vi=(vi1，vi2，…，viD)。每个粒子的位置按如下公式进行变化： 其中，c1、c2为正常数，称为加速常数；rand()为[0，1]之间的随机数；ω为惯性权重[13]。 3.2 粒子群算法的改进
在标准粒子群算法中，易出现过早收敛于局极值缺点，这主要因为在搜索后期，粒子位置缺乏多样性。经过试验表明，可以假设在初始搜索时使用比较大的C1，而比较小的C2，这样就使得粒子能够比较自由的分散到搜索空间中去，受到“社会意识部分”的微弱影响，以此使得粒子的多样性得到增加。而随着迭代次数的增加，让C1线性递减，而C2线性递增，那么随着迭代次数的增加，C1变小，而C2增大，加强了粒子全局最优的收敛能力。公式如下：
式中，C1e、C2e为加速因子 C1、C2的终值；C1s、C2s为加速因子C1、C2
基于改进粒子群算法的物流配送车辆调度优化
