● 摘要
车辆路径问题（VRP）是运筹学中非常具有理论研究意义和实际应用价值的经典组合优化难题，本文在总结现有的求解VRP问题的亚启发式算法的基础上提出了增强回溯算法，该算法吸收了现有的亚启发式算法的优点，同时回避了它们的不足，使得该算法快速而有效。针对随机性VRP问题涉及到多阶段决策或者动态决策，而直接应用马尔科夫决策存在“维数灾难”等问题，本文提出了动态机会约束序贯优化策略，该策略实现了人为参与的以3W+N方式为特点的序贯优化决策，为解决随机性VRP问题提供了一个新的思路和方法。本文的研究工作主要体现在以下几个方面：1） 对求解VRP问题的亚启发式算法的理论分析与研究。创新点有：提出了回溯算法，该算法吸收了模拟退火、禁忌搜索、遗传算法的优点，同时能够回避它们的不足，因而使得该算法快速而有效。通过理论分析，证明了该算法所以快速的原因——隐含着大规模并行性，有效的原因——具有全局最优收敛性。2） 对回溯算法的改进研究。创新点有：提出了增强回溯算法以求解大规模装载量约束车辆路径问题（CVRP）问题，这是应用VRP解的局部改进可以使整体解得到优化的性质，通过抽取CVRP问题的区域子图，使增强算法具有更高的隐含大规模并行性而实现的。3） 将增强回溯算法应用于带时间窗的车辆路径问题(VRPTW)问题。创新点有：针对VRPTW约束很紧，解空间中不可行解比例过大而使得当前解不容易跳出局部最优的问题，提出了带有约束松弛的增强回溯算法。应用该算法在求解100点的大规模VRPTW国际算例时，得到最好解有的超过了算例中公布的最好解。4） 对于随机性VRP问题的理论分析与研究。创新点有：提出了动态机会约束序贯优化策略，并给出了该策略的一般数学表达式，以及决策变量的确定方法。动态机会约束序贯优化策略实现了人为参与的以3W+N方式为特点的序贯优化决策，由于有决策人的主动参与，克服了以往策略在面对具体情况不够灵活的缺点，更加符合人类的决策习惯和实际，能够充分发挥决策人的主观能动性。5） 对随机性VRP问题的动态机会约束序贯优化策略建立仿真模型。创新点有：将增强回溯算法嵌入决策仿真模型中，使人为参与的以3W+N方式为特点的序贯优化决策得以仿真实现，最后将该仿真模型应用于某轿车生产厂商的销售物流配送的实证研究中取得了良好的效果。