Multiple Traveling Salesman Problem (MTSP) is an important combinatorial optimization problem. However, it is applicable to only the cases in which multiple executing individuals (traveling salesman) share the common workspace (city set). It cannot be used to handle many multi-machine engineering systems where multiple machines' workspaces are not the same and partially overlap with each other This paper proposes and formulates a new MTSP called colored traveling salesman problem (CTSP). Each of its salesmen is assigned a private city set and all salesmen share a public city set. Every set of cities is colored differently. To solve CTSP, we present two improved genetic algorithms (GA) by combining the classic one with a greedy algorithm and hill-climbing one to achieve better performance Finally, the algorithms are applied and compared through a case study. The result shows that the hill-climbing GA enjoys the best performance among the investigated ones.