凝聚层次聚类-深度强化学习耦合的动态车辆路径实时优化OA

动态车辆路径问题(DVRP)是现阶段物流领域最常见的问题之一,通过引入凝聚层次聚类算法(agglomerative hierarchical clustering,AHC)对初始数据集进行预处理将其划分给多辆车,形成多个车辆服务簇,再结合混合启发式算法对各服务簇进行求解极大提高了求解效率和解的质量。为进一步提高求解速度和解的质量,提出自注意力机制驱动的深度强化学习(deep reinforcement learning,DRL)。该方法采用关键点更新策略和“预优化+实时优化”策略,构建基于双Q网络(double Q-network,DDQN)的静态预优化框架和多场景实时优化框架,在框架的构建中考虑车辆时变特性,同时在双Q网络中引入自注意力机制。通过三组实验测试,并与混合蚁群优化算法(hybrid ant colony optimization,HACO)、禁忌搜索算法(tabu search,TS)以及自适应大邻域搜索(adaptive large neighborhood search,ALNS)进行比较,验证了所提出的自注意力机制驱动的深度强化学习框架的可行性和有效性,经过训练的模型在实际案例中对每个动态订单的动态调整平均耗时仅为0.18 s即可得到较优解。