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

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