车辆路径问题的建模及优化算法研究

论文摘要

智能交通系统作为基于现代科学技术建立起来的，一种在大范围内全方位发挥作用的，准时、准确、高效的交通运输管理体系，受到各国的普遍重视。全球经济的一体化，也正推动着被称为是企业“第三利润源”——现代物流业的快速发展。车辆路径问题作为智能交通系统中的重要内容，在现代物流中占据着很重要位置。虽然经过几十年研究，取得了不少的成果，但由于该问题的复杂性，目前还存在许多需要进一步加强研究的问题。随着计算技术和优化方法以及信息和通信技术的发展，过去解决不够完善的或没能解决的问题，可以借助现代科技的力量，将其进一步完善或解决。本文针对目前车辆路径问题的现状，利用系统工程理论和最新的优化方法，对存在的问题进行建模和优化算法研究，具有重要的理论意义和实用价值。论文主要做了以下几方面工作：1、针对带时间窗有限车辆路径问题，设计了一种混合遗传禁忌算法。在描述问题和建立模型的基础上，首先，因染色体中仅有部分基因起作用，为充分利用染色体包含的信息，提出采用Bellman-Ford最短路算法，找到它最佳的分割方法。其次，利用禁忌搜索法改善因遗传算法变异概率小，带来局部搜索能力低的问题。另外，对禁忌搜索法又进行设计，通过在目标函数中添加惩罚项，使搜索在可行和不可行交界区域间动态调整，既使搜索不偏离最优解太远，又丰富了搜索区域，提高获得更优解的概率。最后，将解与已知的最优解进行对比，并分析参数对解的影响。2、针对大规模单车型带软时间窗车辆路径问题，设计了一种基于大系统分解协调技术新的解决方法。在对问题进行了描述并给出它的模型后，首先，运用动态聚类法，基于每辆车的位置坐标对车辆聚类，得到分类车辆的中心坐标；再根据每个任务到分类车辆中心的距离，对任务进行分类。其次，针对采用传统分解协调法解决该问题，收敛性能比较差的问题，设计了有效的协调参数，并在主／子系统中，分别设计了不同的自适应遗传算法。通过仿真试验，证实了该算法的有效性。针对大规模多车型带软时间窗车辆路径问题，设计了一个有效的禁忌搜索算法。在给出了问题描述并建立了它的模型后，首先，提出采用候选表策略，通过它舍弃大部分没有希望的移动，且随着搜索过程的进展，动态地调整与搜索邻域有关候选表的大小，提供了一个简单的实施集中性搜索和分散性搜索的方法。其次，采用动态摆动策略，控制它集中在可行和不可行空间交界区域搜索。仿真试验结果证实了所设计禁忌搜索算法的有效性。3、对多库房带时间窗车辆路径问题，在分析几个经典的多库房位置模型后，对该问题进行了描述并构建了它的模型。针对目前解决多库房车辆路径问题，效率低且易陷于局部最优解的问题，提出一种采用分解协调技术解决该问题的新方法。首先，根据启发式方法，将用户分解为耦合和非耦合用户。其次，利用遗传算法设计了协调参数，并设计了禁忌搜索算法，有效地解决各库房的车辆路径问题。最后，通过仿真试验，对它的有效性进行了验证。对多库房随机需求车辆路径问题，在描述该问题以及分析了有关模型的基础上，建立了它的数学模型。基于分解协调技术，在协调层，利用自适应遗传算法确定耦合用户的最佳分解方式；在执行层，对解决子系统的随机需求车辆路径问题，基于预防性补救措施，设计了自适应交叉熵法。最后，通过对不同算法仿真结果比较，验证了所设计方法的有效性。4、在分析了几种解决随机需求车辆路径问题典型方法后，提出了一种基于交叉熵，结合重要抽样、Monte-Carlo及Markov状态转移技术，解决更复杂的随机用户和需求车辆路径问题新方法。在对该问题进行了描述，并建立模型后，首先，针对路径期望费用函数的复杂性，设计了基于Monte-Carlo抽样求解的有效方法。其次，为提高标准交叉熵法性能，根据迭代过程中分位值改变大小，对用于更新转移矩阵关键的路径，设计了自适应调整方法。最后，利用仿真试验，验证了所设计交叉熵法的鲁棒性和有效性。5、在分析了随机最短路问题的基础上，对动态随机需求车辆路径问题进行了描述，并建立它的最优策略模型。针对状态空间“维数灾”问题，基于增强学习函数近似原理，利用径向基函数网络逼近最优cost-to-go函数。首先，对径向基函数进行分析和设计，其次，在一给定的控制策略下，将最小平方瞬时差分法确定近似函数权系数与交叉熵法确定隐层节点基函数参数相结合，通过在线调整，使Bellman残差平方和性能指标达到最小，以实现对最优cost-to-go函数的逼近。通过仿真试验，证实了此算法的有效性。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 选题背景及意义
• 1.2 车辆路径问题描述及分类
• 1.2.1 车辆路径问题描述
• 1.2.2 车辆路径问题分类
• 1.3 车辆路径问题研究概况
• 1.3.1 国内车辆路径问题研究概况
• 1.3.2 国外车辆路径问题研究概况
• 1.4 研究中存在的问题
• 1.5 论文的主要工作及章节安排
• 1.5.1 主要工作
• 1.5.2 章节安排
• 第二章 基础知识
• 2.1 经典启发式方法
• 2.1.1 Solomon的插入法
• 2.1.2 多库房用户的分配方法
• 2.1.3 循环法
• 2.2 大系统分解与协调法
• 2.3 遗传算法
• 2.3.1 遗传算法的基本原理
• 2.3.2 遗传算法的内容
• 2.3.3 遗传算法的特点
• 2.4 禁忌搜索法
• 2.4.1 禁忌搜索法原理
• 2.4.2 几种基本邻域结构生成方法
• 2.5 交叉熵法
• 2.5.1 交叉熵法原理
• 2.5.2 交叉熵法实施步骤
• 2.6 增强学习
• 2.6.1 增强学习原理
• 2.6.2 瞬时差分算法
• 2.7 小结
• 第三章 带时间窗有限车辆路径问题
• 3.1 引言
• 3.2 问题的描述
• 3.3 数学模型的建立
• 3.4 混合遗传禁忌搜索算法的设计
• 3.4.1 遗传算法的设计
• 3.4.2 用Bellman-Ford算法确定染色体最佳分割
• 3.4.3 禁忌搜索算法的设计
• 3.5 仿真试验与结果分析
• 3.6 小结
• 第四章 大规模车辆路径问题
• 4.1 前言
• 4.2 单车型带软时间窗车辆路径问题
• 4.2.1 问题的描述
• 4.2.2 数学模型的建立
• 4.2.3 应用动态聚类法分解任务
• 4.2.4 分解协调技术及遗传算法设计
• 4.2.5 仿真试验及结果分析
• 4.3 多车型带软时间窗车辆路径问题
• 4.3.1 问题的描述
• 4.3.2 数学模型的建立
• 4.3.3 禁忌搜索法的设计
• 4.3.4 仿真试验及结果分析
• 4.4 多库房带时间窗车辆路径问题
• 4.4.1 模型的分析
• 4.4.2 问题的描述
• 4.4.3 模型的建立
• 4.4.4 分解协调技术及禁忌搜索算法的设计
• 4.4.5 仿真试验及结果分析
• 4.5 小结
• 第五章 静态随机车辆路径问题
• 5.1 引言
• 5.2 随机需求车辆路径问题
• 5.2.1 问题的描述
• 5.2.2 问题的求解方法
• 5.3 随机用户和需求车辆路径问题
• 5.3.1 问题的描述
• 5.3.2 模型的建立
• 5.3.3 路径期望费用的求解
• 5.3.4 交叉熵法的设计
• 5.3.5 仿真试验及结果分析
• 5.4 多库房随机需求车辆路径问题
• 5.4.1 问题的描述
• 5.4.2 模型的分析及建立
• 5.4.3 分解协调技术及自适应交叉熵法的设计
• 5.4.4 仿真试验与结果分析
• 5.5 小结
• 第六章 动态随机需求车辆路径问题
• 6.1 引言
• 6.2 问题的描述
• 6.3 模型的分析与建立
• 6.4 动态随机需求车辆路径问题的求解
• 6.4.1 径向基函数网络设计
• 6.4.2 基于最小平方瞬时差分法设计权系数
• 6.4.3 基于交叉熵法设计基函数参数
• 6.5 仿真试验与结果分析
• 6.6 小结
• 第七章 回顾与展望
• 7.1 论文工作回顾
• 7.2 工作展望
• 致谢
• 参考文献
• 攻读博士学位期间发表的论文及科研工作情况