有时间窗的车辆路径问题仿真优化方法研究

摘要

本文针对有时间窗的车辆路径问题的求解模型复杂度大，求解算法效率不高的问题，提出了基于启发式变换的仿真优化方法求解该问题的新思路。阐述了基于启发式变换的仿真优化方法的原理，给出了利用矩阵分析和变换实现启发式变换的方法。通过深入分析有时间窗的车辆路径问题及其特点，引入矩阵变换的理论和方法，建立了有时间窗的车辆路径问题的矩阵模型；并以此为基础，构造了有时间窗的车辆路径问题的概率转移矩阵，并利用概率转移矩阵来生成问题的初始化方案；通过矩阵分析、矩阵变换，改进优化搜索策略，最终找到最优解或满意解。本文所做的主要研究工作包括： (1)通过对仿真优化方法中仿真与优化算法之间的关系进行研究，从系统的角度考虑优化算法与仿真模型的关系，给出了基于启发式变换的仿真优化方法的原理，提出了基于启发式变换的仿真优化方法。 (2)在对有时间窗的车辆路径问题特点分析的基础上，用邻接矩阵表示物流配送方案，通过矩阵变换的理论和方法，建立了有时间窗的车辆路径问题的矩阵模型。 (3)以有时间窗的车辆路径问题的矩阵模型为基础，对客户点的时间窗和距离矩阵进行分析，构造了有时间窗的车辆路径问题的概率转移矩阵，并利用基于概率转移矩阵的初始化方案生成方法，产生有时间窗的车辆路径问题的初始化方案。 (4)通过对成本矩阵和概率转移矩阵的分析，构建启发式规则，对初始化决策矩阵进行矩阵变换，改进优化搜索策略，最终找到最优解或满意解。 (5)通过系统分析、系统设计的方法建立系统，实现基于启发式变换的仿真优化算法。用随机生成的VRP和国际上标准测试用例Benchmarkproblems对该算法的稳定性和有效性进行测试，结果表明该算法具有良好的稳定性，算法的求解结果在配送总成本方面优于已知的最优结果，证明了算法的有效性。 本文利用基于启发式变换的仿真优化方法求解有时间窗的车辆路径问题，具有一定的理论意义和实际价值。提出的概率转移矩阵、基于启发式变换的仿真优化方法对同类问题的研究具有借鉴作用。

目录

文摘

英文文摘

独创性说明及大连理工大学学位论文版权使用授权书

1引言

1.1问题的提出

1.2国内外同类研究现状

1.2.1 VRP及其求解算法的研究进展

1.2.2物流系统仿真研究进展

1.2.3仿真优化方法的研究进展

1.2.4国内外同类研究总结

1.3本文的主要研究工作

2 VRPTW分析和基于启发式变换的仿真优化方法的原理

2.1 VRPTW特点分析

2.2 VRPTW求解难点分析

2.3基于启发式变换的仿真优化方法原理

3基于启发式变换的VRPTW仿真优化求解方法

3.1物流配送方案的邻接矩阵表示

3.2基于邻接矩阵的VRPTW的数学模型

3.2.1基本车辆路径问题的矩阵模型

3.2.2矩阵的变换

3.2.3有时间窗的车辆路径问题的矩阵模型

3.3基于概率转移矩阵的VRPTW初始化方案的生成方法

3.3.1概率转移矩阵的构造

3.3.2基于概率转移矩阵的初始化方案生成方法

3.4基于启发式变换的策略改进方法

4算例分析与验证

4.1算法实现

4.1.1编程语言的选择

4.1.2系统分析

4.1.3系统总体设计

4.1.3系统详细设计

4.1.3系统实现

4.2结果验证

4.2.1对VRP求解验证

4.2.2对Benchmark Problems求解验证

5结论

5.1结论(创新点)

5.2进一步研究的方向

参考文献

附录A基于启发式变换的仿真优化算法核心代码

攻读硕士学位期间发表学术论文情况

致谢