Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation

• URL: http://arxiv.org/abs/2012.08888v1
• Date: Wed, 16 Dec 2020 12:06:05 GMT
• Title: Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation
• Authors: Lei Yang, Zitong Zhang, Xiaotian Jia, Peipei Kang, Wensheng Zhang, Dongya Wang
• Abstract summary: 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.
• Score: 8.620967398331265
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem that attracts many scholars. The TTP interconnects two well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1 Knapsack Problem (KP). Increasingly algorithms have been proposed for solving this novel problem that combines two interdependent sub-problems. 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 in the light of the scoring value is proposed to solve the problem. Different approaches for solving the TTP are compared and analyzed; the experimental investigations suggest that our proposed approach is very efficient in meeting or beating current state-of-the-art heuristic solutions on a comprehensive set of benchmark TTP instances.

Related papers

• 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)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Thought Propagation: An Analogical Approach to Complex Reasoning with Large Language Models [62.96551299003463]
  We propose textbftextitThought Propagation (TP) to enhance the complex reasoning ability of Large Language Models. TP first prompts LLMs to propose and solve a set of analogous problems that are related to the input one. TP reuses the results of analogous problems to directly yield a new solution or derive a knowledge-intensive plan for execution to amend the initial solution obtained from scratch.
  arXiv  Detail & Related papers  (2023-10-06T01:40:09Z)
• 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)
• Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding [25.11387753357413]
  We study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally.
  arXiv  Detail & Related papers  (2022-08-02T03:17:29Z)
• 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)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)
• 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)
• A Non-Dominated Sorting Based Customized Random-Key Genetic Algorithm for the Bi-Objective Traveling Thief Problem [7.088487500434561]
  We propose a method to solve a bi-objective variant of the well-studied Traveling Thief Problem (TTP) We address the BI-TTP, where the goal is to minimize the overall traveling time and to maximize the profit of the collected items. Our proposed method is based on a biased-random key genetic algorithm with customizations addressing problem-specific characteristics.
  arXiv  Detail & Related papers  (2020-02-11T10:56:13Z)

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.