随机车辆路径问题研究

随着市场竞争的日益加剧、世界经济一体化进程的加快和科学技术的飞速发展，许多企业已经把物流作为提高市场竞争能力和提升核心竞争能力的重要手段，将先进的物流理论和物流技术引入企业的生产和经营管理中。作为实现物流合理化的重要内容和手段，研究车辆路径有助于企业降低物流成本，提高运作效率，全面提高顾客满意度。由于车辆路径问题将运筹学理论与生产实践紧密地结合在一起，近几十年取得了很多成果，因此被称为“最近几十年运筹学领域最成功的研究之一”。以往对车辆路径问题的研究多是基于确定性信息，而在实际中出现在路径制定者面前的往往是一些具有统计规律的随机性信息，研究确定性车辆路径问题的有效方法不一定能有效解决随机车辆路径问题，因此有必要研究随机车辆路径问题的特征，构造有效的模型和算法。但到目前为止，对随机性信息条件下车辆路径问题的研究仍然较少，许多不尽人意的地方有待于进一步完善和改进。本文较深入地研究了随机性信息条件下的一系列车辆路径问题，具有重要的理论意义和实用价值。 论文的主要研究内容如下： 第1章在对大量相关文献进行总结提炼的基础上，分别回顾了国内、外对车辆路径问题的研究成果，分析了构成该问题的各个要素，并指出了随机车辆路径问题研究中存在的不足和潜在的研究领域。 第2章简要地介绍了组合优化问题中的一些概念，对目前应用广泛的亚启发式算法的一般特征进行了总结，重点阐述了遗传算法和模拟退火算法的产生、发展、机理和特点。另外，针对基于序数编码遗传算法理论不足的现状，研究了基于序数编码遗传算法的模式定理：短阶、高平均适应值的模式数量将随着代数的增加呈指数增长。 第3章研究了一类随机顾客和随机需求量车辆路径问题的模型和算法。该问题的特别之处在于，假设顾客需求不可分割，且顾客是否需求商品的信息在车辆还未到达该顾客点前就已获得，而准确的需求量仅仅当车辆到达该顾客点时才能获知。论文提出了单回路策略和多回路策略，分析了这两种策略的上、下界和渐近性能，并以对预回路的评价作为目标函数，设计了求解问题的遗传算法和模拟退火算法。 第4章研究了随机旅行时间车辆路径问题的模型和算法。作者提出了具有容量约束的机会约束模型和补偿模型，并把它们改造成便于使用遗传算法 第11页 西南交通大学博士研究生学位论文 求解的形式；基于新构造的 MX3和 MX4两种交叉算子分别设计出求解上述 两种模型的遗传算法，实验表明这两种交叉算子优于MXI和MXZ算子。 第5章利用组合优化、排队论和几何概率领域的理论和知识，研究以期 望系统时间最小为目标函数的有容量约束动态随机需求量车辆路径问题的下 界，提出了解决该问题的TSP策略及其改进的TSP策略，并对这两种运作策 略的渐近性能进行了分析。 库存控制问题和路径问题是物流管理中两个重要的、联系密切的问题， 将它们综合在一起考虑会进一步降低企业的物流成本，在第6章中以库存成 本和路径成本最小化作为目标，提出了求解一类随机库存路径问题的启发式 算法，该算法体系具有简明实用且行之有效的特点。 结论部分指出论文的主要创新之处，并对未来研究作以展望。