论文部分内容阅读
车辆路径问题(Vehicle Routing Problem, VRP)是近二十年来运筹学、图论、网络分析、应用数学、计算机应用及交通运输等学科研究的一个热点问题,它已被证实是组合优化中带约束条件的NP-Hard完全问题,难以用常规方法求解,国内外学者尝试使用智能优化算法的研究,如遗传算法、蚁群算法、禁忌搜索最优化等。本文就是在国内外研究现状的基础上,建立了VRP问题的多目标优化模型,用基于分区域搜索的多目标进化算法求解VRP问题,实现了基于分区域多目标进化算法在VRP问题中的应用和软件仿真,验证了模型的有效性和算法的可行性。本文主要的研究工作和创新如下：(1)带时间窗的多配送中心协同车辆路径问题的研究。在现有文献仅以车辆配送总费用最小化为目标的基础上,兼顾顾客的满意度目标,首次建立了带有时间窗的多物流中心协同配送的车辆路径多目标优化问题的数学模型。对建立的多目标优化问题,采用基于分区域搜索的多目标进化算法思想,构造了利于产生可行解的编码方式,从而提高算法的运行效率。并且通过算例验证了建立的模型能有效地解决协同物流配送车辆路径问题。通过多目标进化算法返回一个非支配解的集合而非单一的一个非支配解,为决策者提供了更有力的决策支持。(2)基于沿途接驳补货策略的车辆路径问题的研究。针对大区域多需求点的物流配送系统,在原有文献仅以车辆配送总费用为目标的基础上,兼顾顾客的满意度目标,建立了带有时间窗车辆路径问题的多目标最优化模型,该模型基于大小车沿途在虚拟场站接驳补货策略,节省了货车往返配送中心补货次数、距离与时间。根据该模型需要部分顾客作补货点的特点,首先利用k均值聚类的方法将顾客分类,然后采用基于分区域和极大极小策略的多目标进化算法思想进行求解,最后以测试题库The VRP Web中的算例进行测试分析。经由测试结果比较,相较于非接驳补货的传统VRPTW,该模型效益明显。