旅行商问题即TSP(Traveling Salesman Problem)是组合优化问题中的经典问题,同时也是NP难问题之一,已成为研究重点。蚁群算法由于具有分布式计算、组织性、正反馈、鲁棒性等优点,同时还易于与其他算法相结合,被广泛应用于组合优化问题的求解上。但蚁群算法也存在着自身的不足,在求解问题时易于进入停滞状态和求解质量不好等缺点。基于上述情况,在阅读相关文献和书籍的基础上,本文从蚁群算法的缺点着手,并结合求解路径规划TSP问题的已有优化算法和有关图论模型,提出了一种基于动态凸包引导的偏优规划蚁群算法(ACADCG)来求解TSP问题。此外在上述改进算法的基础上本文又针对收敛速度进行了进一步的改进,提出一种基于重构Sigmoid函数的S-ACADCG算法。论文的主要研究及算法改进方面包括:1、在蚂蚁的城市节点选择范围方面,针对蚂蚁起始期间选择范围空间大的缺陷,根据蚂蚁的遍历效果对蚂蚁的城市节点选择范围进行动态控制。此策略将缩小搜索空间,节省搜索时间,同时有利于对蚂蚁遍历方向的了解与控制。2、在城市节点选择策略方面,为了避免蚁群算法较早的陷入局部最优和提高解的质量,将延陷漂流因子和二维凸包引入其中。延陷漂流因子能增加算法运行前期蚂蚁遍历解的多样性,同时用蚂蚁每到一个城市就与其邻居节点构建的二维凸包,来引导当前蚂蚁的走向,即对最近己构建凸包区域范围交集中未访问的节点进行优先遍历,以防蚂蚁跳出附近的点,避免蚂蚁后续折回遍历之前未访问过的节点,减少因折回原因而可能形成的非优路径,提高当前蚂蚁的遍历质量。3、在信息素更新方面,利用已遍历路径上所构建的二维凸包来获取蚂蚁已走过路径的方向,即用已构建的凸包及存在的凸包角来改进信息素更新公式来弱化引起非优路径出现的边上信息素及非优路径上信息素,引导后继蚂蚁路径偏优规划,减少非优路径的产生。此外为了更进一步对蚁群算法进行调控,基于蚂蚁分类采用两种不同步的全局信息素更新方式,同时将局部路径信息与整体路径信息也融入其中,来提高算法的求解精度。4、在信息素控制策略方面,为了更进一步减少蚁群算法的迭代次数,根据算法在不同时期的迭代特征并结合原始Sigmoid函数,对Sigmoid函数进行重构,然后将其与原始信息素上下限值控制公式相结合,来对算法前期、中期、后期的信息素进行不同程度的控制,既抑制了由于边与边上信息素浓度差距过大而引起算法停滞现象的发生,又提高了算法的收敛速度。