【摘要】着色旅行商问题(Colored Traveling Salesman Problem, CTSP)来源于一类多机器人加工实践应用，在现实生活中有着广泛的应用场景。在CTSP中，每个旅行商各自分配一种特定的颜色，每个城市节点携带一个或者多个旅行商的颜色值，这些城市节点只能被带有相同颜色的旅行商访问。针对CTSP这个NP难问题，本文提出了一种高效的自适应大邻域搜索算法来求解CTSP。该算法包括四个重要的组成部分：一个随机贪心的初始解构造方法、四个专门的破坏操作和修复操作、一个高效的局部搜索程序和一个自适应破坏和修复操作选择机制。在文献中三组标准算例集上的实验结果表明，本文提出的自适应大邻域搜索算法能够高效地求解CTSP问题。