嵌套分区算法是近年来提出的一种求解大规模优化问题的新型全局优化方法。介绍了嵌套分区算法（NPM）的基本思想，将其应用于求解旅行商问题。分析确定了嵌套分区算法各个算子的策略，提出了一种改进的嵌套分区算法。该算法采用加权抽样法求得初始最可能域，用全局数组记录下每个区域的历史最优解，用3-opt局部搜索算法改进每个区域解的质量。对TSPLIB中部分实例仿真结果表明，所提出的结合3-opt算法的改进嵌套分区算法在求解 TSP问题时可以获得高质量的解。