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

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

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.