时变网络环境下车辆调度问题研究

论文摘要

我国十一五规划中将现代物流业作为今后重点发展领域,提出到2010年全社会物流成本下降2-3个百分点。运输配送是影响物流总成本的重要因素,大约占物流成本的60%。作为物流系统优化中关键的一环,物流配送车辆的优化调度问题成为研究的热点。在以往的静态车辆调度问题（vehicle routing problem,简写VRP）研究中,车辆路径安排大部分都是基于确定性的信息,其中包括需求确定、车辆位置确定和车辆在路途的行驶时间确定,尤其考虑车辆在任意两节点（顾客或车场）间的运行成本（时间）只取决于节点间的距离,通常被认为是已知且静态的常量。但在实际的车辆行驶过程中,由于交通管理、交通流量、交通事故、天气变化、上下班高峰期等因素的影响,车辆的行驶速度总是处在不断变化之中,从而导致了路网中各个路段上的运行成本（时间）也相应地发生变化。这种动态变化的情况,静态VRP问题的理论和方法已无法适用,这就使得对时变网络VRP问题的研究成为迫切需要。本论文主要以时变网络VRP的三类子问题作为研究对象,分别是基于时段的时间依赖型旅行商问题（time dependenttraveling salesman problem,简写TDTSP）、基于具体位置的TDTSP问题和时间依赖型车辆调度问题（time dependent vehicle routing problem,简写TDVRP）。主要研究内容如下:第1章首先介绍了论文所要研究问题的来源及研究目的,进而分析了时变网络VRP问题的背景和研究意义,并描述了本文即将讨论的三类子问题的研究特点,最后指出了本文的技术路线和主要研究工作。第2章在对大量相关文献进行总结提炼的基础上,综述时变网络VRP问题的研究现状。描述了目前对时变网络问题的研究情况,并对已研究的时变网络VRP问题进行分类,总结了时变网络特性处理方法的研究现状。在求解算法方面,对静态VRP问题和时变网络VRP问题的求解算法进行综述,并引入本文将用于求解时变网络VRP问题的大规模邻域（very large scale neighborhood,简写VLSN）搜索技术,最后指出现有文献中存在的问题及进一步需要研究的方向。第3章以基于时段的TDTSP问题作为研究对象,描述该问题的特征与性质,提出一种满足先入先出（first in first out,简写FIFO）准则的时变网络特征处理方法,建立问题的数学模型,并给出传统的动态规划启发式算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。第4章以基于位置的TDTSP问题作为研究对象,描述该问题的特征与性质,建立问题的数学模型。在求解算法上,同样采用一种基于VLSN搜索技术的动态搜索算法求解该问题。通过实验比较不同算法的性能,并对算法性能进行分析。第5章以TDVRP问题作为研究对象,描述该问题的特征与性质,提出一种满足FIFO准则的时变网络特性处理方法,建立问题的数学模型,并给出传统的最近邻算法求解策略。在求解算法上,采用一种基于VLSN搜索技术的动态规划启发式算法和环状交换算法分别求解该问题,共有五类策略。通过实验比较不同算法的性能,并对算法性能进行分析。第6章以成都某物流企业的配送作为背景,收集实际数据,建立该企业配送的数学模型。通过实际数据分析,对配送环境进行合理假设,得出不同情形下的最优配送路线,该路线同样也是本论文中所提算法的计算结果。该实际案例为本文所提算法的有效性提供了一个很好的实际验证背景,为企业配送作出满意决策。结论部分对论文内容进行了全面的总结,指出了进一步研究的方向。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 问题的研究目的及意义
• 1.1.1 问题的来源及研究目的
• 1.1.2 问题研究意义及问题描述
• 1.2 本文问题的研究特点
• 1.3 本文的技术研究路线及主要工作
• 1.3.1 研究的技术路线
• 1.3.2 本文的主要工作
• 第2章 时变网络VRP问题国内外研究综述
• 2.1 时变网络VRP问题的研究现状
• 2.2 时变网络特性处理方法研究现状
• 2.3 VRP问题算法国内外研究现状
• 2.3.1 静态网络VRP问题算法研究现状
• 2.3.2 时变网络VRP问题算法研究现状
• 2.4 大规模邻域搜索技术
• 2.4.1 局域搜索算法
• 2.4.2 传统邻域结构
• 2.4.3 大规模邻域结构
• 2.5 小结
• 第3章 基于时段的时间依赖型旅行商问题研究
• 3.1 引言
• 3.2 基于时段的TDTSP问题模型
• 3.2.1 处理跨越单时段问题
• 3.2.2 处理跨越多时段问题
• 3.2.3 TDTSP问题数学模型
• 3.3 动态规划启发式算法
• 3.3.1 动态规划精确算法
• 3.3.2 动态规划启发式算法
• 3.4 动态搜索算法
• 3.4.1 求解TSP问题的传统改进策略
• 3.4.2 动态搜索策略
• 3.5 实验及算法性能比较
• 3.6 小结
• 第4章 基于具体位置的TDTSP问题研究
• 4.1 引言
• 4.2 基于具体位置的TDTSP问题模型
• 4.3 动态搜索算法
• 4.4 实验及算法性能比较
• 4.5 小结
• 第5章 时间依赖型车辆调度问题研究
• 5.1 引言
• 5.2 TDVRP问题模型
• 5.2.1 处理跨越单时段问题
• 5.2.2 处理跨越多时段问题
• 5.2.3 TDVRP问题数学模型
• 5.3 传统求解策略—最近邻算法
• 5.4 动态规划启发式算法
• 5.5 环状交换算法
• 5.5.1 环状交换的基本理论
• 5.5.2 环状交换动态规划算法
• 5.6 改进环状交换动态规划算法
• 5.6.1 在路线里加入虚拟的顾客
• 5.6.2 底层嵌入insert
• 5.7 实验及算法性能比较
• 5.8 小结
• 第6章 案例分析
• 6.1 公司介绍
• 6.2 公司同城派送业务介绍
• 6.3 数学模型建立
• 6.4 数据收集及分析
• 6.5 小结
• 结论
• 1.本论文主要工作
• 2.本论文的创新之处
• 3.有待进一步研究的问题
• 致谢
• 参考文献
• 攻读博士学位期间发表的论文及科研情况