微粒群算法及其在物流系统中的应用研究

论文摘要

物流被称为企业的“第三利润源泉”。在“自然资源领域”和“人力资源领域”利润开拓越来越困难的情况下,物流领域的潜力被人们发现并受到重视。通过优化物流系统可以降低成本,从而增加企业利润及市场竞争力,因此通过优化算法对物流系统进行优化具有十分重要的意义和应用价值。微粒群算法（Particle Swarm Optimization,PSO）是一种拥有收敛速度快和简便易行优点的随机全局优化算法。论文对标准微粒群算法进行了深入的研究和分析,针对其缺陷提出了相应的改进方法,在此基础上采用遗传算法编码、交叉和变异的遗传微粒群算法求解物流系统中的库存优化和车辆路径优化问题,并分别设计了启发式算子提高遗传微粒群算法的性能,仿真试验的结果证实了算法的有效性和稳定性。对于微粒群算法改进的工作在于:（1）对于无约束优化问题,提出基于对个体评价的动态个体惯性权重调整策略,其中也包含对多种变异算子的研究。仿真结果显示,这种方法对于提高微粒群算法的性能有非常明显的帮助。（2）对于约束优化问题,通过仿真计算比较了多种变异算子的效果,在此基础上尝试了多变异算子串行融合,然后为了克服多变异算子相互间的干扰并减少计算量,提出了自适应的变异算子选取策略。最后,本文提出了将标准微粒群算法与遗传微粒群算法相融合的双重微粒群算法,仿真计算显示,这种算法在与两种微粒群算法计算量相当的情况下展现出明显高效的搜索效率和精度。对于物流系统优化的贡献在于:（1）采用遗传微粒群算法求解背包问题,采用1-2opt启发式算子融入遗传微粒群算法,仿真结果显示本算法要优于本文提到的标准微粒群算法和遗传算法。在此基础上,对一个典型货运中转业务建模,通过综合运用双重微粒群算法和求解背包问题的遗传微粒群算法求解,仿真结果验证了算法的有效性,并对于物流业务的实际运行有一定的参考价值。（2）提出采用混合遗传微粒群算法求解旅行商问题的框架结构。针对微粒群算法特有的三条染色体交叉的特性,设计改进的顺序交叉算子,它能够在交叉的同时保留优质解的信息;此外采用基于2-opt的变异算子显著的增强算法的收敛性能。通过以上改造,提出了求解旅行商问题的遗传微粒群算法结构,此结构相对于标准微粒群算法更加简单、直观、易于实现并且可扩展性好。仿真实验显示了此算法的可行性和有效性。（3）采用混合遗传微粒群算法对带车辆能力约束的车辆路径优化问题求解,其中采用了求解旅行商问题的交叉和变异算子,并采用了启发式算子处理其约束条件,仿真结果表示它具有精度高和速度快的优点。（4）采用两段式混合微粒群算法对于由多个仓库同时配送的多车场路径问题进行求解。第一阶段中采用分配规则将客户节点分配到各个仓库,将问题简化为多个单仓库的车辆路径优化子问题;第二阶段采用混合遗传微粒群算法对每个子问题进行求解,仿真结果验证算法的可行性。仿真结果显示算法不仅能在满足配送要求下优化配送线路减少行驶里程,还可以对公司货车的购置调度和仓库选址等提供决策支持。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 论文结构及主要工作
• 2 微粒群算法概述
• 2.1 优化算法
• 2.2 进化算法
• 2.3 微粒群算法
• 2.4 动态个体惯性权重调整微粒群算法
• 2.5 本章小结
• 3 约束优化问题的微粒群算法求解
• 3.1 引言
• 3.2 微粒群算法求解约束优化问题相关研究成果
• 3.3 微粒群算法变异算子的选择
• 3.4 双重微粒群算法（DUAL-PARTICLE SWARM OPTIMIZATION, DUAL-PSO）
• 3.5 本章小节
• 4 求解背包问题的混合遗传微粒群算法
• 4.1 引言
• 4.2 问题描述与数学模型
• 4.3 微粒群算法求解KP 问题相关研究成果
• 4.4 求解KP 问题的混合遗传微粒群算法
• 4.5 基于混合微粒群算法的货物中转模型优化
• 4.6 本章小结
• 5 车辆调度问题的混合遗传微粒群算法求解
• 5.1 求解TSP 问题的混合遗传微粒群算法（HGPSO-TSP）
• 5.2 求解CVRP 问题的混合遗传微粒群算法（HGPSO-CVRP）
• 5.3 HGPSO-CVRP 应用实例
• 5.4 本章小结
• 6 总结与展望
• 6.1 本文的主要工作及研究结论
• 6.2 展望
• 致谢
• 参考文献
• 附录1 攻读博士学位期间发表论文目录
• 附录2 本文所采用的基准约束优化问题
• 附录3 本文采用的背包问题实例
• 附录4 广州某食品有限公司卖场之间里程