组合优化问题是计算机科学与运筹学中一个重要的问题,其在物流、生产调度、资源分配和社交网络等领域应用广泛。由于该问题具有重要的理论价值和应用前景,一直以来受到学者的广泛关注。旅行商问题是组合优化领域中一个典型的NP难问题,传统的旅行商问题考虑确定的客户集并已知客户之间的运输距离,其优化的目标是找一个从仓库出发访问每个客户仅一次并回到仓库的最短路径序列。包含随机因素的动态旅行商问题是更为一般化的问题形式,在传统问题形式中加入了影响路径规划的随机因素,例如动态的旅行时间和动态的客户需求。事实上,动态随机的旅行商问题更贴近实际应用,因此相比于静态问题它更具有研究价值和实际应用性。本文提出了一个基于强化学习构建的模型并用于求解包含随机客户的动态旅行商问题。在标准旅行商问题的基础上,本文假设客户的需求是动态变化的,每次求解只有部分客户有配送需求,而所规划车辆路径只需访问有需求的客户并使路径花费达到最小。该问题模型可以刻画物流企业中的日常配送问题,在该类问题中客户相对固定,但每天所需要配送的客户集合不完全一致,路径的规划需反复求解相近的问题。车辆路径规划模型主要由两部分构成:第一部分基于启发式算法在各随机节点问题上的求解数据,采用分段聚类算法将所有节点分割成若干个类簇,以此作为强化学习方法中状态表示和动作选择的基础。第二部分基于随机生成的动态实例应用Q-Learning算法训练模型,采用Res Ne Xt网络架构结合空间注意力机制作为模型决策网络,并用于决策类簇间的访问序列,而类内待访问节点序列采用2-OPT算法进行优化,最终得到动态问题的策略序列。本文将所提出的模型架构称为DTSPSC-RL,在对模型进行训练后,DTSPSC-RL可以反复求解节点数量动态变化的旅行商问题,无需对每个问题实例重新训练模型,从而达到了有效解决物流企业日常配送问题。基于上述模型,本文从离线决策和在线决策两个方面分别给出了相应的求解方案,离线决策指在执行计划之前计算解决方案的方法,在车辆出发前已知本次需要服务的客户对象集合,基于DTSPSC-RL规划访问路径以求解包含随机客户的动态旅行商问题。在线决策指在动态事件发生时立即计算解决方案的方法,在车辆出发前已知部分具有需求的客户对象,而另一部分客户的需求在车辆配送过程中才被提交,本文在DTSPSC-RL的基础上,提出了一种在线路径调整方法以实时求解包含随机客户的动态旅行商问题。