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

车辆路径问题(VRP)是物流管理研究中的一项重要内容。如何有效地调度车辆,合理地安排行车路径和出行时间,以最低成本将货物准时送达客户,实现物流配送系统高效低成本的运作,是多年来困扰学术界和产业界的难题。目前车辆路径问题的求解多集中在算法的研究上,这种研究方法通常将VRP问题看作是一个理论性很强的静态问题,事实上,实际的物流配送系统往往具有相当的随机性和复杂性,因此单纯依靠算法的研究已经很难满足VRP问题的复杂性需求。 鉴于此,本文在现有车辆路径问题研究的基础上,从仿真优化的角度对车辆路径问题进行了研究,主要研究内容和成果如下： (1)构建了车辆路径问题的仿真优化模型。针对车辆路径问题的复杂性,利用离散事件仿真方法对物流配送过程进行建模,并采用面向对象的技术实现。为了求解VRP问题,将仿真技术与优化算法(本文选择遗传算法作为优化算法)有机融合,建立了仿真优化模型,并此模型上增加了智能决策模块,解决VRP随机问题、处理约束条件、辅助优化算法寻优。 (2)优化算法的改进研究。鉴于仿真计算代价过高会影响优化速度,对传统的遗传算法进行了改进,提出了新的自适应遗传算法,即算法的运行参数——交叉率和变异率不是固定的数值,而是能够根据适应度值在进化的不同阶段进行自适应调节。此外,针对VRP问题本身的特点,改进了变异方法,并在标准遗传算法流程的基础上,增加了局部优化的过程。实验结果表明,对遗传算法所做的这些改进明显提高了VRP问题的求解质量和求解速度。 (3)研究了硬时间窗车辆路径问题(VRPHTW)的仿真优化解决方法。鉴于客户对车辆到达时间的严格限制,设计了仿真优化框架中的智能决策模块,即运用人工智能的方法解决传统的VRPHTW问题。为更贴近实际配送的需要,对传统的VRPHTW问题进行了扩展,提出了配送过程无等待硬时间窗VRP问题的定义并设计了解决方案。在求解两类硬时间窗VRP问题时,遗传算法会产生大量不符合客户时间窗要求的基因个体,影响优化效率,针对这个问题,本文从仿真策略和优化方法两个方面进行了改进。通过对Solomon基准测试集的实例进行实验计算,验证了改进方法的有效性和可行性。 (4)研究了动态车辆路径问题。利用仿真优化在处理动态复杂系统方面的优势,提出了一系列解决动态车辆路径问题的策略准则和方法,建立了动态仿真优化模型,并利用仿真实例验证了方法的有效性。 (5)设计并实现了车辆路径问题仿真优化软件系统。采用面向对象的语言VC++6.0实现了本文提出的标准车辆路径问题及其扩展问题的基本思想。此研究成果不但对车辆路径问题的实际应用具有指导意义,而且可以为物流配送调度系统提供决策支持。