多点多旅行商问题（MTSP）

多点多旅行商问题（MTSP）是指在一个给定的城市集合中，有多个旅行商要分别从一个起点出发，经过所有的城市，最后回到起点。每个旅行商的路径长度之和要最小化。MTSP的基本要素包括目标、机器个体和任务，可以与MTSP的目标、销售人员和城市相匹配。然而，由于工作空间部分重叠，MTSP无法直接用于制造执行系统的调度问题建模。为了解决这个问题，提出了一种新的具有不同颜色城市集的MTSP，称为有色TSP（CTSP）。CTSP是一个普遍的问题，源于但不限于多机系统的调度问题，值得在理论和实践上进行大量的研究。\[1\]

CTSP与传统的TSP和MTSP的组合不同，因为在CTSP中，销售人员以任意顺序访问不同的城市，包括专属城市和共享城市。这导致了CTSP的解决方案空间大小与传统的组合和MTSP不同。因此，CTSP不能转换为TSP和MTSP的组合进行解决。\[2\]

根据证明，具有双染色体编码的MTSP的解决方案大小为n！，而CTSP的解决方案空间大小小于n！。这是因为MTSP的解决方案是将多个TSP和一个MTSP的结果结合起来，而CTSP的解决方案是将多个TSP和MTSP的结果结合起来。因此，CTSP的解空间大小比MTSP小。\[3\]
#### 引用[.reference_title]
- *1* *2* *3* [颜色旅行商问题](https://blog.csdn.net/qq_45874683/article/details/129846762)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v91^control_2,239^v3^insert_chatgpt"}} ] [.reference_item]
[ .reference_list ]