树上的最小-最大k旅行商问题(Min-Max k-TSPT)指的是,给定一棵边权树T=(V,E),一个仓库s以及k个相同的旅行商,其中k是与输入无关的固定常数,Min-Max k-TSPT需要找到一个k条回路的集合,每条回路都从s点出发并返回s点,我们需要在保证k个旅行商可以通过这k条回路服务到所有位于树中结点上的顾客的同时,最小化其中最长回路的长度。本文对于Min-Max k-TSPT以及它的多仓库推广问题给出了新的经过简化的拟多项式时间精确算法。基于该简化方法,我们为Min-Max k-TSPT与其多仓库扩展的若干自然变种问题分别设计了拟多项式时间精确算法。此外,通过使用标准的舍入和缩放技术,我们将本文中提出的拟多项式时间精确算法转换为完全多项式时间近似方案(FPTAS),即对于任意ε>0,可以给出多项式时间的(1+ε)近似算法。本文第一章介绍了本文的研究背景和基本概念,对组合优化问题进行了概括性的阐述,介绍了本文研究的基础——旅行商问题,同时还介绍了前人们在本文相关问题上已经取得的成果。第二章介绍了本文所研究的问题以及本文中所用到的一些符号,此外还介绍了将本文的实例进行标准化以及节点编号有序化的准备工作。第三章对于树上的最小-最大k旅行商问题给出了经过改良的拟多项式时间精确算法,并在此基础上对于树上的最小-最大k路覆盖问题给出了拟多项式时间精确算法。第四章对于三个多仓库推广问题给出了拟多项式时间精确算法,分别是树上的多仓库最小-最大k树覆盖问题、树上的多仓库最小-最大k路覆盖问题以及树上的多仓库最小-最大k邮递员覆盖问题。第五章对于第三章与第四章中提出的拟多项式时间精确算法给出了对应的完全多项式时间近似方案。第六章对本文进行了总结,并给出了未来还可以进行研究的方向。