策略梯度的超启发算法求解带容量约束车辆路径问题
张景玲
孙钰粟
赵燕伟
余孟凡
蒋玉勇
浙江工业大学特种装备制造及先进加工技术教育部重点实验室,浙江杭州 310014
摘要：有容量车辆路径问题是组合优化问题中比较热门的问题,它属于经典的NP-hard问题并且时间复杂度高.本文提出了一种基于策略梯度的超启发算法,将强化学习中的确定性策略梯度算法引入到超启发算法的高层策略中的底层算法选择策略,确定性策略梯度算法采用Actor-Critic框架,另外为了能够在后续计算和神经网络参数更新中引用历史经验数据,在确定性策略梯度算法中设计了经验池用于存储状态转移数据.在超启发算法解的接受准则方面,文中通过实验对比了3种接受准则的效果,最终选择了自适应接受准则作为高层策略中解的接受准则.通过对有容量车辆路径问题标准算例的计算,并将求解结果与其他算法对比,验证了所提算法在该问题求解上的有效性和稳定性.
关键词：车辆路径问题强化学习关策略梯度算法神经网络超启发算法
论文发表日期：2024-06-28
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：12( 1111-1122 )
英文信息