Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/82585
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | The travelling thief problem: the first step in the transition from theoretical problems to realistic problems |
Author: | Bonyadi, M. Michalewicz, Z. Barone, L. |
Citation: | 2013 IEEE Congress on Evolutionary Computation, Cancun, Mexico, 20-23 June 2013: pp.1078-1044 |
Publisher: | IEEE |
Publisher Place: | United States |
Issue Date: | 2013 |
ISBN: | 9781479904525 |
Conference Name: | IEEE Congress on Evolutionary Computation (2013 : Cancun, Mexico) |
Statement of Responsibility: | Mohammad Reza Bonyadi, Zbigniew Michalewicz, Luigi Barone |
Abstract: | There are some questions concerning the applicability of meta-heuristic methods for real-world problems; further, some researchers claim there is a growing gap between research and practice in this area. The reason is that the complexity of real-world problems is growing very fast (e.g. due to globalisation), while researchers experiment with benchmark problems that are fundamentally the same as those of 50 years ago. Thus there is a need for a new class of benchmark problems that reflect the characteristics of real-world problems. In this paper, two main characteristics of real-world problems are introduced: combination and interdependence. We argue that real-world problems usually consist of two or more sub-problems that are interdependent (to each other). This interdependence is responsible for the complexity of the real-world problems, while the type of complexity in current benchmark problems is missing. A new problem, called the travelling thief problem, is introduced; it is a combination of two well-known problems, the knapsack problem and the travelling salesman problem. Some parameters which are responsible for the interdependence of these two sub-problems are defined. Two sets of parameters are introduced that result in generating two instances of the travelling thief problem. The complexities that are raised by interdependences for these two instances are discussed in detail. Finally, a procedure for generating these two instances is given. |
Keywords: | Real-world problems NP-hard problems combinatorial benchmark problems complexity |
Rights: | © 2013 IEEE |
DOI: | 10.1109/CEC.2013.6557681 |
Grant ID: | http://purl.org/au-research/grants/arc/DP0985723 http://purl.org/au-research/grants/arc/DP1096053 http://purl.org/au-research/grants/arc/DP130104395 http://purl.org/au-research/grants/arc/DP1096053 http://purl.org/au-research/grants/arc/DP0985723 |
Description (link): | http://www.cec2013.org/ |
Published version: | http://dx.doi.org/10.1109/cec.2013.6557681 |
Appears in Collections: | Aurora harvest 4 Computer Science publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
RA_hdl_82585.pdf Restricted Access | Restricted Access | 812.56 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.