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 进行访问。