针对传统遗传算法在求解带时间窗的车辆路径问题(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的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。展开更多
针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯...针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯随机游走策略对个体的历史最优位置进行回溯搜索,改善算法的探索能力;考虑到自适应策略对初始种群多样性敏感的问题,结合Tent混沌映射初始化种群,提高算法的鲁棒性以及全局寻优能力;将提出的改进算法在13个经典测试函数中进行性能验证,并移植于无人机三维路径规划问题中。在30峰、40峰、50峰的环境模型下进行测试,与遗传算法、粒子群算法、SRM-PSO(self-regulating and self-perception particle swarm optimization with mutation mechanism)算法以及野马算法对比,全粒子推动野马算法皆取得最短平均路径,且在所有测试中都找到满足约束、无碰的路径。仿真结果证明,在复杂环境下全粒子推动野马算法具有优秀的全局寻优能力以及较好的鲁棒性。展开更多
文摘针对传统遗传算法在求解带时间窗的车辆路径问题(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的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。
文摘针对无人机路径规划求解计算量大、难收敛等问题,提出了一种基于全粒子推动野马算法的路径规划方法。建立三维环境模型与路径代价模型,将路径规划问题转化为多维函数优化问题;采用一种自适应邻域搜索策略,改善算法的开发能力;利用高斯随机游走策略对个体的历史最优位置进行回溯搜索,改善算法的探索能力;考虑到自适应策略对初始种群多样性敏感的问题,结合Tent混沌映射初始化种群,提高算法的鲁棒性以及全局寻优能力;将提出的改进算法在13个经典测试函数中进行性能验证,并移植于无人机三维路径规划问题中。在30峰、40峰、50峰的环境模型下进行测试,与遗传算法、粒子群算法、SRM-PSO(self-regulating and self-perception particle swarm optimization with mutation mechanism)算法以及野马算法对比,全粒子推动野马算法皆取得最短平均路径,且在所有测试中都找到满足约束、无碰的路径。仿真结果证明,在复杂环境下全粒子推动野马算法具有优秀的全局寻优能力以及较好的鲁棒性。
