Dynamic programming operators for the bi-objective Traveling Thief Problem
- 1 July 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-8
Abstract
The traveling thief problem (TTP) has emerged as a realistic multi-component problem that poses a number of challenges to traditional optimizers. In this paper we propose different ways to incorporate dynamic programming (DP) as a local optimization operator of population-based approaches to the biobjective TTP. The DP operators use different characterizations of the TTP instance to search for packing plans that improve the best current solutions. We evaluate the efficiency of the DP-based operators using TTP instances of up to 33810 cities and 338100 items, and compare the results of the DP operators with state-of-the-art algorithms for these instances. Our results show that DP-based approaches, applied individually and in combination with other types of operators, can produce good approximations of the Pareto sets for these problems.Keywords
This publication has 18 references indexed in Scilit:
- Efficiently solving the Traveling Thief Problem using hill climbing and simulated annealingInformation Sciences, 2018
- A comparison of probabilistic-based optimization approaches for vehicle routing problems2017
- A case study of algorithm selection for the traveling thief problemJournal of Heuristics, 2017
- Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms2017
- An Evolutionary Approach to the Full Optimization of the Traveling Thief Problem2016
- Heuristic evolution with genetic programming for traveling thief problem2015
- On investigation of interdependence between sub-problems of the Travelling Thief ProblemSoft Computing, 2014
- A comprehensive benchmark set and heuristics for the traveling thief problem2014
- Improving Efficiency of Heuristics for the Large Scale Traveling Thief Problem2014
- The travelling thief problem: The first step in the transition from theoretical problems to realistic problems2013