为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻...为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(improved adaptive large neighborhood search,IALNS)算法,提出新的删除、修复算子及动态阶段加速策略,分别针对大规模的静态算例与动态算例进行算法性能测试。结果表明,与无改进策略的IALNS(IALNS-ND)相比,静态问题中在相同的求解时间内75%的算例(12个算例中9个)IALNS得到的最小值和平均值优于IALNS-ND,动态问题中95%(60个算例中57个算例)的算例可以得到成本和时间均优于IALNS-ND的解;与三种算法——自适应大规模邻域搜索算法(ALNS)、大规模邻域搜索算法(LNS)以及变邻域搜索算法(VNS)相比,静态问题中所有算例IALNS获得的总成本的最小值和平均值均优于三个对比算法,动态问题中58%(60个算例中35个算例)的算例IALNS能够以少于三个对比算法1.5倍甚至10倍的时间获得更优的解。同时随着问题动态度的提高,IALNS的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。展开更多
针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将...针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。展开更多
文摘为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(improved adaptive large neighborhood search,IALNS)算法,提出新的删除、修复算子及动态阶段加速策略,分别针对大规模的静态算例与动态算例进行算法性能测试。结果表明,与无改进策略的IALNS(IALNS-ND)相比,静态问题中在相同的求解时间内75%的算例(12个算例中9个)IALNS得到的最小值和平均值优于IALNS-ND,动态问题中95%(60个算例中57个算例)的算例可以得到成本和时间均优于IALNS-ND的解;与三种算法——自适应大规模邻域搜索算法(ALNS)、大规模邻域搜索算法(LNS)以及变邻域搜索算法(VNS)相比,静态问题中所有算例IALNS获得的总成本的最小值和平均值均优于三个对比算法,动态问题中58%(60个算例中35个算例)的算例IALNS能够以少于三个对比算法1.5倍甚至10倍的时间获得更优的解。同时随着问题动态度的提高,IALNS的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。
文摘针对传统遗传算法在求解带时间窗的车辆路径问题(vehicle routing problems with time window,VRPTW)上存在的易陷入局部最优及求解质量不高等问题,本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合,称为ALNS-GA设计了3个移除算子和2个重插算子,以提高遗传算法的局部搜索能力,并优化了初始种群生成策略。同时,为了验证算法的有效性,分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法(LNS-GA、LNS*-GA),并选取Solomon数据库上VRPTW测试算例,在Matlab R2016b上进行实验验证。实验结果表明,当终止条件为迭代100次时,ALNS-GA的求解质量高于传统遗传算法,大部分案例中,ALNS-GA所求的最好值优于LNS-GA和LNS*-GA,且ALNS-GA平均用时均小于LNS-GA和LNS*-GA,特别是当顾客规模为100时,ALNS-GA的平均用时更少,虽然小部分案例的平均值略高于LNS-GA和LNS*-GA,但从整体上看,ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA,说明经过改进后,遗传算法的局部搜索能力明显提高,可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。
