Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions

• URL: http://arxiv.org/abs/2006.03260v1
• Date: Fri, 5 Jun 2020 07:07:28 GMT
• Title: Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
• Authors: Jakob Bossek, Aneta Neumann, Frank Neumann
• Abstract summary: 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.
• Score: 13.026567958569965
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) addresses such interactions by combining two combinatorial optimisation problems, namely the TSP and the Knapsack Problem (KP). Recently, 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. In this paper, we compare W-TSP and TTP. We investigate the structure of the optimised tours for W-TSP and TTP and the impact of using each others fitness function. Our experimental results suggest (1) that the W-TSP often can be solved better using the TTP fitness function and (2) final W-TSP and TTP solutions show different distributions when compared with optimal TSP or weighted greedy solutions.

Related papers

• Semi-Supervised Coupled Thin-Plate Spline Model for Rotation Correction and Beyond [84.56978780892783]
  We propose CoupledTPS, which iteratively couples multiple TPS with limited control points into a more flexible and powerful transformation. In light of the laborious annotation cost, we develop a semi-supervised learning scheme to improve warping quality by exploiting unlabeled data. Experiments demonstrate the superiority and universality of CoupledTPS over the existing state-of-the-art solutions for rotation correction.
  arXiv  Detail & Related papers  (2024-01-24T13:03:28Z)
• Equivariant Deep Weight Space Alignment [54.65847470115314]
  We propose a novel framework aimed at learning to solve the weight alignment problem. We first prove that weight alignment adheres to two fundamental symmetries and then, propose a deep architecture that respects these symmetries.
  arXiv  Detail & Related papers  (2023-10-20T10:12:06Z)
• Solving Travelling Thief Problems using Coordination Based Methods [16.685542610215286]
  A travelling thief problem (TTP) is a proxy to real-life problems such as postal collection. In TTP, city selection and item selection decisions need close coordination since the thief's travelling speed depends on the knapsack's weight. Existing TTP solvers deal with city selection and item selection separately, keeping decisions for one type unchanged while dealing with the other type.
  arXiv  Detail & Related papers  (2023-10-11T03:03:50Z)
• Roulette-Wheel Selection-Based PSO Algorithm for Solving the Vehicle Routing Problem with Time Windows [58.891409372784516]
  This paper presents a novel form of the PSO methodology that uses the Roulette Wheel Method (RWPSO) Experiments using the Solomon VRPTW benchmark datasets on the RWPSO demonstrate that RWPSO is competitive with other state-of-the-art algorithms from the literature.
  arXiv  Detail & Related papers  (2023-06-04T09:18:02Z)
• 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)
• Different Tunes Played with Equal Skill: Exploring a Unified Optimization Subspace for Delta Tuning [95.72622659619445]
  Delta tuning (DET) is deemed as the new paradigm for using pre-trained language models (PLMs) Up to now, various DETs with distinct design elements have been proposed, achieving performance on par with fine-tuning.
  arXiv  Detail & Related papers  (2022-10-24T14:57:35Z)
• 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)
• 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)
• 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)
• 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)
• The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics [10.946271021892922]
  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.
  arXiv  Detail & Related papers  (2020-02-04T00:57:35Z)

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.