最短路径问题又称为旅行商问题(Traveling Saleman Problem,TSP),此问题是数学中的组合优化问题之一,也是物流业中讨论的热门话题。对该问题进行讨论和深入的研究具有重要的理论意义和现实意义。首先,本文介绍了解决组合优化问题的四种算法如分支定界算法、动态规划算法、蚁群算法和粒子群算法,接着介绍了一种新的求解组合优化问题的算法---智能水滴算法,并证明了它的收敛性,讨论了该算法的优缺点,并将其应用到最短路径问题中,通过小规模的实例验证了该算法的可行性和有效性。其次,本文提出了一种具有变异特性的智能水滴算法。考虑到智能水滴算法在处理大规模旅行商问题(最短路径问题)时存在一定的局限性,如搜索到最优解的质量不高或搜索到最优解时所需要时间较长等问题,本文在智能水滴算法的基础上加入变异机制的作用,借用逆转变异的方法,利用2-opt方法简便高效的特点,提出了具备变异特性的智能水滴算法。该算法的基本思想是让算法搜索到的最优路径经过变异的作用,得到新的解(新的路径),从而可以提高最优解的质量,进而提高整个群体的性能。又因为变异的次数是随机性的并且变异的这个过程用到的运算量比智能水滴算法中的迭代过程要简便的多,从而在运算量上节省了时间,进而提高了算法的收敛速度。最后,通过MATLAB7.0实现了具备变异特性的智能水滴算法,并对中国10个城市和34个城市的TSP问题,分别采用智能水滴算法和改进的智能水滴算法进行仿真实验,结果表明改进的智能水滴算法相较于智能水滴算法,在求解小规模(10个城市)问题时虽然没有相对的优劣势,但在求解相对大规模(34个城市)问题时,表现出相对的优势,它不仅提高了最优解的质量而且加快了算法的收敛速度,故该改进算法具有一定的可行性和有效性。