A weighted-sum method for solving the bi-objective traveling thief problem
Many real-world optimization problems have multiple interacting components. Each of these can be NP-hard and they can be in conflict with each other, i.e., the optimal solution for one component does not necessarily represent an optimal solution for the other components. This can be a challenge for single-objective formulations, where the respective influence that each component has on the overall solution quality can vary from instance to instance. In this paper, we study a bi-objective formulation of the traveling thief problem, which has as components the traveling salesperson problem and the knapsack problem. We present a weighted-sum method that makes use of randomized versions of existing heuristics, that outperforms participants on 6 of 9 instances of recent competitions, and that has found new best solutions to 379 single-objective problem instances.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Efficiently solving the thief orienteering problem with a max-min ant colony optimization approach
We tackle the Thief Orienteering Problem (ThOP), an academic multi-component problem that combines two classical combinatorial problems, namely the Knapsack Problem and the Orienteering Problem. In the ThOP, a thief has …
BenchmarkingOptimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
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) ad…
The Node Weight Dependent Traveling Salesperson Problem: Approximation Algorithms and Randomized Search Heuristics
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 (…
Leveraging Symbolic Regression for Heuristic Design in the Traveling Thief Problem
The Traveling Thief Problem is an NP-hard combination of the well known traveling salesman and knapsack packing problems. In this paper, we use symbolic regression to learn useful features of near-optimal packing plans, …
regressionSymbolic RegressionExact Approaches for the Travelling Thief Problem
Many evolutionary and constructive heuristic approaches have been introduced in order to solve the Traveling Thief Problem (TTP). However, the accuracy of such approaches is unknown due to their inability to find global …