董学士 董文永 蔡永乐

(武汉大学计算机学院 武汉 430072) (dxs_cs@163.com)

着色旅行商问题(colored traveling salesman problem, CTSP)是旅行商问题(traveling salesman problem, TSP)与多旅行商问题(multiple traveling salesman problem, MTSP)的一种扩展模型，CTSP是一种来源于但不局限于多机器工程系统(multi-machine engineering system, MES)的模型，可应用在具有部分重合工作区域的规划[1].为建模有部分重合区域的人员与车辆调配的路线优化问题，本文给出了一种新的模型——着色瓶颈旅行商问题(colored bottleneck traveling salesman problem, CBTSP)，可应用于有合作与单独任务的人员与车辆的路线规划等问题，其目标是最小化所有旅行路线的最大边，具体的应用场景参见1.3节的论述.在智能交通、多任务协作等领域，一些实际问题可用CBTSP来建模，所构建模型的尺度(对应着CBTSP的城市数量)往往趋于大尺度(城市数量1 000或以上)，因此，研究大尺度的CBTSP及其求解算法有一定的意义.

由于CBTSP是本文提出的模型，尚没有相应的求解算法，算法方面的研究主要集中在CTSP模型.东南大学Li等人[2]提出CTSP模型，并用遗传算法求解该问题；之后，Li等人[1]将贪心遗传算法(genetic algorithm with greedy initialization, GAG)、爬山法遗传算法(hill-climbing genetic algorithm, HCGA)与模拟退火遗传算法(simulated annealing genetic algorithm, SAGA)应用在求解小规模的CTSP，即CTSP的城市数量小于等于101.瓶颈旅行商(bottleneck traveling salesman problem, BTSP)[3-10]相关工作有：Vairaktarakis[3]给出了 BTSP是NP完全问题，可应用在工作流的规划领域；BTSP也可应用在重构相邻信息的排序序列[4]；Garfinkel等人[5]将BTSP应用在集成线路的排序；BTSP另一种应用就是最小化状态变化机的排序[7]；BTSP也可以应用于最小化机器的最大变化状态[8]；Ahmed[10]应用遗传算法求解BTSP.元启发式算法的其他相关应用：Liao等人[11]将蚁群算法应用于混合可变的优化问题；Ferreira[12]将一种蚁……