车辆路径问题的仿真模型及优化方法研究

论文摘要

车辆路径问题是物流管理领域关注的热点和难点问题之一。如何合理地安排车辆、行车路径和出行时间，以最低成本将货物准时送达客户，实现物流配送系统高效低成本地运作，这是多年来困扰学术界和产业界的难题。本文从仿真的角度来探讨车辆路径问题的求解，利用物流系统仿真平台eM-Plant，建立求解车辆路径问题的仿真模型；针对仿真模型求解效率不高及在传统仿真优化方法中仿真与优化相互独立的缺陷，将仿真与优化两个关键环节有机结合和融和，改进仿真优化方法，提出了基于启发式变换的仿真优化的原理及求解方法；最后实现了车辆路径问题的仿真优化软件系统并通过算例对上述方法进行了验证。本文的具体研究工作如下：（1）车辆路径问题仿真模型的构建。对车辆路径问题的难点进行分析，建立具有多个随机约束条件的车辆路径问题的数学模型。针对其难以求解的困难，提出了面向对象的车辆路径问题仿真模型的总体结构，并基于物流系统仿真平台eM-Plant构建了车辆路径问题的仿真模型。（2）基于启发式变换的车辆路径问题的仿真优化方法研究。提出了物流配送系统中车辆路径问题仿真优化体系结构；将仿真与优化环节有机融合，提出基于启发式变换的仿真优化的原理，利用矩阵分析和变换实现了仿真优化过程的启发式变换，利用启发式运行规则对仿真运行的参数进行分析，通过矩阵变换改进优化搜索策略并求出车辆路径问题的最优解或满意解。（3）车辆路径问题的仿真优化软件系统研究与算例验证。设计并实现了车辆路径问题仿真优化软件系统；并通过算例验证了基于eM-Plant的车辆路径问题的仿真模型和基于启发式变换的仿真优化方法的有效性。实验结果表明，基于矩阵变换的仿真优化方法具有良好的稳定性和求解效率较高的优势。本项研究是仿真技术、运筹学及组合优化等学科理论和方法的交叉与渗透，为求解车辆路径问题这一NP-hard问题进行了有益的探索。其研究成果可以为物流配送系统提供决策支持，对于物流企业降低物流成本具有重要的现实意义；对于求解电子商务环境下物流配送这类多目标动态规划问题也具有重要的理论价值。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 问题的提出与研究意义
• 1.1.1 问题的提出
• 1.1.2 研究意义
• 1.2 国内外相关研究综述
• 1.2.1 车辆路径问题模型与算法研究进展
• 1.2.2 物流系统仿真及优化研究进展
• 1.2.3 国内外相关研究小结
• 1.3 本文的主要研究内容与研究思路
• 1.3.1 本文的主要研究内容
• 1.3.2 本文的研究思路
• 2 车辆路径问题仿真模型的构建
• 2.1 有时间窗的车辆路径问题的分析与数学模型
• 2.1.1 有时间窗的车辆路径问题求解难点分析
• 2.1.2 有时间窗的车辆路径问题的界定及符号说明
• 2.1.3 有时间窗的车辆路径问题的数学模型
• 2.2 有时间窗的车辆路径问题的仿真建模分析
• 2.2.1 面向对象的仿真建模分析
• 2.2.2 有时间窗的车辆路径问题的仿真目标
• 2.3 基于eM-Plant的仿真模型的构建
• 2.3.1 仿真工具的选择
• 2.3.2 仿真模型的结构
• 2.3.3 仿真模型的逻辑流程
• 2.4 本章小结
• 3 基于启发式变换的车辆路径问题仿真优化方法研究
• 3.1 车辆路径问题仿真优化体系结构
• 3.2 基于启发式变换的仿真优化的原理及结构
• 3.2.1 基于启发式变换的仿真优化的原理
• 3.2.2 基于启发式变换的仿真优化的结构
• 3.3 基于启发式变换的仿真优化求解方法
• 3.3.1 物流配送方案的邻接矩阵表示
• 3.3.2 基于邻接矩阵的车辆路径问题的数学模型
• 3.3.3 基于概率转移矩阵的VRPTW初始化方案的生成方法
• 3.3.4 基于启发式变换的策略改进方法
• 3.4 本章小结
• 4 车辆路径问题的仿真优化软件系统与算例验证
• 4.1 车辆路径问题仿真优化软件系统的分析
• 4.2 车辆路径问题仿真优化软件系统的设计
• 4.2.1 系统功能与结构
• 4.2.2 系统流程
• 4.3 车辆路径问题仿真优化软件系统的实现
• 4.3.1 系统开发工具选择
• 4.3.2 仿真模型子系统的实现
• 4.3.3 仿真优化子系统的实现
• 4.4 算例验证
• 4.4.1 仿真模型的验证与分析
• 4.4.2 仿真优化方法的验证
• 4.5 本章小结
• 5 结论与展望
• 5.1 论文的主要创新性成果
• 5.2 展望
• 参考文献
• 附录A 重要程序源代码
• 攻读博士学位期间发表学术论文情况
• 致谢