The paper introduces a new model and training method for learning heuristics in combinatorial optimization problems, particularly for routing tasks like the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), Orienteering Problem (OP), and Prize Collecting TSP (PCTSP). The model uses attention mechanisms and is trained with REINFORCE algorithm and a greedy rollout baseline. It outperforms previous learned heuristics and traditional algorithms, achieving results close to optimal for TSP with up to 100 nodes. The model is also effective for VRP variants, OP, and stochastic PCTSP. The attention-based encoder-decoder model improves upon the Pointer Network by using attention layers and a more efficient training method. The model is trained with a baseline that reduces gradient variance, leading to faster learning. The results show that the model can learn strong heuristics for multiple routing problems with a single set of hyperparameters, demonstrating significant improvements over existing methods. The paper also discusses the scalability of the model and its potential for solving other combinatorial optimization problems on graphs.The paper introduces a new model and training method for learning heuristics in combinatorial optimization problems, particularly for routing tasks like the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), Orienteering Problem (OP), and Prize Collecting TSP (PCTSP). The model uses attention mechanisms and is trained with REINFORCE algorithm and a greedy rollout baseline. It outperforms previous learned heuristics and traditional algorithms, achieving results close to optimal for TSP with up to 100 nodes. The model is also effective for VRP variants, OP, and stochastic PCTSP. The attention-based encoder-decoder model improves upon the Pointer Network by using attention layers and a more efficient training method. The model is trained with a baseline that reduces gradient variance, leading to faster learning. The results show that the model can learn strong heuristics for multiple routing problems with a single set of hyperparameters, demonstrating significant improvements over existing methods. The paper also discusses the scalability of the model and its potential for solving other combinatorial optimization problems on graphs.