Chen, J; Gong, Z; Chen, L; Liu, M; Wang, J; Yu, Y; Zhang, W; (2025) Looking Ahead to Avoid Being Late: Solving Hard-Constrained Traveling Salesman Problem. In: DAI '24: Proceedings of the 2024 6th International Conference on Distributed Artificial Intelligences. (pp. pp. 1-12). ACM (Association for Computing Machinery): Singapore, Singapore.

Preview

Text 2403.05318v1.pdf - Published Version Download (567kB) | Preview

Abstract

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, MUSLA, that uses multi-step 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.

Download activity - last month

Export as JSONCSVXML

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as JSONCSVXML

Archive Staff Only

View Item