根据提供的文件内容,本篇论文围绕的是时变网络环境下车辆调度问题研究,尤其是针对旅行商问题(TSP)和车辆路径问题(VRP)在时变条件下的新解法。下面将详细阐述文档中提到的各个知识点。
1. 时变网络环境下车辆调度问题的提出背景
论文的背景是现代物流业的发展需求,十一五规划提出降低全社会物流成本的目标,强调运输配送对物流成本的重要性,物流配送车辆的优化调度问题成了研究的热点。在静态VRP问题中,路径安排基于确定性信息,如需求、车辆位置、行驶时间等,但实际中这些因素会受多种因素影响而变化,如交通管理、流量、事故、天气变化等,导致车辆行驶速度和运行成本(时间)不断变化。这就需要对时变网络下的VRP问题进行研究。
2. 研究的三类子问题
论文主要研究的三类子问题包括:
- 基于时段的时间依赖型旅行商问题(TDTSP)
- 基于具体位置的TDTSP问题
- 时间依赖型车辆调度问题(TDVRP)
3. 研究内容和技术路线
论文首先分析了研究问题的来源、目的和意义,并对三类子问题的研究特点进行描述,指出了技术路线和主要研究工作。第2章综述了时变网络VRP问题的研究现状,包括对时变网络问题的研究情况、分类、处理方法研究现状、静态和时变网络VRP问题的求解算法,以及引入的用于求解时变网络VRP问题的大规模邻域搜索技术。
4. 研究创新点
- 提出一种满足FIFO准则的时变网络特性处理方法,用于计算车辆在跨时段行驶时间的计算公式,并不包含路段距离和车辆行驶速度,使得操作性加强。
- 构造基于大规模邻域搜索技术的动态搜索算法ds^opt(Q2,2.5,3),采用动态规划搜索多个独立的bopt移动,能在多项式时间内搜索到指数大小的邻域,算法性能优于现有的动态规划启发式算法。
- 针对TDVRP问题,构造了基于VLSN搜索技术的动态规划启发式算法和环状交换动态规划算法。动态规划启发式算法通过设置参数平衡解质量和算法运行时间,环状交换动态规划算法采用多车交换策略,打破传统优化单条路径的局限。
5. 时变网络特性处理方法
在时变网络环境下,车辆行驶速度的变化导致路网中各个路段上的运行成本(时间)也相应变化。静态VRP问题的理论和方法不能适用,因此需要研究时变网络VRP问题,寻求新的解法来处理这些变化。
6. 动态规划启发式算法
该算法通过设置参数平衡解的质量和算法的运行时间,扩大最近邻算法的邻域空间,缩短动态规划精确算法的运行时间。
7. 环状交换动态规划算法
该算法允许顾客在多辆车之间进行交换,打破传统只能对某辆车路线进行优化的思想,从而扩大搜索空间。为了保证原有路线的最佳性和环状交换的可行性,构造了带有虚拟顾客的改进环状交换策略以及底层嵌入insert的改进策略,能在保证解质量的前提下缩短算法运行时间。
本篇论文针对现代物流配送中的车辆调度优化问题,在时变网络环境下进行了深入研究,创新性地提出了多种算法和技术,旨在提高物流运输配送效率,降低成本。论文的研究成果对于物流行业在车辆调度优化方面具有重要的理论和实际应用价值。