A travelling thief problem (TTP) is a proxy to real-life problems such as
postal collection. TTP comprises an entanglement of a travelling salesman
problem (TSP) and a knapsack problem (KP) since items of KP are scattered over
cities of TSP, and a thief has to visit cities to collect items. In TTP, city
selection and item selection decisions need close coordination since the
thief's travelling speed depends on the knapsack's weight and the order of
visiting cities affects the order of item collection. Existing TTP solvers deal
with city selection and item selection separately, keeping decisions for one
type unchanged while dealing with the other type. This separation essentially
means very poor coordination between two types of decision. In this paper, we
first show that a simple local search based coordination approach does not work
in TTP. Then, to address the aforementioned problems, we propose a human
designed coordination heuristic that makes changes to collection plans during
exploration of cyclic tours. We further propose another human designed
coordination heuristic that explicitly exploits the cyclic tours in item
selections during collection plan exploration. Lastly, we propose a machine
learning based coordination heuristic that captures characteristics of the two
human designed coordination heuristics. Our proposed coordination based
approaches help our TTP solver significantly outperform existing
state-of-the-art TTP solvers on a set of benchmark problems. Our solver is
named Cooperation Coordination (CoCo) and its source code is available from
this https URL

本研究提出了一种基于协调的解决方案以提高旅行窃贼问题（TTP）求解器的性能，并通过利用循环路径在物品选择时进行协调。我们还建议一种基于机器学习的协调启发式算法，通过捕捉两种人类设计协调启发式算法的特征来进一步提高性能。最终，我们的求解器名为 Cooperation Coordination（CoCo）并且其源代码可从给定的 URL 进行访问。

基于协调方法解决旅行窃贼问题

Solving Travelling Thief Problems using Coordination Based Methods

Since its inception in 2013, the Travelling Thief Problem (TTP) has been
widely studied as an example of problems with multiple interconnected
sub-problems. The dependency in this model arises when tying the travelling
time of the "thief" to the weight of the knapsack. However, other forms of
dependency as well as combinations of dependencies should be considered for
investigation, as they are often found in complex real-world problems. Our goal
is to study the impact of different forms of dependency in the TTP using a
simple local search algorithm. To achieve this, we use Local Optima Networks, a
technique for analysing the fitness landscape.

本文主要研究尝试不同形式的 TTP（Travelling Thief Problem）依赖性对于简单局部搜索算法的影响，使用适应性景观分析技术进行分析，旨在探讨复杂实际问题的多个相互关联子问题的依赖性。