论文部分内容阅读
车辆路径问题(Vehicle Routing Problem,VRP)作为物流运输研究的一个重要问题,在现实中具有广泛的应用基础。人类需求的日益多样化和现实世界存在的大量不确定因素,都加大了车辆调度管理的难度。尽管不确定因素下的VRP问题已有了一系列研究成果,但缺乏探讨车辆配送中的动态管理策略和处理异常信息的快速反应机制。本文重点研究了不确定因素下VRP的建模和优化方法,主要研究内容和创新性工作如下:针对标准的带时间窗VRP的多目标数学模型,研究了三种基于混合搜索策略的启发式算法。离散差分进化混合算法采用线性加权的方法来处理多目标模型,并发展了新的变异和交叉算子,对精英个体运用局部禁忌搜索以提高算法的寻优能力。提出了一种构造多样性初始解的随机车辆配载方法,以及插入可行邻域和2-Opt可行邻域两种搜索可行解的邻域结构。文化基因算法和多目标文化基因算法分别采用线性加权法和Pareto方法来处理多目标模型,种群搜索采用遗传算法,局部搜索采用禁忌搜索。仿真对比实验验证了三种算法的有效性。针对具有模糊需求量的VRP,提出了一种动态管理方法。采取一种事前预测的策略,在初始计划执行中实时进行动态调整。设计了一种嵌入模糊模拟的NSGA-Ⅱ混合算法,分析了决策者主观偏好值对决策目标的影响,然后与传统车辆调度方法进行了对比分析,验证了本文提出的动态管理策略的有效性。针对具有模糊预约时间的VRP,应用模糊事件给出了车队服务满意度的一个新的度量方法和求最大满意度的计算方法。进而提出了一种基于Pareto优化的多目标禁忌搜索算法,通过与NSGA-Ⅱ算法进行仿真对比实验,证明了多目标禁忌搜索算法是求解多目标组合优化问题的一种有效的方法。考虑顾客的主观偏好影响,研究了模糊时间窗VRP的集成优化方法。在多目标禁忌搜索算法中嵌入优化顾客满意度的动态规划方法,来求解以物流配送成本和顾客平均满意度为目标的模型。对模糊时间窗为线性分段函数形式和非线性凹函数形式的隶属度函数,分别提出了有限枚举算法和次梯度二分迭代算法来优化顾客的最优开始服务时间。进一步,研究了带随机时间和模糊时间窗的VRP。为了处理随机因素,提出了预先安排车辆行驶计划,然后在车辆行驶过程中根据时间调度规则随时调整开始服务时间的策略,动态优化顾客的满意度水平。对带时间窗的动态VRP进行了研究,提出了一种新的紧急顾客插入和分批驱动调度策略,该策略只需实时插入紧急顾客。与新顾客插入后的重复优化策略和批处理策略进行了对比,并分析了分批优化间隔长度对调度性能的影响。