Decision Transformer-based Traveling Salesman Tour Generation

With the surge of new machine learning methods, research in classic problems like the Traveling Salesman Problem (TSP) is receiving a resurgence of popularity. One of the biggest goals in this renewed interest is to create a model that can not only outperform state-of-the-art heuristic solvers in speed for trivial sizes, but also generalize to larger TSP instances that are currently intractable. In this thesis we approach the TSP with the Decision Transformer, a transformer-based architecture transforming reinforcement learning environments into transformer-compatible sequence-modeling problems. By modeling a TSP instance as an graph-based environment with states and actions, we can input partial tours into the Decision Transformer to infer the next best action in an autoregressive fashion. With the power of the transformer, we take the first step in making headway on the issue of generalization where past models have failed.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2023

Author dc:creator

• Liu, Daniel S.

Advisor dc:contributor.advisor

• Balakrishnan, Hamsa

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright retained by author(s)

Licence dc:rights.uri

• https://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/151529

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/151529