Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Approximate approaches to the traveling thief problem
Author: Faulkner, H.
Polyakovskiy, S.
Schultz, T.
Wagner, M.
Citation: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, 2015 / Silva, S. (ed./s), pp.385-392
Publisher: ACM
Issue Date: 2015
ISBN: 978-1-4503-3472-3
Conference Name: 2015 Annual Conference on Genetic and Evolutionary Computation (GECCO '15) (11 Jul 2015 - 15 Jul 2015 : Madrid, Spain)
Editor: Silva, S.
Statement of
Hayden Faulkner, Sergey Polyakovskiy, Tom Schultz, Markus Wagner
Abstract: This study addresses the recently introduced Traveling Thief Problem (TTP) which combines the classical Traveling Salesman Problem (TSP) with the 0-1 Knapsack Problem (KP). The problem consists of a set of cities, each containing a set of available items with weights and profits. It involves searching for a permutation of the cities to visit and a decision on items to pick. A selected item contributes its profit to the overall profit at the price of higher transportation cost incurred by its weight. The objective is to maximize the resulting profit. We propose a number of problem-specific packing strategies run on top of TSP solutions derived by the Chained Lin-Kernighan heuristic. The investigations provided on the set of benchmark instances prove their rapidity and efficiency when compared with an approximate mixed integer programming based approach and state-of-the-art heuristic solutions from the literature.
Keywords: Traveling thief problem, local search, multi-component problems
Rights: © 2015 ACM. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and, or a fee. Request permissions from permissions,
DOI: 10.1145/2739480.2754716
Grant ID:
Published version:
Appears in Collections:Aurora harvest 3
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access4.51 MBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.