论文标题
根据项目选择权重和反向订单分配解决旅行小偷问题
Solving the Travelling Thief Problem based on Item Selection Weight and Reverse Order Allocation
论文作者
论文摘要
旅行小偷问题（TTP）是一个具有挑战性的组合优化问题，吸引了许多学者。 TTP互连了两个众所周知的NP障碍问题：旅行推销员问题（TSP）和0-1 knapsack问题（KP）。已经提出了越来越多的算法来解决这个新的问题，该问题结合了两个相互依存的子问题。在本文中，TTP在理论上和经验上进行了研究。根据评分值，提出了基于我们提出的公式在采摘项目和对项目中排序项目中提出的公式计算的分数值的算法，以解决问题。比较和分析了解决TTP的不同方法；实验研究表明，我们提出的方法在满足或击败当前最新的启发式解决方案上非常有效。
The Travelling Thief Problem (TTP) is a challenging combinatorial optimization problem that attracts many scholars. The TTP interconnects two well-known NP-hard problems: the Travelling Salesman Problem (TSP) and the 0-1 Knapsack Problem (KP). Increasingly algorithms have been proposed for solving this novel problem that combines two interdependent sub-problems. In this paper, TTP is investigated theoretically and empirically. An algorithm based on the score value calculated by our proposed formulation in picking items and sorting items in the reverse order in the light of the scoring value is proposed to solve the problem. Different approaches for solving the TTP are compared and analyzed; the experimental investigations suggest that our proposed approach is very efficient in meeting or beating current state-of-the-art heuristic solutions on a comprehensive set of benchmark TTP instances.
