Abstract
The traveling thief problem (TTP) is fast gaining attention for being a challenging combinatorial optimization problem. A number of algorithms have been proposed for solving this problem in the recent past. Despite being a challenging problem, it is often argued if TTP is realistic enough because of its formulation, which only allows a single thief to travel across hundreds or thousands of cities to collect (steal) items. In addition, the thief is required to visit all cities, regardless of whether an item is stolen there or not. In this paper we discuss the shortcomings of the current formulation and present a relaxed version of the problem which allows multiple thieves to travel across different cities with the aim of maximizing the group's collective profit. A number of fast heuristics for solving the newly proposed multiple traveling thieves problem (MTTP) are also proposed and evaluated.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 2016 Genetic and Evolutionary Computation Conference |
| Editors | Frank Neumann |
| Place of Publication | New York NY USA |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 293-300 |
| Number of pages | 8 |
| ISBN (Electronic) | 9781450342063 |
| DOIs | |
| Publication status | Published - 2016 |
| Externally published | Yes |
| Event | The Genetic and Evolutionary Computation Conference 2016 - Hyatt Regency Denver Tech Center, Denver, United States of America Duration: 20 Jul 2016 → 24 Jul 2016 Conference number: 18th http://gecco-2016.sigevo.org/index.html/ https://dl.acm.org/doi/proceedings/10.1145/2908812 (Proceedings) |
Conference
| Conference | The Genetic and Evolutionary Computation Conference 2016 |
|---|---|
| Abbreviated title | GECCO 2016 |
| Country/Territory | United States of America |
| City | Denver |
| Period | 20/07/16 → 24/07/16 |
| Internet address |
Keywords
- Combinatorial optimization
- Knapsack problem
- Traveling salesman problem
- Traveling thief problem