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.

使用前瞻信息作为特征，提出一种利用学习方法改善具有时间窗口的 TSP 解决方案合法性的新方法，并构建了具有硬约束条件的 TSPTW 数据集进行准确评估和基准测试。通过对多种数据集进行综合实验，MUSLA 优于现有基线算法且具有一定的泛化能力。