GRAWA: A Deep Reinforcement Learning Approach for the Multi-Objective Traveling Salesman Problem
5 affiliations
- 1School of Automation, Nanjing University of Information Science and Technology, Nanjing 210044, China
- 2The Sixty-Third Research Institute, National University of Defense Technology, Nanjing 210007, China
- 3Laboratory for Big Data and Decision, National University of Defense Technology, Changsha 410073, China
- 4National Key Laboratory of Information Systems Engineering, National University of Defense Technology, Changsha 410073, China
- 5School of Artificial Intelligence, Nanjing University of Information Science and Technology, Nanjing 210044, China
Abstract
The multi-objective traveling salesman problem (MOTSP) is a typical challenging multi-objective combinatorial optimization problem. Numerous advanced deep reinforcement learning algorithms have been developed to solve it. Existing learning-based methods can share information across subproblems through mechanisms such as parameter transfer. This paper investigates explicit graph-based modeling of preference relationships within a shared policy and proposes a graph-relation-driven deep reinforcement learning algorithm for MOTSP. The proposed algorithm trains a model to map problem instances to approximate Pareto sets under a collection of preference vectors. Specifically, the graph weight encoder combines global and objective-specific city representations with preference features learned on a fixed graph whose edges are defined by distances between weight vectors. A graph co-guided fusion module then combines global and objective-specific city embeddings with the learned preference representations to generate preference-conditioned city embeddings. The resulting problem embeddings and contextual embeddings are supplied to the decoder to generate candidate tours in parallel, providing an approximation to the Pareto set. Furthermore, a Top-p training baseline is introduced to adaptively select reference candidates according to their scalarized costs. Finally, extensive experiments are conducted on various MOTSP instances. Comparisons are carried out between the proposed algorithm and heuristic and learning-based algorithms. Experimental results demonstrate the solution quality of the proposed algorithm on the evaluated multi-objective traveling salesman problems. Its computational cost is reported under the specified hardware, decoding budgets, and evaluation settings.
Related
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Traveling Salesman Problem on Graphs with Proportional Independent Set
- On the Segment-Based Remove-and-Reinsert Heuristic for the Generalized Traveling Salesman Problem
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
- Collaborative Attention Ant Colony Optimization for Large-Scale Traveling Salesman Problems
BibTeX
@article{ji2026grawa,
title = {{GRAWA: A Deep Reinforcement Learning Approach for the Multi-Objective Traveling Salesman Problem}},
author = {Zhengtao Ji and Xiaoxiong Zhang and Xixi Zhu and Shengye Yan},
journal = {Mathematics},
year = {2026},
month = nov,
doi = {10.3390/math14214090},
url = {https://www.mdpi.com/2227-7390/14/21/4090},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - GRAWA: A Deep Reinforcement Learning Approach for the Multi-Objective Traveling Salesman Problem
AU - Zhengtao Ji
AU - Xiaoxiong Zhang
AU - Xixi Zhu
AU - Shengye Yan
PY - 2026
DA - 2026/11/07
JO - Mathematics
DO - 10.3390/math14214090
UR - https://www.mdpi.com/2227-7390/14/21/4090
AB - The multi-objective traveling salesman problem (MOTSP) is a typical challenging multi-objective combinatorial optimization problem. Numerous advanced deep reinforcement learning algorithms have been developed to solve it. Existing learning-based methods can share information across subproblems through mechanisms such as parameter transfer. This paper investigates explicit graph-based modeling of preference relationships within a shared policy and proposes a graph-relation-driven deep reinforcement learning algorithm for MOTSP. The proposed algorithm trains a model to map problem instances to approximate Pareto sets under a collection of preference vectors. Specifically, the graph weight encoder combines global and objective-specific city representations with preference features learned on a fixed graph whose edges are defined by distances between weight vectors. A graph co-guided fusion module then combines global and objective-specific city embeddings with the learned preference representations to generate preference-conditioned city embeddings. The resulting problem embeddings and contextual embeddings are supplied to the decoder to generate candidate tours in parallel, providing an approximation to the Pareto set. Furthermore, a Top-p training baseline is introduced to adaptively select reference candidates according to their scalarized costs. Finally, extensive experiments are conducted on various MOTSP instances. Comparisons are carried out between the proposed algorithm and heuristic and learning-based algorithms. Experimental results demonstrate the solution quality of the proposed algorithm on the evaluated multi-objective traveling salesman problems. Its computational cost is reported under the specified hardware, decoding budgets, and evaluation settings.
SN - 2227-7390
ER -