The travelling thief problem: The first step in the transition from theoretical problems to realistic problems
The travelling thief problem: The first step in the transition from theoretical problems to realistic problems
复制标题
旅行小偷问题：从理论问题转向现实问题的第一步
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
L. Barone
中科院分区：
文献类型：
--
作者：
M. Bonyadi;Z. Michalewicz;L. Barone
关于元启发式方法在现实问题中的适用性存在一些问题；此外，一些研究人员声称，这一领域的研究与实践之间的差距越来越大。原因是现实世界问题的复杂性增长非常快（例如，由于全球化），而研究人员对基准问题的实验与50年前的基本相同。因此，需要一类新的基准问题来反映现实世界问题的特征。本文介绍了现实问题的两个主要特征：组合和相互依赖。我们认为，现实世界的问题通常由两个或多个相互依赖的子问题组成。这种相互依赖导致了现实世界问题的复杂性，而当前基准问题中的复杂性类型却缺失了。引入了一个新的问题——行窃问题；它是两个著名问题的组合，背包问题和旅行推销员问题。定义了决定这两个子问题相互依赖关系的一些参数。引入了两组参数，产生了两个行贼问题的实例。详细讨论了这两个实例的相互依赖性所带来的复杂性。最后给出了这两个实例的生成过程。
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.
影响因子：
3.6
作者：
Burke, Edmund K.;Gendreau, Michel;Qu, Rong
通讯作者：
Qu, Rong