Back to Search
Start Over
Hybrid pointer networks for traveling salesman problems optimization
- Source :
- PLoS ONE, PLoS ONE, Vol 16, Iss 12, p e0260995 (2021)
- Publication Year :
- 2021
- Publisher :
- Public Library of Science, 2021.
-
Abstract
- In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer’s encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.
- Subjects :
- FOS: Computer and information sciences
Optimization
Computer Science - Machine Learning
Computer and Information Sciences
Computer Science - Artificial Intelligence
Permutation
Science
Research and Analysis Methods
Polynomials
Machine Learning (cs.LG)
Machine Learning
Machine Learning Algorithms
Artificial Intelligence
FOS: Mathematics
Computer Simulation
Mathematics - Optimization and Control
Multidisciplinary
Discrete Mathematics
Applied Mathematics
Simulation and Modeling
Models, Theoretical
Artificial Intelligence (cs.AI)
Algebra
Optimization and Control (math.OC)
Combinatorics
Physical Sciences
Medicine
Mathematics
Algorithms
Network Analysis
Software
Research Article
Subjects
Details
- Language :
- English
- ISSN :
- 19326203
- Volume :
- 16
- Issue :
- 12
- Database :
- OpenAIRE
- Journal :
- PLoS ONE
- Accession number :
- edsair.doi.dedup.....f799f780d08784310644584f60855fdc