超图定义下的广义着色旅行商问题的理论与方法研究

Starting from engineering practice, the applicant propose the Colored Traveling Salesman Problem (CTSP). CTSP has overcome the issue that the existing Traveling Salesman Problem (TSP), Multiple TSP, and their variants cannot represent the differential city visit among multiple salesmen. It is an important development and breakthrough toward TSP. To make CTSP more general and systematic, this proposal intends to present and study the generalized CTSP theory and solution methods on the basis of the preliminary results achieved. Particularly, it includes the following research tasks. First, proposing the generalized CTSP (GCTSP) by generalizing the city colors and describing by means of hypergraphs instead of graphs and analysis of its generalization performance and computational complexity. Second, mathematically modeling and solution of GCTSP and time window constrained and precedence constrained GCTSP. Third, modeling and solution of four types of dynamic GCTSP subject to the changes of cities, the visit edges, the city colors and the color coefficients. Finally, conducting the application study of the GCTSP theory and methods in logistics distribution. The successful implementation of this proposal will bring important theoretical and practical value, and promote the development of TSP research. Also, it is expected to provide a theoretical support for the solution of a large class of travel optimization problems in the context of complex networks.

申请人从工程实践中所提出的着色旅行商问题（CTSP）解决了现有的旅行商问题（TSP）、多旅行商问题及它们的变体都没法描述多重商人的差别化城市访问的难题，是对TSP理论的一次重要的发展和突破。为使CTSP更具一般性、更加系统化，本项目拟在初步研究成果的基础上，提出并研究广义CTSP理论方法。具体内容包括：（1）提出采用超图（Hypergraph）代替图（Graph）定义的广义CTSP，分析其计算复杂性及其对现有多种旅行商问题的泛化能力；（2）研究广义CTSP以及时间窗约束、优先约束下的广义CTSP的数学建模与求解；（3）研究城市、访问边、城市颜色、颜色系数变化的四类动态的广义CTSP的建模与求解；（4）完成上述的广义CTSP理论方法在物流配送中的应用研究。该项目的成功实施将产生重要的理论和应用价值，推动TSP研究的发展进步，并有望为复杂网络背景下一大类旅行优化问题的解决提供理论方法支撑。

先前提出的着色旅行商问题（CTSP）借助颜色创新地实现了商人和城市之间的访问匹配关系的描述，是对旅行商问题理论的重要突破和发展，统一和泛化了现有多种旅行商问题。针对现有的CTSP的颜色单调、优化目标单一、未考虑约束和动态性的问题，本项目开展了广义CTSP理论方法的研究，完成的主要工作如下：首先，采用超图代替图来定义CTSP，借助超图的关联矩阵（颜色矩阵）实现了对商人与城市之间的访问匹配关系的完全描述，形成了广义CTSP模型，并提出大规模问题的高效求解方法。其次，提出了有约束、多目标广义CTSP模型，分别设计了针对时窗约束、优先约束和无约束双目标的三种广义CTSP的元启发算法，各算法在收敛性和解质量上均有突出表现。再次，建立了城市边权和城市颜色变化两类动态CTSP模型，设计了基于种群迁移的元启发算法，实现动态最优解的有效跟踪。最后，完成广义CTSP理论方法在物流配送、仓储、港口场景中的实验与应用研究，验证了理论方法的正确性和效果。上述研究已取得了突出成果，达成预期目标。共发表（录用）高质量论文18篇，12篇为IEEE Trans. Cybernetics、IEEE T SMC: Systems、IEEE Trans. Intelligent Transportation System等顶刊论文；指导的博士学位论文已被推荐参评优秀学位论文；已申请发明专利7份。部分成果已达到国际领先水平，其中提出的大规模广义CTSP的求解方法远高于现有求解规模和水平，将CTSP的研究推向一个新高潮，对应论文已入选2021年ESI高被引论文。广义CTSP的理论方法具有广阔的应用前景和推广价值。它作为一种统一的建模与求解方法，广泛适应于各种多机多任务系统的作业调度、路径规划等次序决策问题的建模和求解，多个应用合作已在开展中。为实现广泛的工程应用，理论方法的进一步完善和工具化是课题组的下一步重点研究方向。