论文部分内容阅读
本文基于烟草配送体系的特点，研究带时间窗的车辆路径问题，以降低企业的物流成本和费用，增加企业利润，进而提高企业自身的核心竞争力。本文设计了混合两阶段算法来求解带时间窗的车辆路径问题。这类问题的首要目标是最小化使用的车辆数，其次是最小化车辆的总行驶里程。文中混合两阶段算法第一阶段采用的是变邻域搜索算法，致力于降低使用的车辆数；第二阶段采用的是禁忌搜索算法，是在第一阶段的基础上最小化车辆的总行驶里程。第一阶段变邻域搜索算法包含四个过程，初始解构造、产生邻域解、局部搜索及当前最优解更新过程。初始解采用的是改进后的Solomon插入算法，产生邻域解过程是应用交换法、2-OPT法、交叉法等算子随机产生邻域解，而后采用重定位法和Ejection Chain算子对邻域解进行局部搜索，当前最优解得到更新的准则是最小化使用的车辆数、最小化最短路径的顾客点数、最小化车辆的总行驶里程，三准则的优先级依次降低。变邻域搜索算法在计算多次未更新最优解时，即达到最大迭代次数后退出。第二阶段禁忌搜索算法包含初始解、候选解、禁忌表、特赦准则、收敛准则等要素的设计。初始解是第一阶段变邻域搜索算法搜索得到的解，候选解集的产生是采用交换法、2-OPT法和重定位法三种算子随机生成，禁忌表中存储的禁忌对象是解的总行驶里程。最优解得到更新的准则是最小化使用的车辆数和最小化车辆的总行驶里程。禁忌搜索算法在计算多次未更新最优解时，即达到最大迭代次数后退出。为了较快较有效的获得计算结果，本文还设计了单向链表结构来存储解决方案，与一维二维存储结构相比大大降低了计算时间。本文对算法参数进行多种组合测试最终确定最佳参数取值，而后对356个实例共6组实例集Solomon、G02、G04、G06、G08、G10进行多次计算并统计，分析得到混合两阶段算法对每组实例集均计算出新的最优解，共获得了103个新解。算法对Solomon和G02实例集的计算效果显著，新解个数占实例总数的82.14%、58.33%；对G04有较好的计算效果；对G06、G08、G10有一定的计算效果。本文还将设计的混合两阶段算法嵌入到TransRouter智能车辆路径规划系统中，并应用其为重庆英雄公司和郑州烟草规划线路。