Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108006
Citations | ||
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 1611-3349 |
Conference Name: | 10th International Conference on Swarm Intelligence (ANTS) (7 Sep 2016 - 9 Sep 2016 : Brussels, Belgium) |
Statement of Responsibility: | 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: | http://dx.doi.org/10.1007/978-3-319-44427-7_25 |
Appears in Collections: | Aurora harvest 3 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_108006.pdf Restricted Access | Restricted Access | 1.59 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.