近年、深層強化学習が組み合わせ最適化タスクに対する有望なアプローチとして注目されている。本研究では、ランダム生成された巡回セールスマン問題インスタンスに対し、ベースライン付きREINFORCEとActor-Criticの2つの強化学習モデルを適用した。また、両モデルの方策ネットワークにはMulti-Head Attentionをベースとしたアーキテクチャを採用した。モデルの評価として整数計画法による厳密解との経路長のGap（乖離度）を算出したところ、Actor-Criticモデルがより厳密解に近い経路を導出した。本研究で得られた知見は、実現場における配送経路最適化の足掛かりとなる可能性がある。