The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics

• URL: http://arxiv.org/abs/2002.01070v1
• Date: Tue, 4 Feb 2020 00:57:35 GMT
• Title: The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
• Authors: Jakob Bossek, Katrin Casel, Pascal Kerschke and Frank Neumann
• Abstract summary: Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP) In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour.
• Score: 10.946271021892922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several important optimization problems in the area of vehicle routing can be seen as a variant of the classical Traveling Salesperson Problem (TSP). In the area of evolutionary computation, the traveling thief problem (TTP) has gained increasing interest over the last 5 years. In this paper, we investigate the effect of weights on such problems, in the sense that the cost of traveling increases with respect to the weights of nodes already visited during a tour. This provides abstractions of important TSP variants such as the Traveling Thief Problem and time dependent TSP variants, and allows to study precisely the increase in difficulty caused by weight dependence. We provide a 3.59-approximation for this weight dependent version of TSP with metric distances and bounded positive weights. Furthermore, we conduct experimental investigations for simple randomized local search with classical mutation operators and two variants of the state-of-the-art evolutionary algorithm EAX adapted to the weighted TSP. Our results show the impact of the node weights on the position of the nodes in the resulting tour.

Related papers

• On the Impact of Operators and Populations within Evolutionary Algorithms for the Dynamic Weighted Traveling Salesperson Problem [13.026567958569965]
  We investigate the node weighted traveling salesperson problem (W-TSP) in dynamic settings. In the dynamic setting of the problem, items that have to be collected as part of a TSP tour change over time. Our first experimental investigations study the impact of such changes on resulting optimized tours.
  arXiv  Detail & Related papers  (2023-05-30T11:39:49Z)
• Neural Functional Transformers [99.98750156515437]
  This paper uses the attention mechanism to define a novel set of permutation equivariant weight-space layers called neural functional Transformers (NFTs) NFTs respect weight-space permutation symmetries while incorporating the advantages of attention, which have exhibited remarkable success across multiple domains. We also leverage NFTs to develop Inr2Array, a novel method for computing permutation invariant representations from the weights of implicit neural representations (INRs)
  arXiv  Detail & Related papers  (2023-05-22T23:38:27Z)
• 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)
• SRRT: Exploring Search Region Regulation for Visual Object Tracking [58.68120400180216]
  We propose a novel tracking paradigm, called Search Region Regulation Tracking (SRRT) SRRT applies a proposed search region regulator to estimate an optimal search region dynamically for each frame. On the large-scale LaSOT benchmark, SRRT improves SiamRPN++ and TransT with absolute gains of 4.6% and 3.1% in terms of AUC.
  arXiv  Detail & Related papers  (2022-07-10T11:18:26Z)
• Averaging Spatio-temporal Signals using Optimal Transport and Soft Alignments [110.79706180350507]
  We show that our proposed loss can be used to define temporal-temporal baryechecenters as Fr'teche means duality. Experiments on handwritten letters and brain imaging data confirm our theoretical findings.
  arXiv  Detail & Related papers  (2022-03-11T09:46:22Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• The Implicit Biases of Stochastic Gradient Descent on Deep Neural Networks with Batch Normalization [44.30960913470372]
  Deep neural networks with batch normalization (BN-DNNs) are invariant to weight rescaling due to their normalization operations. We investigate the implicit biases of gradient descent (SGD) on BN-DNNs to provide a theoretical explanation for the efficacy of weight decay.
  arXiv  Detail & Related papers  (2021-02-06T03:40:20Z)
• Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation [8.620967398331265]
  The Travelling Thief Problem (TTP) is a challenging optimization problem that attracts many scholars. In this paper, TTP is investigated theoretically and empirically. An algorithm based on the score value calculated by our proposed formulation in picking items and sorting items in the reverse order is proposed to solve the problem.
  arXiv  Detail & Related papers  (2020-12-16T12:06:05Z)
• Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions [13.026567958569965]
  The Traveling Thief Problem (TTP) addresses such interactions by combining two optimisation problems. A new problem called the node weight dependent Traveling Salesperson Problem (W-TSP) has been introduced where nodes have weights that influence the cost of the tour. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function.
  arXiv  Detail & Related papers  (2020-06-05T07:07:28Z)
• Surrogate Assisted Optimisation for Travelling Thief Problems [14.836145520657592]
  The travelling thief problem (TTP) is a multi-component optimisation problem involving two interdependent NP-hard components. Recent state-of-the-art TTP solvers modify the underlying TTP and KP solutions in an iterative and interleaved fashion. We propose to make the search more efficient through an adaptive surrogate model that learns the characteristics of initial TSP tours that lead to good TTP solutions.
  arXiv  Detail & Related papers  (2020-05-14T02:49:16Z)
• Revisiting Initialization of Neural Networks [72.24615341588846]
  We propose a rigorous estimation of the global curvature of weights across layers by approximating and controlling the norm of their Hessian matrix. Our experiments on Word2Vec and the MNIST/CIFAR image classification tasks confirm that tracking the Hessian norm is a useful diagnostic tool.
  arXiv  Detail & Related papers  (2020-04-20T18:12:56Z)

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.