Towards Feature-free TSP Solver Selection: A Deep Learning Approach

• URL: http://arxiv.org/abs/2006.00715v2
• Date: Wed, 14 Apr 2021 10:28:04 GMT
• Title: Towards Feature-free TSP Solver Selection: A Deep Learning Approach
• Authors: Kangfei Zhao, Shengcai Liu, Yu Rong, Jeffrey Xu Yu
• Abstract summary: The Travelling Salesman Problem (TSP) is a classical NP-hard problem and has broad applications in many disciplines and industries. In this paper, we propose a deep learning framework, CTAS, for TSP solver selection in an end-to-end manner.
• Score: 35.05032046810422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Travelling Salesman Problem (TSP) is a classical NP-hard problem and has broad applications in many disciplines and industries. In a large scale location-based services system, users issue TSP queries concurrently, where a TSP query is a TSP instance with $n$ points. In the literature, many advanced TSP solvers are developed to find high-quality solutions. Such solvers can solve some TSP instances efficiently but may take an extremely long time for some other instances. Due to the diversity of TSP instances, it is well-known that there exists no universal best solver dominating all other solvers on all possible TSP instances. To solve TSP efficiently, in addition to developing new TSP solvers, it needs to find a per-instance solver for each TSP instance, which is known as the TSP solver selection problem. In this paper, for the first time, we propose a deep learning framework, \CTAS, for TSP solver selection in an end-to-end manner. Specifically, \CTAS exploits deep convolutional neural networks to extract informative features from TSP instances and involves data argumentation strategies to handle the scarcity of labeled TSP instances. Moreover, to support large scale TSP solver selection, we construct a challenging TSP benchmark dataset with 6,000 instances, which is known as the largest TSP benchmark. Our \CTAS achieves over 2$\times$ speedup of the average running time, comparing the single best solver, and outperforms the state-of-the-art statistical models.

Related papers

• Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem [67.32731657297377]
  Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics. Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency. We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
  arXiv  Detail & Related papers  (2023-04-19T03:48:32Z)
• H-TSP: Hierarchically Solving the Large-Scale Travelling Salesman Problem [11.310986634385742]
  We propose an end-to-end learning framework based on hierarchical reinforcement learning, called H-TSP, for addressing the large-scale Travelling Salesman Problem (TSP) We show that H-TSP can achieve comparable results as SOTA search-based approaches, and we reduce the time consumption up to two orders of magnitude (3.32s vs. 395.85s) Although there are still gaps to SOTA results with respect to solution quality, we believe H-TSP will be useful for practical applications, particularly those that are time-sensitive e.g., on-call routing and ride
  arXiv  Detail & Related papers  (2023-04-19T03:10:30Z)
• Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning [59.14935871979047]
  This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) Common to these approaches is the use of graph models based on multi-head attention layers.
  arXiv  Detail & Related papers  (2022-07-04T14:31:47Z)
• Learning to Solve Travelling Salesman Problem with Hardness-adaptive Curriculum [42.28343071442175]
  We propose a hardness-adaptive generator to generate instances ten times harder than the existing methods. Our proposed method achieves significant improvement over state-of-the-art models in terms of the optimality gap.
  arXiv  Detail & Related papers  (2022-04-07T05:59:05Z)
• Fast Approximations for Job Shop Scheduling: A Lagrangian Dual Deep Learning Method [44.4747903763245]
  The Jobs shop Scheduling Problem (JSP) is a canonical optimization problem that is routinely solved for a variety of industrial purposes. The problem is NP-hard and computationally challenging even for medium-sized instances. This paper explores a deep learning approach to deliver efficient and accurate approximations to the problem.
  arXiv  Detail & Related papers  (2021-10-12T21:15:19Z)
• Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
  This paper tries to train a small-scale model, which could be repetitively used to build heat maps for the traveling salesman problem (TSP) Heat maps are fed into a reinforcement learning approach (Monte Carlo tree search) to guide the search of high-quality solutions. Experimental results show that, this new approach clearly outperforms the existing machine learning based TSP algorithms.
  arXiv  Detail & Related papers  (2020-12-19T11:06:30Z)
• Learning to Optimise General TSP Instances [2.6782615615913348]
  The Travelling Salesman Problem (TSP) is a classical optimisation problem. Deep learning has been successfully extended to meta-learning, where previous solving efforts assist in learning how to optimise future instances. This paper introduces a new learning-based approach to solve a variety of different and common TSP problems.
  arXiv  Detail & Related papers  (2020-10-23T07:37:16Z)
• Solving the Clustered Traveling Salesman Problem via TSP methods [16.304413942851397]
  The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP.
  arXiv  Detail & Related papers  (2020-07-10T08:56:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.