DET: Learn to Solve the Tunnel Traveling Salesmen Problem using Double-Encoder Transformer
Its authors withdrew this paper, so there is no full text to read or summarize.
Lists
Only you see this
Abstract
We delve into a challenging variant of the Traveling Salesman Problem (TSP), namely tunnel TSP, which incorporates a new important constraint requiring the traversal of a prescribed set of tunnels. While traditional deep reinforcement learning (DRL) based neural TSP algorithms excel in optimizing routes without tunnel restrictions, they often struggle to achieve optimal performance in tunnel TSP due to the neglect of the crucial role of tunnel attributes during solution generation. To address this challenge, we propose a simple but effective and flexible technique, called Double-Encoder Transformer (DET), which can be seamlessly integrated into various existing autoregressive neural TSP solvers. DET processes node and tunnel location information separately and encodes them in two distinct feature spaces. Following an efficient fusion strategy, DET then integrates the encoded information from nodes and tunnels, harnessing their intricate interactions. Experimental validation demonstrates that integrating DET into existing autoregressive neural solvers significantly improves performance, enabling us to reduce the average optimality gap for tunnel TSP from 12.58% (of the previous Single-Encoder model) to 7.35%.
BibTeX
@misc{zhao2025det,
author = {Nan Zhao and Jinshan Zhang and Paul Weng and Feng Wang and Jianwei Yin},
title = {{DET: Learn to Solve the Tunnel Traveling Salesmen Problem using Double-Encoder Transformer}},
year = {2025},
url = {https://openreview.net/forum?id=2YzeOOjvOi},
howpublished = {OpenReview},
note = {Submitted to ICLR 2025},
}Loading related content...