摘要
随着交通运输与物流配送行业的快速发展，物流企业逐渐有能力满足商家或客户指定的服务时间要求。带时间窗的车辆路径问题在在现实生活中应用日益广泛，如：物流配送、外卖配送、校车接送、班车接送及邮件揽收等。通过快速精确的优化算法，可以根据用户的需要，在保证物流效率的前提下为物流企业提供最佳配送方案，以实现减少运输总成本及配送车辆启用数量的目标。本文在充分考虑城市商品配送过程中客户点时间窗、配送车辆载重、配送车辆最大运输距离等约束的前提下，建立第一优化目标为运输总成本最小、第二优化目标为配送车辆启用数目最小的FSMVRPTW模型。通过设计6种删除算子及6种插入算子来丰富ALNS算法的算子选择池，并改进算法的评分策略及算子选择策略，进一步扩展了ALNS算法在求解大规模客户节点问题上的搜索能力。本次研究主要内容如下： (1)介绍带时间窗的车辆路径规划问题的研究背景，并从理论和实际两方面来理解和把握VRPTW的研究意义。总结多种类型的车辆路径问题及相应求解算法的国内外研究现状。 (2)根据实际配送问题的特点，确定优化目标。识别影响路径规划决策的关键要素，充分考虑VRP中涉及关键要素的多项约束，同时线性化研究过程中出现的变量间非线性关系，最终建立相应数学模型。 (3)介绍经典的蚁群算法和邻域搜索算法的原理及优缺点，并对算法进行改进。引入ALNS算法对带时间窗的车辆路径问题进行求解，介绍基于节约里程法的初始解的构建方法，阐明了自适应大邻域搜索算法的基本框架、模拟退火接受准则、经典破坏修复算子、自适应层中权重更新方式及算法终止条件。同时针对问题特点，对算法进行改进，设计新的破坏修复算子、评分策略及算子选择策略。 (4)对国际公开数据集中的Solomon、Gehringamp;Homberger标准数据集及其已知最优解提交平台的基本情况进行了介绍并给出通过控制变量法确定的改进ALNS算法的最佳参数值。对比分析改进的ALNS算法、ACO算法、NS算法的计算结果，算例测试结果显示：改进ALNS算法的运算结果优于SINTEF榜单中的已知最优解，在求解VRPTW时表现出了较强的适用性。同时在部分大规模客户点的算例实验中，算法计算结果优于阿里菜鸟网络仓配智能化算法团队提交的已知最优解。
NETL