Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem
Author: Wagner, M.
Citation: Lecture Notes in Artificial Intelligence, 2016, vol.9882 LNCS, pp.273-281
Publisher: Springer
Issue Date: 2016
Series/Report no.: Lecture Notes in Computer Science
ISBN: 9783319444260
ISSN: 0302-9743
Conference Name: 10th International Conference on Swarm Intelligence (ANTS) (7 Sep 2016 - 9 Sep 2016 : Brussels, Belgium)
Statement of
Markus Wagner
Abstract: The travelling thief problem (TTP) is an academic combinatorial optimisation problem in which its two components, namely the travelling salesperson problem (TSP) and the knapsack problem, interact. The goal is to provide to a thief a tour across all given cities and a packing plan that defines which items should be taken in which city. The combining elements are the knapsack’s renting rate that is to be paid for the travel time, and the thief’s slowdown with increasing knapsack use. Previously, successful algorithms focussed almost exclusively on constructing packing plans for near-optimal TSP tours. Even though additional hill-climbers are used at times, this strong initial bias prevents them from finding better solutions that require longer tours that can give rise to more profitable packing plans. Our swarm intelligence approach shifts the focus away from good TSP tours to good TTP tours. In our study we observe that this is effective and computationally efficient, as we outperform state-of-the-art approaches on instances with up to 250 cities and 2000 items, sometimes by more than 10%
Keywords: MAX-MIN ant system; Travelling thief problem
Rights: © Springer International Publishing Switzerland 2016
DOI: 10.1007/978-3-319-44427-7_25
Published version:
Appears in Collections:Aurora harvest 3
Computer Science publications

Files in This Item:
File Description SizeFormat 
  Restricted Access
Restricted Access1.59 MBAdobe PDFView/Open

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