Abstract: The Traveling Thief Problem（TTP） is a composite optimization problem which combines the Traveling Salesman Problem（TSP） with the Knapsack Problem（KP）, and has an accumulated computational complexity caused by these two problems. In this paper, based on the original version of TTP, a new optimization model with probability distribution information is firstly proposed by considering that the thief doesn’t explicitly know the item location in advance in all cities. Then, by calculating the effective value of each item, a selection scheme of items is provided. Finally, taking advantage of a present genetic algorithm for solving TSP and a designed local search scheme, a new hybrid genetic algorithm is developed for dealing with the new TTP model. The simulation results show the proposed algorithm is feasible and efficient.

Key words: traveling thief problem, genetic algorithm, effective value, maximum profit

摘要： 流窜犯问题（Traveling Thief Problem，TTP）是旅行商问题和背包问题的一个组合问题，同时具有两个问题的计算复杂度。在现有TTP问题中考虑了小偷提前不知道物品具体位置的情况，给出了新的具有概率分布信息的优化模型；利用有效价值指标，给出了物品的选取方法；基于一个TSP的遗传算法框架和新设计的局部搜索策略，提出了求解该模型的混合遗传算法。数值仿真结果表明，提出的算法是可行有效的。

关键词: 流窜犯问题, 遗传算法, 有效价值, 最大收益