随机时变网络环境下的物流配送路径优化问题研究

车辆路径问题（Vehicle Routing Problem, VRP）是物流配送的核心问题，国内外学者已经展开了大量研究工作。以往的研究大多假设路网的行程时间是常数或按某一确定型函数变化。但对于实际路网，由于受到交通流量、突发事故、天气等因素的影响，行程时间往往经常发生变化，具有一定的随机性。本课题研究随机时变路网环境下，如何安排车辆的配送线路和时刻表，在保证一定配送服务水平的基础上，使得综合配送成本达到最优。主要内容包括：以海量的实际交通数据为基础，研究随机时变路网的行程时间分布特性和预测方法；建立基于可靠度的车辆路径问题的数学模型；面向大规模实际路网，研究车辆配送路径的优化算法；以及针对突发交通事件的配送路径动态调整策略和方法。本研究考虑了路网交通状况的时变特征和随机性，更加符合物流配送的实际情况，对于降低配送成本，提高配送服务水平和客户满意度具有重意义。

本课题围绕随机时变路网环境下的配送车辆路径问题展开研究，主要完成了5部分工作：随机时变网络的行程时间特征、随机时变网络建模、随机时变网络的最优路径问题、随机时变网络的车辆路径问题以及模型和算法的软件实现。首先，基于线圈数据、浮动车数据和车牌照数据等实际交通数据，分析了网络交通状态的可预测性；从概率分布、统计指标、时间序列特征等角度分析了路径行程时间的可靠性；针对行程时间波动率的尖峰厚尾特征，通过ARCH模型分析了路径行程时间的波动性。接着，以行程车速的时间依赖函数为基础对随机时变路网进行建模，并通过实际浮动车数据，对路网进行标定。接下来，针对传统基于行程时间随机分布建模方法的计算时间复杂度高，只能求解小规模网络的不足，基于鲁棒优化方法，分别采用3种鲁棒优化准则，对随机时变路网的最优路径问题进行建模；证明了在路网满足“先入先出”特性的条件下，可以将原问题转换为确定型时变路网的行程时间最短路径问题；设计了改进Dijkstra算法；通过测试算例和实际算例证明了算法具有较高的效率。然后，对于确定型时变路网的车辆路径问题，提出了一种出发时刻优化的路径构造算法；将鲁棒优化方法引入随机时变路网的车辆路径问题的建模，并将其转换为确定型时变路网的车辆路径问题；设计了路径构造算法和蚁群算法；通过测试算例和实际算例证明了算法的有效性，即使对于1000个客户节点的大规模问题，算法仍具有较高的计算效率。最后，从计算效率角度出发，进行了上述模型和算法的计算机程序设计，并采用组件化方式开发了软件。