Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling
  Salesman Problem
Jingxiao Chen Ziqin Gong Minghuan Liu Jun Wang Yong Yu Weinan Zhang
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.