# Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2403.05318 · HTML: https://mlsanity.com/paper/2403.05318/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 29 references that are in the map.
- First posted on arXiv 8 Mar 2024.

## Builds on (most cited first, 14 of 14)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Stabilizing Transformers for Reinforcement Learning](https://mlsanity.com/paper/1910.06764/) (2019)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Reinforced Lin-Kernighan-Helsgaun Algorithms for the Traveling Salesman Problems](https://mlsanity.com/paper/2207.03876/) (2022)
- [Learning to Solve Soft-Constrained Vehicle Routing Problems with Lagrangian Relaxation](https://mlsanity.com/paper/2207.09860/) (2022)

## Built on by (most cited first, 8 of 8)

- [Learning to Handle Complex Constraints for Vehicle Routing Problems](https://mlsanity.com/paper/2410.21066/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [LMask: Learn to Solve Constrained Routing Problems with Lazy Masking](https://mlsanity.com/paper/2505.17938/) (2025)
- [Towards Efficient Constraint Handling in Neural Solvers for Routing Problems](https://mlsanity.com/paper/2602.16012/) (2026)
- [Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs](https://mlsanity.com/paper/2506.22095/) (2025)
- [Learning to Search for Vehicle Routing with Multiple Time Windows](https://mlsanity.com/paper/2505.23098/) (2025)
- [Learning to Solve Orienteering Problem with Time Windows and Variable Profits](https://mlsanity.com/paper/2603.06260/) (2026)
- [Two-Stage Learned Decomposition for Scalable Routing on Multigraphs](https://mlsanity.com/paper/2605.05389/) (2026)

## Abstract (arXiv)

Many real-world problems can be formulated as a constrained Traveling Salesman Problem (TSP). However, the constraints are always complex and numerous, making the TSPs challenging to solve. When the number of complicated constraints grows, it is time-consuming for traditional heuristic algorithms to avoid illegitimate outcomes. Learning-based methods provide an alternative to solve TSPs in a soft manner, which also supports GPU acceleration to generate solutions quickly. Nevertheless, the soft manner inevitably results in difficulty solving hard-constrained problems with learning algorithms, and the conflicts between legality and optimality may substantially affect the optimality of the solution. To overcome this problem and to have an effective solution against hard constraints, we proposed a novel learning-based method that uses looking-ahead information as the feature to improve the legality of TSP with Time Windows (TSPTW) solutions. Besides, we constructed TSPTW datasets with hard constraints in order to accurately evaluate and benchmark the statistical performance of various approaches, which can serve the community for future research. With comprehensive experiments on diverse datasets, MUSLA outperforms existing baselines and shows generalizability potential.