Solving the Clustered Traveling Salesman Problem via TSP methods

• URL: http://arxiv.org/abs/2007.05254v3
• Date: Thu, 14 Apr 2022 11:34:37 GMT
• Title: Solving the Clustered Traveling Salesman Problem via TSP methods
• Authors: Yongliang Lu, Jin-Kao Hao, Qinghua Wu
• Abstract summary: 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.
• Score: 16.304413942851397
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.

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)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• TCT: Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels [141.29156234353133]
  State-of-the-art convex learning methods can perform far worse than their centralized counterparts when clients have dissimilar data distributions. We show this disparity can largely be attributed to challenges presented by non-NISTity. We propose a Train-Convexify neural network (TCT) procedure to sidestep this issue.
  arXiv  Detail & Related papers  (2022-07-13T16:58:22Z)
• 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)
• On the Use of Quality Diversity Algorithms for The Traveling Thief Problem [11.590506672325668]
  In real-world optimisation, it is common to face several sub-problems interacting and forming the main problem. In this paper, we investigate the inter-dependency of the traveling salesperson problem(TSP) and the knapsack problem(KP) by means of quality diversity(QD) approaches.
  arXiv  Detail & Related papers  (2021-12-16T05:08:39Z)
• 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)
• Towards Feature-free TSP Solver Selection: A Deep Learning Approach [35.05032046810422]
  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.
  arXiv  Detail & Related papers  (2020-06-01T04:48:36Z)

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.